///|
/// Active edge record used by the scanline rasterizer.
priv struct Edge {
y_top : Int
y_bot : Int
sy : Double
ey : Double
x : Double
dx : Double
winding : Int
}
///|
fn build_edges(polylines : Array[Array[(Double, Double)]]) -> Array[Edge] {
let edges : Array[Edge] = []
for line in polylines {
if line.length() >= 2 {
for i in 0..<(line.length() - 1) {
let (x0, y0) = line[i]
let (x1, y1) = line[i + 1]
if y0 != y1 {
let (sy, ey, sx, ex, winding) = if y0 < y1 {
(y0, y1, x0, x1, 1)
} else {
(y1, y0, x1, x0, -1)
}
let y_top = (sy - 0.5).ceil().to_int()
let y_bot = (ey - 0.5).ceil().to_int()
if y_top < y_bot {
let slope = (ex - sx) / (ey - sy)
let x_at_top = sx + slope * (y_top.to_double() - sy)
edges.push({ y_top, y_bot, sy, ey, x: x_at_top, dx: slope, winding })
}
}
}
}
}
edges
}
///|
/// Fill polylines using non-zero winding. AA off: each pixel is fully covered
/// (coverage == 256) or not covered at all. Gradient fills sample per pixel
/// after inverse-transforming the pixel center into user space.
pub fn fill_polylines(
pixels : FixedArray[Byte],
width : Int,
height : Int,
polylines : Array[Array[(Double, Double)]],
style : FillStyle,
matrix : Matrix2D,
clip : ClipMask?,
global_alpha : Double,
aa : Bool,
) -> Unit {
if aa {
fill_polylines_aa(
pixels, width, height, polylines, style, matrix, clip, global_alpha,
)
return
}
let edges = build_edges(polylines)
if edges.length() == 0 {
return
}
let matrix_inv = matrix.invert()
// Vertical bounds, clipped to the framebuffer.
let mut y_min = height
let mut y_max = 0
for e in edges {
if e.y_top < y_min {
y_min = e.y_top
}
if e.y_bot > y_max {
y_max = e.y_bot
}
}
if y_min < 0 {
y_min = 0
}
if y_max > height {
y_max = height
}
let active : Array[(Double, Int)] = []
for y in y_min.. 0 && active[j - 1].0 > cur.0 {
active[j] = active[j - 1]
j = j - 1
}
active[j] = cur
}
// Walk sorted crossings with non-zero winding accumulation.
let mut winding = 0
let mut prev_x = 0.0
for crossing in active {
let (x, w) = crossing
if winding != 0 {
let x0 = prev_x
let x1 = x
let ix0 = if x0 < 0.0 { 0 } else { x0.ceil().to_int() }
let ix1_d = if x1 > width.to_double() { width.to_double() } else { x1 }
let ix1 = ix1_d.ceil().to_int()
for x_pix in ix0.. 255
Some(mask) => mask.data[y * width + x_pix].to_int()
}
if clip_cov != 0 {
let color = resolve_color(
style,
matrix_inv,
x_pix.to_double() + 0.5,
y.to_double() + 0.5,
)
let effective = if clip_cov == 255 {
256
} else {
(256 * clip_cov + 127) / 255
}
blend_over(pixels, offset, color, effective, global_alpha)
}
}
}
winding = winding + w
prev_x = x
}
}
}
///|
/// 4×4 supersampled anti-aliased fill. Coverage is accumulated per pixel
/// across 4 sub-rows × 4 sub-columns (16 samples), then passed to
/// `blend_over` as an integer 0..=256.
fn fill_polylines_aa(
pixels : FixedArray[Byte],
width : Int,
height : Int,
polylines : Array[Array[(Double, Double)]],
style : FillStyle,
matrix : Matrix2D,
clip : ClipMask?,
global_alpha : Double,
) -> Unit {
let edges = build_edges(polylines)
if edges.length() == 0 {
return
}
let matrix_inv = matrix.invert()
// Vertical bounds clipped to framebuffer.
let mut y_min = height
let mut y_max = 0
for e in edges {
if e.y_top < y_min {
y_min = e.y_top
}
if e.y_bot > y_max {
y_max = e.y_bot
}
}
if y_min < 0 {
y_min = 0
}
if y_max > height {
y_max = height
}
// Per-row coverage buffer reused across sub-rows.
let coverage : FixedArray[Int] = FixedArray::make(width, 0)
let active : Array[(Double, Int)] = []
for y in y_min.. 0 && active[j - 1].0 > cur.0 {
active[j] = active[j - 1]
j = j - 1
}
active[j] = cur
}
// Walk crossings, accumulate fractional coverage per pixel in the row.
let mut winding = 0
let mut prev_x = 0.0
for crossing in active {
let (x, w) = crossing
if winding != 0 {
let x0 = if prev_x < 0.0 { 0.0 } else { prev_x }
let x1 = if x > width.to_double() { width.to_double() } else { x }
if x0 < x1 {
// For each integer pixel column overlapped by [x0, x1], compute
// the horizontal fraction covered, then convert to coverage
// units. Each of the 16 samples per pixel is worth 16 units
// (256 / 16), so a fully covered sub-row contributes 64 units.
let ix0 = x0.floor().to_int()
let ix1 = x1.ceil().to_int()
for px in ix0..= 0 && px < width {
let left = if x0 > px.to_double() { x0 } else { px.to_double() }
let right = if x1 < px.to_double() + 1.0 {
x1
} else {
px.to_double() + 1.0
}
let frac = right - left
if frac > 0.0 {
let units = (frac * 64.0 + 0.5).to_int()
coverage[px] = coverage[px] + units
}
}
}
}
}
winding = winding + w
prev_x = x
}
}
// Flush row: for each pixel with non-zero coverage, blend using the
// accumulated coverage as 0..=256.
for px in 0.. 0 {
let c_clamped = if c > 256 { 256 } else { c }
let clip_cov = match clip {
None => 255
Some(mask) => mask.data[y * width + px].to_int()
}
if clip_cov != 0 {
let offset = (y * width + px) * 4
let color = resolve_color(
style,
matrix_inv,
px.to_double() + 0.5,
y.to_double() + 0.5,
)
let effective = if clip_cov == 255 {
c_clamped
} else {
(c_clamped * clip_cov + 127) / 255
}
blend_over(pixels, offset, color, effective, global_alpha)
}
}
}
}
}
///|
/// Returns the fill color at device-space pixel center `(dev_x, dev_y)` for
/// the given fill style. For gradient variants, the pixel center is
/// inverse-transformed through `matrix_inv` before sampling. If the matrix
/// was singular (`matrix_inv is None`), gradient pixels become transparent.
fn resolve_color(
style : FillStyle,
matrix_inv : Matrix2D?,
dev_x : Double,
dev_y : Double,
) -> Color {
match style {
FillStyle::Solid(c) => c
FillStyle::Linear(g) =>
match matrix_inv {
Some(inv) => {
let (u, v) = inv.transform_point(dev_x, dev_y)
sample_linear(g, u, v)
}
None => Color::transparent()
}
FillStyle::Radial(g) =>
match matrix_inv {
Some(inv) => {
let (u, v) = inv.transform_point(dev_x, dev_y)
sample_radial(g, u, v)
}
None => Color::transparent()
}
}
}
///|
/// Stroke each polyline by expanding it into an offset polygon and filling.
/// Cap = butt (perpendicular at endpoints), join = miter with a hard miter
/// limit of 10.0; past the limit, fall back to bevel.
pub fn stroke_polylines(
pixels : FixedArray[Byte],
width : Int,
height : Int,
polylines : Array[Array[(Double, Double)]],
style : FillStyle,
line_width : Double,
line_cap : LineCap,
line_join : LineJoin,
matrix : Matrix2D,
clip : ClipMask?,
global_alpha : Double,
aa : Bool,
) -> Unit {
let half_w = line_width * 0.5
let miter_limit = 10.0
let outlined : Array[Array[(Double, Double)]] = []
for line in polylines {
if line.length() < 2 {
continue
}
// Collect left-side offset points (forward) and right-side offset points
// (forward; reversed at polygon-close time).
let left : Array[(Double, Double)] = []
let right : Array[(Double, Double)] = []
for i in 0.. butt-right),
// -1 for end (butt-right -> butt-left).
let sign = if is_start { 1.0 } else { -1.0 }
for k in 0..<=n_segs {
let theta = @math.PI * k.to_double() / n_segs.to_double()
let c = @math.cos(theta)
let s = @math.sin(theta)
let rx = sign * c * nxv + s * tx
let ry = sign * c * nyv + s * ty
left.push((x + rx * half_w, y + ry * half_w))
}
// NOTHING pushed to `right` — the arc already covers both sides.
} else if is_start || is_end {
// Butt or Square endpoint.
let nxv = if is_start { out_nx_raw } else { in_nx_raw }
let nyv = if is_start { out_ny_raw } else { in_ny_raw }
let off_x = nxv * half_w
let off_y = nyv * half_w
let (shift_x, shift_y) = if line_cap == LineCap::Square {
let (tx_raw, ty_raw) = if is_start {
(-out_dx, -out_dy)
} else {
(in_dx, in_dy)
}
let tlen = (tx_raw * tx_raw + ty_raw * ty_raw).sqrt()
if tlen == 0.0 {
(0.0, 0.0)
} else {
(tx_raw * half_w / tlen, ty_raw * half_w / tlen)
}
} else {
(0.0, 0.0)
}
left.push((x + off_x + shift_x, y + off_y + shift_y))
right.push((x - off_x + shift_x, y - off_y + shift_y))
} else if avg_len_sq < 1.0e-12 {
// Interior collinear — fallback.
let off_x = in_nx_raw * half_w
let off_y = in_ny_raw * half_w
left.push((x + off_x, y + off_y))
right.push((x - off_x, y - off_y))
} else if line_join == LineJoin::Round {
// Round join: arc on the outer side from in_normal to out_normal,
// bevel-style single point on the inner side.
let cross_z = in_dx * out_dy - in_dy * out_dx
// Angle between the two normals via dot product.
let dot_normals = in_nx_raw * out_nx_raw + in_ny_raw * out_ny_raw
let cos_clamped = if dot_normals < -1.0 {
-1.0
} else if dot_normals > 1.0 {
1.0
} else {
dot_normals
}
let angle = @math.acos(cos_clamped)
let n_segs = {
let m = (angle * half_w).ceil().to_int()
if m < 8 {
8
} else {
m
}
}
// Mirror the bevel branch's side selection: for cross_z > 0 the
// arc replaces the OUTER (right-array) single point; the inner
// (left-array) gets a bevel-style chord to match bevel inner
// geometry. For cross_z < 0 it's mirrored.
if cross_z > 0.0 {
// Outer side = right: arc from (-in_n) around to (-out_n).
// We rotate (-in_n) toward (-out_n); since we negate both endpoints
// the same rotation matrix that takes in_n to out_n also takes
// -in_n to -out_n.
for k in 0..<=n_segs {
let t = k.to_double() / n_segs.to_double()
let a = angle * t
let c = @math.cos(a)
let s = @math.sin(a)
let rx = c * in_nx_raw - s * in_ny_raw
let ry = s * in_nx_raw + c * in_ny_raw
right.push((x - rx * half_w, y - ry * half_w))
}
// Inner (left): keep the bevel chord so the interior matches bevel.
left.push((x + in_nx_raw * half_w, y + in_ny_raw * half_w))
left.push((x + out_nx_raw * half_w, y + out_ny_raw * half_w))
} else {
// Outer side = left.
for k in 0..<=n_segs {
let t = k.to_double() / n_segs.to_double()
let a = angle * t
let c = @math.cos(a)
let s = @math.sin(a)
let rx = c * in_nx_raw + s * in_ny_raw
let ry = -s * in_nx_raw + c * in_ny_raw
left.push((x + rx * half_w, y + ry * half_w))
}
// Inner (right): bevel chord.
right.push((x - in_nx_raw * half_w, y - in_ny_raw * half_w))
right.push((x - out_nx_raw * half_w, y - out_ny_raw * half_w))
}
} else if line_join == LineJoin::Bevel {
// Bevel join — push 2 points on the outer side, 1 on the inner.
// Outer side is determined by the sign of the cross product of
// incoming and outgoing direction vectors.
let cross_z = in_dx * out_dy - in_dy * out_dx
if cross_z > 0.0 {
// Outer side is left (positive normal direction).
left.push((x + in_nx_raw * half_w, y + in_ny_raw * half_w))
left.push((x + out_nx_raw * half_w, y + out_ny_raw * half_w))
right.push((x - in_nx_raw * half_w, y - in_ny_raw * half_w))
} else {
// Outer side is right (negative normal direction).
left.push((x + in_nx_raw * half_w, y + in_ny_raw * half_w))
right.push((x - in_nx_raw * half_w, y - in_ny_raw * half_w))
right.push((x - out_nx_raw * half_w, y - out_ny_raw * half_w))
}
} else {
// Interior miter (with bevel fallback).
let dot = avg_nx * in_nx_raw + avg_ny * in_ny_raw
let (off_x, off_y) = if dot < 1.0 / miter_limit {
(in_nx_raw * half_w, in_ny_raw * half_w)
} else {
let factor = half_w / dot
(avg_nx * factor, avg_ny * factor)
}
left.push((x + off_x, y + off_y))
right.push((x - off_x, y - off_y))
}
}
// Explicit polygon close sequence.
let polygon : Array[(Double, Double)] = []
for p in left {
polygon.push(p)
}
for i in 0.. Unit {
let edges = build_edges(polylines)
if edges.length() == 0 {
return
}
let mut y_min = height
let mut y_max = 0
for e in edges {
if e.y_top < y_min {
y_min = e.y_top
}
if e.y_bot > y_max {
y_max = e.y_bot
}
}
if y_min < 0 {
y_min = 0
}
if y_max > height {
y_max = height
}
let active : Array[(Double, Int)] = []
for y in y_min.. 0 && active[j - 1].0 > cur.0 {
active[j] = active[j - 1]
j = j - 1
}
active[j] = cur
}
let mut winding = 0
let mut prev_x = 0.0
for crossing in active {
let (x, w) = crossing
if winding != 0 {
let x0 = if prev_x < 0.0 { 0.0 } else { prev_x }
let x1 = if x > width.to_double() { width.to_double() } else { x }
let ix0 = x0.ceil().to_int()
let ix1 = x1.ceil().to_int()
for xp in ix0.. Bool {
let n = pattern.length()
if n == 0 {
return false
}
let mut any_positive = false
for v in pattern {
// Portable NaN check: NaN != NaN.
if v != v {
return false
}
if v < 0.0 {
return false
}
// Portable infinity check: finite iff v - v == 0.
if v - v != 0.0 {
return false
}
if v > 0.0 {
any_positive = true
}
}
any_positive
}
///|
/// In-place intersection: `dst.data[i] = (dst.data[i] * src.data[i] + 127) / 255`.
/// Uses integer math with half-to-up rounding to minimize drift across
/// successive intersections. `dst` and `src` must have matching dimensions;
/// mismatched sizes lead to out-of-bounds reads and are the caller's problem.
pub fn intersect_clip(dst : ClipMask, src : ClipMask) -> Unit {
let n = dst.data.length()
for i in 0.. Unit {
let edges = build_edges(polylines)
if edges.length() == 0 {
return
}
let width = target.width
let height = target.height
let mut y_min = height
let mut y_max = 0
for e in edges {
if e.y_top < y_min {
y_min = e.y_top
}
if e.y_bot > y_max {
y_max = e.y_bot
}
}
if y_min < 0 {
y_min = 0
}
if y_max > height {
y_max = height
}
if aa {
let coverage : FixedArray[Int] = FixedArray::make(width, 0)
let active : Array[(Double, Int)] = []
for y in y_min.. 0 && active[j - 1].0 > cur.0 {
active[j] = active[j - 1]
j = j - 1
}
active[j] = cur
}
let mut winding = 0
let mut prev_x = 0.0
for crossing in active {
let (x, w) = crossing
if winding != 0 {
let x0 = if prev_x < 0.0 { 0.0 } else { prev_x }
let x1 = if x > width.to_double() { width.to_double() } else { x }
if x0 < x1 {
let ix0 = x0.floor().to_int()
let ix1 = x1.ceil().to_int()
for px in ix0..= 0 && px < width {
let left = if x0 > px.to_double() {
x0
} else {
px.to_double()
}
let right = if x1 < px.to_double() + 1.0 {
x1
} else {
px.to_double() + 1.0
}
let frac = right - left
if frac > 0.0 {
let units = (frac * 64.0 + 0.5).to_int()
coverage[px] = coverage[px] + units
}
}
}
}
}
winding = winding + w
prev_x = x
}
}
for px in 0.. 0 {
// 0..=256 -> 0..=255 byte.
let clamped = if c >= 256 { 255 } else { c * 255 / 256 }
target.data[y * width + px] = clamped.to_byte()
}
}
}
} else {
let active : Array[(Double, Int)] = []
for y in y_min.. 0 && active[j - 1].0 > cur.0 {
active[j] = active[j - 1]
j = j - 1
}
active[j] = cur
}
let mut winding = 0
let mut prev_x = 0.0
for crossing in active {
let (x, w) = crossing
if winding != 0 {
let x0 = prev_x
let x1 = x
let ix0 = if x0 < 0.0 { 0 } else { x0.ceil().to_int() }
let ix1_d = if x1 > width.to_double() {
width.to_double()
} else {
x1
}
let ix1 = ix1_d.ceil().to_int()
for x_pix in ix0..= 0 && x_pix < width {
target.data[y * width + x_pix] = b'\xFF'
}
}
}
winding = winding + w
prev_x = x
}
}
}
}
///|
/// Split each sub-polyline into dashed sub-polylines. Returns only the
/// "on" segments; "off" gaps are dropped from the output. Each input
/// sub-polyline restarts the dash phase from `offset` (matching HTML
/// Canvas `moveTo` semantics — dash is not continuous across sub-paths).
/// Caller must have validated `pattern` via `is_valid_dash_pattern`.
pub fn dash_polylines(
polylines : Array[Array[(Double, Double)]],
pattern : Array[Double],
offset : Double,
) -> Array[Array[(Double, Double)]] {
let result : Array[Array[(Double, Double)]] = []
let cycle = {
let mut s = 0.0
for v in pattern {
s = s + v
}
s
}
for line in polylines {
if line.length() < 2 {
continue
}
// Normalize phase to [0, cycle).
let mut phase = offset - (offset / cycle).floor() * cycle
if phase < 0.0 {
phase = phase + cycle
}
// Find the pattern index containing `phase` and how much of that
// element is left.
let mut dash_index = 0
let mut consumed = 0.0
while dash_index < pattern.length() &&
consumed + pattern[dash_index] <= phase {
consumed = consumed + pattern[dash_index]
dash_index = dash_index + 1
}
// Guard against floating-point drift past the end of pattern.
if dash_index >= pattern.length() {
dash_index = 0
}
let mut dash_remaining = pattern[dash_index] - (phase - consumed)
let mut dash_on = dash_index % 2 == 0
// Current output polyline (for an on segment in progress).
let mut current : Array[(Double, Double)] = []
let mut current_started = false
for i in 0..<(line.length() - 1) {
let (ax, ay) = line[i]
let (bx, by) = line[i + 1]
let dx = bx - ax
let dy = by - ay
let seg_len = (dx * dx + dy * dy).sqrt()
if seg_len == 0.0 {
continue
}
let mut t = 0.0
if dash_on && !current_started {
current = [(ax, ay)]
current_started = true
}
while t < 1.0 {
let seg_remaining = seg_len * (1.0 - t)
let take = if seg_remaining < dash_remaining {
seg_remaining
} else {
dash_remaining
}
let new_t = t + take / seg_len
let px = ax + dx * new_t
let py = ay + dy * new_t
if dash_on {
if !current_started {
current = [(px, py)]
current_started = true
} else {
current.push((px, py))
}
} else if current_started {
if current.length() >= 2 {
result.push(current)
}
current = []
current_started = false
}
dash_remaining = dash_remaining - take
t = new_t
if dash_remaining <= 0.0 {
dash_index = (dash_index + 1) % pattern.length()
dash_remaining = pattern[dash_index]
dash_on = dash_index % 2 == 0
if dash_on && !current_started {
current = [(px, py)]
current_started = true
}
}
}
}
if current_started && current.length() >= 2 {
result.push(current)
}
}
result
}