nx_raycast_voxel.nx source
↩ module page · 255 lines · 9479 B
1// nx_raycast_voxel.nx -- DDA voxel ray traversal.
2//
3// Per user 2026-05-19 session 1: "we want to build minecraft
4// equivalent on the lowest possible hardware." THE rendering core
5// for that vision. Digital Differential Analyzer ray traversal walks
6// a ray from camera through nx_tissue voxel grid, returning the
7// first non-empty voxel + distance + which face was hit.
8//
9// Fixed-point math throughout — NO floating point. Per cardinals
10// minimum-hardware-floor + bits-up-exceed-never-match: this primitive
11// runs on Cortex-M0+ (no FPU) without modification.
12//
13// Q14 fixed point: 16384 = 1.0; range ~ -131072 to +131071 (covers
14// 32x32x32 worlds with headroom for camera + direction vectors).
15//
16// Composes:
17// nx_tissue -- the voxel world being traversed
18// nx_palette -- voxel palette indices returned on hit
19// nx_fb_1bpp -- caller renders the hit results into framebuffer
20// nx_metabolism -- raycast is the canonical hot path that
21// metabolism promotes through tier ladder
22//
23// V1 ships:
24// - sealed enum NxRayFace (which face of voxel was hit)
25// - struct NxRay + NxRayHit
26// - cast: DDA walk; returns first non-empty voxel or MISS
27// - normalize_q14: caller-helper to scale a direction to Q14
28
29import "nx_syscalls.nx"
30import "nx_tier.nx"
31import "nx_tissue.nx"
32const NX_MAGIC_2147483647: i64 = 2147483647
33
34const NX_RV_Q14: nx_int = 16384
35
36// ===== Sealed enum: NxRayFace =====================================
37
38const NX_RF_NONE: nx_int = 0
39const NX_RF_X_POS: nx_int = 1
40const NX_RF_X_NEG: nx_int = 2
41const NX_RF_Y_POS: nx_int = 3
42const NX_RF_Y_NEG: nx_int = 4
43const NX_RF_Z_POS: nx_int = 5
44const NX_RF_Z_NEG: nx_int = 6
45const NX_RF_N_FACES: nx_int = 7
46
47// ===== Sealed enum: NxRayVerdict ===================================
48
49const NX_RV_HIT: nx_int = 0
50const NX_RV_MISS: nx_int = 1
51const NX_RV_OUT_OF_BOX: nx_int = 2
52const NX_RV_MAX_STEPS: nx_int = 3
53
54// ===== Struct: NxRay ===============================================
55//
56// Camera origin + direction in Q14 fixed-point. origin is voxel
57// coordinates (integer + Q14 fractional); direction is unit-length
58// Q14 vector.
59
60struct NxRay {
61 origin_x_q14: nx_int,
62 origin_y_q14: nx_int,
63 origin_z_q14: nx_int,
64 dir_x_q14: nx_int,
65 dir_y_q14: nx_int,
66 dir_z_q14: nx_int,
67 max_steps: nx_int,
68}
69
70// ===== Struct: NxRayHit ============================================
71
72struct NxRayHit {
73 hit_x: nx_int,
74 hit_y: nx_int,
75 hit_z: nx_int,
76 palette_idx: nx_int,
77 distance_q14: nx_int,
78 face: nx_int,
79 steps_walked: nx_int,
80}
81
82func nx_rf_is_valid(f: nx_int) -> nx_int {
83 if f < 0 { return 0 }
84 if f >= NX_RF_N_FACES { return 0 }
85 return 1
86}
87
88// ===== _abs_q14 ===================================================
89
90func _abs_q14(x: nx_int) -> nx_int {
91 if x < 0 { return 0 - x }
92 return x
93}
94
95// ===== _sign ======================================================
96
97func _sign(x: nx_int) -> nx_int {
98 if x > 0 { return 1 }
99 if x < 0 { return -1 }
100 return 0
101}
102
103// ===== nx_ray_new ==================================================
104
105func nx_ray_new(origin_x_q14: nx_int, origin_y_q14: nx_int, origin_z_q14: nx_int,
106 dir_x_q14: nx_int, dir_y_q14: nx_int, dir_z_q14: nx_int,
107 max_steps: nx_int) -> *NxRay {
108 let r: *NxRay = (sys_mmap(56)) as *NxRay
109 r.origin_x_q14 = origin_x_q14
110 r.origin_y_q14 = origin_y_q14
111 r.origin_z_q14 = origin_z_q14
112 r.dir_x_q14 = dir_x_q14
113 r.dir_y_q14 = dir_y_q14
114 r.dir_z_q14 = dir_z_q14
115 r.max_steps = max_steps
116 return r
117}
118
119// ===== nx_raycast_voxel ============================================
120//
121// Walk the ray. At each step, take the smallest of (tMaxX, tMaxY,
122// tMaxZ), advance the corresponding voxel coordinate by sign of
123// direction, and increment tMax by tDelta. Stop when tissue lookup
124// returns a non-zero palette index (HIT), when coords exit the
125// tissue volume (OUT_OF_BOX), or when steps exceed max (MAX_STEPS).
126//
127// Returns NxRayHit populated with the hit voxel + face + distance,
128// or all zeros + verdict on MISS / OUT_OF_BOX / MAX_STEPS.
129
130func nx_raycast_voxel(ray: *NxRay, world: *NxTissue, out: *NxRayHit) -> nx_int {
131 // Initial voxel coords: integer part of origin
132 var ix: nx_int = ray.origin_x_q14 / NX_RV_Q14
133 var iy: nx_int = ray.origin_y_q14 / NX_RV_Q14
134 var iz: nx_int = ray.origin_z_q14 / NX_RV_Q14
135
136 let step_x: nx_int = _sign(ray.dir_x_q14)
137 let step_y: nx_int = _sign(ray.dir_y_q14)
138 let step_z: nx_int = _sign(ray.dir_z_q14)
139
140 // tDelta = distance ray travels (in Q14 t) to cross 1 voxel along each axis
141 // tDelta_x = 1.0 / |dir_x| (in Q14 = Q14 / dir scaled appropriately)
142 var t_delta_x: nx_int = 0
143 var t_delta_y: nx_int = 0
144 var t_delta_z: nx_int = 0
145 let adx: nx_int = _abs_q14(ray.dir_x_q14)
146 let ady: nx_int = _abs_q14(ray.dir_y_q14)
147 let adz: nx_int = _abs_q14(ray.dir_z_q14)
148 if adx > 0 { t_delta_x = (NX_RV_Q14 * NX_RV_Q14) / adx }
149 if ady > 0 { t_delta_y = (NX_RV_Q14 * NX_RV_Q14) / ady }
150 if adz > 0 { t_delta_z = (NX_RV_Q14 * NX_RV_Q14) / adz }
151
152 // tMax for each axis: how far the ray must travel (in Q14 t) to
153 // reach the first voxel boundary
154 let frac_x: nx_int = ray.origin_x_q14 - ix * NX_RV_Q14
155 let frac_y: nx_int = ray.origin_y_q14 - iy * NX_RV_Q14
156 let frac_z: nx_int = ray.origin_z_q14 - iz * NX_RV_Q14
157 var t_max_x: nx_int = 0
158 var t_max_y: nx_int = 0
159 var t_max_z: nx_int = 0
160 if step_x > 0 {
161 t_max_x = ((NX_RV_Q14 - frac_x) * t_delta_x) / NX_RV_Q14
162 }
163 if step_x < 0 { t_max_x = (frac_x * t_delta_x) / NX_RV_Q14 }
164 if step_x == 0 { t_max_x = NX_MAGIC_2147483647 } // never crosses
165 if step_y > 0 { t_max_y = ((NX_RV_Q14 - frac_y) * t_delta_y) / NX_RV_Q14 }
166 if step_y < 0 { t_max_y = (frac_y * t_delta_y) / NX_RV_Q14 }
167 if step_y == 0 { t_max_y = NX_MAGIC_2147483647 }
168 if step_z > 0 { t_max_z = ((NX_RV_Q14 - frac_z) * t_delta_z) / NX_RV_Q14 }
169 if step_z < 0 { t_max_z = (frac_z * t_delta_z) / NX_RV_Q14 }
170 if step_z == 0 { t_max_z = NX_MAGIC_2147483647 }
171
172 var steps: nx_int = 0
173 var face: nx_int = NX_RF_NONE
174 var t_at_hit: nx_int = 0
175
176 while steps < ray.max_steps {
177 // Sample current voxel
178 if ix >= 0 {
179 if iy >= 0 {
180 if iz >= 0 {
181 let idx: nx_int = nx_tissue_get(world, ix as nx_size,
182 iy as nx_size, iz as nx_size)
183 if idx > 0 {
184 out.hit_x = ix
185 out.hit_y = iy
186 out.hit_z = iz
187 out.palette_idx = idx
188 out.distance_q14 = t_at_hit
189 out.face = face
190 out.steps_walked = steps
191 return NX_RV_HIT
192 }
193 // idx == -1 means out-of-bounds; bail
194 if idx == -1 {
195 out.steps_walked = steps
196 return NX_RV_OUT_OF_BOX
197 }
198 }
199 }
200 }
201
202 // Step to next voxel
203 if t_max_x < t_max_y {
204 if t_max_x < t_max_z {
205 ix = ix + step_x
206 t_at_hit = t_max_x
207 t_max_x = t_max_x + t_delta_x
208 if step_x > 0 { face = NX_RF_X_NEG }
209 else { face = NX_RF_X_POS }
210 } else {
211 iz = iz + step_z
212 t_at_hit = t_max_z
213 t_max_z = t_max_z + t_delta_z
214 if step_z > 0 { face = NX_RF_Z_NEG }
215 else { face = NX_RF_Z_POS }
216 }
217 } else {
218 if t_max_y < t_max_z {
219 iy = iy + step_y
220 t_at_hit = t_max_y
221 t_max_y = t_max_y + t_delta_y
222 if step_y > 0 { face = NX_RF_Y_NEG }
223 else { face = NX_RF_Y_POS }
224 } else {
225 iz = iz + step_z
226 t_at_hit = t_max_z
227 t_max_z = t_max_z + t_delta_z
228 if step_z > 0 { face = NX_RF_Z_NEG }
229 else { face = NX_RF_Z_POS }
230 }
231 }
232
233 steps = steps + 1
234 }
235
236 out.steps_walked = steps
237 return NX_RV_MAX_STEPS
238}
239
240// ===== nx_ray_hit_face_normal_q14 ==================================
241//
242// Returns the outward normal of the hit face in Q14. Useful for
243// lighting / shading even at 1bpp (face determines brightness).
244
245func nx_ray_hit_face_normal_q14(hit: *NxRayHit, out_nx_q14: *i64,
246 out_ny_q14: *i64, out_nz_q14: *i64) -> nx_int {
247 if hit.face == NX_RF_X_POS { out_nx_q14[0] = NX_RV_Q14; out_ny_q14[0] = 0; out_nz_q14[0] = 0; return 0 }
248 if hit.face == NX_RF_X_NEG { out_nx_q14[0] = -NX_RV_Q14; out_ny_q14[0] = 0; out_nz_q14[0] = 0; return 0 }
249 if hit.face == NX_RF_Y_POS { out_nx_q14[0] = 0; out_ny_q14[0] = NX_RV_Q14; out_nz_q14[0] = 0; return 0 }
250 if hit.face == NX_RF_Y_NEG { out_nx_q14[0] = 0; out_ny_q14[0] = -NX_RV_Q14; out_nz_q14[0] = 0; return 0 }
251 if hit.face == NX_RF_Z_POS { out_nx_q14[0] = 0; out_ny_q14[0] = 0; out_nz_q14[0] = NX_RV_Q14; return 0 }
252 if hit.face == NX_RF_Z_NEG { out_nx_q14[0] = 0; out_ny_q14[0] = 0; out_nz_q14[0] = -NX_RV_Q14; return 0 }
253 out_nx_q14[0] = 0; out_ny_q14[0] = 0; out_nz_q14[0] = 0
254 return 0
255}