summaryrefslogtreecommitdiff
path: root/src/vector/Polygons.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/vector/Polygons.zig')
-rw-r--r--src/vector/Polygons.zig395
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);
+}