nx_mesh_print_check.nx source
↩ module page · 171 lines · 6643 B
1// nx_mesh_print_check.nx -- printability checks on the L1 canonical
2// NxMesh (defined in nx_mesh.nx). Adds:
3// - axis-aligned bounding box computation
4// - watertight / 2-manifold edge check
5// - tetrahedron factory (smallest non-degenerate closed mesh, for
6// smokes and calibration tests)
7//
8// Composes nx_mesh.nx -- does NOT modify the L1 container. Per
9// cardinal feedback-DRY-through-shared-libraries: extend at the
10// primitive boundary, do not fork the canonical mesh.
11//
12// Why split from nx_mesh.nx:
13// nx_mesh is the canonical L1 graphics primitive (used by
14// nx_raster, nx_voxel_mesh, nx_render_pass). Manifold / bbox /
15// printability are FDM-print-specific predicates. Keeping them
16// in a sibling primitive prevents graphics callers from pulling
17// print-only dependencies.
18//
19// Per cardinal NISHI_3D_PRINT_ROADMAP §2.1+2.2: a watertight,
20// closed manifold mesh is a hard precondition for any slicer that
21// claims to EXCEED OrcaSlicer's tree-support / adaptive-Z handling.
22// Non-manifold meshes cascade into ambiguous slice contours.
23// Detect at the boundary (Cardinal 12), not deep in the slicer.
24//
25// Coordinate convention: inherits nx_mesh's Q14 fixed-point xyz.
26// 1 Q14 unit = 1/16384. Tetrahedron factory takes a unit-edge
27// length and scales to Q14 internally.
28//
29// Manifold check algorithm (O(t²) for P0.1):
30// In a watertight orientable 2-manifold, every undirected edge
31// appears in EXACTLY two triangles, with opposite winding (one
32// sees a->b, the other sees b->a). For each directed edge
33// emitted by triangle T, find the reverse-direction edge in
34// some OTHER triangle. Reverse count must equal 1 for every
35// directed edge. O(t²) is fine for P0.1 smokes (tetrahedron =
36// 4 tris); P0.2 swaps in a hashed-edge O(t) impl for the
37// Christus (~200K tris).
38//
39// license_tier: ORIGINAL
40
41import "nx_syscalls.nx"
42import "nx_mesh.nx"
43
44// ===== bbox =========================================================
45
46struct NxMeshBBox {
47 min_x: i64, min_y: i64, min_z: i64,
48 max_x: i64, max_y: i64, max_z: i64,
49 valid: i64,
50}
51
52const NX_MESH_BBOX_BYTES: i64 = 56
53
54func nx_mesh_bbox_compute(m: *NxMesh) -> *NxMeshBBox {
55 let bb: *NxMeshBBox = (sys_mmap(NX_MESH_BBOX_BYTES)) as *NxMeshBBox
56 bb.valid = 0
57 if m.n_verts <= 0 { return bb }
58
59 var mnx: i64 = nx_mesh_get_vertex_x(m, 0)
60 var mny: i64 = nx_mesh_get_vertex_y(m, 0)
61 var mnz: i64 = nx_mesh_get_vertex_z(m, 0)
62 var mxx: i64 = mnx
63 var mxy: i64 = mny
64 var mxz: i64 = mnz
65 var i: nx_int = 1
66 while i < m.n_verts {
67 let x: i64 = nx_mesh_get_vertex_x(m, i)
68 let y: i64 = nx_mesh_get_vertex_y(m, i)
69 let z: i64 = nx_mesh_get_vertex_z(m, i)
70 if x < mnx { mnx = x }
71 if y < mny { mny = y }
72 if z < mnz { mnz = z }
73 if x > mxx { mxx = x }
74 if y > mxy { mxy = y }
75 if z > mxz { mxz = z }
76 i = i + 1
77 }
78 bb.min_x = mnx; bb.min_y = mny; bb.min_z = mnz
79 bb.max_x = mxx; bb.max_y = mxy; bb.max_z = mxz
80 bb.valid = 1
81 return bb
82}
83
84// ===== manifold check ==============================================
85
86const NX_MESH_PRINT_OK: i64 = 0
87const NX_MESH_PRINT_ERR_NOT_MANIFOLD: i64 = 1
88const NX_MESH_PRINT_ERR_NONE_TRIS: i64 = 2
89
90// Read triangle vertex index. k in [0,1,2].
91func nx_mesh_print_tri_v(m: *NxMesh, ti: nx_int, k: i64) -> i64 {
92 return m.indices[ti * NX_MESH_IDX_STRIDE + k]
93}
94
95// Count occurrences of directed edge (va -> vb) across all triangles
96// EXCEPT exclude_tri. Returns the count.
97func nx_mesh_print_dir_edge_count(m: *NxMesh, va: i64, vb: i64, exclude_tri: nx_int) -> i64 {
98 var count: i64 = 0
99 var ti: nx_int = 0
100 while ti < m.n_tris {
101 if ti != exclude_tri {
102 let v0: i64 = nx_mesh_print_tri_v(m, ti, 0)
103 let v1: i64 = nx_mesh_print_tri_v(m, ti, 1)
104 let v2: i64 = nx_mesh_print_tri_v(m, ti, 2)
105 if v0 == va { if v1 == vb { count = count + 1 } }
106 if v1 == va { if v2 == vb { count = count + 1 } }
107 if v2 == va { if v0 == vb { count = count + 1 } }
108 }
109 ti = ti + 1
110 }
111 return count
112}
113
114// Returns NX_MESH_PRINT_OK if every directed edge has exactly one
115// reverse-direction partner in another triangle.
116func nx_mesh_is_manifold(m: *NxMesh) -> i64 {
117 if m.n_tris <= 0 { return NX_MESH_PRINT_ERR_NONE_TRIS }
118 var ti: nx_int = 0
119 while ti < m.n_tris {
120 let v0: i64 = nx_mesh_print_tri_v(m, ti, 0)
121 let v1: i64 = nx_mesh_print_tri_v(m, ti, 1)
122 let v2: i64 = nx_mesh_print_tri_v(m, ti, 2)
123 // For each directed edge of this CCW triangle, the REVERSE
124 // edge (vb -> va) must appear exactly once in some other tri.
125 if nx_mesh_print_dir_edge_count(m, v1, v0, ti) != 1 { return NX_MESH_PRINT_ERR_NOT_MANIFOLD }
126 if nx_mesh_print_dir_edge_count(m, v2, v1, ti) != 1 { return NX_MESH_PRINT_ERR_NOT_MANIFOLD }
127 if nx_mesh_print_dir_edge_count(m, v0, v2, ti) != 1 { return NX_MESH_PRINT_ERR_NOT_MANIFOLD }
128 ti = ti + 1
129 }
130 return NX_MESH_PRINT_OK
131}
132
133// ===== tetrahedron factory =========================================
134//
135// Standard simplex with vertices at (0,0,0), (1,0,0), (0,1,0), (0,0,1).
136// Outward winding from the centroid (~0.25, 0.25, 0.25). Smallest
137// non-degenerate closed mesh in R³; perfect for manifold-check smoke.
138//
139// `edge_q14` = edge length along each axis in Q14 units. Pass
140// 16384 for a unit cube's worth (1.0).
141//
142// Vertex indices:
143// 0 = (0, 0, 0) origin
144// 1 = (edge_q14, 0, 0) +x
145// 2 = (0, edge_q14, 0) +y
146// 3 = (0, 0, edge_q14) +z
147//
148// Triangle winding (CCW when viewed from OUTSIDE the tetrahedron):
149// T0: v1, v2, v3 far face (normal ~ +x +y +z)
150// T1: v0, v3, v2 x = 0 face (normal ~ -x)
151// T2: v0, v1, v3 y = 0 face (normal ~ -y)
152// T3: v0, v2, v1 z = 0 face (normal ~ -z)
153//
154// Each undirected edge is shared by exactly two triangles, opposite
155// winding -> manifold-check passes.
156
157func nx_mesh_make_tetrahedron(edge_q14: i64, color: i64) -> *NxMesh {
158 let m: *NxMesh = nx_mesh_alloc(4, 4, 0)
159 if (m as i64) == 0 { return m }
160
161 nx_mesh_set_vertex(m, 0, 0, 0, 0, color)
162 nx_mesh_set_vertex(m, 1, edge_q14, 0, 0, color)
163 nx_mesh_set_vertex(m, 2, 0, edge_q14, 0, color)
164 nx_mesh_set_vertex(m, 3, 0, 0, edge_q14, color)
165
166 nx_mesh_set_triangle(m, 0, 1, 2, 3)
167 nx_mesh_set_triangle(m, 1, 0, 3, 2)
168 nx_mesh_set_triangle(m, 2, 0, 1, 3)
169 nx_mesh_set_triangle(m, 3, 0, 2, 1)
170 return m
171}