summaryrefslogtreecommitdiff
path: root/src/vector/Cpu.zig
diff options
context:
space:
mode:
Diffstat (limited to 'src/vector/Cpu.zig')
-rw-r--r--src/vector/Cpu.zig185
1 files changed, 185 insertions, 0 deletions
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);
+}