nx_mesh_decimate.nx source

1// nx_mesh_decimate.nx -- mesh DECIMATION by dense-grid vertex clustering (Rossignac-Borrel 1993), 2// pure integer. Marching-tetrahedra meshes are dense (many tiny triangles on flat faces); this 3// snaps every vertex to a regular cell grid (cell-CENTROID representative) and drops triangles 4// that collapse (>=2 verts land in the same cell) -> far fewer triangles for the SAME shape, with 5// bounded error <= ~cell. The transfer/size EXCEED: a sovereign STL shrinks Nx with one tolerance 6// knob, deterministically (integer). No hash needed (a dense bbox grid has no key collisions). 7// Reuses nx_mesh + nx_mesh_print_check (bbox). HONEST: this is a SIZE/transfer decimation, lossy 8// by <=~cell and not guaranteed watertight; closure-preserving decimation is a later rung. 9// license_tier: ORIGINAL 10import "nx_syscalls.nx" 11import "nx_mesh.nx" 12import "nx_mesh_print_check.nx" 13 14const NX_DECIM_MAX_CELLS: i64 = 6000000 15 16// linear cell index of (x,y,z) within the grid anchored at (minx,miny,minz), cell size `cell`. 17func decim_cell(x: i64, y: i64, z: i64, minx: i64, miny: i64, minz: i64, 18 cell: i64, nx_: i64, ny_: i64) -> i64 { 19 let cx: i64 = (x - minx) / cell 20 let cy: i64 = (y - miny) / cell 21 let cz: i64 = (z - minz) / cell 22 return cx + cy * nx_ + cz * nx_ * ny_ 23} 24 25func nx_mesh_decimate(m: *NxMesh, cell: i64) -> *NxMesh { 26 if (m as i64) == 0 { return 0 as *NxMesh } 27 if cell <= 0 { return 0 as *NxMesh } 28 let bb: *NxMeshBBox = nx_mesh_bbox_compute(m) 29 if bb.valid != 1 { return 0 as *NxMesh } 30 let minx: i64 = bb.min_x; let miny: i64 = bb.min_y; let minz: i64 = bb.min_z 31 let nx_: i64 = (bb.max_x - minx) / cell + 1 32 let ny_: i64 = (bb.max_y - miny) / cell + 1 33 let nz_: i64 = (bb.max_z - minz) / cell + 1 34 let nc: i64 = nx_ * ny_ * nz_ 35 if nc <= 0 { return 0 as *NxMesh } 36 if nc > NX_DECIM_MAX_CELLS { return 0 as *NxMesh } // cell too fine for this bbox 37 38 let cidx: *i64 = (sys_mmap(nc * 8)) as *i64 39 let sx: *i64 = (sys_mmap(nc * 8)) as *i64 40 let sy: *i64 = (sys_mmap(nc * 8)) as *i64 41 let sz: *i64 = (sys_mmap(nc * 8)) as *i64 42 let cnt: *i64 = (sys_mmap(nc * 8)) as *i64 43 var i: i64 = 0 44 while i < nc { cidx[i] = 0 - 1; sx[i] = 0; sy[i] = 0; sz[i] = 0; cnt[i] = 0; i = i + 1 } 45 46 // pass 1: accumulate centroid sums per occupied cell 47 var v: i64 = 0 48 while v < m.n_verts { 49 let x: i64 = nx_mesh_get_vertex_x(m, v) 50 let y: i64 = nx_mesh_get_vertex_y(m, v) 51 let z: i64 = nx_mesh_get_vertex_z(m, v) 52 let ci: i64 = decim_cell(x, y, z, minx, miny, minz, cell, nx_, ny_) 53 if ci >= 0 { if ci < nc { 54 sx[ci] = sx[ci] + x; sy[ci] = sy[ci] + y; sz[ci] = sz[ci] + z; cnt[ci] = cnt[ci] + 1 55 } } 56 v = v + 1 57 } 58 59 // assign new vertex indices to occupied cells 60 var nv: i64 = 0 61 i = 0 62 while i < nc { if cnt[i] > 0 { cidx[i] = nv; nv = nv + 1 } i = i + 1 } 63 if nv <= 0 { return 0 as *NxMesh } 64 65 // count surviving (non-degenerate) triangles 66 var nt2: i64 = 0 67 var t: i64 = 0 68 while t < m.n_tris { 69 let a: i64 = m.indices[t*3+0]; let b: i64 = m.indices[t*3+1]; let c: i64 = m.indices[t*3+2] 70 let ca: i64 = decim_cell(nx_mesh_get_vertex_x(m,a), nx_mesh_get_vertex_y(m,a), nx_mesh_get_vertex_z(m,a), minx,miny,minz,cell,nx_,ny_) 71 let cb: i64 = decim_cell(nx_mesh_get_vertex_x(m,b), nx_mesh_get_vertex_y(m,b), nx_mesh_get_vertex_z(m,b), minx,miny,minz,cell,nx_,ny_) 72 let cc: i64 = decim_cell(nx_mesh_get_vertex_x(m,c), nx_mesh_get_vertex_y(m,c), nx_mesh_get_vertex_z(m,c), minx,miny,minz,cell,nx_,ny_) 73 if ca != cb { if cb != cc { if ca != cc { nt2 = nt2 + 1 } } } 74 t = t + 1 75 } 76 if nt2 <= 0 { return 0 as *NxMesh } 77 78 let out: *NxMesh = nx_mesh_alloc(nv, nt2, 0) 79 if (out as i64) == 0 { return out } 80 81 // emit centroid vertices (integer average of the cell's members) 82 i = 0 83 while i < nc { 84 if cnt[i] > 0 { 85 nx_mesh_set_vertex(out, cidx[i], sx[i]/cnt[i], sy[i]/cnt[i], sz[i]/cnt[i], 0) 86 } 87 i = i + 1 88 } 89 // emit remapped, non-degenerate triangles 90 var tt: i64 = 0 91 t = 0 92 while t < m.n_tris { 93 let a: i64 = m.indices[t*3+0]; let b: i64 = m.indices[t*3+1]; let c: i64 = m.indices[t*3+2] 94 let ca: i64 = cidx[decim_cell(nx_mesh_get_vertex_x(m,a), nx_mesh_get_vertex_y(m,a), nx_mesh_get_vertex_z(m,a), minx,miny,minz,cell,nx_,ny_)] 95 let cb: i64 = cidx[decim_cell(nx_mesh_get_vertex_x(m,b), nx_mesh_get_vertex_y(m,b), nx_mesh_get_vertex_z(m,b), minx,miny,minz,cell,nx_,ny_)] 96 let cc: i64 = cidx[decim_cell(nx_mesh_get_vertex_x(m,c), nx_mesh_get_vertex_y(m,c), nx_mesh_get_vertex_z(m,c), minx,miny,minz,cell,nx_,ny_)] 97 if ca != cb { if cb != cc { if ca != cc { 98 nx_mesh_set_triangle(out, tt, ca, cb, cc); tt = tt + 1 99 } } } 100 t = t + 1 101 } 102 return out 103}