//! Closed polygons in device pixels: what a fill or a stroke becomes before //! any backend sees it. Fills keep their contours as the path had them; //! strokes become many small pieces (segment quads, joins, caps), all wound //! the same way, so the nonzero rule unions them. const Polygons = @This(); const std = @import("std"); const geom = @import("geom.zig"); const Drawing = @import("Drawing.zig"); const Vec = geom.Vec; const Affine = geom.Affine; /// Device-space flattening tolerance, in pixels. pub const tolerance = 0.2; gpa: std.mem.Allocator, points: std.ArrayList(Vec) = .empty, /// Point count of each contour, in order. contours: std.ArrayList(u32) = .empty, /// Scratch polylines. line: std.ArrayList(Vec) = .empty, dashed: std.ArrayList(Vec) = .empty, clipped: std.ArrayList(Vec) = .empty, clip_scratch: std.ArrayList(Vec) = .empty, clip_counts: std.ArrayList(u32) = .empty, pub fn init(gpa: std.mem.Allocator) Polygons { return .{ .gpa = gpa }; } pub fn deinit(p: *Polygons) void { p.points.deinit(p.gpa); p.contours.deinit(p.gpa); p.line.deinit(p.gpa); p.dashed.deinit(p.gpa); p.clipped.deinit(p.gpa); p.clip_scratch.deinit(p.gpa); p.clip_counts.deinit(p.gpa); } /// Keeps only what lies inside the convex `quad` (device space), contour by /// contour (Sutherland–Hodgman). Winding numbers inside the quad are /// unchanged, so both fill rules still hold. pub fn clipConvex(p: *Polygons, quad: [4]Vec) !void { var area: f32 = 0; for (quad, 0..) |q, i| area += geom.cross(q, quad[(i + 1) % 4]); const sign: f32 = if (area >= 0) 1 else -1; p.clipped.clearRetainingCapacity(); p.clip_counts.clearRetainingCapacity(); var it = p.iterator(); while (it.next()) |pts| { p.clip_scratch.clearRetainingCapacity(); try p.clip_scratch.appendSlice(p.gpa, pts); for (quad, 0..) |a, i| { const b = quad[(i + 1) % 4]; const edge = b - a; const input = try p.gpa.dupe(Vec, p.clip_scratch.items); defer p.gpa.free(input); p.clip_scratch.clearRetainingCapacity(); if (input.len == 0) break; var prev = input[input.len - 1]; var prev_in = sign * geom.cross(edge, prev - a) >= 0; for (input) |cur| { const cur_in = sign * geom.cross(edge, cur - a) >= 0; if (cur_in != prev_in) { const d0 = geom.cross(edge, prev - a); const d1 = geom.cross(edge, cur - a); try p.clip_scratch.append(p.gpa, geom.mix(prev, cur, d0 / (d0 - d1))); } if (cur_in) try p.clip_scratch.append(p.gpa, cur); prev = cur; prev_in = cur_in; } } if (p.clip_scratch.items.len >= 3) { try p.clipped.appendSlice(p.gpa, p.clip_scratch.items); try p.clip_counts.append(p.gpa, @intCast(p.clip_scratch.items.len)); } } p.points.clearRetainingCapacity(); p.contours.clearRetainingCapacity(); try p.points.appendSlice(p.gpa, p.clipped.items); try p.contours.appendSlice(p.gpa, p.clip_counts.items); } pub fn clear(p: *Polygons) void { p.points.clearRetainingCapacity(); p.contours.clearRetainingCapacity(); } pub fn empty(p: *const Polygons) bool { return p.contours.items.len == 0; } pub fn bounds(p: *const Polygons) geom.Bounds { var b: geom.Bounds = .{}; for (p.points.items) |q| b.add(q); return b; } /// Iterates contours as point slices. pub fn iterator(p: *const Polygons) Iterator { return .{ .p = p }; } pub const Iterator = struct { p: *const Polygons, contour: usize = 0, start: usize = 0, pub fn next(it: *Iterator) ?[]const Vec { if (it.contour == it.p.contours.items.len) return null; const len = it.p.contours.items[it.contour]; defer { it.start += len; it.contour += 1; } return it.p.points.items[it.start..][0..len]; } }; fn contour(p: *Polygons, pts: []const Vec) !void { if (pts.len < 3) return; try p.points.appendSlice(p.gpa, pts); try p.contours.append(p.gpa, @intCast(pts.len)); } /// A closed polygon wound positively (in device space) whatever its order, /// so overlapping stroke pieces add up instead of cancelling. fn piece(p: *Polygons, m: Affine, pts: []const Vec) !void { var area: f32 = 0; for (pts, 0..) |q, i| area += geom.cross(q, pts[(i + 1) % pts.len]); if (m.determinant() < 0) area = -area; const start = p.points.items.len; for (0..pts.len) |k| try p.points.append(p.gpa, m.apply(if (area >= 0) pts[k] else pts[(pts.len - k) % pts.len])); try p.contours.append(p.gpa, @intCast(p.points.items.len - start)); } // --------------------------------------------------------------------------- // Fills /// The subpaths of `shape` as contours, with `m` from shape to device space. pub fn fill(p: *Polygons, d: Drawing, shape: Drawing.Shape, m: Affine) !void { for (d.subpathsOf(shape)) |sp| { p.line.clearRetainingCapacity(); try flatten(p.gpa, &p.line, d.cubicsOf(sp), m, tolerance); try p.contour(p.line.items); } } // --------------------------------------------------------------------------- // Strokes pub const Stroke = struct { width: f32, cap: Drawing.Cap = .butt, join: Drawing.Join = .miter, miter_limit: f32 = 4, dashes: []const f32 = &.{}, dash_offset: f32 = 0, /// The drawn fraction of the path, along its length (0..1). trim: f32 = 1, /// From the space the stroke is laid out in to pixels: the shape's own /// space (width and dashes then follow its transform), or identity for a /// fixed pixel width. space: Affine, pub fn of(style: Drawing.Style, space: Affine) Stroke { return .{ .width = style.stroke_width, .cap = style.cap, .join = style.join, .miter_limit = style.miter_limit, .dash_offset = style.dash_offset, .space = space, }; } }; /// The stroke of `shape` as positively wound pieces; `m` takes the shape to /// device space. pub fn stroke(p: *Polygons, d: Drawing, shape: Drawing.Shape, m: Affine, st: Stroke) !void { if (st.width <= 0) return; const to_layout = st.space.invert().mul(m); const layout_tolerance = tolerance / @max(st.space.scaleFactor(), 1e-6); var budget = std.math.inf(f32); if (st.trim < 1) { var total: f32 = 0; for (d.subpathsOf(shape)) |sp| { p.line.clearRetainingCapacity(); try flatten(p.gpa, &p.line, d.cubicsOf(sp), to_layout, layout_tolerance); total += length(p.line.items); } budget = @max(st.trim, 0) * total; if (budget <= 0) return; } for (d.subpathsOf(shape)) |sp| { if (budget <= 0) break; p.line.clearRetainingCapacity(); try flatten(p.gpa, &p.line, d.cubicsOf(sp), to_layout, layout_tolerance); var pts: []const Vec = p.line.items; var closed = sp.closed; const len = length(pts); if (len > budget) { pts = truncate(&p.line, budget); closed = false; } budget -= len; if (st.dashes.len > 0) try p.dash(pts, closed, st) else try p.polyline(pts, closed, st); } } fn dash(p: *Polygons, pts: []const Vec, closed: bool, st: Stroke) !void { var period: f32 = 0; for (st.dashes) |v| period += v; if (period <= 0 or pts.len < 2) return p.polyline(pts, closed, st); var index: usize = 0; var left = @mod(st.dash_offset, period); while (left >= st.dashes[index]) { left -= st.dashes[index]; index = (index + 1) % st.dashes.len; } var remaining = st.dashes[index] - left; var on = index % 2 == 0; p.dashed.clearRetainingCapacity(); if (on) try p.dashed.append(p.gpa, pts[0]); const segments = pts.len - 1 + @intFromBool(closed); for (0..segments) |i| { var a = pts[i]; const b = pts[(i + 1) % pts.len]; var seg = geom.length(b - a); while (seg > remaining) { const q = geom.mix(a, b, remaining / seg); try p.dashed.append(p.gpa, q); if (on) try p.polyline(p.dashed.items, false, st); p.dashed.clearRetainingCapacity(); if (!on) try p.dashed.append(p.gpa, q); seg -= remaining; a = q; on = !on; index = (index + 1) % st.dashes.len; remaining = st.dashes[index]; } remaining -= seg; if (on) try p.dashed.append(p.gpa, b); } if (on and p.dashed.items.len > 1) try p.polyline(p.dashed.items, false, st); } fn polyline(p: *Polygons, pts: []const Vec, closed: bool, st: Stroke) !void { const hw = st.width / 2; if (pts.len == 0) return; const m = st.space; var moved = false; for (pts[1..]) |q| if (geom.length(q - pts[0]) > 1e-6) { moved = true; break; }; // A lone point still shows with round or square caps. if (!moved) return switch (st.cap) { .round => p.circle(m, pts[0], hw), .square => p.piece(m, &.{ pts[0] + Vec{ -hw, -hw }, pts[0] + Vec{ hw, -hw }, pts[0] + Vec{ hw, hw }, pts[0] + Vec{ -hw, hw } }), .butt => {}, }; var first: ?struct { point: Vec, dir: Vec } = null; var last_dir: Vec = undefined; var last_point: Vec = undefined; const count = pts.len - 1 + @intFromBool(closed); for (0..count) |i| { const a = pts[i]; const b = pts[(i + 1) % pts.len]; const delta = b - a; if (geom.length(delta) < 1e-6) continue; const dir = geom.normalize(delta); const n = geom.perp(dir) * geom.splat(hw); try p.piece(m, &.{ a + n, b + n, b - n, a - n }); if (first == null) first = .{ .point = a, .dir = dir } else try p.join(m, a, last_dir, dir, hw, st); last_dir = dir; last_point = b; } const f = first orelse return; if (closed) { try p.join(m, f.point, last_dir, f.dir, hw, st); } else { try p.cap(m, f.point, -f.dir, hw, st.cap); try p.cap(m, last_point, last_dir, hw, st.cap); } } fn join(p: *Polygons, m: Affine, v: Vec, d0: Vec, d1: Vec, hw: f32, st: Stroke) !void { const turn = geom.cross(d0, d1); if (@abs(turn) < 1e-6 and geom.dot(d0, d1) > 0) return; if (st.join == .round) return p.circle(m, v, hw); // Offsets on the outer side of the turn: `perp` is the left side, which // is outside when the path turns right (positive cross in y-down space). const side: f32 = if (turn > 0) 1 else -1; const n0 = geom.perp(d0) * geom.splat(hw * side); const n1 = geom.perp(d1) * geom.splat(hw * side); if (st.join == .miter) { // The tip lies along the bisector; SVG's limit bounds its length // over the stroke width. const bisector = geom.normalize(n0 + n1); const cos_half = geom.dot(bisector, geom.normalize(n0)); if (cos_half > 1e-6 and 1 / cos_half <= st.miter_limit) { return p.piece(m, &.{ v, v + n0, v + bisector * geom.splat(hw / cos_half), v + n1 }); } } try p.piece(m, &.{ v, v + n0, v + n1 }); } fn cap(p: *Polygons, m: Affine, at: Vec, dir: Vec, hw: f32, kind: Drawing.Cap) !void { switch (kind) { .butt => {}, .round => try p.circle(m, at, hw), .square => { const n = geom.perp(dir) * geom.splat(hw); const out = dir * geom.splat(hw); try p.piece(m, &.{ at + n, at + n + out, at - n + out, at - n }); }, } } fn circle(p: *Polygons, m: Affine, center: Vec, r: f32) !void { const device_r = @max(r * m.scaleFactor(), tolerance); const steps: usize = @intFromFloat(std.math.clamp(@ceil(std.math.pi / std.math.acos(@max(1 - tolerance / device_r, -1))), 8, 128)); var buf: [128]Vec = undefined; for (0..steps) |i| { const a = @as(f32, @floatFromInt(i)) / @as(f32, @floatFromInt(steps)) * std.math.tau; buf[i] = center + Vec{ @cos(a), @sin(a) } * geom.splat(r); } try p.piece(m, buf[0..steps]); } // --------------------------------------------------------------------------- // Polylines /// Cubics to a polyline, each transformed by `m`, within `tol`. pub fn flatten(gpa: std.mem.Allocator, out: *std.ArrayList(Vec), cubics: []const geom.Cubic, m: Affine, tol: f32) !void { for (cubics, 0..) |raw, i| { const c: geom.Cubic = .{ m.apply(raw[0]), m.apply(raw[1]), m.apply(raw[2]), m.apply(raw[3]) }; if (i == 0) try out.append(gpa, c[0]); const n = geom.flattenCount(c, tol); const step = 1 / @as(f32, @floatFromInt(n)); for (1..n) |k| try out.append(gpa, geom.eval(c, @as(f32, @floatFromInt(k)) * step)); try out.append(gpa, c[3]); } } pub fn length(pts: []const Vec) f32 { if (pts.len < 2) return 0; var total: f32 = 0; for (pts[0 .. pts.len - 1], pts[1..]) |a, b| total += geom.length(b - a); return total; } /// Shortens the polyline in `list` to `len` and returns it. fn truncate(list: *std.ArrayList(Vec), len: f32) []const Vec { const pts = list.items; var left = len; for (pts[0 .. pts.len - 1], pts[1..], 1..) |a, b, i| { const seg = geom.length(b - a); if (seg >= left) { pts[i] = geom.mix(a, b, if (seg > 0) left / seg else 0); list.shrinkRetainingCapacity(i + 1); return list.items; } left -= seg; } return pts; } test "a square stroke is four quads and four miters, all wound one way" { var p: Polygons = .init(std.testing.allocator); defer p.deinit(); var b: Drawing.Builder = .init(std.testing.allocator); defer { b.cubics.deinit(b.gpa); b.subpaths.deinit(b.gpa); b.shapes.deinit(b.gpa); b.gradients.deinit(b.gpa); } try b.rect(.{ .w = 10, .h = 10 }, 0); try b.endShape(.identity, .{}); const d: Drawing = .{ .cubics = b.cubics.items, .subpaths = b.subpaths.items, .shapes = b.shapes.items }; try p.stroke(d, d.shapes[0], .identity, .{ .width = 2, .space = .identity }); try std.testing.expectEqual(@as(usize, 8), p.contours.items.len); var it = p.iterator(); while (it.next()) |pts| { var area: f32 = 0; for (pts, 0..) |q, i| area += geom.cross(q, pts[(i + 1) % pts.len]); try std.testing.expect(area > 0); } const bb = p.bounds().rect(); try std.testing.expectEqual(@as(f32, -1), bb.x); try std.testing.expectEqual(@as(f32, 12), bb.w); }