dymokomi/luce-svg
Source of release 0.9.2
0.9.2 / 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
# element's fill, then its stroke, into an 8-bit mask, composited source-over as
# rgba.lucb composites colors, so a mask is the alpha a full renderer draws.
#
#==============================================================================================
## 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)
## The coverage of a pixel whose accumulated winding is `sum`: nonzero clamps it to
## one; even-odd folds it, so a pixel covered twice is empty (exact for whole windings,
## the usual approximation along edges).
func covered(sum: f32, evenodd: bool) -> f64:
let winding = math.abs((f64)sum)
if not evenodd:
return math.min(1.0, winding)
let folded = winding - 2.0 * math.floor(winding * 0.5)
return 2.0 - folded if folded > 1.0 else folded
## Resolve the accumulated outlines into coverage at `opacity` and composite them over
## `coverage` (source-over: a pixel at a gets c(1 - a) more), clearing `acc`.
func resolve_coverage(acc: f32[], width: usize, height: usize, opacity: f64, evenodd: bool, 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 = covered(sum, evenodd) * opacity
if value < 1.0 / 512.0:
continue
let slot = row * width + column
let below = (f64)coverage[slot] / 255.0
coverage[slot] = (u8)((value + below * (1.0 - value)) * 255.0 + 0.5)
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.
## Element by element, all of its fill outlines accumulate together by its fill rule
## (so holes stay open), then its strokes, each composited source-over onto the mask.
## Strokes get their width, caps, joins and dashes.
## 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)
var start: usize = 0
while start < drawing.contour_used:
# The element's contours run from `start` to `end`, sharing one style.
let head = drawing.contours[start]
var end = start + 1
while end < drawing.contour_used and drawing.contours[end].element == head.element:
end += 1
if head.fill.painted:
var traced = false
for index in start..<end:
if drawing.contours[index].length >= 3:
trace_fill(acc, w, h, drawing, drawing.contours[index], fit)
traced = true
if traced:
resolve_coverage(acc, w, h, head.fill_opacity, head.evenodd, coverage)
if head.stroke.painted:
for index in start..<end:
if drawing.contours[index].length >= 1:
try trace_stroke(acc, w, h, drawing, drawing.contours[index], fit)
resolve_coverage(acc, w, h, head.stroke_opacity, false, coverage)
start = end