Skip to main content

rusting_brain/
mesh.rs

1//! Triangle meshes, and turning them into the signed distances a shape model
2//! trains on.
3//!
4//! Nothing here learns anything. It is the offline half of an image-to-3D
5//! pipeline: read a mesh, put it in a unit cube, ask where its surface is, and
6//! turn a field of distances back into a mesh at the end.
7//!
8//! The three pieces that carry the rest:
9//!
10//! - [`Bvh`] over the triangles, built once and asked two questions:
11//!   [`Bvh::closest_point`] for how far a point is from the surface, and
12//!   [`Bvh::winding_number`] for which side of it the point is on.
13//! - The generalized winding number rather than a ray cast, because a real
14//!   dataset is full of meshes with holes, duplicated faces and flipped
15//!   normals. A ray cast needs a closed surface to count crossings against; the
16//!   winding number degrades smoothly instead, reading a little over one inside
17//!   a mesh with a hole in it rather than flipping to the wrong answer.
18//! - [`marching_tetrahedra`] to go back, which is watertight by construction.
19//!
20//! ```no_run
21//! # use rusting_brain::mesh::{Mesh, Bvh, QuerySampling};
22//! # fn main() -> Result<(), Box<dyn std::error::Error>> {
23//! let mut mesh = Mesh::read_obj("chair.obj")?;
24//! let transform = mesh.normalize();          // into [-1, 1], invertible
25//! let bvh = Bvh::build(&mesh);
26//!
27//! let mut rng = <rand::rngs::StdRng as rand::SeedableRng>::seed_from_u64(0);
28//! let queries = bvh.sample_queries(&QuerySampling::default(), &mut rng);
29//! let distances = bvh.signed_distance(&queries);
30//! # let _ = (transform, distances);
31//! # Ok(())
32//! # }
33//! ```
34
35use crate::matrix::Matrix;
36use crate::network::NetworkError;
37use rand::Rng;
38use rayon::prelude::*;
39use std::collections::HashMap;
40use std::path::Path;
41
42/// A triangle mesh, indexed.
43///
44/// `normals`, `uvs` and `colors` are either empty or as long as `positions`.
45/// The geometry here needs none of them; they are carried so a reader and a
46/// writer round-trip, and `colors` is what the vertex-colour stand-in for
47/// texture is trained on and written from.
48#[derive(Clone, Debug, Default)]
49pub struct Mesh {
50    pub positions: Vec<[f32; 3]>,
51    pub normals: Vec<[f32; 3]>,
52    pub uvs: Vec<[f32; 2]>,
53    /// Linear RGB per vertex, 0 to 1.
54    pub colors: Vec<[f32; 3]>,
55    pub indices: Vec<[u32; 3]>,
56}
57
58/// The similarity transform [`Mesh::normalize`] applied, kept so a mesh that
59/// comes back out of the model can be put where the original was.
60#[derive(Clone, Copy, Debug, PartialEq)]
61pub struct Transform {
62    pub center: [f32; 3],
63    pub scale: f32,
64}
65
66impl Transform {
67    /// Undoes the normalization: the point in the original mesh's coordinates.
68    pub fn invert(&self, point: [f32; 3]) -> [f32; 3] {
69        std::array::from_fn(|axis| point[axis] / self.scale + self.center[axis])
70    }
71}
72
73impl Mesh {
74    /// The three corners of a face.
75    pub fn triangle(&self, face: usize) -> [[f32; 3]; 3] {
76        let face = self.indices[face];
77        std::array::from_fn(|corner| self.positions[face[corner] as usize])
78    }
79
80    /// The smallest axis-aligned box holding every vertex.
81    pub fn bounds(&self) -> ([f32; 3], [f32; 3]) {
82        let mut low = [f32::INFINITY; 3];
83        let mut high = [f32::NEG_INFINITY; 3];
84        for position in &self.positions {
85            for axis in 0..3 {
86                low[axis] = low[axis].min(position[axis]);
87                high[axis] = high[axis].max(position[axis]);
88            }
89        }
90        (low, high)
91    }
92
93    /// Centres the mesh on its bounding box and scales it to fill `[-1, 1]`,
94    /// returning the transform that was applied.
95    ///
96    /// The longest axis reaches the faces of the cube and the others fall short
97    /// of them, because scaling the axes separately would change the shape.
98    pub fn normalize(&mut self) -> Transform {
99        let (low, high) = self.bounds();
100        let center: [f32; 3] = std::array::from_fn(|axis| (low[axis] + high[axis]) / 2.0);
101        let extent = (0..3)
102            .map(|axis| high[axis] - low[axis])
103            .fold(0.0f32, f32::max);
104        // A mesh with no extent at all is a point; scaling it is meaningless,
105        // so it is left where it is rather than divided by zero.
106        let scale = match extent > 0.0 {
107            true => 2.0 / extent,
108            false => 1.0,
109        };
110        for position in &mut self.positions {
111            for axis in 0..3 {
112                position[axis] = (position[axis] - center[axis]) * scale;
113            }
114        }
115        Transform { center, scale }
116    }
117
118    /// Replaces the per-vertex normals with area-weighted face normals.
119    ///
120    /// Weighting by area rather than averaging the unit face normals is what
121    /// keeps a vertex where one huge triangle meets several slivers from being
122    /// dominated by the slivers.
123    pub fn recompute_normals(&mut self) {
124        let mut normals = vec![[0.0f32; 3]; self.positions.len()];
125        for face in 0..self.indices.len() {
126            let [a, b, c] = self.triangle(face);
127            // The cross product's length is twice the triangle's area, so
128            // accumulating it unnormalized is the weighting.
129            let normal = cross(sub(b, a), sub(c, a));
130            for corner in self.indices[face] {
131                for axis in 0..3 {
132                    normals[corner as usize][axis] += normal[axis];
133                }
134            }
135        }
136        for normal in &mut normals {
137            *normal = normalize(*normal);
138        }
139        self.normals = normals;
140    }
141
142    /// Total surface area.
143    pub fn area(&self) -> f32 {
144        (0..self.indices.len())
145            .map(|face| {
146                let [a, b, c] = self.triangle(face);
147                length(cross(sub(b, a), sub(c, a))) / 2.0
148            })
149            .sum()
150    }
151
152    /// Reads a Wavefront OBJ file.
153    ///
154    /// Positions, normals, texture coordinates and faces. Faces with more than
155    /// three corners are fanned into triangles, which is right for the convex
156    /// quads an exporter emits. Materials, groups and smoothing are skipped:
157    /// the geometry is what a distance field is built from.
158    pub fn read_obj<P: AsRef<Path>>(path: P) -> Result<Self, NetworkError> {
159        let text = std::fs::read_to_string(path)?;
160        let mut positions = Vec::new();
161        let mut normals = Vec::new();
162        let mut uvs = Vec::new();
163        let mut colours: Vec<[f32; 3]> = Vec::new();
164        // OBJ indexes position, normal and texture coordinate separately, and a
165        // mesh indexes them together, so each distinct triple becomes a vertex.
166        let mut vertices: HashMap<(i64, i64, i64), u32> = HashMap::new();
167        let mut mesh = Mesh::default();
168
169        for (number, line) in text.lines().enumerate() {
170            let mut fields = line.split_whitespace();
171            let complain =
172                |what: &str| NetworkError::InvalidDataset(format!("line {}: {what}", number + 1));
173            match fields.next() {
174                Some("v") => {
175                    positions.push(
176                        triple(&mut fields)
177                            .ok_or_else(|| complain("a vertex needs three coordinates"))?,
178                    );
179                    // The extended form writes the vertex colour in the three
180                    // fields after the position. Exporters that do not write it
181                    // leave the line at three fields, and the mismatch check
182                    // below drops a half-coloured mesh.
183                    if let Some(colour) = triple(&mut fields) {
184                        colours.push(colour);
185                    }
186                }
187                Some("vn") => normals.push(
188                    triple(&mut fields)
189                        .ok_or_else(|| complain("a normal needs three components"))?,
190                ),
191                Some("vt") => {
192                    let u = fields.next().and_then(|f| f.parse().ok());
193                    let v: f32 = fields.next().and_then(|f| f.parse().ok()).unwrap_or(0.0);
194                    // An .obj counts v up from the bottom of the image, glTF
195                    // counts it down from the top. Whatever reads `uvs` back
196                    // cannot tell which file they came from, so both readers
197                    // hand it the same convention: glTF's.
198                    uvs.push([
199                        u.ok_or_else(|| complain("a texture coordinate needs a u"))?,
200                        1.0 - v,
201                    ]);
202                }
203                Some("f") => {
204                    let corners = fields
205                        .map(|field| {
206                            let mut parts = field.split('/');
207                            let position = parts.next().and_then(|p| p.parse::<i64>().ok());
208                            let uv = parts.next().and_then(|p| p.parse::<i64>().ok());
209                            let normal = parts.next().and_then(|p| p.parse::<i64>().ok());
210                            position
211                                .map(|position| (position, uv.unwrap_or(0), normal.unwrap_or(0)))
212                        })
213                        .collect::<Option<Vec<_>>>()
214                        .ok_or_else(|| complain("a face corner needs a vertex index"))?;
215                    if corners.len() < 3 {
216                        return Err(complain("a face needs three corners"));
217                    }
218
219                    let mut resolved = Vec::with_capacity(corners.len());
220                    for key in corners {
221                        let index = match vertices.get(&key) {
222                            Some(index) => *index,
223                            None => {
224                                let index = mesh.positions.len() as u32;
225                                mesh.positions.push(*pick(&positions, key.0).ok_or_else(|| {
226                                    complain("a face names a vertex that is not there")
227                                })?);
228                                if let Some(colour) = pick(&colours, key.0) {
229                                    mesh.colors.push(*colour);
230                                }
231                                if let Some(uv) = pick(&uvs, key.1) {
232                                    mesh.uvs.push(*uv);
233                                }
234                                if let Some(normal) = pick(&normals, key.2) {
235                                    mesh.normals.push(*normal);
236                                }
237                                vertices.insert(key, index);
238                                index
239                            }
240                        };
241                        resolved.push(index);
242                    }
243                    // A fan, which is correct for the convex polygons an
244                    // exporter writes and is what every other reader does.
245                    for corner in 1..resolved.len() - 1 {
246                        mesh.indices
247                            .push([resolved[0], resolved[corner], resolved[corner + 1]]);
248                    }
249                }
250                _ => {}
251            }
252        }
253
254        if mesh.indices.is_empty() {
255            return Err(NetworkError::InvalidDataset("the file has no faces".into()));
256        }
257        // Half a vertex's attributes is worse than none: a consumer cannot tell
258        // which vertices have them.
259        if mesh.uvs.len() != mesh.positions.len() {
260            mesh.uvs.clear();
261        }
262        if mesh.normals.len() != mesh.positions.len() {
263            mesh.normals.clear();
264        }
265        if mesh.colors.len() != mesh.positions.len() {
266            mesh.colors.clear();
267        }
268        Ok(mesh)
269    }
270
271    /// Writes a Wavefront OBJ file: positions, normals if there are any, and
272    /// faces.
273    pub fn write_obj<P: AsRef<Path>>(&self, path: P) -> Result<(), NetworkError> {
274        use std::io::Write;
275        let mut file = std::io::BufWriter::new(std::fs::File::create(path)?);
276        for [x, y, z] in &self.positions {
277            writeln!(file, "v {x} {y} {z}")?;
278        }
279        for [x, y, z] in &self.normals {
280            writeln!(file, "vn {x} {y} {z}")?;
281        }
282        let normals = !self.normals.is_empty();
283        for face in &self.indices {
284            let [a, b, c] = face.map(|index| index + 1);
285            match normals {
286                true => writeln!(file, "f {a}//{a} {b}//{b} {c}//{c}")?,
287                false => writeln!(file, "f {a} {b} {c}")?,
288            }
289        }
290        Ok(())
291    }
292}
293
294/// OBJ indices count from one, and a negative index counts back from the end.
295fn pick<T>(values: &[T], index: i64) -> Option<&T> {
296    match index {
297        0 => None,
298        index if index > 0 => values.get(index as usize - 1),
299        index => values
300            .len()
301            .checked_sub(index.unsigned_abs() as usize)
302            .map(|at| &values[at]),
303    }
304}
305
306fn triple<'a>(fields: &mut impl Iterator<Item = &'a str>) -> Option<[f32; 3]> {
307    let mut values = [0.0; 3];
308    for value in &mut values {
309        *value = fields.next()?.parse().ok()?;
310    }
311    Some(values)
312}
313
314// -- Vector helpers. Three components, no dependency, no trait. ---------------
315
316fn sub(a: [f32; 3], b: [f32; 3]) -> [f32; 3] {
317    std::array::from_fn(|axis| a[axis] - b[axis])
318}
319
320fn add3(a: [f32; 3], b: [f32; 3]) -> [f32; 3] {
321    std::array::from_fn(|axis| a[axis] + b[axis])
322}
323
324fn scale(a: [f32; 3], factor: f32) -> [f32; 3] {
325    std::array::from_fn(|axis| a[axis] * factor)
326}
327
328fn dot(a: [f32; 3], b: [f32; 3]) -> f32 {
329    a[0] * b[0] + a[1] * b[1] + a[2] * b[2]
330}
331
332fn cross(a: [f32; 3], b: [f32; 3]) -> [f32; 3] {
333    [
334        a[1] * b[2] - a[2] * b[1],
335        a[2] * b[0] - a[0] * b[2],
336        a[0] * b[1] - a[1] * b[0],
337    ]
338}
339
340fn length(a: [f32; 3]) -> f32 {
341    dot(a, a).sqrt()
342}
343
344fn normalize(a: [f32; 3]) -> [f32; 3] {
345    match length(a) {
346        0.0 => [0.0; 3],
347        length => scale(a, 1.0 / length),
348    }
349}
350
351// -- The tree ----------------------------------------------------------------
352
353/// One node of a [`Bvh`]. Interior nodes keep the left child next to them and
354/// the right child's index; leaves keep a run of faces.
355#[derive(Clone, Debug)]
356struct Node {
357    low: [f32; 3],
358    high: [f32; 3],
359    /// First face in `order`, for a leaf.
360    start: u32,
361    /// Faces in the leaf, or zero for an interior node.
362    count: u32,
363    /// Right child, for an interior node.
364    right: u32,
365    /// Area-weighted normal summed over the node's faces, and the area-weighted
366    /// mean of their centroids. Together they are the dipole the winding number
367    /// approximates a distant node with.
368    moment: [f32; 3],
369    centroid: [f32; 3],
370    /// Distance from `centroid` to the furthest point of the node's faces,
371    /// which is what decides whether the approximation is allowed.
372    radius: f32,
373}
374
375/// A bounding volume hierarchy over a mesh's triangles.
376///
377/// Built once per mesh and asked two questions many times over, so it borrows
378/// the mesh rather than copying it.
379pub struct Bvh<'a> {
380    mesh: &'a Mesh,
381    nodes: Vec<Node>,
382    /// Face indices, permuted so a leaf is a contiguous run.
383    order: Vec<u32>,
384}
385
386/// Faces in a leaf. Four is the usual answer: fewer makes the tree deeper than
387/// the traversal saves, more makes the leaf scan dominate.
388const LEAF_SIZE: usize = 4;
389
390/// How far a node has to be, in multiples of its own radius, before its faces
391/// are replaced by one dipole. Jacobson's paper uses 2; larger is more accurate
392/// and slower.
393const WINDING_BETA: f32 = 2.0;
394
395impl<'a> Bvh<'a> {
396    /// Builds the tree. `O(n log n)`, single-threaded, and fast enough that it
397    /// has never been the thing worth parallelizing.
398    pub fn build(mesh: &'a Mesh) -> Self {
399        let centroids: Vec<[f32; 3]> = (0..mesh.indices.len())
400            .map(|face| {
401                let [a, b, c] = mesh.triangle(face);
402                scale(add3(add3(a, b), c), 1.0 / 3.0)
403            })
404            .collect();
405
406        let mut tree = Self {
407            mesh,
408            nodes: Vec::new(),
409            order: (0..mesh.indices.len() as u32).collect(),
410        };
411        if !tree.order.is_empty() {
412            tree.split(0, tree.mesh.indices.len(), &centroids);
413        }
414        tree
415    }
416
417    /// Builds the node covering `order[start..end]` and returns its index.
418    fn split(&mut self, start: usize, end: usize, centroids: &[[f32; 3]]) -> u32 {
419        let index = self.nodes.len() as u32;
420        let (low, high) = self.face_bounds(start, end);
421        self.nodes.push(Node {
422            low,
423            high,
424            start: start as u32,
425            count: (end - start) as u32,
426            right: 0,
427            moment: [0.0; 3],
428            centroid: [0.0; 3],
429            radius: 0.0,
430        });
431        self.summarize(index as usize, start, end);
432
433        if end - start > LEAF_SIZE {
434            // Split at the median along the widest axis of the centroids. A
435            // surface-area heuristic builds a better tree; the median one is
436            // twenty lines and has never been what a query waits on.
437            let axis = (0..3)
438                .max_by(|a, b| {
439                    (high[*a] - low[*a])
440                        .partial_cmp(&(high[*b] - low[*b]))
441                        .unwrap_or(std::cmp::Ordering::Equal)
442                })
443                .unwrap_or(0);
444            let middle = start + (end - start) / 2;
445            self.order[start..end].select_nth_unstable_by(middle - start, |a, b| {
446                centroids[*a as usize][axis]
447                    .partial_cmp(&centroids[*b as usize][axis])
448                    .unwrap_or(std::cmp::Ordering::Equal)
449            });
450            self.nodes[index as usize].count = 0;
451            self.split(start, middle, centroids);
452            let right = self.split(middle, end, centroids);
453            self.nodes[index as usize].right = right;
454        }
455        index
456    }
457
458    fn face_bounds(&self, start: usize, end: usize) -> ([f32; 3], [f32; 3]) {
459        let mut low = [f32::INFINITY; 3];
460        let mut high = [f32::NEG_INFINITY; 3];
461        for face in &self.order[start..end] {
462            for corner in self.mesh.triangle(*face as usize) {
463                for axis in 0..3 {
464                    low[axis] = low[axis].min(corner[axis]);
465                    high[axis] = high[axis].max(corner[axis]);
466                }
467            }
468        }
469        (low, high)
470    }
471
472    /// Fills in the dipole the winding number uses for a distant node.
473    fn summarize(&mut self, index: usize, start: usize, end: usize) {
474        let mut moment = [0.0f32; 3];
475        let mut centroid = [0.0f32; 3];
476        let mut area = 0.0f32;
477        for face in &self.order[start..end] {
478            let [a, b, c] = self.mesh.triangle(*face as usize);
479            // Twice the area times the unit normal, which is the weight the
480            // solid angle of a distant triangle is proportional to.
481            let doubled = cross(sub(b, a), sub(c, a));
482            let face_area = length(doubled) / 2.0;
483            moment = add3(moment, scale(doubled, 0.5));
484            centroid = add3(centroid, scale(add3(add3(a, b), c), face_area / 3.0));
485            area += face_area;
486        }
487        if area > 0.0 {
488            centroid = scale(centroid, 1.0 / area);
489        }
490        let mut radius = 0.0f32;
491        for face in &self.order[start..end] {
492            for corner in self.mesh.triangle(*face as usize) {
493                radius = radius.max(length(sub(corner, centroid)));
494            }
495        }
496        let node = &mut self.nodes[index];
497        node.moment = moment;
498        node.centroid = centroid;
499        node.radius = radius;
500    }
501
502    /// The point on the mesh closest to `query`, and its distance.
503    ///
504    /// Returns `None` for a mesh with no faces.
505    pub fn closest_point(&self, query: [f32; 3]) -> Option<([f32; 3], f32)> {
506        if self.nodes.is_empty() {
507            return None;
508        }
509        let mut best = ([0.0; 3], f32::INFINITY);
510        self.descend(0, query, &mut best);
511        Some(best)
512    }
513
514    fn descend(&self, index: u32, query: [f32; 3], best: &mut ([f32; 3], f32)) {
515        let node = &self.nodes[index as usize];
516        if box_distance(node.low, node.high, query) >= best.1 {
517            return;
518        }
519        if node.count > 0 {
520            let range = node.start as usize..(node.start + node.count) as usize;
521            for face in &self.order[range] {
522                let point = closest_on_triangle(query, self.mesh.triangle(*face as usize));
523                let distance = length(sub(point, query));
524                if distance < best.1 {
525                    *best = (point, distance);
526                }
527            }
528            return;
529        }
530        // Nearer child first, so the further one is more likely to be culled.
531        let (left, right) = (index + 1, node.right);
532        let order = match box_distance(
533            self.nodes[left as usize].low,
534            self.nodes[left as usize].high,
535            query,
536        ) <= box_distance(
537            self.nodes[right as usize].low,
538            self.nodes[right as usize].high,
539            query,
540        ) {
541            true => [left, right],
542            false => [right, left],
543        };
544        for child in order {
545            self.descend(child, query, best);
546        }
547    }
548
549    /// The generalized winding number at `query`: about 1 inside a closed mesh,
550    /// about 0 outside, and something in between near a hole.
551    ///
552    /// Exact for nearby triangles and a first-order dipole for distant nodes,
553    /// which is the Barnes-Hut arrangement from Jacobson, Kavan and Sorkine-
554    /// Hornung's *Robust Inside-Outside Segmentation using Generalized Winding
555    /// Numbers*. Without the approximation every query would touch every
556    /// triangle, because a solid angle has no cutoff.
557    ///
558    /// NOTE: first-order only. Adding the second-order term would let
559    /// `WINDING_BETA` drop and the traversal stop sooner; the first order is
560    /// what the paper shows is enough to classify points, which is all this is
561    /// used for.
562    pub fn winding_number(&self, query: [f32; 3]) -> f32 {
563        match self.nodes.is_empty() {
564            true => 0.0,
565            false => self.wind(0, query) / (4.0 * std::f32::consts::PI),
566        }
567    }
568
569    fn wind(&self, index: u32, query: [f32; 3]) -> f32 {
570        let node = &self.nodes[index as usize];
571        let offset = sub(node.centroid, query);
572        let distance = length(offset);
573        if distance > WINDING_BETA * node.radius && distance > 0.0 {
574            return dot(node.moment, offset) / (distance * distance * distance);
575        }
576        if node.count > 0 {
577            let range = node.start as usize..(node.start + node.count) as usize;
578            return self.order[range]
579                .iter()
580                .map(|face| solid_angle(query, self.mesh.triangle(*face as usize)))
581                .sum();
582        }
583        self.wind(index + 1, query) + self.wind(node.right, query)
584    }
585
586    /// Distance to the surface, negative inside it.
587    ///
588    /// One thread per query point: they are independent, and a field of two
589    /// million of them is the usual ask.
590    pub fn signed_distance(&self, queries: &[[f32; 3]]) -> Vec<f32> {
591        queries
592            .par_iter()
593            .map(|query| {
594                let distance = self.closest_point(*query).map_or(0.0, |(_, d)| d);
595                // A half turn is the boundary: a closed mesh reads 1 inside and
596                // 0 outside, and a mesh with a hole reads somewhere between.
597                match self.winding_number(*query) > 0.5 {
598                    true => -distance,
599                    false => distance,
600                }
601            })
602            .collect()
603    }
604}
605
606/// Distance from a point to a box, zero inside it.
607fn box_distance(low: [f32; 3], high: [f32; 3], query: [f32; 3]) -> f32 {
608    let outside: [f32; 3] = std::array::from_fn(|axis| {
609        (low[axis] - query[axis])
610            .max(query[axis] - high[axis])
611            .max(0.0)
612    });
613    length(outside)
614}
615
616/// The point of a triangle closest to `query`, by the region test from
617/// Ericson's *Real-Time Collision Detection*: check the three vertices, then
618/// the three edges, then the interior.
619fn closest_on_triangle(query: [f32; 3], [a, b, c]: [[f32; 3]; 3]) -> [f32; 3] {
620    let (ab, ac, aq) = (sub(b, a), sub(c, a), sub(query, a));
621    let (d1, d2) = (dot(ab, aq), dot(ac, aq));
622    if d1 <= 0.0 && d2 <= 0.0 {
623        return a;
624    }
625    let bq = sub(query, b);
626    let (d3, d4) = (dot(ab, bq), dot(ac, bq));
627    if d3 >= 0.0 && d4 <= d3 {
628        return b;
629    }
630    let vc = d1 * d4 - d3 * d2;
631    if vc <= 0.0 && d1 >= 0.0 && d3 <= 0.0 {
632        return add3(a, scale(ab, d1 / (d1 - d3)));
633    }
634    let cq = sub(query, c);
635    let (d5, d6) = (dot(ab, cq), dot(ac, cq));
636    if d6 >= 0.0 && d5 <= d6 {
637        return c;
638    }
639    let vb = d5 * d2 - d1 * d6;
640    if vb <= 0.0 && d2 >= 0.0 && d6 <= 0.0 {
641        return add3(a, scale(ac, d2 / (d2 - d6)));
642    }
643    let va = d3 * d6 - d5 * d4;
644    if va <= 0.0 && (d4 - d3) >= 0.0 && (d5 - d6) >= 0.0 {
645        return add3(b, scale(sub(c, b), (d4 - d3) / ((d4 - d3) + (d5 - d6))));
646    }
647    let denominator = va + vb + vc;
648    if denominator == 0.0 {
649        // A degenerate triangle, which a real dataset does contain.
650        return a;
651    }
652    let (v, w) = (vb / denominator, vc / denominator);
653    add3(add3(a, scale(ab, v)), scale(ac, w))
654}
655
656/// The signed solid angle a triangle subtends at `query`, by Van Oosterom and
657/// Strackee's formula. Its sum over a closed mesh is `4Ï€` inside and 0 outside.
658fn solid_angle(query: [f32; 3], [a, b, c]: [[f32; 3]; 3]) -> f32 {
659    let (a, b, c) = (sub(a, query), sub(b, query), sub(c, query));
660    let (la, lb, lc) = (length(a), length(b), length(c));
661    let denominator = la * lb * lc + dot(a, b) * lc + dot(a, c) * lb + dot(b, c) * la;
662    match denominator == 0.0 && dot(a, cross(b, c)) == 0.0 {
663        // The query is on the triangle's plane inside it, where the angle is
664        // undefined and `atan2(0, 0)` would answer zero.
665        true => 0.0,
666        false => 2.0 * dot(a, cross(b, c)).atan2(denominator),
667    }
668}
669
670// -- Sampling ----------------------------------------------------------------
671
672/// How the query points a shape model trains on are spread around.
673///
674/// The ratio between the two kinds is the single biggest lever on how a learned
675/// distance field turns out. All-uniform and the model never sees the surface
676/// closely enough to place it; all-near-surface and it has no idea which side
677/// of the shape the empty space is on, so it hallucinates a second surface out
678/// in the open. Start at the default and move it, rather than treating it as
679/// settled.
680#[derive(Clone, Copy, Debug, PartialEq)]
681pub struct QuerySampling {
682    /// Points to draw in total.
683    pub count: usize,
684    /// The fraction drawn near the surface rather than uniformly in the box.
685    pub near_surface: f32,
686    /// Standard deviation of the offset applied to a near-surface point, in the
687    /// units the mesh is normalized to.
688    pub jitter: f32,
689    /// Half-width of the uniform box, `1.0` for a mesh through
690    /// [`Mesh::normalize`]. A little over 1 leaves the model some empty space
691    /// outside the shape to learn from.
692    pub extent: f32,
693}
694
695impl Default for QuerySampling {
696    fn default() -> Self {
697        Self {
698            count: 200_000,
699            near_surface: 0.7,
700            jitter: 0.02,
701            extent: 1.1,
702        }
703    }
704}
705
706/// Points, normals or colours: one `[f32; 3]` per surface sample.
707pub type Cloud = Vec<[f32; 3]>;
708
709impl Bvh<'_> {
710    /// Points on the surface, area-weighted, with the face normal at each.
711    ///
712    /// Area weighting is what makes this uniform over the surface instead of
713    /// uniform over the faces: without it a mesh with one huge floor triangle
714    /// and a thousand small ones on a lamp would put almost every sample on the
715    /// lamp.
716    pub fn sample_surface<R: Rng>(
717        &self,
718        count: usize,
719        rng: &mut R,
720    ) -> (Vec<[f32; 3]>, Vec<[f32; 3]>) {
721        let (points, normals, _) = self.sample_surface_colored(count, rng);
722        (points, normals)
723    }
724
725    /// The same sampling, with the vertex colour interpolated at each point.
726    ///
727    /// The colours come back empty when the mesh carries none, so a caller that
728    /// wants them still has to check.
729    pub fn sample_surface_colored<R: Rng>(
730        &self,
731        count: usize,
732        rng: &mut R,
733    ) -> (Cloud, Cloud, Cloud) {
734        let faces = self.mesh.indices.len();
735        if faces == 0 || count == 0 {
736            return (Vec::new(), Vec::new(), Vec::new());
737        }
738        let colored = self.mesh.colors.len() == self.mesh.positions.len();
739        // Cumulative area, so a uniform draw lands in a face with probability
740        // proportional to its area.
741        let mut cumulative = Vec::with_capacity(faces);
742        let mut total = 0.0f32;
743        for face in 0..faces {
744            let [a, b, c] = self.mesh.triangle(face);
745            total += length(cross(sub(b, a), sub(c, a))) / 2.0;
746            cumulative.push(total);
747        }
748
749        let mut points = Vec::with_capacity(count);
750        let mut normals = Vec::with_capacity(count);
751        let mut colors = Vec::with_capacity(if colored { count } else { 0 });
752        for _ in 0..count {
753            let target = rng.gen_range(0.0..total.max(f32::MIN_POSITIVE));
754            let face = cumulative
755                .partition_point(|value| *value < target)
756                .min(faces - 1);
757            let [a, b, c] = self.mesh.triangle(face);
758            // The square root keeps the pair uniform over the triangle rather
759            // than bunched towards `a`.
760            let (u, v) = (rng.r#gen::<f32>().sqrt(), rng.r#gen::<f32>());
761            let point = add3(
762                add3(a, scale(sub(b, a), u * (1.0 - v))),
763                scale(sub(c, a), u * v),
764            );
765            points.push(point);
766            normals.push(normalize(cross(sub(b, a), sub(c, a))));
767            if colored {
768                // The same barycentric weights the point was built from.
769                let corners = self.mesh.indices[face];
770                let weights = [1.0 - u, u * (1.0 - v), u * v];
771                colors.push(std::array::from_fn(|channel| {
772                    (0..3)
773                        .map(|corner| {
774                            weights[corner] * self.mesh.colors[corners[corner] as usize][channel]
775                        })
776                        .sum()
777                }));
778            }
779        }
780        (points, normals, colors)
781    }
782
783    /// The query points a distance field is fitted on: some uniform in the box,
784    /// the rest hugging the surface.
785    pub fn sample_queries<R: Rng>(&self, config: &QuerySampling, rng: &mut R) -> Vec<[f32; 3]> {
786        let near = (config.count as f32 * config.near_surface.clamp(0.0, 1.0)) as usize;
787        let (surface, _) = self.sample_surface(near, rng);
788        let mut queries: Vec<[f32; 3]> = surface
789            .into_iter()
790            .map(|point| std::array::from_fn(|axis| point[axis] + gaussian(rng) * config.jitter))
791            .collect();
792        for _ in near..config.count {
793            queries.push(std::array::from_fn(|_| {
794                rng.gen_range(-config.extent..config.extent)
795            }));
796        }
797        queries
798    }
799}
800
801/// One standard normal, by Box-Muller. `rand_distr` would bring a dependency
802/// for three lines.
803fn gaussian<R: Rng>(rng: &mut R) -> f32 {
804    let uniform: f32 = rng.gen_range(f32::MIN_POSITIVE..1.0);
805    let angle: f32 = rng.gen_range(0.0..std::f32::consts::TAU);
806    (-2.0 * uniform.ln()).sqrt() * angle.cos()
807}
808
809// -- Back to a mesh ----------------------------------------------------------
810
811/// Turns a distance field into a mesh: the surface where it crosses `iso`.
812///
813/// `field` is handed a `[n, 3]` matrix of query points and returns one value
814/// per row, which is the shape a chunked decoder already speaks. It is called
815/// once per slab of the grid rather than once for the whole thing, so a
816/// `128³` grid never has all 2.1 million points resident at once.
817///
818/// NOTE: tetrahedra, not cubes. Each cell is cut into six tetrahedra, which
819/// have sixteen cases between them instead of a cube's 256, so the lookup table
820/// is four lines instead of three hundred and there is no ambiguous case to get
821/// wrong and leave a hole in. The cost is about twice the triangles for the
822/// same surface. Swap in the full marching-cubes tables if the triangle count
823/// ever matters more than the code does.
824pub fn marching_tetrahedra(
825    field: impl Fn(&Matrix) -> Result<Vec<f32>, NetworkError> + Sync,
826    resolution: usize,
827    bounds: ([f32; 3], [f32; 3]),
828    iso: f32,
829) -> Result<Mesh, NetworkError> {
830    let grid = Grid::new(resolution, bounds)?;
831    let mut mesh = Mesh::default();
832    let mut welded = HashMap::new();
833    let mut previous: Option<Vec<f32>> = None;
834
835    for z in 0..resolution {
836        let mut points = Matrix::new(grid.plane, 3);
837        for y in 0..resolution {
838            for x in 0..resolution {
839                points
840                    .row_mut(y * resolution + x)
841                    .copy_from_slice(&grid.at(x, y, z));
842            }
843        }
844        let values = grid.evaluate(&field, &points)?;
845        if let Some(lower) = previous {
846            grid.emit_cells(&mut mesh, &mut welded, iso, z, &lower, &values);
847        }
848        previous = Some(values);
849    }
850
851    mesh.recompute_normals();
852    Ok(mesh)
853}
854
855/// [`marching_tetrahedra`] with the empty space skipped, for a field that is
856/// expensive to evaluate.
857///
858/// The marcher itself costs almost nothing — two planes of values live at a
859/// time, so a `256³` grid holds 27 MB whatever the field is. What a high
860/// resolution costs is *calls*: `256³` is 16.7 million query points, and a
861/// decoder that answers a point in a few microseconds spends half an hour on
862/// them. Nearly all of those points are deep inside or far outside the shape,
863/// where there is nothing to find.
864///
865/// So this runs the grid twice. A coarse pass every `coarse` samples finds the
866/// cells the surface crosses; the fine pass evaluates only the points inside
867/// those cells and their immediate neighbours, and marches the fine cells whose
868/// eight corners it has. A sphere at `256³` with a `coarse` of 4 costs 1.6
869/// million query points instead of 16.7 million, and gives back the same mesh
870/// vertex for vertex.
871///
872/// The caveat is the one every hierarchical extractor has: a feature that fits
873/// entirely inside a coarse cell without crossing any of its corners is not
874/// seen, and the fine pass never looks there. `coarse` is the thickness of the
875/// thinnest wall this can find, in samples: 4 on a `256³` grid means a wall
876/// thinner than about 1/64 of the box may be missed. It is also what decides
877/// the saving, and the two pull the same way — a larger stride skips more
878/// coarse cells but each one drags in its 26 neighbours, so past about 4 the
879/// dilated cells start to overlap and the saving falls off. Use
880/// [`marching_tetrahedra`] when a thin wall matters more than the time.
881pub fn marching_tetrahedra_sparse(
882    field: impl Fn(&Matrix) -> Result<Vec<f32>, NetworkError> + Sync,
883    resolution: usize,
884    bounds: ([f32; 3], [f32; 3]),
885    iso: f32,
886    coarse: usize,
887) -> Result<Mesh, NetworkError> {
888    if coarse < 2 {
889        return Err(NetworkError::InvalidConfig(
890            "a coarse stride of one samples the whole grid twice; call \
891             marching_tetrahedra instead"
892                .into(),
893        ));
894    }
895    let grid = Grid::new(resolution, bounds)?;
896    let occupied = grid.coarse_pass(&field, iso, coarse)?;
897
898    let mut mesh = Mesh::default();
899    let mut welded = HashMap::new();
900    let mut previous: Option<Vec<f32>> = None;
901
902    for z in 0..resolution {
903        // A plane of values, `NaN` where the coarse pass said there is nothing
904        // to look at. A cell with a `NaN` corner is skipped rather than
905        // guessed at.
906        let mut values = vec![f32::NAN; grid.plane];
907        let mut wanted: Vec<usize> = Vec::new();
908        for y in 0..resolution {
909            for x in 0..resolution {
910                if occupied.holds(x, y, z) {
911                    wanted.push(y * resolution + x);
912                }
913            }
914        }
915        if !wanted.is_empty() {
916            let mut points = Matrix::new(wanted.len(), 3);
917            for (row, &index) in wanted.iter().enumerate() {
918                let (x, y) = (index % resolution, index / resolution);
919                points.row_mut(row).copy_from_slice(&grid.at(x, y, z));
920            }
921            let evaluated = grid.evaluate(&field, &points)?;
922            for (&index, value) in wanted.iter().zip(evaluated) {
923                values[index] = value;
924            }
925        }
926        if let Some(lower) = previous {
927            grid.emit_cells(&mut mesh, &mut welded, iso, z, &lower, &values);
928        }
929        previous = Some(values);
930    }
931
932    mesh.recompute_normals();
933    Ok(mesh)
934}
935
936/// The sample grid both marchers walk: where a sample sits, and how a cell
937/// between two planes becomes triangles.
938struct Grid {
939    resolution: usize,
940    plane: usize,
941    low: [f32; 3],
942    step: [f32; 3],
943}
944
945impl Grid {
946    fn new(resolution: usize, bounds: ([f32; 3], [f32; 3])) -> Result<Self, NetworkError> {
947        if resolution < 2 {
948            return Err(NetworkError::InvalidConfig(
949                "a grid needs at least two samples along each axis".into(),
950            ));
951        }
952        let (low, high) = bounds;
953        Ok(Self {
954            resolution,
955            plane: resolution * resolution,
956            low,
957            step: std::array::from_fn(|axis| (high[axis] - low[axis]) / (resolution - 1) as f32),
958        })
959    }
960
961    fn at(&self, x: usize, y: usize, z: usize) -> [f32; 3] {
962        [
963            self.low[0] + x as f32 * self.step[0],
964            self.low[1] + y as f32 * self.step[1],
965            self.low[2] + z as f32 * self.step[2],
966        ]
967    }
968
969    /// One call into the field, with the row count checked: a field that
970    /// answers a different number of points than it was asked would otherwise
971    /// silently shift every value onto the wrong grid corner.
972    fn evaluate(
973        &self,
974        field: &(impl Fn(&Matrix) -> Result<Vec<f32>, NetworkError> + Sync),
975        points: &Matrix,
976    ) -> Result<Vec<f32>, NetworkError> {
977        let values = field(points)?;
978        if values.len() != points.rows {
979            return Err(NetworkError::InvalidTarget {
980                expected: points.rows,
981                actual: values.len(),
982            });
983        }
984        Ok(values)
985    }
986
987    /// Marches every cell between plane `z - 1` and plane `z`, skipping the
988    /// ones a sparse pass left unevaluated.
989    fn emit_cells(
990        &self,
991        mesh: &mut Mesh,
992        welded: &mut HashMap<(u32, u32), u32>,
993        iso: f32,
994        z: usize,
995        lower: &[f32],
996        upper: &[f32],
997    ) {
998        let resolution = self.resolution;
999        for y in 0..resolution - 1 {
1000            for x in 0..resolution - 1 {
1001                // The eight corners, in the order CUBE_TETRAHEDRA indexes.
1002                let corners = [
1003                    (x, y, z - 1),
1004                    (x + 1, y, z - 1),
1005                    (x + 1, y + 1, z - 1),
1006                    (x, y + 1, z - 1),
1007                    (x, y, z),
1008                    (x + 1, y, z),
1009                    (x + 1, y + 1, z),
1010                    (x, y + 1, z),
1011                ];
1012                let value = |corner: usize| {
1013                    let (cx, cy, _) = corners[corner];
1014                    let index = cy * resolution + cx;
1015                    match corner < 4 {
1016                        true => lower[index],
1017                        false => upper[index],
1018                    }
1019                };
1020                if (0..8).any(|corner| value(corner).is_nan()) {
1021                    continue;
1022                }
1023
1024                for tetrahedron in CUBE_TETRAHEDRA {
1025                    emit_tetrahedron(
1026                        mesh,
1027                        welded,
1028                        iso,
1029                        tetrahedron.map(|corner| {
1030                            let (cx, cy, cz) = corners[corner];
1031                            let identity = (cz * self.plane + cy * resolution + cx) as u32;
1032                            (identity, self.at(cx, cy, cz), value(corner))
1033                        }),
1034                    );
1035                }
1036            }
1037        }
1038    }
1039
1040    /// Walks the grid every `coarse` samples and reports which coarse cells the
1041    /// surface passes through, each one grown by a cell in every direction so
1042    /// that a fine cell inside a marked one always has all eight of its corners
1043    /// evaluated.
1044    fn coarse_pass(
1045        &self,
1046        field: &(impl Fn(&Matrix) -> Result<Vec<f32>, NetworkError> + Sync),
1047        iso: f32,
1048        coarse: usize,
1049    ) -> Result<Occupancy, NetworkError> {
1050        let cells = (self.resolution - 1).div_ceil(coarse);
1051        let samples = cells + 1;
1052        let sample_at = |index: usize| (index * coarse).min(self.resolution - 1);
1053
1054        let mut straddles = vec![false; cells * cells * cells];
1055        let mut previous: Option<Vec<f32>> = None;
1056        for k in 0..samples {
1057            let mut points = Matrix::new(samples * samples, 3);
1058            for j in 0..samples {
1059                for i in 0..samples {
1060                    points.row_mut(j * samples + i).copy_from_slice(&self.at(
1061                        sample_at(i),
1062                        sample_at(j),
1063                        sample_at(k),
1064                    ));
1065                }
1066            }
1067            let values = self.evaluate(field, &points)?;
1068            if let Some(lower) = previous {
1069                for j in 0..cells {
1070                    for i in 0..cells {
1071                        let corners = [
1072                            lower[j * samples + i],
1073                            lower[j * samples + i + 1],
1074                            lower[(j + 1) * samples + i],
1075                            lower[(j + 1) * samples + i + 1],
1076                            values[j * samples + i],
1077                            values[j * samples + i + 1],
1078                            values[(j + 1) * samples + i],
1079                            values[(j + 1) * samples + i + 1],
1080                        ];
1081                        let inside = corners.iter().any(|&value| value < iso);
1082                        let outside = corners.iter().any(|&value| value >= iso);
1083                        if inside && outside {
1084                            straddles[(k - 1) * cells * cells + j * cells + i] = true;
1085                        }
1086                    }
1087                }
1088            }
1089            previous = Some(values);
1090        }
1091
1092        Ok(Occupancy::dilated(straddles, cells, coarse))
1093    }
1094}
1095
1096/// Which coarse cells the fine pass has to look inside.
1097struct Occupancy {
1098    marked: Vec<bool>,
1099    cells: usize,
1100    coarse: usize,
1101}
1102
1103impl Occupancy {
1104    /// Grows every marked cell into its 26 neighbours. A fine cell sitting at
1105    /// the edge of a marked coarse cell reaches one sample into the next one,
1106    /// so without this its far corners would be `NaN` and the cell would be
1107    /// dropped — a seam along every coarse boundary.
1108    fn dilated(straddles: Vec<bool>, cells: usize, coarse: usize) -> Self {
1109        let mut marked = vec![false; straddles.len()];
1110        for k in 0..cells {
1111            for j in 0..cells {
1112                for i in 0..cells {
1113                    marked[k * cells * cells + j * cells + i] = (-1i64..=1).any(|dk| {
1114                        (-1i64..=1).any(|dj| {
1115                            (-1i64..=1).any(|di| {
1116                                let (ni, nj, nk) = (i as i64 + di, j as i64 + dj, k as i64 + dk);
1117                                let inside = |value: i64| (0..cells as i64).contains(&value);
1118                                inside(ni)
1119                                    && inside(nj)
1120                                    && inside(nk)
1121                                    && straddles[nk as usize * cells * cells
1122                                        + nj as usize * cells
1123                                        + ni as usize]
1124                            })
1125                        })
1126                    });
1127                }
1128            }
1129        }
1130        Self {
1131            marked,
1132            cells,
1133            coarse,
1134        }
1135    }
1136
1137    /// Whether the fine sample at `(x, y, z)` is worth evaluating.
1138    fn holds(&self, x: usize, y: usize, z: usize) -> bool {
1139        let cell = |index: usize| (index / self.coarse).min(self.cells - 1);
1140        self.marked[cell(z) * self.cells * self.cells + cell(y) * self.cells + cell(x)]
1141    }
1142}
1143
1144#[cfg(test)]
1145mod sparse_tests {
1146    use super::*;
1147    use std::sync::atomic::{AtomicUsize, Ordering};
1148
1149    /// A sphere of radius 0.6, and a count of how many points it was asked for.
1150    fn sphere(
1151        radius: f32,
1152        asked: &AtomicUsize,
1153    ) -> impl Fn(&Matrix) -> Result<Vec<f32>, NetworkError> + Sync {
1154        move |points: &Matrix| {
1155            asked.fetch_add(points.rows, Ordering::Relaxed);
1156            Ok((0..points.rows)
1157                .map(|row| {
1158                    let point = points.row(row);
1159                    (point[0] * point[0] + point[1] * point[1] + point[2] * point[2]).sqrt()
1160                        - radius
1161                })
1162                .collect())
1163        }
1164    }
1165
1166    #[test]
1167    fn skipping_the_empty_space_gives_the_same_mesh_as_marching_all_of_it() {
1168        let bounds = ([-1.0; 3], [1.0; 3]);
1169        let dense_calls = AtomicUsize::new(0);
1170        let dense = marching_tetrahedra(sphere(0.6, &dense_calls), 64, bounds, 0.0).unwrap();
1171
1172        let sparse_calls = AtomicUsize::new(0);
1173        let sparse =
1174            marching_tetrahedra_sparse(sphere(0.6, &sparse_calls), 64, bounds, 0.0, 4).unwrap();
1175
1176        assert!(!dense.indices.is_empty(), "the sphere crosses the grid");
1177        assert_eq!(sparse.positions, dense.positions);
1178        assert_eq!(sparse.indices, dense.indices);
1179        assert_eq!(sparse.normals, dense.normals);
1180        assert!(
1181            sparse_calls.load(Ordering::Relaxed) * 2 < dense_calls.load(Ordering::Relaxed),
1182            "the sparse pass asked for {} points against {}",
1183            sparse_calls.load(Ordering::Relaxed),
1184            dense_calls.load(Ordering::Relaxed)
1185        );
1186    }
1187
1188    #[test]
1189    fn a_shell_thinner_than_a_coarse_cell_needs_the_dense_marcher() {
1190        // The documented caveat, pinned: a shell 1/64 of the box thick sits
1191        // inside a coarse cell of 8 samples and the coarse pass steps over it.
1192        let bounds = ([-1.0; 3], [1.0; 3]);
1193        let shell = |points: &Matrix| -> Result<Vec<f32>, NetworkError> {
1194            Ok((0..points.rows)
1195                .map(|row| {
1196                    let point = points.row(row);
1197                    let radius =
1198                        (point[0] * point[0] + point[1] * point[1] + point[2] * point[2]).sqrt();
1199                    (radius - 0.6).abs() - 0.015
1200                })
1201                .collect())
1202        };
1203        let dense = marching_tetrahedra(shell, 64, bounds, 0.0).unwrap();
1204        let sparse = marching_tetrahedra_sparse(shell, 64, bounds, 0.0, 8).unwrap();
1205        assert!(!dense.indices.is_empty());
1206        assert!(sparse.indices.len() < dense.indices.len());
1207    }
1208
1209    #[test]
1210    fn a_coarse_stride_of_one_is_refused() {
1211        let asked = AtomicUsize::new(0);
1212        let error =
1213            marching_tetrahedra_sparse(sphere(0.6, &asked), 16, ([-1.0; 3], [1.0; 3]), 0.0, 1);
1214        assert!(matches!(error, Err(NetworkError::InvalidConfig(_))));
1215    }
1216
1217    #[test]
1218    fn a_grid_of_one_sample_is_refused_by_both_marchers() {
1219        let asked = AtomicUsize::new(0);
1220        let bounds = ([-1.0; 3], [1.0; 3]);
1221        assert!(marching_tetrahedra(sphere(0.6, &asked), 1, bounds, 0.0).is_err());
1222        assert!(marching_tetrahedra_sparse(sphere(0.6, &asked), 1, bounds, 0.0, 4).is_err());
1223    }
1224}
1225
1226/// The six tetrahedra a cube is cut into, as corner indices. Every one of them
1227/// shares the cube's `0`-`6` diagonal, which is what makes the cut consistent
1228/// between neighbouring cells and the result watertight.
1229const CUBE_TETRAHEDRA: [[usize; 4]; 6] = [
1230    [0, 5, 1, 6],
1231    [0, 1, 2, 6],
1232    [0, 2, 3, 6],
1233    [0, 3, 7, 6],
1234    [0, 7, 4, 6],
1235    [0, 4, 5, 6],
1236];
1237
1238/// The six edges of a tetrahedron, as pairs of its corners.
1239const TETRAHEDRON_EDGES: [(usize, usize); 6] = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)];
1240
1241/// Which edges the surface crosses, and how they join up, for each of the
1242/// sixteen ways four corners can be inside or outside.
1243///
1244/// One triangle when a single corner is on its own, two when the corners split
1245/// two and two. `usize::MAX` ends the list.
1246const TETRAHEDRON_TABLE: [[usize; 6]; 16] = [
1247    [usize::MAX; 6],
1248    [0, 1, 2, usize::MAX, usize::MAX, usize::MAX],
1249    [0, 3, 4, usize::MAX, usize::MAX, usize::MAX],
1250    [1, 2, 4, 1, 4, 3],
1251    [1, 3, 5, usize::MAX, usize::MAX, usize::MAX],
1252    [0, 2, 5, 0, 5, 3],
1253    [0, 1, 5, 0, 5, 4],
1254    [2, 5, 4, usize::MAX, usize::MAX, usize::MAX],
1255    [2, 4, 5, usize::MAX, usize::MAX, usize::MAX],
1256    [0, 4, 5, 0, 5, 1],
1257    [0, 5, 2, 0, 3, 5],
1258    [1, 5, 3, usize::MAX, usize::MAX, usize::MAX],
1259    [1, 4, 2, 1, 3, 4],
1260    [0, 4, 3, usize::MAX, usize::MAX, usize::MAX],
1261    [0, 2, 1, usize::MAX, usize::MAX, usize::MAX],
1262    [usize::MAX; 6],
1263];
1264
1265/// Adds whatever of the surface passes through one tetrahedron.
1266fn emit_tetrahedron(
1267    mesh: &mut Mesh,
1268    welded: &mut HashMap<(u32, u32), u32>,
1269    iso: f32,
1270    corners: [(u32, [f32; 3], f32); 4],
1271) {
1272    let mut code = 0usize;
1273    for (bit, (_, _, value)) in corners.iter().enumerate() {
1274        if *value < iso {
1275            code |= 1 << bit;
1276        }
1277    }
1278    let table = TETRAHEDRON_TABLE[code];
1279    if table[0] == usize::MAX {
1280        return;
1281    }
1282    // Outside centroid minus inside centroid, unnormalized: only its sign
1283    // against a face normal is read.
1284    let outward = corners
1285        .iter()
1286        .enumerate()
1287        .fold([0.0; 3], |sum, (bit, (_, point, _))| {
1288            let inside = code & (1 << bit) != 0;
1289            let weight = match inside {
1290                true => -1.0 / code.count_ones() as f32,
1291                false => 1.0 / (4 - code.count_ones()) as f32,
1292            };
1293            add3(sum, scale(*point, weight))
1294        });
1295
1296    let mut vertex = |edge: usize| -> u32 {
1297        let (from, to) = TETRAHEDRON_EDGES[edge];
1298        let (first, second) = (corners[from], corners[to]);
1299        // The key is the pair of grid corners, smaller first, so the two cells
1300        // either side of the edge agree on it.
1301        let key = match first.0 < second.0 {
1302            true => (first.0, second.0),
1303            false => (second.0, first.0),
1304        };
1305        if let Some(index) = welded.get(&key) {
1306            return *index;
1307        }
1308        let span = second.2 - first.2;
1309        // Where the field crosses the isovalue, linearly. A flat edge is cut in
1310        // half, which is arbitrary but keeps the vertex on the edge.
1311        let t = match span == 0.0 {
1312            true => 0.5,
1313            false => ((iso - first.2) / span).clamp(0.0, 1.0),
1314        };
1315        let point = add3(first.1, scale(sub(second.1, first.1), t));
1316        let index = mesh.positions.len() as u32;
1317        mesh.positions.push(point);
1318        welded.insert(key, index);
1319        index
1320    };
1321
1322    let mut faces = Vec::with_capacity(2);
1323    for triangle in table.as_chunks::<3>().0 {
1324        if triangle[0] == usize::MAX {
1325            break;
1326        }
1327        let face = [
1328            vertex(triangle[0]),
1329            vertex(triangle[1]),
1330            vertex(triangle[2]),
1331        ];
1332        // A tetrahedron with two corners at exactly the isovalue can produce a
1333        // triangle with a repeated vertex, which is not a face.
1334        if face[0] != face[1] && face[1] != face[2] && face[0] != face[2] {
1335            faces.push(face);
1336        }
1337    }
1338    for face in faces {
1339        // Wind it so the normal points from the inside corners to the outside
1340        // ones, which the table alone does not guarantee.
1341        let [a, b, c] = face.map(|index| mesh.positions[index as usize]);
1342        let normal = cross(sub(b, a), sub(c, a));
1343        mesh.indices.push(match dot(normal, outward) < 0.0 {
1344            true => [face[0], face[2], face[1]],
1345            false => face,
1346        });
1347    }
1348}
1349
1350/// Mean of the two one-sided nearest-neighbour distances between two point
1351/// sets, which is how a reconstruction is scored against its original.
1352///
1353/// Symmetric on purpose: the one-sided distance alone is happy with a
1354/// reconstruction that covers part of the shape very well and leaves the rest
1355/// off entirely.
1356pub fn chamfer_distance(a: &[[f32; 3]], b: &[[f32; 3]]) -> f32 {
1357    fn one_sided(from: &[[f32; 3]], to: &[[f32; 3]]) -> f32 {
1358        from.par_iter()
1359            .map(|point| {
1360                to.iter()
1361                    .map(|other| length(sub(*point, *other)))
1362                    .fold(f32::INFINITY, f32::min)
1363            })
1364            .sum::<f32>()
1365            / from.len().max(1) as f32
1366    }
1367    (one_sided(a, b) + one_sided(b, a)) / 2.0
1368}
1369
1370#[cfg(test)]
1371mod tests {
1372    use super::*;
1373    use rand::SeedableRng;
1374    use rand::rngs::StdRng;
1375
1376    /// A sphere as a latitude-longitude grid, which gives the tests a mesh with
1377    /// a distance field they can check against arithmetic.
1378    fn sphere(radius: f32, rings: usize, segments: usize) -> Mesh {
1379        let mut mesh = Mesh::default();
1380        for ring in 0..=rings {
1381            let phi = std::f32::consts::PI * ring as f32 / rings as f32;
1382            for segment in 0..=segments {
1383                let theta = std::f32::consts::TAU * segment as f32 / segments as f32;
1384                mesh.positions.push([
1385                    radius * phi.sin() * theta.cos(),
1386                    radius * phi.cos(),
1387                    radius * phi.sin() * theta.sin(),
1388                ]);
1389            }
1390        }
1391        let stride = segments + 1;
1392        for ring in 0..rings {
1393            for segment in 0..segments {
1394                let a = (ring * stride + segment) as u32;
1395                let (b, c, d) = (a + 1, a + stride as u32, a + stride as u32 + 1);
1396                // Wound so the normals point out of the sphere.
1397                mesh.indices.push([a, b, c]);
1398                mesh.indices.push([b, d, c]);
1399            }
1400        }
1401        mesh
1402    }
1403
1404    /// An axis-aligned box, which has flat faces and sharp edges where a sphere
1405    /// has neither.
1406    fn cube(half: f32) -> Mesh {
1407        let mut mesh = Mesh::default();
1408        for corner in 0..8 {
1409            mesh.positions.push([
1410                if corner & 1 == 0 { -half } else { half },
1411                if corner & 2 == 0 { -half } else { half },
1412                if corner & 4 == 0 { -half } else { half },
1413            ]);
1414        }
1415        // Two triangles per face, wound so the normals point outwards.
1416        for face in [
1417            [0, 2, 1, 3],
1418            [4, 5, 6, 7],
1419            [0, 1, 4, 5],
1420            [2, 6, 3, 7],
1421            [0, 4, 2, 6],
1422            [1, 3, 5, 7],
1423        ] {
1424            mesh.indices.push([face[0], face[1], face[2]]);
1425            mesh.indices.push([face[1], face[3], face[2]]);
1426        }
1427        mesh
1428    }
1429
1430    #[test]
1431    fn normalizing_fills_the_cube_without_changing_the_shape() {
1432        let mut mesh = sphere(3.0, 8, 12);
1433        for position in &mut mesh.positions {
1434            position[0] += 10.0;
1435        }
1436        let transform = mesh.normalize();
1437        let (low, high) = mesh.bounds();
1438        for axis in 0..3 {
1439            assert!((low[axis] + 1.0).abs() < 1e-5, "{low:?}");
1440            assert!((high[axis] - 1.0).abs() < 1e-5, "{high:?}");
1441        }
1442        // The transform puts a point back where it came from.
1443        let restored = transform.invert(mesh.positions[0]);
1444        assert!((restored[0] - 10.0).abs() < 1e-3, "{restored:?}");
1445    }
1446
1447    #[test]
1448    fn the_winding_number_separates_inside_from_outside() {
1449        let mesh = cube(1.0);
1450        let bvh = Bvh::build(&mesh);
1451        for point in [[0.0, 0.0, 0.0], [0.5, -0.5, 0.25], [0.9, 0.9, 0.9]] {
1452            let winding = bvh.winding_number(point);
1453            assert!((winding - 1.0).abs() < 0.05, "{point:?} read {winding}");
1454        }
1455        for point in [[2.0, 0.0, 0.0], [0.0, -3.0, 0.0], [1.5, 1.5, 1.5]] {
1456            let winding = bvh.winding_number(point);
1457            assert!(winding.abs() < 0.05, "{point:?} read {winding}");
1458        }
1459    }
1460
1461    #[test]
1462    fn a_holed_mesh_still_classifies_its_interior() {
1463        // A ray cast needs a closed surface to count crossings against, which
1464        // is the case this is here to cover: drop a face and the answer should
1465        // still be close to one deep inside.
1466        let mut mesh = cube(1.0);
1467        mesh.indices.truncate(mesh.indices.len() - 2);
1468        let bvh = Bvh::build(&mesh);
1469        assert!(bvh.winding_number([0.0, 0.0, 0.0]) > 0.7);
1470        assert!(bvh.winding_number([4.0, 0.0, 0.0]).abs() < 0.05);
1471    }
1472
1473    #[test]
1474    fn the_signed_distance_to_a_sphere_is_the_radius_minus_the_offset() {
1475        let mesh = sphere(1.0, 64, 128);
1476        let bvh = Bvh::build(&mesh);
1477        let queries = [
1478            [0.0, 0.0, 0.0],
1479            [0.5, 0.0, 0.0],
1480            [1.5, 0.0, 0.0],
1481            [0.0, 2.0, 0.0],
1482        ];
1483        let distances = bvh.signed_distance(&queries);
1484        for (query, distance) in queries.iter().zip(&distances) {
1485            let expected = length(*query) - 1.0;
1486            // The mesh is a polyhedron inscribed in the sphere, so it sits a
1487            // little inside it.
1488            assert!(
1489                (distance - expected).abs() < 0.01,
1490                "{query:?}: {distance} against {expected}"
1491            );
1492        }
1493    }
1494
1495    /// Colours interpolate linearly across a face, so a mesh whose colour is a
1496    /// linear function of position must sample back as that same function.
1497    #[test]
1498    fn a_sampled_colour_is_the_colour_at_the_sampled_point() {
1499        let mesh = Mesh {
1500            positions: vec![[0.0, 0.0, 0.0], [1.0, 0.0, 0.0], [0.0, 1.0, 0.0]],
1501            indices: vec![[0, 1, 2]],
1502            colors: vec![[0.0, 0.0, 0.5], [1.0, 0.0, 0.5], [0.0, 1.0, 0.5]],
1503            ..Mesh::default()
1504        };
1505        let bvh = Bvh::build(&mesh);
1506        let mut rng = StdRng::seed_from_u64(7);
1507
1508        let (points, _, colors) = bvh.sample_surface_colored(128, &mut rng);
1509        assert_eq!(colors.len(), points.len());
1510        for (point, color) in points.iter().zip(&colors) {
1511            assert!((color[0] - point[0]).abs() < 1e-5);
1512            assert!((color[1] - point[1]).abs() < 1e-5);
1513            assert!((color[2] - 0.5).abs() < 1e-5);
1514        }
1515    }
1516
1517    #[test]
1518    fn surface_samples_land_on_the_surface_and_spread_over_it() {
1519        let mesh = sphere(1.0, 32, 64);
1520        let bvh = Bvh::build(&mesh);
1521        let mut rng = StdRng::seed_from_u64(7);
1522        let (points, normals) = bvh.sample_surface(2_000, &mut rng);
1523        assert_eq!(points.len(), 2_000);
1524        for (point, normal) in points.iter().zip(&normals) {
1525            assert!((length(*point) - 1.0).abs() < 0.01, "{point:?}");
1526            // Outward winding means the normal points away from the centre.
1527            assert!(dot(*normal, *point) > 0.0, "{normal:?} at {point:?}");
1528        }
1529        // Area weighting means every octant gets samples; weighting by face
1530        // would crowd them around the poles, where the rings are finest.
1531        let mut octants = [0usize; 8];
1532        for point in &points {
1533            let index = (point[0] > 0.0) as usize
1534                | ((point[1] > 0.0) as usize) << 1
1535                | ((point[2] > 0.0) as usize) << 2;
1536            octants[index] += 1;
1537        }
1538        assert!(octants.iter().all(|count| *count > 150), "{octants:?}");
1539    }
1540
1541    #[test]
1542    fn query_points_split_between_the_surface_and_the_box() {
1543        let mesh = sphere(1.0, 16, 32);
1544        let bvh = Bvh::build(&mesh);
1545        let mut rng = StdRng::seed_from_u64(11);
1546        let config = QuerySampling {
1547            count: 4_000,
1548            near_surface: 0.75,
1549            jitter: 0.01,
1550            extent: 1.1,
1551        };
1552        let queries = bvh.sample_queries(&config, &mut rng);
1553        assert_eq!(queries.len(), 4_000);
1554        let near = queries
1555            .iter()
1556            .filter(|point| (length(**point) - 1.0).abs() < 0.05)
1557            .count();
1558        // Every near-surface point is close, and a few uniform ones land close
1559        // by chance, so the count is at least the near-surface share.
1560        assert!(near >= 3_000, "{near} of 4000 near the surface");
1561        assert!(
1562            queries
1563                .iter()
1564                .all(|point| point.iter().all(|value| value.abs() <= 1.2)),
1565            "a query left the box"
1566        );
1567    }
1568
1569    #[test]
1570    fn marching_tetrahedra_puts_vertices_on_the_isosurface() {
1571        let mesh = marching_tetrahedra(
1572            |points| {
1573                Ok((0..points.rows)
1574                    .map(|row| {
1575                        let point = points.row(row);
1576                        (point[0] * point[0] + point[1] * point[1] + point[2] * point[2]).sqrt()
1577                            - 0.6
1578                    })
1579                    .collect())
1580            },
1581            24,
1582            ([-1.0; 3], [1.0; 3]),
1583            0.0,
1584        )
1585        .unwrap();
1586
1587        assert!(!mesh.indices.is_empty());
1588        for position in &mesh.positions {
1589            // A vertex is placed by linear interpolation along a grid edge, so
1590            // it is off by the curvature over one cell.
1591            assert!((length(*position) - 0.6).abs() < 0.02, "{position:?}");
1592        }
1593        assert_eq!(mesh.normals.len(), mesh.positions.len());
1594    }
1595
1596    #[test]
1597    fn marching_tetrahedra_winds_every_face_outward() {
1598        let sphere = |points: &Matrix| {
1599            Ok((0..points.rows)
1600                .map(|row| {
1601                    let p = points.row(row);
1602                    length([p[0], p[1], p[2]]) - 0.6
1603                })
1604                .collect())
1605        };
1606        let bounds = ([-1.0; 3], [1.0; 3]);
1607        for mesh in [
1608            marching_tetrahedra(sphere, 48, bounds, 0.0).unwrap(),
1609            marching_tetrahedra_sparse(sphere, 48, bounds, 0.0, 4).unwrap(),
1610        ] {
1611            for face in &mesh.indices {
1612                let [a, b, c] = face.map(|index| mesh.positions[index as usize]);
1613                let centroid = scale(add3(add3(a, b), c), 1.0 / 3.0);
1614                // The field's gradient is the direction from the centre.
1615                assert!(dot(cross(sub(b, a), sub(c, a)), centroid) > 0.0, "{face:?}");
1616            }
1617            let inside = Bvh::build(&mesh).winding_number([0.1, -0.2, 0.05]);
1618            // The tree approximates far clusters, so this is near one, not exact;
1619            // inward faces would give minus one.
1620            assert!((inside - 1.0).abs() < 0.05, "winding number {inside}");
1621        }
1622    }
1623
1624    #[test]
1625    fn the_reconstructed_surface_is_watertight() {
1626        let mesh = marching_tetrahedra(
1627            |points| {
1628                Ok((0..points.rows)
1629                    .map(|row| {
1630                        let point = points.row(row);
1631                        point[0].abs().max(point[1].abs()).max(point[2].abs()) - 0.5
1632                    })
1633                    .collect())
1634            },
1635            16,
1636            ([-1.0; 3], [1.0; 3]),
1637            0.0,
1638        )
1639        .unwrap();
1640
1641        // Every edge shared by exactly two faces is what closed means, and it
1642        // is the property the shared-vertex welding is there to give.
1643        let mut edges: HashMap<(u32, u32), usize> = HashMap::new();
1644        for face in &mesh.indices {
1645            for corner in 0..3 {
1646                let (a, b) = (face[corner], face[(corner + 1) % 3]);
1647                *edges.entry((a.min(b), a.max(b))).or_default() += 1;
1648            }
1649        }
1650        let open = edges.values().filter(|count| **count != 2).count();
1651        assert_eq!(open, 0, "{open} edges are not shared by two faces");
1652    }
1653
1654    #[test]
1655    fn a_mesh_survives_a_trip_through_its_own_distance_field() {
1656        // The check the whole stage exists for: sample a mesh's signed
1657        // distance, rebuild a mesh from it, and compare the two surfaces.
1658        let mut original = sphere(0.8, 24, 48);
1659        original.normalize();
1660        let bvh = Bvh::build(&original);
1661
1662        let rebuilt = marching_tetrahedra(
1663            |points| {
1664                let queries: Vec<[f32; 3]> = (0..points.rows)
1665                    .map(|row| {
1666                        let row = points.row(row);
1667                        [row[0], row[1], row[2]]
1668                    })
1669                    .collect();
1670                Ok(bvh.signed_distance(&queries))
1671            },
1672            48,
1673            ([-1.2; 3], [1.2; 3]),
1674            0.0,
1675        )
1676        .unwrap();
1677
1678        // Point to surface rather than point to point: two independent clouds
1679        // of a few thousand samples are about 0.06 apart on a unit sphere
1680        // purely from where the samples landed, which would swamp the error
1681        // being measured.
1682        let mut rng = StdRng::seed_from_u64(3);
1683        let rebuilt_bvh = Bvh::build(&rebuilt);
1684        let (samples, _) = bvh.sample_surface(3_000, &mut rng);
1685        let onto_rebuilt = samples
1686            .iter()
1687            .map(|point| rebuilt_bvh.closest_point(*point).unwrap().1)
1688            .fold(0.0f32, f32::max);
1689        let onto_original = rebuilt
1690            .positions
1691            .iter()
1692            .map(|point| bvh.closest_point(*point).unwrap().1)
1693            .fold(0.0f32, f32::max);
1694
1695        // The grid is 48 samples over 2.4 units, so a cell is 0.051 across and
1696        // a vertex placed by interpolating along one edge is off by the
1697        // curvature over that cell.
1698        assert!(onto_rebuilt < 0.02, "original to rebuilt {onto_rebuilt}");
1699        assert!(onto_original < 0.02, "rebuilt to original {onto_original}");
1700    }
1701
1702    #[test]
1703    fn the_chamfer_distance_is_zero_for_a_cloud_against_itself() {
1704        let mesh = sphere(1.0, 16, 32);
1705        let bvh = Bvh::build(&mesh);
1706        let mut rng = StdRng::seed_from_u64(5);
1707        let (points, _) = bvh.sample_surface(500, &mut rng);
1708        assert!(chamfer_distance(&points, &points) < 1e-6);
1709
1710        // A rigid shift moves every nearest neighbour by the same amount, so
1711        // the answer is the shift itself.
1712        let shifted: Vec<[f32; 3]> = points
1713            .iter()
1714            .map(|point| [point[0] + 0.1, point[1], point[2]])
1715            .collect();
1716        let distance = chamfer_distance(&points, &shifted);
1717        assert!(distance > 0.05 && distance <= 0.1, "{distance}");
1718    }
1719
1720    #[test]
1721    fn an_obj_file_round_trips() {
1722        let path =
1723            std::env::temp_dir().join(format!("rusting-brain-mesh-{}.obj", std::process::id()));
1724        let mut original = cube(1.0);
1725        original.recompute_normals();
1726        original.write_obj(&path).unwrap();
1727
1728        let read = Mesh::read_obj(&path).unwrap();
1729        assert_eq!(read.indices.len(), original.indices.len());
1730        assert_eq!(read.positions.len(), original.positions.len());
1731        // The reader renumbers vertices in the order the faces first name
1732        // them, so the faces are what has to match, not the vertex list.
1733        for face in 0..read.indices.len() {
1734            for (a, b) in read.triangle(face).iter().zip(&original.triangle(face)) {
1735                assert!(length(sub(*a, *b)) < 1e-6, "{a:?} against {b:?}");
1736            }
1737        }
1738        assert_eq!(read.normals.len(), read.positions.len());
1739        std::fs::remove_file(&path).ok();
1740    }
1741
1742    #[test]
1743    fn a_quad_face_is_triangulated_and_a_negative_index_counts_back() {
1744        let path =
1745            std::env::temp_dir().join(format!("rusting-brain-quad-{}.obj", std::process::id()));
1746        std::fs::write(&path, "v 0 0 0\nv 1 0 0\nv 1 1 0\nv 0 1 0\nf -4 -3 -2 -1\n").unwrap();
1747        let mesh = Mesh::read_obj(&path).unwrap();
1748        assert_eq!(mesh.indices.len(), 2, "a quad is two triangles");
1749        assert_eq!(mesh.positions.len(), 4);
1750        std::fs::remove_file(&path).ok();
1751    }
1752
1753    #[test]
1754    fn an_obj_texture_coordinate_is_flipped_into_the_gltf_convention() {
1755        let path =
1756            std::env::temp_dir().join(format!("rusting-brain-uv-{}.obj", std::process::id()));
1757        std::fs::write(
1758            &path,
1759            "v 0 0 0\nv 1 0 0\nv 1 1 0\nvt 0 0\nvt 1 0.25\nvt 1 1\nf 1/1 2/2 3/3\n",
1760        )
1761        .unwrap();
1762        let mesh = Mesh::read_obj(&path).unwrap();
1763        assert_eq!(mesh.uvs, vec![[0.0, 1.0], [1.0, 0.75], [1.0, 0.0]]);
1764        std::fs::remove_file(&path).ok();
1765    }
1766
1767    #[test]
1768    fn a_file_with_no_faces_is_refused() {
1769        let path =
1770            std::env::temp_dir().join(format!("rusting-brain-empty-{}.obj", std::process::id()));
1771        std::fs::write(&path, "v 0 0 0\nv 1 0 0\n").unwrap();
1772        assert!(Mesh::read_obj(&path).is_err());
1773        std::fs::remove_file(&path).ok();
1774    }
1775}
1776
1777// -- Simplification ----------------------------------------------------------
1778
1779/// A symmetric 4x4 quadric, as its ten distinct coefficients.
1780///
1781/// The order is the upper triangle read row by row: `a2 ab ac ad b2 bc bd c2
1782/// cd d2`, where `(a, b, c, d)` is a plane with a unit normal. The error at a
1783/// point is `v^T Q v` with `v = (x, y, z, 1)`, which is the sum of squared
1784/// distances to every plane that went into it.
1785type Quadric = [f32; 10];
1786
1787/// The quadric of one plane, scaled by how much surface it stands for.
1788fn plane_quadric(normal: [f32; 3], point: [f32; 3], weight: f32) -> Quadric {
1789    let [a, b, c] = normal;
1790    let d = -dot(normal, point);
1791    [
1792        a * a,
1793        a * b,
1794        a * c,
1795        a * d,
1796        b * b,
1797        b * c,
1798        b * d,
1799        c * c,
1800        c * d,
1801        d * d,
1802    ]
1803    .map(|value| value * weight)
1804}
1805
1806fn add_quadric(left: Quadric, right: Quadric) -> Quadric {
1807    std::array::from_fn(|index| left[index] + right[index])
1808}
1809
1810/// `v^T Q v`, the squared distance to the planes the quadric was built from.
1811fn quadric_error(quadric: Quadric, [x, y, z]: [f32; 3]) -> f32 {
1812    let [a2, ab, ac, ad, b2, bc, bd, c2, cd, d2] = quadric;
1813    a2 * x * x
1814        + 2.0 * ab * x * y
1815        + 2.0 * ac * x * z
1816        + 2.0 * ad * x
1817        + b2 * y * y
1818        + 2.0 * bc * y * z
1819        + 2.0 * bd * y
1820        + c2 * z * z
1821        + 2.0 * cd * z
1822        + d2
1823}
1824
1825/// The point that minimizes the quadric, if there is a unique one.
1826///
1827/// The minimum is where the gradient vanishes, which is a 3x3 solve. A flat
1828/// region or a straight edge leaves the system singular — there is a whole
1829/// plane or line of equally good answers — and the caller falls back to
1830/// picking the best of the candidates it already has.
1831fn quadric_minimum(quadric: Quadric) -> Option<[f32; 3]> {
1832    let [a2, ab, ac, ad, b2, bc, bd, c2, cd, _] = quadric;
1833    let matrix = [[a2, ab, ac], [ab, b2, bc], [ac, bc, c2]];
1834    let rhs = [-ad, -bd, -cd];
1835
1836    let determinant = matrix[0][0] * (matrix[1][1] * matrix[2][2] - matrix[1][2] * matrix[2][1])
1837        - matrix[0][1] * (matrix[1][0] * matrix[2][2] - matrix[1][2] * matrix[2][0])
1838        + matrix[0][2] * (matrix[1][0] * matrix[2][1] - matrix[1][1] * matrix[2][0]);
1839    // The scale of the quadric sets the scale of the determinant, so the
1840    // threshold is relative to it rather than an absolute epsilon.
1841    let scale = (a2 + b2 + c2).abs().max(1e-12);
1842    if determinant.abs() < 1e-9 * scale * scale * scale {
1843        return None;
1844    }
1845
1846    // Cramer's rule: three determinants with one column replaced.
1847    Some(std::array::from_fn(|column| {
1848        let mut replaced = matrix;
1849        for row in 0..3 {
1850            replaced[row][column] = rhs[row];
1851        }
1852        (replaced[0][0] * (replaced[1][1] * replaced[2][2] - replaced[1][2] * replaced[2][1])
1853            - replaced[0][1] * (replaced[1][0] * replaced[2][2] - replaced[1][2] * replaced[2][0])
1854            + replaced[0][2] * (replaced[1][0] * replaced[2][1] - replaced[1][1] * replaced[2][0]))
1855            / determinant
1856    }))
1857}
1858
1859/// One pending edge collapse, ordered by the error it would cost.
1860///
1861/// `stamp` is how many collapses each endpoint had taken when this was queued.
1862/// A vertex that has moved since invalidates the entry, which is what lets the
1863/// queue hold stale entries instead of being searched and repaired.
1864struct Collapse {
1865    key: u32,
1866    from: u32,
1867    into: u32,
1868    stamps: [u32; 2],
1869    position: [f32; 3],
1870}
1871
1872impl Ord for Collapse {
1873    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
1874        // Reversed, because `BinaryHeap` is a max-heap and the cheapest
1875        // collapse is the one to take.
1876        other.key.cmp(&self.key)
1877    }
1878}
1879impl PartialOrd for Collapse {
1880    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
1881        Some(self.cmp(other))
1882    }
1883}
1884impl PartialEq for Collapse {
1885    fn eq(&self, other: &Self) -> bool {
1886        self.key == other.key
1887    }
1888}
1889impl Eq for Collapse {}
1890
1891impl Mesh {
1892    /// Collapses edges until the mesh is down to `target_faces`, cheapest
1893    /// first.
1894    ///
1895    /// This is Garland and Heckbert's quadric error metric: every vertex
1896    /// carries the sum of the squared-distance quadrics of the faces around
1897    /// it, an edge costs whatever that sum evaluates to at the point it would
1898    /// collapse onto, and the point itself is the one that minimizes it. A
1899    /// boundary edge gets an extra plane at right angles to its face, weighted
1900    /// heavily, so an open edge is held in place rather than eaten away.
1901    ///
1902    /// Returns the face count it finished on, which can be above the target if
1903    /// there was nothing left that could be collapsed safely.
1904    ///
1905    /// Normals are recomputed if the mesh had them. UVs are dropped: a
1906    /// collapse merges two vertices that generally sit in different places in
1907    /// a texture atlas, and inventing a coordinate for the merged one would be
1908    /// worse than admitting there isn't one.
1909    pub fn simplify(&mut self, target_faces: usize) -> usize {
1910        self.collapse_edges(target_faces, f32::INFINITY).0
1911    }
1912
1913    /// Collapses edges for as long as the quadric error stays under
1914    /// `max_error`, and returns the face count it finished on together with the
1915    /// largest error it accepted.
1916    ///
1917    /// This is [`Mesh::simplify`] asking the other question. A face target says
1918    /// how big the mesh may be and lets the error land where it lands, which is
1919    /// the wrong way round for a pipeline that extracted the mesh from a field
1920    /// and wants it as small as it can be *without* visibly moving the surface.
1921    /// Given a bound, this collapses the cheap edges — a flat region, a
1922    /// redundant row of vertices along a plane — and stops at the first edge
1923    /// that would cost more than the bound.
1924    ///
1925    /// The units are the metric's, not the world's: an error is a sum of
1926    /// squared distances to the planes around the edge, each weighted by the
1927    /// area of the face it came from. So it scales with the mesh, and the way
1928    /// to pick a bound is to simplify one representative mesh to a face count
1929    /// that looks right and use the largest error that run reports. The second
1930    /// return value is there for exactly that.
1931    ///
1932    /// Everything else matches [`Mesh::simplify`]: the same metric, the same
1933    /// refusal to fold a face over, normals recomputed, UVs dropped.
1934    pub fn simplify_within(&mut self, max_error: f32) -> (usize, f32) {
1935        self.collapse_edges(0, max_error)
1936    }
1937
1938    /// The collapse loop both entry points run: cheapest edge first, stopping
1939    /// at `target_faces` or at the first collapse over `max_error`, whichever
1940    /// comes first.
1941    fn collapse_edges(&mut self, target_faces: usize, max_error: f32) -> (usize, f32) {
1942        let mut worst = 0.0f32;
1943        if self.indices.len() <= target_faces {
1944            return (self.indices.len(), worst);
1945        }
1946
1947        let mut positions = self.positions.clone();
1948        let mut faces = self.indices.clone();
1949        let mut face_alive = vec![true; faces.len()];
1950        let mut live_faces = faces.len();
1951
1952        // A vertex's quadric is the sum over the faces touching it, each one
1953        // weighted by its area so a sliver does not count as much as a slab.
1954        let mut quadrics = vec![[0.0f32; 10]; positions.len()];
1955        let mut vertex_faces: Vec<Vec<u32>> = vec![Vec::new(); positions.len()];
1956        for (face, corners) in faces.iter().enumerate() {
1957            let [a, b, c] = corners.map(|corner| positions[corner as usize]);
1958            let cross = cross(sub(b, a), sub(c, a));
1959            let area = length(cross) / 2.0;
1960            let quadric = plane_quadric(normalize(cross), a, area);
1961            for corner in *corners {
1962                quadrics[corner as usize] = add_quadric(quadrics[corner as usize], quadric);
1963                vertex_faces[corner as usize].push(face as u32);
1964            }
1965        }
1966
1967        // An edge with one face behind it is a boundary. The plane standing on
1968        // it, at right angles to that face, is what keeps the boundary where
1969        // it is; the weight is what makes it expensive to cross.
1970        let mut edge_faces: HashMap<(u32, u32), usize> = HashMap::new();
1971        for corners in &faces {
1972            for corner in 0..3 {
1973                let edge = ordered(corners[corner], corners[(corner + 1) % 3]);
1974                *edge_faces.entry(edge).or_insert(0) += 1;
1975            }
1976        }
1977        for corners in &faces {
1978            let [a, b, c] = corners.map(|corner| positions[corner as usize]);
1979            let normal = cross(sub(b, a), sub(c, a));
1980            let area = length(normal) / 2.0;
1981            let normal = normalize(normal);
1982            for corner in 0..3 {
1983                let (first, second) = (corners[corner], corners[(corner + 1) % 3]);
1984                if edge_faces.get(&ordered(first, second)) != Some(&1) {
1985                    continue;
1986                }
1987                let along = sub(positions[second as usize], positions[first as usize]);
1988                let wall = normalize(cross(along, normal));
1989                let quadric =
1990                    plane_quadric(wall, positions[first as usize], area * BOUNDARY_WEIGHT);
1991                for vertex in [first, second] {
1992                    quadrics[vertex as usize] = add_quadric(quadrics[vertex as usize], quadric);
1993                }
1994            }
1995        }
1996
1997        let mut stamps = vec![0u32; positions.len()];
1998        let mut vertex_alive = vec![true; positions.len()];
1999        let mut queue = std::collections::BinaryHeap::new();
2000        for edge in edge_faces.keys() {
2001            if let Some(collapse) = weigh(*edge, &positions, &quadrics, &stamps) {
2002                queue.push(collapse);
2003            }
2004        }
2005
2006        // Edges refused for folding since the last collapse round. A later
2007        // collapse can move the neighbours that made them fold, so once the
2008        // queue has nothing cheap left they are weighed again, for as long as
2009        // a round still collapses something. Without this the result hung on
2010        // which of several equally cheap edges the queue handed out first.
2011        let mut refused: Vec<(u32, u32)> = Vec::new();
2012        let mut progressed = false;
2013        let retry = |queue: &mut std::collections::BinaryHeap<Collapse>,
2014                     refused: &mut Vec<(u32, u32)>,
2015                     progressed: &mut bool,
2016                     positions: &[[f32; 3]],
2017                     quadrics: &[Quadric],
2018                     stamps: &[u32],
2019                     vertex_alive: &[bool]| {
2020            if !std::mem::take(progressed) || refused.is_empty() {
2021                return false;
2022            }
2023            for (from, into) in refused.drain(..) {
2024                if vertex_alive[from as usize] && vertex_alive[into as usize] {
2025                    queue.extend(weigh((from, into), positions, quadrics, stamps));
2026                }
2027            }
2028            true
2029        };
2030
2031        while live_faces > target_faces {
2032            let Some(collapse) = queue.pop() else {
2033                match retry(
2034                    &mut queue,
2035                    &mut refused,
2036                    &mut progressed,
2037                    &positions,
2038                    &quadrics,
2039                    &stamps,
2040                    &vertex_alive,
2041                ) {
2042                    true => continue,
2043                    false => break,
2044                }
2045            };
2046            let (from, into) = (collapse.from as usize, collapse.into as usize);
2047            if !vertex_alive[from] || !vertex_alive[into] {
2048                continue;
2049            }
2050            if [stamps[from], stamps[into]] != collapse.stamps {
2051                continue;
2052            }
2053            // The queue is ordered by error, so the first live collapse that
2054            // costs more than the bound is also the cheapest one left.
2055            let error = f32::from_bits(collapse.key);
2056            if error > max_error {
2057                queue.push(collapse);
2058                match retry(
2059                    &mut queue,
2060                    &mut refused,
2061                    &mut progressed,
2062                    &positions,
2063                    &quadrics,
2064                    &stamps,
2065                    &vertex_alive,
2066                ) {
2067                    true => continue,
2068                    false => break,
2069                }
2070            }
2071            // A collapse that turns a face inside out is a fold, and a folded
2072            // mesh is worse than a coarse one.
2073            if folds(
2074                &positions,
2075                &faces,
2076                &face_alive,
2077                &vertex_faces,
2078                from,
2079                into,
2080                collapse.position,
2081            ) {
2082                refused.push((collapse.from, collapse.into));
2083                continue;
2084            }
2085
2086            progressed = true;
2087            worst = worst.max(error);
2088            positions[into] = collapse.position;
2089            quadrics[into] = add_quadric(quadrics[into], quadrics[from]);
2090            vertex_alive[from] = false;
2091            stamps[into] += 1;
2092
2093            // The faces along the collapsed edge become degenerate and go; the
2094            // rest move over to the surviving vertex.
2095            let moved = std::mem::take(&mut vertex_faces[from]);
2096            for face in moved {
2097                if !face_alive[face as usize] {
2098                    continue;
2099                }
2100                let corners = &mut faces[face as usize];
2101                if corners.contains(&(into as u32)) {
2102                    face_alive[face as usize] = false;
2103                    live_faces -= 1;
2104                    continue;
2105                }
2106                for corner in corners.iter_mut() {
2107                    if *corner == from as u32 {
2108                        *corner = into as u32;
2109                    }
2110                }
2111                vertex_faces[into].push(face);
2112            }
2113            vertex_faces[into].retain(|face| face_alive[*face as usize]);
2114
2115            // Every edge now touching the survivor is a new candidate, and
2116            // every old entry mentioning it is stale by its stamp.
2117            let neighbours: Vec<u32> = vertex_faces[into]
2118                .iter()
2119                .flat_map(|face| faces[*face as usize])
2120                .filter(|corner| *corner != into as u32)
2121                .collect();
2122            for neighbour in neighbours {
2123                if !vertex_alive[neighbour as usize] {
2124                    continue;
2125                }
2126                if let Some(collapse) = weigh(
2127                    ordered(into as u32, neighbour),
2128                    &positions,
2129                    &quadrics,
2130                    &stamps,
2131                ) {
2132                    queue.push(collapse);
2133                }
2134            }
2135        }
2136
2137        self.compact(positions, faces, face_alive);
2138        (self.indices.len(), worst)
2139    }
2140
2141    /// Rebuilds the mesh from the surviving faces, dropping orphaned vertices.
2142    fn compact(&mut self, positions: Vec<[f32; 3]>, faces: Vec<[u32; 3]>, alive: Vec<bool>) {
2143        let mut remap = vec![u32::MAX; positions.len()];
2144        let had_normals = !self.normals.is_empty();
2145        // A collapse moves a vertex but does not blend what it carries, so a
2146        // surviving vertex keeps its own colour. Texture coordinates get no
2147        // such treatment: a moved vertex's UV names the wrong place in an atlas,
2148        // and there is no atlas here to be wrong about.
2149        let colours = std::mem::take(&mut self.colors);
2150        self.positions.clear();
2151        self.indices.clear();
2152        self.normals.clear();
2153        self.uvs.clear();
2154
2155        for (face, corners) in faces.iter().enumerate() {
2156            // A collapse can leave a face whose three corners are not three
2157            // distinct vertices any more; it has no area and no place in the
2158            // output.
2159            if !alive[face]
2160                || corners[0] == corners[1]
2161                || corners[1] == corners[2]
2162                || corners[0] == corners[2]
2163            {
2164                continue;
2165            }
2166            let mut rebased = [0u32; 3];
2167            for (slot, corner) in rebased.iter_mut().zip(corners) {
2168                let corner = *corner as usize;
2169                if remap[corner] == u32::MAX {
2170                    remap[corner] = self.positions.len() as u32;
2171                    self.positions.push(positions[corner]);
2172                    if let Some(colour) = colours.get(corner) {
2173                        self.colors.push(*colour);
2174                    }
2175                }
2176                *slot = remap[corner];
2177            }
2178            self.indices.push(rebased);
2179        }
2180
2181        if had_normals {
2182            self.recompute_normals();
2183        }
2184    }
2185}
2186
2187/// How much more a boundary plane counts than the faces around it. Large
2188/// enough that an open edge is the last thing to go, small enough that a
2189/// boundary vertex can still slide along its own edge.
2190const BOUNDARY_WEIGHT: f32 = 1000.0;
2191
2192fn ordered(first: u32, second: u32) -> (u32, u32) {
2193    match first < second {
2194        true => (first, second),
2195        false => (second, first),
2196    }
2197}
2198
2199/// Prices one edge and picks the point it would collapse onto.
2200fn weigh(
2201    edge: (u32, u32),
2202    positions: &[[f32; 3]],
2203    quadrics: &[Quadric],
2204    stamps: &[u32],
2205) -> Option<Collapse> {
2206    let (from, into) = edge;
2207    if from == into {
2208        return None;
2209    }
2210    let quadric = add_quadric(quadrics[from as usize], quadrics[into as usize]);
2211    let candidates = [
2212        quadric_minimum(quadric),
2213        Some(positions[from as usize]),
2214        Some(positions[into as usize]),
2215        Some(scale(
2216            add3(positions[from as usize], positions[into as usize]),
2217            0.5,
2218        )),
2219    ];
2220    let (position, error) = candidates
2221        .into_iter()
2222        .flatten()
2223        .map(|point| (point, quadric_error(quadric, point)))
2224        .min_by(|left, right| left.1.total_cmp(&right.1))?;
2225
2226    Some(Collapse {
2227        // Rounding can leave the error a hair below zero, and a negative float
2228        // does not sort by its bits.
2229        key: error.max(0.0).to_bits(),
2230        // The survivor is the second of the pair, so the collapse is
2231        // deterministic whichever way the edge was found.
2232        from,
2233        into,
2234        stamps: [stamps[from as usize], stamps[into as usize]],
2235        position,
2236    })
2237}
2238
2239/// Whether moving `into` to `position` and merging `from` onto it would turn
2240/// any surviving face inside out.
2241fn folds(
2242    positions: &[[f32; 3]],
2243    faces: &[[u32; 3]],
2244    face_alive: &[bool],
2245    vertex_faces: &[Vec<u32>],
2246    from: usize,
2247    into: usize,
2248    position: [f32; 3],
2249) -> bool {
2250    for vertex in [from, into] {
2251        for face in &vertex_faces[vertex] {
2252            let corners = faces[*face as usize];
2253            if !face_alive[*face as usize] {
2254                continue;
2255            }
2256            // The faces along the edge itself are the ones meant to vanish.
2257            if corners.contains(&(from as u32)) && corners.contains(&(into as u32)) {
2258                continue;
2259            }
2260            let before = corners.map(|corner| positions[corner as usize]);
2261            let after =
2262                corners.map(
2263                    |corner| match corner as usize == from || corner as usize == into {
2264                        true => position,
2265                        false => positions[corner as usize],
2266                    },
2267                );
2268            let old = cross(sub(before[1], before[0]), sub(before[2], before[0]));
2269            let new = cross(sub(after[1], after[0]), sub(after[2], after[0]));
2270            if dot(old, new) <= 0.0 {
2271                return true;
2272            }
2273        }
2274    }
2275    false
2276}
2277
2278#[cfg(test)]
2279mod simplify_tests {
2280    use super::*;
2281
2282    /// A flat grid of `n x n` quads, triangulated. Every interior vertex sits
2283    /// exactly on the plane its neighbours define, so collapsing it costs
2284    /// nothing.
2285    fn grid(n: usize) -> Mesh {
2286        let mut mesh = Mesh::default();
2287        for row in 0..=n {
2288            for column in 0..=n {
2289                mesh.positions
2290                    .push([column as f32 / n as f32, row as f32 / n as f32, 0.0]);
2291            }
2292        }
2293        let index = |row: usize, column: usize| (row * (n + 1) + column) as u32;
2294        for row in 0..n {
2295            for column in 0..n {
2296                mesh.indices.push([
2297                    index(row, column),
2298                    index(row, column + 1),
2299                    index(row + 1, column),
2300                ]);
2301                mesh.indices.push([
2302                    index(row, column + 1),
2303                    index(row + 1, column + 1),
2304                    index(row + 1, column),
2305                ]);
2306            }
2307        }
2308        mesh
2309    }
2310
2311    /// A sphere from the distance field, which is what the pipeline actually
2312    /// hands the simplifier.
2313    fn sphere(resolution: usize) -> Mesh {
2314        marching_tetrahedra(
2315            |points| {
2316                Ok((0..points.rows)
2317                    .map(|row| {
2318                        let point = points.row(row);
2319                        (point[0] * point[0] + point[1] * point[1] + point[2] * point[2]).sqrt()
2320                            - 0.8
2321                    })
2322                    .collect())
2323            },
2324            resolution,
2325            ([-1.0; 3], [1.0; 3]),
2326            0.0,
2327        )
2328        .unwrap()
2329    }
2330
2331    #[test]
2332    fn a_target_above_the_face_count_changes_nothing() {
2333        let mut mesh = grid(4);
2334        let before = mesh.indices.clone();
2335        assert_eq!(mesh.simplify(10_000), before.len());
2336        assert_eq!(mesh.indices, before);
2337    }
2338
2339    #[test]
2340    fn a_flat_sheet_collapses_to_its_corners_for_nothing() {
2341        let mut mesh = grid(6);
2342        assert_eq!(mesh.indices.len(), 72);
2343        mesh.simplify(2);
2344
2345        // The interior is free to remove and the boundary is not, so what
2346        // survives is the four corners and the two triangles across them.
2347        assert_eq!(mesh.indices.len(), 2);
2348        assert_eq!(mesh.positions.len(), 4);
2349        let (low, high) = mesh.bounds();
2350        assert_eq!(low, [0.0, 0.0, 0.0]);
2351        assert_eq!(high, [1.0, 1.0, 0.0]);
2352    }
2353
2354    #[test]
2355    fn an_error_bound_removes_the_flat_interior_and_keeps_the_shape() {
2356        // A flat sheet: every interior collapse is free, so a bound of nothing
2357        // at all still takes the mesh down to its corners.
2358        let mut sheet = grid(6);
2359        let (faces, worst) = sheet.simplify_within(1e-6);
2360        assert_eq!(faces, 2, "a flat sheet costs nothing to simplify");
2361        assert!(worst < 1e-6, "the worst collapse taken was {worst}");
2362
2363        // A sphere is curved everywhere, so the same bound buys much less.
2364        let mut curved = sphere(24);
2365        let before = curved.indices.len();
2366        let (faces, worst) = curved.simplify_within(1e-6);
2367        assert!(faces < before, "{before} to {faces}");
2368        assert!(worst <= 1e-6);
2369        for point in &curved.positions {
2370            let distance = (length(*point) - 0.8).abs();
2371            assert!(distance < 0.02, "{point:?} sits {distance} off the surface");
2372        }
2373    }
2374
2375    #[test]
2376    fn a_looser_bound_reaches_a_smaller_mesh_and_says_what_it_cost() {
2377        let mut tight = sphere(24);
2378        let (tight_faces, tight_worst) = tight.simplify_within(1e-6);
2379        let mut loose = sphere(24);
2380        let (loose_faces, loose_worst) = loose.simplify_within(1e-3);
2381
2382        assert!(
2383            loose_faces < tight_faces,
2384            "a looser bound should collapse more: {loose_faces} against {tight_faces}"
2385        );
2386        assert!(loose_worst > tight_worst);
2387        assert!(
2388            loose_worst <= 1e-3,
2389            "the bound was not exceeded: {loose_worst}"
2390        );
2391    }
2392
2393    #[test]
2394    fn a_bound_of_zero_takes_only_the_collapses_that_cost_nothing() {
2395        // A marched sphere carries rows of vertices that sit exactly on the
2396        // plane of their neighbours, which the metric prices at zero. Those go;
2397        // nothing that moves the surface does.
2398        let mut mesh = sphere(20);
2399        let before = mesh.indices.len();
2400        let (faces, worst) = mesh.simplify_within(0.0);
2401        assert!(faces < before, "{before} to {faces}");
2402        assert_eq!(worst, 0.0);
2403        for point in &mesh.positions {
2404            let distance = (length(*point) - 0.8).abs();
2405            assert!(distance < 0.01, "{point:?} sits {distance} off the surface");
2406        }
2407    }
2408
2409    #[test]
2410    fn a_sphere_keeps_its_shape_at_a_fifth_of_its_faces() {
2411        let mut mesh = sphere(24);
2412        let before = mesh.indices.len();
2413        let radius = |mesh: &Mesh| {
2414            mesh.positions
2415                .iter()
2416                .map(|point| length(*point))
2417                .fold(0.0f32, f32::max)
2418        };
2419        let before_radius = radius(&mesh);
2420
2421        let after = mesh.simplify(before / 5);
2422        assert!(after <= before / 5 + 8, "{before} to {after}");
2423        assert!(after > 0);
2424
2425        // The surface is still the same sphere: no vertex has wandered off it.
2426        for point in &mesh.positions {
2427            let distance = (length(*point) - 0.8).abs();
2428            assert!(distance < 0.08, "{point:?} sits {distance} off the surface");
2429        }
2430        assert!((radius(&mesh) - before_radius).abs() < 0.08);
2431    }
2432
2433    #[test]
2434    fn simplification_leaves_no_degenerate_or_dangling_geometry() {
2435        let mut mesh = sphere(20);
2436        mesh.recompute_normals();
2437        mesh.uvs = vec![[0.0, 0.0]; mesh.positions.len()];
2438        mesh.simplify(mesh.indices.len() / 4);
2439
2440        let mut used = vec![false; mesh.positions.len()];
2441        for face in &mesh.indices {
2442            assert!(face[0] != face[1] && face[1] != face[2] && face[0] != face[2]);
2443            for corner in face {
2444                assert!((*corner as usize) < mesh.positions.len());
2445                used[*corner as usize] = true;
2446            }
2447        }
2448        assert!(used.iter().all(|used| *used), "an orphaned vertex survived");
2449        assert!(mesh.area() > 0.0);
2450
2451        // Normals come back because there were normals; UVs do not, because a
2452        // collapse has nowhere sensible to put them.
2453        assert_eq!(mesh.normals.len(), mesh.positions.len());
2454        assert!(mesh.uvs.is_empty());
2455        for normal in &mesh.normals {
2456            assert!((length(*normal) - 1.0).abs() < 1e-4);
2457        }
2458    }
2459
2460    /// The quadric is the machinery everything else rests on, so it is checked
2461    /// on its own: the error is the squared distance to the plane.
2462    #[test]
2463    fn a_quadric_measures_squared_distance_to_its_plane() {
2464        let quadric = plane_quadric([0.0, 0.0, 1.0], [0.0, 0.0, 2.0], 1.0);
2465        assert!(quadric_error(quadric, [5.0, -3.0, 2.0]).abs() < 1e-6);
2466        assert!((quadric_error(quadric, [1.0, 1.0, 5.0]) - 9.0).abs() < 1e-5);
2467
2468        // Three planes meeting at a corner have exactly one minimum, and it is
2469        // the corner.
2470        let corner = add_quadric(
2471            add_quadric(
2472                plane_quadric([1.0, 0.0, 0.0], [1.0, 0.0, 0.0], 1.0),
2473                plane_quadric([0.0, 1.0, 0.0], [0.0, 2.0, 0.0], 1.0),
2474            ),
2475            plane_quadric([0.0, 0.0, 1.0], [0.0, 0.0, 3.0], 1.0),
2476        );
2477        let minimum = quadric_minimum(corner).unwrap();
2478        for (found, expected) in minimum.iter().zip(&[1.0, 2.0, 3.0]) {
2479            assert!((found - expected).abs() < 1e-4, "{minimum:?}");
2480        }
2481        // One plane on its own leaves a whole plane of minima, and no answer.
2482        assert!(quadric_minimum(plane_quadric([0.0, 0.0, 1.0], [0.0, 0.0, 2.0], 1.0)).is_none());
2483    }
2484
2485    /// A collapse that would turn a face inside out is refused, which is what
2486    /// keeps a simplified mesh from self-intersecting.
2487    #[test]
2488    fn a_collapse_that_would_fold_a_face_is_refused() {
2489        let positions = [
2490            [0.0, 0.0, 0.0],
2491            [1.0, 0.0, 0.0],
2492            [1.0, 1.0, 0.0],
2493            [0.0, 1.0, 0.0],
2494        ];
2495        let faces = [[0, 1, 2], [0, 2, 3]];
2496        let alive = [true, true];
2497        let vertex_faces = vec![vec![0, 1], vec![0], vec![0, 1], vec![1]];
2498
2499        // Pulling vertex 1 onto vertex 0 keeps both faces the right way round.
2500        assert!(!folds(
2501            &positions,
2502            &faces,
2503            &alive,
2504            &vertex_faces,
2505            1,
2506            0,
2507            [0.0, 0.0, 0.0]
2508        ));
2509        // Dragging vertex 3 far past the diagonal flips the face it is on.
2510        assert!(folds(
2511            &positions,
2512            &faces,
2513            &alive,
2514            &vertex_faces,
2515            3,
2516            0,
2517            [5.0, -5.0, 0.0]
2518        ));
2519    }
2520}