//! Circles, lines and polygons, filled and stroked, as `Command.shape`s. //! //! Two levels, both plain functions with no state of their own: //! //! - **L1, tessellation.** A `Tessellation` is a caller-owned value: points, //! subpath ends and triangle indices, appended to by `fillCircle`, //! `strokeCircle`, `fillPolygon`, `strokePolygon`, `strokePolyline` and //! `strokeLine` with the caller's allocator, each under an `Affine`. Emit //! it with `f.shape(&t, color)`, batch many shapes into one, inspect it, //! or upload its triangles to a GPU pass of your own. //! - **L2, a Pen.** `Pen` is plain data (fill, stroke, width, transform); //! `circle`, `line` and `polygon` tessellate into `f.scratch` and emit one //! shape for the fill and one for the stroke. On out-of-memory they log //! and drop the shape, as `Frame.emit` does. //! //! What a shape guarantees, so both hosts draw the same pixels: its //! triangles are disjoint and positively wound (clockwise on a y-down //! screen, after the transform, mirrored or not), and its subpaths cover //! exactly their union: one positively wound outline, followed by its //! holes wound the other way (a ring's inside). The web fills each such //! group as one nonzero path, native draws the triangles, so each shape //! blends once on both. Shapes batched into one `Tessellation` are drawn //! one after another by both hosts, so where they overlap translucent //! colours blend twice on both. The one known difference: a stroke that //! overlaps itself (a self-crossing polyline, or segments shorter than the //! stroke is wide at an acute turn) blends twice natively where it //! overlaps, and once on the web. //! //! Curves are flattened to within `tolerance` canvas pixels, measured after //! the transform, so a circle scaled up gets more segments. Native shapes //! are not antialiased (like `rect`); the web canvas antialiases edges. const std = @import("std"); const abi = @import("abi"); const math = @import("math"); const root = @import("root.zig"); const Allocator = std.mem.Allocator; const Vec = math.Vec; const Affine = math.Affine; const Color = abi.Color; const splat = math.splat; /// How a stroke turns a corner (Processing's `strokeJoin`). pub const Join = enum { miter, round, bevel }; /// How an open stroke ends (Processing's `strokeCap`). pub const Cap = enum { butt, round, square }; /// A stroke's shape, for `strokePath`. pub const Stroke = struct { width: f32 = 1, join: Join = .miter, cap: Cap = .butt, /// Joined back to the first point, with no caps. closed: bool = false, /// Mitered corners reach at most this many half-widths from the /// vertex, and are bevelled beyond. miter_limit: f32 = miter_limit, }; /// How far, in canvas pixels, a flattened circle may stray from the true /// one. pub const tolerance: f32 = 0.25; /// A stroke's outer corner is mitered up to this many half-widths from the /// vertex, and bevelled beyond (SVG's default). pub const miter_limit: f32 = 4; pub const Error = Allocator.Error; /// Shapes as data: `points` in canvas coordinates, the subpaths /// `points[ends[i - 1] .. ends[i]]`, and triangles, `indices` into `points` /// three at a time. The fields of `Command.shape`; see the module comment /// for what the functions here guarantee about them. pub const Tessellation = struct { points: std.ArrayList([2]f32) = .empty, ends: std.ArrayList(u32) = .empty, indices: std.ArrayList(u32) = .empty, pub const empty: Tessellation = .{}; pub fn deinit(t: *Tessellation, gpa: Allocator) void { t.points.deinit(gpa); t.ends.deinit(gpa); t.indices.deinit(gpa); t.* = .empty; } pub fn clearRetainingCapacity(t: *Tessellation) void { t.points.clearRetainingCapacity(); t.ends.clearRetainingCapacity(); t.indices.clearRetainingCapacity(); } /// The triangles as a flat vertex list (three points each), for a GPU /// pass of your own. pub fn triangles(t: *const Tessellation, gpa: Allocator) Error![][2]f32 { const out = try gpa.alloc([2]f32, t.indices.items.len); for (out, t.indices.items) |*v, i| v.* = t.points.items[i]; return out; } // -- The append API: the pieces the shape functions are made of. -- /// Appends a point already in canvas coordinates; returns its index. pub fn appendPoint(t: *Tessellation, gpa: Allocator, p: Vec) Error!u32 { const index: u32 = @intCast(t.points.items.len); try t.points.append(gpa, .{ p[0], p[1] }); return index; } /// Ends the current subpath at the last point appended. pub fn endSubpath(t: *Tessellation, gpa: Allocator) Error!void { try t.ends.append(gpa, @intCast(t.points.items.len)); } /// Appends the triangle `a`, `b`, `c` (point indices), wound /// positively whatever order they come in. A triangle with no area is /// left out. pub fn appendTriangle(t: *Tessellation, gpa: Allocator, a: u32, b: u32, c: u32) Error!void { const pa = vec(t.points.items[a]); const area = math.cross(vec(t.points.items[b]) - pa, vec(t.points.items[c]) - pa); if (area == 0 or std.math.isNan(area)) return; try t.indices.appendSlice(gpa, if (area > 0) &.{ a, b, c } else &.{ a, c, b }); } // -- Shapes -- /// A disc of `radius` around `center`. pub fn fillCircle(t: *Tessellation, gpa: Allocator, center: Vec, radius: f32, xf: Affine) Error!void { if (!(radius > 0)) return; const mark = t.begin(); const n = circleSegments(radius, xf); const first = try t.ring(gpa, center, radius, n, xf); try t.endSubpath(gpa); for (1..n - 1) |i| try t.appendTriangle(gpa, first, first + @as(u32, @intCast(i)), first + @as(u32, @intCast(i + 1))); t.finish(mark); } /// A ring `width` wide centred on the circle of `radius`: a disc when /// the width reaches the centre. pub fn strokeCircle(t: *Tessellation, gpa: Allocator, center: Vec, radius: f32, width: f32, xf: Affine) Error!void { const hw = width / 2; if (!(hw > 0) or !(radius >= 0)) return; if (radius - hw <= 0) return t.fillCircle(gpa, center, radius + hw, xf); const mark = t.begin(); const n = circleSegments(radius + hw, xf); const outer = try t.ring(gpa, center, radius + hw, n, xf); try t.endSubpath(gpa); // The hole, wound the other way: the same angles, backwards. const inner: u32 = @intCast(t.points.items.len); for (0..n) |k| _ = try t.appendPoint(gpa, xf.apply(center + math.scale(math.unit(angleOf(n - 1 - k, n)), radius - hw))); try t.endSubpath(gpa); for (0..n) |k| { const o0 = outer + @as(u32, @intCast(k)); const o1 = outer + @as(u32, @intCast((k + 1) % n)); const in_0 = inner + @as(u32, @intCast(n - 1 - k)); const in_1 = inner + @as(u32, @intCast((2 * n - 2 - k) % n)); try t.appendTriangle(gpa, o0, o1, in_1); try t.appendTriangle(gpa, o0, in_1, in_0); } t.finish(mark); } /// The inside of a simple polygon, convex or not (ear clipping), in /// either winding. A polygon that crosses itself is filled as a fan /// where clipping finds no ear, which may not match the web. pub fn fillPolygon(t: *Tessellation, gpa: Allocator, points: []const Vec, xf: Affine) Error!void { if (points.len < 3) return; const mark = t.begin(); const first: u32 = @intCast(t.points.items.len); for (points) |p| _ = try t.appendPoint(gpa, xf.apply(p)); // Repeated points (a closing copy of the first, say) clip badly. var n: u32 = @intCast(points.len); while (n > 1 and std.meta.eql(t.points.items[first + n - 1], t.points.items[first])) n -= 1; t.points.shrinkRetainingCapacity(first + n); try t.endSubpath(gpa); if (n >= 3) try t.clip(gpa, first, n); t.finish(mark); } /// The outline of a closed polygon, `width` wide, with mitered corners /// (bevelled past `miter_limit`): `strokePath` with `.closed = true`. pub fn strokePolygon(t: *Tessellation, gpa: Allocator, points: []const Vec, width: f32, xf: Affine) Error!void { return t.stroke(gpa, points, .{ .width = width, .closed = true }, xf); } /// A line through `points`, `width` wide, with mitered corners (bevelled /// past `miter_limit`) and square-cut ends: `strokePath` with the /// defaults. pub fn strokePolyline(t: *Tessellation, gpa: Allocator, points: []const Vec, width: f32, xf: Affine) Error!void { return t.stroke(gpa, points, .{ .width = width }, xf); } /// A line through `points`, open or closed, with the joins and caps /// `style` asks for. Its triangles stay disjoint as everywhere here: a /// round join is the circular segment beyond the bevel, a round cap the /// half disc beyond the end, a square cap a butt cap moved out by half /// the width. A zero-length open path is a dot (round or square caps) /// or nothing (butt), as in SVG. pub fn strokePath(t: *Tessellation, gpa: Allocator, points: []const Vec, style: Stroke, xf: Affine) Error!void { return t.stroke(gpa, points, style, xf); } /// `points` as an open path of dashes: `pattern[0]` units drawn, then /// `pattern[1]` skipped, measured along the path from its start, so a /// dash turns a corner whole (with `style`'s join). For a closed /// outline, give the first point again at the end. pub fn strokeDashes(t: *Tessellation, gpa: Allocator, points: []const Vec, pattern: [2]f32, style: Stroke, xf: Affine) Error!void { if (points.len < 2 or !(pattern[0] > 0) or !(pattern[1] >= 0)) return; var open = style; open.closed = false; var piece: std.ArrayList(Vec) = .empty; defer piece.deinit(gpa); try piece.append(gpa, points[0]); var on = true; var left = pattern[0]; for (points[0 .. points.len - 1], points[1..]) |a, b| { var rest = math.length(b - a); if (rest == 0) continue; const dir = math.scale(b - a, 1 / rest); var at = a; while (rest > left) { at += math.scale(dir, left); rest -= left; if (on) { try piece.append(gpa, at); try t.stroke(gpa, piece.items, open, xf); } piece.clearRetainingCapacity(); on = !on; if (on) try piece.append(gpa, at); left = pattern[@intFromBool(!on)]; // A pattern with no gap is one dash after another. if (left == 0) { on = true; left = pattern[0]; try piece.append(gpa, at); } } left -= rest; if (on) try piece.append(gpa, b); } if (on and piece.items.len > 1) try t.stroke(gpa, piece.items, open, xf); } /// The rect's area. pub fn fillRect(t: *Tessellation, gpa: Allocator, r: math.Rect, xf: Affine) Error!void { if (!(r.w > 0) or !(r.h > 0)) return; const mark = t.begin(); const first: u32 = @intCast(t.points.items.len); for (rectCorners(r)) |p| _ = try t.appendPoint(gpa, xf.apply(p)); try t.endSubpath(gpa); try t.appendTriangle(gpa, first, first + 1, first + 2); try t.appendTriangle(gpa, first, first + 2, first + 3); t.finish(mark); } /// The rect's outline, `width` wide, centred on its edge, with mitered /// corners (Processing's `rect` with `noFill`). pub fn strokeRect(t: *Tessellation, gpa: Allocator, r: math.Rect, width: f32, xf: Affine) Error!void { if (!(r.w > 0) or !(r.h > 0)) return; const cs = rectCorners(r); return t.stroke(gpa, &cs, .{ .width = width, .closed = true }, xf); } /// The segment from `a` to `b`, `width` wide, with round ends; a dot /// when `a` is `b`. pub fn strokeLine(t: *Tessellation, gpa: Allocator, a: Vec, b: Vec, width: f32, xf: Affine) Error!void { const hw = width / 2; if (!(hw > 0)) return; const d = b - a; if (math.length(d) == 0) return t.fillCircle(gpa, a, hw, xf); const mark = t.begin(); // A convex stadium: half a circle around each end. const half = @max(circleSegments(hw, xf) / 2, 2); const heading = math.angle(d); const first: u32 = @intCast(t.points.items.len); for ([_]Vec{ b, a }, 0..) |end, side| { const start = heading - std.math.pi / 2.0 + @as(f32, @floatFromInt(side)) * std.math.pi; for (0..half + 1) |k| { const theta = start + std.math.pi * @as(f32, @floatFromInt(k)) / @as(f32, @floatFromInt(half)); _ = try t.appendPoint(gpa, xf.apply(end + math.scale(math.unit(theta), hw))); } } try t.endSubpath(gpa); const count: u32 = 2 * (half + 1); for (1..count - 1) |i| try t.appendTriangle(gpa, first, first + @as(u32, @intCast(i)), first + @as(u32, @intCast(i + 1))); t.finish(mark); } // -- Internals -- const Mark = struct { points: u32, ends: u32 }; fn begin(t: *const Tessellation) Mark { return .{ .points = @intCast(t.points.items.len), .ends = @intCast(t.ends.items.len) }; } /// Winds the subpaths added since `mark` positively: if the one that /// encloses most area runs the wrong way (a mirroring transform, or /// points given counterclockwise), every one of them is reversed, which /// keeps holes holes. Triangles keep their geometry, so their indices /// are remapped. fn finish(t: *Tessellation, mark: Mark) void { var largest: f32 = 0; var start = mark.points; for (t.ends.items[mark.ends..]) |end| { const a = signedArea(t.points.items[start..end]); if (@abs(a) > @abs(largest)) largest = a; start = end; } if (largest >= 0) return; start = mark.points; for (t.ends.items[mark.ends..]) |end| { std.mem.reverse([2]f32, t.points.items[start..end]); start = end; } // Indices that point into this shape's subpaths follow the flip. for (t.indices.items) |*i| { if (i.* < mark.points) continue; var s = mark.points; for (t.ends.items[mark.ends..]) |end| { if (i.* < end) { i.* = end - 1 - (i.* - s); break; } s = end; } } } /// `n` points around a circle, at increasing angles; returns the first. fn ring(t: *Tessellation, gpa: Allocator, center: Vec, radius: f32, n: u32, xf: Affine) Error!u32 { const first: u32 = @intCast(t.points.items.len); try t.points.ensureUnusedCapacity(gpa, n); for (0..n) |k| _ = try t.appendPoint(gpa, xf.apply(center + math.scale(math.unit(angleOf(k, n)), radius))); return first; } /// Triangulates the polygon `points[first..][0..n]` by ear clipping /// (a fan when it is convex). fn clip(t: *Tessellation, gpa: Allocator, first: u32, n: u32) Error!void { const pts = t.points.items[first..][0..n]; const sign: f32 = if (signedArea(pts) >= 0) 1 else -1; const P = struct { fn at(all: []const [2]f32, i: u32) Vec { return vec(all[i]); } }; var convex = true; for (0..n) |i| { const a = P.at(pts, @intCast(i)); const b = P.at(pts, @intCast((i + 1) % n)); const c = P.at(pts, @intCast((i + 2) % n)); if (sign * math.cross(b - a, c - b) < 0) convex = false; } if (convex) { for (1..n - 1) |i| try t.appendTriangle(gpa, first, first + @as(u32, @intCast(i)), first + @as(u32, @intCast(i + 1))); return; } const remaining = try gpa.alloc(u32, n); defer gpa.free(remaining); for (remaining, 0..) |*r, i| r.* = @intCast(i); var len: usize = n; var guard: usize = 0; var i: usize = 0; while (len > 3) { const ia = remaining[(i + len - 1) % len]; const ib = remaining[i % len]; const ic = remaining[(i + 1) % len]; const a = P.at(pts, ia); const b = P.at(pts, ib); const c = P.at(pts, ic); const turn = sign * math.cross(b - a, c - b); var ear = turn > 0; if (ear) for (remaining[0..len]) |j| { if (j == ia or j == ib or j == ic) continue; const p = P.at(pts, j); if (@reduce(.And, p == a) or @reduce(.And, p == b) or @reduce(.And, p == c)) continue; if (inTriangle(p, a, b, c, sign)) { ear = false; break; } }; // A straight or zero-length corner is cut without a triangle. if (ear or turn == 0 or guard > len) { if (turn != 0) try t.appendTriangle(gpa, first + ia, first + ib, first + ic); const at = i % len; std.mem.copyForwards(u32, remaining[at .. len - 1], remaining[at + 1 .. len]); len -= 1; guard = 0; if (at < i) i -= 1; i %= len; } else { i = (i + 1) % len; guard += 1; } } try t.appendTriangle(gpa, first + remaining[0], first + remaining[1], first + remaining[2]); } const Joint = struct { /// The inner corners meet at one point (`inner`), and the bodies are /// cut back to it: disjoint. Otherwise the bodies overlap on the /// inner side, around the vertex. clean: bool, /// Which side (+1 along the segment normal, -1 against it) is outer. outer: f32, inner: Vec, miter: ?Vec, vertex: Vec, }; const Body = struct { start: [2]Vec, end: [2]Vec }; /// Points appended on an arc, between two corners already in the /// outline: `count` of them from `first`, starting next to `from`. const Arc = struct { first: u32 = 0, count: u32 = 0, from: u32 = 0 }; /// The arc around `center` from `center + from` turning by `sweep` /// radians, its end points left out (they are corners already). fn appendArc(t: *Tessellation, gpa: Allocator, center: Vec, from: Vec, sweep: f32, from_index: u32, xf: Affine) Error!Arc { const radius = math.length(from); const whole: f32 = @floatFromInt(circleSegments(radius, xf)); const pieces: u32 = @intFromFloat(@max(1, @ceil(@abs(sweep) / std.math.tau * whole))); const arc: Arc = .{ .first = @intCast(t.points.items.len), .count = pieces - 1, .from = from_index }; for (1..pieces) |i| { const theta = sweep * @as(f32, @floatFromInt(i)) / @as(f32, @floatFromInt(pieces)); const c = @cos(theta); const s = @sin(theta); _ = try t.appendPoint(gpa, xf.apply(center + Vec{ from[0] * c - from[1] * s, from[0] * s + from[1] * c })); } return arc; } /// The circular segment between an arc and its chord, as a fan from /// the arc's first corner to `to`. fn fanArc(t: *Tessellation, gpa: Allocator, arc: Arc, to: u32) Error!void { var previous = arc.first; if (arc.count == 0) return; for (1..arc.count) |i| { const next = arc.first + @as(u32, @intCast(i)); try t.appendTriangle(gpa, arc.from, previous, next); previous = next; } try t.appendTriangle(gpa, arc.from, previous, to); } fn stroke(t: *Tessellation, gpa: Allocator, input: []const Vec, style: Stroke, xf: Affine) Error!void { const hw = style.width / 2; if (!(hw > 0) or input.len == 0) return; // Consecutive repeats make no direction. const pts = try gpa.alloc(Vec, input.len); defer gpa.free(pts); var n: usize = 0; for (input) |p| { if (n > 0 and @reduce(.And, p == pts[n - 1])) continue; pts[n] = p; n += 1; } if (style.closed) while (n > 1 and @reduce(.And, pts[n - 1] == pts[0])) { n -= 1; }; if (n < 2) { // A zero-length open path: a dot where its caps have area (SVG). if (style.closed) return; return switch (style.cap) { .butt => {}, .round => t.fillCircle(gpa, pts[0], hw, xf), .square => t.fillPolygon(gpa, &.{ pts[0] + Vec{ -hw, -hw }, pts[0] + Vec{ hw, -hw }, pts[0] + Vec{ hw, hw }, pts[0] + Vec{ -hw, hw } }, xf), }; } if (n == 2 and style.closed) { var open = style; open.closed = false; open.cap = .butt; return t.stroke(gpa, pts[0..2], open, xf); } const closed = style.closed; if (!closed and style.cap == .square) { // Square caps are butt caps half a width further out. pts[0] -= math.withLength(pts[1] - pts[0], hw); pts[n - 1] += math.withLength(pts[n - 1] - pts[n - 2], hw); } const segments = if (closed) n else n - 1; const joints = if (closed) n else n - 2; const dirs = try gpa.alloc(Vec, segments); defer gpa.free(dirs); const lens = try gpa.alloc(f32, segments); defer gpa.free(lens); for (dirs, lens, 0..) |*d, *l, i| { const v = pts[(i + 1) % n] - pts[i]; l.* = math.length(v); d.* = v / splat(l.*); } const bodies = try gpa.alloc(Body, segments); defer gpa.free(bodies); for (bodies, dirs, 0..) |*body, d, i| { const nrm = math.scale(math.perp(d), hw); body.* = .{ .start = .{ pts[i] + nrm, pts[i] - nrm }, .end = .{ pts[(i + 1) % n] + nrm, pts[(i + 1) % n] - nrm } }; } const limit = @max(style.miter_limit, 1); const js = try gpa.alloc(Joint, joints); defer gpa.free(js); for (js, 0..) |*j, k| { // Joint k joins segment a = k (open: k) to b = k + 1. const a = if (closed) (k + segments - 1) % segments else k; const b = (a + 1) % segments; const v = pts[(a + 1) % n]; const na = math.perp(dirs[a]); const nb = math.perp(dirs[b]); const turn = math.cross(dirs[a], dirs[b]); const outer: f32 = if (turn > 0) 1 else -1; const cos1 = 1 + math.dot(na, nb); // How far back along each segment the inner corners meet. const back = if (cos1 > 1e-6) hw * @abs(turn) / cos1 else std.math.inf(f32); const budget_a = if (closed or a > 0) lens[a] / 2 else lens[a]; const budget_b = if (closed or b + 1 < segments) lens[b] / 2 else lens[b]; const miter_vec = if (cos1 > 1e-6) math.scale(na + nb, hw / cos1) else splat(0); const mitered = style.join == .miter and cos1 >= 2 / (limit * limit) and @abs(turn) > 1e-6; j.* = .{ .clean = back <= budget_a and back <= budget_b, .outer = outer, .inner = v - math.scale(miter_vec, outer), .miter = if (mitered) v + math.scale(miter_vec, outer) else null, .vertex = v, }; const side: usize = if (outer > 0) 1 else 0; // the inner side's corner index if (j.clean) { bodies[a].end[side] = j.inner; bodies[b].start[side] = j.inner; } } const mark = t.begin(); // Corner indices per body: [start+, end+, end-, start-]. const corners = try gpa.alloc([4]u32, segments); defer gpa.free(corners); const joint_points = try gpa.alloc([2]?u32, joints); // miter, pivot defer gpa.free(joint_points); for (joint_points) |*jp| jp.* = .{ null, null }; const arcs = try gpa.alloc(Arc, joints); defer gpa.free(arcs); @memset(arcs, .{}); var caps: [2]Arc = .{ .{}, .{} }; // end, start const round_join = style.join == .round; // The `+` side forward, then the `-` side backward: one outline // when open, two loops (outer and inner) when closed. A clean inner // corner is one point shared by the bodies on either side of it. for ([_]f32{ 1, -1 }) |side| { const c: usize = if (side > 0) 0 else 1; const loop_start: u32 = @intCast(t.points.items.len); var previous: ?u32 = null; for (0..segments) |s_| { const s = if (side > 0) s_ else segments - 1 - s_; const body = bodies[s]; const first_corner = xf.apply(if (side > 0) body.start[c] else body.end[c]); const last_corner = xf.apply(if (side > 0) body.end[c] else body.start[c]); const fi = if (previous != null and std.meta.eql(t.points.items[previous.?], xy(first_corner))) previous.? else try t.appendPoint(gpa, first_corner); const closing = closed and s_ + 1 == segments and std.meta.eql(t.points.items[loop_start], xy(last_corner)); const li = if (closing) loop_start else try t.appendPoint(gpa, last_corner); if (side > 0) { corners[s][0] = fi; corners[s][1] = li; } else { corners[s][2] = fi; corners[s][3] = li; } previous = li; // The joint after this body, in travel order. const has_joint = if (side > 0) (closed or s + 1 < segments) else (closed or s > 0); if (!has_joint) continue; const k = if (side > 0) (if (closed) (s + 1) % segments else s) else (if (closed) s else s - 1); const j = js[k]; if (j.outer == side) { if (j.miter) |m| joint_points[k][0] = try t.appendPoint(gpa, xf.apply(m)); if (round_join) { // From this body's corner to the next body's, around the vertex. const next = if (side > 0) (s + 1) % segments else (s + segments - 1) % segments; const from = (if (side > 0) body.end[c] else body.start[c]) - j.vertex; const to = (if (side > 0) bodies[next].start[c] else bodies[next].end[c]) - j.vertex; const sweep = std.math.atan2(math.cross(from, to), math.dot(from, to)); arcs[k] = try t.appendArc(gpa, j.vertex, from, sweep, li, xf); } } else if (!j.clean) { joint_points[k][1] = try t.appendPoint(gpa, xf.apply(j.vertex)); } } if (!closed and style.cap == .round) { // Half a turn from this side's last corner to the other side's. const at = if (side > 0) pts[n - 1] else pts[0]; const corner = if (side > 0) bodies[segments - 1].end[0] else bodies[0].start[1]; caps[c] = try t.appendArc(gpa, at, corner - at, std.math.pi, previous.?, xf); previous = null; } if (closed) try t.endSubpath(gpa); } if (!closed) try t.endSubpath(gpa); for (corners) |cs| { try t.appendTriangle(gpa, cs[0], cs[1], cs[2]); try t.appendTriangle(gpa, cs[0], cs[2], cs[3]); } for (js, joint_points, arcs, 0..) |j, jp, arc, k| { const a = if (closed) (k + segments - 1) % segments else k; const b = (a + 1) % segments; const outer_end = if (j.outer > 0) corners[a][1] else corners[a][2]; const outer_start = if (j.outer > 0) corners[b][0] else corners[b][3]; const inner = if (j.clean) (if (j.outer > 0) corners[a][2] else corners[a][1]) else jp[1].?; try t.appendTriangle(gpa, inner, outer_end, outer_start); if (jp[0]) |m| try t.appendTriangle(gpa, outer_end, m, outer_start); if (round_join) try t.fanArc(gpa, arc, if (arc.from == outer_end) outer_start else outer_end); } if (!closed and style.cap == .round) { try t.fanArc(gpa, caps[0], corners[segments - 1][2]); try t.fanArc(gpa, caps[1], corners[0][0]); } t.finish(mark); } }; fn vec(p: [2]f32) Vec { return .{ p[0], p[1] }; } fn xy(p: Vec) [2]f32 { return .{ p[0], p[1] }; } fn rectCorners(r: math.Rect) [4]Vec { return .{ .{ r.x, r.y }, .{ r.x + r.w, r.y }, .{ r.x + r.w, r.y + r.h }, .{ r.x, r.y + r.h } }; } fn angleOf(k: usize, n: u32) f32 { return 2 * std.math.pi * @as(f32, @floatFromInt(k)) / @as(f32, @floatFromInt(n)); } /// Twice nothing: the shoelace sum, positive for clockwise on a y-down /// screen. fn signedArea(points: []const [2]f32) f32 { var sum: f32 = 0; for (points, 0..) |p, i| { const q = points[(i + 1) % points.len]; sum += p[0] * q[1] - q[0] * p[1]; } return sum / 2; } fn inTriangle(p: Vec, a: Vec, b: Vec, c: Vec, sign: f32) bool { return sign * math.cross(b - a, p - a) >= 0 and sign * math.cross(c - b, p - b) >= 0 and sign * math.cross(a - c, p - c) >= 0; } /// Segments for a whole circle of `radius` under `xf`, so that no point of /// the polygon is more than `tolerance` canvas pixels inside the circle. pub fn circleSegments(radius: f32, xf: Affine) u32 { const r = radius * xf.maxScale(); if (!(r > tolerance)) return 8; const n = @ceil(std.math.pi / std.math.acos(1 - tolerance / r)); return @intFromFloat(std.math.clamp(n, 8, 1024)); } // --------------------------------------------------------------------------- // L2: a Pen /// How `circle`, `line`, `polyline`, `polygon`, `rect` and `point` draw: /// plain data, so it can be a `const`, a State field, or a copy changed /// for one call. `transformed` is Processing's push-translate-rotate; the /// copy going out of scope is the pop. `fill = null` is `noFill()`, /// `stroke = null` is `noStroke()`. pub const Pen = struct { fill: ?Color = null, stroke: ?Color = null, /// The stroke's width, in the pen's (transformed) units. width: f32 = 1, /// Corners of `polyline`, `polygon` and `rect` strokes. join: Join = .miter, /// Ends of `line` and `polyline`; a `point` is round with `.round`, /// square otherwise. Processing's defaults, both. cap: Cap = .round, xf: Affine = .identity, /// This pen, drawing in a space placed by `m` inside its own. pub fn transformed(p: Pen, m: Affine) Pen { var q = p; q.xf = p.xf.mul(m); return q; } /// The stroke shape `strokePath` takes, for a path open or `closed`. pub fn outline(p: Pen, closed: bool) Stroke { return .{ .width = p.width, .join = p.join, .cap = p.cap, .closed = closed }; } }; /// A circle of `radius` around `center`: the fill, then the stroke over it, /// centred on the edge. pub fn circle(f: *root.Frame, center: Vec, radius: f32, pen: Pen) void { if (pen.fill) |color| { var t: Tessellation = .empty; t.fillCircle(f.scratch, center, radius, pen.xf) catch return dropped(f); f.shape(&t, color); } if (pen.stroke) |color| { var t: Tessellation = .empty; t.strokeCircle(f.scratch, center, radius, pen.width, pen.xf) catch return dropped(f); f.shape(&t, color); } } /// A segment from `a` to `b` in the stroke colour, with the pen's caps. pub fn line(f: *root.Frame, a: Vec, b: Vec, pen: Pen) void { const color = pen.stroke orelse return; var t: Tessellation = .empty; const done = if (pen.cap == .round) t.strokeLine(f.scratch, a, b, pen.width, pen.xf) else t.strokePath(f.scratch, &.{ a, b }, pen.outline(false), pen.xf); done catch return dropped(f); f.shape(&t, color); } /// An open path through `points`: Processing's `beginShape()` ... /// `endShape()`. The fill, if any, is the polygon the points close (as /// Processing fills it), then the stroke along the open path, with the /// pen's joins and caps. pub fn polyline(f: *root.Frame, points: []const Vec, pen: Pen) void { path(f, points, pen, false); } /// A closed polygon (simple: convex or not): the fill, then the stroke, /// with the pen's joins. `endShape(CLOSE)`. pub fn polygon(f: *root.Frame, points: []const Vec, pen: Pen) void { path(f, points, pen, true); } /// A rect: the fill, then the stroke centred on its edge. pub fn rect(f: *root.Frame, r: math.Rect, pen: Pen) void { const cs = rectCorners(r); if (r.w > 0 and r.h > 0) path(f, &cs, pen, true); } /// A dot `pen.width` across in the stroke colour, round or square by the /// pen's cap: Processing's `point`. pub fn point(f: *root.Frame, at: Vec, pen: Pen) void { const color = pen.stroke orelse return; var t: Tessellation = .empty; const done = if (pen.cap == .round) t.fillCircle(f.scratch, at, pen.width / 2, pen.xf) else t.fillRect(f.scratch, .{ .x = at[0] - pen.width / 2, .y = at[1] - pen.width / 2, .w = pen.width, .h = pen.width }, pen.xf); done catch return dropped(f); f.shape(&t, color); } /// `polyline` in dashes, `pattern[0]` units drawn and `pattern[1]` skipped /// along the path, in the stroke colour (no fill): a freed block's outline, /// a link on its way out. Give the first point again to close the outline. pub fn dashed(f: *root.Frame, points: []const Vec, pattern: [2]f32, pen: Pen) void { const color = pen.stroke orelse return; var t: Tessellation = .empty; t.strokeDashes(f.scratch, points, pattern, pen.outline(false), pen.xf) catch return dropped(f); f.shape(&t, color); } fn path(f: *root.Frame, points: []const Vec, pen: Pen, closed: bool) void { if (pen.fill) |color| { var t: Tessellation = .empty; t.fillPolygon(f.scratch, points, pen.xf) catch return dropped(f); f.shape(&t, color); } if (pen.stroke) |color| { var t: Tessellation = .empty; t.strokePath(f.scratch, points, pen.outline(closed), pen.xf) catch return dropped(f); f.shape(&t, color); } } fn dropped(f: *root.Frame) void { f.host.log("out of scratch memory: shape dropped"); } // --------------------------------------------------------------------------- // Tests: every shape keeps the contract. const testing = std.testing; /// Checks the contract: indices in range, every triangle positively /// wound, no two triangles overlapping (beyond touching), the triangles' /// area equal to the subpaths' nonzero area, and subpath ends in order. fn expectValid(t: *const Tessellation) !void { return expectShape(t, .{}); } /// `expectValid` with knobs: `disjoint = false` allows triangles to /// overlap, for the documented exceptions, and then checks only that /// triangles and subpaths cover the same region (no holes on the web). fn expectShape(t: *const Tessellation, options: struct { disjoint: bool = true }) !void { const pts = t.points.items; try testing.expect(t.indices.items.len % 3 == 0); var previous: u32 = 0; for (t.ends.items) |e| { try testing.expect(e >= previous and e <= pts.len); previous = e; } try testing.expectEqual(@as(usize, previous), pts.len); var total: f64 = 0; const tris = t.indices.items; var i: usize = 0; while (i < tris.len) : (i += 3) { for (tris[i..][0..3]) |k| try testing.expect(k < pts.len); const a = vec(pts[tris[i]]); const b = vec(pts[tris[i + 1]]); const c = vec(pts[tris[i + 2]]); const area = math.cross(b - a, c - a) / 2; try testing.expect(area > 0); total += area; } // Disjoint: sampled, since exact polygon intersection is a lot of code // for a test. Every sample point lies in at most one triangle's // interior, and in one exactly when the subpaths' winding is nonzero. var lo: Vec = splat(std.math.inf(f32)); var hi: Vec = splat(-std.math.inf(f32)); for (pts) |p| { lo = @min(lo, vec(p)); hi = @max(hi, vec(p)); } const steps = 160; for (0..steps) |yi| for (0..steps) |xi| { // Off-grid offsets, so samples rarely land on an edge. const fx = (@as(f32, @floatFromInt(xi)) + 0.3711) / steps; const fy = (@as(f32, @floatFromInt(yi)) + 0.6173) / steps; const p = lo + (hi - lo) * Vec{ fx, fy }; var inside: u32 = 0; i = 0; while (i < tris.len) : (i += 3) { const a = vec(pts[tris[i]]); const b = vec(pts[tris[i + 1]]); const c = vec(pts[tris[i + 2]]); if (strictlyInside(p, a, b, c)) inside += 1; } if (options.disjoint) try testing.expect(inside <= 1); const wind = winding(t, p); if (inside >= 1) try testing.expect(wind != 0); if (wind != 0 and inside == 0) try testing.expect(onAnyEdge(t, p)); }; // And the areas agree: the triangles tile the filled region. var region: f64 = 0; var start: u32 = 0; for (t.ends.items) |e| { region += signedArea(pts[start..e]); start = e; } if (options.disjoint) try testing.expectApproxEqRel(region, total, 1e-3); } fn strictlyInside(p: Vec, a: Vec, b: Vec, c: Vec) bool { const eps = 1e-4; return math.cross(b - a, p - a) > eps and math.cross(c - b, p - b) > eps and math.cross(a - c, p - c) > eps; } fn onAnyEdge(t: *const Tessellation, p: Vec) bool { const tris = t.indices.items; var i: usize = 0; while (i < tris.len) : (i += 3) { for (0..3) |e| { const a = vec(t.points.items[tris[i + e]]); const b = vec(t.points.items[tris[i + (e + 1) % 3]]); const ab = b - a; const l2 = math.dot(ab, ab); if (l2 == 0) continue; const u = std.math.clamp(math.dot(p - a, ab) / l2, 0, 1); if (math.length(a + math.scale(ab, u) - p) < 1e-2) return true; } } return false; } /// The subpaths' winding number around `p`. fn winding(t: *const Tessellation, p: Vec) i32 { var w: i32 = 0; var start: u32 = 0; for (t.ends.items) |e| { const ring_pts = t.points.items[start..e]; for (ring_pts, 0..) |a_, k| { const a = vec(a_); const b = vec(ring_pts[(k + 1) % ring_pts.len]); if (a[1] <= p[1]) { if (b[1] > p[1] and math.cross(b - a, p - a) > 0) w += 1; } else { if (b[1] <= p[1] and math.cross(b - a, p - a) < 0) w -= 1; } } start = e; } return w; } test "circles: positive, disjoint, and as many segments as the scale needs" { const gpa = testing.allocator; var t: Tessellation = .empty; defer t.deinit(gpa); try t.fillCircle(gpa, .{ 50, 40 }, 20, .identity); try expectValid(&t); try testing.expectEqual(@as(usize, 1), t.ends.items.len); const n = t.points.items.len; try testing.expectEqual(@as(usize, 3 * (n - 2)), t.indices.items.len); try testing.expect(circleSegments(20, .scale(4, 4)) > circleSegments(20, .identity)); try testing.expectEqual(circleSegments(80, .identity), circleSegments(20, .scale(4, 4))); t.clearRetainingCapacity(); try t.strokeCircle(gpa, .{ 0, 0 }, 30, 6, .identity); try expectValid(&t); try testing.expectEqual(@as(usize, 2), t.ends.items.len); try testing.expectEqual(@as(usize, 3 * t.points.items.len), t.indices.items.len); // A mirroring transform still winds positively. t.clearRetainingCapacity(); try t.strokeCircle(gpa, .{ 10, 0 }, 30, 6, Affine.scale(-1, 1).mul(.rotate(0.3))); try expectValid(&t); t.clearRetainingCapacity(); try t.fillCircle(gpa, .{ 10, 0 }, 3, .scale(1, -2)); try expectValid(&t); } test "polygons: convex, concave, either winding, mirrored" { const gpa = testing.allocator; var t: Tessellation = .empty; defer t.deinit(gpa); const triangle = [_]Vec{ .{ 20, 0 }, .{ -10, -8 }, .{ -10, 8 } }; const arrow = [_]Vec{ .{ 0, 0 }, .{ 60, 0 }, .{ 60, 60 }, .{ 30, 20 }, .{ 0, 60 } }; const star = blk: { var s: [10]Vec = undefined; for (&s, 0..) |*p, i| p.* = math.scale(math.unit(@as(f32, @floatFromInt(i)) * std.math.pi / 5.0), if (i % 2 == 0) 50 else 20); break :blk s; }; var backwards = arrow; std.mem.reverse(Vec, &backwards); for ([_][]const Vec{ &triangle, &arrow, &backwards, &star }) |shape| { for ([_]Affine{ .identity, .place(.{ 100, 50 }, 1.1), .scale(-2, 1) }) |xf| { t.clearRetainingCapacity(); try t.fillPolygon(gpa, shape, xf); try expectValid(&t); try testing.expectEqual(3 * (shape.len - 2), t.indices.items.len); t.clearRetainingCapacity(); try t.strokePolygon(gpa, shape, 3, xf); try expectValid(&t); } } } test "strokes: lines with round ends, acute zig-zags without overlap" { const gpa = testing.allocator; var t: Tessellation = .empty; defer t.deinit(gpa); try t.strokeLine(gpa, .{ 10, 10 }, .{ 200, 60 }, 9, .identity); try expectValid(&t); t.clearRetainingCapacity(); try t.strokeLine(gpa, .{ 10, 10 }, .{ 10, 10 }, 4, .identity); try expectValid(&t); t.clearRetainingCapacity(); try t.strokeLine(gpa, .{ 0, 0.5 }, .{ 100, 0.5 }, 1, .identity); try expectValid(&t); const zigzag = [_]Vec{ .{ 20, 200 }, .{ 70, 60 }, .{ 120, 200 }, .{ 170, 60 }, .{ 220, 200 }, .{ 240, 190 } }; for ([_]f32{ 2, 12, 30 }) |w| { t.clearRetainingCapacity(); try t.strokePolyline(gpa, &zigzag, w, .identity); try expectValid(&t); t.clearRetainingCapacity(); try t.strokePolyline(gpa, &zigzag, w, .scale(-1, 1)); try expectValid(&t); } // Segments shorter than an acute turn needs: the bodies overlap (the // documented exception), but the web's outline still has no holes. const tight = [_]Vec{ .{ 0, 100 }, .{ 10, 0 }, .{ 20, 100 }, .{ 25, 95 }, .{ 30, 100 } }; t.clearRetainingCapacity(); try t.strokePolyline(gpa, &tight, 16, .identity); try expectShape(&t, .{ .disjoint = false }); t.clearRetainingCapacity(); try t.strokePolygon(gpa, &tight, 16, .identity); try expectShape(&t, .{ .disjoint = false }); // Straight runs and repeated points. const straight = [_]Vec{ .{ 0, 0 }, .{ 10, 0 }, .{ 10, 0 }, .{ 20, 0 }, .{ 30, 10 } }; t.clearRetainingCapacity(); try t.strokePolyline(gpa, &straight, 4, .identity); try expectValid(&t); // A square's outline: a ring with a hole. const square = [_]Vec{ .{ 0, 0 }, .{ 50, 0 }, .{ 50, 50 }, .{ 0, 50 } }; t.clearRetainingCapacity(); try t.strokePolygon(gpa, &square, 6, .identity); try expectValid(&t); try testing.expectEqual(@as(usize, 2), t.ends.items.len); } test "dashes: measured along the path, whole round a corner" { const gpa = testing.allocator; var t: Tessellation = .empty; defer t.deinit(gpa); // 100 long, 12 on and 8 off: five dashes, the last ending at 92. try t.strokeDashes(gpa, &.{ .{ 0, 0 }, .{ 100, 0 } }, .{ 12, 8 }, .{ .width = 4 }, .identity); try expectValid(&t); try testing.expectEqual(@as(usize, 5), t.ends.items.len); var reach: f32 = 0; for (t.points.items) |p| reach = @max(reach, p[0]); try testing.expectEqual(@as(f32, 92), reach); // A dash that meets a corner goes round it as one piece: 30 of path, // 20 on from the start, so it ends 10 down the second side. t.clearRetainingCapacity(); try t.strokeDashes(gpa, &.{ .{ 0, 0 }, .{ 10, 0 }, .{ 10, 20 } }, .{ 20, 100 }, .{ .width = 2 }, .identity); try expectValid(&t); try testing.expectEqual(@as(usize, 1), t.ends.items.len); var down: f32 = 0; for (t.points.items) |p| down = @max(down, p[1]); try testing.expectEqual(@as(f32, 10), down); // Nothing to dash. t.clearRetainingCapacity(); try t.strokeDashes(gpa, &.{.{ 0, 0 }}, .{ 12, 8 }, .{ .width = 4 }, .identity); try t.strokeDashes(gpa, &.{ .{ 0, 0 }, .{ 9, 0 } }, .{ 0, 8 }, .{ .width = 4 }, .identity); try testing.expectEqual(@as(usize, 0), t.indices.items.len); } test "nothing to draw draws nothing" { const gpa = testing.allocator; var t: Tessellation = .empty; defer t.deinit(gpa); try t.fillCircle(gpa, .{ 0, 0 }, 0, .identity); try t.strokeCircle(gpa, .{ 0, 0 }, 10, 0, .identity); try t.fillPolygon(gpa, &.{ .{ 0, 0 }, .{ 1, 1 } }, .identity); try t.strokePolyline(gpa, &.{.{ 0, 0 }}, 3, .identity); try testing.expectEqual(@as(usize, 0), t.points.items.len + t.indices.items.len + t.ends.items.len); } test "joins and caps: every combination keeps the contract" { const gpa = testing.allocator; var t: Tessellation = .empty; defer t.deinit(gpa); const zigzag = [_]Vec{ .{ 20, 200 }, .{ 70, 60 }, .{ 120, 200 }, .{ 170, 60 }, .{ 220, 200 }, .{ 240, 190 } }; const path_like = [_]Vec{ .{ -20, 180 }, .{ 150, 40 }, .{ 450, 300 }, .{ 660, 180 } }; const square = [_]Vec{ .{ 0, 0 }, .{ 50, 0 }, .{ 50, 50 }, .{ 0, 50 } }; for ([_]Join{ .miter, .round, .bevel }) |join| for ([_]Cap{ .butt, .round, .square }) |cap| { for ([_]f32{ 2, 12, 30 }) |w| for ([_]Affine{ .identity, .scale(-1, 1), .place(.{ 30, 40 }, 0.7) }) |xf| { t.clearRetainingCapacity(); try t.strokePath(gpa, &zigzag, .{ .width = w, .join = join, .cap = cap }, xf); try expectValid(&t); t.clearRetainingCapacity(); try t.strokePath(gpa, &square, .{ .width = w, .join = join, .closed = true }, xf); try expectValid(&t); }; t.clearRetainingCapacity(); try t.strokePath(gpa, &path_like, .{ .width = 40, .join = join, .cap = cap }, .identity); try expectValid(&t); }; // Round caps and joins add area: a round-capped segment is the stadium. t.clearRetainingCapacity(); try t.strokePath(gpa, &.{ .{ 10, 10 }, .{ 110, 10 } }, .{ .width = 20, .cap = .round }, .identity); try expectValid(&t); const stadium = triangleArea(&t); try testing.expectApproxEqRel(@as(f32, 100 * 20 + std.math.pi * 100), stadium, 0.01); t.clearRetainingCapacity(); try t.strokePath(gpa, &.{ .{ 10, 10 }, .{ 110, 10 } }, .{ .width = 20, .cap = .square }, .identity); try testing.expectApproxEqRel(@as(f32, 120 * 20), triangleArea(&t), 1e-4); // A zero-length path is a dot with round or square caps. t.clearRetainingCapacity(); try t.strokePath(gpa, &.{ .{ 5, 5 }, .{ 5, 5 } }, .{ .width = 4, .cap = .square }, .identity); try testing.expectApproxEqRel(@as(f32, 16), triangleArea(&t), 1e-4); t.clearRetainingCapacity(); try t.strokePath(gpa, &.{.{ 5, 5 }}, .{ .width = 4 }, .identity); try testing.expectEqual(@as(usize, 0), t.indices.items.len); } test "rects: filled and stroked, many in one tessellation" { const gpa = testing.allocator; var t: Tessellation = .empty; defer t.deinit(gpa); try t.fillRect(gpa, .{ .x = 10, .y = 20, .w = 30, .h = 40 }, .identity); try expectValid(&t); try testing.expectApproxEqRel(@as(f32, 1200), triangleArea(&t), 1e-5); t.clearRetainingCapacity(); try t.strokeRect(gpa, .{ .x = 10, .y = 20, .w = 30, .h = 40 }, 2, .identity); try expectValid(&t); try testing.expectApproxEqRel(@as(f32, 32 * 42 - 28 * 38), triangleArea(&t), 1e-4); t.clearRetainingCapacity(); for (0..4) |i| { const x: f32 = @floatFromInt(i * 40); try t.strokeRect(gpa, .{ .x = x, .y = 0, .w = 30, .h = 30 }, 1, .identity); } try testing.expectEqual(@as(usize, 8), t.ends.items.len); try t.fillRect(gpa, .{ .x = 0, .y = 0, .w = 0, .h = 5 }, .identity); try testing.expectEqual(@as(usize, 8), t.ends.items.len); } fn triangleArea(t: *const Tessellation) f32 { var sum: f32 = 0; var i: usize = 0; while (i < t.indices.items.len) : (i += 3) { const a = vec(t.points.items[t.indices.items[i]]); const b = vec(t.points.items[t.indices.items[i + 1]]); const c = vec(t.points.items[t.indices.items[i + 2]]); sum += math.cross(b - a, c - a) / 2; } return sum; }