lib/filigree/src/font/coverage.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2
3 const samples: i32 = 4;
4 const sample_total: u32 = @intCast(samples * samples);
5 const srgb_alpha = [sample_total + 1]u8{
6 0, 71, 99, 120, 137, 152, 165, 177, 188,
7 198, 207, 216, 225, 233, 240, 248, 255,
8 };
9
10 /// Encodes 4x4 linear area coverage as sRGB alpha for light text on a dark surface.
11 pub fn gammaAwareAlpha(covered_samples: u32) u8 {
12 std.debug.assert(covered_samples <= sample_total);
13 return srgb_alpha[@intCast(covered_samples)];
14 }
15
16 pub fn rasterizeAlloc(
17 allocator: std.mem.Allocator,
18 alpha: []u8,
19 width: i32,
20 height: i32,
21 points: anytype,
22 contours: anytype,
23 ) std.mem.Allocator.Error!void {
24 if (points.len == 0) {
25 @memset(alpha, 0);
26 return;
27 }
28 const crossings = try allocator.alloc(f32, try edgeCapacity(points.len, contours));
29 defer allocator.free(crossings);
30
31 var y: i32 = 0;
32 while (y < height) : (y += 1) {
33 const row_start = @as(usize, @intCast(y)) * @as(usize, @intCast(width));
34 const row = alpha[row_start..][0..@intCast(width)];
35 @memset(row, 0);
36
37 var sy: i32 = 0;
38 while (sy < samples) : (sy += 1) {
39 const py = sampleCoordinate(y, sy);
40 const crossing_count = collectCrossings(points, contours, py, crossings);
41 std.mem.sort(f32, crossings[0..crossing_count], {}, crossingLessThan);
42
43 var crossing_index: usize = 0;
44 var x: i32 = 0;
45 while (x < width) : (x += 1) {
46 var sx: i32 = 0;
47 while (sx < samples) : (sx += 1) {
48 const px = sampleCoordinate(x, sx);
49 while (crossing_index < crossing_count and !(px < crossings[crossing_index])) {
50 crossing_index += 1;
51 }
52 if ((crossing_count - crossing_index) & 1 == 1) {
53 row[@intCast(x)] += 1;
54 }
55 }
56 }
57 }
58
59 for (row) |*value| {
60 value.* = gammaAwareAlpha(value.*);
61 }
62 }
63 }
64
65 fn edgeCapacity(points_len: usize, contours: anytype) std.mem.Allocator.Error!usize {
66 var capacity: usize = 0;
67 for (contours) |contour| {
68 if (contour.end <= contour.start or contour.end > points_len) continue;
69 capacity = std.math.add(usize, capacity, contour.end - contour.start) catch return error.OutOfMemory;
70 }
71 return capacity;
72 }
73
74 fn sampleCoordinate(pixel: i32, sample: i32) f32 {
75 return @as(f32, @floatFromInt(pixel)) +
76 (@as(f32, @floatFromInt(sample)) + 0.5) / @as(f32, @floatFromInt(samples));
77 }
78
79 fn collectCrossings(points: anytype, contours: anytype, y: f32, crossings: []f32) usize {
80 var count: usize = 0;
81 for (contours) |contour| {
82 if (contour.end <= contour.start or contour.end > points.len) continue;
83 var previous = contour.end - 1;
84 var current = contour.start;
85 while (current < contour.end) : (current += 1) {
86 const a = points[previous];
87 const b = points[current];
88 if ((a.y > y) != (b.y > y)) {
89 const crossing = (b.x - a.x) * (y - a.y) / (b.y - a.y) + a.x;
90 if (!std.math.isNan(crossing)) {
91 std.debug.assert(count < crossings.len);
92 crossings[count] = crossing;
93 count += 1;
94 }
95 }
96 previous = current;
97 }
98 }
99 return count;
100 }
101
102 fn crossingLessThan(_: void, a: f32, b: f32) bool {
103 return a < b;
104 }
105
106 pub fn rasterizeReference(
107 alpha: []u8,
108 width: i32,
109 height: i32,
110 points: anytype,
111 contours: anytype,
112 ) void {
113 var y: i32 = 0;
114 while (y < height) : (y += 1) {
115 var x: i32 = 0;
116 while (x < width) : (x += 1) {
117 var value: u32 = 0;
118 var sy: i32 = 0;
119 while (sy < samples) : (sy += 1) {
120 var sx: i32 = 0;
121 while (sx < samples) : (sx += 1) {
122 if (containsPoint(points, contours, sampleCoordinate(x, sx), sampleCoordinate(y, sy))) value += 1;
123 }
124 }
125 const index = @as(usize, @intCast(y)) * @as(usize, @intCast(width)) + @as(usize, @intCast(x));
126 alpha[index] = gammaAwareAlpha(value);
127 }
128 }
129 }
130
131 fn containsPoint(points: anytype, contours: anytype, x: f32, y: f32) bool {
132 var inside = false;
133 for (contours) |contour| {
134 if (contour.end <= contour.start or contour.end > points.len) continue;
135 var previous = contour.end - 1;
136 var current = contour.start;
137 while (current < contour.end) : (current += 1) {
138 const a = points[previous];
139 const b = points[current];
140 if ((a.y > y) != (b.y > y)) {
141 const crossing = (b.x - a.x) * (y - a.y) / (b.y - a.y) + a.x;
142 if (x < crossing) inside = !inside;
143 }
144 previous = current;
145 }
146 }
147 return inside;
148 }
149
150 const TestPoint = struct {
151 x: f32,
152 y: f32,
153 };
154
155 const TestContour = struct {
156 start: usize,
157 end: usize,
158 };
159
160 fn linearCoverageAlpha(covered_samples: u32) u8 {
161 return @intCast((covered_samples * 255) / sample_total);
162 }
163
164 fn srgbToLinear(alpha: u8) f64 {
165 const encoded = @as(f64, @floatFromInt(alpha)) / 255.0;
166 if (encoded <= 0.04045) return encoded / 12.92;
167 return std.math.pow(f64, (encoded + 0.055) / 1.055, 2.4);
168 }
169
170 fn referenceGammaAwareAlpha(covered_samples: u32) u8 {
171 const linear = @as(f64, @floatFromInt(covered_samples)) / @as(f64, @floatFromInt(sample_total));
172 const encoded = if (linear > 0.0031308)
173 1.055 * std.math.pow(f64, linear, 1.0 / 2.4) - 0.055
174 else
175 12.92 * linear;
176 return @intFromFloat(@round(encoded * 255.0));
177 }
178
179 fn expectMatchesReference(
180 points: []const TestPoint,
181 contours: []const TestContour,
182 width: i32,
183 height: i32,
184 ) !void {
185 const allocator = std.testing.allocator;
186 const pixel_count = @as(usize, @intCast(width)) * @as(usize, @intCast(height));
187 const expected = try allocator.alloc(u8, pixel_count);
188 defer allocator.free(expected);
189 const actual = try allocator.alloc(u8, pixel_count);
190 defer allocator.free(actual);
191
192 rasterizeReference(expected, width, height, points, contours);
193 try rasterizeAlloc(allocator, actual, width, height, points, contours);
194 try std.testing.expectEqualSlices(u8, expected, actual);
195 }
196
197 test "scanline coverage matches point reference at sample boundaries" {
198 const points = [_]TestPoint{
199 .{ .x = 0.125, .y = 0.125 },
200 .{ .x = 3.875, .y = 0.125 },
201 .{ .x = 3.875, .y = 3.875 },
202 .{ .x = 0.125, .y = 3.875 },
203 };
204 const contours = [_]TestContour{.{ .start = 0, .end = points.len }};
205 try expectMatchesReference(&points, &contours, 5, 5);
206 }
207
208 test "gamma-aware coverage preserves measured light-on-dark stem weight" {
209 var covered_samples: u32 = 0;
210 while (covered_samples <= sample_total) : (covered_samples += 1) {
211 try std.testing.expectEqual(referenceGammaAwareAlpha(covered_samples), gammaAwareAlpha(covered_samples));
212 }
213
214 const stem_profile = [_]u32{ 4, 8, 12, 16, 16, 12, 8, 4 };
215 var before_luminance: f64 = 0;
216 var after_luminance: f64 = 0;
217 for (stem_profile) |coverage| {
218 before_luminance += srgbToLinear(linearCoverageAlpha(coverage));
219 after_luminance += srgbToLinear(gammaAwareAlpha(coverage));
220 }
221 before_luminance /= stem_profile.len;
222 after_luminance /= stem_profile.len;
223 const before_darkness = 1.0 - before_luminance;
224 const after_darkness = 1.0 - after_luminance;
225
226 try std.testing.expectApproxEqAbs(@as(f64, 0.554266776), before_darkness, 0.000001);
227 try std.testing.expectApproxEqAbs(@as(f64, 0.373503260), after_darkness, 0.000001);
228 try std.testing.expectApproxEqAbs(@as(f64, 0.625), after_luminance, 0.002);
229 try std.testing.expect(after_darkness < before_darkness);
230 }
231
232 test "scanline coverage matches point reference for holes and overlaps" {
233 const points = [_]TestPoint{
234 .{ .x = -0.5, .y = -0.5 },
235 .{ .x = 5.5, .y = -0.5 },
236 .{ .x = 5.5, .y = 5.5 },
237 .{ .x = -0.5, .y = 5.5 },
238 .{ .x = 1.375, .y = 1.375 },
239 .{ .x = 1.375, .y = 4.125 },
240 .{ .x = 4.125, .y = 4.125 },
241 .{ .x = 4.125, .y = 1.375 },
242 .{ .x = 2.125, .y = 0.625 },
243 .{ .x = 6.25, .y = 0.625 },
244 .{ .x = 6.25, .y = 3.625 },
245 .{ .x = 2.125, .y = 3.625 },
246 };
247 const contours = [_]TestContour{
248 .{ .start = 0, .end = 4 },
249 .{ .start = 4, .end = 8 },
250 .{ .start = 8, .end = 12 },
251 };
252 try expectMatchesReference(&points, &contours, 7, 6);
253 }
254
255 test "scanline coverage matches point reference for shared and horizontal edges" {
256 const points = [_]TestPoint{
257 .{ .x = 0.125, .y = 2.125 },
258 .{ .x = 2.125, .y = 0.125 },
259 .{ .x = 4.125, .y = 2.125 },
260 .{ .x = 2.125, .y = 4.125 },
261 .{ .x = 4.125, .y = 2.125 },
262 .{ .x = 6.125, .y = 0.125 },
263 .{ .x = 6.125, .y = 4.125 },
264 .{ .x = 4.125, .y = 4.125 },
265 .{ .x = 4.125, .y = 2.125 },
266 };
267 const contours = [_]TestContour{
268 .{ .start = 0, .end = 4 },
269 .{ .start = 4, .end = 9 },
270 .{ .start = 3, .end = 3 },
271 .{ .start = 0, .end = 99 },
272 };
273 try expectMatchesReference(&points, &contours, 7, 5);
274 }
275
276 test "scanline coverage matches point reference for repeated contour ranges" {
277 const points = [_]TestPoint{
278 .{ .x = 0.125, .y = 0.125 },
279 .{ .x = 4.125, .y = 0.125 },
280 .{ .x = 4.125, .y = 4.125 },
281 .{ .x = 0.125, .y = 4.125 },
282 };
283 const contours = [_]TestContour{
284 .{ .start = 0, .end = points.len },
285 .{ .start = 0, .end = points.len },
286 .{ .start = 0, .end = points.len },
287 };
288 try expectMatchesReference(&points, &contours, 5, 5);
289 }
290
291 test "scanline coverage matches point reference for NaN crossings" {
292 const points = [_]TestPoint{
293 .{ .x = 0.125, .y = 0.125 },
294 .{ .x = std.math.nan(f32), .y = 0.125 },
295 .{ .x = 4.125, .y = 4.125 },
296 .{ .x = 0.125, .y = 4.125 },
297 };
298 const contours = [_]TestContour{.{ .start = 0, .end = points.len }};
299 try expectMatchesReference(&points, &contours, 5, 5);
300 }