Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-svg

Source of release 0.9.1

0.9.1 / src / svg / coverage.lucb

#==============================================================================================
#
#   svg/coverage - The exact-area coverage rasteriser and the 8-bit mask
#
#   DESCRIPTION:
#       Scan conversion shared by both rasterisers: edges accumulate signed area into a
#       row-major buffer (one spare cell per row), and a prefix sum along each row turns it
#       into per-pixel coverage, which is exact for polygons. Fills trace an element's
#       outlines as they are (strokes are traced in stroke.lucb). `rasterize` resolves each
#       contour into an 8-bit mask, the higher value winning where shapes overlap.
#
#==============================================================================================

## Where the drawing lands in a `width` by `height` pixel bitmap: scaled to fit
## uniformly and centred, as an icon is fitted to its slot.
struct Placement:
    var scale: f64
    var offset_x: f64
    var offset_y: f64

func placement(drawing: const Drawing*, width: u32, height: u32) -> Placement:
    let scale = math.min((f64)width / drawing.view_w, (f64)height / drawing.view_h)
    return Placement(scale = scale, offset_x = ((f64)width - drawing.view_w * scale) * 0.5, offset_y = ((f64)height - drawing.view_h * scale) * 0.5)

## Signed-area accumulation of one edge into `acc` (width + 1 cells per row), the
## exact-area method font rasterisers use: after a prefix sum along each row,
## a cell holds the winding-weighted coverage of that pixel. The edge is first
## cut where it crosses the bitmap's left and right sides: a piece to the left
## counts only its winding, at the first column, and a piece to the right lands
## in the spare cell. So a window of a drawing (a canvas cell) covers its pixels
## exactly as the whole drawing does.
func accumulate(acc: f32[], width: usize, height: usize, x0: f64, y0: f64, x1: f64, y1: f64):
    if y0 == y1:
        return
    let right = (f64)width
    # Where the edge crosses x = 0 and x = width, as fractions along it, in order.
    var first = 2.0
    var second = 2.0
    if x1 != x0:
        let at_left = (0.0 - x0) / (x1 - x0)
        let at_right = (right - x0) / (x1 - x0)
        if at_left > 0.0 and at_left < 1.0:
            first = at_left
        if at_right > 0.0 and at_right < 1.0:
            if first > 1.0:
                first = at_right
            elif at_right < first:
                second = first
                first = at_right
            else:
                second = at_right
    if first > 1.0:
        accumulate_piece(acc, width, height, clamp_x(x0, right), y0, clamp_x(x1, right), y1)
        return
    accumulate_part(acc, width, height, x0, y0, x1, y1, 0.0, first)
    if second > 1.0:
        accumulate_part(acc, width, height, x0, y0, x1, y1, first, 1.0)
        return
    accumulate_part(acc, width, height, x0, y0, x1, y1, first, second)
    accumulate_part(acc, width, height, x0, y0, x1, y1, second, 1.0)

## The part of edge (`x0`, `y0`)–(`x1`, `y1`) from fraction `ta` to `tb`, which lies
## wholly on one side of each of the bitmap's sides: to the left it counts only its
## winding, at the first column; to the right it lands in the spare cell.
func accumulate_part(acc: f32[], width: usize, height: usize, x0: f64, y0: f64, x1: f64, y1: f64, ta: f64, tb: f64):
    let right = (f64)width
    let ya = y0 + (y1 - y0) * ta
    let yb = y0 + (y1 - y0) * tb
    let xa = x0 + (x1 - x0) * ta
    let xb = x0 + (x1 - x0) * tb
    let middle = (xa + xb) * 0.5
    if middle <= 0.0:
        accumulate_piece(acc, width, height, 0.0, ya, 0.0, yb)
    elif middle >= right:
        accumulate_piece(acc, width, height, right, ya, right, yb)
    else:
        accumulate_piece(acc, width, height, clamp_x(xa, right), ya, clamp_x(xb, right), yb)

## `x` held within 0..`right`, where a piece that only grazes a side is put.
func clamp_x(x: f64, right: f64) -> f64:
    return math.clamp(x, 0.0, right)

