nx_slice_plane.nx source
↩ module page · 377 lines · 14080 B
1// nx_slice_plane.nx -- intersect a triangle mesh with a Z-plane.
2// Returns a flat "segment soup" of 2D line segments (Q14 xy) where
3// each segment is one triangle's intersection with the plane.
4//
5// This IS the slicer kernel. Bridges nx_mesh + nx_bvh + nx_polygon:
6// - nx_bvh walk prunes triangles whose AABB doesn't straddle the
7// plane (the slice-time win lever vs naive O(n_tris) scan)
8// - per-candidate triangle, compute the 0/1/2 line segments the
9// plane intersects
10// - emit segments into a flat soup buffer
11//
12// Polygon assembly (linking endpoint-shared segments into closed
13// contours) is a SEPARATE primitive (nx_slice_contour, P2.2) per
14// Cardinal 9. Slice-plane is one job: mesh -> segment soup.
15//
16// Per cardinal NISHI_3D_PRINT_ROADMAP §2.7 (incremental slice):
17// re-slicing on parameter changes with the same mesh reuses the
18// same BVH; only this kernel re-runs. The win lever vs OrcaSlicer
19// is: BVH-pruned candidates instead of full-mesh sweep, integer-
20// only intersection arithmetic (no per-coord float epsilon drift).
21//
22// Triangle vs plane case analysis (signs s0, s1, s2 of vi.z - plane_z):
23// all same sign (not zero) -> no intersection
24// two same sign, one opposite -> one segment from the two
25// straddled edges
26// exactly one zero, others opposite -> one segment from the
27// on-plane vertex to the
28// straddled edge crossing
29// exactly one zero, others same sign -> degenerate touch, skip
30// exactly two zeros -> the triangle edge IS the
31// segment (already 2D)
32// all three zero -> coplanar tri, emit no
33// segment (caller's slicer
34// handles coplanar surfaces
35// via a separate "horizontal
36// face" pass)
37//
38// Coordinate convention: Q14 fixed-point inherited from nx_mesh.
39//
40// Plane-edge intersection (no overflow in i64 for slicer-scale coords):
41// intersection.x_q14 = va.x + (plane_z - va.z) * (vb.x - va.x)
42// / (vb.z - va.z)
43// Products: (plane_z - va.z) <= 2^23, (vb.x - va.x) <= 2^23, product
44// <= 2^46. Division by (vb.z - va.z) returns Q14-range value. Pure
45// i64 throughout -- no nx_i128 needed.
46//
47// license_tier: ORIGINAL
48
49import "nx_syscalls.nx"
50import "nx_mesh.nx"
51import "nx_mesh_print_check.nx"
52import "nx_bvh.nx"
53
54const NX_SLICE_SEG_STRIDE: i64 = 32 // 4 × i64 per segment (x1,y1,x2,y2)
55
56// ===== sealed-enum verdicts ========================================
57
58const NX_SLICE_OK: i64 = 0
59const NX_SLICE_ERR_NULL_MESH: i64 = 1
60const NX_SLICE_ERR_NULL_BVH: i64 = 2
61const NX_SLICE_ERR_CAPACITY: i64 = 3
62const NX_SLICE_N_VERDICTS: i64 = 4
63
64func nx_slice_verdict_name(v: i64) -> *u8 {
65 if v == NX_SLICE_OK { return "OK" }
66 if v == NX_SLICE_ERR_NULL_MESH { return "NULL_MESH" }
67 if v == NX_SLICE_ERR_NULL_BVH { return "NULL_BVH" }
68 if v == NX_SLICE_ERR_CAPACITY { return "CAPACITY" }
69 return "UNKNOWN"
70}
71
72// ===== segment soup ================================================
73
74struct NxSliceSoup {
75 segments: *u8, // packed (x1, y1, x2, y2) per segment
76 n_segments: i64,
77 capacity: i64,
78 verdict: i64,
79}
80
81const NX_SLICE_SOUP_BYTES: i64 = 32
82
83func nx_slice_soup_new(capacity: i64) -> *NxSliceSoup {
84 let s: *NxSliceSoup = (sys_mmap(NX_SLICE_SOUP_BYTES)) as *NxSliceSoup
85 s.segments = sys_mmap(capacity * NX_SLICE_SEG_STRIDE)
86 s.n_segments = 0
87 s.capacity = capacity
88 s.verdict = NX_SLICE_OK
89 return s
90}
91
92func nx_slice_soup_seg_ptr(s: *NxSliceSoup, i: i64) -> *i64 {
93 return ((s.segments as i64) + i * NX_SLICE_SEG_STRIDE) as *i64
94}
95
96func nx_slice_soup_emit(s: *NxSliceSoup, x1: i64, y1: i64,
97 x2: i64, y2: i64) -> i64 {
98 if s.n_segments >= s.capacity { return -1 }
99 let p: *i64 = nx_slice_soup_seg_ptr(s, s.n_segments)
100 p[0] = x1; p[1] = y1; p[2] = x2; p[3] = y2
101 s.n_segments = s.n_segments + 1
102 return 0
103}
104
105// ===== plane-edge intersection ======================================
106//
107// Returns (x_q14, y_q14) of the point where the edge from va to vb
108// crosses the plane z = plane_z. Caller guarantees va.z != vb.z
109// (signs differ or exactly one is zero).
110//
111// Output written to out[0] = x, out[1] = y.
112
113func nx_slice_edge_at_z(va_x: i64, va_y: i64, va_z: i64,
114 vb_x: i64, vb_y: i64, vb_z: i64,
115 plane_z: i64, out: *i64) -> i64 {
116 // WATERTIGHT FIX: canonicalize the endpoint order so the crossing
117 // point depends ONLY on the unordered edge {a,b} + plane_z, never on
118 // which triangle (traversal direction) computes it. Integer division
119 // truncates toward zero, so va..vb and vb..va round differently by up
120 // to 1 ULP; the contour linker matches endpoints by EXACT equality, so
121 // a 1-ULP split leaves slanted/curved faces with un-linkable segments
122 // (axis-aligned cubes are immune -- their crossings have dx=dy=0).
123 // Picking a deterministic first endpoint (lowest z, then x, then y)
124 // makes both adjacent triangles emit the identical point -> contours
125 // close for arbitrary geometry (pyramids, spheres, sculpted meshes).
126 var ax: i64 = va_x
127 var ay: i64 = va_y
128 var az: i64 = va_z
129 var bx: i64 = vb_x
130 var by: i64 = vb_y
131 var bz: i64 = vb_z
132 var swap: i64 = 0
133 if vb_z < va_z { swap = 1 }
134 if vb_z == va_z { if vb_x < va_x { swap = 1 } }
135 if vb_z == va_z { if vb_x == va_x { if vb_y < va_y { swap = 1 } } }
136 if swap == 1 {
137 ax = vb_x; ay = vb_y; az = vb_z
138 bx = va_x; by = va_y; bz = va_z
139 }
140 let dz: i64 = bz - az
141 // dz == 0 should never happen per caller contract (opposite signs ->
142 // distinct z); defensive:
143 if dz == 0 {
144 out[0] = ax
145 out[1] = ay
146 return -1
147 }
148 let num_z: i64 = plane_z - az
149 let dx: i64 = bx - ax
150 let dy: i64 = by - ay
151 out[0] = ax + (num_z * dx) / dz
152 out[1] = ay + (num_z * dy) / dz
153 return 0
154}
155
156// ===== per-triangle slice ==========================================
157//
158// Given one triangle and a Z-plane, emit 0 or 1 segments into the
159// soup. Skips coplanar-tri and degenerate-touch cases.
160
161func nx_slice_one_tri(m: *NxMesh, ti: i64, plane_z: i64,
162 s: *NxSliceSoup) -> i64 {
163 let v0: i64 = nx_mesh_print_tri_v(m, ti, 0)
164 let v1: i64 = nx_mesh_print_tri_v(m, ti, 1)
165 let v2: i64 = nx_mesh_print_tri_v(m, ti, 2)
166 let x0: i64 = nx_mesh_get_vertex_x(m, v0)
167 let y0: i64 = nx_mesh_get_vertex_y(m, v0)
168 let z0: i64 = nx_mesh_get_vertex_z(m, v0)
169 let x1: i64 = nx_mesh_get_vertex_x(m, v1)
170 let y1: i64 = nx_mesh_get_vertex_y(m, v1)
171 let z1: i64 = nx_mesh_get_vertex_z(m, v1)
172 let x2: i64 = nx_mesh_get_vertex_x(m, v2)
173 let y2: i64 = nx_mesh_get_vertex_y(m, v2)
174 let z2: i64 = nx_mesh_get_vertex_z(m, v2)
175
176 // Signs of (z - plane_z) for each vertex: -1, 0, +1.
177 var s0: i64 = 0
178 if z0 > plane_z { s0 = 1 }
179 if z0 < plane_z { s0 = -1 }
180 var s1: i64 = 0
181 if z1 > plane_z { s1 = 1 }
182 if z1 < plane_z { s1 = -1 }
183 var s2: i64 = 0
184 if z2 > plane_z { s2 = 1 }
185 if z2 < plane_z { s2 = -1 }
186
187 let n_pos: i64 = (s0 == 1) as i64 + (s1 == 1) as i64 + (s2 == 1) as i64
188 let n_neg: i64 = (s0 == -1) as i64 + (s1 == -1) as i64 + (s2 == -1) as i64
189 let n_zero: i64 = 3 - n_pos - n_neg
190
191 // All same sign or all coplanar: no segment.
192 if n_zero == 3 { return 0 }
193 if n_pos == 3 { return 0 }
194 if n_neg == 3 { return 0 }
195 // Single-vertex touch with the other two on the same side =
196 // degenerate point-contact, not a true crossing. Skip.
197 // (n_zero == 2 with one positive or one negative IS a real
198 // on-plane edge -- handled below as the "two coplanar" case.)
199 if n_zero == 1 {
200 if n_pos == 2 { return 0 }
201 if n_neg == 2 { return 0 }
202 }
203
204 // Two vertices coplanar: the connecting triangle edge IS the segment.
205 if n_zero == 2 {
206 // Find the two zero-sign vertices; emit segment between them.
207 var ax: i64 = 0; var ay: i64 = 0
208 var bx: i64 = 0; var by: i64 = 0
209 var got: i64 = 0
210 if s0 == 0 { ax = x0; ay = y0; got = 1 }
211 if s1 == 0 {
212 if got == 0 { ax = x1; ay = y1; got = 1 }
213 if got == 1 { bx = x1; by = y1; got = 2 }
214 }
215 if s2 == 0 {
216 if got == 0 { ax = x2; ay = y2; got = 1 }
217 if got == 1 { bx = x2; by = y2; got = 2 }
218 }
219 if got == 2 {
220 if nx_slice_soup_emit(s, ax, ay, bx, by) != 0 {
221 s.verdict = NX_SLICE_ERR_CAPACITY
222 return -1
223 }
224 }
225 return 0
226 }
227
228 // The general case: produce a segment by intersecting the plane
229 // with the two triangle edges that span opposite signs. An edge
230 // (va, vb) "spans opposite signs" iff sa != sb AND not both zero.
231 // We collect up to two crossing points.
232 let p_ab: *i64 = (sys_mmap(16)) as *i64
233 let p_bc: *i64 = (sys_mmap(16)) as *i64
234 let p_ca: *i64 = (sys_mmap(16)) as *i64
235 var n_pts: i64 = 0
236 let pts: *i64 = (sys_mmap(32)) as *i64
237
238 if s0 != s1 {
239 // Treat zero as "on plane": still a crossing endpoint.
240 if s0 == 0 {
241 pts[n_pts * 2 + 0] = x0
242 pts[n_pts * 2 + 1] = y0
243 n_pts = n_pts + 1
244 }
245 if s1 == 0 {
246 pts[n_pts * 2 + 0] = x1
247 pts[n_pts * 2 + 1] = y1
248 n_pts = n_pts + 1
249 }
250 if s0 != 0 {
251 if s1 != 0 {
252 nx_slice_edge_at_z(x0, y0, z0, x1, y1, z1, plane_z, p_ab)
253 pts[n_pts * 2 + 0] = p_ab[0]
254 pts[n_pts * 2 + 1] = p_ab[1]
255 n_pts = n_pts + 1
256 }
257 }
258 }
259 if s1 != s2 {
260 if s1 == 0 {
261 // already emitted via s0!=s1 if it was zero there too;
262 // re-emit safe (dedup at caller is acceptable).
263 pts[n_pts * 2 + 0] = x1
264 pts[n_pts * 2 + 1] = y1
265 n_pts = n_pts + 1
266 }
267 if s2 == 0 {
268 pts[n_pts * 2 + 0] = x2
269 pts[n_pts * 2 + 1] = y2
270 n_pts = n_pts + 1
271 }
272 if s1 != 0 {
273 if s2 != 0 {
274 nx_slice_edge_at_z(x1, y1, z1, x2, y2, z2, plane_z, p_bc)
275 pts[n_pts * 2 + 0] = p_bc[0]
276 pts[n_pts * 2 + 1] = p_bc[1]
277 n_pts = n_pts + 1
278 }
279 }
280 }
281 if s2 != s0 {
282 if s2 == 0 {
283 pts[n_pts * 2 + 0] = x2
284 pts[n_pts * 2 + 1] = y2
285 n_pts = n_pts + 1
286 }
287 if s0 == 0 {
288 pts[n_pts * 2 + 0] = x0
289 pts[n_pts * 2 + 1] = y0
290 n_pts = n_pts + 1
291 }
292 if s2 != 0 {
293 if s0 != 0 {
294 nx_slice_edge_at_z(x2, y2, z2, x0, y0, z0, plane_z, p_ca)
295 pts[n_pts * 2 + 0] = p_ca[0]
296 pts[n_pts * 2 + 1] = p_ca[1]
297 n_pts = n_pts + 1
298 }
299 }
300 }
301
302 // Normalize: take first two distinct points as the segment.
303 if n_pts >= 2 {
304 let ax: i64 = pts[0]
305 let ay: i64 = pts[1]
306 // Find a second point not equal to the first.
307 var bx: i64 = pts[2]
308 var by: i64 = pts[3]
309 var k: i64 = 2
310 var have_b: i64 = 0
311 if bx != ax { have_b = 1 }
312 if by != ay { have_b = 1 }
313 while have_b == 0 {
314 k = k + 1
315 if k >= n_pts {
316 k = n_pts // exit
317 have_b = 0
318 // No distinct second point; tri touches plane at a
319 // single point (degenerate vertex touch). Skip.
320 return 0
321 }
322 bx = pts[k * 2 + 0]
323 by = pts[k * 2 + 1]
324 if bx != ax { have_b = 1 }
325 if by != ay { have_b = 1 }
326 }
327 if nx_slice_soup_emit(s, ax, ay, bx, by) != 0 {
328 s.verdict = NX_SLICE_ERR_CAPACITY
329 return -1
330 }
331 }
332 return 0
333}
334
335// ===== BVH walk: collect candidate tris that span the plane =======
336//
337// Walks the BVH; for any node whose AABB straddles plane_z, descends.
338// Internal nodes -> recurse on left/right children (children are at
339// node.left_or_first and node.left_or_first + 1 per the depth-first
340// build invariant). Leaf nodes -> for each tri in the leaf, slice
341// it into the soup.
342
343func nx_slice_walk_node(m: *NxMesh, b: *NxBvh, plane_z: i64,
344 node_idx: i64, s: *NxSliceSoup) -> i64 {
345 if s.verdict != NX_SLICE_OK { return -1 }
346 let n: *NxBvhNode = nx_bvh_node_at(b, node_idx)
347 if n.mnz > plane_z { return 0 }
348 if n.mxz < plane_z { return 0 }
349 if n.count > 0 {
350 // Leaf node: tris are tri_order[first..first+count]
351 var k: i64 = 0
352 while k < n.count {
353 let ti: i64 = b.tri_order[n.left_or_first + k]
354 nx_slice_one_tri(m, ti, plane_z, s)
355 k = k + 1
356 }
357 return 0
358 }
359 // Internal: recurse children (left = left_or_first, right = left+1)
360 nx_slice_walk_node(m, b, plane_z, n.left_or_first, s)
361 nx_slice_walk_node(m, b, plane_z, n.left_or_first + 1, s)
362 return 0
363}
364
365// ===== public entry ================================================
366
367func nx_slice_plane(m: *NxMesh, b: *NxBvh, plane_z: i64) -> *NxSliceSoup {
368 // Capacity heuristic: in the worst case every triangle crosses
369 // the plane and produces a segment. Allocate n_tris slots.
370 let cap: i64 = m.n_tris
371 let s: *NxSliceSoup = nx_slice_soup_new(cap)
372 if (m as i64) == 0 { s.verdict = NX_SLICE_ERR_NULL_MESH; return s }
373 if (b as i64) == 0 { s.verdict = NX_SLICE_ERR_NULL_BVH; return s }
374 if b.n_nodes <= 0 { return s } // empty BVH = no work
375 nx_slice_walk_node(m, b, plane_z, 0, s)
376 return s
377}