From 9c33714591a2147f7e5879e77212ca9886d0c967 Mon Sep 17 00:00:00 2001 From: Gabriel Schneider Date: Fri, 25 Sep 2026 21:47:58 -0300 Subject: Put the game first: lib/sketchbook, sketches/vecanim The root is the game. The platform library moves to lib/sketchbook (with serve_web.py, which serves any sketch's web build, as a tool of it), and vecanim to sketches/vecanim, still its own package on the same library. --- src/vector/Cpu.zig | 185 ++++++++++ src/vector/Drawing.zig | 195 ++++++++++ src/vector/Gpu.zig | 174 +++++++++ src/vector/Paint.zig | 110 ++++++ src/vector/Polygons.zig | 395 +++++++++++++++++++++ src/vector/geom.zig | 239 +++++++++++++ src/vector/layouts.zig | 40 +++ src/vector/morph.zig | 178 ++++++++++ src/vector/root.zig | 144 ++++++++ src/vector/shaders/cover.frag | 65 ++++ src/vector/shaders/path.vert | 9 + src/vector/shaders/stencil.frag | 7 + src/vector/svg.zig | 768 ++++++++++++++++++++++++++++++++++++++++ 13 files changed, 2509 insertions(+) create mode 100644 src/vector/Cpu.zig create mode 100644 src/vector/Drawing.zig create mode 100644 src/vector/Gpu.zig create mode 100644 src/vector/Paint.zig create mode 100644 src/vector/Polygons.zig create mode 100644 src/vector/geom.zig create mode 100644 src/vector/layouts.zig create mode 100644 src/vector/morph.zig create mode 100644 src/vector/root.zig create mode 100644 src/vector/shaders/cover.frag create mode 100644 src/vector/shaders/path.vert create mode 100644 src/vector/shaders/stencil.frag create mode 100644 src/vector/svg.zig (limited to 'src/vector') diff --git a/src/vector/Cpu.zig b/src/vector/Cpu.zig new file mode 100644 index 0000000..c17366f --- /dev/null +++ b/src/vector/Cpu.zig @@ -0,0 +1,185 @@ +//! The CPU backend: polygons into premultiplied RGBA8, with exact coverage. +//! +//! Each edge adds its signed area to a grid of cells (the font-rs method); a +//! running sum along a row is then the winding coverage of every pixel, so +//! the cost is proportional to the fill's bounding box. It runs anywhere, +//! 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 Drawing = @import("Drawing.zig"); +const Polygons = @import("Polygons.zig"); +const Paint = @import("Paint.zig"); +const Vec = geom.Vec; + +gpa: std.mem.Allocator, +width: u32, +height: u32, +/// Premultiplied RGBA, `width * 4` bytes per row. +pixels: []u8, +/// Signed-area cells, `width + 2` per row; zero between fills. +cells: []f32, + +pub fn init(gpa: std.mem.Allocator, width: u32, height: u32) !Cpu { + const pixels = try gpa.alloc(u8, @as(usize, width) * height * 4); + errdefer gpa.free(pixels); + const cells = try gpa.alloc(f32, (@as(usize, width) + 2) * (height + 1)); + @memset(cells, 0); + @memset(pixels, 0); + return .{ .gpa = gpa, .width = width, .height = height, .pixels = pixels, .cells = cells }; +} + +pub fn deinit(c: *Cpu) void { + c.gpa.free(c.pixels); + c.gpa.free(c.cells); +} + +pub fn clear(c: *Cpu, color: Drawing.Color) void { + const px = Paint.premultiply(color); + const word: [4]u8 = .{ toByte(px[0]), toByte(px[1]), toByte(px[2]), toByte(px[3]) }; + @memset(std.mem.bytesAsSlice([4]u8, c.pixels), word); +} + +pub fn fill(c: *Cpu, polys: *const Polygons, rule: Drawing.FillRule, paint: *const Paint, alpha: f32) void { + if (polys.empty() or alpha <= 0) return; + var extent: geom.Bounds = .{}; + var it = polys.iterator(); + while (it.next()) |pts| { + var prev = pts[pts.len - 1]; + for (pts) |p| { + c.edge(prev, p, &extent); + prev = p; + } + } + c.composite(extent, rule, paint, alpha); +} + +/// Adds one edge, in device pixels. +fn edge(c: *Cpu, p0: Vec, p1: Vec, extent: *geom.Bounds) void { + if (p0[1] == p1[1] or !std.math.isFinite(p0[0] + p0[1] + p1[0] + p1[1])) return; + const w: f32 = @floatFromInt(c.width); + const h: f32 = @floatFromInt(c.height); + const dir: f32 = if (p0[1] < p1[1]) 1 else -1; + const a = if (dir > 0) p0 else p1; + const b = if (dir > 0) p1 else p0; + if (b[1] <= 0 or a[1] >= h) return; + const dxdy = (b[0] - a[0]) / (b[1] - a[1]); + var x = a[0]; + var y0 = a[1]; + if (y0 < 0) { + x -= y0 * dxdy; + y0 = 0; + } + const y1 = @min(b[1], h); + extent.add(.{ @min(a[0], b[0]), y0 }); + extent.add(.{ @max(a[0], b[0]), y1 }); + const stride = c.width + 2; + var y: u32 = @intFromFloat(y0); + const y_end: u32 = @intFromFloat(@ceil(y1)); + while (y < y_end) : (y += 1) { + const fy: f32 = @floatFromInt(y); + const dy = @min(fy + 1, y1) - @max(fy, y0); + const xnext = x + dxdy * dy; + const d = dy * dir; + // Left of the canvas counts at its left edge and right of it is + // never drawn: clamping keeps every winding number exact. + const x0 = std.math.clamp(@min(x, xnext), 0, w); + const x1 = std.math.clamp(@max(x, xnext), 0, w); + const row = c.cells[@as(usize, y) * stride ..][0..stride]; + const x0f = @floor(x0); + const x0i: usize = @intFromFloat(x0f); + const x1c = @ceil(x1); + const x1i: usize = @intFromFloat(x1c); + if (x1i <= x0i + 1) { + const xm = 0.5 * (x0 + x1) - x0f; + row[x0i] += d - d * xm; + row[x0i + 1] += d * xm; + } else { + const s = 1 / (x1 - x0); + const fx0 = x0 - x0f; + const a0 = 0.5 * s * (1 - fx0) * (1 - fx0); + const fx1 = x1 - x1c + 1; + const am = 0.5 * s * fx1 * fx1; + row[x0i] += d * a0; + if (x1i == x0i + 2) { + row[x0i + 1] += d * (1 - a0 - am); + } else { + const a1 = s * (1.5 - fx0); + row[x0i + 1] += d * (a1 - a0); + for (x0i + 2..x1i - 1) |xi| row[xi] += d * s; + const a2 = a1 + @as(f32, @floatFromInt(x1i - x0i - 3)) * s; + row[x1i - 1] += d * (1 - a2 - am); + } + row[x1i] += d * am; + } + x = xnext; + } +} + +/// Pixels from the cells in `extent`, zeroing the cells again. +fn composite(c: *Cpu, extent: geom.Bounds, rule: Drawing.FillRule, paint: *const Paint, alpha: f32) void { + if (extent.empty()) return; + const w = c.width; + const fw: f32 = @floatFromInt(w); + const stride = w + 2; + const x_start: usize = @intFromFloat(std.math.clamp(@floor(extent.min[0]), 0, fw)); + const x_end: usize = @min(@as(usize, @intFromFloat(std.math.clamp(@floor(extent.max[0]), 0, fw))) + 2, stride); + const y_start: usize = @intFromFloat(@max(0, @floor(extent.min[1]))); + const y_end: usize = @min(@as(usize, @intFromFloat(@ceil(extent.max[1]))), c.height); + // Gradients sample a table: 256 steps is below 8-bit output precision. + var lut: [256]@Vector(4, f32) = undefined; + if (paint.kind != .solid) for (&lut, 0..) |*e, i| { + e.* = paint.stopColor(@as(f32, @floatFromInt(i)) / 255); + }; + for (y_start..y_end) |y| { + const row = c.cells[y * stride ..][0..stride]; + const out = c.pixels[y * w * 4 ..][0 .. w * 4]; + var acc: f32 = 0; + for (x_start..x_end) |x| { + acc += row[x]; + row[x] = 0; + if (x >= w) continue; + const cover = switch (rule) { + .nonzero => @min(@abs(acc), 1), + .evenodd => blk: { + const t = @mod(@abs(acc), 2); + break :blk if (t > 1) 2 - t else t; + }, + }; + const a = cover * alpha; + if (a < 1.0 / 512.0) continue; + const color = if (paint.kind == .solid) + paint.color + else + lut[@intFromFloat(paint.param(.{ @as(f32, @floatFromInt(x)) + 0.5, @as(f32, @floatFromInt(y)) + 0.5 }) * 255 + 0.5)]; + blend(out[x * 4 ..][0..4], color * @as(@Vector(4, f32), @splat(a))); + } + } +} + +fn toByte(v: f32) u8 { + return @intFromFloat(std.math.clamp(v * 255 + 0.5, 0, 255)); +} + +/// Source-over, premultiplied. +inline fn blend(dst: *[4]u8, src: @Vector(4, f32)) void { + const d: @Vector(4, f32) = .{ @floatFromInt(dst[0]), @floatFromInt(dst[1]), @floatFromInt(dst[2]), @floatFromInt(dst[3]) }; + const out = src * @as(@Vector(4, f32), @splat(255)) + d * @as(@Vector(4, f32), @splat(1 - src[3])); + inline for (0..4) |i| dst[i] = @intFromFloat(@min(out[i] + 0.5, 255)); +} + +test "a half-covered pixel is half covered, under both rules" { + var c: Cpu = try .init(std.testing.allocator, 4, 4); + defer c.deinit(); + var p: Polygons = .init(std.testing.allocator); + defer p.deinit(); + try p.points.appendSlice(std.testing.allocator, &.{ .{ 1, 1 }, .{ 2.5, 1 }, .{ 2.5, 3 }, .{ 1, 3 } }); + try p.contours.append(std.testing.allocator, 4); + const white: Paint = .solid(.{ 1, 1, 1, 1 }); + c.fill(&p, .nonzero, &white, 1); + try std.testing.expectEqual(@as(u8, 255), c.pixels[(1 * 4 + 1) * 4 + 3]); + try std.testing.expectEqual(@as(u8, 128), c.pixels[(1 * 4 + 2) * 4 + 3]); + try std.testing.expectEqual(@as(u8, 0), c.pixels[(0 * 4 + 1) * 4 + 3]); + // Cells are clean for the next fill. + for (c.cells) |cell| try std.testing.expectEqual(@as(f32, 0), cell); +} diff --git a/src/vector/Drawing.zig b/src/vector/Drawing.zig new file mode 100644 index 0000000..0a3b77b --- /dev/null +++ b/src/vector/Drawing.zig @@ -0,0 +1,195 @@ +//! A vector drawing as plain data: shapes made of subpaths made of cubics. +//! Parsers and generators build these; the rasterizer and animations only +//! read and recombine them. +const Drawing = @This(); +const std = @import("std"); +const geom = @import("geom.zig"); +const Vec = geom.Vec; +const Cubic = geom.Cubic; + +cubics: []const Cubic = &.{}, +subpaths: []const Subpath = &.{}, +shapes: []const Shape = &.{}, +gradients: []const Gradient = &.{}, +/// The user-space rectangle the drawing occupies (SVG `viewBox`). +view: geom.Rect = .{}, +/// Intended size in pixels (SVG `width`/`height`). +width: f32 = 0, +height: f32 = 0, + +pub const Subpath = struct { + first: u32, + count: u32, + closed: bool, +}; + +/// Straight (not premultiplied) RGBA in 0..1. +pub const Color = @Vector(4, f32); + +pub const Paint = union(enum) { + none, + color: Color, + /// Index into `gradients`. + gradient: u32, +}; + +pub const Cap = enum { butt, round, square }; +pub const Join = enum { miter, round, bevel }; +pub const FillRule = enum { nonzero, evenodd }; + +pub const Style = struct { + fill: Paint = .{ .color = .{ 0, 0, 0, 1 } }, + fill_rule: FillRule = .nonzero, + fill_opacity: f32 = 1, + stroke: Paint = .none, + stroke_width: f32 = 1, + stroke_opacity: f32 = 1, + cap: Cap = .butt, + join: Join = .miter, + miter_limit: f32 = 4, + dashes: [8]f32 = @splat(0), + dash_count: u8 = 0, + dash_offset: f32 = 0, + /// Applied to fill and stroke alike. + opacity: f32 = 1, +}; + +pub const Shape = struct { + first: u32, + count: u32, + /// From the shape's own coordinates to the drawing's user space. + transform: geom.Affine = .identity, + style: Style = .{}, + /// A convex quad in the drawing's user space outside of which nothing + /// shows (a symbol's viewport). + clip: ?[4]Vec = null, +}; + +pub const Gradient = struct { + kind: enum { linear, radial } = .linear, + /// Linear: start and end. Radial: center and focus. + p0: Vec = .{ 0, 0 }, + p1: Vec = .{ 1, 0 }, + radius: f32 = 0.5, + /// Coordinates are fractions of the shape's bounds, not user space. + bounding_box: bool = true, + transform: geom.Affine = .identity, + spread: enum { pad, reflect, repeat } = .pad, + stops: []const Stop = &.{}, + + pub const Stop = struct { offset: f32, color: Color }; +}; + +pub fn subpathsOf(d: Drawing, shape: Shape) []const Subpath { + return d.subpaths[shape.first..][0..shape.count]; +} + +pub fn cubicsOf(d: Drawing, subpath: Subpath) []const Cubic { + return d.cubics[subpath.first..][0..subpath.count]; +} + +/// Bounds of `shape` in its own coordinates (control points: a little loose). +pub fn shapeBounds(d: Drawing, shape: Shape) geom.Bounds { + var b: geom.Bounds = .{}; + for (d.subpathsOf(shape)) |sp| for (d.cubicsOf(sp)) |c| for (c) |p| b.add(p); + return b; +} + +/// Bounds of the whole drawing in user space. +pub fn bounds(d: Drawing) geom.Bounds { + var b: geom.Bounds = .{}; + for (d.shapes) |shape| for (d.subpathsOf(shape)) |sp| for (d.cubicsOf(sp)) |c| for (c) |p| b.add(shape.transform.apply(p)); + return b; +} + +/// Accumulates a drawing. Everything lands in one allocator (an arena, in +/// practice), so a drawing is freed all at once. +pub const Builder = struct { + gpa: std.mem.Allocator, + cubics: std.ArrayList(Cubic) = .empty, + subpaths: std.ArrayList(Subpath) = .empty, + shapes: std.ArrayList(Shape) = .empty, + gradients: std.ArrayList(Gradient) = .empty, + shape_start: u32 = 0, + subpath_start: u32 = 0, + + pub fn init(gpa: std.mem.Allocator) Builder { + return .{ .gpa = gpa }; + } + + pub fn cubic(b: *Builder, c: Cubic) !void { + try b.cubics.append(b.gpa, c); + } + pub fn lineTo(b: *Builder, from: Vec, to: Vec) !void { + try b.cubic(geom.line(from, to)); + } + /// Ends the current subpath, if it has any segments. + pub fn closeSubpath(b: *Builder, closed: bool) !void { + const count: u32 = @intCast(b.cubics.items.len - b.subpath_start); + if (count > 0) try b.subpaths.append(b.gpa, .{ .first = b.subpath_start, .count = count, .closed = closed }); + b.subpath_start = @intCast(b.cubics.items.len); + } + /// Ends the current shape, if it has any subpaths. + pub fn endShape(b: *Builder, transform: geom.Affine, style: Style) !void { + try b.closeSubpath(false); + const count: u32 = @intCast(b.subpaths.items.len - b.shape_start); + if (count > 0) try b.shapes.append(b.gpa, .{ .first = b.shape_start, .count = count, .transform = transform, .style = style }); + b.shape_start = @intCast(b.subpaths.items.len); + } + pub fn finish(b: *Builder, view: geom.Rect, width: f32, height: f32) !Drawing { + return .{ + .cubics = try b.cubics.toOwnedSlice(b.gpa), + .subpaths = try b.subpaths.toOwnedSlice(b.gpa), + .shapes = try b.shapes.toOwnedSlice(b.gpa), + .gradients = try b.gradients.toOwnedSlice(b.gpa), + .view = view, + .width = width, + .height = height, + }; + } + + // Primitive shapes, each a closed subpath of cubics. + + pub fn rect(b: *Builder, r: geom.Rect, radius: f32) !void { + const rr = @min(radius, @min(r.w, r.h) / 2); + if (rr <= 0) { + const p = [4]Vec{ .{ r.x, r.y }, .{ r.x + r.w, r.y }, .{ r.x + r.w, r.y + r.h }, .{ r.x, r.y + r.h } }; + for (0..4) |i| try b.lineTo(p[i], p[(i + 1) % 4]); + } else { + try b.roundedRect(r, rr, rr); + } + try b.closeSubpath(true); + } + pub fn roundedRect(b: *Builder, r: geom.Rect, rx: f32, ry: f32) !void { + const k = 0.5522847498; + const x0 = r.x; + const y0 = r.y; + const x1 = r.x + r.w; + const y1 = r.y + r.h; + try b.lineTo(.{ x0 + rx, y0 }, .{ x1 - rx, y0 }); + try b.cubic(.{ .{ x1 - rx, y0 }, .{ x1 - rx + rx * k, y0 }, .{ x1, y0 + ry - ry * k }, .{ x1, y0 + ry } }); + try b.lineTo(.{ x1, y0 + ry }, .{ x1, y1 - ry }); + try b.cubic(.{ .{ x1, y1 - ry }, .{ x1, y1 - ry + ry * k }, .{ x1 - rx + rx * k, y1 }, .{ x1 - rx, y1 } }); + try b.lineTo(.{ x1 - rx, y1 }, .{ x0 + rx, y1 }); + try b.cubic(.{ .{ x0 + rx, y1 }, .{ x0 + rx - rx * k, y1 }, .{ x0, y1 - ry + ry * k }, .{ x0, y1 - ry } }); + try b.lineTo(.{ x0, y1 - ry }, .{ x0, y0 + ry }); + try b.cubic(.{ .{ x0, y0 + ry }, .{ x0, y0 + ry - ry * k }, .{ x0 + rx - rx * k, y0 }, .{ x0 + rx, y0 } }); + } + pub fn ellipse(b: *Builder, center: Vec, rx: f32, ry: f32) !void { + const k = 0.5522847498; + const cx = center[0]; + const cy = center[1]; + // Clockwise from the right, like SVG's circle. + try b.cubic(.{ .{ cx + rx, cy }, .{ cx + rx, cy + ry * k }, .{ cx + rx * k, cy + ry }, .{ cx, cy + ry } }); + try b.cubic(.{ .{ cx, cy + ry }, .{ cx - rx * k, cy + ry }, .{ cx - rx, cy + ry * k }, .{ cx - rx, cy } }); + try b.cubic(.{ .{ cx - rx, cy }, .{ cx - rx, cy - ry * k }, .{ cx - rx * k, cy - ry }, .{ cx, cy - ry } }); + try b.cubic(.{ .{ cx, cy - ry }, .{ cx + rx * k, cy - ry }, .{ cx + rx, cy - ry * k }, .{ cx + rx, cy } }); + try b.closeSubpath(true); + } + pub fn polyline(b: *Builder, points: []const Vec, closed: bool) !void { + if (points.len < 2) return; + for (points[0 .. points.len - 1], points[1..]) |p, q| try b.lineTo(p, q); + if (closed and !@reduce(.And, points[0] == points[points.len - 1])) try b.lineTo(points[points.len - 1], points[0]); + try b.closeSubpath(closed); + } +}; diff --git a/src/vector/Gpu.zig b/src/vector/Gpu.zig new file mode 100644 index 0000000..a557537 --- /dev/null +++ b/src/vector/Gpu.zig @@ -0,0 +1,174 @@ +//! 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`. +const Gpu = @This(); +const std = @import("std"); +const abi = @import("abi"); +const geom = @import("geom.zig"); +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 = .{ .spirv = shaders.path_vert, .uniform_buffers = 1 }; +const stencil_only: abi.gpu.Shader = .{ .spirv = shaders.stencil_frag }; + +const pipelines = [_]abi.gpu.Pipeline{ + // 0: 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 } }, + }), + // 1: even-odd. + abi.gpu.pipeline(layouts.Vertex, .{ + .vertex = vertex, + .fragment = stencil_only, + .blend = .none, + .write_color = false, + .stencil = .{ .front = .{ .pass = .invert }, .back = .{ .pass = .invert } }, + }), + // 2: cover. + abi.gpu.pipeline(layouts.Vertex, .{ + .vertex = vertex, + .fragment = .{ .spirv = shaders.cover_frag, .uniform_buffers = 1 }, + .stencil = .{ + .front = .{ .compare = .not_equal, .pass = .zero }, + .back = .{ .compare = .not_equal, .pass = .zero }, + }, + }), +}; + +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 = &.{}, + +pub fn begin(g: *Gpu, arena: std.mem.Allocator, clear: Drawing.Color) void { + g.arena = arena; + g.draws = .empty; + 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 { + // 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); + 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] }; + 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)), + }); +} + +/// `Paint` as the shader's uniform 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(@intFromEnum(paint.kind)) }, + .row1 = .{ m.b, m.d, m.f, @floatFromInt(@intFromEnum(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] }; +} + +/// The pass that draws everything recorded since `begin`. +pub fn pass(g: *const Gpu) abi.gpu.Pass { + return .{ + .image = g.image, + .width = g.width, + .height = g.height, + .samples = samples, + .stencil = true, + .clear = g.clear_color, + .pipelines = &pipelines, + .draws = g.draws.items, + }; +} + +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 = @enumFromInt(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]); +} diff --git a/src/vector/Paint.zig b/src/vector/Paint.zig new file mode 100644 index 0000000..fb838d0 --- /dev/null +++ b/src/vector/Paint.zig @@ -0,0 +1,110 @@ +//! A paint resolved for one fill: a premultiplied color, or a gradient with +//! the map from device pixels into its own space. The CPU backend samples it +//! here; the GPU backend uploads the same numbers to its fragment shader, +//! which mirrors `param` and `stopColor`. +const Paint = @This(); +const std = @import("std"); +const geom = @import("geom.zig"); +const Drawing = @import("Drawing.zig"); +const Vec = geom.Vec; + +pub const Kind = enum(u32) { solid, linear, radial }; +pub const Spread = enum(u32) { pad, reflect, repeat }; + +kind: Kind = .solid, +/// Premultiplied, for solid paints. +color: @Vector(4, f32) = .{ 0, 0, 0, 0 }, +/// Linear: start and end. Radial: center and focus. +p0: Vec = .{ 0, 0 }, +p1: Vec = .{ 0, 0 }, +radius: f32 = 0, +spread: Spread = .pad, +/// Device pixels to gradient space. +to_gradient: geom.Affine = .identity, +stops: []const Drawing.Gradient.Stop = &.{}, + +pub fn solid(color: Drawing.Color) Paint { + return .{ .color = premultiply(color) }; +} + +/// `paint` of `shape`, drawn with `m` from shape to device space. +pub fn of(d: Drawing, shape: Drawing.Shape, paint: Drawing.Paint, m: geom.Affine) Paint { + return switch (paint) { + .none => .{}, + .color => |c| solid(c), + .gradient => |index| blk: { + const g = d.gradients[index]; + var space = m; + if (g.bounding_box) { + const b = d.shapeBounds(shape).rect(); + space = space.mul(.translate(b.x, b.y)).mul(.scale(@max(b.w, 1e-6), @max(b.h, 1e-6))); + } + break :blk .{ + .kind = if (g.kind == .linear) .linear else .radial, + .p0 = g.p0, + .p1 = g.p1, + .radius = g.radius, + .spread = switch (g.spread) { + .pad => .pad, + .reflect => .reflect, + .repeat => .repeat, + }, + .to_gradient = space.mul(g.transform).invert(), + .stops = g.stops, + }; + }, + }; +} + +/// The gradient parameter at device point `q`, spread applied: 0..1. +pub fn param(p: *const Paint, q: Vec) f32 { + const g = p.to_gradient.apply(q); + var t: f32 = switch (p.kind) { + .solid => 0, + .linear => blk: { + const dir = p.p1 - p.p0; + const len2 = geom.dot(dir, dir); + break :blk if (len2 > 0) geom.dot(g - p.p0, dir) / len2 else 0; + }, + .radial => blk: { + // Where the ray from the focus through g meets the circle. + const dq = g - p.p1; + const cf = p.p1 - p.p0; + const a = geom.dot(dq, dq); + if (a <= 0) break :blk 0; + const b = geom.dot(dq, cf); + const c = geom.dot(cf, cf) - p.radius * p.radius; + const s = (-b + @sqrt(@max(b * b - a * c, 0))) / a; + break :blk if (s > 0) 1 / s else 1; + }, + }; + t = switch (p.spread) { + .pad => std.math.clamp(t, 0, 1), + .repeat => t - @floor(t), + .reflect => blk: { + const r = @mod(t, 2); + break :blk if (r > 1) 2 - r else r; + }, + }; + return t; +} + +/// The premultiplied color at gradient parameter `t`. +pub fn stopColor(p: *const Paint, t: f32) @Vector(4, f32) { + const stops = p.stops; + if (stops.len == 0) return .{ 0, 0, 0, 0 }; + if (t <= stops[0].offset) return premultiply(stops[0].color); + for (stops[0 .. stops.len - 1], stops[1..]) |a, b| { + if (t <= b.offset) { + const span = b.offset - a.offset; + const u = if (span > 0) (t - a.offset) / span else 1; + // Interpolate straight colors, as SVG does, then premultiply. + return premultiply(a.color + (b.color - a.color) * @as(Drawing.Color, @splat(u))); + } + } + return premultiply(stops[stops.len - 1].color); +} + +pub fn premultiply(c: Drawing.Color) @Vector(4, f32) { + return .{ c[0] * c[3], c[1] * c[3], c[2] * c[3], c[3] }; +} diff --git a/src/vector/Polygons.zig b/src/vector/Polygons.zig new file mode 100644 index 0000000..c0ed335 --- /dev/null +++ b/src/vector/Polygons.zig @@ -0,0 +1,395 @@ +//! Closed polygons in device pixels: what a fill or a stroke becomes before +//! any backend sees it. Fills keep their contours as the path had them; +//! strokes become many small pieces (segment quads, joins, caps), all wound +//! the same way, so the nonzero rule unions them. +const Polygons = @This(); +const std = @import("std"); +const geom = @import("geom.zig"); +const Drawing = @import("Drawing.zig"); +const Vec = geom.Vec; +const Affine = geom.Affine; + +/// Device-space flattening tolerance, in pixels. +pub const tolerance = 0.2; + +gpa: std.mem.Allocator, +points: std.ArrayList(Vec) = .empty, +/// Point count of each contour, in order. +contours: std.ArrayList(u32) = .empty, +/// Scratch polylines. +line: std.ArrayList(Vec) = .empty, +dashed: std.ArrayList(Vec) = .empty, +clipped: std.ArrayList(Vec) = .empty, +clip_scratch: std.ArrayList(Vec) = .empty, +clip_counts: std.ArrayList(u32) = .empty, + +pub fn init(gpa: std.mem.Allocator) Polygons { + return .{ .gpa = gpa }; +} + +pub fn deinit(p: *Polygons) void { + p.points.deinit(p.gpa); + p.contours.deinit(p.gpa); + p.line.deinit(p.gpa); + p.dashed.deinit(p.gpa); + p.clipped.deinit(p.gpa); + p.clip_scratch.deinit(p.gpa); + p.clip_counts.deinit(p.gpa); +} + +/// Keeps only what lies inside the convex `quad` (device space), contour by +/// contour (Sutherland–Hodgman). Winding numbers inside the quad are +/// unchanged, so both fill rules still hold. +pub fn clipConvex(p: *Polygons, quad: [4]Vec) !void { + var area: f32 = 0; + for (quad, 0..) |q, i| area += geom.cross(q, quad[(i + 1) % 4]); + const sign: f32 = if (area >= 0) 1 else -1; + p.clipped.clearRetainingCapacity(); + p.clip_counts.clearRetainingCapacity(); + var it = p.iterator(); + while (it.next()) |pts| { + p.clip_scratch.clearRetainingCapacity(); + try p.clip_scratch.appendSlice(p.gpa, pts); + for (quad, 0..) |a, i| { + const b = quad[(i + 1) % 4]; + const edge = b - a; + const input = try p.gpa.dupe(Vec, p.clip_scratch.items); + defer p.gpa.free(input); + p.clip_scratch.clearRetainingCapacity(); + if (input.len == 0) break; + var prev = input[input.len - 1]; + var prev_in = sign * geom.cross(edge, prev - a) >= 0; + for (input) |cur| { + const cur_in = sign * geom.cross(edge, cur - a) >= 0; + if (cur_in != prev_in) { + const d0 = geom.cross(edge, prev - a); + const d1 = geom.cross(edge, cur - a); + try p.clip_scratch.append(p.gpa, geom.mix(prev, cur, d0 / (d0 - d1))); + } + if (cur_in) try p.clip_scratch.append(p.gpa, cur); + prev = cur; + prev_in = cur_in; + } + } + if (p.clip_scratch.items.len >= 3) { + try p.clipped.appendSlice(p.gpa, p.clip_scratch.items); + try p.clip_counts.append(p.gpa, @intCast(p.clip_scratch.items.len)); + } + } + p.points.clearRetainingCapacity(); + p.contours.clearRetainingCapacity(); + try p.points.appendSlice(p.gpa, p.clipped.items); + try p.contours.appendSlice(p.gpa, p.clip_counts.items); +} + +pub fn clear(p: *Polygons) void { + p.points.clearRetainingCapacity(); + p.contours.clearRetainingCapacity(); +} + +pub fn empty(p: *const Polygons) bool { + return p.contours.items.len == 0; +} + +pub fn bounds(p: *const Polygons) geom.Bounds { + var b: geom.Bounds = .{}; + for (p.points.items) |q| b.add(q); + return b; +} + +/// Iterates contours as point slices. +pub fn iterator(p: *const Polygons) Iterator { + return .{ .p = p }; +} + +pub const Iterator = struct { + p: *const Polygons, + contour: usize = 0, + start: usize = 0, + + pub fn next(it: *Iterator) ?[]const Vec { + if (it.contour == it.p.contours.items.len) return null; + const len = it.p.contours.items[it.contour]; + defer { + it.start += len; + it.contour += 1; + } + return it.p.points.items[it.start..][0..len]; + } +}; + +fn contour(p: *Polygons, pts: []const Vec) !void { + if (pts.len < 3) return; + try p.points.appendSlice(p.gpa, pts); + try p.contours.append(p.gpa, @intCast(pts.len)); +} + +/// A closed polygon wound positively (in device space) whatever its order, +/// so overlapping stroke pieces add up instead of cancelling. +fn piece(p: *Polygons, m: Affine, pts: []const Vec) !void { + var area: f32 = 0; + for (pts, 0..) |q, i| area += geom.cross(q, pts[(i + 1) % pts.len]); + if (m.determinant() < 0) area = -area; + const start = p.points.items.len; + for (0..pts.len) |k| try p.points.append(p.gpa, m.apply(if (area >= 0) pts[k] else pts[(pts.len - k) % pts.len])); + try p.contours.append(p.gpa, @intCast(p.points.items.len - start)); +} + +// --------------------------------------------------------------------------- +// Fills + +/// The subpaths of `shape` as contours, with `m` from shape to device space. +pub fn fill(p: *Polygons, d: Drawing, shape: Drawing.Shape, m: Affine) !void { + for (d.subpathsOf(shape)) |sp| { + p.line.clearRetainingCapacity(); + try flatten(p.gpa, &p.line, d.cubicsOf(sp), m, tolerance); + try p.contour(p.line.items); + } +} + +// --------------------------------------------------------------------------- +// Strokes + +pub const Stroke = struct { + width: f32, + cap: Drawing.Cap = .butt, + join: Drawing.Join = .miter, + miter_limit: f32 = 4, + dashes: []const f32 = &.{}, + dash_offset: f32 = 0, + /// The drawn fraction of the path, along its length (0..1). + trim: f32 = 1, + /// From the space the stroke is laid out in to pixels: the shape's own + /// space (width and dashes then follow its transform), or identity for a + /// fixed pixel width. + space: Affine, + + pub fn of(style: Drawing.Style, space: Affine) Stroke { + return .{ + .width = style.stroke_width, + .cap = style.cap, + .join = style.join, + .miter_limit = style.miter_limit, + .dash_offset = style.dash_offset, + .space = space, + }; + } +}; + +/// The stroke of `shape` as positively wound pieces; `m` takes the shape to +/// device space. +pub fn stroke(p: *Polygons, d: Drawing, shape: Drawing.Shape, m: Affine, st: Stroke) !void { + if (st.width <= 0) return; + const to_layout = st.space.invert().mul(m); + const layout_tolerance = tolerance / @max(st.space.scaleFactor(), 1e-6); + var budget = std.math.inf(f32); + if (st.trim < 1) { + var total: f32 = 0; + for (d.subpathsOf(shape)) |sp| { + p.line.clearRetainingCapacity(); + try flatten(p.gpa, &p.line, d.cubicsOf(sp), to_layout, layout_tolerance); + total += length(p.line.items); + } + budget = @max(st.trim, 0) * total; + if (budget <= 0) return; + } + for (d.subpathsOf(shape)) |sp| { + if (budget <= 0) break; + p.line.clearRetainingCapacity(); + try flatten(p.gpa, &p.line, d.cubicsOf(sp), to_layout, layout_tolerance); + var pts: []const Vec = p.line.items; + var closed = sp.closed; + const len = length(pts); + if (len > budget) { + pts = truncate(&p.line, budget); + closed = false; + } + budget -= len; + if (st.dashes.len > 0) try p.dash(pts, closed, st) else try p.polyline(pts, closed, st); + } +} + +fn dash(p: *Polygons, pts: []const Vec, closed: bool, st: Stroke) !void { + var period: f32 = 0; + for (st.dashes) |v| period += v; + if (period <= 0 or pts.len < 2) return p.polyline(pts, closed, st); + var index: usize = 0; + var left = @mod(st.dash_offset, period); + while (left >= st.dashes[index]) { + left -= st.dashes[index]; + index = (index + 1) % st.dashes.len; + } + var remaining = st.dashes[index] - left; + var on = index % 2 == 0; + p.dashed.clearRetainingCapacity(); + if (on) try p.dashed.append(p.gpa, pts[0]); + const segments = pts.len - 1 + @intFromBool(closed); + for (0..segments) |i| { + var a = pts[i]; + const b = pts[(i + 1) % pts.len]; + var seg = geom.length(b - a); + while (seg > remaining) { + const q = geom.mix(a, b, remaining / seg); + try p.dashed.append(p.gpa, q); + if (on) try p.polyline(p.dashed.items, false, st); + p.dashed.clearRetainingCapacity(); + if (!on) try p.dashed.append(p.gpa, q); + seg -= remaining; + a = q; + on = !on; + index = (index + 1) % st.dashes.len; + remaining = st.dashes[index]; + } + remaining -= seg; + if (on) try p.dashed.append(p.gpa, b); + } + if (on and p.dashed.items.len > 1) try p.polyline(p.dashed.items, false, st); +} + +fn polyline(p: *Polygons, pts: []const Vec, closed: bool, st: Stroke) !void { + const hw = st.width / 2; + if (pts.len == 0) return; + const m = st.space; + var moved = false; + for (pts[1..]) |q| if (geom.length(q - pts[0]) > 1e-6) { + moved = true; + break; + }; + // A lone point still shows with round or square caps. + if (!moved) return switch (st.cap) { + .round => p.circle(m, pts[0], hw), + .square => p.piece(m, &.{ pts[0] + Vec{ -hw, -hw }, pts[0] + Vec{ hw, -hw }, pts[0] + Vec{ hw, hw }, pts[0] + Vec{ -hw, hw } }), + .butt => {}, + }; + var first: ?struct { point: Vec, dir: Vec } = null; + var last_dir: Vec = undefined; + var last_point: Vec = undefined; + const count = pts.len - 1 + @intFromBool(closed); + for (0..count) |i| { + const a = pts[i]; + const b = pts[(i + 1) % pts.len]; + const delta = b - a; + if (geom.length(delta) < 1e-6) continue; + const dir = geom.normalize(delta); + const n = geom.perp(dir) * geom.splat(hw); + try p.piece(m, &.{ a + n, b + n, b - n, a - n }); + if (first == null) first = .{ .point = a, .dir = dir } else try p.join(m, a, last_dir, dir, hw, st); + last_dir = dir; + last_point = b; + } + const f = first orelse return; + if (closed) { + try p.join(m, f.point, last_dir, f.dir, hw, st); + } else { + try p.cap(m, f.point, -f.dir, hw, st.cap); + try p.cap(m, last_point, last_dir, hw, st.cap); + } +} + +fn join(p: *Polygons, m: Affine, v: Vec, d0: Vec, d1: Vec, hw: f32, st: Stroke) !void { + const turn = geom.cross(d0, d1); + if (@abs(turn) < 1e-6 and geom.dot(d0, d1) > 0) return; + if (st.join == .round) return p.circle(m, v, hw); + // Offsets on the outer side of the turn: `perp` is the left side, which + // is outside when the path turns right (positive cross in y-down space). + const side: f32 = if (turn > 0) 1 else -1; + const n0 = geom.perp(d0) * geom.splat(hw * side); + const n1 = geom.perp(d1) * geom.splat(hw * side); + if (st.join == .miter) { + // The tip lies along the bisector; SVG's limit bounds its length + // over the stroke width. + const bisector = geom.normalize(n0 + n1); + const cos_half = geom.dot(bisector, geom.normalize(n0)); + if (cos_half > 1e-6 and 1 / cos_half <= st.miter_limit) { + return p.piece(m, &.{ v, v + n0, v + bisector * geom.splat(hw / cos_half), v + n1 }); + } + } + try p.piece(m, &.{ v, v + n0, v + n1 }); +} + +fn cap(p: *Polygons, m: Affine, at: Vec, dir: Vec, hw: f32, kind: Drawing.Cap) !void { + switch (kind) { + .butt => {}, + .round => try p.circle(m, at, hw), + .square => { + const n = geom.perp(dir) * geom.splat(hw); + const out = dir * geom.splat(hw); + try p.piece(m, &.{ at + n, at + n + out, at - n + out, at - n }); + }, + } +} + +fn circle(p: *Polygons, m: Affine, center: Vec, r: f32) !void { + const device_r = @max(r * m.scaleFactor(), tolerance); + const steps: usize = @intFromFloat(std.math.clamp(@ceil(std.math.pi / std.math.acos(@max(1 - tolerance / device_r, -1))), 8, 128)); + var buf: [128]Vec = undefined; + for (0..steps) |i| { + const a = @as(f32, @floatFromInt(i)) / @as(f32, @floatFromInt(steps)) * std.math.tau; + buf[i] = center + Vec{ @cos(a), @sin(a) } * geom.splat(r); + } + try p.piece(m, buf[0..steps]); +} + +// --------------------------------------------------------------------------- +// Polylines + +/// Cubics to a polyline, each transformed by `m`, within `tol`. +pub fn flatten(gpa: std.mem.Allocator, out: *std.ArrayList(Vec), cubics: []const geom.Cubic, m: Affine, tol: f32) !void { + for (cubics, 0..) |raw, i| { + const c: geom.Cubic = .{ m.apply(raw[0]), m.apply(raw[1]), m.apply(raw[2]), m.apply(raw[3]) }; + if (i == 0) try out.append(gpa, c[0]); + const n = geom.flattenCount(c, tol); + const step = 1 / @as(f32, @floatFromInt(n)); + for (1..n) |k| try out.append(gpa, geom.eval(c, @as(f32, @floatFromInt(k)) * step)); + try out.append(gpa, c[3]); + } +} + +pub fn length(pts: []const Vec) f32 { + if (pts.len < 2) return 0; + var total: f32 = 0; + for (pts[0 .. pts.len - 1], pts[1..]) |a, b| total += geom.length(b - a); + return total; +} + +/// Shortens the polyline in `list` to `len` and returns it. +fn truncate(list: *std.ArrayList(Vec), len: f32) []const Vec { + const pts = list.items; + var left = len; + for (pts[0 .. pts.len - 1], pts[1..], 1..) |a, b, i| { + const seg = geom.length(b - a); + if (seg >= left) { + pts[i] = geom.mix(a, b, if (seg > 0) left / seg else 0); + list.shrinkRetainingCapacity(i + 1); + return list.items; + } + left -= seg; + } + return pts; +} + +test "a square stroke is four quads and four miters, all wound one way" { + var p: Polygons = .init(std.testing.allocator); + defer p.deinit(); + var b: Drawing.Builder = .init(std.testing.allocator); + defer { + b.cubics.deinit(b.gpa); + b.subpaths.deinit(b.gpa); + b.shapes.deinit(b.gpa); + b.gradients.deinit(b.gpa); + } + try b.rect(.{ .w = 10, .h = 10 }, 0); + try b.endShape(.identity, .{}); + const d: Drawing = .{ .cubics = b.cubics.items, .subpaths = b.subpaths.items, .shapes = b.shapes.items }; + try p.stroke(d, d.shapes[0], .identity, .{ .width = 2, .space = .identity }); + try std.testing.expectEqual(@as(usize, 8), p.contours.items.len); + var it = p.iterator(); + while (it.next()) |pts| { + var area: f32 = 0; + for (pts, 0..) |q, i| area += geom.cross(q, pts[(i + 1) % pts.len]); + try std.testing.expect(area > 0); + } + const bb = p.bounds().rect(); + try std.testing.expectEqual(@as(f32, -1), bb.x); + try std.testing.expectEqual(@as(f32, 12), bb.w); +} diff --git a/src/vector/geom.zig b/src/vector/geom.zig new file mode 100644 index 0000000..b80c55a --- /dev/null +++ b/src/vector/geom.zig @@ -0,0 +1,239 @@ +//! 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 new file mode 100644 index 0000000..097e682 --- /dev/null +++ b/src/vector/layouts.zig @@ -0,0 +1,40 @@ +//! What the vector GPU backend hands its shaders. These Zig structs are the +//! only definition: the shaders include GLSL generated from them (see +//! `glsl.zig`). No imports, so the shader build can compile this alone. + +pub const max_stops = 32; + +/// A path point in device pixels. +pub const Vertex = extern struct { + position: [2]f32, + + pub const glsl = .vertex; +}; + +pub const Viewport = extern struct { + size: [2]f32, + pad: [2]f32 = .{ 0, 0 }, + + pub const glsl = .{ .uniform = .{ .set = 1, .instance = "viewport" } }; +}; + +/// A resolved `Paint`, as `cover.frag` reads it. +pub const Paint = extern struct { + /// Premultiplied solid color. + color: [4]f32, + /// Device pixels to gradient space: a, c, e; then the kind (0 solid, + /// 1 linear, 2 radial). + row0: [4]f32, + /// b, d, f; then the spread (0 pad, 1 reflect, 2 repeat). + row1: [4]f32, + /// p0 then p1. + points: [4]f32, + /// Radius, alpha, 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" } }; +}; diff --git a/src/vector/morph.zig b/src/vector/morph.zig new file mode 100644 index 0000000..319eccf --- /dev/null +++ b/src/vector/morph.zig @@ -0,0 +1,178 @@ +//! Drawings in between two drawings, as manim transforms them: shapes pair up +//! in order; each pair's subpaths, then each subpath's cubics, are made equal +//! in number by splitting the longest curves; then every control point and +//! 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 Drawing = @import("Drawing.zig"); +const Vec = geom.Vec; +const Cubic = geom.Cubic; + +/// The drawing `t` of the way from `a` (placed by `ma`) to `b` (placed by +/// `mb`), in the space both transforms map to. Allocated in `arena`. +pub fn between(arena: std.mem.Allocator, a: Drawing, ma: geom.Affine, b: Drawing, mb: geom.Affine, t: f32) !Drawing { + var out: Drawing.Builder = .init(arena); + const ca = center(a, ma); + const cb = center(b, mb); + const n = @max(a.shapes.len, b.shapes.len); + for (0..n) |i| { + const sa: ?Drawing.Shape = if (i < a.shapes.len) a.shapes[i] else null; + const sb: ?Drawing.Shape = if (i < b.shapes.len) b.shapes[i] else null; + // The missing side is the other side, shrunk to a point. + const pa = try placed(arena, a, sa, ma, sb, b, mb, cb); + const pb = try placed(arena, b, sb, mb, sa, a, ma, ca); + const count = @max(pa.len, pb.len); + for (0..count) |k| { + const from = try pad(arena, pa, k, if (pa.len > 0) lastPoint(pa) else ca); + const to = try pad(arena, pb, k, if (pb.len > 0) lastPoint(pb) else cb); + const aligned = try align2(arena, from.cubics, to.cubics); + for (aligned[0], aligned[1]) |x, y| { + var c: Cubic = undefined; + for (&c, x, y) |*p, u, v| p.* = geom.mix(u, v, t); + try out.cubic(c); + } + try out.closeSubpath(from.closed or to.closed); + } + const style_a = if (sa) |s| s.style else fade(sb.?.style); + const style_b = if (sb) |s| s.style else fade(sa.?.style); + try out.endShape(.identity, mixStyle(a, style_a, b, style_b, t)); + } + return out.finish(a.view, a.width, a.height); +} + +const Path = struct { cubics: []const Cubic, closed: bool }; + +/// The subpaths of `shape` in the shared space; for a missing shape, its +/// partner's subpaths collapsed onto `point`. +fn placed(arena: std.mem.Allocator, d: Drawing, shape: ?Drawing.Shape, m: geom.Affine, partner: ?Drawing.Shape, pd: Drawing, pm: geom.Affine, point: Vec) ![]Path { + const s = shape orelse { + const p = partner.?; + const subpaths = pd.subpathsOf(p); + const out = try arena.alloc(Path, subpaths.len); + for (out, subpaths) |*o, sp| { + const cubics = try arena.alloc(Cubic, pd.cubicsOf(sp).len); + @memset(cubics, .{ point, point, point, point }); + o.* = .{ .cubics = cubics, .closed = sp.closed }; + } + _ = pm; + return out; + }; + const subpaths = d.subpathsOf(s); + const full = m.mul(s.transform); + const out = try arena.alloc(Path, subpaths.len); + for (out, subpaths) |*o, sp| { + const src = d.cubicsOf(sp); + const cubics = try arena.alloc(Cubic, src.len); + for (cubics, src) |*dst, c| dst.* = .{ full.apply(c[0]), full.apply(c[1]), full.apply(c[2]), full.apply(c[3]) }; + o.* = .{ .cubics = cubics, .closed = sp.closed }; + } + return out; +} + +/// Subpath `k`, or a point-sized one where the list is shorter. +fn pad(arena: std.mem.Allocator, paths: []const Path, k: usize, point: Vec) !Path { + if (k < paths.len) return paths[k]; + const one = try arena.alloc(Cubic, 1); + one[0] = .{ point, point, point, point }; + return .{ .cubics = one, .closed = false }; +} + +fn lastPoint(paths: []const Path) Vec { + const last = paths[paths.len - 1].cubics; + return last[last.len - 1][3]; +} + +/// Both lists with the same number of cubics: the shorter one's longest +/// curves are split in half until they match. +fn align2(arena: std.mem.Allocator, a: []const Cubic, b: []const Cubic) ![2][]const Cubic { + if (a.len == b.len) return .{ a, b }; + if (a.len < b.len) return .{ try refine(arena, a, b.len), b }; + return .{ a, try refine(arena, b, a.len) }; +} + +fn refine(arena: std.mem.Allocator, cubics: []const Cubic, n: usize) ![]const Cubic { + var list: std.ArrayList(Cubic) = try .initCapacity(arena, n); + list.appendSliceAssumeCapacity(cubics); + while (list.items.len < n) { + var longest: usize = 0; + var best: f32 = -1; + for (list.items, 0..) |c, i| { + const len = geom.roughLength(c); + if (len > best) { + best = len; + longest = i; + } + } + const halves = geom.split(list.items[longest], 0.5); + list.items[longest] = halves[0]; + list.insertAssumeCapacity(longest + 1, halves[1]); + } + return list.items; +} + +fn center(d: Drawing, m: geom.Affine) Vec { + const b = d.bounds(); + return m.apply(if (b.empty()) d.view.center() else b.rect().center()); +} + +/// A style that draws nothing, for shapes appearing from or vanishing into +/// a point. +fn fade(s: Drawing.Style) Drawing.Style { + var out = s; + out.opacity = 0; + return out; +} + +/// Styles in between: numbers blend; solid colors blend; anything else +/// switches halfway. +fn mixStyle(a: Drawing, sa: Drawing.Style, b: Drawing, sb: Drawing.Style, t: f32) Drawing.Style { + var s = if (t < 0.5) sa else sb; + s.fill = mixPaint(a, sa.fill, b, sb.fill, t); + s.stroke = mixPaint(a, sa.stroke, b, sb.stroke, t); + s.stroke_width = std.math.lerp(sa.stroke_width, sb.stroke_width, t); + s.opacity = std.math.lerp(sa.opacity, sb.opacity, t); + s.fill_opacity = std.math.lerp(sa.fill_opacity, sb.fill_opacity, t); + s.stroke_opacity = std.math.lerp(sa.stroke_opacity, sb.stroke_opacity, t); + return s; +} + +fn mixPaint(a: Drawing, pa: Drawing.Paint, b: Drawing, pb: Drawing.Paint, t: f32) Drawing.Paint { + _ = a; + _ = b; + const ca = switch (pa) { + .color => |c| c, + .none => if (pb == .color) pb.color * Drawing.Color{ 1, 1, 1, 0 } else return pb, + .gradient => return if (t < 0.5) pa else pb, + }; + const cb = switch (pb) { + .color => |c| c, + .none => ca * Drawing.Color{ 1, 1, 1, 0 }, + .gradient => return if (t < 0.5) pa else pb, + }; + return .{ .color = ca + (cb - ca) * @as(Drawing.Color, @splat(t)) }; +} + +test "a square becomes a circle through aligned cubics" { + var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); + defer arena.deinit(); + var ba: Drawing.Builder = .init(arena.allocator()); + try ba.rect(.{ .x = -10, .y = -10, .w = 20, .h = 20 }, 0); + try ba.endShape(.identity, .{ .fill = .{ .color = .{ 1, 0, 0, 1 } } }); + const square = try ba.finish(.{}, 0, 0); + var bb: Drawing.Builder = .init(arena.allocator()); + try bb.ellipse(.{ 0, 0 }, 10, 10); + try bb.ellipse(.{ 30, 0 }, 5, 5); + try bb.endShape(.identity, .{ .fill = .{ .color = .{ 0, 0, 1, 1 } } }); + const circles = try bb.finish(.{}, 0, 0); + + const start = try between(arena.allocator(), square, .identity, circles, .identity, 0); + const end = try between(arena.allocator(), square, .identity, circles, .identity, 1); + const mid = try between(arena.allocator(), square, .identity, circles, .identity, 0.5); + try std.testing.expectEqual(@as(usize, 2), mid.subpaths.len); + try std.testing.expectEqual(mid.subpaths[0].count, mid.subpaths[1].count); + // The ends are the originals. + try std.testing.expectEqual(square.cubics[0][0], start.cubics[0][0]); + try std.testing.expectEqual(geom.vec(10, 0), end.cubics[0][0]); + try std.testing.expectEqual(Drawing.Color{ 0.5, 0, 0.5, 1 }, mid.shapes[0].style.fill.color); +} diff --git a/src/vector/root.zig b/src/vector/root.zig new file mode 100644 index 0000000..7556948 --- /dev/null +++ b/src/vector/root.zig @@ -0,0 +1,144 @@ +//! 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 +//! 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 Drawing = @import("Drawing.zig"); +pub const svg = @import("svg.zig"); +pub const Polygons = @import("Polygons.zig"); +pub const Paint = @import("Paint.zig"); +pub const Cpu = @import("Cpu.zig"); +pub const Gpu = @import("Gpu.zig"); +pub const layouts = @import("vector_layouts"); +pub const morph = @import("morph.zig"); + +pub const Backend = enum { cpu, gpu }; + +pub const Options = struct { + /// Multiplies everything the shape draws. + alpha: f32 = 1, + fill: bool = true, + stroke: bool = true, + /// Also outline the shape in its fill color, `width` device pixels wide + /// (manim's Write draws glyph borders before filling them). + outline: ?struct { width: f32, alpha: f32 = 1 } = null, + /// The drawn fraction of strokes and outlines, along their length. + trim: f32 = 1, +}; + +/// Draws drawings into an image of `width` x `height` pixels. `host` is a +/// `sketch.Host`; `f` a `sketch.Frame`. Both are duck-typed, so the library +/// depends on nothing but the ABI. +pub fn Renderer(comptime backend: Backend) type { + return struct { + const Self = @This(); + pub const kind = backend; + + target: switch (backend) { + .cpu => Cpu, + .gpu => Gpu, + }, + polys: Polygons, + image: abi.Image, + + pub fn init(gpa: std.mem.Allocator, host: anytype, w: u32, h: u32) !Self { + const image = host.newImage(w, h); + return .{ + .target = switch (backend) { + .cpu => try .init(gpa, w, h), + .gpu => .{ .width = w, .height = h, .image = image }, + }, + .polys = .init(gpa), + .image = image, + }; + } + + pub fn deinit(r: *Self, host: anytype) void { + if (backend == .cpu) r.target.deinit(); + r.polys.deinit(); + host.freeImage(r.image); + } + + pub fn width(r: *const Self) u32 { + return r.target.width; + } + pub fn height(r: *const Self) u32 { + return r.target.height; + } + + /// Starts a picture. `f.arena` holds what the GPU pass needs until + /// the frame is consumed. + pub fn begin(r: *Self, f: anytype, clear: Drawing.Color) void { + switch (backend) { + .cpu => r.target.clear(clear), + .gpu => r.target.begin(f.arena, clear), + } + } + + /// All shapes of `d`; `m` maps its user space to pixels. + pub fn draw(r: *Self, d: Drawing, m: geom.Affine, alpha: f32) !void { + for (d.shapes) |shape| try r.drawShape(d, shape, m, .{ .alpha = alpha }); + } + + pub fn drawShape(r: *Self, d: Drawing, shape: Drawing.Shape, user_to_device: geom.Affine, o: Options) !void { + const m = user_to_device.mul(shape.transform); + const s = shape.style; + const clip: ?[4]geom.Vec = if (shape.clip) |q| .{ user_to_device.apply(q[0]), user_to_device.apply(q[1]), user_to_device.apply(q[2]), user_to_device.apply(q[3]) } else null; + if (o.fill and s.fill != .none) { + r.polys.clear(); + try r.polys.fill(d, shape, m); + if (clip) |q| try r.polys.clipConvex(q); + r.fill(s.fill_rule, &Paint.of(d, shape, s.fill, m), o.alpha * s.opacity * s.fill_opacity); + } + if (o.stroke and s.stroke != .none and s.stroke_width > 0) { + var st: Polygons.Stroke = .of(s, m); + st.dashes = s.dashes[0..s.dash_count]; + st.trim = o.trim; + r.polys.clear(); + try r.polys.stroke(d, shape, m, st); + if (clip) |q| try r.polys.clipConvex(q); + r.fill(.nonzero, &Paint.of(d, shape, s.stroke, m), o.alpha * s.opacity * s.stroke_opacity); + } + if (o.outline) |outline| if (s.fill != .none) { + r.polys.clear(); + try r.polys.stroke(d, shape, m, .{ .width = outline.width, .cap = .round, .join = .round, .trim = o.trim, .space = .identity }); + r.fill(.nonzero, &Paint.of(d, shape, s.fill, m), o.alpha * s.opacity * outline.alpha); + }; + } + + /// Fills whatever is in `r.polys`. + pub fn fill(r: *Self, rule: Drawing.FillRule, paint: *const Paint, alpha: f32) void { + r.target.fill(&r.polys, rule, paint, alpha); + } + + /// Hands the picture to the host and draws it at `dst`. + 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()), + } + f.image(r.image, dst, .{}); + } + }; +} + +/// The transform placing a drawing's view box into `dst`, centered and +/// scaled to fit (SVG's default `xMidYMid meet`). +pub fn fit(d: Drawing, dst: geom.Rect) geom.Affine { + const v = d.view; + if (v.w <= 0 or v.h <= 0) return .translate(dst.x, dst.y); + const s = @min(dst.w / v.w, dst.h / v.h); + return geom.Affine.translate(dst.x + (dst.w - v.w * s) / 2, dst.y + (dst.h - v.h * s) / 2).mul(.scale(s, s)).mul(.translate(-v.x, -v.y)); +} + +test { + _ = morph; + _ = geom; + _ = svg; + _ = Polygons; + _ = Cpu; + _ = Gpu; +} diff --git a/src/vector/shaders/cover.frag b/src/vector/shaders/cover.frag new file mode 100644 index 0000000..a57a916 --- /dev/null +++ b/src/vector/shaders/cover.frag @@ -0,0 +1,65 @@ +#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. +layout(location = 0) out vec4 out_color; + +#include "Paint.glsl" + +float offset_at(int i) { + return paint.offsets[i / 4][i % 4]; +} + +vec4 premultiply(vec4 c) { + return vec4(c.rgb * c.a, c.a); +} + +float param(vec2 q) { + vec2 g = vec2(dot(paint.row0.xyz, vec3(q, 1.0)), dot(paint.row1.xyz, vec3(q, 1.0))); + vec2 p0 = paint.points.xy; + vec2 p1 = paint.points.zw; + float t = 0.0; + if (paint.row0.w < 1.5) { + vec2 dir = p1 - p0; + float len2 = dot(dir, dir); + t = len2 > 0.0 ? dot(g - p0, dir) / len2 : 0.0; + } else { + // Where the ray from the focus through g meets the circle. + vec2 dq = g - p1; + vec2 cf = p1 - p0; + float a = dot(dq, dq); + if (a > 0.0) { + float b = dot(dq, cf); + float c = dot(cf, cf) - paint.extra.x * paint.extra.x; + float s = (-b + sqrt(max(b * b - a * c, 0.0))) / a; + t = s > 0.0 ? 1.0 / s : 1.0; + } + } + if (paint.row1.w < 0.5) return clamp(t, 0.0, 1.0); + if (paint.row1.w < 1.5) { + float r = mod(t, 2.0); + return r > 1.0 ? 2.0 - r : r; + } + return t - floor(t); +} + +vec4 stop_color(float t) { + int count = int(paint.extra.z); + if (count == 0) return vec4(0.0); + if (t <= offset_at(0)) return premultiply(paint.colors[0]); + for (int i = 1; i < count; i++) { + float b = offset_at(i); + if (t <= b) { + float a = offset_at(i - 1); + float u = b > a ? (t - a) / (b - a) : 1.0; + return premultiply(mix(paint.colors[i - 1], paint.colors[i], u)); + } + } + return premultiply(paint.colors[count - 1]); +} + +void main() { + vec4 c = paint.row0.w < 0.5 ? paint.color : stop_color(param(gl_FragCoord.xy)); + out_color = c * paint.extra.y; +} diff --git a/src/vector/shaders/path.vert b/src/vector/shaders/path.vert new file mode 100644 index 0000000..dbca9f8 --- /dev/null +++ b/src/vector/shaders/path.vert @@ -0,0 +1,9 @@ +#version 450 +#extension GL_GOOGLE_include_directive : require +// Device pixels (y down) to normalized device coordinates (y up). +#include "Vertex.glsl" +#include "Viewport.glsl" + +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); +} diff --git a/src/vector/shaders/stencil.frag b/src/vector/shaders/stencil.frag new file mode 100644 index 0000000..caf85f4 --- /dev/null +++ b/src/vector/shaders/stencil.frag @@ -0,0 +1,7 @@ +#version 450 +// Stencil passes write no color; the pipeline masks it out anyway. +layout(location = 0) out vec4 color; + +void main() { + color = vec4(0.0); +} diff --git a/src/vector/svg.zig b/src/vector/svg.zig new file mode 100644 index 0000000..9c0ec53 --- /dev/null +++ b/src/vector/svg.zig @@ -0,0 +1,768 @@ +//! SVG to `Drawing`: the static subset that documents (Typst's output in +//! particular) are made of. Structure: `svg`, `g`, `defs`, `symbol`, `use`. +//! Shapes: `path` (every command, arcs included), `rect`, `circle`, +//! `ellipse`, `line`, `polyline`, `polygon`. Styling: presentation +//! attributes and `style="..."`, inherited as SVG specifies; solid colors, +//! linear and radial gradients; fill rules; stroke width, caps, joins, miter +//! limit and dashes; `opacity`, `fill-opacity`, `stroke-opacity`. +//! +//! Not supported: text (Typst outlines it), filters, masks, clipping, +//! 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 Drawing = @import("Drawing.zig"); +const Vec = geom.Vec; +const Affine = geom.Affine; + +pub const Error = error{ InvalidSvg, OutOfMemory }; + +/// Parses `source` into a drawing allocated with `arena`. +pub fn parse(arena: std.mem.Allocator, source: []const u8) Error!Drawing { + var doc = try Document.parse(arena, source); + const root = doc.root orelse return error.InvalidSvg; + if (!std.mem.eql(u8, doc.nodes.items[root].name, "svg")) return error.InvalidSvg; + + var p: Parser = .{ .doc = &doc, .b = .init(arena), .arena = arena, .view = .{} }; + const n = doc.nodes.items[root]; + const w = doc.attr(n, "width"); + const h = doc.attr(n, "height"); + var view: geom.Rect = .{}; + if (doc.attr(n, "viewBox")) |vb| { + var nums = Numbers{ .text = vb }; + view = .{ .x = nums.next() orelse 0, .y = nums.next() orelse 0, .w = nums.next() orelse 0, .h = nums.next() orelse 0 }; + } + var width = if (w) |v| lengthPx(v, view.w) else view.w; + var height = if (h) |v| lengthPx(v, view.h) else view.h; + if (view.w <= 0 or view.h <= 0) view = .{ .w = width, .h = height }; + if (width <= 0) width = view.w; + if (height <= 0) height = view.h; + p.view = view; + try p.children(root, .identity, .{}); + return p.b.finish(view, width, height); +} + +// --------------------------------------------------------------------------- +// A minimal XML reader: elements and attributes into flat arrays. + +const Attr = struct { name: []const u8, value: []const u8 }; +const Node = struct { + name: []const u8, + attrs: []const Attr, + first_child: ?u32 = null, + next_sibling: ?u32 = null, +}; + +const Document = struct { + nodes: std.ArrayList(Node) = .empty, + ids: std.StringHashMapUnmanaged(u32) = .empty, + root: ?u32 = null, + + fn attr(doc: *const Document, n: Node, name: []const u8) ?[]const u8 { + _ = doc; + for (n.attrs) |a| if (std.mem.eql(u8, a.name, name)) return a.value; + return null; + } + + fn parse(arena: std.mem.Allocator, s: []const u8) Error!Document { + var doc: Document = .{}; + // Open elements, and the last child appended to each. + var stack: std.ArrayList(struct { node: u32, last: ?u32 }) = .empty; + var i: usize = 0; + while (std.mem.indexOfScalarPos(u8, s, i, '<')) |lt| { + i = lt + 1; + if (std.mem.startsWith(u8, s[i..], "!--")) { + i = (std.mem.indexOfPos(u8, s, i, "-->") orelse return error.InvalidSvg) + 3; + } else if (std.mem.startsWith(u8, s[i..], "![CDATA[")) { + i = (std.mem.indexOfPos(u8, s, i, "]]>") orelse return error.InvalidSvg) + 3; + } else if (s.len > i and (s[i] == '?' or s[i] == '!')) { + i = (std.mem.indexOfScalarPos(u8, s, i, '>') orelse return error.InvalidSvg) + 1; + } else if (s.len > i and s[i] == '/') { + i = (std.mem.indexOfScalarPos(u8, s, i, '>') orelse return error.InvalidSvg) + 1; + _ = stack.pop() orelse return error.InvalidSvg; + } else { + const name_end = std.mem.indexOfAnyPos(u8, s, i, " \t\r\n/>") orelse return error.InvalidSvg; + const name = localName(s[i..name_end]); + i = name_end; + var attrs: std.ArrayList(Attr) = .empty; + var self_closing = false; + while (true) { + while (i < s.len and std.ascii.isWhitespace(s[i])) i += 1; + if (i >= s.len) return error.InvalidSvg; + if (s[i] == '>') { + i += 1; + break; + } + if (s[i] == '/') { + self_closing = true; + i = (std.mem.indexOfScalarPos(u8, s, i, '>') orelse return error.InvalidSvg) + 1; + break; + } + const eq = std.mem.indexOfScalarPos(u8, s, i, '=') orelse return error.InvalidSvg; + const attr_name = std.mem.trim(u8, s[i..eq], " \t\r\n"); + var q = eq + 1; + while (q < s.len and std.ascii.isWhitespace(s[q])) q += 1; + if (q >= s.len or (s[q] != '"' and s[q] != '\'')) return error.InvalidSvg; + const close = std.mem.indexOfScalarPos(u8, s, q + 1, s[q]) orelse return error.InvalidSvg; + try attrs.append(arena, .{ .name = attr_name, .value = try entities(arena, s[q + 1 .. close]) }); + i = close + 1; + } + const index: u32 = @intCast(doc.nodes.items.len); + try doc.nodes.append(arena, .{ .name = name, .attrs = attrs.items }); + for (attrs.items) |a| if (std.mem.eql(u8, a.name, "id")) try doc.ids.put(arena, a.value, index); + if (stack.items.len == 0) { + if (doc.root == null) doc.root = index; + } else { + const parent = &stack.items[stack.items.len - 1]; + if (parent.last) |last| doc.nodes.items[last].next_sibling = index else doc.nodes.items[parent.node].first_child = index; + parent.last = index; + } + if (!self_closing) try stack.append(arena, .{ .node = index, .last = null }); + } + } + return doc; + } +}; + +/// `svg:path` and `path` are the same element to us. +fn localName(qualified: []const u8) []const u8 { + return if (std.mem.indexOfScalar(u8, qualified, ':')) |colon| qualified[colon + 1 ..] else qualified; +} + +fn entities(arena: std.mem.Allocator, raw: []const u8) ![]const u8 { + if (std.mem.indexOfScalar(u8, raw, '&') == null) return raw; + var out: std.ArrayList(u8) = .empty; + var i: usize = 0; + while (i < raw.len) { + if (raw[i] == '&') if (std.mem.indexOfScalarPos(u8, raw, i, ';')) |semi| { + const name = raw[i + 1 .. semi]; + const char: ?u21 = if (std.mem.eql(u8, name, "amp")) '&' else if (std.mem.eql(u8, name, "lt")) '<' else if (std.mem.eql(u8, name, "gt")) '>' else if (std.mem.eql(u8, name, "quot")) '"' else if (std.mem.eql(u8, name, "apos")) '\'' else if (name.len > 1 and name[0] == '#') + (if (name[1] == 'x') std.fmt.parseInt(u21, name[2..], 16) catch null else std.fmt.parseInt(u21, name[1..], 10) catch null) + else + null; + if (char) |ch| { + var buf: [4]u8 = undefined; + const len = std.unicode.utf8Encode(ch, &buf) catch 0; + try out.appendSlice(arena, buf[0..len]); + i = semi + 1; + continue; + } + }; + try out.append(arena, raw[i]); + i += 1; + } + return out.items; +} + +// --------------------------------------------------------------------------- +// Tree walk: inherited style and transforms, shapes into the builder. + +const Parser = struct { + doc: *Document, + b: Drawing.Builder, + arena: std.mem.Allocator, + /// The root viewport, which `100%` lengths refer to. + view: geom.Rect, + /// Gradient ids already converted, by index in the builder. + gradients: std.StringHashMapUnmanaged(u32) = .empty, + /// Guards against `use` cycles. + depth: u32 = 0, + + const Inherited = struct { + style: Drawing.Style = .{}, + color: Drawing.Color = .{ 0, 0, 0, 1 }, + /// The innermost viewport clip, in the drawing's user space. + clip: ?[4]Vec = null, + }; + + fn children(p: *Parser, index: u32, transform: Affine, inherited: Inherited) Error!void { + var child = p.doc.nodes.items[index].first_child; + while (child) |c| : (child = p.doc.nodes.items[c].next_sibling) try p.element(c, transform, inherited); + } + + fn element(p: *Parser, index: u32, parent_transform: Affine, parent: Inherited) Error!void { + const n = p.doc.nodes.items[index]; + const name = n.name; + const skip = [_][]const u8{ "defs", "symbol", "linearGradient", "radialGradient", "clipPath", "mask", "pattern", "marker", "style", "title", "desc", "metadata", "filter", "text", "image", "foreignObject" }; + for (skip) |s| if (std.mem.eql(u8, name, s)) return; + if (p.depth > 64) return; + var inherited = parent; + try p.applyStyle(n, &inherited); + if (std.mem.eql(u8, p.doc.attr(n, "display") orelse "", "none")) return; + var transform = parent_transform; + if (p.doc.attr(n, "transform")) |t| transform = transform.mul(parseTransform(t)); + + if (std.mem.eql(u8, name, "g") or std.mem.eql(u8, name, "svg") or std.mem.eql(u8, name, "a") or std.mem.eql(u8, name, "switch")) { + if (std.mem.eql(u8, name, "svg")) transform = transform.mul(.translate(p.number(n, "x"), p.number(n, "y"))); + return p.children(index, transform, inherited); + } + if (std.mem.eql(u8, name, "use")) { + const href = p.doc.attr(n, "href") orelse p.doc.attr(n, "xlink:href") orelse return; + if (href.len < 2 or href[0] != '#') return; + const target = p.doc.ids.get(href[1..]) orelse return; + transform = transform.mul(.translate(p.number(n, "x"), p.number(n, "y"))); + p.depth += 1; + defer p.depth -= 1; + const t = p.doc.nodes.items[target]; + if (std.mem.eql(u8, t.name, "symbol")) { + var sym = inherited; + try p.applyStyle(t, &sym); + // A symbol is a new viewport: the use's size, or the whole + // canvas; its viewBox maps into it, and it clips unless its + // overflow is visible. + const w = if (p.doc.attr(n, "width")) |v| lengthPx(v, p.view.w) else p.view.w; + const h = if (p.doc.attr(n, "height")) |v| lengthPx(v, p.view.h) else p.view.h; + const overflow = p.doc.attr(t, "overflow") orelse "hidden"; + if (!std.mem.eql(u8, overflow, "visible") and !std.mem.eql(u8, overflow, "auto")) { + sym.clip = .{ transform.apply(.{ 0, 0 }), transform.apply(.{ w, 0 }), transform.apply(.{ w, h }), transform.apply(.{ 0, h }) }; + } + var inner = transform; + if (p.doc.attr(t, "viewBox")) |vb| { + var nums = Numbers{ .text = vb }; + const v: geom.Rect = .{ .x = nums.next() orelse 0, .y = nums.next() orelse 0, .w = nums.next() orelse 0, .h = nums.next() orelse 0 }; + if (v.w > 0 and v.h > 0) { + const s = @min(w / v.w, h / v.h); + inner = inner.mul(.translate((w - v.w * s) / 2, (h - v.h * s) / 2)).mul(.scale(s, s)).mul(.translate(-v.x, -v.y)); + } + } + return p.children(target, inner, sym); + } + return p.element(target, transform, inherited); + } + + const b = &p.b; + if (std.mem.eql(u8, name, "path")) { + try pathData(b, p.arena, p.doc.attr(n, "d") orelse return); + } else if (std.mem.eql(u8, name, "rect")) { + const w = p.number(n, "width"); + const h = p.number(n, "height"); + if (w <= 0 or h <= 0) return; + var rx = p.doc.attr(n, "rx"); + var ry = p.doc.attr(n, "ry"); + if (rx == null) rx = ry; + if (ry == null) ry = rx; + const r: geom.Rect = .{ .x = p.number(n, "x"), .y = p.number(n, "y"), .w = w, .h = h }; + const rxv = @min(if (rx) |v| parseLength(v) else 0, w / 2); + const ryv = @min(if (ry) |v| parseLength(v) else 0, h / 2); + if (rxv > 0 and ryv > 0) { + try b.roundedRect(r, rxv, ryv); + try b.closeSubpath(true); + } else try b.rect(r, 0); + } else if (std.mem.eql(u8, name, "circle")) { + const r = p.number(n, "r"); + if (r <= 0) return; + try b.ellipse(.{ p.number(n, "cx"), p.number(n, "cy") }, r, r); + } else if (std.mem.eql(u8, name, "ellipse")) { + const rx = p.number(n, "rx"); + const ry = p.number(n, "ry"); + if (rx <= 0 or ry <= 0) return; + try b.ellipse(.{ p.number(n, "cx"), p.number(n, "cy") }, rx, ry); + } else if (std.mem.eql(u8, name, "line")) { + try b.lineTo(.{ p.number(n, "x1"), p.number(n, "y1") }, .{ p.number(n, "x2"), p.number(n, "y2") }); + try b.closeSubpath(false); + } else if (std.mem.eql(u8, name, "polyline") or std.mem.eql(u8, name, "polygon")) { + var points: std.ArrayList(Vec) = .empty; + var nums = Numbers{ .text = p.doc.attr(n, "points") orelse return }; + while (nums.next()) |x| try points.append(p.arena, .{ x, nums.next() orelse break }); + try b.polyline(points.items, std.mem.eql(u8, name, "polygon")); + } else return; + const before = b.shapes.items.len; + try b.endShape(transform, inherited.style); + if (b.shapes.items.len > before) b.shapes.items[before].clip = inherited.clip; + } + + fn number(p: *Parser, n: Node, name: []const u8) f32 { + return parseLength(p.doc.attr(n, name) orelse return 0); + } + + /// Presentation attributes, then `style="..."` declarations on top. + fn applyStyle(p: *Parser, n: Node, inherited: *Inherited) Error!void { + // `opacity` multiplies down the tree (see `property`). + for (n.attrs) |a| try p.property(a.name, a.value, inherited); + if (p.doc.attr(n, "style")) |css| { + var decls = std.mem.tokenizeScalar(u8, css, ';'); + while (decls.next()) |decl| { + const colon = std.mem.indexOfScalar(u8, decl, ':') orelse continue; + try p.property(std.mem.trim(u8, decl[0..colon], " \t\r\n"), std.mem.trim(u8, decl[colon + 1 ..], " \t\r\n"), inherited); + } + } + } + + fn property(p: *Parser, name: []const u8, raw: []const u8, inherited: *Inherited) Error!void { + const value = std.mem.trim(u8, raw, " \t\r\n"); + const s = &inherited.style; + const eql = std.mem.eql; + if (eql(u8, value, "inherit")) return; + if (eql(u8, name, "color")) { + if (parseColor(value, inherited.color)) |c| inherited.color = c; + } else if (eql(u8, name, "fill")) { + s.fill = try p.paint(value, inherited.color) orelse s.fill; + } else if (eql(u8, name, "stroke")) { + s.stroke = try p.paint(value, inherited.color) orelse s.stroke; + } else if (eql(u8, name, "fill-rule")) { + s.fill_rule = if (eql(u8, value, "evenodd")) .evenodd else .nonzero; + } else if (eql(u8, name, "fill-opacity")) { + s.fill_opacity = parseOpacity(value); + } else if (eql(u8, name, "stroke-opacity")) { + s.stroke_opacity = parseOpacity(value); + } else if (eql(u8, name, "opacity")) { + s.opacity *= parseOpacity(value); + } else if (eql(u8, name, "stroke-width")) { + s.stroke_width = parseLength(value); + } else if (eql(u8, name, "stroke-linecap")) { + s.cap = std.meta.stringToEnum(Drawing.Cap, value) orelse s.cap; + } else if (eql(u8, name, "stroke-linejoin")) { + s.join = if (eql(u8, value, "miter-clip") or eql(u8, value, "arcs")) .miter else std.meta.stringToEnum(Drawing.Join, value) orelse s.join; + } else if (eql(u8, name, "stroke-miterlimit")) { + s.miter_limit = @max(1, parseLength(value)); + } else if (eql(u8, name, "stroke-dasharray")) { + s.dash_count = 0; + if (!eql(u8, value, "none")) { + var nums = Numbers{ .text = value }; + var total: f32 = 0; + while (nums.next()) |d| { + if (s.dash_count == s.dashes.len or d < 0) break; + s.dashes[s.dash_count] = d; + s.dash_count += 1; + total += d; + } + if (total <= 0) s.dash_count = 0; + // An odd list repeats to make an even one. + if (s.dash_count % 2 == 1 and s.dash_count * 2 <= s.dashes.len) { + @memcpy(s.dashes[s.dash_count..][0..s.dash_count], s.dashes[0..s.dash_count]); + s.dash_count *= 2; + } + } + } else if (eql(u8, name, "stroke-dashoffset")) { + s.dash_offset = parseLength(value); + } + } + + fn paint(p: *Parser, value: []const u8, current: Drawing.Color) Error!?Drawing.Paint { + if (std.mem.eql(u8, value, "none")) return .none; + if (std.mem.startsWith(u8, value, "url(")) { + const close = std.mem.indexOfScalar(u8, value, ')') orelse return null; + const ref = std.mem.trim(u8, value[4..close], " '\""); + if (ref.len > 1 and ref[0] == '#') if (try p.gradient(ref[1..])) |g| return .{ .gradient = g }; + // A missing paint server falls back to what follows it, or none. + const fallback = std.mem.trim(u8, value[close + 1 ..], " "); + return if (fallback.len > 0) try p.paint(fallback, current) else .none; + } + return if (parseColor(value, current)) |c| .{ .color = c } else null; + } + + fn gradient(p: *Parser, id: []const u8) Error!?u32 { + if (p.gradients.get(id)) |g| return g; + const index = p.doc.ids.get(id) orelse return null; + const n = p.doc.nodes.items[index]; + const radial = std.mem.eql(u8, n.name, "radialGradient"); + if (!radial and !std.mem.eql(u8, n.name, "linearGradient")) return null; + var g: Drawing.Gradient = .{ .kind = if (radial) .radial else .linear }; + if (radial) { + g.p0 = .{ 0.5, 0.5 }; + g.p1 = .{ 0.5, 0.5 }; + } + // Attributes and stops come from the first element in the href chain + // that has them. + var chain: [8]Node = undefined; + var len: usize = 0; + var at: ?u32 = index; + while (at) |i| : (len += 1) { + if (len == chain.len) break; + chain[len] = p.doc.nodes.items[i]; + const href = p.doc.attr(chain[len], "href") orelse p.doc.attr(chain[len], "xlink:href") orelse ""; + at = if (href.len > 1 and href[0] == '#') p.doc.ids.get(href[1..]) else null; + } + const find = struct { + fn find(doc: *Document, nodes: []const Node, name: []const u8) ?[]const u8 { + for (nodes) |node| if (doc.attr(node, name)) |v| return v; + return null; + } + }.find; + const nodes = chain[0..len]; + if (find(p.doc, nodes, "gradientUnits")) |u| g.bounding_box = !std.mem.eql(u8, u, "userSpaceOnUse"); + if (find(p.doc, nodes, "gradientTransform")) |t| g.transform = parseTransform(t); + if (find(p.doc, nodes, "spreadMethod")) |s| g.spread = if (std.mem.eql(u8, s, "reflect")) .reflect else if (std.mem.eql(u8, s, "repeat")) .repeat else .pad; + const coord = struct { + fn coord(doc: *Document, ns: []const Node, name: []const u8, default: f32, bbox: bool) f32 { + const v = find(doc, ns, name) orelse return default; + const t = std.mem.trim(u8, v, " "); + if (bbox and t.len > 0 and t[t.len - 1] == '%') return (std.fmt.parseFloat(f32, t[0 .. t.len - 1]) catch 0) / 100; + return parseLength(t); + } + }.coord; + if (radial) { + const cx = coord(p.doc, nodes, "cx", 0.5, g.bounding_box); + const cy = coord(p.doc, nodes, "cy", 0.5, g.bounding_box); + g.p0 = .{ cx, cy }; + g.p1 = .{ coord(p.doc, nodes, "fx", cx, g.bounding_box), coord(p.doc, nodes, "fy", cy, g.bounding_box) }; + g.radius = coord(p.doc, nodes, "r", 0.5, g.bounding_box); + } else { + g.p0 = .{ coord(p.doc, nodes, "x1", 0, g.bounding_box), coord(p.doc, nodes, "y1", 0, g.bounding_box) }; + g.p1 = .{ coord(p.doc, nodes, "x2", 1, g.bounding_box), coord(p.doc, nodes, "y2", 0, g.bounding_box) }; + } + var stops: std.ArrayList(Drawing.Gradient.Stop) = .empty; + for (nodes) |node| { + var child = node.first_child; + while (child) |c| : (child = p.doc.nodes.items[c].next_sibling) { + const stop = p.doc.nodes.items[c]; + if (!std.mem.eql(u8, stop.name, "stop")) continue; + var color: Drawing.Color = .{ 0, 0, 0, 1 }; + var opacity: f32 = 1; + var offset: f32 = 0; + const apply = struct { + fn apply(name: []const u8, value: []const u8, col: *Drawing.Color, op: *f32, off: *f32) void { + const v = std.mem.trim(u8, value, " "); + if (std.mem.eql(u8, name, "stop-color")) { + if (parseColor(v, .{ 0, 0, 0, 1 })) |parsed| col.* = parsed; + } else if (std.mem.eql(u8, name, "stop-opacity")) { + op.* = parseOpacity(v); + } else if (std.mem.eql(u8, name, "offset")) { + off.* = parseOpacity(v); + } + } + }.apply; + for (stop.attrs) |a| apply(a.name, a.value, &color, &opacity, &offset); + if (p.doc.attr(stop, "style")) |css| { + var decls = std.mem.tokenizeScalar(u8, css, ';'); + while (decls.next()) |decl| { + const colon = std.mem.indexOfScalar(u8, decl, ':') orelse continue; + apply(std.mem.trim(u8, decl[0..colon], " "), decl[colon + 1 ..], &color, &opacity, &offset); + } + } + color[3] *= opacity; + // Offsets never go backwards. + if (stops.items.len > 0) offset = @max(offset, stops.items[stops.items.len - 1].offset); + try stops.append(p.arena, .{ .offset = std.math.clamp(offset, 0, 1), .color = color }); + } + if (stops.items.len > 0) break; + } + if (stops.items.len == 0) return null; + g.stops = stops.items; + const at_index: u32 = @intCast(p.b.gradients.items.len); + try p.b.gradients.append(p.arena, g); + try p.gradients.put(p.arena, id, at_index); + return at_index; + } +}; + +// --------------------------------------------------------------------------- +// Values + +/// Numbers separated by whitespace and/or commas, SVG style: "1-2" is two +/// numbers, ".5.5" too. +pub const Numbers = struct { + text: []const u8, + i: usize = 0, + + pub fn next(n: *Numbers) ?f32 { + n.skip(); + if (n.i >= n.text.len) return null; + const start = n.i; + var j = n.i; + if (j < n.text.len and (n.text[j] == '+' or n.text[j] == '-')) j += 1; + var dot = false; + while (j < n.text.len) : (j += 1) { + const ch = n.text[j]; + if (std.ascii.isDigit(ch)) continue; + if (ch == '.' and !dot) { + dot = true; + continue; + } + if ((ch == 'e' or ch == 'E') and j + 1 < n.text.len and (std.ascii.isDigit(n.text[j + 1]) or ((n.text[j + 1] == '-' or n.text[j + 1] == '+') and j + 2 < n.text.len and std.ascii.isDigit(n.text[j + 2])))) { + j += 2; + while (j < n.text.len and std.ascii.isDigit(n.text[j])) j += 1; + break; + } + break; + } + if (j == start) return null; + n.i = j; + return std.fmt.parseFloat(f32, n.text[start..j]) catch null; + } + /// A single `0`/`1` arc flag, which may be glued to what follows. + pub fn flag(n: *Numbers) ?bool { + n.skip(); + if (n.i >= n.text.len) return null; + const ch = n.text[n.i]; + if (ch != '0' and ch != '1') return null; + n.i += 1; + return ch == '1'; + } + fn skip(n: *Numbers) void { + while (n.i < n.text.len and (std.ascii.isWhitespace(n.text[n.i]) or n.text[n.i] == ',')) n.i += 1; + } +}; + +/// A length in user units: unitless and px as-is, other absolute units +/// converted at 96 dpi. Percentages and font units fall back to the number. +pub fn parseLength(raw: []const u8) f32 { + const v = std.mem.trim(u8, raw, " \t\r\n"); + var nums = Numbers{ .text = v }; + const n = nums.next() orelse return 0; + const unit = std.mem.trim(u8, v[nums.i..], " "); + const scale: f32 = if (std.mem.eql(u8, unit, "pt")) 4.0 / 3.0 else if (std.mem.eql(u8, unit, "pc")) 16 else if (std.mem.eql(u8, unit, "in")) 96 else if (std.mem.eql(u8, unit, "cm")) 96.0 / 2.54 else if (std.mem.eql(u8, unit, "mm")) 96.0 / 25.4 else if (std.mem.eql(u8, unit, "em")) 16 else 1; + return n * scale; +} + +/// Like `parseLength`, but a percentage of `reference`. +fn lengthPx(raw: []const u8, reference: f32) f32 { + const v = std.mem.trim(u8, raw, " "); + if (v.len > 0 and v[v.len - 1] == '%') return (std.fmt.parseFloat(f32, v[0 .. v.len - 1]) catch 100) / 100 * reference; + return parseLength(v); +} + +fn parseOpacity(raw: []const u8) f32 { + const v = std.mem.trim(u8, raw, " "); + if (v.len > 0 and v[v.len - 1] == '%') return std.math.clamp((std.fmt.parseFloat(f32, v[0 .. v.len - 1]) catch 100) / 100, 0, 1); + return std.math.clamp(std.fmt.parseFloat(f32, v) catch 1, 0, 1); +} + +pub fn parseTransform(text: []const u8) Affine { + var m: Affine = .identity; + var i: usize = 0; + while (std.mem.indexOfScalarPos(u8, text, i, '(')) |open| { + const name = std.mem.trim(u8, text[i..open], " \t\r\n,"); + const close = std.mem.indexOfScalarPos(u8, text, open, ')') orelse break; + var nums = Numbers{ .text = text[open + 1 .. close] }; + var v: [6]f32 = @splat(0); + var count: usize = 0; + while (nums.next()) |x| : (count += 1) { + if (count == v.len) break; + v[count] = x; + } + const deg = std.math.pi / 180.0; + const t: Affine = if (std.mem.eql(u8, name, "matrix") and count == 6) + .{ .a = v[0], .b = v[1], .c = v[2], .d = v[3], .e = v[4], .f = v[5] } + else if (std.mem.eql(u8, name, "translate")) + .translate(v[0], if (count > 1) v[1] else 0) + else if (std.mem.eql(u8, name, "scale")) + .scale(v[0], if (count > 1) v[1] else v[0]) + else if (std.mem.eql(u8, name, "rotate")) + Affine.translate(v[1], v[2]).mul(.rotate(v[0] * deg)).mul(.translate(-v[1], -v[2])) + else if (std.mem.eql(u8, name, "skewX")) + .skew(v[0] * deg, 0) + else if (std.mem.eql(u8, name, "skewY")) + .skew(0, v[0] * deg) + else + .identity; + m = m.mul(t); + i = close + 1; + } + return m; +} + +/// `#rgb`, `#rgba`, `#rrggbb`, `#rrggbbaa`, `rgb()`/`rgba()` (numbers or +/// percentages), `currentColor`, `transparent` and the common named colors. +pub fn parseColor(raw: []const u8, current: Drawing.Color) ?Drawing.Color { + const v = std.mem.trim(u8, raw, " \t\r\n"); + if (v.len == 0) return null; + if (v[0] == '#') { + const hex = v[1..]; + const digit = struct { + fn d(ch: u8) ?f32 { + return @floatFromInt(std.fmt.charToDigit(ch, 16) catch return null); + } + }.d; + switch (hex.len) { + 3, 4 => { + var c: [4]f32 = .{ 0, 0, 0, 1 }; + for (hex, 0..) |ch, i| c[i] = (digit(ch) orelse return null) * 17 / 255; + return c; + }, + 6, 8 => { + var c: [4]f32 = .{ 0, 0, 0, 1 }; + for (0..hex.len / 2) |i| c[i] = ((digit(hex[2 * i]) orelse return null) * 16 + (digit(hex[2 * i + 1]) orelse return null)) / 255; + return c; + }, + else => return null, + } + } + if (std.ascii.startsWithIgnoreCase(v, "rgb")) { + const open = std.mem.indexOfScalar(u8, v, '(') orelse return null; + const close = std.mem.indexOfScalar(u8, v, ')') orelse return null; + var parts = std.mem.tokenizeAny(u8, v[open + 1 .. close], ", /"); + var c: [4]f32 = .{ 0, 0, 0, 1 }; + var i: usize = 0; + while (parts.next()) |part| : (i += 1) { + if (i == 4) break; + const pct = part[part.len - 1] == '%'; + const n = std.fmt.parseFloat(f32, if (pct) part[0 .. part.len - 1] else part) catch return null; + c[i] = std.math.clamp(if (i == 3) (if (pct) n / 100 else n) else if (pct) n / 100 else n / 255, 0, 1); + } + return c; + } + if (std.ascii.eqlIgnoreCase(v, "currentColor")) return current; + if (std.ascii.eqlIgnoreCase(v, "transparent")) return .{ 0, 0, 0, 0 }; + for (named) |entry| if (std.ascii.eqlIgnoreCase(v, entry[0])) { + const rgb: u24 = entry[1]; + return .{ @as(f32, @floatFromInt(rgb >> 16)) / 255, @as(f32, @floatFromInt((rgb >> 8) & 0xff)) / 255, @as(f32, @floatFromInt(rgb & 0xff)) / 255, 1 }; + }; + return null; +} + +const named = [_]struct { []const u8, u24 }{ + .{ "black", 0x000000 }, .{ "white", 0xffffff }, .{ "red", 0xff0000 }, .{ "lime", 0x00ff00 }, + .{ "green", 0x008000 }, .{ "blue", 0x0000ff }, .{ "yellow", 0xffff00 }, .{ "cyan", 0x00ffff }, + .{ "aqua", 0x00ffff }, .{ "magenta", 0xff00ff }, .{ "fuchsia", 0xff00ff }, .{ "gray", 0x808080 }, + .{ "grey", 0x808080 }, .{ "silver", 0xc0c0c0 }, .{ "maroon", 0x800000 }, .{ "olive", 0x808000 }, + .{ "navy", 0x000080 }, .{ "purple", 0x800080 }, .{ "teal", 0x008080 }, .{ "orange", 0xffa500 }, + .{ "pink", 0xffc0cb }, .{ "brown", 0xa52a2a }, .{ "gold", 0xffd700 }, .{ "indigo", 0x4b0082 }, + .{ "violet", 0xee82ee }, .{ "coral", 0xff7f50 }, .{ "salmon", 0xfa8072 }, .{ "tomato", 0xff6347 }, + .{ "orchid", 0xda70d6 }, .{ "crimson", 0xdc143c }, .{ "skyblue", 0x87ceeb }, .{ "steelblue", 0x4682b4 }, + .{ "darkgray", 0xa9a9a9 }, .{ "lightgray", 0xd3d3d3 }, .{ "darkgreen", 0x006400 }, .{ "darkblue", 0x00008b }, + .{ "darkred", 0x8b0000 }, .{ "lightblue", 0xadd8e6 }, .{ "turquoise", 0x40e0d0 }, .{ "khaki", 0xf0e68c }, +}; + +/// Path data into cubics: every command, absolute and relative, with +/// implicit repeats and the smooth-curve reflections. +pub fn pathData(b: *Drawing.Builder, gpa: std.mem.Allocator, d: []const u8) !void { + var nums = Numbers{ .text = d }; + var command: u8 = 0; + var current: Vec = .{ 0, 0 }; + var start: Vec = .{ 0, 0 }; + // Last control point, for S and T reflections. + var last_cubic: ?Vec = null; + var last_quad: ?Vec = null; + var arcs: std.ArrayList(geom.Cubic) = .empty; + while (true) { + nums.skip(); + if (nums.i >= d.len) break; + const ch = d[nums.i]; + if (std.ascii.isAlphabetic(ch) and ch != 'e' and ch != 'E') { + command = ch; + nums.i += 1; + if (ch == 'z' or ch == 'Z') { + if (@reduce(.Or, current != start)) try b.lineTo(current, start); + try b.closeSubpath(true); + current = start; + last_cubic = null; + last_quad = null; + continue; + } + } else if (command == 0) return; + const rel = std.ascii.isLower(command); + const base: Vec = if (rel) current else .{ 0, 0 }; + const cubic_before = last_cubic; + const quad_before = last_quad; + last_cubic = null; + last_quad = null; + switch (std.ascii.toUpper(command)) { + 'M' => { + const p = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + try b.closeSubpath(false); + current = p; + start = p; + // Further pairs are line-tos. + command = if (rel) 'l' else 'L'; + }, + 'L' => { + const p = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + try b.lineTo(current, p); + current = p; + }, + 'H' => { + const x = nums.next() orelse return; + const p: Vec = .{ if (rel) current[0] + x else x, current[1] }; + try b.lineTo(current, p); + current = p; + }, + 'V' => { + const y = nums.next() orelse return; + const p: Vec = .{ current[0], if (rel) current[1] + y else y }; + try b.lineTo(current, p); + current = p; + }, + 'C' => { + const c1 = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + const c2 = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + const p = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + try b.cubic(.{ current, c1, c2, p }); + last_cubic = c2; + current = p; + }, + 'S' => { + const c1 = if (cubic_before) |c| current * geom.splat(2) - c else current; + const c2 = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + const p = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + try b.cubic(.{ current, c1, c2, p }); + last_cubic = c2; + current = p; + }, + 'Q' => { + const c = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + const p = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + try b.cubic(geom.quad(current, c, p)); + last_quad = c; + current = p; + }, + 'T' => { + const c = if (quad_before) |q| current * geom.splat(2) - q else current; + const p = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + try b.cubic(geom.quad(current, c, p)); + last_quad = c; + current = p; + }, + 'A' => { + const rx = nums.next() orelse return; + const ry = nums.next() orelse return; + const rotation = nums.next() orelse return; + const large = nums.flag() orelse return; + const sweep = nums.flag() orelse return; + const p = base + Vec{ nums.next() orelse return, nums.next() orelse return }; + arcs.clearRetainingCapacity(); + try geom.arc(&arcs, gpa, current, .{ rx, ry }, rotation, large, sweep, p); + for (arcs.items) |c| try b.cubic(c); + current = p; + }, + else => return, + } + } + try b.closeSubpath(false); +} + +test "typst-style use of symbols, transforms and inherited fill" { + var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); + defer arena.deinit(); + const d = try parse(arena.allocator(), + \\ + \\ + \\ + \\ + ); + try std.testing.expectEqual(@as(f32, 20), d.width); + try std.testing.expectEqual(@as(usize, 1), d.shapes.len); + const shape = d.shapes[0]; + try std.testing.expectEqual(Drawing.FillRule.evenodd, shape.style.fill_rule); + try std.testing.expectEqual(Drawing.Color{ 1, 0, 0, 1 }, shape.style.fill.color); + try std.testing.expectEqual(@as(usize, 4), d.cubicsOf(d.subpathsOf(shape)[0]).len); + const corner = shape.transform.apply(d.cubics[0][0]); + try std.testing.expectEqual(geom.vec(6, 7), corner); +} + +test "path data: implicit repeats, relative commands, smooth curves and arcs" { + var arena: std.heap.ArenaAllocator = .init(std.testing.allocator); + defer arena.deinit(); + var b: Drawing.Builder = .init(arena.allocator()); + try pathData(&b, arena.allocator(), "M10-20l5 5 5-5h-1e1s1,2,3,4q1 1 2 0t2 0a5 5 0 1 0 10 0z"); + try std.testing.expectEqual(@as(usize, 1), b.subpaths.items.len); + try std.testing.expect(b.subpaths.items[0].closed); + const cubics = b.cubics.items; + try std.testing.expectEqual(geom.vec(15, -15), cubics[0][3]); + try std.testing.expectEqual(geom.vec(20, -20), cubics[1][3]); + try std.testing.expectEqual(geom.vec(10, -20), cubics[2][3]); + // The first S has no previous curve: its first control is the current point. + try std.testing.expectEqual(geom.vec(10, -20), cubics[3][1]); + try std.testing.expectEqual(geom.vec(13, -16), cubics[3][3]); + var nums = Numbers{ .text = "1.5.5-2e-1" }; + try std.testing.expectEqual(@as(f32, 1.5), nums.next().?); + try std.testing.expectEqual(@as(f32, 0.5), nums.next().?); + try std.testing.expectEqual(@as(f32, -0.2), nums.next().?); +} + +test "colors and lengths" { + try std.testing.expectEqual(Drawing.Color{ 1, 1, 1, 1 }, parseColor("#fff", .{ 0, 0, 0, 1 }).?); + try std.testing.expectEqual(Drawing.Color{ 0, 0.5, 1, 1 }, parseColor("rgb(0, 50%, 255)", .{ 0, 0, 0, 1 }).?); + try std.testing.expectEqual(@as(f32, 20), parseLength("15pt")); + try std.testing.expectEqual(@as(f32, 0.5), parseOpacity("50%")); +} -- cgit v1.3