//! 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("math"); const Drawing = @import("Drawing.zig"); const Polygons = @import("Polygons.zig"); const Paint = @import("Paint.zig"); const layouts = @import("vector_layouts"); const shaders = @import("vector_shaders"); 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{ // Stencil fans, nonzero winding. abi.gpu.pipeline(layouts.Vertex, .{ .vertex = vertex, .fragment = stencil_only, .blend = .none, .write_color = false, .stencil = .{ .front = .{ .pass = .increment_and_wrap }, .back = .{ .pass = .decrement_and_wrap } }, }), // Stencil fans, even-odd. abi.gpu.pipeline(layouts.Vertex, .{ .vertex = vertex, .fragment = stencil_only, .blend = .none, .write_color = false, .stencil = .{ .front = .{ .pass = .invert }, .back = .{ .pass = .invert } }, }), // 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, 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) } }); } pub fn fill(g: *Gpu, polys: *const Polygons, rule: Drawing.FillRule, paint: *const Paint, alpha: f32) void { if (polys.empty() or alpha <= 0) return; g.record(polys, rule, paint, alpha) catch {}; } 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 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..3].* = .{ .{ .position = pts[0] }, .{ .position = pts[k] }, .{ .position = pts[k + 1] } }; i += 3; }; 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] }), }); } /// 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 = .{ .color = paint.color, .row0 = .{ m.a, m.c, m.e, @floatFromInt(@backingInt(paint.kind)) }, .row1 = .{ m.b, m.d, m.f, @floatFromInt(@backingInt(paint.spread)) }, .points = .{ paint.p0[0], paint.p0[1], paint.p1[0], paint.p1[1] }, .extra = .{ paint.radius, alpha, 0, 0 }, .offsets = @splat(@splat(0)), .colors = @splat(@splat(0)), }; const stops = paint.stops; const n = @min(stops.len, layouts.max_stops); for (0..n) |i| { const t = if (stops.len <= layouts.max_stops) stops[i].offset else @as(f32, @floatFromInt(i)) / @as(f32, @floatFromInt(n - 1)); const color = if (stops.len <= layouts.max_stops) stops[i].color else unpremultiply(paint.stopColor(t)); out.offsets[i / 4][i % 4] = t; out.colors[i] = color; } out.extra[2] = @floatFromInt(n); return out; } fn unpremultiply(c: @Vector(4, f32)) [4]f32 { if (c[3] <= 0) return .{ 0, 0, 0, 0 }; 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: *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, .height = g.height, .samples = samples, .stencil = true, .clear = g.clear_color, .pipelines = &pipelines, .draws = g.draws.items, }; } 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); }