summaryrefslogtreecommitdiff
path: root/src/vector/Cpu.zig
blob: ac5c6eabdb24812568d4ac0170f46e4c68b165e8 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
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("math");
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);
}