box3d_rust/mesh/
create.rs

1//! Mesh creation, edge identification, validation, and destroy.
2//!
3//! SPDX-FileCopyrightText: 2026 Erin Catto
4//! SPDX-License-Identifier: MIT
5
6use super::bvh::{
7    build_recursive, collect_primitives, fill_triangles, sort_mesh_triangles, weld_vertices,
8};
9use super::types::{
10    MeshData, MeshDef, MeshNode, MeshTriangle, CONCAVE_EDGE1, CONCAVE_EDGE2, CONCAVE_EDGE3,
11    INVERSE_CONCAVE_EDGE1, INVERSE_CONCAVE_EDGE2, INVERSE_CONCAVE_EDGE3, MESH_DATA_SIZE,
12    MESH_NODE_SIZE, MESH_TRIANGLE_SIZE, MESH_VERSION,
13};
14use crate::core::{hash, non_zero_hash, HASH_INIT, NULL_INDEX};
15use crate::math_functions::{
16    align_up8, cross, dot, max_int, min_int, normalize, signed_volume, sub, Vec3,
17};
18use std::collections::HashMap;
19
20struct MeshEdge {
21    vertex1: i32,
22    vertex2: i32,
23    triangle1: i32,
24    triangle2: i32,
25    triangle_count: u16,
26    triangle_edge_index1: u8,
27    triangle_edge_index2: u8,
28}
29
30fn identify_edges(mesh: &mut MeshData) {
31    let triangle_count = mesh.triangle_count as usize;
32    let edge_count = 3 * triangle_count;
33    let mut edges = Vec::with_capacity(edge_count);
34    let mut normals = vec![Vec3::default(); triangle_count];
35
36    for i in 0..triangle_count {
37        let triangle = mesh.triangles[i];
38        let i1 = triangle.index1;
39        let i2 = triangle.index2;
40        let i3 = triangle.index3;
41
42        edges.push(MeshEdge {
43            vertex1: min_int(i1, i2),
44            vertex2: max_int(i1, i2),
45            triangle1: i as i32,
46            triangle2: NULL_INDEX,
47            triangle_edge_index1: 0,
48            triangle_edge_index2: 0xFF,
49            triangle_count: 1,
50        });
51        edges.push(MeshEdge {
52            vertex1: min_int(i2, i3),
53            vertex2: max_int(i2, i3),
54            triangle1: i as i32,
55            triangle2: NULL_INDEX,
56            triangle_edge_index1: 1,
57            triangle_edge_index2: 0xFF,
58            triangle_count: 1,
59        });
60        edges.push(MeshEdge {
61            vertex1: min_int(i3, i1),
62            vertex2: max_int(i3, i1),
63            triangle1: i as i32,
64            triangle2: NULL_INDEX,
65            triangle_edge_index1: 2,
66            triangle_edge_index2: 0xFF,
67            triangle_count: 1,
68        });
69
70        let v1 = mesh.vertices[i1 as usize];
71        let v2 = mesh.vertices[i2 as usize];
72        let v3 = mesh.vertices[i3 as usize];
73        let e1 = sub(v2, v1);
74        let e2 = sub(v3, v1);
75        let n = cross(e1, e2);
76        normals[i] = normalize(n);
77    }
78
79    let mut map: HashMap<u64, i32> = HashMap::with_capacity(edge_count);
80    let key0 = ((edges[0].vertex1 as u64) << 32) | (edges[0].vertex2 as u64);
81    map.insert(key0, 0);
82
83    for i in 1..edge_count {
84        let key = ((edges[i].vertex1 as u64) << 32) | (edges[i].vertex2 as u64);
85        let triangle1 = edges[i].triangle1;
86        let triangle_edge_index1 = edges[i].triangle_edge_index1;
87        if let Some(&other_index) = map.get(&key) {
88            debug_assert!((other_index as usize) < i);
89            let base = &mut edges[other_index as usize];
90            if base.triangle_count == 1 {
91                base.triangle2 = triangle1;
92                base.triangle_edge_index2 = triangle_edge_index1;
93            }
94            base.triangle_count += 1;
95        } else {
96            map.insert(key, i as i32);
97        }
98    }
99    drop(map);
100
101    let edge_flags_concave = [CONCAVE_EDGE1, CONCAVE_EDGE2, CONCAVE_EDGE3];
102    let edge_flags_inverse = [
103        INVERSE_CONCAVE_EDGE1,
104        INVERSE_CONCAVE_EDGE2,
105        INVERSE_CONCAVE_EDGE3,
106    ];
107
108    for i in 0..edge_count {
109        let edge = &edges[i];
110        if edge.triangle_count != 2 {
111            continue;
112        }
113
114        debug_assert!(edge.triangle_edge_index1 < 3);
115        debug_assert!(edge.triangle_edge_index2 < 3);
116
117        let triangle1 = mesh.triangles[edge.triangle1 as usize];
118        let triangle2 = mesh.triangles[edge.triangle2 as usize];
119
120        let j1 = triangle2.index1;
121        let j2 = triangle2.index2;
122        let j3 = triangle2.index3;
123
124        let opposite = match edge.triangle_edge_index2 {
125            0 => j3,
126            1 => j1,
127            2 => j2,
128            _ => unreachable!(),
129        };
130
131        let i1 = triangle1.index1;
132        let i2 = triangle1.index2;
133        let i3 = triangle1.index3;
134
135        let v1 = mesh.vertices[i1 as usize];
136        let v2 = mesh.vertices[i2 as usize];
137        let v3 = mesh.vertices[i3 as usize];
138        let p = mesh.vertices[opposite as usize];
139
140        let cos5_deg = 0.9962f32;
141        let signed_vol = signed_volume(v1, v2, v3, p);
142        let n1 = normals[edge.triangle1 as usize];
143        let n2 = normals[edge.triangle2 as usize];
144        let cos_angle = dot(n1, n2);
145
146        if signed_vol > 0.0 || cos_angle > cos5_deg {
147            mesh.flags[edge.triangle1 as usize] |=
148                edge_flags_concave[edge.triangle_edge_index1 as usize] as u8;
149            mesh.flags[edge.triangle2 as usize] |=
150                edge_flags_concave[edge.triangle_edge_index2 as usize] as u8;
151        }
152
153        if signed_vol < 0.0 || cos_angle > cos5_deg {
154            mesh.flags[edge.triangle1 as usize] |=
155                edge_flags_inverse[edge.triangle_edge_index1 as usize] as u8;
156            mesh.flags[edge.triangle2 as usize] |=
157                edge_flags_inverse[edge.triangle_edge_index2 as usize] as u8;
158        }
159    }
160}
161
162fn node_height(nodes: &[MeshNode], index: usize) -> i32 {
163    let node = &nodes[index];
164    if node.is_leaf() {
165        return 0;
166    }
167    let left = node_height(nodes, index + 1);
168    let right = node_height(nodes, index + node.child_offset() as usize);
169    1 + left.max(right)
170}
171
172/// Height of the mesh BVH. (b3GetHeight)
173pub fn get_height(mesh: &MeshData) -> i32 {
174    if mesh.nodes.is_empty() {
175        return 0;
176    }
177    node_height(&mesh.nodes, 0)
178}
179
180/// Validate mesh version and size. (b3IsValidMesh)
181pub fn is_valid_mesh(mesh: Option<&MeshData>) -> bool {
182    let Some(mesh) = mesh else {
183        return false;
184    };
185    if mesh.version != MESH_VERSION {
186        return false;
187    }
188    if mesh.byte_count < MESH_DATA_SIZE as i32 {
189        return false;
190    }
191    true
192}
193
194/// Create a mesh from a definition. (b3CreateMesh)
195///
196/// Returns `None` on invalid input or BVH overflow. Degenerate triangle indices
197/// are written into `degenerate_triangle_indices` when provided (up to its length).
198pub fn create_mesh(
199    def: &MeshDef,
200    degenerate_triangle_indices: Option<&mut [i32]>,
201) -> Option<MeshData> {
202    let vertex_count_in = def.vertices.len() as i32;
203    let triangle_count_in = (def.indices.len() / 3) as i32;
204
205    if vertex_count_in < 3 || triangle_count_in <= 0 || def.indices.len() < 3 {
206        return None;
207    }
208
209    let mut indices = vec![0i32; (3 * triangle_count_in) as usize];
210    let mut vertices: Vec<Vec3>;
211    let mut vertex_count = vertex_count_in;
212
213    if def.weld_vertices && def.weld_tolerance > 0.0 {
214        vertices = vec![Vec3::default(); vertex_count as usize];
215        vertex_count = weld_vertices(
216            &def.vertices,
217            &def.indices[..(3 * triangle_count_in) as usize],
218            &mut vertices,
219            &mut indices,
220            def.weld_tolerance,
221        );
222        vertices.truncate(vertex_count as usize);
223        debug_assert!(vertex_count <= vertex_count_in);
224    } else {
225        vertices = def.vertices.clone();
226        indices.copy_from_slice(&def.indices[..(3 * triangle_count_in) as usize]);
227    }
228
229    let src_materials = if def.material_indices.is_empty() {
230        None
231    } else {
232        Some(def.material_indices.as_slice())
233    };
234
235    let (mut primitives, degenerate_count, surface_area, material_count, mesh_bounds) =
236        collect_primitives(&vertices, &indices, src_materials, triangle_count_in);
237
238    if let Some(out) = degenerate_triangle_indices {
239        let min_area = 0.01 * crate::constants::linear_slop() * crate::constants::linear_slop();
240        let mut written = 0usize;
241        let mut seen = 0i32;
242        for index in 0..triangle_count_in {
243            let index1 = indices[(3 * index) as usize];
244            let index2 = indices[(3 * index + 1) as usize];
245            let index3 = indices[(3 * index + 2) as usize];
246            let vertex1 = vertices[index1 as usize];
247            let vertex2 = vertices[index2 as usize];
248            let vertex3 = vertices[index3 as usize];
249            let normal = cross(sub(vertex2, vertex1), sub(vertex3, vertex1));
250            let area = 0.5 * crate::math_functions::length(normal);
251            if area < min_area && index1 != index2 && index1 != index3 && index2 != index3 {
252                seen += 1;
253                if written < out.len() {
254                    out[written] = index;
255                    written += 1;
256                }
257            }
258        }
259        debug_assert_eq!(seen, degenerate_count);
260        let _ = seen;
261    }
262
263    let triangle_count = primitives.len() as i32;
264    if !crate::math_functions::is_sane_aabb(mesh_bounds) {
265        return None;
266    }
267
268    let mut temp_nodes = Vec::with_capacity((2 * triangle_count - 1).max(1) as usize);
269    let mut tree_height = 0i32;
270    build_recursive(
271        &mut temp_nodes,
272        triangle_count,
273        &mut primitives,
274        0,
275        def.use_median_split,
276        &mut tree_height,
277    );
278
279    let mut byte_count = align_up8(MESH_DATA_SIZE);
280    let node_offset = byte_count as i32;
281    byte_count += align_up8(temp_nodes.len() * MESH_NODE_SIZE);
282    let vertex_offset = byte_count as i32;
283    byte_count += align_up8(vertex_count as usize * core::mem::size_of::<Vec3>());
284    let triangle_offset = byte_count as i32;
285    byte_count += align_up8(triangle_count as usize * MESH_TRIANGLE_SIZE);
286    let material_indices_offset = byte_count as i32;
287    byte_count += align_up8(triangle_count as usize);
288    let flags_offset = byte_count as i32;
289    byte_count += align_up8(triangle_count as usize);
290
291    let mut mesh = MeshData {
292        version: MESH_VERSION,
293        byte_count: byte_count as i32,
294        hash: 0,
295        bounds: mesh_bounds,
296        surface_area,
297        node_count: temp_nodes.len() as i32,
298        tree_height,
299        vertex_count,
300        triangle_count,
301        degenerate_count,
302        node_offset,
303        vertex_offset,
304        triangle_offset,
305        material_offset: material_indices_offset,
306        material_count,
307        flags_offset,
308        nodes: temp_nodes,
309        vertices,
310        triangles: vec![MeshTriangle::default(); triangle_count as usize],
311        material_indices: vec![0u8; triangle_count as usize],
312        flags: vec![0u8; triangle_count as usize],
313    };
314
315    fill_triangles(
316        &mut mesh.triangles,
317        &mut mesh.material_indices,
318        &mut mesh.flags,
319        &primitives,
320        &indices,
321        src_materials,
322    );
323
324    if !sort_mesh_triangles(&mut mesh) {
325        return None;
326    }
327
328    if def.identify_edges {
329        identify_edges(&mut mesh);
330    }
331
332    let bytes = mesh.to_bytes_with_hash(0);
333    mesh.hash = non_zero_hash(hash(HASH_INIT, &bytes));
334
335    Some(mesh)
336}
337
338/// Destroy a mesh (no-op drop for owned Rust data). (b3DestroyMesh)
339pub fn destroy_mesh(_mesh: MeshData) {}
340
341#[cfg(test)]
342mod tests {
343    use super::*;
344    use crate::math_functions::Vec3;
345
346    /// Degenerate triangle indices must be written when an out-buffer is provided
347    /// (C `b3CreateMesh` + MeshViewer `m_degenerateTriangles`).
348    #[test]
349    fn create_mesh_collects_degenerate_triangle_indices() {
350        // One valid triangle + one near-zero-area triangle with distinct verts.
351        let def = MeshDef {
352            vertices: vec![
353                Vec3 {
354                    x: 0.0,
355                    y: 0.0,
356                    z: 0.0,
357                },
358                Vec3 {
359                    x: 1.0,
360                    y: 0.0,
361                    z: 0.0,
362                },
363                Vec3 {
364                    x: 0.0,
365                    y: 1.0,
366                    z: 0.0,
367                },
368                Vec3 {
369                    x: 2.0,
370                    y: 0.0,
371                    z: 0.0,
372                }, // collinear with v0,v1 → degenerate
373            ],
374            indices: vec![0, 1, 2, 0, 1, 3],
375            material_indices: vec![],
376            weld_tolerance: 0.0,
377            weld_vertices: false,
378            use_median_split: true,
379            identify_edges: false,
380        };
381        let mut degenerate = [-1i32; 8];
382        let mesh = create_mesh(&def, Some(&mut degenerate)).expect("mesh");
383        assert_eq!(mesh.degenerate_count, 1);
384        assert_eq!(mesh.triangle_count, 1); // only the valid tri survives into the BVH
385        assert_eq!(degenerate[0], 1); // second input triangle
386        assert_eq!(degenerate[1], -1); // untouched past written count
387    }
388
389    /// Concave-edge identification and welding flags must both be accepted by
390    /// `create_mesh` (Viewer rebuild path); welding can collapse a near-duplicate
391    /// without inventing extra degenerates from duplicate-index triangles.
392    #[test]
393    fn create_mesh_viewer_flags_weld_and_identify_edges() {
394        let def = MeshDef {
395            vertices: vec![
396                Vec3 {
397                    x: 0.0,
398                    y: 0.0,
399                    z: 0.0,
400                },
401                Vec3 {
402                    x: 1.0,
403                    y: 0.0,
404                    z: 0.0,
405                },
406                Vec3 {
407                    x: 0.0,
408                    y: 1.0,
409                    z: 0.0,
410                },
411                Vec3 {
412                    x: 0.0005,
413                    y: 0.0,
414                    z: 0.0,
415                }, // within 1.5 mm weld tolerance of v0
416            ],
417            indices: vec![0, 1, 2, 3, 1, 2],
418            material_indices: vec![0, 1],
419            weld_tolerance: 0.0015,
420            weld_vertices: true,
421            use_median_split: true,
422            identify_edges: true,
423        };
424        let mut degenerate = [0i32; 8];
425        let mesh = create_mesh(&def, Some(&mut degenerate)).expect("mesh");
426        assert!(mesh.triangle_count >= 1);
427        assert!(mesh.vertex_count <= 3); // v0 and v3 weld together
428        assert!(mesh.degenerate_count >= 0);
429    }
430}
box3d_rust/mesh/create.rs

box3d_rust/mesh/
create.rs
