diff options
Diffstat (limited to 'src/vector/Cpu.zig')
| -rw-r--r-- | src/vector/Cpu.zig | 185 |
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); +} |
