diff options
| author | Gabriel Schneider <[email protected]> | 2026-09-25 21:47:58 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-09-25 21:48:16 -0300 |
| commit | 9c33714591a2147f7e5879e77212ca9886d0c967 (patch) | |
| tree | d250be9d9bc365d7894d49455c0f6376966b58be /src/vector/Polygons.zig | |
| download | sketchbook-9c33714591a2147f7e5879e77212ca9886d0c967.tar.gz sketchbook-9c33714591a2147f7e5879e77212ca9886d0c967.zip | |
Put the game first: lib/sketchbook, sketches/vecanim
The root is the game. The platform library moves to lib/sketchbook (with
serve_web.py, which serves any sketch's web build, as a tool of it), and
vecanim to sketches/vecanim, still its own package on the same library.
Diffstat (limited to 'src/vector/Polygons.zig')
| -rw-r--r-- | src/vector/Polygons.zig | 395 |
1 files changed, 395 insertions, 0 deletions
diff --git a/src/vector/Polygons.zig b/src/vector/Polygons.zig new file mode 100644 index 0000000..c0ed335 --- /dev/null +++ b/src/vector/Polygons.zig @@ -0,0 +1,395 @@ +//! 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); +} |
