Skip to main content

irmf_output_voxels/
lib.rs

1//! Shared voxel processing and output formats.
2//!
3//! This crate provides a central `BinVox` struct for representing a 3D voxel grid
4//! and implementations for various output formats like Binvox, ZIP, SVX, and DLP.
5//! It also includes a Marching Cubes algorithm to convert voxels to a mesh.
6//!
7//! For more information about the IRMF format and its capabilities, visit the
8//! [official IRMF website](https://irmf.io).
9
10pub mod binvox_out;
11pub mod gpu_mc;
12pub mod photon_out;
13pub mod svx_out;
14pub mod zip_out;
15
16use std::io::Write;
17
18/// A 3D voxel grid.
19pub struct BinVox {
20    /// Number of voxels in the X dimension.
21    pub nx: usize,
22    /// Number of voxels in the Y dimension.
23    pub ny: usize,
24    /// Number of voxels in the Z dimension.
25    pub nz: usize,
26    /// Minimum X coordinate.
27    pub min_x: f64,
28    /// Minimum Y coordinate.
29    pub min_y: f64,
30    /// Minimum Z coordinate.
31    pub min_z: f64,
32    /// Maximum X coordinate.
33    pub max_x: f64,
34    /// Maximum Y coordinate.
35    pub max_y: f64,
36    /// Maximum Z coordinate.
37    pub max_z: f64,
38    /// Scale of the model (usually the Z-extent).
39    pub scale: f64,
40    /// Bit-packed voxel data.
41    pub data: Vec<u8>,
42}
43
44impl BinVox {
45    /// Creates a new `BinVox` grid.
46    pub fn new(nx: usize, ny: usize, nz: usize, min: [f32; 3], max: [f32; 3]) -> Self {
47        let size = (nx * ny * nz).div_ceil(8);
48        Self {
49            nx,
50            ny,
51            nz,
52            min_x: min[0] as f64,
53            min_y: min[1] as f64,
54            min_z: min[2] as f64,
55            max_x: max[0] as f64,
56            max_y: max[1] as f64,
57            max_z: max[2] as f64,
58            scale: (max[2] - min[2]) as f64,
59            data: vec![0; size],
60        }
61    }
62
63    /// Sets the voxel at the given coordinates to solid.
64    pub fn set(&mut self, x: usize, y: usize, z: usize) {
65        if x >= self.nx || y >= self.ny || z >= self.nz {
66            return;
67        }
68        let index = z * self.nx * self.ny + y * self.nx + x;
69        self.data[index / 8] |= 1 << (index % 8);
70    }
71
72    /// Returns `true` if the voxel at the given coordinates is solid.
73    pub fn get(&self, x: usize, y: usize, z: usize) -> bool {
74        if x >= self.nx || y >= self.ny || z >= self.nz {
75            return false;
76        }
77        let index = z * self.nx * self.ny + y * self.nx + x;
78        (self.data[index / 8] & (1 << (index % 8))) != 0
79    }
80
81    /// Runs the Marching Cubes algorithm on the voxel grid to generate a mesh.
82    ///
83    /// # Arguments
84    ///
85    /// * `on_progress` - Optional callback for reporting progress (current slice, total slices).
86    pub fn marching_cubes<P: FnMut(usize, usize)>(&self, mut on_progress: Option<P>) -> Mesh {
87        let mut triangles = Vec::new();
88        let dx = (self.max_x - self.min_x) / (self.nx as f64);
89        let dy = (self.max_y - self.min_y) / (self.ny as f64);
90        let dz = (self.max_z - self.min_z) / (self.nz as f64);
91
92        for z in -1..self.nz as i32 {
93            if let Some(ref mut p) = on_progress {
94                p((z + 1) as usize, self.nz + 1);
95            }
96            for y in -1..self.ny as i32 {
97                for x in -1..self.nx as i32 {
98                    let mut cube_index = 0;
99                    if self.get_i32(x, y, z) {
100                        cube_index |= 1;
101                    }
102                    if self.get_i32(x + 1, y, z) {
103                        cube_index |= 2;
104                    }
105                    if self.get_i32(x + 1, y + 1, z) {
106                        cube_index |= 4;
107                    }
108                    if self.get_i32(x, y + 1, z) {
109                        cube_index |= 8;
110                    }
111                    if self.get_i32(x, y, z + 1) {
112                        cube_index |= 16;
113                    }
114                    if self.get_i32(x + 1, y, z + 1) {
115                        cube_index |= 32;
116                    }
117                    if self.get_i32(x + 1, y + 1, z + 1) {
118                        cube_index |= 64;
119                    }
120                    if self.get_i32(x, y + 1, z + 1) {
121                        cube_index |= 128;
122                    }
123
124                    let edges = TRI_TABLE[cube_index];
125                    let mut i = 0;
126                    while i < edges.len() && edges[i] != -1 {
127                        let delta = [dx, dy, dz];
128                        let v1 = self.interp_edge(x, y, z, edges[i], delta);
129                        let v2 = self.interp_edge(x, y, z, edges[i + 1], delta);
130                        let v3 = self.interp_edge(x, y, z, edges[i + 2], delta);
131
132                        // Winding order check: (v2-v1) x (v3-v1) for outward normal
133                        let u_vec = [v2[0] - v1[0], v2[1] - v1[1], v2[2] - v1[2]];
134                        let v_vec = [v3[0] - v1[0], v3[1] - v1[1], v3[2] - v1[2]];
135                        let normal = [
136                            u_vec[1] * v_vec[2] - u_vec[2] * v_vec[1],
137                            u_vec[2] * v_vec[0] - u_vec[0] * v_vec[2],
138                            u_vec[0] * v_vec[1] - u_vec[1] * v_vec[0],
139                        ];
140                        let len =
141                            (normal[0] * normal[0] + normal[1] * normal[1] + normal[2] * normal[2])
142                                .sqrt();
143                        let normal = if len > 0.0 {
144                            [normal[0] / len, normal[1] / len, normal[2] / len]
145                        } else {
146                            [0.0, 0.0, 0.0]
147                        };
148
149                        triangles.push(Triangle::new(v1, v2, v3, normal));
150                        i += 3;
151                    }
152                }
153            }
154        }
155        Mesh { triangles }
156    }
157
158    fn get_i32(&self, x: i32, y: i32, z: i32) -> bool {
159        if x < 0
160            || y < 0
161            || z < 0
162            || x >= self.nx as i32
163            || y >= self.ny as i32
164            || z >= self.nz as i32
165        {
166            return false;
167        }
168        self.get(x as usize, y as usize, z as usize)
169    }
170
171    fn interp_edge(&self, x: i32, y: i32, z: i32, edge: i32, delta: [f64; 3]) -> [f32; 3] {
172        let dx = delta[0];
173        let dy = delta[1];
174        let dz = delta[2];
175        let edge_vertices = [
176            [0, 1],
177            [1, 2],
178            [2, 3],
179            [3, 0],
180            [4, 5],
181            [5, 6],
182            [6, 7],
183            [7, 4],
184            [0, 4],
185            [1, 5],
186            [2, 6],
187            [3, 7],
188        ];
189        let v1_idx = edge_vertices[edge as usize][0];
190        let v2_idx = edge_vertices[edge as usize][1];
191        let p = [
192            [x, y, z],
193            [x + 1, y, z],
194            [x + 1, y + 1, z],
195            [x, y + 1, z],
196            [x, y, z + 1],
197            [x + 1, y, z + 1],
198            [x + 1, y + 1, z + 1],
199            [x, y + 1, z + 1],
200        ];
201        let p1 = p[v1_idx];
202        let p2 = p[v2_idx];
203        let mx = self.min_x + (p1[0] as f64 + 0.5 + p2[0] as f64 + 0.5) * 0.5 * dx;
204        let my = self.min_y + (p1[1] as f64 + 0.5 + p2[1] as f64 + 0.5) * 0.5 * dy;
205        let mz = self.min_z + (p1[2] as f64 + 0.5 + p2[2] as f64 + 0.5) * 0.5 * dz;
206        [mx as f32, my as f32, mz as f32]
207    }
208
209    /// Writes the voxel data in the Binvox format.
210    pub fn write_binvox<W: Write>(&self, mut w: W) -> std::io::Result<()> {
211        writeln!(w, "#binvox 1")?;
212        writeln!(w, "dim {} {} {}", self.nx, self.ny, self.nz)?;
213        writeln!(w, "translate {} {} {}", self.min_x, self.min_y, self.min_z)?;
214        writeln!(w, "scale {}", self.scale)?;
215        writeln!(w, "data")?;
216        let mut current_value = self.get(0, 0, 0);
217        let mut count = 0u8;
218        for z in 0..self.nz {
219            for y in 0..self.ny {
220                for x in 0..self.nx {
221                    let val = self.get(x, y, z);
222                    if val == current_value && count < 255 {
223                        count += 1;
224                    } else {
225                        w.write_all(&[current_value as u8, count])?;
226                        current_value = val;
227                        count = 1;
228                    }
229                }
230            }
231        }
232        w.write_all(&[current_value as u8, count])?;
233        Ok(())
234    }
235}
236
237/// A triangle in a 3D mesh.
238#[derive(Copy, Clone, Debug)]
239pub struct Triangle {
240    /// Normal vector of the triangle.
241    pub normal: [f32; 3],
242    /// First vertex.
243    pub v1: [f32; 3],
244    /// Second vertex.
245    pub v2: [f32; 3],
246    /// Third vertex.
247    pub v3: [f32; 3],
248}
249impl Triangle {
250    /// Creates a new `Triangle`.
251    pub fn new(v1: [f32; 3], v2: [f32; 3], v3: [f32; 3], normal: [f32; 3]) -> Self {
252        Self { normal, v1, v2, v3 }
253    }
254}
255/// A 3D mesh consisting of triangles.
256pub struct Mesh {
257    /// List of triangles in the mesh.
258    pub triangles: Vec<Triangle>,
259}
260impl Mesh {
261    /// Saves the mesh to a binary STL file.
262    pub fn save_stl<W: Write>(&self, mut w: W) -> std::io::Result<()> {
263        let header = [0u8; 80];
264        w.write_all(&header)?;
265        let count = self.triangles.len() as u32;
266        w.write_all(&count.to_le_bytes())?;
267        for tri in &self.triangles {
268            w.write_all(bytemuck::bytes_of(&tri.normal))?;
269            w.write_all(bytemuck::bytes_of(&tri.v1))?;
270            w.write_all(bytemuck::bytes_of(&tri.v2))?;
271            w.write_all(bytemuck::bytes_of(&tri.v3))?;
272            w.write_all(&0u16.to_le_bytes())?;
273        }
274        Ok(())
275    }
276}
277
278/// Triangle table for the Marching Cubes algorithm.
279pub const TRI_TABLE: [[i32; 16]; 256] = [
280    [
281        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
282    ],
283    [0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
284    [0, 1, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
285    [1, 8, 3, 9, 8, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
286    [1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
287    [0, 8, 3, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
288    [9, 2, 10, 0, 2, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
289    [2, 8, 3, 2, 10, 8, 10, 9, 8, -1, -1, -1, -1, -1, -1, -1],
290    [3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
291    [0, 11, 2, 8, 11, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
292    [1, 9, 0, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
293    [1, 11, 2, 1, 9, 11, 9, 8, 11, -1, -1, -1, -1, -1, -1, -1],
294    [3, 10, 1, 11, 10, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
295    [0, 10, 1, 0, 8, 10, 8, 11, 10, -1, -1, -1, -1, -1, -1, -1],
296    [3, 9, 0, 3, 11, 9, 11, 10, 9, -1, -1, -1, -1, -1, -1, -1],
297    [9, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
298    [4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
299    [4, 3, 0, 7, 3, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
300    [0, 1, 9, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
301    [4, 1, 9, 4, 7, 1, 7, 3, 1, -1, -1, -1, -1, -1, -1, -1],
302    [1, 2, 10, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
303    [3, 4, 7, 3, 0, 4, 1, 2, 10, -1, -1, -1, -1, -1, -1, -1],
304    [9, 2, 10, 9, 0, 2, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1],
305    [2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4, -1, -1, -1, -1],
306    [8, 4, 7, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
307    [11, 4, 7, 11, 2, 4, 2, 0, 4, -1, -1, -1, -1, -1, -1, -1],
308    [9, 0, 1, 8, 4, 7, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1],
309    [4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1, -1, -1, -1, -1],
310    [3, 10, 1, 3, 11, 10, 7, 8, 4, -1, -1, -1, -1, -1, -1, -1],
311    [1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4, -1, -1, -1, -1],
312    [4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3, -1, -1, -1, -1],
313    [4, 7, 11, 4, 11, 9, 9, 11, 10, -1, -1, -1, -1, -1, -1, -1],
314    [9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
315    [9, 5, 4, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
316    [0, 5, 4, 1, 5, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
317    [8, 5, 4, 8, 3, 5, 3, 1, 5, -1, -1, -1, -1, -1, -1, -1],
318    [1, 2, 10, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
319    [3, 0, 8, 1, 2, 10, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1],
320    [5, 2, 10, 5, 4, 2, 4, 0, 2, -1, -1, -1, -1, -1, -1, -1],
321    [2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8, -1, -1, -1, -1],
322    [9, 5, 4, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
323    [0, 11, 2, 0, 8, 11, 4, 9, 5, -1, -1, -1, -1, -1, -1, -1],
324    [0, 5, 4, 0, 1, 5, 2, 3, 11, -1, -1, -1, -1, -1, -1, -1],
325    [2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5, -1, -1, -1, -1],
326    [10, 3, 11, 10, 1, 3, 9, 5, 4, -1, -1, -1, -1, -1, -1, -1],
327    [4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10, -1, -1, -1, -1],
328    [5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3, -1, -1, -1, -1],
329    [5, 4, 8, 5, 8, 10, 10, 8, 11, -1, -1, -1, -1, -1, -1, -1],
330    [9, 7, 8, 5, 7, 9, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
331    [9, 3, 0, 9, 5, 3, 5, 7, 3, -1, -1, -1, -1, -1, -1, -1],
332    [0, 7, 8, 0, 1, 7, 1, 5, 7, -1, -1, -1, -1, -1, -1, -1],
333    [1, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
334    [9, 7, 8, 9, 5, 7, 10, 1, 2, -1, -1, -1, -1, -1, -1, -1],
335    [10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3, -1, -1, -1, -1],
336    [8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2, -1, -1, -1, -1],
337    [2, 10, 5, 2, 5, 3, 3, 5, 7, -1, -1, -1, -1, -1, -1, -1],
338    [7, 9, 5, 7, 8, 9, 3, 11, 2, -1, -1, -1, -1, -1, -1, -1],
339    [9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11, -1, -1, -1, -1],
340    [2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7, -1, -1, -1, -1],
341    [11, 2, 1, 11, 1, 7, 7, 1, 5, -1, -1, -1, -1, -1, -1, -1],
342    [9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11, -1, -1, -1, -1],
343    [5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0, -1],
344    [11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0, -1],
345    [11, 10, 5, 7, 11, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
346    [10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
347    [0, 8, 3, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
348    [9, 0, 1, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
349    [1, 8, 3, 1, 9, 8, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1],
350    [1, 6, 5, 2, 6, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
351    [1, 6, 5, 1, 2, 6, 3, 0, 8, -1, -1, -1, -1, -1, -1, -1],
352    [9, 6, 5, 9, 0, 6, 0, 2, 6, -1, -1, -1, -1, -1, -1, -1],
353    [5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8, -1, -1, -1, -1],
354    [2, 3, 11, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
355    [11, 0, 8, 11, 2, 0, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1],
356    [0, 1, 9, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1, -1, -1, -1],
357    [5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11, -1, -1, -1, -1],
358    [6, 3, 11, 6, 5, 3, 5, 1, 3, -1, -1, -1, -1, -1, -1, -1],
359    [0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6, -1, -1, -1, -1],
360    [3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9, -1, -1, -1, -1],
361    [6, 5, 9, 6, 9, 11, 11, 9, 8, -1, -1, -1, -1, -1, -1, -1],
362    [5, 10, 6, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
363    [4, 3, 0, 4, 7, 3, 6, 5, 10, -1, -1, -1, -1, -1, -1, -1],
364    [1, 9, 0, 5, 10, 6, 8, 4, 7, -1, -1, -1, -1, -1, -1, -1],
365    [10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4, -1, -1, -1, -1],
366    [6, 1, 2, 6, 5, 1, 4, 7, 8, -1, -1, -1, -1, -1, -1, -1],
367    [1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7, -1, -1, -1, -1],
368    [8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6, -1, -1, -1, -1],
369    [7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9, -1],
370    [3, 11, 2, 7, 8, 4, 10, 6, 5, -1, -1, -1, -1, -1, -1, -1],
371    [5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11, -1, -1, -1, -1],
372    [0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6, -1, -1, -1, -1],
373    [9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6, -1],
374    [8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6, -1, -1, -1, -1],
375    [5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11, -1],
376    [0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7, -1],
377    [6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9, -1, -1, -1, -1],
378    [10, 4, 9, 6, 4, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
379    [4, 10, 6, 4, 9, 10, 0, 8, 3, -1, -1, -1, -1, -1, -1, -1],
380    [10, 0, 1, 10, 6, 0, 6, 4, 0, -1, -1, -1, -1, -1, -1, -1],
381    [8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10, -1, -1, -1, -1],
382    [1, 4, 9, 1, 2, 4, 2, 6, 4, -1, -1, -1, -1, -1, -1, -1],
383    [3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4, -1, -1, -1, -1],
384    [0, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
385    [8, 3, 2, 8, 2, 4, 4, 2, 6, -1, -1, -1, -1, -1, -1, -1],
386    [10, 4, 9, 10, 6, 4, 11, 2, 3, -1, -1, -1, -1, -1, -1, -1],
387    [0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6, -1, -1, -1, -1],
388    [3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10, -1, -1, -1, -1],
389    [6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1, -1],
390    [9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3, -1, -1, -1, -1],
391    [8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1, -1],
392    [3, 11, 6, 3, 6, 0, 0, 6, 4, -1, -1, -1, -1, -1, -1, -1],
393    [6, 4, 8, 11, 6, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
394    [7, 10, 6, 7, 8, 10, 8, 9, 10, -1, -1, -1, -1, -1, -1, -1],
395    [0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10, -1, -1, -1, -1],
396    [10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0, -1, -1, -1, -1],
397    [10, 6, 7, 10, 7, 1, 1, 7, 3, -1, -1, -1, -1, -1, -1, -1],
398    [1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7, -1, -1, -1, -1],
399    [2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9, -1],
400    [7, 8, 0, 7, 0, 6, 6, 0, 2, -1, -1, -1, -1, -1, -1, -1],
401    [7, 3, 2, 6, 7, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
402    [2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7, -1, -1, -1, -1],
403    [2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7, -1],
404    [1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11, -1],
405    [11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1, -1, -1, -1, -1],
406    [8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6, -1],
407    [0, 9, 1, 11, 6, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
408    [7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0, -1, -1, -1, -1],
409    [7, 11, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
410    [7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
411    [3, 0, 8, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
412    [0, 1, 9, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
413    [8, 1, 9, 8, 3, 1, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1],
414    [10, 1, 2, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
415    [1, 2, 10, 3, 0, 8, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1],
416    [2, 9, 0, 2, 10, 9, 6, 11, 7, -1, -1, -1, -1, -1, -1, -1],
417    [6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8, -1, -1, -1, -1],
418    [7, 2, 3, 6, 2, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
419    [7, 0, 8, 7, 6, 0, 6, 2, 0, -1, -1, -1, -1, -1, -1, -1],
420    [2, 7, 6, 2, 3, 7, 0, 1, 9, -1, -1, -1, -1, -1, -1, -1],
421    [1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6, -1, -1, -1, -1],
422    [10, 7, 6, 10, 1, 7, 1, 3, 7, -1, -1, -1, -1, -1, -1, -1],
423    [10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8, -1, -1, -1, -1],
424    [0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7, -1, -1, -1, -1],
425    [7, 6, 10, 7, 10, 8, 8, 10, 9, -1, -1, -1, -1, -1, -1, -1],
426    [6, 8, 4, 11, 8, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
427    [3, 6, 11, 3, 0, 6, 0, 4, 6, -1, -1, -1, -1, -1, -1, -1],
428    [8, 6, 11, 8, 4, 6, 9, 0, 1, -1, -1, -1, -1, -1, -1, -1],
429    [9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6, -1, -1, -1, -1],
430    [6, 8, 4, 6, 11, 8, 2, 10, 1, -1, -1, -1, -1, -1, -1, -1],
431    [1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6, -1, -1, -1, -1],
432    [4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9, -1, -1, -1, -1],
433    [10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3, -1],
434    [8, 2, 3, 8, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1],
435    [0, 4, 2, 4, 6, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
436    [1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8, -1, -1, -1, -1],
437    [1, 9, 4, 1, 4, 2, 2, 4, 6, -1, -1, -1, -1, -1, -1, -1],
438    [8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1, -1, -1, -1, -1],
439    [10, 1, 0, 10, 0, 6, 6, 0, 4, -1, -1, -1, -1, -1, -1, -1],
440    [4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3, -1],
441    [10, 9, 4, 6, 10, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
442    [4, 9, 5, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
443    [0, 8, 3, 4, 9, 5, 11, 7, 6, -1, -1, -1, -1, -1, -1, -1],
444    [5, 0, 1, 5, 4, 0, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1],
445    [11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5, -1, -1, -1, -1],
446    [9, 5, 4, 10, 1, 2, 7, 6, 11, -1, -1, -1, -1, -1, -1, -1],
447    [6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5, -1, -1, -1, -1],
448    [7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2, -1, -1, -1, -1],
449    [3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6, -1],
450    [7, 2, 3, 7, 6, 2, 5, 4, 9, -1, -1, -1, -1, -1, -1, -1],
451    [9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7, -1, -1, -1, -1],
452    [3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0, -1, -1, -1, -1],
453    [6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8, -1],
454    [9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7, -1, -1, -1, -1],
455    [1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4, -1],
456    [4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10, -1],
457    [7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10, -1, -1, -1, -1],
458    [6, 9, 5, 6, 11, 9, 11, 8, 9, -1, -1, -1, -1, -1, -1, -1],
459    [3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5, -1, -1, -1, -1],
460    [0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11, -1, -1, -1, -1],
461    [6, 11, 3, 6, 3, 5, 5, 3, 1, -1, -1, -1, -1, -1, -1, -1],
462    [1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6, -1, -1, -1, -1],
463    [0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10, -1],
464    [11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5, -1],
465    [6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3, -1, -1, -1, -1],
466    [5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2, -1, -1, -1, -1],
467    [9, 5, 6, 9, 6, 0, 0, 6, 2, -1, -1, -1, -1, -1, -1, -1],
468    [1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8, -1],
469    [1, 5, 6, 2, 1, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
470    [1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6, -1],
471    [10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0, -1, -1, -1, -1],
472    [0, 3, 8, 5, 6, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
473    [10, 5, 6, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
474    [11, 5, 10, 7, 5, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
475    [11, 5, 10, 11, 7, 5, 8, 3, 0, -1, -1, -1, -1, -1, -1, -1],
476    [5, 11, 7, 5, 10, 11, 1, 9, 0, -1, -1, -1, -1, -1, -1, -1],
477    [10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1, -1, -1, -1, -1],
478    [11, 1, 2, 11, 7, 1, 7, 5, 1, -1, -1, -1, -1, -1, -1, -1],
479    [0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11, -1, -1, -1, -1],
480    [9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7, -1, -1, -1, -1],
481    [7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2, -1],
482    [2, 5, 10, 2, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1],
483    [8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5, -1, -1, -1, -1],
484    [9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2, -1, -1, -1, -1],
485    [9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2, -1],
486    [1, 3, 5, 3, 7, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
487    [0, 8, 7, 0, 7, 1, 1, 7, 5, -1, -1, -1, -1, -1, -1, -1],
488    [9, 0, 3, 9, 3, 5, 5, 3, 7, -1, -1, -1, -1, -1, -1, -1],
489    [9, 8, 7, 5, 9, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
490    [5, 8, 4, 5, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1],
491    [5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0, -1, -1, -1, -1],
492    [0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5, -1, -1, -1, -1],
493    [10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4, -1],
494    [2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8, -1, -1, -1, -1],
495    [0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11, -1],
496    [0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5, -1],
497    [9, 4, 5, 2, 11, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
498    [2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4, -1, -1, -1, -1],
499    [5, 10, 2, 5, 2, 4, 4, 2, 0, -1, -1, -1, -1, -1, -1, -1],
500    [3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9, -1],
501    [5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2, -1, -1, -1, -1],
502    [8, 4, 5, 8, 5, 3, 3, 5, 1, -1, -1, -1, -1, -1, -1, -1],
503    [0, 4, 5, 1, 0, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
504    [8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5, -1, -1, -1, -1],
505    [9, 4, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
506    [4, 11, 7, 4, 9, 11, 9, 10, 11, -1, -1, -1, -1, -1, -1, -1],
507    [0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11, -1, -1, -1, -1],
508    [1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11, -1, -1, -1, -1],
509    [3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4, -1],
510    [4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2, -1, -1, -1, -1],
511    [9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3, -1],
512    [11, 7, 4, 11, 4, 2, 2, 4, 0, -1, -1, -1, -1, -1, -1, -1],
513    [11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4, -1, -1, -1, -1],
514    [2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9, -1, -1, -1, -1],
515    [9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7, -1],
516    [3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10, -1],
517    [1, 10, 2, 8, 7, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
518    [4, 9, 1, 4, 1, 7, 7, 1, 3, -1, -1, -1, -1, -1, -1, -1],
519    [4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1, -1, -1, -1, -1],
520    [4, 0, 3, 7, 4, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
521    [4, 8, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
522    [9, 10, 8, 10, 11, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
523    [3, 0, 9, 3, 9, 11, 11, 9, 10, -1, -1, -1, -1, -1, -1, -1],
524    [0, 1, 10, 0, 10, 8, 8, 10, 11, -1, -1, -1, -1, -1, -1, -1],
525    [3, 1, 10, 11, 3, 10, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
526    [1, 2, 11, 1, 11, 9, 9, 11, 8, -1, -1, -1, -1, -1, -1, -1],
527    [3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9, -1, -1, -1, -1],
528    [0, 2, 11, 8, 0, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
529    [3, 2, 11, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
530    [2, 3, 8, 2, 8, 10, 10, 8, 9, -1, -1, -1, -1, -1, -1, -1],
531    [9, 10, 2, 0, 9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
532    [2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8, -1, -1, -1, -1],
533    [1, 10, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
534    [1, 3, 8, 9, 1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
535    [0, 9, 1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
536    [0, 3, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1],
537    [
538        -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
539    ],
540];
541
542#[cfg(test)]
543mod tests {
544    use super::*;
545
546    #[test]
547    fn test_marching_cubes_single_voxel() {
548        let mut b = BinVox::new(2, 2, 2, [0.0, 0.0, 0.0], [2.0, 2.0, 2.0]);
549        b.set(0, 0, 0); // Only V0 is solid
550        let mesh = b.marching_cubes::<fn(usize, usize)>(None);
551        // A single point solid in the middle of a grid should be surrounded by 8 cubes.
552        // Each cube has one corner solid, so each should produce 1 triangle.
553        // Total 8 triangles forming an octahedron.
554        assert_eq!(mesh.triangles.len(), 8);
555
556        // Voxel (0,0,0) is centered at (0.5, 0.5, 0.5) with dx=1.0.
557        // Grid points are at -0.5, 0.5, 1.5, 2.5.
558        // Point (0,0,0) at index 0 is at (0.5, 0.5, 0.5).
559        // It is solid. Neighbors are empty.
560        // Surface should cross edges between index 0 and -1, and 0 and 1.
561        // Edge between -1 and 0 is at 0.0.
562        // Edge between 0 and 1 is at 1.0.
563        // So vertices should be at 0.0 or 1.0.
564        for tri in &mesh.triangles {
565            for v in &[tri.v1, tri.v2, tri.v3] {
566                let ok = (v[0] == 0.0 || v[0] == 1.0 || v[0] == 0.5)
567                    && (v[1] == 0.0 || v[1] == 1.0 || v[1] == 0.5)
568                    && (v[2] == 0.0 || v[2] == 1.0 || v[2] == 0.5);
569                assert!(ok, "Vertex {:?} is not at a boundary or midpoint", v);
570            }
571        }
572    }
573
574    #[test]
575    fn test_marching_cubes_octahedron() {
576        // 3x3x3 grid, points at 0.0, 1.0, 2.0
577        let mut b = BinVox::new(3, 3, 3, [0.0, 0.0, 0.0], [3.0, 3.0, 3.0]);
578        b.set(1, 1, 1); // Central point is solid
579        let mesh = b.marching_cubes::<fn(usize, usize)>(None);
580        // A single point solid in the middle of a grid should be surrounded by 8 cubes.
581        // Total 8 triangles forming an octahedron.
582        assert_eq!(mesh.triangles.len(), 8);
583
584        // dx=1.0. Voxel (1,1,1) is at (1.5, 1.5, 1.5).
585        // Edges between 0 and 1 are at 1.0.
586        // Edges between 1 and 2 are at 2.0.
587        for tri in &mesh.triangles {
588            for v in &[tri.v1, tri.v2, tri.v3] {
589                let ok = (v[0] == 1.0 || v[0] == 2.0 || v[0] == 1.5)
590                    && (v[1] == 1.0 || v[1] == 2.0 || v[1] == 1.5)
591                    && (v[2] == 1.0 || v[2] == 2.0 || v[2] == 1.5);
592                assert!(
593                    ok,
594                    "Vertex {:?} is not a midpoint of an edge connected to (1,1,1)",
595                    v
596                );
597            }
598        }
599    }
600
601    #[test]
602    fn test_marching_cubes_full_cube() {
603        let mut b = BinVox::new(2, 2, 2, [0.0, 0.0, 0.0], [2.0, 2.0, 2.0]);
604        for x in 0..2 {
605            for y in 0..2 {
606                for z in 0..2 {
607                    b.set(x, y, z);
608                }
609            }
610        }
611        let mesh = b.marching_cubes::<fn(usize, usize)>(None);
612        // A fully solid 2x2x2 cube should produce a 2x2x2 box mesh.
613        // It produces 44 triangles because of the subdivided boundary cubes.
614        assert_eq!(mesh.triangles.len(), 44);
615    }
616
617    #[test]
618    fn test_marching_cubes_manifold() {
619        let mut b = BinVox::new(3, 3, 3, [0.0, 0.0, 0.0], [2.0, 2.0, 2.0]);
620        b.set(1, 1, 1);
621        let mesh = b.marching_cubes::<fn(usize, usize)>(None);
622        assert_eq!(mesh.triangles.len(), 8);
623
624        // Manifold check: every edge must appear exactly twice (with opposite winding, but we just check count)
625        use std::collections::HashMap;
626        let mut edges = HashMap::new();
627
628        fn sort_v(v1: [f32; 3], v2: [f32; 3]) -> ([u32; 3], [u32; 3]) {
629            let k1 = [
630                (v1[0] * 1000.0) as u32,
631                (v1[1] * 1000.0) as u32,
632                (v1[2] * 1000.0) as u32,
633            ];
634            let k2 = [
635                (v2[0] * 1000.0) as u32,
636                (v2[1] * 1000.0) as u32,
637                (v2[2] * 1000.0) as u32,
638            ];
639            if k1 < k2 { (k1, k2) } else { (k2, k1) }
640        }
641
642        for tri in &mesh.triangles {
643            let e1 = sort_v(tri.v1, tri.v2);
644            let e2 = sort_v(tri.v2, tri.v3);
645            let e3 = sort_v(tri.v3, tri.v1);
646            *edges.entry(e1).or_insert(0) += 1;
647            *edges.entry(e2).or_insert(0) += 1;
648            *edges.entry(e3).or_insert(0) += 1;
649        }
650
651        for (edge, count) in edges {
652            assert_eq!(
653                count, 2,
654                "Edge {:?} appeared {} times, expected 2",
655                edge, count
656            );
657        }
658    }
659}