nx_meshvalid_lib.nx source
↩ module page · 367 lines · 15341 B
1// nx_meshvalid_lib.nx -- THE MESH VALIDITY REFEREE: it REFUSES a broken asset instead of shipping it.
2// /compare/dcc DC3, and it is the tooth the retopology and sculpt rungs both bind their claims to.
3//
4// WHY THIS AND NOT AN OVERLAY. Blender, ZBrush and Maya all SHOW mesh problems to an artist in a viewport
5// overlay; none of them REFUSES on one, because a person is always there to look. An estate that emits
6// assets from rules with no person in the loop needs the opposite: a named count, the offending element
7// index, and a non-zero verdict. nx_spendgate found no incumbent -- nx_meshgen BUILDS watertight meshes by
8// construction (surface nets) and nx_step_tess2 tessellates with hole bridging, but nothing in the estate
9// VALIDATES a mesh it did not itself produce, which is exactly the case an importer creates.
10//
11// EVERY DEFECT IS ITS OWN NAMED CLASS, never a single boolean. A compound assertion that will not name its
12// failing conjunct is a false-alarm generator: the reader always guesses the alarming one. Six classes,
13// each with a count AND a first-offender index, and a manifold verdict composed from them.
14//
15// COMPLEXITY IS DECLARED, NOT DISCOVERED. Edge and vertex identity both go through an open-addressing hash
16// table whose capacity is DERIVED from the input size (next power of two at or above four times the element
17// count, a load factor at or below one quarter), so the check is linear in triangles rather than the
18// quadratic pairwise scan the naive version would be. There is no fixed table size to outgrow and no cap to
19// silently hit. All integer: the zero-area test is an exact cross product, never a float epsilon, so
20// DEGENERATE here means exactly degenerate rather than nearly so.
21// 100% sovereign. No hardware writes (Rule 26). license_tier: ORIGINAL
22import "nx_syscalls.nx"
23
24const MV_H_NV: i64 = 0
25const MV_H_NT: i64 = 1
26const MV_H_ECAP: i64 = 2
27const MV_H_VCAP: i64 = 3
28const MV_H_ERR: i64 = 4
29const MV_H_RAN: i64 = 5
30// THE HEADER MUST OUTRANK THE HIGHEST FIRST-OFFENDER SLOT, AND THE FIRST DRAFT DID NOT.
31// Each counter at slot S keeps its first-offender at S + MV_FIRST_STRIDE, so the highest header word in use
32// is MV_C_DUPV + MV_FIRST_STRIDE = 19. With MV_HDR at 16 the vertex array began at word 16, so slots 16..19
33// ALIASED vertices 0 and 1: mv_check's own reset loop wrote -1 over v0's coordinates on entry, silently
34// MOVING a vertex. Every topology class still passed (a moved corner is still a valid tetrahedron), and the
35// only visible symptom was that the duplicate-vertex detector could never fire -- the gate caught it as
36// FAIL [VACUOUS: did not fire on the bad input], which is precisely the tooth that class of bug needs.
37// A structural invariant tooth now asserts this relation so it cannot regress in silence.
38const MV_HDR: i64 = 24
39const MV_I64: i64 = 8
40
41// counter slots, and each has a paired first-offender slot 8 above it
42const MV_C_DEGEN: i64 = 6
43const MV_C_INDEX: i64 = 7
44const MV_C_NONMAN: i64 = 8
45const MV_C_BOUND: i64 = 9
46const MV_C_WIND: i64 = 10
47const MV_C_DUPV: i64 = 11
48const MV_FIRST_STRIDE: i64 = 8
49
50const MV_OK: i64 = 0
51const MV_E_INDEX: i64 = 0 - 1
52const MV_E_DEGEN: i64 = 0 - 2
53const MV_E_NONMAN: i64 = 0 - 3
54const MV_E_BOUND: i64 = 0 - 4
55const MV_E_WIND: i64 = 0 - 5
56const MV_E_DUPV: i64 = 0 - 6
57const MV_E_ARGS: i64 = 0 - 7
58const MV_E_NOTRUN: i64 = 0 - 8
59
60// PUBLISHED multipliers, named rather than inlined: the FNV-1a 64-bit prime and Knuth's multiplicative
61// constant (2^32 divided by the golden ratio). Two independent multipliers so the two key words do not
62// cancel each other in the mix.
63const MV_MUL_A: i64 = 1099511628211
64const MV_MUL_B: i64 = 2654435761
65const MV_LOAD_NUM: i64 = 4
66
67// table record: [key0, key1, count, balance]
68const MV_TREC: i64 = 4
69const MV_T_K0: i64 = 0
70const MV_T_K1: i64 = 1
71const MV_T_CNT: i64 = 2
72const MV_T_BAL: i64 = 3
73const MV_EMPTY: i64 = 0 - 999999999
74
75// GEOMETRY LAYOUT, NAMED ONCE. Before this block a bare literal 3 stood for FOUR unrelated things in this
76// file -- components per vertex, vertices per triangle, edges contributed per triangle, and the balance
77// field of the record above -- and a bare 2 for three more. One constant serving several unrelated purposes
78// can never be tuned for any of them, and each of those sites was a second copy of a layout that existed
79// only in a comment: reorder or widen either record and every bare offset still compiles and still reads a
80// word, just the wrong one, with no diagnostic anywhere.
81const MV_VCOMP: i64 = 3 // components per vertex: [x, y, z]
82const MV_VX: i64 = 0
83const MV_VY: i64 = 1
84const MV_VZ: i64 = 2
85const MV_TVERT: i64 = 3 // vertices per triangle: [a, b, c] -- and a triangle contributes exactly
86 // this many EDGES, which is why the edge table is sized from it
87const MV_TA: i64 = 0
88const MV_TB: i64 = 1
89const MV_TC: i64 = 2
90
91// A MANIFOLD EDGE IS SHARED BY EXACTLY TWO FACES, and a boundary edge by one. That is the definition of a
92// two-manifold surface rather than a threshold anyone may tune, and it was previously spelled as a bare 1
93// and a bare 2 in the single place the whole topology verdict is decided.
94const MV_BOUNDARY_FACES: i64 = 1
95const MV_MANIFOLD_FACES: i64 = 2
96
97// Folds x and y into one key word ahead of the two published multipliers, so that (x,y) and (y,x) do not
98// collide. Any small factor other than 1 serves; the value carries no other meaning and is named here so it
99// is not mistaken for the vertex stride it happens to equal.
100const MV_VKEY_FOLD: i64 = 3
101
102func mv_err_name(e: i64) -> *u8 {
103 if e == MV_OK { return "VALID" as *u8 }
104 if e == MV_E_INDEX { return "REFUSED-TRIANGLE-INDEX-OUT-OF-RANGE" as *u8 }
105 if e == MV_E_DEGEN { return "REFUSED-DEGENERATE-TRIANGLE" as *u8 }
106 if e == MV_E_NONMAN { return "REFUSED-NON-MANIFOLD-EDGE" as *u8 }
107 if e == MV_E_BOUND { return "REFUSED-BOUNDARY-EDGE-HOLE" as *u8 }
108 if e == MV_E_WIND { return "REFUSED-INCONSISTENT-WINDING" as *u8 }
109 if e == MV_E_DUPV { return "REFUSED-DUPLICATE-VERTEX" as *u8 }
110 if e == MV_E_ARGS { return "REFUSED-BAD-ARGUMENTS" as *u8 }
111 if e == MV_E_NOTRUN { return "REFUSED-CHECK-NOT-RUN" as *u8 }
112 return "REFUSED-UNCLASSIFIED" as *u8
113}
114
115// next power of two at or above n*MV_LOAD_NUM. Derived from the input, so there is no table size to tune.
116func mv_cap_for(n: i64) -> i64 {
117 var want: i64 = n * MV_LOAD_NUM
118 if want < MV_LOAD_NUM { want = MV_LOAD_NUM }
119 var c: i64 = 1
120 while c < want { c = c + c }
121 return c
122}
123
124func mv_verts_off(m: *i64) -> i64 { return MV_HDR }
125func mv_tris_off(m: *i64) -> i64 { return MV_HDR + m[MV_H_NV] * MV_VCOMP }
126func mv_etab_off(m: *i64) -> i64 { return MV_HDR + m[MV_H_NV] * MV_VCOMP + m[MV_H_NT] * MV_TVERT }
127func mv_vtab_off(m: *i64) -> i64 { return mv_etab_off(m) + m[MV_H_ECAP] * MV_TREC }
128
129func mv_words_for(nv: i64, nt: i64, ecap: i64, vcap: i64) -> i64 {
130 return MV_HDR + nv * MV_VCOMP + nt * MV_TVERT + ecap * MV_TREC + vcap * MV_TREC
131}
132
133func mv_new(nv: i64, nt: i64) -> *i64 {
134 if nv <= 0 { return 0 as *i64 }
135 if nt <= 0 { return 0 as *i64 }
136 let ecap: i64 = mv_cap_for(nt * MV_TVERT)
137 let vcap: i64 = mv_cap_for(nv)
138 let m: *i64 = sys_mmap(mv_words_for(nv, nt, ecap, vcap) * MV_I64) as *i64
139 m[MV_H_NV] = nv
140 m[MV_H_NT] = nt
141 m[MV_H_ECAP] = ecap
142 m[MV_H_VCAP] = vcap
143 m[MV_H_ERR] = MV_E_NOTRUN
144 m[MV_H_RAN] = 0
145 return m
146}
147
148func mv_set_vert(m: *i64, i: i64, x: i64, y: i64, z: i64) -> i64 {
149 if i < 0 { return MV_E_ARGS }
150 if i >= m[MV_H_NV] { return MV_E_ARGS }
151 let o: i64 = mv_verts_off(m) + i * MV_VCOMP
152 m[o + MV_VX] = x
153 m[o + MV_VY] = y
154 m[o + MV_VZ] = z
155 return MV_OK
156}
157
158func mv_set_tri(m: *i64, i: i64, a: i64, b: i64, c: i64) -> i64 {
159 if i < 0 { return MV_E_ARGS }
160 if i >= m[MV_H_NT] { return MV_E_ARGS }
161 let o: i64 = mv_tris_off(m) + i * MV_TVERT
162 m[o + MV_TA] = a
163 m[o + MV_TB] = b
164 m[o + MV_TC] = c
165 return MV_OK
166}
167
168func mv_count(m: *i64, slot: i64) -> i64 {
169 if slot < MV_C_DEGEN { return 0 - 1 }
170 if slot > MV_C_DUPV { return 0 - 1 }
171 return m[slot]
172}
173// the offending element index for a class, or -1 when that class is clean. A count without a worklist is
174// not actionable, and one offender is the smallest worklist that still names something.
175func mv_first(m: *i64, slot: i64) -> i64 {
176 if slot < MV_C_DEGEN { return 0 - 1 }
177 if slot > MV_C_DUPV { return 0 - 1 }
178 if m[slot] == 0 { return 0 - 1 }
179 return m[slot + MV_FIRST_STRIDE]
180}
181
182func mv_bump(m: *i64, slot: i64, idx: i64) -> i64 {
183 if m[slot] == 0 { m[slot + MV_FIRST_STRIDE] = idx }
184 m[slot] = m[slot] + 1
185 return 0
186}
187
188func mv_mix(a: i64, b: i64, cap: i64) -> i64 {
189 var h: i64 = a * MV_MUL_A + b * MV_MUL_B
190 if h < 0 { h = 0 - h }
191 if h < 0 { h = 0 }
192 return h % cap
193}
194
195// Insert or find the undirected edge (a,b). dir is +1 when the triangle traverses low->high, -1 otherwise.
196// Returns the slot index. Linear probing; the table cannot fill because capacity is derived at 4x.
197func mv_edge_touch(m: *i64, a: i64, b: i64, dir: i64) -> i64 {
198 var lo: i64 = a
199 var hi: i64 = b
200 if lo > hi { lo = b; hi = a }
201 let cap: i64 = m[MV_H_ECAP]
202 let base: i64 = mv_etab_off(m)
203 var s: i64 = mv_mix(lo, hi, cap)
204 var guard: i64 = 0
205 while guard < cap {
206 let o: i64 = base + s * MV_TREC
207 if m[o + MV_T_CNT] == 0 {
208 m[o + MV_T_K0] = lo
209 m[o + MV_T_K1] = hi
210 m[o + MV_T_CNT] = 1
211 m[o + MV_T_BAL] = dir
212 return s
213 }
214 if m[o + MV_T_K0] == lo {
215 if m[o + MV_T_K1] == hi {
216 m[o + MV_T_CNT] = m[o + MV_T_CNT] + 1
217 m[o + MV_T_BAL] = m[o + MV_T_BAL] + dir
218 return s
219 }
220 }
221 s = s + 1
222 if s >= cap { s = 0 }
223 guard = guard + 1
224 }
225 return 0 - 1
226}
227
228// Vertex identity by exact coordinates. Stores index+1 so that 0 reads as empty.
229func mv_vert_touch(m: *i64, i: i64) -> i64 {
230 let vo: i64 = mv_verts_off(m) + i * MV_VCOMP
231 let x: i64 = m[vo + MV_VX]
232 let y: i64 = m[vo + MV_VY]
233 let z: i64 = m[vo + MV_VZ]
234 let cap: i64 = m[MV_H_VCAP]
235 let base: i64 = mv_vtab_off(m)
236 var s: i64 = mv_mix(x * MV_VKEY_FOLD + y, z, cap)
237 var guard: i64 = 0
238 while guard < cap {
239 let o: i64 = base + s * MV_TREC
240 if m[o + MV_T_CNT] == 0 {
241 m[o + MV_T_K0] = i
242 m[o + MV_T_CNT] = i + 1
243 return 0
244 }
245 let j: i64 = m[o + MV_T_K0]
246 let jo: i64 = mv_verts_off(m) + j * MV_VCOMP
247 var same: i64 = 1
248 if m[jo + MV_VX] != x { same = 0 }
249 if m[jo + MV_VY] != y { same = 0 }
250 if m[jo + MV_VZ] != z { same = 0 }
251 if same == 1 { return 1 }
252 s = s + 1
253 if s >= cap { s = 0 }
254 guard = guard + 1
255 }
256 return 0
257}
258
259// exact integer cross product of (b-a) x (c-a); zero vector means the three points are collinear, which
260// includes the repeated-index case. No epsilon, so this is exact rather than nearly exact.
261func mv_is_degenerate(m: *i64, a: i64, b: i64, c: i64) -> i64 {
262 let vo: i64 = mv_verts_off(m)
263 let ax: i64 = m[vo + a * MV_VCOMP + MV_VX]
264 let ay: i64 = m[vo + a * MV_VCOMP + MV_VY]
265 let az: i64 = m[vo + a * MV_VCOMP + MV_VZ]
266 let ux: i64 = m[vo + b * MV_VCOMP + MV_VX] - ax
267 let uy: i64 = m[vo + b * MV_VCOMP + MV_VY] - ay
268 let uz: i64 = m[vo + b * MV_VCOMP + MV_VZ] - az
269 let wx: i64 = m[vo + c * MV_VCOMP + MV_VX] - ax
270 let wy: i64 = m[vo + c * MV_VCOMP + MV_VY] - ay
271 let wz: i64 = m[vo + c * MV_VCOMP + MV_VZ] - az
272 let cx: i64 = uy * wz - uz * wy
273 let cy: i64 = uz * wx - ux * wz
274 let cz: i64 = ux * wy - uy * wx
275 if cx != 0 { return 0 }
276 if cy != 0 { return 0 }
277 if cz != 0 { return 0 }
278 return 1
279}
280
281// THE REFEREE. Runs every class, counts them all rather than stopping at the first, and only then composes
282// a verdict -- because an author needs the whole worklist, not the first thing that went wrong.
283func mv_check(m: *i64) -> i64 {
284 let nv: i64 = m[MV_H_NV]
285 let nt: i64 = m[MV_H_NT]
286 let to: i64 = mv_tris_off(m)
287 var s: i64 = MV_C_DEGEN
288 while s <= MV_C_DUPV { m[s] = 0; m[s + MV_FIRST_STRIDE] = 0 - 1; s = s + 1 }
289
290 // pass 1: index range. Everything downstream dereferences these, so it must run first and alone.
291 var t: i64 = 0
292 while t < nt {
293 var k: i64 = 0
294 while k < MV_TVERT {
295 let v: i64 = m[to + t * MV_TVERT + k]
296 if v < 0 { mv_bump(m, MV_C_INDEX, t) } else { if v >= nv { mv_bump(m, MV_C_INDEX, t) } }
297 k = k + 1
298 }
299 t = t + 1
300 }
301 if m[MV_C_INDEX] > 0 {
302 m[MV_H_RAN] = 1
303 m[MV_H_ERR] = MV_E_INDEX
304 return MV_E_INDEX
305 }
306
307 // pass 2: degeneracy and edge accumulation
308 t = 0
309 while t < nt {
310 let a: i64 = m[to + t * MV_TVERT + MV_TA]
311 let b: i64 = m[to + t * MV_TVERT + MV_TB]
312 let c: i64 = m[to + t * MV_TVERT + MV_TC]
313 if mv_is_degenerate(m, a, b, c) == 1 { mv_bump(m, MV_C_DEGEN, t) }
314 var d1: i64 = 1
315 if a > b { d1 = 0 - 1 }
316 var d2: i64 = 1
317 if b > c { d2 = 0 - 1 }
318 var d3: i64 = 1
319 if c > a { d3 = 0 - 1 }
320 mv_edge_touch(m, a, b, d1)
321 mv_edge_touch(m, b, c, d2)
322 mv_edge_touch(m, c, a, d3)
323 t = t + 1
324 }
325
326 // pass 3: read the edge table once. count 1 = a hole, count > 2 = non-manifold, count 2 with a non-zero
327 // direction balance = the two faces traverse the shared edge the same way, i.e. inconsistent winding.
328 let ecap: i64 = m[MV_H_ECAP]
329 let ebase: i64 = mv_etab_off(m)
330 var e: i64 = 0
331 while e < ecap {
332 let o: i64 = ebase + e * MV_TREC
333 let cnt: i64 = m[o + MV_T_CNT]
334 if cnt == MV_BOUNDARY_FACES { mv_bump(m, MV_C_BOUND, m[o + MV_T_K0]) }
335 if cnt > MV_MANIFOLD_FACES { mv_bump(m, MV_C_NONMAN, m[o + MV_T_K0]) }
336 if cnt == MV_MANIFOLD_FACES { if m[o + MV_T_BAL] != 0 { mv_bump(m, MV_C_WIND, m[o + MV_T_K0]) } }
337 e = e + 1
338 }
339
340 // pass 4: duplicate vertices by exact coordinate
341 var i: i64 = 0
342 while i < nv {
343 if mv_vert_touch(m, i) == 1 { mv_bump(m, MV_C_DUPV, i) }
344 i = i + 1
345 }
346
347 m[MV_H_RAN] = 1
348 // ORDER IS THE SEVERITY ORDER, and it is deliberate: a degenerate triangle makes every edge claim about
349 // it meaningless, so it outranks the topology classes.
350 if m[MV_C_DEGEN] > 0 { m[MV_H_ERR] = MV_E_DEGEN; return MV_E_DEGEN }
351 if m[MV_C_NONMAN] > 0 { m[MV_H_ERR] = MV_E_NONMAN; return MV_E_NONMAN }
352 if m[MV_C_BOUND] > 0 { m[MV_H_ERR] = MV_E_BOUND; return MV_E_BOUND }
353 if m[MV_C_WIND] > 0 { m[MV_H_ERR] = MV_E_WIND; return MV_E_WIND }
354 if m[MV_C_DUPV] > 0 { m[MV_H_ERR] = MV_E_DUPV; return MV_E_DUPV }
355 m[MV_H_ERR] = MV_OK
356 return MV_OK
357}
358
359// 1 only for a closed, orientable, manifold surface with no duplicate vertices. ABSTAINS rather than
360// acquits when the check has not been run: a verdict that cannot distinguish clean from unexamined is a lie.
361func mv_manifold(m: *i64) -> i64 {
362 if m[MV_H_RAN] == 0 { return 0 - 1 }
363 if m[MV_H_ERR] == MV_OK { return 1 }
364 return 0
365}
366
367func mv_verdict(m: *i64) -> i64 { return m[MV_H_ERR] }