fast_mesh/
lib.rs

1//! Fast triangle mesh utilities.
2//!
3//! Meshes use flat buffers, the same layout as WebGL / three.js `BufferGeometry`:
4//! - `positions`: `[x0, y0, z0, x1, y1, z1, ...]`, length = vertex count × 3
5//! - `indices`: `[a0, b0, c0, a1, b1, c1, ...]`, length = triangle count × 3
6//!
7//! This crate has no WebAssembly dependencies so it can be tested natively and
8//! reused from plain Rust. The JS bindings live in `fast-mesh-wasm`.
9
10use std::fmt;
11
12/// Errors returned when input buffers do not describe a valid triangle mesh.
13#[derive(Debug, Clone, PartialEq, Eq)]
14pub enum MeshError {
15    /// `positions.len()` is not a multiple of 3.
16    PositionsNotMultipleOf3 { len: usize },
17    /// `indices.len()` is not a multiple of 3.
18    IndicesNotMultipleOf3 { len: usize },
19    /// An index points past the last vertex.
20    IndexOutOfRange { index: u32, vertex_count: usize },
21    /// The mesh has no vertices.
22    Empty,
23}
24
25impl fmt::Display for MeshError {
26    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
27        match self {
28            Self::PositionsNotMultipleOf3 { len } => {
29                write!(f, "positions length must be a multiple of 3, got {len}")
30            }
31            Self::IndicesNotMultipleOf3 { len } => {
32                write!(f, "indices length must be a multiple of 3, got {len}")
33            }
34            Self::IndexOutOfRange {
35                index,
36                vertex_count,
37            } => write!(
38                f,
39                "index {index} is out of range for a mesh with {vertex_count} vertices"
40            ),
41            Self::Empty => write!(f, "mesh has no vertices"),
42        }
43    }
44}
45
46impl std::error::Error for MeshError {}
47
48/// Axis-aligned bounding box.
49#[derive(Debug, Clone, Copy, PartialEq)]
50pub struct Aabb {
51    pub min: [f32; 3],
52    pub max: [f32; 3],
53}
54
55fn vertex_count(positions: &[f32]) -> Result<usize, MeshError> {
56    if !positions.len().is_multiple_of(3) {
57        return Err(MeshError::PositionsNotMultipleOf3 {
58            len: positions.len(),
59        });
60    }
61    Ok(positions.len() / 3)
62}
63
64fn validate_indices(indices: &[u32], vertex_count: usize) -> Result<(), MeshError> {
65    if !indices.len().is_multiple_of(3) {
66        return Err(MeshError::IndicesNotMultipleOf3 { len: indices.len() });
67    }
68    match indices.iter().find(|&&i| i as usize >= vertex_count) {
69        Some(&index) => Err(MeshError::IndexOutOfRange {
70            index,
71            vertex_count,
72        }),
73        None => Ok(()),
74    }
75}
76
77/// Computes smooth per-vertex normals.
78///
79/// Each face normal is weighted by the triangle's area, accumulated on its three
80/// vertices, then normalized. Vertices not used by any non-degenerate triangle
81/// get a `[0, 0, 0]` normal. Returns a buffer with the same length as `positions`.
82pub fn compute_vertex_normals(positions: &[f32], indices: &[u32]) -> Result<Vec<f32>, MeshError> {
83    let count = vertex_count(positions)?;
84    validate_indices(indices, count)?;
85
86    let mut normals = vec![0.0f32; positions.len()];
87    let p = |i: usize| [positions[i * 3], positions[i * 3 + 1], positions[i * 3 + 2]];
88
89    for &tri in indices.as_chunks::<3>().0 {
90        let (a, b, c) = (tri[0] as usize, tri[1] as usize, tri[2] as usize);
91        let (pa, pb, pc) = (p(a), p(b), p(c));
92        let e1 = [pb[0] - pa[0], pb[1] - pa[1], pb[2] - pa[2]];
93        let e2 = [pc[0] - pa[0], pc[1] - pa[1], pc[2] - pa[2]];
94        // The cross product's length is twice the triangle area, which gives area weighting for free.
95        let n = [
96            e1[1] * e2[2] - e1[2] * e2[1],
97            e1[2] * e2[0] - e1[0] * e2[2],
98            e1[0] * e2[1] - e1[1] * e2[0],
99        ];
100        for v in [a, b, c] {
101            normals[v * 3] += n[0];
102            normals[v * 3 + 1] += n[1];
103            normals[v * 3 + 2] += n[2];
104        }
105    }
106
107    for n in normals.as_chunks_mut::<3>().0 {
108        let len = (n[0] * n[0] + n[1] * n[1] + n[2] * n[2]).sqrt();
109        if len > 0.0 {
110            n.iter_mut().for_each(|x| *x /= len);
111        }
112    }
113    Ok(normals)
114}
115
116/// Computes the axis-aligned bounding box of all vertices.
117pub fn compute_bounds(positions: &[f32]) -> Result<Aabb, MeshError> {
118    if vertex_count(positions)? == 0 {
119        return Err(MeshError::Empty);
120    }
121    let mut min = [f32::INFINITY; 3];
122    let mut max = [f32::NEG_INFINITY; 3];
123    for v in positions.as_chunks::<3>().0 {
124        for axis in 0..3 {
125            min[axis] = min[axis].min(v[axis]);
126            max[axis] = max[axis].max(v[axis]);
127        }
128    }
129    Ok(Aabb { min, max })
130}
131
132#[cfg(test)]
133mod tests {
134    use super::*;
135
136    // Unit quad on the XY plane, two counter-clockwise triangles facing +Z.
137    const QUAD_POSITIONS: [f32; 12] = [0., 0., 0., 1., 0., 0., 1., 1., 0., 0., 1., 0.];
138    const QUAD_INDICES: [u32; 6] = [0, 1, 2, 0, 2, 3];
139
140    #[test]
141    fn flat_quad_normals_point_up() {
142        let normals = compute_vertex_normals(&QUAD_POSITIONS, &QUAD_INDICES).unwrap();
143        assert_eq!(normals.len(), QUAD_POSITIONS.len());
144        for n in normals.as_chunks::<3>().0 {
145            assert_eq!(n, &[0., 0., 1.]);
146        }
147    }
148
149    #[test]
150    fn unused_vertex_gets_zero_normal() {
151        let mut positions = QUAD_POSITIONS.to_vec();
152        positions.extend_from_slice(&[5., 5., 5.]);
153        let normals = compute_vertex_normals(&positions, &QUAD_INDICES).unwrap();
154        assert_eq!(&normals[12..], &[0., 0., 0.]);
155    }
156
157    #[test]
158    fn rejects_bad_buffers() {
159        assert_eq!(
160            compute_vertex_normals(&[0., 0.], &[]),
161            Err(MeshError::PositionsNotMultipleOf3 { len: 2 })
162        );
163        assert_eq!(
164            compute_vertex_normals(&QUAD_POSITIONS, &[0, 1]),
165            Err(MeshError::IndicesNotMultipleOf3 { len: 2 })
166        );
167        assert_eq!(
168            compute_vertex_normals(&QUAD_POSITIONS, &[0, 1, 9]),
169            Err(MeshError::IndexOutOfRange {
170                index: 9,
171                vertex_count: 4
172            })
173        );
174    }
175
176    #[test]
177    fn bounds_of_quad() {
178        let b = compute_bounds(&QUAD_POSITIONS).unwrap();
179        assert_eq!(b.min, [0., 0., 0.]);
180        assert_eq!(b.max, [1., 1., 0.]);
181        assert_eq!(compute_bounds(&[]), Err(MeshError::Empty));
182    }
183}
fast_mesh/lib.rs

fast_mesh/
lib.rs