## `accumulate` for an edge within the bitmap's columns.
func accumulate_piece(acc: f32[], width: usize, height: usize, x0: f64, y0: f64, x1: f64, y1: f64):
    if y0 == y1:
        return
    let stride = width + 1
    let direction: f64 = 1.0 if y1 > y0 else -1.0
    var top = y0
    var bottom = y1
    var left = x0
    var right = x1
    if direction < 0.0:
        top = y1
        bottom = y0
        left = x1
        right = x0
    let dxdy = (right - left) / (bottom - top)
    var x = left
    var row = (usize)math.max(0.0, math.floor(top))
    if top < 0.0:
        x -= top * dxdy
    let last_row = (usize)math.min((f64)height, math.ceil(bottom))
    while row < last_row:
        let row_top = math.max(top, (f64)row)
        let row_bottom = math.min(bottom, (f64)(row + 1))
        let dy = row_bottom - row_top
        let x_next = x + dxdy * dy
        let base = row * stride
        # The piece lies within the columns; rounding along it must not step outside.
        var xa = math.clamp(x, 0.0, (f64)width)
        var xb = math.clamp(x_next, 0.0, (f64)width)
        if xa > xb:
            let swap = xa
            xa = xb
            xb = swap
        let xa_floor = math.floor(xa)
        let xa_index = (i64)xa_floor
        let xb_index = (i64)math.ceil(xb)
        if xa_index < 0 or xb_index > (i64)width + 1:
            # Off the bitmap: only its winding matters for what lies to the right.
            if xa_index < 0:
                acc[base] += (f32)(direction * dy)
            else:
                x = x_next
                row += 1
                continue
        elif xa_index + 1 >= xb_index:
            # Within one column: split the area between it and the next, which for an
            # edge in the spare cell lies past the row and is dropped.
            let coverage = (xa_floor + 1.0 - (xa + xb) * 0.5)
            acc[base + (usize)xa_index] += (f32)(direction * dy * coverage)
            if (usize)xa_index < width:
                acc[base + (usize)xa_index + 1] += (f32)(direction * dy * (1.0 - coverage))
        else:
            # Across several columns: the exact-area split font rasterisers use.
            let d = direction * dy
            let s = 1.0 / (xb - xa)
            let xa_frac = xa - xa_floor
            let a0 = 0.5 * s * (1.0 - xa_frac) * (1.0 - xa_frac)
            let xb_frac = xb - (f64)xb_index + 1.0
            let am = 0.5 * s * xb_frac * xb_frac
            acc[base + (usize)xa_index] += (f32)(d * a0)
            if xb_index == xa_index + 2:
                acc[base + (usize)xa_index + 1] += (f32)(d * (1.0 - a0 - am))
            else:
                let a1 = s * (1.5 - xa_frac)
                acc[base + (usize)xa_index + 1] += (f32)(d * (a1 - a0))
                var column = xa_index + 2
                while column < xb_index - 1:
                    acc[base + (usize)column] += (f32)(d * s)
                    column += 1
                let a2 = a1 + (f64)(xb_index - xa_index - 3) * s
                acc[base + (usize)(xb_index - 1)] += (f32)(d * (1.0 - a2 - am))
            if (usize)xb_index <= width:
                acc[base + (usize)xb_index] += (f32)(d * am)
        x = x_next
        row += 1

## Accumulate a closed polygon of pixel-space points, oriented so its area counts positive.
func accumulate_polygon(acc: f32[], width: usize, height: usize, polygon: const Point[]):
    if polygon.length < 3:
        return
    var area = 0.0
    for index in 0..<polygon.length:
        let a = polygon[index]
        let b = polygon[(index + 1) % polygon.length]
        area += a.x * b.y - b.x * a.y
    for index in 0..<polygon.length:
        var a = polygon[index]
        var b = polygon[(index + 1) % polygon.length]
        if area < 0.0:
            let swap = a
            a = b
            b = swap
        accumulate(acc, width, height, a.x, a.y, b.x, b.y)

## Resolve the accumulator into `coverage` at `opacity`, taking the higher value
## where shapes overlap, then clear it for the next shape.
func resolve_coverage(acc: f32[], width: usize, height: usize, opacity: f64, coverage: u8[]):
    let stride = width + 1
    for row in 0..<height:
        var sum: f32 = 0.0
        for column in 0..<width:
            sum += acc[row * stride + column]
            acc[row * stride + column] = 0.0
            let value = math.min(1.0, math.abs((f64)sum)) * opacity
            let byte = (u8)(value * 255.0 + 0.5)
            let slot = row * width + column
            if byte > coverage[slot]:
                coverage[slot] = byte
        acc[row * stride + width] = 0.0

## Accumulate a contour's outline for filling; its winding is the author's.
func trace_fill(acc: f32[], width: usize, height: usize, drawing: const Drawing*, contour: Contour, fit: Placement):
    let origin = contour.start
    let count = contour.length
    for index in 0..<count:
        let a = drawing.points[origin + index]
        let b = drawing.points[origin + (index + 1) % count]
        accumulate(acc, width, height, fit.offset_x + a.x * fit.scale, fit.offset_y + a.y * fit.scale, fit.offset_x + b.x * fit.scale, fit.offset_y + b.y * fit.scale)

## Check a bitmap's size and allocate a cleared accumulator for it.
func accumulator(width: u32, height: u32) -> f32[]!:
    if width == 0 or height == 0 or width > 4096 or height > 4096:
        error(invalid, "a bitmap is 1..4096 pixels on a side")
    let acc = try new f32[((usize)width + 1) * (usize)height] --- in memory.heap
    for index in 0..<acc.length:
        acc[index] = 0.0
    return acc

## Rasterise `drawing` into `coverage`, `width * height` bytes, top-down: 255 where
## a fill or stroke covers a pixel fully, less along edges and under partial opacity.
## Strokes get their width, caps, joins and dashes; fills use the nonzero rule.
## Colors are ignored: this is the mask a caller tints, as luce-ui does for icons.
pub func rasterize(drawing: const Drawing*, width: u32, height: u32, coverage: u8[]) -> !:
    let acc = try accumulator(width, height)
    defer free(acc) in memory.heap
    if coverage.length != (usize)width * (usize)height:
        error(invalid, "the coverage buffer must hold width * height bytes")
    for index in 0..<coverage.length:
        coverage[index] = 0
    let w = (usize)width
    let h = (usize)height
    let fit = placement(drawing, width, height)
    for contour_index in 0..<drawing.contour_used:
        let contour = drawing.contours[contour_index]
        if contour.length < 1:
            continue
        if contour.fill.painted and contour.length >= 3:
            trace_fill(acc, w, h, drawing, contour, fit)
            resolve_coverage(acc, w, h, contour.fill_opacity, coverage)
        if contour.stroke.painted:
            try trace_stroke(acc, w, h, drawing, contour, fit)
            resolve_coverage(acc, w, h, contour.stroke_opacity, coverage)