//! 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); }