1pub mod blend;
57mod bspline;
58mod curve;
59mod edges;
60mod math;
61mod measure;
62mod model;
63mod nurbs;
64pub mod primitives;
65mod reconstruct;
66mod seams;
67mod solve;
68pub mod spline;
69mod step;
70mod surf;
71mod tangency;
72mod topo;
73mod validate;
74
75use std::fmt;
76
77pub use measure::{Measure, measure};
78pub use model::*;
79pub use reconstruct::{Options, StopFn, Tolerances};
80pub use step::{StepOptions, write_step};
81pub use tangency::find_tangencies;
82pub use validate::{Validation, validate};
83
84use crate::math::UnionFind;
85
86#[derive(Clone, Debug, PartialEq)]
88pub enum Error {
89 InvalidInput(String),
91 NotManifold(String),
93 Unsupported(&'static str),
95 Reconstruction(String),
97 TopologyMismatch(String),
105 Stopped,
107}
108
109impl fmt::Display for Error {
110 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
111 match self {
112 Error::InvalidInput(s) => write!(f, "invalid input: {s}"),
113 Error::NotManifold(s) => write!(f, "not a manifold: {s}"),
114 Error::Unsupported(k) => write!(f, "{k} surfaces are not supported yet"),
115 Error::Reconstruction(s) => write!(f, "reconstruction failed: {s}"),
116 Error::TopologyMismatch(s) => {
117 write!(f, "the mesh's topology differs from the exact model's: {s}")
118 }
119 Error::Stopped => write!(f, "stopped by the caller"),
120 }
121 }
122}
123
124impl std::error::Error for Error {}
125
126#[derive(Clone, Debug, PartialEq)]
128pub struct Failure {
129 pub error: Error,
131 pub triangles: Vec<u32>,
138}
139
140impl From<Error> for Failure {
141 fn from(error: Error) -> Failure {
142 Failure {
143 error,
144 triangles: Vec::new(),
145 }
146 }
147}
148
149impl fmt::Display for Failure {
150 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
151 self.error.fmt(f)
152 }
153}
154
155impl std::error::Error for Failure {}
156
157pub fn reconstruct(mesh: &TaggedMesh, options: &Options) -> Result<Brep, Error> {
163 reconstruct_with(mesh, options, true).map_err(|f| f.error)
164}
165
166pub fn reconstruct_located(mesh: &TaggedMesh, options: &Options) -> Result<Brep, Failure> {
169 reconstruct_with(mesh, options, true)
170}
171
172fn reconstruct_with(mesh: &TaggedMesh, options: &Options, contacts: bool) -> Result<Brep, Failure> {
173 let built = reconstruct::build(mesh, options, contacts)?;
174 let mut topo = built.topo;
175 options.poll()?;
176 let max_pcurve = seams::parametrise(&mut topo, built.scale, options.tolerances.fit)?;
177 options.poll()?;
178 let max_edge = topo.edges.iter().map(|e| e.dev).fold(0.0, f64::max);
179 let mut b = assemble(topo);
180 let touch_tol = options.tolerances.fit.max(1e-9 * built.scale);
181 let mut stopped = false;
182 let folded: Vec<(usize, String)> = (0..b.faces.len())
183 .filter_map(|f| {
184 if stopped || options.stopped() {
187 stopped = true;
188 return None;
189 }
190 validate::face_crossing(&b, f)
191 .or_else(|| validate::face_touch(&b, f, touch_tol))
192 .map(|m| (f, m))
193 })
194 .collect();
195 if stopped {
196 return Err(Error::Stopped.into());
197 }
198 if !folded.is_empty() {
199 let more = folded.len().saturating_sub(3);
202 let mut msg = folded[..folded.len().min(3)]
203 .iter()
204 .map(|(_, m)| m.as_str())
205 .collect::<Vec<_>>()
206 .join("; ");
207 if more > 0 {
208 msg.push_str(&format!("; and {more} more"));
209 }
210 let mut triangles: Vec<u32> = folded
211 .iter()
212 .flat_map(|&(f, _)| b.report.face_triangles[f].iter().copied())
213 .collect();
214 triangles.sort_unstable();
215 return Err(Failure {
216 error: Error::TopologyMismatch(msg),
217 triangles,
218 });
219 }
220 let mut uf = UnionFind::new(b.faces.len());
222 let mut first_face = vec![usize::MAX; b.edges.len()];
223 for (fi, f) in b.faces.iter().enumerate() {
224 for lp in &f.loops {
225 for c in &lp.coedges {
226 let e = c.edge as usize;
227 if first_face[e] == usize::MAX {
228 first_face[e] = fi;
229 } else {
230 uf.join(first_face[e], fi);
231 }
232 }
233 }
234 }
235 let mut shells: std::collections::BTreeMap<usize, Vec<u32>> = Default::default();
236 for f in 0..b.faces.len() {
237 shells.entry(uf.find(f)).or_default().push(f as u32);
238 }
239 b.shells = shells
242 .into_values()
243 .map(|faces| {
244 let v: f64 = faces
245 .iter()
246 .map(|&f| built.face_mesh_volume[f as usize])
247 .sum();
248 Shell {
249 faces,
250 void: v < 0.0,
251 }
252 })
253 .collect();
254 b.report.scale = built.scale;
255 b.report.faces_uncrossed = true;
257 b.report.mesh_genus = built.mesh_genus;
258 b.report.mesh_components = built.mesh_components;
259 b.report.max_vertex_residual = built.max_vertex_residual;
260 b.report.max_edge_deviation = max_edge;
261 b.report.max_pcurve_deviation = max_pcurve;
262 b.report.max_chain_deviation = built.max_chain_deviation;
263 b.report.tangencies = built
264 .tangencies
265 .iter()
266 .flat_map(|(a, c, k)| {
267 let (a, c) = (*a, *c);
268 k.to_public(a, c).into_iter().map(move |contact| Tangency {
269 surfaces: [a.min(c), a.max(c)],
270 contact,
271 })
272 })
273 .collect();
274 Ok(b)
275}
276
277fn assemble(topo: topo::Topo) -> Brep {
280 let mut vnum = vec![u32::MAX; topo.verts.len()];
281 let mut vertices = Vec::new();
282 let mut edges = Vec::with_capacity(topo.edges.len());
283 let edge_chain_deviation = topo.edges.iter().map(|e| e.chain_dev).collect();
284 let face_triangles = topo.faces.iter().map(|f| f.source.clone()).collect();
285 for e in &topo.edges {
286 for vi in [e.v0, e.v1] {
287 if vnum[vi] == u32::MAX {
288 vnum[vi] = vertices.len() as u32;
289 vertices.push(topo.verts[vi].arr());
290 }
291 }
292 edges.push(Edge {
293 start: vnum[e.v0],
294 end: vnum[e.v1],
295 curve: e.curve.clone(),
296 range: e.range,
297 seam: e.seam,
298 });
299 }
300 let faces = topo
301 .faces
302 .into_iter()
303 .map(|f| {
304 let p = f.param.expect("param");
305 let loops = f
306 .loops
307 .iter()
308 .enumerate()
309 .map(|(li, lp)| Loop {
310 coedges: lp
311 .iter()
312 .enumerate()
313 .map(|(ci, &(e, fwd))| Coedge {
314 edge: e as u32,
315 forward: fwd,
316 pcurve: f.pcurves.get(li).and_then(|l| l[ci].clone()),
317 })
318 .collect(),
319 outer: f.outer.get(li).copied().unwrap_or(false),
320 })
321 .collect();
322 Face {
323 surface: p.s.to_public(),
324 frame: p.frame(),
325 ref_radius: p.r0,
326 same_sense: f.same_sense,
327 loops,
328 faceted: f.faceted,
329 }
330 })
331 .collect();
332 Brep {
333 vertices,
334 edges,
335 faces,
336 shells: Vec::new(),
337 report: Report {
338 notes: topo.notes,
339 edge_chain_deviation,
340 face_triangles,
341 ..Report::default()
342 },
343 }
344}
345
346#[cfg(test)]
347mod tests {
348 use super::*;
349 use manifold_rust::manifold::Manifold;
350 use manifold_rust::types::{MeshGL64, OpType};
351 use primitives::Transform;
352
353 fn capsule() -> TaggedMesh {
356 let parts = [
357 primitives::frustum(20.0, 5.0, 5.0, 32, &Transform::IDENTITY),
358 primitives::sphere(5.0, 32, &Transform::IDENTITY),
359 primitives::sphere(5.0, 32, &Transform::translate([0.0, 0.0, 20.0])),
360 ];
361 let mut surfaces = Vec::new();
362 let ms: Vec<Manifold> = parts
363 .iter()
364 .map(|m| {
365 let off = surfaces.len() as u64;
366 surfaces.extend(m.surfaces.iter().cloned());
367 Manifold::from_mesh_gl64(&MeshGL64 {
368 num_prop: 3,
369 vert_properties: m.positions.iter().flatten().copied().collect(),
370 tri_verts: m
371 .triangles
372 .iter()
373 .flatten()
374 .map(|&i| u64::from(i))
375 .collect(),
376 face_id: m
377 .triangle_surface
378 .iter()
379 .map(|&s| u64::from(s) + off)
380 .collect(),
381 run_index: vec![0, 3 * m.triangles.len() as u64],
382 run_original_id: vec![Manifold::reserve_ids(1)],
383 ..Default::default()
384 })
385 })
386 .collect();
387 let gl = Manifold::batch_boolean(&ms, OpType::Add).get_mesh_gl64(-1);
388 TaggedMesh {
389 positions: gl
390 .vert_properties
391 .chunks(3)
392 .map(|c| [c[0], c[1], c[2]])
393 .collect(),
394 triangles: gl
395 .tri_verts
396 .chunks(3)
397 .map(|c| [c[0] as u32, c[1] as u32, c[2] as u32])
398 .collect(),
399 triangle_surface: gl.face_id.iter().map(|&f| f as u32).collect(),
400 surfaces,
401 }
402 }
403
404 fn minus(first: &TaggedMesh, rest: &[TaggedMesh]) -> TaggedMesh {
406 let mut surfaces = Vec::new();
407 let mut to = |m: &TaggedMesh| {
408 let off = surfaces.len() as u64;
409 surfaces.extend(m.surfaces.iter().cloned());
410 Manifold::from_mesh_gl64(&MeshGL64 {
411 num_prop: 3,
412 vert_properties: m.positions.iter().flatten().copied().collect(),
413 tri_verts: m
414 .triangles
415 .iter()
416 .flatten()
417 .map(|&i| u64::from(i))
418 .collect(),
419 face_id: m
420 .triangle_surface
421 .iter()
422 .map(|&s| u64::from(s) + off)
423 .collect(),
424 run_index: vec![0, 3 * m.triangles.len() as u64],
425 run_original_id: vec![Manifold::reserve_ids(1)],
426 ..Default::default()
427 })
428 };
429 let mut out = to(first);
430 for r in rest {
431 out = out.boolean(&to(r), OpType::Subtract);
432 }
433 let gl = out.get_mesh_gl64(-1);
434 TaggedMesh {
435 positions: gl
436 .vert_properties
437 .chunks(3)
438 .map(|c| [c[0], c[1], c[2]])
439 .collect(),
440 triangles: gl
441 .tri_verts
442 .chunks(3)
443 .map(|c| [c[0] as u32, c[1] as u32, c[2] as u32])
444 .collect(),
445 triangle_surface: gl.face_id.iter().map(|&f| f as u32).collect(),
446 surfaces,
447 }
448 }
449
450 fn says(v: &Validation, what: &str) -> bool {
451 v.errors.iter().any(|e| e.contains(what))
452 }
453
454 #[test]
458 fn a_face_narrower_than_the_tolerance_is_an_error() {
459 let slab = primitives::cuboid([10.0, 5e-7, 10.0], &Transform::IDENTITY);
460 let b = reconstruct(&slab, &Options::default()).unwrap();
461 let v = validate(&b, 1e-6);
462 assert!(says(&v, "narrower than the tolerance"), "{:?}", v.errors);
463 assert_eq!(v.error_faces.len(), 4, "{:?}", v.error_faces);
464 assert!(validate(&b, 1e-7).is_valid());
465 }
466
467 #[test]
471 fn a_closed_edge_inside_a_longer_loop_is_an_error() {
472 let mesh = primitives::frustum(10.0, 5.0, 5.0, 32, &Transform::IDENTITY);
473 let mut b = reconstruct(&mesh, &Options::default()).unwrap();
474 assert!(b.report.faces_uncrossed);
477 assert!(validate(&b, 1e-6).is_valid());
478 let f = b
479 .faces
480 .iter()
481 .position(|f| {
482 matches!(f.surface, Surface::Plane { .. })
483 && f.loops.len() == 1
484 && f.loops[0].coedges.len() == 1
485 })
486 .expect("a cap bounded by its circle");
487 let c = b.faces[f].loops[0].coedges[0].clone();
488 b.faces[f].loops[0].coedges.push(c);
489 let v = validate(&b, 1e-6);
490 assert!(says(&v, "inside a longer loop"), "{:?}", v.errors);
491 assert!(v.error_faces.contains(&(f as u32)));
492 }
493
494 #[test]
497 fn a_hole_outside_its_outer_loop_is_an_error() {
498 let plate = primitives::cuboid([20.0, 20.0, 5.0], &Transform::IDENTITY);
499 let hole =
500 primitives::frustum(7.0, 3.0, 3.0, 32, &Transform::translate([10.0, 10.0, -1.0]));
501 let mesh = minus(&plate, &[hole]);
502 let mut b = reconstruct(&mesh, &Options::default()).unwrap();
503 assert!(validate(&b, 1e-6).is_valid());
504 let f = b
505 .faces
506 .iter()
507 .position(|f| f.loops.len() == 2 && matches!(f.surface, Surface::Plane { .. }))
508 .expect("a face with a hole");
509 for l in &mut b.faces[f].loops {
510 l.outer = !l.outer;
511 }
512 let v = validate(&b, 1e-6);
513 assert!(says(&v, "a hole not inside"), "{:?}", v.errors);
514 }
515
516 #[test]
521 fn arcs_split_at_tangent_vertices_are_merged() {
522 let mesh = capsule();
523 let with = reconstruct_with(&mesh, &Options::default(), true).unwrap();
524 let without = reconstruct_with(&mesh, &Options::default(), false).unwrap();
525 assert!(with.report.notes.iter().all(|n| !n.contains("merged")));
526 assert!(
527 without.report.notes.iter().any(|n| n.contains("merged")),
528 "{:?}",
529 without.report.notes
530 );
531 let circles = |b: &Brep| {
532 b.edges
533 .iter()
534 .filter(|e| !e.seam && matches!(e.curve, Curve::Circle { .. }))
535 .count()
536 };
537 assert_eq!(circles(&with), 2);
538 assert_eq!(circles(&without), 2);
539 assert!(validate(&without, 1e-6).is_valid());
540 let v = measure(&without).unwrap().volume;
541 let exact = std::f64::consts::PI * (500.0 + 500.0 / 3.0);
542 assert!((v - exact).abs() < 1e-9 * exact, "{v} vs {exact}");
543 }
544
545 #[test]
551 fn a_flat_closed_component_is_dropped() {
552 let cube = primitives::cuboid([2.0, 2.0, 2.0], &Transform::IDENTITY);
553 let mut mesh = cube.clone();
554 let base = mesh.positions.len() as u32;
555 mesh.positions.extend([
558 [0.0, 0.0, 5.0],
559 [1.0, 0.0, 5.0],
560 [1.0, 1.0, 5.0],
561 [0.0, 1.0, 5.0],
562 ]);
563 let plane = mesh.surfaces.len() as u32;
564 mesh.surfaces.push(Surface::Plane {
565 origin: [0.0, 0.0, 5.0],
566 normal: [0.0, 0.0, 1.0],
567 });
568 for t in [[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]] {
569 mesh.triangles.push(t.map(|i| base + i));
570 mesh.triangle_surface.push(plane);
571 }
572 let b = reconstruct(&mesh, &Options::default()).unwrap();
573 assert!(
574 b.report
575 .notes
576 .iter()
577 .any(|n| n.contains("flat closed component")),
578 "{:?}",
579 b.report.notes
580 );
581 assert_eq!(b.faces.len(), 6);
582 assert_eq!(b.shells.len(), 1);
583 assert!(validate(&b, 1e-6).is_valid());
584 assert!((measure(&b).unwrap().volume - 8.0).abs() < 1e-12);
585 let mut solid = mesh.clone();
587 solid.positions[base as usize + 2][2] = 6.0;
588 assert!(reconstruct(&solid, &Options::default()).is_err());
589 }
590
591 #[test]
592 fn tangencies_are_found_from_the_records() {
593 let surfaces = [
594 Surface::Plane {
595 origin: [0.0, 0.0, 0.0],
596 normal: [0.0, 1.0, 0.0],
597 },
598 Surface::Cylinder {
599 origin: [0.0, 3.0, 0.0],
600 axis: [0.0, 0.0, 1.0],
601 radius: 3.0,
602 },
603 Surface::Sphere {
604 center: [0.0, 3.0, 7.0],
605 radius: 3.0,
606 },
607 Surface::Faceted,
608 ];
609 let t = find_tangencies(&surfaces, 1e-9);
610 assert_eq!(t.len(), 3, "{t:?}");
611 assert!(matches!(t[0].contact, Contact::Line { .. }));
612 assert!(matches!(t[1].contact, Contact::Point { .. }));
613 assert!(matches!(t[2].contact, Contact::Circle { .. }));
614 }
615
616 #[test]
619 fn torus_tangencies_are_circles() {
620 let z = [0.0, 0.0, 1.0];
621 let surfaces = [
622 Surface::Torus {
623 center: [0.0; 3],
624 axis: z,
625 major_radius: 7.0,
626 minor_radius: 3.0,
627 },
628 Surface::Plane {
630 origin: [0.0, 0.0, 3.0],
631 normal: z,
632 },
633 Surface::Cylinder {
634 origin: [0.0; 3],
635 axis: z,
636 radius: 4.0,
637 },
638 Surface::Cylinder {
639 origin: [0.0, 0.0, -5.0],
640 axis: [0.0, 0.0, -1.0],
641 radius: 10.0,
642 },
643 Surface::Cylinder {
645 origin: [0.0; 3],
646 axis: z,
647 radius: 8.0,
648 },
649 ];
650 let t = find_tangencies(&surfaces, 1e-9);
651 let radii: Vec<f64> = t
652 .iter()
653 .filter(|x| x.surfaces[0] == 0)
654 .map(|x| match x.contact {
655 Contact::Circle { radius, .. } => radius,
656 _ => f64::NAN,
657 })
658 .collect();
659 assert_eq!(radii, [7.0, 4.0, 10.0], "{t:?}");
660 }
661}