nx_meshcheck.nx source

1// nx_meshcheck.nx -- MESH INTEGRITY, the check nothing in this estate performed. 2// 3// WHAT THIS IS AND WHY IT IS MISSING-SHAPED. The estate GENERATES meshes -- surface nets from SDFs, 4// layered bodies, skulls, faces -- and measures them for SHAPE AGREEMENT against a reference 5// (nx_mmdev_lib md_measure, exact per-vertex deviation) and for anatomical plausibility. Nothing 6// asks the prior question: IS THIS MESH STRUCTURALLY WELL-FORMED AT ALL. A mesh can sit perfectly 7// on its reference and still have inverted winding on a third of its faces, an edge shared by three 8// triangles, or four hundred vertices no triangle references -- and every one of those shows up to 9// the eye as junk while every ruler we own reports agreement. 10// 11// THE ONE PRIOR CHECK, AND WHY IT IS NOT ENOUGH. nx_faceanat_mesh_gate carries a WATERTIGHT tooth 12// using the Euler characteristic: for a closed genus-0 triangle mesh V = F/2 + 2, tested within a 13// tolerance of F/16. That is a real check and it is NECESSARY, NOT SUFFICIENT, for two reasons the 14// tooth itself cannot see. First, Euler is a SINGLE SCALAR over the whole surface, so compensating 15// defects cancel: punch a hole and add a handle and the characteristic is unchanged. Second, it is 16// computed on ONE subject inside ONE gate, so it is a tooth rather than a ruler -- no other mesh in 17// the estate is ever asked. This organ counts the actual incidences instead, which is the direct 18// measurement Euler is a proxy for. 19// 20// EVERY DEFECT CLASS IS COUNTED SEPARATELY AND CARRIES A WORKLIST. A single is-it-broken boolean is 21// not actionable, and two defect classes with opposite remedies must never share a counter: a 22// boundary edge means the surface is OPEN, a three-face edge means it is NON-MANIFOLD, and an 23// inconsistently wound pair means the surface is CLOSED but its normals disagree. Those are three 24// different repairs. Each class reports its count AND the first offenders by index, and says so when 25// that list is a PREFIX rather than the whole set. 26// 27// PURE INTEGER, NO FLOAT ANYWHERE. Coordinates are caller-defined integer units (micrometres is the 28// estate's habit). The area test is an exact integer cross product, so a degenerate triangle is 29// PROVEN degenerate rather than declared so by an epsilon somebody picked. 30// license_tier: ORIGINAL No hardware writes (Rule 26). Reads buffers, opens nothing. 31import "nx_syscalls.nx" 32 33const MC_I64: i64 = 8 34const MC_LIST_MAX: i64 = 32 // offenders NAMED per class; beyond this the list is a declared PREFIX 35 36// A triangle-key packs three vertex indices into one i64 as ((lo*nv)+mid)*nv+hi, so nv is bounded by 37// the cube root of the i64 range. DERIVED, not picked: 2097151^3 < 2^63. Above it the duplicate-face 38// check REFUSES rather than silently skipping, because a check that quietly does not run is worse 39// than one that says it could not. 40const MC_TRIKEY_MAX_NV: i64 = 2097151 41 42// ---- verdicts ------------------------------------------------------------------------------------ 43const MC_CLEAN: i64 = 0 44const MC_DEFECTS: i64 = 1 45const MC_UNMEASURABLE: i64 = 3 // no faces or no vertices: an empty mesh is not a clean mesh 46const MC_INVALID: i64 = 4 // an index out of range: nothing further can be trusted 47 48// ---- out slots ----------------------------------------------------------------------------------- 49const MC_O_VERTS: i64 = 0 50const MC_O_TRIS: i64 = 1 51const MC_O_EDGES: i64 = 2 // distinct undirected edges 52const MC_O_BADINDEX: i64 = 3 // triangles referencing a vertex outside [0,nv) 53const MC_O_DEGEN_TOPO: i64 = 4 // a triangle naming the same vertex twice 54const MC_O_DEGEN_AREA: i64 = 5 // three distinct vertices that are collinear: exact zero cross product 55const MC_O_LOOSE: i64 = 6 // vertices no triangle references 56const MC_O_BOUNDARY: i64 = 7 // edges with exactly ONE incident face: the surface is open here 57const MC_O_NONMANIFOLD: i64 = 8 // edges with THREE OR MORE incident faces 58const MC_O_WINDING: i64 = 9 // two-face edges whose faces traverse it the SAME way 59const MC_O_DUPFACE: i64 = 10 // two triangles over the same three vertices 60const MC_O_EULER: i64 = 11 // V - E + F, REPORTED not judged: a proxy, and it is why this organ exists 61const MC_O_DUPCHECKED: i64 = 12 // 1 when the duplicate-face check actually ran, 0 when nv exceeded its bound 62const MC_O_LIST_PREFIX: i64 = 13 // 1 when at least one worklist below is a prefix of its own count 63const MC_O_SLOTS: i64 = 14 64 65// worklist buffer layout: MC_LIST_MAX entries per class, classes in the order 66// BADINDEX, DEGEN_TOPO, DEGEN_AREA, LOOSE, BOUNDARY, NONMANIFOLD, WINDING, DUPFACE 67const MC_L_BADINDEX: i64 = 0 68const MC_L_DEGEN_TOPO: i64 = 1 69const MC_L_DEGEN_AREA: i64 = 2 70const MC_L_LOOSE: i64 = 3 71const MC_L_BOUNDARY: i64 = 4 72const MC_L_NONMANIFOLD: i64 = 5 73const MC_L_WINDING: i64 = 6 74const MC_L_DUPFACE: i64 = 7 75const MC_L_CLASSES: i64 = 8 76 77func mc_list_slots() -> i64 { return MC_L_CLASSES * MC_LIST_MAX } 78 79func mc_list_put(list: *i64, klass: i64, count_so_far: i64, value: i64) -> i64 { 80 if count_so_far < MC_LIST_MAX { list[klass * MC_LIST_MAX + count_so_far] = value; return 1 } 81 return 0 82} 83func mc_list_get(list: *i64, klass: i64, i: i64) -> i64 { return list[klass * MC_LIST_MAX + i] } 84 85// ---- bottom-up merge sort over (key, payload) ---------------------------------------------------- 86// O(n log n) DELIBERATELY. A mesh here can be the 662k-triangle BodyParts3D skeleton, which is about 87// two million directed edges; an insertion sort would be a quadratic hang that reads to the caller as 88// a crash. The estate has banked that exact confusion -- an unbounded scan that never returns is 89// indistinguishable from a dead process -- so the complexity is chosen from the data size, not taste. 90func mc_msort(k: *i64, d: *i64, tk: *i64, td: *i64, n: i64) -> i64 { 91 var width: i64 = 1 92 while width < n { 93 var i: i64 = 0 94 while i < n { 95 let lo: i64 = i 96 var mid: i64 = i + width 97 var hi: i64 = i + width + width 98 if mid > n { mid = n } 99 if hi > n { hi = n } 100 var a: i64 = lo 101 var b: i64 = mid 102 var o: i64 = lo 103 while o < hi { 104 var take_a: i64 = 0 105 if a < mid { 106 if b >= hi { take_a = 1 } 107 else { if k[a] <= k[b] { take_a = 1 } } 108 } 109 if take_a == 1 { tk[o] = k[a]; td[o] = d[a]; a = a + 1 } 110 else { tk[o] = k[b]; td[o] = d[b]; b = b + 1 } 111 o = o + 1 112 } 113 i = i + width + width 114 } 115 var c: i64 = 0 116 while c < n { k[c] = tk[c]; d[c] = td[c]; c = c + 1 } 117 width = width + width 118 } 119 return 0 120} 121 122func mc_min(a: i64, b: i64) -> i64 { if a < b { return a } return b } 123func mc_max(a: i64, b: i64) -> i64 { if a > b { return a } return b } 124 125// ---- THE SWEEP ----------------------------------------------------------------------------------- 126// verts: 3 integer coords per vertex. tris: 3 vertex indices per triangle. 127// Returns MC_CLEAN / MC_DEFECTS / MC_UNMEASURABLE / MC_INVALID. 128func mc_check(verts: *i64, nv: i64, tris: *i64, nt: i64, out: *i64, list: *i64) -> i64 { 129 var z: i64 = 0 130 while z < MC_O_SLOTS { out[z] = 0; z = z + 1 } 131 z = 0 132 while z < mc_list_slots() { list[z] = 0 - 1; z = z + 1 } 133 out[MC_O_VERTS] = nv 134 out[MC_O_TRIS] = nt 135 // AN EMPTY MESH IS NOT A CLEAN MESH. Returning CLEAN for zero faces would let a generator that 136 // emitted nothing pass the integrity sweep -- the empty-set-passes defect, wearing geometry. 137 if nt <= 0 { return MC_UNMEASURABLE } 138 if nv <= 0 { return MC_UNMEASURABLE } 139 140 // ---- PASS 1: index validity FIRST. Every later pass dereferences these indices, so validating 141 // them afterwards would mean reading out of bounds to discover they were out of bounds. 142 var bad: i64 = 0 143 var t: i64 = 0 144 while t < nt { 145 var c: i64 = 0 146 var t_bad: i64 = 0 147 while c < 3 { 148 let vi: i64 = tris[t * 3 + c] 149 if vi < 0 { t_bad = 1 } 150 if vi >= nv { t_bad = 1 } 151 c = c + 1 152 } 153 if t_bad == 1 { 154 if mc_list_put(list, MC_L_BADINDEX, bad, t) == 0 { out[MC_O_LIST_PREFIX] = 1 } 155 bad = bad + 1 156 } 157 t = t + 1 158 } 159 out[MC_O_BADINDEX] = bad 160 if bad > 0 { return MC_INVALID } 161 162 // ---- PASS 2: degeneracy, and the two kinds are NOT merged. 163 // A triangle naming one vertex twice is a TOPOLOGICAL degeneracy -- the mesh data is wrong. 164 // Three distinct vertices that happen to be collinear is a GEOMETRIC degeneracy -- the data is 165 // well-formed and the shape has zero area. Same symptom on screen, different repair, so they get 166 // different counters. The area test is an EXACT integer cross product: no epsilon, no float, so a 167 // zero here is proven rather than thresholded. 168 var dtopo: i64 = 0 169 var darea: i64 = 0 170 t = 0 171 while t < nt { 172 let ia: i64 = tris[t * 3] 173 let ib: i64 = tris[t * 3 + 1] 174 let ic: i64 = tris[t * 3 + 2] 175 var topo: i64 = 0 176 if ia == ib { topo = 1 } 177 if ib == ic { topo = 1 } 178 if ia == ic { topo = 1 } 179 if topo == 1 { 180 if mc_list_put(list, MC_L_DEGEN_TOPO, dtopo, t) == 0 { out[MC_O_LIST_PREFIX] = 1 } 181 dtopo = dtopo + 1 182 } 183 else { 184 let ux: i64 = verts[ib * 3] - verts[ia * 3] 185 let uy: i64 = verts[ib * 3 + 1] - verts[ia * 3 + 1] 186 let uz: i64 = verts[ib * 3 + 2] - verts[ia * 3 + 2] 187 let wx: i64 = verts[ic * 3] - verts[ia * 3] 188 let wy: i64 = verts[ic * 3 + 1] - verts[ia * 3 + 1] 189 let wz: i64 = verts[ic * 3 + 2] - verts[ia * 3 + 2] 190 let cx: i64 = uy * wz - uz * wy 191 let cy: i64 = uz * wx - ux * wz 192 let cz: i64 = ux * wy - uy * wx 193 if cx == 0 { if cy == 0 { if cz == 0 { 194 if mc_list_put(list, MC_L_DEGEN_AREA, darea, t) == 0 { out[MC_O_LIST_PREFIX] = 1 } 195 darea = darea + 1 196 } } } 197 } 198 t = t + 1 199 } 200 out[MC_O_DEGEN_TOPO] = dtopo 201 out[MC_O_DEGEN_AREA] = darea 202 203 // ---- PASS 3: loose vertices. A vertex no triangle references is invisible, ships in every file, 204 // and is the single most common reason a generated mesh is larger than the shape it draws. 205 let used: *i64 = sys_mmap(nv * MC_I64) as *i64 206 var v: i64 = 0 207 while v < nv { used[v] = 0; v = v + 1 } 208 t = 0 209 while t < nt { 210 used[tris[t * 3]] = 1 211 used[tris[t * 3 + 1]] = 1 212 used[tris[t * 3 + 2]] = 1 213 t = t + 1 214 } 215 var loose: i64 = 0 216 v = 0 217 while v < nv { 218 if used[v] == 0 { 219 if mc_list_put(list, MC_L_LOOSE, loose, v) == 0 { out[MC_O_LIST_PREFIX] = 1 } 220 loose = loose + 1 221 } 222 v = v + 1 223 } 224 out[MC_O_LOOSE] = loose 225 sys_munmap(used as *u8, nv * MC_I64) 226 227 // ---- PASS 4: edge incidence. THIS IS THE MEASUREMENT EULER IS A PROXY FOR. 228 // Every directed edge is keyed by its UNDIRECTED identity (lo*nv+hi) and carries the direction it 229 // was traversed. Sorting by key groups the faces that share each edge, and the run length is the 230 // incidence count: 1 = boundary, 2 = manifold, 3+ = non-manifold. Within a 2-run, two faces that 231 // traversed the edge the SAME way disagree about which side is outside -- inconsistent winding, 232 // which renders as a black or inside-out patch and which a deviation ruler cannot see at all. 233 let ne: i64 = nt * 3 234 let ekey: *i64 = sys_mmap(ne * MC_I64) as *i64 235 let edat: *i64 = sys_mmap(ne * MC_I64) as *i64 236 let tk: *i64 = sys_mmap(ne * MC_I64) as *i64 237 let td: *i64 = sys_mmap(ne * MC_I64) as *i64 238 var e: i64 = 0 239 t = 0 240 while t < nt { 241 var c: i64 = 0 242 while c < 3 { 243 var d: i64 = c + 1 244 if d == 3 { d = 0 } 245 let u: i64 = tris[t * 3 + c] 246 let w: i64 = tris[t * 3 + d] 247 let lo: i64 = mc_min(u, w) 248 let hi: i64 = mc_max(u, w) 249 ekey[e] = lo * nv + hi 250 // payload: direction bit (1 = traversed low to high) times nt, plus the face index, so one 251 // slot carries both without a second array 252 var dir: i64 = 0 253 if u == lo { dir = 1 } 254 edat[e] = dir * nt + t 255 e = e + 1 256 c = c + 1 257 } 258 t = t + 1 259 } 260 mc_msort(ekey, edat, tk, td, ne) 261 var distinct: i64 = 0 262 var boundary: i64 = 0 263 var nonman: i64 = 0 264 var wind: i64 = 0 265 var i: i64 = 0 266 while i < ne { 267 // RUN SCAN WITH AN EXPLICIT FLAG, NEVER A SENTINEL WRITTEN INTO THE CURSOR. The first version 268 // of this loop exited by assigning j = ne + ne and then tried to recover the real end with 269 // j = j - ne, which silently yields exactly ne for EVERY run -- so all three thousand directed 270 // edges read as one enormous run and the clean tetrahedron reported ITSELF non-manifold. That 271 // is this estate's own banked anti-pattern, named in the standing law: A LOOP-EXIT SENTINEL 272 // WRITTEN INTO THE SEARCH CURSOR ERASES THE ANSWER. It was caught on the gate's FIRST run, and 273 // caught in the most useful possible form -- gv_bite reported FALSE-POSITIVE: fired on the good 274 // input, which points straight at the detector rather than at the fixture. 275 var j: i64 = i + 1 276 var run: i64 = 1 277 var scanning: i64 = 1 278 while scanning == 1 { 279 if j >= ne { scanning = 0 } 280 else { 281 if ekey[j] == ekey[i] { run = run + 1; j = j + 1 } 282 else { scanning = 0 } 283 } 284 } 285 distinct = distinct + 1 286 if run == 1 { 287 if mc_list_put(list, MC_L_BOUNDARY, boundary, ekey[i]) == 0 { out[MC_O_LIST_PREFIX] = 1 } 288 boundary = boundary + 1 289 } 290 if run == 2 { 291 let d0: i64 = edat[i] / nt 292 let d1: i64 = edat[i + 1] / nt 293 if d0 == d1 { 294 if mc_list_put(list, MC_L_WINDING, wind, ekey[i]) == 0 { out[MC_O_LIST_PREFIX] = 1 } 295 wind = wind + 1 296 } 297 } 298 if run > 2 { 299 if mc_list_put(list, MC_L_NONMANIFOLD, nonman, ekey[i]) == 0 { out[MC_O_LIST_PREFIX] = 1 } 300 nonman = nonman + 1 301 } 302 i = j 303 } 304 out[MC_O_EDGES] = distinct 305 out[MC_O_BOUNDARY] = boundary 306 out[MC_O_NONMANIFOLD] = nonman 307 out[MC_O_WINDING] = wind 308 sys_munmap(ekey as *u8, ne * MC_I64) 309 sys_munmap(edat as *u8, ne * MC_I64) 310 sys_munmap(tk as *u8, ne * MC_I64) 311 sys_munmap(td as *u8, ne * MC_I64) 312 313 // ---- PASS 5: duplicate faces, or an HONEST REFUSAL. The key packs three indices into one i64, 314 // which bounds nv at the cube root of the range. Above that this check REPORTS THAT IT DID NOT RUN 315 // rather than returning a comfortable zero -- a check that silently skips is indistinguishable 316 // from a check that passed, and this organ exists because that confusion ships defects. 317 var dup: i64 = 0 318 if nv <= MC_TRIKEY_MAX_NV { 319 out[MC_O_DUPCHECKED] = 1 320 let fkey: *i64 = sys_mmap(nt * MC_I64) as *i64 321 let fdat: *i64 = sys_mmap(nt * MC_I64) as *i64 322 let fk2: *i64 = sys_mmap(nt * MC_I64) as *i64 323 let fd2: *i64 = sys_mmap(nt * MC_I64) as *i64 324 t = 0 325 while t < nt { 326 let a0: i64 = tris[t * 3] 327 let b0: i64 = tris[t * 3 + 1] 328 let c0: i64 = tris[t * 3 + 2] 329 var lo: i64 = mc_min(a0, mc_min(b0, c0)) 330 var hi: i64 = mc_max(a0, mc_max(b0, c0)) 331 let mid: i64 = a0 + b0 + c0 - lo - hi 332 fkey[t] = (lo * nv + mid) * nv + hi 333 fdat[t] = t 334 t = t + 1 335 } 336 mc_msort(fkey, fdat, fk2, fd2, nt) 337 var q: i64 = 1 338 while q < nt { 339 if fkey[q] == fkey[q - 1] { 340 if mc_list_put(list, MC_L_DUPFACE, dup, fdat[q]) == 0 { out[MC_O_LIST_PREFIX] = 1 } 341 dup = dup + 1 342 } 343 q = q + 1 344 } 345 sys_munmap(fkey as *u8, nt * MC_I64) 346 sys_munmap(fdat as *u8, nt * MC_I64) 347 sys_munmap(fk2 as *u8, nt * MC_I64) 348 sys_munmap(fd2 as *u8, nt * MC_I64) 349 } 350 out[MC_O_DUPFACE] = dup 351 352 // EULER IS REPORTED, NEVER JUDGED. V - E + F equals 2 for a closed genus-0 surface, and this organ 353 // publishes it so the number the older tooth tests remains visible -- but it is a single scalar 354 // over the whole surface and compensating defects cancel inside it, which is exactly why the 355 // incidence counts above exist. Reading this field as a verdict would reinstate the proxy. 356 out[MC_O_EULER] = nv - distinct + nt 357 358 if dtopo > 0 { return MC_DEFECTS } 359 if darea > 0 { return MC_DEFECTS } 360 if loose > 0 { return MC_DEFECTS } 361 if nonman > 0 { return MC_DEFECTS } 362 if wind > 0 { return MC_DEFECTS } 363 if dup > 0 { return MC_DEFECTS } 364 // A BOUNDARY EDGE IS DELIBERATELY NOT A DEFECT. An open surface is a legitimate thing to author -- 365 // a plane, a cloth patch, a cut-away anatomical section. Watertightness is a SEPARATE question and 366 // gets its own predicate below, so callers who need it ask for it rather than having it imposed. 367 return MC_CLEAN 368} 369 370// Watertight = closed AND manifold AND consistently wound. Asked separately, on purpose. 371func mc_watertight(out: *i64) -> i64 { 372 if out[MC_O_BOUNDARY] != 0 { return 0 } 373 if out[MC_O_NONMANIFOLD] != 0 { return 0 } 374 if out[MC_O_WINDING] != 0 { return 0 } 375 return 1 376} 377 378// Total defects across every class that IS a defect -- boundary excluded for the reason above. 379func mc_defect_total(out: *i64) -> i64 { 380 return out[MC_O_DEGEN_TOPO] + out[MC_O_DEGEN_AREA] + out[MC_O_LOOSE] 381 + out[MC_O_NONMANIFOLD] + out[MC_O_WINDING] + out[MC_O_DUPFACE] 382}