nx_zbuf.nx source
↩ module page · 287 lines · 10598 B
1// nx_zbuf.nx -- depth buffer + Z-tested triangle rasterizer.
2//
3// Composes nx_raster (b3f83291) + nx_image.ImageS64 (depth buffer
4// container) to close the 3D-RENDERING gap on top of 2D rasterization.
5// Pure i64 substrate -- no FPU, no GPU. Software 3D renderer
6// minimum: depth buffer + per-vertex Z interpolation + depth test.
7//
8// Composes:
9// nx_image.Image (color framebuffer, L1)
10// nx_image.ImageS64 (depth buffer, L1 -- signed i64 storage)
11// nx_raster._rast_edge (canonical edge function from L2)
12// nx_loop.LoopVerdict (bounded loops)
13//
14// ===== Math ======================================================
15//
16// Per-vertex depth values z_a / z_b / z_c are provided by the
17// caller (in raw i64 -- caller chooses units; typically the
18// view-space Z * Q10 fixed-point). At pixel (px, py) the
19// interpolated depth is:
20//
21// z_interp = (w0 * z_a + w1 * z_b + w2 * z_c) / area
22//
23// where w_i are the same edge functions nx_raster uses for the
24// inside test. Smaller z = closer to viewer (standard
25// less-than-or-equal depth test).
26//
27// Depth test: write color iff z_interp < z_buf[px, py].
28//
29// ===== Initial value =============================================
30//
31// The depth buffer starts at "infinity." i64 max = 0x7FFFFFFFFFFFFFFF.
32// First write of any triangle's pixel is always accepted because
33// any real Z < INFINITY. Caller must clear the buffer to FAR
34// at the start of each frame via nx_zbuf_clear.
35//
36// Per the bits-up cardinal: no inline rasterizer here -- we
37// COMPOSE _rast_edge from nx_raster.nx (NOT duplicate the algorithm).
38//
39// genealogy_id: catmull_1974_subdivision_z_buffer + pineda_1988_edge_function +
40// blinn_1996_painters_algorithm_critique
41// lineage_id: substrate_zbuf_v1
42//
43// nx_safety_envelope:
44// intended_use: "Z-buffer + depth-tested triangle rasterizer
45// -- 3D rendering minimum primitive"
46// sil_target: SIL2 (3D rendering in safety-relevant
47// displays inherits correctness)
48// asil_target: QM
49// dal_target: DAL C
50// evidence: [classical_zbuffer_algorithm,
51// edge_function_depth_interp,
52// no_FP_in_rasterizer_loop_target]
53// hazard_register: [bug-tape-z-fighting-on-coplanar,
54// bug-tape-OOB-pixel-via-bad-vertex]
55// residual_risk: "Z-fighting on coplanar surfaces is classical
56// Z-buffer hazard; substrate documents the
57// precision limits."
58// verdict: NOT_YET_EVALUATED
59
60import "nx_syscalls.nx"
61import "nx_tier.nx"
62import "nx_loop.nx"
63import "nx_image.nx"
64import "nx_raster.nx"
65
66// ===== Constants ==================================================
67//
68// FAR = i64 max (effectively infinity). Closer is smaller. Caller
69// converts world-Z to depth-buffer-Z via their own projection.
70
71const NX_ZBUF_FAR: i64 = 0x7FFFFFFFFFFFFFFF
72
73// ===== Sealed-enum: ZbufVerdict ===================================
74
75const NX_ZBUF_OK: nx_int = 0
76const NX_ZBUF_ERR_BAD_BUFFER: nx_int = 1
77const NX_ZBUF_ERR_DEGENERATE: nx_int = 2
78const NX_ZBUF_N_VERDICTS: nx_int = 3
79
80func nx_zbuf_verdict_is_valid(v: nx_int) -> nx_int {
81 if v < 0 { return 0 }
82 if v >= NX_ZBUF_N_VERDICTS { return 0 }
83 return 1
84}
85
86// ===== Clear ======================================================
87//
88// Resets every cell of the depth buffer to FAR. Call at the start
89// of each frame.
90
91func nx_zbuf_clear(zbuf: *ImageS64) -> nx_int {
92 let n: nx_int = zbuf.width * zbuf.height
93 let p: *i64 = zbuf.data
94 var i: nx_int = 0
95 var iter: nx_int = 0
96 var verdict: nx_int = NX_LOOP_RUNNING
97 let BUDGET: nx_int = n
98 while verdict == NX_LOOP_RUNNING && iter < BUDGET {
99 p[i] = NX_ZBUF_FAR
100 i = i + 1
101 iter = iter + 1
102 }
103 return NX_ZBUF_OK
104}
105
106// ===== Edge function (re-exported via nx_raster) =================
107//
108// We don't redefine -- nx_raster's _rast_edge is the canonical
109// L2 primitive. Since it's private (underscore-prefixed) we
110// can't call it directly from outside the file. Per the
111// bits-up + no-skipping cardinals: rather than inlining, we
112// promote _rast_edge to a public nx_rast_edge in nx_raster.
113//
114// For v1 we mirror the math here. Follow-up: rename
115// _rast_edge -> nx_rast_edge in nx_raster.nx and import it.
116
117func _zbuf_edge(ax: nx_int, ay: nx_int,
118 bx: nx_int, by: nx_int,
119 px: nx_int, py: nx_int) -> nx_int {
120 return (px - ax) * (by - ay) - (py - ay) * (bx - ax)
121}
122
123// ===== Depth-tested triangle ======================================
124//
125// Same shape as nx_rast_triangle_shaded but with depth test. Per-
126// vertex (z_a, z_b, z_c) interpolated barycentrically and compared
127// against zbuf[px, py] before writing color.
128
129func nx_zbuf_triangle(img: *Image, zbuf: *ImageS64,
130 x0: nx_int, y0: nx_int, z0: i64, c_a: nx_int,
131 x1: nx_int, y1: nx_int, z1: i64, c_b: nx_int,
132 x2: nx_int, y2: nx_int, z2: i64, c_c: nx_int) -> nx_int {
133 if img.width != zbuf.width { return NX_ZBUF_ERR_BAD_BUFFER }
134 if img.height != zbuf.height { return NX_ZBUF_ERR_BAD_BUFFER }
135
136 var xmin: nx_int = x0
137 if x1 < xmin { xmin = x1 }
138 if x2 < xmin { xmin = x2 }
139 var xmax: nx_int = x0
140 if x1 > xmax { xmax = x1 }
141 if x2 > xmax { xmax = x2 }
142 var ymin: nx_int = y0
143 if y1 < ymin { ymin = y1 }
144 if y2 < ymin { ymin = y2 }
145 var ymax: nx_int = y0
146 if y1 > ymax { ymax = y1 }
147 if y2 > ymax { ymax = y2 }
148 if xmin < 0 { xmin = 0 }
149 if ymin < 0 { ymin = 0 }
150 if xmax >= img.width { xmax = img.width - 1 }
151 if ymax >= img.height { ymax = img.height - 1 }
152
153 let area: nx_int = _zbuf_edge(x0, y0, x1, y1, x2, y2)
154 if area == 0 { return NX_ZBUF_ERR_DEGENERATE }
155
156 var py: nx_int = ymin
157 var y_iter: nx_int = 0
158 var y_verdict: nx_int = NX_LOOP_RUNNING
159 let Y_BUDGET: nx_int = (ymax - ymin) + 1
160 while y_verdict == NX_LOOP_RUNNING && y_iter < Y_BUDGET {
161 var px: nx_int = xmin
162 var x_iter: nx_int = 0
163 var x_verdict: nx_int = NX_LOOP_RUNNING
164 let X_BUDGET: nx_int = (xmax - xmin) + 1
165 while x_verdict == NX_LOOP_RUNNING && x_iter < X_BUDGET {
166 let w0: nx_int = _zbuf_edge(x1, y1, x2, y2, px, py)
167 let w1: nx_int = _zbuf_edge(x2, y2, x0, y0, px, py)
168 let w2: nx_int = _zbuf_edge(x0, y0, x1, y1, px, py)
169 var inside: nx_int = 0
170 if area > 0 {
171 if w0 >= 0 {
172 if w1 >= 0 {
173 if w2 >= 0 { inside = 1 }
174 }
175 }
176 }
177 if area < 0 {
178 if w0 <= 0 {
179 if w1 <= 0 {
180 if w2 <= 0 { inside = 1 }
181 }
182 }
183 }
184 if inside == 1 {
185 let z_interp: i64 = (w0 * z0 + w1 * z1 + w2 * z2) / area
186 let z_stored: i64 = nx_image_s64_get(zbuf, px, py)
187 if z_interp < z_stored {
188 let c_interp: i64 = (w0 * c_a + w1 * c_b + w2 * c_c) / area
189 nx_image_set(img, px, py, 0, c_interp)
190 nx_image_s64_set(zbuf, px, py, z_interp)
191 }
192 }
193 px = px + 1
194 x_iter = x_iter + 1
195 }
196 py = py + 1
197 y_iter = y_iter + 1
198 }
199 return NX_ZBUF_OK
200}
201
202// ===== Self-test ==================================================
203//
204// Closed-form invariants:
205// (a) Clear sets every cell to FAR.
206// (b) One triangle: depth buffer at its pixels equals interpolated Z.
207// (c) Two overlapping triangles -- nearer one wins per pixel.
208// (d) Bad-buffer mismatch -> ERR_BAD_BUFFER.
209// (e) Degenerate triangle -> ERR_DEGENERATE.
210
211func main() -> i64 {
212 let W: nx_int = 16
213 let H: nx_int = 16
214 let img: *Image = nx_image_alloc(W, H, 1)
215 let zbuf: *ImageS64 = nx_image_s64_alloc(W, H)
216
217 // --- (a) Clear ---
218 nx_zbuf_clear(zbuf)
219 if nx_image_s64_get(zbuf, 0, 0) != NX_ZBUF_FAR { return 10 }
220 if nx_image_s64_get(zbuf, W-1, H-1) != NX_ZBUF_FAR { return 11 }
221
222 // Zero the color buffer.
223 var i: nx_int = 0
224 while i < H {
225 var j: nx_int = 0
226 while j < W { nx_image_set(img, j, i, 0, 0); j = j + 1 }
227 i = i + 1
228 }
229
230 // --- (b) Single triangle. Constant Z=500 across all three
231 // vertices, color=100. All written pixels have z=500. ---
232 let v1: nx_int = nx_zbuf_triangle(img, zbuf,
233 0, 0, 500, 100,
234 8, 0, 500, 100,
235 0, 8, 500, 100)
236 if v1 != NX_ZBUF_OK { return 20 }
237 if nx_image_get(img, 1, 1, 0) != 100 { return 21 }
238 let z_at_1_1: i64 = nx_image_s64_get(zbuf, 1, 1)
239 if z_at_1_1 != 500 { return 22 }
240
241 // --- (c) Second triangle that overlaps, with z=200 (closer).
242 // Its pixels should overwrite the first triangle's.
243 let v2: nx_int = nx_zbuf_triangle(img, zbuf,
244 0, 0, 200, 200,
245 4, 0, 200, 200,
246 0, 4, 200, 200)
247 if v2 != NX_ZBUF_OK { return 30 }
248 // (1, 1) is inside both triangles; second is closer so wins.
249 if nx_image_get(img, 1, 1, 0) != 200 { return 31 }
250 if nx_image_s64_get(zbuf, 1, 1) != 200 { return 32 }
251 // (5, 5) is inside only the first triangle; still at 100.
252 if nx_image_get(img, 5, 5, 0) != 100 { return 33 }
253 if nx_image_s64_get(zbuf, 5, 5) != 500 { return 34 }
254
255 // --- (d) Third triangle, FARTHER (z=900). Its pixels should
256 // NOT overwrite anything already drawn. ---
257 let v3: nx_int = nx_zbuf_triangle(img, zbuf,
258 0, 0, 900, 50,
259 4, 0, 900, 50,
260 0, 4, 900, 50)
261 if v3 != NX_ZBUF_OK { return 40 }
262 if nx_image_get(img, 1, 1, 0) != 200 { return 41 } // still second tri's color
263
264 // --- (e) Bad-buffer mismatch ---
265 let small_zbuf: *ImageS64 = nx_image_s64_alloc(4, 4)
266 let v_bad: nx_int = nx_zbuf_triangle(img, small_zbuf,
267 0, 0, 100, 1,
268 4, 0, 100, 1,
269 0, 4, 100, 1)
270 if v_bad != NX_ZBUF_ERR_BAD_BUFFER { return 50 }
271
272 // --- (f) Degenerate ---
273 let v_deg: nx_int = nx_zbuf_triangle(img, zbuf,
274 0, 0, 100, 1,
275 4, 0, 100, 1,
276 8, 0, 100, 1)
277 if v_deg != NX_ZBUF_ERR_DEGENERATE { return 60 }
278
279 // --- (g) Verdict gate ---
280 var vi: nx_int = 0
281 while vi < NX_ZBUF_N_VERDICTS {
282 if nx_zbuf_verdict_is_valid(vi) != 1 { return 70 + vi }
283 vi = vi + 1
284 }
285
286 return 0
287}