nx_raster_legacy.nx source
↩ module page · 433 lines · 15372 B
1// nx_raster.nx -- software 2D rasterizer (lines + triangles).
2//
3// Closes the GRAPHICS-PATH gap named in docs/VULKAN_COMPARISON.md.
4// Vulkan / OpenGL / DirectX / Metal all do graphics; we had zero
5// rasterizer until this brick. Pure i64 substrate -- no FPU, no GPU
6// dependency -- runs on every backend including Cortex-M3 with a
7// framebuffer.
8//
9// L2 canonical primitive composing:
10// nx_image.Image (L1 canonical pixel container)
11// nx_loop.LoopVerdict (bounded loops)
12//
13// ===== Algorithms ================================================
14//
15// Lines: Bresenham 1965 (the canonical integer-only rasterizer).
16// Pure integer ops; no division beyond /2 and bit shifts.
17// O(max(dx, dy)) pixels visited.
18//
19// Triangles: edge-function method (Pineda 1988 "A Parallel
20// Algorithm for Polygon Rasterization"). For each
21// triangle vertex pair, compute the 2D cross product
22// (the "edge function") at each pixel; pixel is inside
23// the triangle iff all three edge functions have the
24// same sign. Bounding-box prune to avoid testing the
25// whole framebuffer.
26//
27// Barycentric: the three edge functions ARE the barycentric
28// coordinates (after normalization by triangle area).
29// Free interpolation of per-vertex attributes.
30//
31// ===== Why pure i64 ==============================================
32//
33// Substrate has no FPU yet (compiler I2 parked). All rasterization
34// can be done in i64 with edge functions and barycentric weights
35// scaled to Q10. Subpixel accuracy via fixed-point coordinate input
36// (caller passes coords in Q4 or Q8 if needed; this v1 accepts i64
37// pixel-aligned coordinates).
38//
39// Subpixel coords + perspective-correct attribute interpolation
40// queued for v2.
41//
42// genealogy_id: bresenham_1965_line + pineda_1988_polygon_edge_function +
43// heckbert_1990_fundamentals_of_texture_mapping
44// lineage_id: substrate_raster_v1
45//
46// nx_safety_envelope:
47// intended_use: "Software 2D rasterizer -- lines + triangles
48// for substrate-emitted UI / charts / graphics
49// without GPU dependency"
50// sil_target: SIL2 (UI rendering for safety-relevant
51// displays inherits the rasterizer's
52// correctness; pixel-exact output
53// testable)
54// asil_target: QM
55// dal_target: DAL C
56// evidence: [Bresenham_canonical_line,
57// edge_function_triangle_classical,
58// bit_equal_pixel_output_deterministic,
59// no_FP_in_rasterizer_loop]
60// hazard_register: [bug-tape-OOB-pixel-write-via-bad-vertex,
61// bug-tape-degenerate-triangle-silent-skip,
62// bug-tape-clip-rect-not-applied]
63// residual_risk: "Clipping is caller-pre-supplied; rasterizer
64// does NOT clip to viewport. Callers must
65// intersect geometry with viewport upstream."
66// verdict: NOT_YET_EVALUATED
67
68import "nx_syscalls.nx"
69import "nx_tier.nx"
70import "nx_loop.nx"
71import "nx_image.nx"
72
73// ===== Sealed-enum: RasterVerdict =================================
74
75const NX_RAST_OK: nx_int = 0
76const NX_RAST_ERR_BAD_IMAGE: nx_int = 1
77const NX_RAST_ERR_DEGENERATE: nx_int = 2
78const NX_RAST_N_VERDICTS: nx_int = 3
79
80func nx_rast_verdict_is_valid(v: nx_int) -> nx_int {
81 if v < 0 { return 0 }
82 if v >= NX_RAST_N_VERDICTS { return 0 }
83 return 1
84}
85
86// ===== Bresenham line ==============================================
87//
88// Draws a line from (x0, y0) to (x1, y1) in `img`, setting every
89// pixel on the line to `color`. Out-of-bounds pixels silently
90// clipped via nx_image_set's own clamping.
91
92func _rast_abs(x: nx_int) -> nx_int {
93 if x < 0 { return 0 - x }
94 return x
95}
96
97func nx_rast_line(img: *Image, x0: nx_int, y0: nx_int,
98 x1: nx_int, y1: nx_int, color: nx_int) -> nx_int {
99 var x: nx_int = x0
100 var y: nx_int = y0
101 let dx: nx_int = _rast_abs(x1 - x0)
102 let dy: nx_int = _rast_abs(y1 - y0)
103 var sx: nx_int = 1
104 if x0 > x1 { sx = 0 - 1 }
105 var sy: nx_int = 1
106 if y0 > y1 { sy = 0 - 1 }
107 var err: nx_int = dx - dy
108
109 var iter: nx_int = 0
110 var verdict: nx_int = NX_LOOP_RUNNING
111 let BUDGET: nx_int = dx + dy + 2
112 while verdict == NX_LOOP_RUNNING && iter < BUDGET {
113 nx_image_set(img, x, y, 0, color)
114 if x == x1 {
115 if y == y1 { verdict = NX_LOOP_DONE_EXIT }
116 }
117 if verdict == NX_LOOP_RUNNING {
118 let e2: nx_int = err + err
119 if e2 > 0 - dy {
120 err = err - dy
121 x = x + sx
122 }
123 if e2 < dx {
124 err = err + dx
125 y = y + sy
126 }
127 }
128 iter = iter + 1
129 }
130 return NX_RAST_OK
131}
132
133// ===== Edge function ==============================================
134//
135// edge(a, b, p) = (p.x - a.x)*(b.y - a.y) - (p.y - a.y)*(b.x - a.x)
136//
137// This is the 2D cross product of (b-a) and (p-a). Sign tells us
138// which side of the line ab the point p is on; magnitude is twice
139// the signed area of triangle apb.
140
141func _rast_edge(ax: nx_int, ay: nx_int,
142 bx: nx_int, by: nx_int,
143 px: nx_int, py: nx_int) -> nx_int {
144 return (px - ax) * (by - ay) - (py - ay) * (bx - ax)
145}
146
147// ===== Triangle rasterizer (filled) ===============================
148//
149// Pineda 1988 edge-function method. For each pixel in the bounding
150// box of the triangle, compute three edge functions w0/w1/w2. If
151// all three have the same sign, the pixel is inside.
152//
153// Vertex order: assume counter-clockwise winding (positive area).
154// If the caller provides clockwise winding, the area is negative;
155// we flip the sign-comparison so both windings work.
156
157func nx_rast_triangle(img: *Image,
158 x0: nx_int, y0: nx_int,
159 x1: nx_int, y1: nx_int,
160 x2: nx_int, y2: nx_int,
161 color: nx_int) -> nx_int {
162 // Bounding box, clipped to image.
163 var xmin: nx_int = x0
164 if x1 < xmin { xmin = x1 }
165 if x2 < xmin { xmin = x2 }
166 var xmax: nx_int = x0
167 if x1 > xmax { xmax = x1 }
168 if x2 > xmax { xmax = x2 }
169 var ymin: nx_int = y0
170 if y1 < ymin { ymin = y1 }
171 if y2 < ymin { ymin = y2 }
172 var ymax: nx_int = y0
173 if y1 > ymax { ymax = y1 }
174 if y2 > ymax { ymax = y2 }
175
176 if xmin < 0 { xmin = 0 }
177 if ymin < 0 { ymin = 0 }
178 if xmax >= img.width { xmax = img.width - 1 }
179 if ymax >= img.height { ymax = img.height - 1 }
180
181 // Twice-signed area; if zero the triangle is degenerate.
182 let area: nx_int = _rast_edge(x0, y0, x1, y1, x2, y2)
183 if area == 0 { return NX_RAST_ERR_DEGENERATE }
184
185 var py: nx_int = ymin
186 var y_iter: nx_int = 0
187 var y_verdict: nx_int = NX_LOOP_RUNNING
188 let Y_BUDGET: nx_int = (ymax - ymin) + 1
189 while y_verdict == NX_LOOP_RUNNING && y_iter < Y_BUDGET {
190 var px: nx_int = xmin
191 var x_iter: nx_int = 0
192 var x_verdict: nx_int = NX_LOOP_RUNNING
193 let X_BUDGET: nx_int = (xmax - xmin) + 1
194 while x_verdict == NX_LOOP_RUNNING && x_iter < X_BUDGET {
195 let w0: nx_int = _rast_edge(x1, y1, x2, y2, px, py)
196 let w1: nx_int = _rast_edge(x2, y2, x0, y0, px, py)
197 let w2: nx_int = _rast_edge(x0, y0, x1, y1, px, py)
198 // Both windings: pixel is inside iff w0, w1, w2 all have
199 // the same sign as area.
200 var inside: nx_int = 0
201 if area > 0 {
202 if w0 >= 0 {
203 if w1 >= 0 {
204 if w2 >= 0 { inside = 1 }
205 }
206 }
207 }
208 if area < 0 {
209 if w0 <= 0 {
210 if w1 <= 0 {
211 if w2 <= 0 { inside = 1 }
212 }
213 }
214 }
215 if inside == 1 {
216 nx_image_set(img, px, py, 0, color)
217 }
218 px = px + 1
219 x_iter = x_iter + 1
220 }
221 py = py + 1
222 y_iter = y_iter + 1
223 }
224 return NX_RAST_OK
225}
226
227// ===== Barycentric interpolation ==================================
228//
229// Given a triangle ABC with per-vertex i64 attributes attr_a /
230// attr_b / attr_c, returns the interpolated attribute at point
231// (px, py) inside the triangle. Returns the Q10 average per the
232// barycentric weights.
233//
234// Caller checks inside-ness separately (or uses
235// nx_rast_triangle_attributed below which does the inside test
236// itself).
237
238func nx_rast_barycentric_attr(x0: nx_int, y0: nx_int, attr_a: i64,
239 x1: nx_int, y1: nx_int, attr_b: i64,
240 x2: nx_int, y2: nx_int, attr_c: i64,
241 px: nx_int, py: nx_int) -> i64 {
242 let area: nx_int = _rast_edge(x0, y0, x1, y1, x2, y2)
243 if area == 0 { return 0 }
244 let w0: nx_int = _rast_edge(x1, y1, x2, y2, px, py)
245 let w1: nx_int = _rast_edge(x2, y2, x0, y0, px, py)
246 let w2: nx_int = _rast_edge(x0, y0, x1, y1, px, py)
247 return (w0 * attr_a + w1 * attr_b + w2 * attr_c) / area
248}
249
250// ===== Triangle with per-vertex shading ==========================
251//
252// Fills the triangle and interpolates a Q10 colour value across
253// pixels using barycentric weights. v1 supports a single
254// "intensity" attribute per vertex (0..255 grayscale). Per-vertex
255// RGB queued.
256
257func nx_rast_triangle_shaded(img: *Image,
258 x0: nx_int, y0: nx_int, c_a: nx_int,
259 x1: nx_int, y1: nx_int, c_b: nx_int,
260 x2: nx_int, y2: nx_int, c_c: nx_int) -> nx_int {
261 var xmin: nx_int = x0
262 if x1 < xmin { xmin = x1 }
263 if x2 < xmin { xmin = x2 }
264 var xmax: nx_int = x0
265 if x1 > xmax { xmax = x1 }
266 if x2 > xmax { xmax = x2 }
267 var ymin: nx_int = y0
268 if y1 < ymin { ymin = y1 }
269 if y2 < ymin { ymin = y2 }
270 var ymax: nx_int = y0
271 if y1 > ymax { ymax = y1 }
272 if y2 > ymax { ymax = y2 }
273 if xmin < 0 { xmin = 0 }
274 if ymin < 0 { ymin = 0 }
275 if xmax >= img.width { xmax = img.width - 1 }
276 if ymax >= img.height { ymax = img.height - 1 }
277
278 let area: nx_int = _rast_edge(x0, y0, x1, y1, x2, y2)
279 if area == 0 { return NX_RAST_ERR_DEGENERATE }
280
281 var py: nx_int = ymin
282 var y_iter: nx_int = 0
283 var y_verdict: nx_int = NX_LOOP_RUNNING
284 let Y_BUDGET: nx_int = (ymax - ymin) + 1
285 while y_verdict == NX_LOOP_RUNNING && y_iter < Y_BUDGET {
286 var px: nx_int = xmin
287 var x_iter: nx_int = 0
288 var x_verdict: nx_int = NX_LOOP_RUNNING
289 let X_BUDGET: nx_int = (xmax - xmin) + 1
290 while x_verdict == NX_LOOP_RUNNING && x_iter < X_BUDGET {
291 let w0: nx_int = _rast_edge(x1, y1, x2, y2, px, py)
292 let w1: nx_int = _rast_edge(x2, y2, x0, y0, px, py)
293 let w2: nx_int = _rast_edge(x0, y0, x1, y1, px, py)
294 var inside: nx_int = 0
295 if area > 0 {
296 if w0 >= 0 {
297 if w1 >= 0 {
298 if w2 >= 0 { inside = 1 }
299 }
300 }
301 }
302 if area < 0 {
303 if w0 <= 0 {
304 if w1 <= 0 {
305 if w2 <= 0 { inside = 1 }
306 }
307 }
308 }
309 if inside == 1 {
310 let c_interp: i64 = (w0 * c_a + w1 * c_b + w2 * c_c) / area
311 nx_image_set(img, px, py, 0, c_interp)
312 }
313 px = px + 1
314 x_iter = x_iter + 1
315 }
316 py = py + 1
317 y_iter = y_iter + 1
318 }
319 return NX_RAST_OK
320}
321
322// ===== Self-test ==================================================
323//
324// Closed-form invariants:
325//
326// (a) Line from (0,0) to (4,0) marks 5 pixels along y=0
327// (b) Line from (0,0) to (0,4) marks 5 pixels along x=0
328// (c) Diagonal line from (0,0) to (4,4) marks the diagonal
329// (d) Triangle at known coords sets its interior pixels
330// (e) Degenerate triangle (collinear) returns ERR_DEGENERATE
331// (f) Barycentric: at vertex A the interpolated attribute = A
332// (g) Verdict gate
333
334func main() -> i64 {
335 let W: nx_int = 16
336 let H: nx_int = 16
337 let img: *Image = nx_image_alloc(W, H, 1)
338
339 // Zero the framebuffer first.
340 var i: nx_int = 0
341 while i < H {
342 var j: nx_int = 0
343 while j < W { nx_image_set(img, j, i, 0, 0); j = j + 1 }
344 i = i + 1
345 }
346
347 // --- (a) Horizontal line ---
348 nx_rast_line(img, 0, 0, 4, 0, 200)
349 var c: nx_int = 0
350 while c <= 4 {
351 if nx_image_get(img, c, 0, 0) != 200 { return 10 + c }
352 c = c + 1
353 }
354
355 // --- (b) Vertical line ---
356 nx_rast_line(img, 0, 0, 0, 4, 150)
357 var r: nx_int = 1
358 while r <= 4 {
359 if nx_image_get(img, 0, r, 0) != 150 { return 20 + r }
360 r = r + 1
361 }
362
363 // --- (c) Diagonal ---
364 var cc: nx_int = 0
365 while cc < H {
366 var cj: nx_int = 0
367 while cj < W { nx_image_set(img, cj, cc, 0, 0); cj = cj + 1 }
368 cc = cc + 1
369 }
370 nx_rast_line(img, 0, 0, 4, 4, 100)
371 var d: nx_int = 0
372 while d <= 4 {
373 if nx_image_get(img, d, d, 0) != 100 { return 30 + d }
374 d = d + 1
375 }
376
377 // --- (d) Right triangle (0,0)-(8,0)-(0,8) ---
378 // CCW order so area > 0. Pixel (1,1) is inside.
379 // Pixel (8,8) is outside.
380 var cc2: nx_int = 0
381 while cc2 < H {
382 var cj2: nx_int = 0
383 while cj2 < W { nx_image_set(img, cj2, cc2, 0, 0); cj2 = cj2 + 1 }
384 cc2 = cc2 + 1
385 }
386 let v_tri: nx_int = nx_rast_triangle(img, 0, 0, 8, 0, 0, 8, 99)
387 if v_tri != NX_RAST_OK { return 40 }
388 if nx_image_get(img, 1, 1, 0) != 99 { return 41 }
389 if nx_image_get(img, 0, 0, 0) != 99 { return 42 } // corner
390 if nx_image_get(img, 8, 8, 0) != 0 { return 43 } // outside
391 if nx_image_get(img, 9, 0, 0) != 0 { return 44 } // outside x
392
393 // --- (e) Degenerate triangle (collinear points) ---
394 let v_deg: nx_int = nx_rast_triangle(img, 0, 0, 4, 0, 8, 0, 50)
395 if v_deg != NX_RAST_ERR_DEGENERATE { return 50 }
396
397 // --- (f) Barycentric: at vertex A, attribute should == A's ---
398 // Triangle (0,0; 4,0; 0,4) with attrs (100, 200, 50).
399 // At (0,0) interpolated value should be 100 +/- 1.
400 let bary: i64 = nx_rast_barycentric_attr(
401 0, 0, 100,
402 4, 0, 200,
403 0, 4, 50,
404 0, 0)
405 if bary < 99 { return 60 }
406 if bary > 101 { return 61 }
407
408 // --- (g) Shaded triangle smoke ---
409 var cc3: nx_int = 0
410 while cc3 < H {
411 var cj3: nx_int = 0
412 while cj3 < W { nx_image_set(img, cj3, cc3, 0, 0); cj3 = cj3 + 1 }
413 cc3 = cc3 + 1
414 }
415 let v_sh: nx_int = nx_rast_triangle_shaded(img,
416 0, 0, 100,
417 8, 0, 200,
418 0, 8, 50)
419 if v_sh != NX_RAST_OK { return 70 }
420 // Vertex A: shaded value at (0,0) ≈ 100.
421 let a_val: nx_int = nx_image_get(img, 0, 0, 0)
422 if a_val < 99 { return 71 }
423 if a_val > 101 { return 72 }
424
425 // --- (h) Verdict gate ---
426 var vi: nx_int = 0
427 while vi < NX_RAST_N_VERDICTS {
428 if nx_rast_verdict_is_valid(vi) != 1 { return 80 + vi }
429 vi = vi + 1
430 }
431
432 return 0
433}