1use crate::matrix::Matrix;
36use crate::network::NetworkError;
37use rand::Rng;
38use rayon::prelude::*;
39use std::collections::HashMap;
40use std::path::Path;
41
42#[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 pub colors: Vec<[f32; 3]>,
55 pub indices: Vec<[u32; 3]>,
56}
57
58#[derive(Clone, Copy, Debug, PartialEq)]
61pub struct Transform {
62 pub center: [f32; 3],
63 pub scale: f32,
64}
65
66impl Transform {
67 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 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 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 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 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 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 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 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 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 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 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 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 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 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 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
294fn 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
314fn 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#[derive(Clone, Debug)]
356struct Node {
357 low: [f32; 3],
358 high: [f32; 3],
359 start: u32,
361 count: u32,
363 right: u32,
365 moment: [f32; 3],
369 centroid: [f32; 3],
370 radius: f32,
373}
374
375pub struct Bvh<'a> {
380 mesh: &'a Mesh,
381 nodes: Vec<Node>,
382 order: Vec<u32>,
384}
385
386const LEAF_SIZE: usize = 4;
389
390const WINDING_BETA: f32 = 2.0;
394
395impl<'a> Bvh<'a> {
396 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(), ¢roids);
413 }
414 tree
415 }
416
417 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 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(¢roids[*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 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 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 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 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 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 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 match self.winding_number(*query) > 0.5 {
598 true => -distance,
599 false => distance,
600 }
601 })
602 .collect()
603 }
604}
605
606fn 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
616fn 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 return a;
651 }
652 let (v, w) = (vb / denominator, vc / denominator);
653 add3(add3(a, scale(ab, v)), scale(ac, w))
654}
655
656fn 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 true => 0.0,
666 false => 2.0 * dot(a, cross(b, c)).atan2(denominator),
667 }
668}
669
670#[derive(Clone, Copy, Debug, PartialEq)]
681pub struct QuerySampling {
682 pub count: usize,
684 pub near_surface: f32,
686 pub jitter: f32,
689 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
706pub type Cloud = Vec<[f32; 3]>;
708
709impl Bvh<'_> {
710 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 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 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 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 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 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
801fn 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
809pub 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
855pub 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 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
936struct 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 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 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 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 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
1096struct Occupancy {
1098 marked: Vec<bool>,
1099 cells: usize,
1100 coarse: usize,
1101}
1102
1103impl Occupancy {
1104 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 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 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 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
1226const 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
1238const TETRAHEDRON_EDGES: [(usize, usize); 6] = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)];
1240
1241const 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
1265fn 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 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 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 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 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 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
1350pub 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 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 mesh.indices.push([a, b, c]);
1398 mesh.indices.push([b, d, c]);
1399 }
1400 }
1401 mesh
1402 }
1403
1404 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 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 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 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 assert!(
1489 (distance - expected).abs() < 0.01,
1490 "{query:?}: {distance} against {expected}"
1491 );
1492 }
1493 }
1494
1495 #[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 assert!(dot(*normal, *point) > 0.0, "{normal:?} at {point:?}");
1528 }
1529 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 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 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 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 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 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 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 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 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 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 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
1777type Quadric = [f32; 10];
1786
1787fn 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
1810fn 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
1825fn 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 let scale = (a2 + b2 + c2).abs().max(1e-12);
1842 if determinant.abs() < 1e-9 * scale * scale * scale {
1843 return None;
1844 }
1845
1846 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
1859struct 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 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 pub fn simplify(&mut self, target_faces: usize) -> usize {
1910 self.collapse_edges(target_faces, f32::INFINITY).0
1911 }
1912
1913 pub fn simplify_within(&mut self, max_error: f32) -> (usize, f32) {
1935 self.collapse_edges(0, max_error)
1936 }
1937
1938 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 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 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 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 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 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 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 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 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 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 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
2187const 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
2199fn 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 key: error.max(0.0).to_bits(),
2230 from,
2233 into,
2234 stamps: [stamps[from as usize], stamps[into as usize]],
2235 position,
2236 })
2237}
2238
2239fn 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 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 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 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 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 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 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 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 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 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 #[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 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 assert!(quadric_minimum(plane_quadric([0.0, 0.0, 1.0], [0.0, 0.0, 2.0], 1.0)).is_none());
2483 }
2484
2485 #[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 assert!(!folds(
2501 &positions,
2502 &faces,
2503 &alive,
2504 &vertex_faces,
2505 1,
2506 0,
2507 [0.0, 0.0, 0.0]
2508 ));
2509 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}