diff options
| author | Gabriel Schneider <[email protected]> | 2026-10-30 21:34:41 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-11-12 13:22:02 -0300 |
| commit | 2348776791e9dd17afeb12a06ba42a4a71917bcf (patch) | |
| tree | 780c4b12b76c8b97a28408dd40944d65f159fdc7 /src/vector | |
| parent | 590ba7b9b579b97e34b51ab7e3460ebc85713343 (diff) | |
| download | sketchbook-2348776791e9dd17afeb12a06ba42a4a71917bcf.tar.gz sketchbook-2348776791e9dd17afeb12a06ba42a4a71917bcf.zip | |
sketchbook: a drawing layer on top, host fixes for replay and migration
Diffstat (limited to 'src/vector')
| -rw-r--r-- | src/vector/Cpu.zig | 2 | ||||
| -rw-r--r-- | src/vector/Drawing.zig | 2 | ||||
| -rw-r--r-- | src/vector/Gpu.zig | 381 | ||||
| -rw-r--r-- | src/vector/Paint.zig | 2 | ||||
| -rw-r--r-- | src/vector/Polygons.zig | 59 | ||||
| -rw-r--r-- | src/vector/geom.zig | 239 | ||||
| -rw-r--r-- | src/vector/layouts.zig | 22 | ||||
| -rw-r--r-- | src/vector/morph.zig | 2 | ||||
| -rw-r--r-- | src/vector/root.zig | 15 | ||||
| -rw-r--r-- | src/vector/shaders/paint.frag (renamed from src/vector/shaders/cover.frag) | 14 | ||||
| -rw-r--r-- | src/vector/shaders/paint.vert | 15 | ||||
| -rw-r--r-- | src/vector/svg.zig | 2 |
12 files changed, 436 insertions, 319 deletions
diff --git a/src/vector/Cpu.zig b/src/vector/Cpu.zig index c17366f..ac5c6ea 100644 --- a/src/vector/Cpu.zig +++ b/src/vector/Cpu.zig @@ -6,7 +6,7 @@ //! wasm included, and is the reference the GPU backend is tested against. const Cpu = @This(); const std = @import("std"); -const geom = @import("geom.zig"); +const geom = @import("math"); const Drawing = @import("Drawing.zig"); const Polygons = @import("Polygons.zig"); const Paint = @import("Paint.zig"); diff --git a/src/vector/Drawing.zig b/src/vector/Drawing.zig index 0a3b77b..339f1ce 100644 --- a/src/vector/Drawing.zig +++ b/src/vector/Drawing.zig @@ -3,7 +3,7 @@ //! read and recombine them. const Drawing = @This(); const std = @import("std"); -const geom = @import("geom.zig"); +const geom = @import("math"); const Vec = geom.Vec; const Cubic = geom.Cubic; diff --git a/src/vector/Gpu.zig b/src/vector/Gpu.zig index 5853145..3c9d48c 100644 --- a/src/vector/Gpu.zig +++ b/src/vector/Gpu.zig @@ -1,16 +1,33 @@ -//! The GPU backend, as data: every fill becomes a stencil draw and a cover -//! draw in an `abi.gpu.Pass` that the host runs. Stencil-then-cover: -//! - stencil: the contours as triangle fans, counting windings in the -//! stencil buffer (increment/decrement by facing for nonzero, invert for -//! even-odd), color writes off; -//! - cover: the bounding box, painted where the stencil is set, zeroing the -//! stencil as it goes so the next fill starts clean. -//! Anti-aliasing is 8x multisampling. Paint runs in `cover.frag`, the GPU -//! twin of `Paint.zig`. +//! The GPU backend, as data: fills become draws in an `abi.gpu.Pass` that +//! the host runs. A fill is drawn one of two ways: +//! - direct, when its polygons are one convex contour: its triangle fan, +//! painted, covers each inside sample exactly once; +//! - stencil-then-cover otherwise: the contours as triangle fans count +//! windings in the stencil buffer (increment/decrement by facing for +//! nonzero, invert for even-odd), color writes off; then its bounding box +//! is painted where the stencil is set, zeroing the stencil as it goes so +//! the next fill starts clean. +//! +//! Fills are batched into layers, so the draw count follows how deep fills +//! pile up, not how many there are. A layer draws its stencil fans (one +//! draw per fill rule), then its cover boxes, then its direct fans, each in +//! one draw. A fill goes into the lowest layer that keeps the picture as if +//! every fill were drawn alone, in order: above every layer holding an +//! earlier fill whose box overlaps its own, except that a direct fill may +//! share the layer of what it overlaps (it is drawn after that layer's +//! covers, and after earlier direct fans in order). Stencilled fills in one +//! layer never overlap, so their stencils and covers cannot mix. Overlap is +//! judged on a coarse grid of the image, conservatively: neighbours in a +//! cell count as overlapping. +//! +//! Each vertex of a painted triangle carries its fill's paint: a solid +//! color, or the index of a gradient in a storage buffer of `Paint` blocks +//! uploaded with the pass. Anti-aliasing is 8x multisampling. Gradients run +//! in `paint.frag`, the GPU twin of `Paint.zig`. const Gpu = @This(); const std = @import("std"); const abi = @import("abi"); -const geom = @import("geom.zig"); +const geom = @import("math"); const Drawing = @import("Drawing.zig"); const Polygons = @import("Polygons.zig"); const Paint = @import("Paint.zig"); @@ -21,9 +38,13 @@ pub const samples = 8; const vertex: abi.gpu.Shader = .{ .code = shaders.path_vert, .uniform_buffers = 1 }; const stencil_only: abi.gpu.Shader = .{ .code = shaders.stencil_frag }; +const painted_vertex: abi.gpu.Shader = .{ .code = shaders.paint_vert, .uniform_buffers = 1 }; +const painted_fragment: abi.gpu.Shader = .{ .code = shaders.paint_frag, .storage_buffers = 1 }; + +pub const Pipeline = enum(u32) { nonzero, evenodd, cover, direct }; const pipelines = [_]abi.gpu.Pipeline{ - // 0: nonzero winding. + // Stencil fans, nonzero winding. abi.gpu.pipeline(layouts.Vertex, .{ .vertex = vertex, .fragment = stencil_only, @@ -31,7 +52,7 @@ const pipelines = [_]abi.gpu.Pipeline{ .write_color = false, .stencil = .{ .front = .{ .pass = .increment_and_wrap }, .back = .{ .pass = .decrement_and_wrap } }, }), - // 1: even-odd. + // Stencil fans, even-odd. abi.gpu.pipeline(layouts.Vertex, .{ .vertex = vertex, .fragment = stencil_only, @@ -39,30 +60,58 @@ const pipelines = [_]abi.gpu.Pipeline{ .write_color = false, .stencil = .{ .front = .{ .pass = .invert }, .back = .{ .pass = .invert } }, }), - // 2: cover. - abi.gpu.pipeline(layouts.Vertex, .{ - .vertex = vertex, - .fragment = .{ .code = shaders.cover_frag, .uniform_buffers = 1 }, + // Cover boxes. + abi.gpu.pipeline(layouts.Painted, .{ + .vertex = painted_vertex, + .fragment = painted_fragment, .stencil = .{ .front = .{ .compare = .not_equal, .pass = .zero }, .back = .{ .compare = .not_equal, .pass = .zero }, }, }), + // Convex fills, drawn directly. + abi.gpu.pipeline(layouts.Painted, .{ .vertex = painted_vertex, .fragment = painted_fragment }), +}; + +/// One layer's triangles, one draw each. +const Layer = struct { + /// Stencil fans by fill rule. + stencil: [2]std.ArrayList(layouts.Vertex) = .{ .empty, .empty }, + cover: std.ArrayList(layouts.Painted) = .empty, + direct: std.ArrayList(layouts.Painted) = .empty, }; +/// The overlap grid's cells are 2^shift pixels square. +const min_shift = 2; +const max_cells = 1 << 16; + width: u32, height: u32, image: abi.Image, /// Frame lifetime: the pass's vertices and uniforms live here until the /// host consumes the frame. arena: std.mem.Allocator = undefined, -draws: std.ArrayList(abi.gpu.Draw) = .empty, clear_color: [4]f32 = .{ 0, 0, 0, 0 }, viewport: []const u8 = &.{}, +layers: std.ArrayList(Layer) = .empty, +/// The gradients of this pass's fills, uploaded by `upload`. +paints: std.ArrayList(layouts.Paint) = .empty, +/// Per grid cell: 1 + the highest layer of a fill touching it; 0 if none. +grid: []u32 = &.{}, +shift: u5 = min_shift, +columns: u32 = 0, +draws: std.ArrayList(abi.gpu.Draw) = .empty, +/// GPU memory for `paints`, kept across frames: made, and remade larger, +/// by `upload`; freed by the renderer's `deinit`. +paint_buffer: abi.Buffer = .none, +paint_capacity: u32 = 0, pub fn begin(g: *Gpu, arena: std.mem.Allocator, clear: Drawing.Color) void { g.arena = arena; g.draws = .empty; + g.layers = .empty; + g.paints = .empty; + g.grid = &.{}; g.clear_color = Paint.premultiply(clear); g.viewport = abi.gpu.uniform(arena, layouts.Viewport{ .size = .{ @floatFromInt(g.width), @floatFromInt(g.height) } }); } @@ -73,45 +122,97 @@ pub fn fill(g: *Gpu, polys: *const Polygons, rule: Drawing.FillRule, paint: *con } fn record(g: *Gpu, polys: *const Polygons, rule: Drawing.FillRule, paint: *const Paint, alpha: f32) !void { + const b = polys.bounds(); + const lo = @max(@floor(b.min), geom.splat(0)); + const hi = @min(@ceil(b.max), geom.Vec{ @floatFromInt(g.width), @floatFromInt(g.height) }); + if (!(lo[0] < hi[0] and lo[1] < hi[1])) return; + const direct = polys.contours.items.len == 1 and Polygons.convex(polys.points.items); + const layer = try g.place(lo, hi, direct); + const p = try g.painted(paint, alpha); + if (direct) { + // A convex polygon's fan from its first point: no triangle overlaps + // another, so each sample inside is painted once. + const pts = polys.points.items; + const out = try layer.direct.addManyAsSlice(g.arena, (pts.len - 2) * 3); + for (1..pts.len - 1) |k| { + const tri = out[(k - 1) * 3 ..][0..3]; + tri.* = .{ p.at(pts[0]), p.at(pts[k]), p.at(pts[k + 1]) }; + } + return; + } // Fans from each contour's first point. Their overlaps cancel or add // exactly as the winding rule needs, so no triangulation is required. var triangles: usize = 0; var it = polys.iterator(); while (it.next()) |pts| triangles += pts.len - 2; - const fan = try g.arena.alloc(layouts.Vertex, triangles * 3); + const fan = try layer.stencil[@backingInt(rule)].addManyAsSlice(g.arena, triangles * 3); var i: usize = 0; it = polys.iterator(); while (it.next()) |pts| for (1..pts.len - 1) |k| { - fan[i + 0] = .{ .position = pts[0] }; - fan[i + 1] = .{ .position = pts[k] }; - fan[i + 2] = .{ .position = pts[k + 1] }; + fan[i..][0..3].* = .{ .{ .position = pts[0] }, .{ .position = pts[k] }, .{ .position = pts[k + 1] } }; i += 3; }; - const b = polys.bounds(); - const lo = @max(@floor(b.min), geom.splat(0)); - const hi = @min(@ceil(b.max), geom.Vec{ @floatFromInt(g.width), @floatFromInt(g.height) }); - if (lo[0] >= hi[0] or lo[1] >= hi[1]) return; - const quad = try g.arena.dupe(layouts.Vertex, &.{ - .{ .position = .{ lo[0], lo[1] } }, .{ .position = .{ hi[0], lo[1] } }, .{ .position = .{ hi[0], hi[1] } }, - .{ .position = .{ lo[0], lo[1] } }, .{ .position = .{ hi[0], hi[1] } }, .{ .position = .{ lo[0], hi[1] } }, - }); - try g.draws.append(g.arena, .{ - .pipeline = if (rule == .nonzero) 0 else 1, - .vertices = std.mem.sliceAsBytes(fan), - .vertex_count = @intCast(fan.len), - .vertex_uniforms = g.viewport, - }); - try g.draws.append(g.arena, .{ - .pipeline = 2, - .vertices = std.mem.sliceAsBytes(quad), - .vertex_count = 6, - .vertex_uniforms = g.viewport, - .fragment_uniforms = abi.gpu.uniform(g.arena, block(paint, alpha)), + try layer.cover.appendSlice(g.arena, &.{ + p.at(.{ lo[0], lo[1] }), p.at(.{ hi[0], lo[1] }), p.at(.{ hi[0], hi[1] }), + p.at(.{ lo[0], lo[1] }), p.at(.{ hi[0], hi[1] }), p.at(.{ lo[0], hi[1] }), }); } -/// `Paint` as the shader's uniform block. More stops than the block holds -/// are resampled evenly. +/// The layer for a fill covering pixels `lo` to `hi`, its cells marked. +fn place(g: *Gpu, lo: geom.Vec, hi: geom.Vec, direct: bool) !*Layer { + if (g.grid.len == 0) { + g.shift = min_shift; + while (cells(g.width, g.shift) * cells(g.height, g.shift) > max_cells) g.shift += 1; + g.columns = cells(g.width, g.shift); + g.grid = try g.arena.alloc(u32, g.columns * cells(g.height, g.shift)); + @memset(g.grid, 0); + } + const x0: u32 = @as(u32, @intFromFloat(lo[0])) >> g.shift; + const y0: u32 = @as(u32, @intFromFloat(lo[1])) >> g.shift; + const x1: u32 = (@as(u32, @intFromFloat(hi[0])) - 1) >> g.shift; + const y1: u32 = (@as(u32, @intFromFloat(hi[1])) - 1) >> g.shift; + var top: u32 = 0; + for (y0..y1 + 1) |y| for (g.grid[y * g.columns ..][x0 .. x1 + 1]) |cell| { + top = @max(top, cell); + }; + const index = layerFor(top, direct); + for (y0..y1 + 1) |y| for (g.grid[y * g.columns ..][x0 .. x1 + 1]) |*cell| { + cell.* = @max(cell.*, index + 1); + }; + while (g.layers.items.len <= index) try g.layers.append(g.arena, .{}); + return &g.layers.items[index]; +} + +/// The layer for a fill whose box overlaps fills up to layer `top - 1` +/// (`top` 0: none). A direct fill may join that layer; a stencilled one +/// goes above it. +pub fn layerFor(top: u32, direct: bool) u32 { + if (top == 0) return 0; + return if (direct) top - 1 else top; +} + +fn cells(pixels: u32, shift: u5) u32 { + return @max((pixels + (@as(u32, 1) << shift) - 1) >> shift, 1); +} + +/// A fill's paint, as its vertices carry it. +const Painted = struct { + color: [4]f32, + gradient: f32, + + fn at(p: Painted, q: geom.Vec) layouts.Painted { + return .{ .position = q, .color = p.color, .gradient = p.gradient }; + } +}; + +fn painted(g: *Gpu, paint: *const Paint, alpha: f32) !Painted { + if (paint.kind == .solid) return .{ .color = paint.color * @as(@Vector(4, f32), @splat(alpha)), .gradient = -1 }; + try g.paints.append(g.arena, block(paint, alpha)); + return .{ .color = @splat(alpha), .gradient = @floatFromInt(g.paints.items.len - 1) }; +} + +/// `Paint` as the shader's block. More stops than the block holds are +/// resampled evenly. fn block(paint: *const Paint, alpha: f32) layouts.Paint { const m = paint.to_gradient; var out: layouts.Paint = .{ @@ -140,8 +241,36 @@ fn unpremultiply(c: @Vector(4, f32)) [4]f32 { return .{ c[0] / c[3], c[1] / c[3], c[2] / c[3], c[3] }; } +/// Puts this pass's gradients in GPU memory, before `pass`. `f` is a +/// `sketch.Frame`. Painted draws bind the buffer even when no fill has a +/// gradient, so there always is one. +pub fn upload(g: *Gpu, f: anytype) void { + const count: u32 = @intCast(@max(g.paints.items.len, 1)); + if (count > g.paint_capacity) { + if (g.paint_buffer != .none) f.host.freeBuffer(g.paint_buffer); + const capacity = std.math.ceilPowerOfTwo(u32, count) catch count; + g.paint_buffer = f.host.newBuffer(capacity * @sizeOf(layouts.Paint)); + g.paint_capacity = if (g.paint_buffer == .none) 0 else capacity; + } + if (g.paints.items.len > 0 and g.paint_buffer != .none) f.upload(g.paint_buffer, 0, std.mem.sliceAsBytes(g.paints.items)); +} + +/// Frees what `upload` made. `host` is a `sketch.Host`. +pub fn deinit(g: *Gpu, host: anytype) void { + if (g.paint_buffer != .none) host.freeBuffer(g.paint_buffer); + g.paint_buffer = .none; + g.paint_capacity = 0; +} + /// The pass that draws everything recorded since `begin`. -pub fn pass(g: *const Gpu) abi.gpu.Pass { +pub fn pass(g: *Gpu) abi.gpu.Pass { + g.draws = .empty; + const storage = g.arena.dupe(abi.Buffer, &.{g.paint_buffer}) catch &.{}; + for (g.layers.items) |*layer| { + for (layer.stencil, [_]Pipeline{ .nonzero, .evenodd }) |fans, pipeline| g.add(pipeline, std.mem.sliceAsBytes(fans.items), fans.items.len, storage); + g.add(.cover, std.mem.sliceAsBytes(layer.cover.items), layer.cover.items.len, storage); + g.add(.direct, std.mem.sliceAsBytes(layer.direct.items), layer.direct.items.len, storage); + } return .{ .image = g.image, .width = g.width, @@ -154,21 +283,151 @@ pub fn pass(g: *const Gpu) abi.gpu.Pass { }; } -test "a fill is a stencil fan and a covering quad with its paint" { - var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); - defer arena.deinit(); - var g: Gpu = .{ .width = 100, .height = 50, .image = @fromBackingInt(@intCast(1)) }; - g.begin(arena.allocator(), .{ 0, 0, 0, 1 }); - var p: Polygons = .init(arena.allocator()); - try p.points.appendSlice(arena.allocator(), &.{ .{ 10, 10 }, .{ 40, 10 }, .{ 40, 30 }, .{ 10, 30 } }); - try p.contours.append(arena.allocator(), 4); - const red: Paint = .solid(.{ 1, 0, 0, 1 }); - g.fill(&p, .evenodd, &red, 0.5); - const pass_ = g.pass(); - try std.testing.expectEqual(@as(usize, 2), pass_.draws.len); - try std.testing.expectEqual(@as(u32, 1), pass_.draws[0].pipeline); - try std.testing.expectEqual(@as(u32, 6), pass_.draws[0].vertex_count); - const block_ = std.mem.bytesAsValue(layouts.Paint, pass_.draws[1].fragment_uniforms); - try std.testing.expectEqual(@as(f32, 0.5), block_.extra[1]); - try std.testing.expectEqual(@as(f32, 1), block_.color[0]); +fn add(g: *Gpu, pipeline: Pipeline, vertices: []const u8, count: usize, storage: []const abi.Buffer) void { + if (count == 0) return; + const painted_ = pipeline == .cover or pipeline == .direct; + g.draws.append(g.arena, .{ + .pipeline = @backingInt(pipeline), + .vertices = vertices, + .vertex_count = @intCast(count), + .vertex_uniforms = g.viewport, + .fragment_storage = if (painted_) storage else &.{}, + }) catch {}; +} + +// --------------------------------------------------------------------------- +// Tests + +const Test = struct { + arena: std.heap.ArenaAllocator, + g: Gpu, + p: Polygons, + + fn init(t: *Test) void { + t.arena = .init(std.testing.allocator); + t.g = .{ .width = 100, .height = 50, .image = @fromBackingInt(@intCast(1)) }; + t.g.begin(t.arena.allocator(), .{ 0, 0, 0, 1 }); + t.p = .init(t.arena.allocator()); + } + + fn deinit(t: *Test) void { + t.arena.deinit(); + } + + /// Fills the contours `shape`, offset by `at`. + fn fill(t: *Test, shape: []const []const geom.Vec, at: geom.Vec, rule: Drawing.FillRule, paint: Paint) !void { + t.p.clear(); + for (shape) |pts| { + for (pts) |q| try t.p.points.append(t.arena.allocator(), q + at); + try t.p.contours.append(t.arena.allocator(), @intCast(pts.len)); + } + t.g.fill(&t.p, rule, &paint, 1); + } + + fn pipelinesOf(t: *Test) ![]const Pipeline { + const draws = t.g.pass().draws; + const out = try t.arena.allocator().alloc(Pipeline, draws.len); + for (draws, out) |d, *o| o.* = @fromBackingInt(@intCast(d.pipeline)); + return out; + } +}; + +const square: []const []const geom.Vec = &.{&.{ .{ 0, 0 }, .{ 10, 0 }, .{ 10, 10 }, .{ 0, 10 } }}; +/// Not convex: two contours. +const ring: []const []const geom.Vec = &.{ &.{ .{ 0, 0 }, .{ 10, 0 }, .{ 10, 10 }, .{ 0, 10 } }, &.{ .{ 3, 3 }, .{ 3, 7 }, .{ 7, 7 }, .{ 7, 3 } } }; +const red: Paint = .solid(.{ 1, 0, 0, 1 }); + +test "a convex fill is one painted fan, no stencil" { + var t: Test = undefined; + t.init(); + defer t.deinit(); + try t.fill(square, .{ 10, 10 }, .evenodd, red); + const draws = t.g.pass().draws; + try std.testing.expectEqual(@as(usize, 1), draws.len); + try std.testing.expectEqual(@backingInt(Pipeline.direct), draws[0].pipeline); + try std.testing.expectEqual(@as(u32, 6), draws[0].vertex_count); + const v = std.mem.bytesAsSlice(layouts.Painted, draws[0].vertices); + try std.testing.expectEqual([4]f32{ 1, 0, 0, 1 }, v[0].color); + try std.testing.expectEqual(@as(f32, -1), v[0].gradient); +} + +test "a fill that is not convex is a stencil fan and a covering quad with its paint" { + var t: Test = undefined; + t.init(); + defer t.deinit(); + t.p.clear(); + const half: Paint = .solid(.{ 1, 0, 0, 0.5 }); + try t.fill(ring, .{ 10, 10 }, .evenodd, half); + const draws = t.g.pass().draws; + try std.testing.expectEqualSlices(Pipeline, &.{ .evenodd, .cover }, try t.pipelinesOf()); + try std.testing.expectEqual(@as(u32, 12), draws[0].vertex_count); + try std.testing.expectEqual(@as(u32, 6), draws[1].vertex_count); + const v = std.mem.bytesAsSlice(layouts.Painted, draws[1].vertices); + try std.testing.expectEqual([4]f32{ 0.5, 0, 0, 0.5 }, v[0].color); + try std.testing.expectEqual(geom.Vec{ 10, 10 }, v[0].position); + try std.testing.expectEqual(geom.Vec{ 20, 20 }, v[2].position); +} + +test "fills batch into layers: disjoint ones share draws, overlapping ones keep their order" { + var t: Test = undefined; + t.init(); + defer t.deinit(); + // Three disjoint rings, both rules: one layer, a stencil draw per rule + // and one cover draw for all three. + try t.fill(ring, .{ 0, 0 }, .nonzero, red); + try t.fill(ring, .{ 30, 0 }, .evenodd, red); + try t.fill(ring, .{ 60, 0 }, .nonzero, red); + try std.testing.expectEqualSlices(Pipeline, &.{ .nonzero, .evenodd, .cover }, try t.pipelinesOf()); + try std.testing.expectEqual(@as(u32, 18), t.g.pass().draws[2].vertex_count); + // A convex fill over the first ring joins its layer, drawn after the + // covers; a second one over it too, after it. + try t.fill(square, .{ 5, 5 }, .nonzero, red); + try t.fill(square, .{ 8, 8 }, .nonzero, red); + try std.testing.expectEqualSlices(Pipeline, &.{ .nonzero, .evenodd, .cover, .direct }, try t.pipelinesOf()); + // A ring over those goes above them; so does a convex fill over it. + try t.fill(ring, .{ 10, 10 }, .nonzero, red); + try t.fill(square, .{ 12, 12 }, .nonzero, red); + try std.testing.expectEqualSlices(Pipeline, &.{ .nonzero, .evenodd, .cover, .direct, .nonzero, .cover, .direct }, try t.pipelinesOf()); + // Far from everything: the bottom layer again. + try t.fill(ring, .{ 80, 30 }, .evenodd, red); + try std.testing.expectEqualSlices(Pipeline, &.{ .nonzero, .evenodd, .cover, .direct, .nonzero, .cover, .direct }, try t.pipelinesOf()); + try std.testing.expectEqual(@as(u32, 24), t.g.pass().draws[2].vertex_count); +} + +test "layers: stencilled fills go above what they overlap, direct ones join it" { + try std.testing.expectEqual(@as(u32, 0), layerFor(0, false)); + try std.testing.expectEqual(@as(u32, 0), layerFor(0, true)); + try std.testing.expectEqual(@as(u32, 3), layerFor(3, false)); + try std.testing.expectEqual(@as(u32, 2), layerFor(3, true)); +} + +test "gradients go to the paint buffer, their vertices carry the index and alpha" { + var t: Test = undefined; + t.init(); + defer t.deinit(); + const stops = [_]Drawing.Gradient.Stop{ .{ .offset = 0, .color = .{ 1, 0, 0, 1 } }, .{ .offset = 1, .color = .{ 0, 0, 1, 1 } } }; + const gradient: Paint = .{ .kind = .linear, .p1 = .{ 1, 0 }, .stops = &stops }; + try t.fill(square, .{ 0, 0 }, .nonzero, red); + t.p.clear(); + try t.p.points.appendSlice(t.arena.allocator(), &.{ .{ 30, 0 }, .{ 40, 0 }, .{ 40, 10 }, .{ 30, 10 } }); + try t.p.contours.append(t.arena.allocator(), 4); + t.g.fill(&t.p, .nonzero, &gradient, 0.25); + try std.testing.expectEqual(@as(usize, 1), t.g.paints.items.len); + try std.testing.expectEqual(@as(f32, 2), t.g.paints.items[0].extra[2]); + const draws = t.g.pass().draws; + try std.testing.expectEqual(@as(usize, 1), draws.len); + try std.testing.expectEqual(@as(usize, 1), draws[0].fragment_storage.len); + const v = std.mem.bytesAsSlice(layouts.Painted, draws[0].vertices); + try std.testing.expectEqual(@as(f32, -1), v[0].gradient); + try std.testing.expectEqual(@as(f32, 0), v[6].gradient); + try std.testing.expectEqual([4]f32{ 0.25, 0.25, 0.25, 0.25 }, v[6].color); +} + +test "fills outside the image draw nothing" { + var t: Test = undefined; + t.init(); + defer t.deinit(); + try t.fill(square, .{ 200, 0 }, .nonzero, red); + try t.fill(ring, .{ -50, 0 }, .nonzero, red); + try std.testing.expectEqual(@as(usize, 0), t.g.pass().draws.len); } diff --git a/src/vector/Paint.zig b/src/vector/Paint.zig index fb838d0..0c56588 100644 --- a/src/vector/Paint.zig +++ b/src/vector/Paint.zig @@ -4,7 +4,7 @@ //! which mirrors `param` and `stopColor`. const Paint = @This(); const std = @import("std"); -const geom = @import("geom.zig"); +const geom = @import("math"); const Drawing = @import("Drawing.zig"); const Vec = geom.Vec; diff --git a/src/vector/Polygons.zig b/src/vector/Polygons.zig index c0ed335..c64db3d 100644 --- a/src/vector/Polygons.zig +++ b/src/vector/Polygons.zig @@ -4,7 +4,7 @@ //! the same way, so the nonzero rule unions them. const Polygons = @This(); const std = @import("std"); -const geom = @import("geom.zig"); +const geom = @import("math"); const Drawing = @import("Drawing.zig"); const Vec = geom.Vec; const Affine = geom.Affine; @@ -97,6 +97,44 @@ pub fn bounds(p: *const Polygons) geom.Bounds { return b; } +/// Whether `pts`, as a closed contour, is a convex polygon going around once: +/// every turn the same way (straight runs and repeated points allowed), and +/// the edge direction's x flips sign at most twice, which rules out +/// spirals. Its fan from any point then covers each inside point once and +/// nothing outside, under either fill rule. Exact: the slightest reflex +/// turn says no. +pub fn convex(pts: []const Vec) bool { + var turn: f32 = 0; + var flips: u32 = 0; + var first: ?Vec = null; + var prev: Vec = undefined; + var first_sign: f32 = 0; + var last_sign: f32 = 0; + for (0..pts.len) |i| { + const e = pts[(i + 1) % pts.len] - pts[i]; + if (e[0] == 0 and e[1] == 0) continue; + if (first == null) first = e else if (!turns(prev, e, &turn)) return false; + prev = e; + if (e[0] != 0) { + const sign = std.math.sign(e[0]); + if (first_sign == 0) first_sign = sign else if (sign != last_sign) flips += 1; + last_sign = sign; + } + } + if (!turns(prev, first orelse return false, &turn)) return false; + if (last_sign != first_sign) flips += 1; + return turn != 0 and flips <= 2; +} + +/// Whether the corner from edge `a` to edge `b` turns the way `turn` (the +/// first nonzero cross product so far) does, or goes straight on. +fn turns(a: Vec, b: Vec, turn: *f32) bool { + const cross = geom.cross(a, b); + if (cross == 0) return geom.dot(a, b) > 0; + if (turn.* == 0) turn.* = cross; + return (cross > 0) == (turn.* > 0); +} + /// Iterates contours as point slices. pub fn iterator(p: *const Polygons) Iterator { return .{ .p = p }; @@ -368,6 +406,25 @@ fn truncate(list: *std.ArrayList(Vec), len: f32) []const Vec { return pts; } +test "convex contours" { + const square = [_]Vec{ .{ 0, 0 }, .{ 10, 0 }, .{ 10, 10 }, .{ 0, 10 } }; + try std.testing.expect(convex(&square)); + // Either orientation, repeated points, a closing point equal to the + // first, straight runs. + try std.testing.expect(convex(&.{ .{ 0, 10 }, .{ 10, 10 }, .{ 10, 0 }, .{ 0, 0 } })); + try std.testing.expect(convex(&.{ .{ 0, 0 }, .{ 5, 0 }, .{ 5, 0 }, .{ 10, 0 }, .{ 10, 10 }, .{ 0, 10 }, .{ 0, 0 } })); + // A reflex corner (an L), a bow tie, a pentagram, a square wound twice, + // a line and a point. + try std.testing.expect(!convex(&.{ .{ 0, 0 }, .{ 10, 0 }, .{ 10, 5 }, .{ 5, 5 }, .{ 5, 10 }, .{ 0, 10 } })); + try std.testing.expect(!convex(&.{ .{ 0, 0 }, .{ 10, 10 }, .{ 10, 0 }, .{ 0, 10 } })); + var star: [5]Vec = undefined; + for (&star, 0..) |*q, i| q.* = geom.unit(@as(f32, @floatFromInt(i * 2)) * std.math.tau / 5) * geom.splat(10); + try std.testing.expect(!convex(&star)); + try std.testing.expect(!convex(&(square ++ square))); + try std.testing.expect(!convex(&.{ .{ 0, 0 }, .{ 10, 0 }, .{ 20, 0 } })); + try std.testing.expect(!convex(&.{ .{ 1, 1 }, .{ 1, 1 }, .{ 1, 1 } })); +} + test "a square stroke is four quads and four miters, all wound one way" { var p: Polygons = .init(std.testing.allocator); defer p.deinit(); diff --git a/src/vector/geom.zig b/src/vector/geom.zig deleted file mode 100644 index b80c55a..0000000 --- a/src/vector/geom.zig +++ /dev/null @@ -1,239 +0,0 @@ -//! Points, affine transforms and cubic Béziers: the only geometry there is. -//! Every path is a list of cubics, lines included, as in manim: one shape of -//! data makes morphing and partial drawing plain arithmetic. -const std = @import("std"); - -pub const Vec = @Vector(2, f32); - -pub fn vec(x: f32, y: f32) Vec { - return .{ x, y }; -} -pub fn dot(a: Vec, b: Vec) f32 { - return @reduce(.Add, a * b); -} -pub fn cross(a: Vec, b: Vec) f32 { - return a[0] * b[1] - a[1] * b[0]; -} -pub fn length(a: Vec) f32 { - return @sqrt(dot(a, a)); -} -pub fn splat(s: f32) Vec { - return @splat(s); -} -pub fn mix(a: Vec, b: Vec, t: f32) Vec { - return a + (b - a) * splat(t); -} -/// Perpendicular, rotated a quarter turn counterclockwise in y-down space. -pub fn perp(a: Vec) Vec { - return .{ a[1], -a[0] }; -} -pub fn normalize(a: Vec) Vec { - const l = length(a); - return if (l > 0) a / splat(l) else a; -} - -/// `[a c e; b d f]`, SVG's `matrix(a b c d e f)`. -pub const Affine = struct { - a: f32 = 1, - b: f32 = 0, - c: f32 = 0, - d: f32 = 1, - e: f32 = 0, - f: f32 = 0, - - pub const identity: Affine = .{}; - - pub fn translate(x: f32, y: f32) Affine { - return .{ .e = x, .f = y }; - } - pub fn scale(sx: f32, sy: f32) Affine { - return .{ .a = sx, .d = sy }; - } - pub fn rotate(radians: f32) Affine { - const c = @cos(radians); - const s = @sin(radians); - return .{ .a = c, .b = s, .c = -s, .d = c }; - } - pub fn skew(x: f32, y: f32) Affine { - return .{ .b = @tan(y), .c = @tan(x) }; - } - /// `self` after `inner`: apply `inner` first. - pub fn mul(self: Affine, inner: Affine) Affine { - return .{ - .a = self.a * inner.a + self.c * inner.b, - .b = self.b * inner.a + self.d * inner.b, - .c = self.a * inner.c + self.c * inner.d, - .d = self.b * inner.c + self.d * inner.d, - .e = self.a * inner.e + self.c * inner.f + self.e, - .f = self.b * inner.e + self.d * inner.f + self.f, - }; - } - pub fn apply(m: Affine, p: Vec) Vec { - return .{ m.a * p[0] + m.c * p[1] + m.e, m.b * p[0] + m.d * p[1] + m.f }; - } - pub fn applyVector(m: Affine, p: Vec) Vec { - return .{ m.a * p[0] + m.c * p[1], m.b * p[0] + m.d * p[1] }; - } - pub fn determinant(m: Affine) f32 { - return m.a * m.d - m.b * m.c; - } - /// How much the transform scales lengths, on average. - pub fn scaleFactor(m: Affine) f32 { - return @sqrt(@abs(m.determinant())); - } - pub fn invert(m: Affine) Affine { - const det = m.determinant(); - if (det == 0) return .{}; - const i = 1 / det; - return .{ - .a = m.d * i, - .b = -m.b * i, - .c = -m.c * i, - .d = m.a * i, - .e = (m.c * m.f - m.d * m.e) * i, - .f = (m.b * m.e - m.a * m.f) * i, - }; - } -}; - -pub const Rect = struct { - x: f32 = 0, - y: f32 = 0, - w: f32 = 0, - h: f32 = 0, - - pub fn center(r: Rect) Vec { - return .{ r.x + r.w / 2, r.y + r.h / 2 }; - } -}; - -/// Growing bounds over points. -pub const Bounds = struct { - min: Vec = splat(std.math.inf(f32)), - max: Vec = splat(-std.math.inf(f32)), - - pub fn add(b: *Bounds, p: Vec) void { - b.min = @min(b.min, p); - b.max = @max(b.max, p); - } - pub fn empty(b: Bounds) bool { - return b.min[0] > b.max[0]; - } - pub fn rect(b: Bounds) Rect { - if (b.empty()) return .{}; - return .{ .x = b.min[0], .y = b.min[1], .w = b.max[0] - b.min[0], .h = b.max[1] - b.min[1] }; - } -}; - -/// A cubic's four control points. -pub const Cubic = [4]Vec; - -pub fn line(a: Vec, b: Vec) Cubic { - return .{ a, mix(a, b, 1.0 / 3.0), mix(a, b, 2.0 / 3.0), b }; -} - -pub fn quad(a: Vec, c: Vec, b: Vec) Cubic { - return .{ a, mix(a, c, 2.0 / 3.0), mix(b, c, 2.0 / 3.0), b }; -} - -pub fn eval(c: Cubic, t: f32) Vec { - const u = 1 - t; - return c[0] * splat(u * u * u) + c[1] * splat(3 * u * u * t) + c[2] * splat(3 * u * t * t) + c[3] * splat(t * t * t); -} - -/// de Casteljau: the two halves of `c` at `t`. -pub fn split(c: Cubic, t: f32) [2]Cubic { - const ab = mix(c[0], c[1], t); - const bc = mix(c[1], c[2], t); - const cd = mix(c[2], c[3], t); - const abc = mix(ab, bc, t); - const bcd = mix(bc, cd, t); - const p = mix(abc, bcd, t); - return .{ .{ c[0], ab, abc, p }, .{ p, bcd, cd, c[3] } }; -} - -/// Line segments needed to stay within `tolerance` of the curve. -pub fn flattenCount(c: Cubic, tolerance: f32) u32 { - const d1 = c[0] - splat(2) * c[1] + c[2]; - const d2 = c[1] - splat(2) * c[2] + c[3]; - const dd = @max(length(d1), length(d2)); - const n = @ceil(@sqrt(0.75 * dd / tolerance)); - return @intFromFloat(std.math.clamp(n, 1, 256)); -} - -/// A cheap length estimate: between chord and control polygon. -pub fn roughLength(c: Cubic) f32 { - const chord = length(c[3] - c[0]); - const polygon = length(c[1] - c[0]) + length(c[2] - c[1]) + length(c[3] - c[2]); - return (chord + polygon) / 2; -} - -/// Cubics for an SVG elliptical arc from `p0` to `p1` (endpoint form). -pub fn arc(out: *std.ArrayList(Cubic), gpa: std.mem.Allocator, p0: Vec, radii: Vec, x_rotation_degrees: f32, large: bool, sweep: bool, p1: Vec) !void { - var rx = @abs(radii[0]); - var ry = @abs(radii[1]); - if (rx == 0 or ry == 0 or @reduce(.And, p0 == p1)) { - if (!@reduce(.And, p0 == p1)) try out.append(gpa, line(p0, p1)); - return; - } - const phi = x_rotation_degrees * std.math.pi / 180; - const cos_phi = @cos(phi); - const sin_phi = @sin(phi); - const half = (p0 - p1) / splat(2); - const x1 = cos_phi * half[0] + sin_phi * half[1]; - const y1 = -sin_phi * half[0] + cos_phi * half[1]; - // Radii too small to reach are scaled up, as the SVG spec says. - const lambda = (x1 * x1) / (rx * rx) + (y1 * y1) / (ry * ry); - if (lambda > 1) { - rx *= @sqrt(lambda); - ry *= @sqrt(lambda); - } - const num = rx * rx * ry * ry - rx * rx * y1 * y1 - ry * ry * x1 * x1; - const den = rx * rx * y1 * y1 + ry * ry * x1 * x1; - var coef = @sqrt(@max(0, num / den)); - if (large == sweep) coef = -coef; - const cx1 = coef * rx * y1 / ry; - const cy1 = -coef * ry * x1 / rx; - const mid = (p0 + p1) / splat(2); - const center: Vec = .{ cos_phi * cx1 - sin_phi * cy1 + mid[0], sin_phi * cx1 + cos_phi * cy1 + mid[1] }; - const start = std.math.atan2((y1 - cy1) / ry, (x1 - cx1) / rx); - var delta = std.math.atan2((-y1 - cy1) / ry, (-x1 - cx1) / rx) - start; - if (sweep and delta < 0) delta += 2 * std.math.pi; - if (!sweep and delta > 0) delta -= 2 * std.math.pi; - const pieces: u32 = @intFromFloat(@max(1, @ceil(@abs(delta) / (std.math.pi / 2.0) - 1e-4))); - const step = delta / @as(f32, @floatFromInt(pieces)); - const k = 4.0 / 3.0 * @tan(step / 4); - const m: Affine = (Affine{ .a = cos_phi, .b = sin_phi, .c = -sin_phi, .d = cos_phi, .e = center[0], .f = center[1] }).mul(.scale(rx, ry)); - var angle = start; - var from = p0; - for (0..pieces) |i| { - const next = angle + step; - const a: Vec = .{ @cos(angle), @sin(angle) }; - const b: Vec = .{ @cos(next), @sin(next) }; - const to = if (i + 1 == pieces) p1 else m.apply(b); - try out.append(gpa, .{ from, m.apply(a + perp(a) * splat(-k)), m.apply(b - perp(b) * splat(-k)), to }); - from = to; - angle = next; - } -} - -test "affine composition and inversion round trip" { - const m = Affine.translate(10, 5).mul(.rotate(0.7)).mul(.scale(2, 3)); - const p = vec(3, -4); - const q = m.invert().apply(m.apply(p)); - try std.testing.expectApproxEqAbs(p[0], q[0], 1e-4); - try std.testing.expectApproxEqAbs(p[1], q[1], 1e-4); -} - -test "a half-circle arc stays on the circle" { - var cubics: std.ArrayList(Cubic) = .empty; - defer cubics.deinit(std.testing.allocator); - try arc(&cubics, std.testing.allocator, vec(-10, 0), vec(10, 10), 0, false, true, vec(10, 0)); - try std.testing.expectEqual(@as(usize, 2), cubics.items.len); - for (cubics.items) |c| for (0..9) |i| { - const r = length(eval(c, @as(f32, @floatFromInt(i)) / 8)); - try std.testing.expectApproxEqAbs(@as(f32, 10), r, 0.03); - }; - // Sweep flag 1 in y-down space goes through negative y. - try std.testing.expect(eval(cubics.items[0], 1)[1] < -9.9); -} diff --git a/src/vector/layouts.zig b/src/vector/layouts.zig index 097e682..5d17568 100644 --- a/src/vector/layouts.zig +++ b/src/vector/layouts.zig @@ -4,13 +4,26 @@ pub const max_stops = 32; -/// A path point in device pixels. +/// A path point in device pixels, for stencil fans. pub const Vertex = extern struct { position: [2]f32, pub const glsl = .vertex; }; +/// A point of a painted triangle (a cover quad, or a convex fill's fan), +/// carrying its fill's paint, so fills of any paint share one draw. +pub const Painted = extern struct { + position: [2]f32, + /// Solid paints: the premultiplied color times the fill's alpha. + /// Gradients: the alpha, in all four. + color: [4]f32, + /// The gradient's index in the pass's `Paint` buffer; -1 for solid. + gradient: f32, + + pub const glsl = .vertex; +}; + pub const Viewport = extern struct { size: [2]f32, pad: [2]f32 = .{ 0, 0 }, @@ -18,7 +31,8 @@ pub const Viewport = extern struct { pub const glsl = .{ .uniform = .{ .set = 1, .instance = "viewport" } }; }; -/// A resolved `Paint`, as `cover.frag` reads it. +/// A resolved gradient `Paint`, as `paint.frag` reads it from a storage +/// buffer (all members are vec4s, so std430 lays it out as std140 would). pub const Paint = extern struct { /// Premultiplied solid color. color: [4]f32, @@ -29,12 +43,12 @@ pub const Paint = extern struct { row1: [4]f32, /// p0 then p1. points: [4]f32, - /// Radius, alpha, stop count. + /// Radius, alpha (unused: the vertices carry it), stop count. extra: [4]f32, /// Stop offsets, four per element. offsets: [max_stops / 4][4]f32, /// Straight stop colors. colors: [max_stops][4]f32, - pub const glsl = .{ .uniform = .{ .set = 3, .instance = "paint" } }; + pub const glsl = .plain; }; diff --git a/src/vector/morph.zig b/src/vector/morph.zig index 319eccf..f285c7e 100644 --- a/src/vector/morph.zig +++ b/src/vector/morph.zig @@ -4,7 +4,7 @@ //! color is interpolated. A shape without a partner collapses to (or grows //! from) the other drawing's center. const std = @import("std"); -const geom = @import("geom.zig"); +const geom = @import("math"); const Drawing = @import("Drawing.zig"); const Vec = geom.Vec; const Cubic = geom.Cubic; diff --git a/src/vector/root.zig b/src/vector/root.zig index 0414286..e5e9975 100644 --- a/src/vector/root.zig +++ b/src/vector/root.zig @@ -1,11 +1,12 @@ //! Vector graphics for sketches: SVG in, cubic geometry as data, and two //! interchangeable renderers. The CPU backend computes exact coverage and //! runs anywhere (it is also the reference in tests); the GPU backend -//! describes stencil-then-cover passes for the host to run. The backend is +//! describes passes for the host to run: convex fills drawn directly, the +//! rest stencil-then-cover, batched into a few draws (see `Gpu.zig`). The backend is //! a comptime choice: `vector.Renderer(.gpu)` or `vector.Renderer(.cpu)`. const std = @import("std"); const abi = @import("abi"); -pub const geom = @import("geom.zig"); +pub const geom = @import("math"); pub const Drawing = @import("Drawing.zig"); pub const svg = @import("svg.zig"); pub const Polygons = @import("Polygons.zig"); @@ -57,7 +58,10 @@ pub fn Renderer(comptime backend: Backend) type { } pub fn deinit(r: *Self, host: anytype) void { - if (backend == .cpu) r.target.deinit(); + switch (backend) { + .cpu => r.target.deinit(), + .gpu => r.target.deinit(host), + } r.polys.deinit(); host.freeImage(r.image); } @@ -118,7 +122,10 @@ pub fn Renderer(comptime backend: Backend) type { pub fn present(r: *Self, f: anytype, dst: anytype) void { switch (backend) { .cpu => f.pixels(r.image, r.target.width, r.target.height, r.target.pixels, .{ .premultiplied = true }), - .gpu => f.gpu(r.target.pass()), + .gpu => { + r.target.upload(f); + f.gpu(r.target.pass()); + }, } f.image(r.image, dst, .{}); } diff --git a/src/vector/shaders/cover.frag b/src/vector/shaders/paint.frag index a57a916..97eb551 100644 --- a/src/vector/shaders/cover.frag +++ b/src/vector/shaders/paint.frag @@ -1,11 +1,16 @@ #version 450 #extension GL_GOOGLE_include_directive : require -// Paints the covered pixels. Mirrors vector/Paint.zig: `param` gives the -// gradient parameter, `stop_color` the color at it. The uniform block is -// generated from vector/layouts.zig. +// Paints a fill: its solid color, or its gradient times its alpha. A draw +// holds many fills, so each vertex says which (paint.vert). Mirrors +// vector/Paint.zig: `param` gives the gradient parameter, `stop_color` the +// color at it. The Paint struct is generated from vector/layouts.zig. +layout(location = 0) flat in vec4 fill_color; +layout(location = 1) flat in int fill_gradient; layout(location = 0) out vec4 out_color; #include "Paint.glsl" +layout(set = 2, binding = 0, std430) readonly buffer Paints { Paint paints[]; }; +#define paint paints[fill_gradient] float offset_at(int i) { return paint.offsets[i / 4][i % 4]; @@ -60,6 +65,5 @@ vec4 stop_color(float t) { } void main() { - vec4 c = paint.row0.w < 0.5 ? paint.color : stop_color(param(gl_FragCoord.xy)); - out_color = c * paint.extra.y; + out_color = fill_gradient < 0 ? fill_color : stop_color(param(gl_FragCoord.xy)) * fill_color; } diff --git a/src/vector/shaders/paint.vert b/src/vector/shaders/paint.vert new file mode 100644 index 0000000..89c2c82 --- /dev/null +++ b/src/vector/shaders/paint.vert @@ -0,0 +1,15 @@ +#version 450 +#extension GL_GOOGLE_include_directive : require +// Painted triangles: device pixels (y down) to normalized device +// coordinates (y up), as in path.vert, with the fill's paint passed on. +#include "Painted.glsl" +#include "Viewport.glsl" + +layout(location = 0) flat out vec4 fill_color; +layout(location = 1) flat out int fill_gradient; + +void main() { + gl_Position = vec4(position.x / viewport.size.x * 2.0 - 1.0, 1.0 - position.y / viewport.size.y * 2.0, 0.0, 1.0); + fill_color = color; + fill_gradient = int(gradient); +} diff --git a/src/vector/svg.zig b/src/vector/svg.zig index 9c0ec53..31d9b15 100644 --- a/src/vector/svg.zig +++ b/src/vector/svg.zig @@ -10,7 +10,7 @@ //! patterns, markers, images, CSS stylesheets. Group opacity is approximated //! by multiplying it into each shape. const std = @import("std"); -const geom = @import("geom.zig"); +const geom = @import("math"); const Drawing = @import("Drawing.zig"); const Vec = geom.Vec; const Affine = geom.Affine; |
