diff options
Diffstat (limited to 'src/sketch/draw.zig')
| -rw-r--r-- | src/sketch/draw.zig | 1024 |
1 files changed, 1024 insertions, 0 deletions
diff --git a/src/sketch/draw.zig b/src/sketch/draw.zig new file mode 100644 index 0000000..c151ab2 --- /dev/null +++ b/src/sketch/draw.zig @@ -0,0 +1,1024 @@ +//! 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); + } + + /// 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); +} + +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 "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; +} |
