nx_bvh.nx source
↩ module page · 333 lines · 11652 B
1// nx_bvh.nx -- axis-aligned bounding volume hierarchy on NxMesh
2// triangles. Top-down median-split build, flat node array.
3//
4// Used by the slicer (plane vs triangle pruning), by support tree
5// generation (ray casts for overhang detection), by mesh repair
6// (find near-duplicate verts via spatial proximity). Composes
7// nx_mesh -- does NOT modify it. Per Cardinal 9 (single
8// responsibility): BVH is a spatial index ON nx_mesh, not part of
9// the mesh itself.
10//
11// Storage:
12// - Flat array of NxBvhNode (64 bytes each)
13// - Per-tri precomputed centroid + AABB in NxBvhTriInfo
14// - Permutation array tri_order: leaf nodes point into tri_order;
15// tri_order[i] is the mesh triangle index
16//
17// Build complexity: O(n log n) expected with median-of-three partition.
18// Real-world worst case on degenerate meshes (all tris colinear on
19// the chosen axis): O(n^2). Acceptable for P0.2b smoke; the
20// Christus is well-distributed and will see expected complexity.
21//
22// Node layout invariant: when an internal node is created, its
23// LEFT child is the very next node in the array (idx + 1) and its
24// RIGHT child is whatever node is allocated after the left subtree
25// completes. Depth-first build maintains this.
26//
27// Per cardinal NISHI_3D_PRINT_ROADMAP ยง2.7: this BVH IS the
28// incremental-slice substrate. Re-slicing on a config change with
29// the same mesh reuses the same BVH; only the slice traversal
30// reruns. That's the slice-time win lever vs OrcaSlicer's per-
31// param-change full re-slice.
32//
33// license_tier: ORIGINAL
34
35import "nx_syscalls.nx"
36import "nx_mesh.nx"
37import "nx_mesh_print_check.nx"
38
39const NX_BVH_LEAF_DEFAULT: i64 = 4
40const NX_BVH_NODE_BYTES: i64 = 64 // 8 i64
41const NX_BVH_TRI_BYTES: i64 = 72 // 9 i64
42
43// ===== node ========================================================
44//
45// Internal node: count = 0, left_or_first = index of left child
46// (right child = left + 1).
47// Leaf node: count > 0, left_or_first = first index into
48// tri_order; leaf owns tri_order[first..first+count].
49
50struct NxBvhNode {
51 mnx: i64, mny: i64, mnz: i64,
52 mxx: i64, mxy: i64, mxz: i64,
53 left_or_first: i64,
54 count: i64,
55}
56
57// ===== per-tri info (precomputed) =================================
58//
59// Centroid is integer divide-by-3 of vertex sum, which loses up to
60// 1 Q14 unit (1/16384 mm = 61 nm) of precision per axis. Far below
61// any FDM nozzle resolution.
62
63struct NxBvhTriInfo {
64 cx: i64, cy: i64, cz: i64,
65 mnx: i64, mny: i64, mnz: i64,
66 mxx: i64, mxy: i64, mxz: i64,
67}
68
69// ===== top-level BVH ===============================================
70
71struct NxBvh {
72 nodes: *u8, // packed NxBvhNode array
73 n_nodes: i64,
74 capacity_nodes: i64,
75 tri_info: *u8, // packed NxBvhTriInfo array
76 tri_order: *i64, // permutation; tri_order[i] = mesh tri idx
77 n_tris: i64,
78}
79
80const NX_BVH_BYTES: i64 = 48
81
82// ===== pointer helpers ============================================
83
84func nx_bvh_node_at(b: *NxBvh, idx: i64) -> *NxBvhNode {
85 return ((b.nodes as i64) + idx * NX_BVH_NODE_BYTES) as *NxBvhNode
86}
87
88func nx_bvh_tri_at(b: *NxBvh, idx: i64) -> *NxBvhTriInfo {
89 return ((b.tri_info as i64) + idx * NX_BVH_TRI_BYTES) as *NxBvhTriInfo
90}
91
92// ===== per-tri precompute ========================================
93
94func nx_bvh_min3(a: i64, b: i64, c: i64) -> i64 {
95 var m: i64 = a
96 if b < m { m = b }
97 if c < m { m = c }
98 return m
99}
100
101func nx_bvh_max3(a: i64, b: i64, c: i64) -> i64 {
102 var m: i64 = a
103 if b > m { m = b }
104 if c > m { m = c }
105 return m
106}
107
108func nx_bvh_compute_tri_info(b: *NxBvh, m: *NxMesh) -> i64 {
109 var ti: i64 = 0
110 while ti < b.n_tris {
111 let v0: i64 = nx_mesh_print_tri_v(m, ti, 0)
112 let v1: i64 = nx_mesh_print_tri_v(m, ti, 1)
113 let v2: i64 = nx_mesh_print_tri_v(m, ti, 2)
114 let x0: i64 = nx_mesh_get_vertex_x(m, v0)
115 let y0: i64 = nx_mesh_get_vertex_y(m, v0)
116 let z0: i64 = nx_mesh_get_vertex_z(m, v0)
117 let x1: i64 = nx_mesh_get_vertex_x(m, v1)
118 let y1: i64 = nx_mesh_get_vertex_y(m, v1)
119 let z1: i64 = nx_mesh_get_vertex_z(m, v1)
120 let x2: i64 = nx_mesh_get_vertex_x(m, v2)
121 let y2: i64 = nx_mesh_get_vertex_y(m, v2)
122 let z2: i64 = nx_mesh_get_vertex_z(m, v2)
123
124 let t: *NxBvhTriInfo = nx_bvh_tri_at(b, ti)
125 t.cx = (x0 + x1 + x2) / 3
126 t.cy = (y0 + y1 + y2) / 3
127 t.cz = (z0 + z1 + z2) / 3
128 t.mnx = nx_bvh_min3(x0, x1, x2)
129 t.mny = nx_bvh_min3(y0, y1, y2)
130 t.mnz = nx_bvh_min3(z0, z1, z2)
131 t.mxx = nx_bvh_max3(x0, x1, x2)
132 t.mxy = nx_bvh_max3(y0, y1, y2)
133 t.mxz = nx_bvh_max3(z0, z1, z2)
134 ti = ti + 1
135 }
136 return 0
137}
138
139// ===== AABB of a range of tris ====================================
140
141func nx_bvh_range_aabb(b: *NxBvh, lo: i64, hi: i64, dst: *NxBvhNode) -> i64 {
142 let t0: *NxBvhTriInfo = nx_bvh_tri_at(b, b.tri_order[lo])
143 var mnx: i64 = t0.mnx
144 var mny: i64 = t0.mny
145 var mnz: i64 = t0.mnz
146 var mxx: i64 = t0.mxx
147 var mxy: i64 = t0.mxy
148 var mxz: i64 = t0.mxz
149 var i: i64 = lo + 1
150 while i < hi {
151 let t: *NxBvhTriInfo = nx_bvh_tri_at(b, b.tri_order[i])
152 if t.mnx < mnx { mnx = t.mnx }
153 if t.mny < mny { mny = t.mny }
154 if t.mnz < mnz { mnz = t.mnz }
155 if t.mxx > mxx { mxx = t.mxx }
156 if t.mxy > mxy { mxy = t.mxy }
157 if t.mxz > mxz { mxz = t.mxz }
158 i = i + 1
159 }
160 dst.mnx = mnx; dst.mny = mny; dst.mnz = mnz
161 dst.mxx = mxx; dst.mxy = mxy; dst.mxz = mxz
162 return 0
163}
164
165// Returns the longest axis (0=x, 1=y, 2=z) for the AABB held in n.
166func nx_bvh_longest_axis(n: *NxBvhNode) -> i64 {
167 let dx: i64 = n.mxx - n.mnx
168 let dy: i64 = n.mxy - n.mny
169 let dz: i64 = n.mxz - n.mnz
170 if dx >= dy {
171 if dx >= dz { return 0 }
172 return 2
173 }
174 if dy >= dz { return 1 }
175 return 2
176}
177
178// Get the centroid value of tri_order[idx] on axis (0=x, 1=y, 2=z).
179func nx_bvh_centroid_on_axis(b: *NxBvh, idx: i64, axis: i64) -> i64 {
180 let t: *NxBvhTriInfo = nx_bvh_tri_at(b, b.tri_order[idx])
181 if axis == 0 { return t.cx }
182 if axis == 1 { return t.cy }
183 return t.cz
184}
185
186func nx_bvh_swap_tri_order(b: *NxBvh, i: i64, j: i64) -> i64 {
187 let tmp: i64 = b.tri_order[i]
188 b.tri_order[i] = b.tri_order[j]
189 b.tri_order[j] = tmp
190 return 0
191}
192
193// Hoare-style partition of tri_order[lo..hi) around the pivot
194// centroid value on `axis`. Returns the split point: indices
195// [lo, split) have centroid <= pivot, [split, hi) have > pivot.
196// Pivot = centroid value at the middle index (median-of-three would
197// be marginally better but adds code; mid-element is fine for
198// reasonably-distributed meshes).
199func nx_bvh_partition_by_axis(b: *NxBvh, lo: i64, hi: i64, axis: i64) -> i64 {
200 let mid_idx: i64 = lo + (hi - lo) / 2
201 let pivot: i64 = nx_bvh_centroid_on_axis(b, mid_idx, axis)
202 var i: i64 = lo
203 var j: i64 = hi - 1
204 while i <= j {
205 while nx_bvh_centroid_on_axis(b, i, axis) < pivot { i = i + 1 }
206 while nx_bvh_centroid_on_axis(b, j, axis) > pivot { j = j - 1 }
207 if i <= j {
208 nx_bvh_swap_tri_order(b, i, j)
209 i = i + 1
210 j = j - 1
211 }
212 }
213 // Ensure non-degenerate split: if everything went left or right,
214 // force a midpoint split to keep recursion finite.
215 if i == lo { i = lo + 1 }
216 if i == hi { i = hi - 1 }
217 return i
218}
219
220// ===== node allocator =============================================
221
222func nx_bvh_alloc_node(b: *NxBvh) -> i64 {
223 if b.n_nodes >= b.capacity_nodes { return -1 }
224 let idx: i64 = b.n_nodes
225 b.n_nodes = b.n_nodes + 1
226 return idx
227}
228
229// ===== recursive build ============================================
230//
231// Builds the subtree covering tri_order[lo..hi) and returns its
232// node index. The node is filled with its AABB; if the range is
233// small enough it becomes a leaf, otherwise it partitions and
234// recurses. leaf_threshold caps the leaf size.
235
236// Fill a PRE-ALLOCATED node at `idx` covering tri_order[lo..hi). Allocates
237// the two child node slots ADJACENTLY (right == left + 1) BEFORE recursing,
238// so the walk's "right child = left_or_first + 1" invariant holds for EVERY
239// internal node -- including those whose left child is itself a multi-node
240// subtree.
241//
242// BUGFIX (2026-06-20): the old build returned each subtree's ROOT index and
243// assumed right == left + 1. That is false whenever the left subtree spans
244// more than one node: depth-first allocation puts right at left + size(left),
245// so the parent aliased a WRONG right child and ORPHANED the real one ->
246// some triangles sliced twice, others never -> non-closing contours on any
247// slanted/curved mesh (pyramid, sphere, sculpts). Axis-aligned cubes hid it
248// by luck (unbalanced splits kept the left child a single leaf).
249func nx_bvh_fill_subtree(b: *NxBvh, idx: i64, lo: i64, hi: i64, leaf_threshold: i64) -> i64 {
250 let node: *NxBvhNode = nx_bvh_node_at(b, idx)
251 nx_bvh_range_aabb(b, lo, hi, node)
252
253 let span: i64 = hi - lo
254 if span <= leaf_threshold {
255 node.left_or_first = lo
256 node.count = span
257 return 0
258 }
259
260 let axis: i64 = nx_bvh_longest_axis(node)
261 let split: i64 = nx_bvh_partition_by_axis(b, lo, hi, axis)
262 let left: i64 = nx_bvh_alloc_node(b)
263 if left < 0 { return -1 }
264 let right: i64 = nx_bvh_alloc_node(b) // == left + 1 (contiguous alloc)
265 if right < 0 { return -1 }
266
267 let nptr: *NxBvhNode = nx_bvh_node_at(b, idx)
268 nptr.left_or_first = left
269 nptr.count = 0
270 if nx_bvh_fill_subtree(b, left, lo, split, leaf_threshold) < 0 { return -1 }
271 if nx_bvh_fill_subtree(b, right, split, hi, leaf_threshold) < 0 { return -1 }
272 return 0
273}
274
275func nx_bvh_build_subtree(b: *NxBvh, lo: i64, hi: i64, leaf_threshold: i64) -> i64 {
276 let root: i64 = nx_bvh_alloc_node(b)
277 if root < 0 { return -1 }
278 nx_bvh_fill_subtree(b, root, lo, hi, leaf_threshold)
279 return root
280}
281
282// ===== public build entries =======================================
283
284// Build a BVH over all triangles in `m` with the given leaf
285// threshold. Returns NULL on alloc failure.
286func nx_bvh_build_with_threshold(m: *NxMesh, leaf_threshold: i64) -> *NxBvh {
287 let b: *NxBvh = (sys_mmap(NX_BVH_BYTES)) as *NxBvh
288 b.n_tris = m.n_tris
289 if b.n_tris <= 0 { return b }
290
291 b.tri_info = sys_mmap(b.n_tris * NX_BVH_TRI_BYTES)
292 b.tri_order = (sys_mmap(b.n_tris * 8)) as *i64
293 b.capacity_nodes = b.n_tris * 2 + 1
294 b.nodes = sys_mmap(b.capacity_nodes * NX_BVH_NODE_BYTES)
295 b.n_nodes = 0
296
297 var i: i64 = 0
298 while i < b.n_tris { b.tri_order[i] = i; i = i + 1 }
299 nx_bvh_compute_tri_info(b, m)
300 nx_bvh_build_subtree(b, 0, b.n_tris, leaf_threshold)
301 return b
302}
303
304func nx_bvh_build(m: *NxMesh) -> *NxBvh {
305 return nx_bvh_build_with_threshold(m, NX_BVH_LEAF_DEFAULT)
306}
307
308// ===== tree walk helpers (used by slicer + smoke) =================
309
310// Sum of count fields across all leaf nodes. Must equal n_tris for
311// a well-formed tree.
312func nx_bvh_total_leaf_count(b: *NxBvh) -> i64 {
313 var sum: i64 = 0
314 var i: i64 = 0
315 while i < b.n_nodes {
316 let n: *NxBvhNode = nx_bvh_node_at(b, i)
317 if n.count > 0 { sum = sum + n.count }
318 i = i + 1
319 }
320 return sum
321}
322
323// Count of leaf nodes (count > 0).
324func nx_bvh_leaf_node_count(b: *NxBvh) -> i64 {
325 var c: i64 = 0
326 var i: i64 = 0
327 while i < b.n_nodes {
328 let n: *NxBvhNode = nx_bvh_node_at(b, i)
329 if n.count > 0 { c = c + 1 }
330 i = i + 1
331 }
332 return c
333}