Skip to main content

meshbrep/
lib.rs

1//! Rebuild an exact boundary representation from a triangle mesh whose
2//! triangles each name the exact surface they came from, and write it as
3//! STEP.
4//!
5//! A mesh kernel such as Manifold does booleans robustly but only on
6//! triangles. If every input triangle is tagged with the exact surface it
7//! approximates (a plane, cylinder, cone, sphere, torus or B-spline
8//! surface; [`spline`] builds the B-splines blends need), the tags survive the
9//! booleans, and the output mesh says which surface each region lies on.
10//! This crate turns that into a B-rep:
11//!
12//! - **faces** are connected regions on one surface (equal surfaces from
13//!   different solids are merged, so two coplanar tops give one face);
14//! - **edges** are the boundaries between two faces, with exact curves
15//!   where a closed form exists (lines, circles, ellipses) and cubic
16//!   B-splines within a tolerance otherwise;
17//! - **vertices** are where three or more faces meet, solved on the exact
18//!   surfaces; tangent surfaces are detected analytically and their
19//!   contact lines used instead of an ill-conditioned solve;
20//! - **seams** and **parameter-space curves** are added on curved faces,
21//!   so that a STEP reader trims them exactly instead of re-fitting;
22//! - triangles tagged [`Surface::Faceted`] become planar faces, so
23//!   mesh-only regions mix with exact ones in one valid solid;
24//! - features of the mesh below the touching tolerance (edges shorter
25//!   than it, needle triangles narrower) are cleaned up first, and so are
26//!   faces and closed components of no area or volume.
27//!
28//! Each face names the input triangles it came from
29//! ([`Report::face_triangles`]), and [`reconstruct_located`] names the
30//! triangles where a failure happened, so a caller can tag the faces it
31//! cannot have exact as [`Surface::Faceted`] and try again.
32//!
33//! The mesh's tessellation never reaches the output, only its topology:
34//! build it with the [`primitives`] (or the same rules: segment counts a
35//! multiple of 4 with vertices on the axes, spheres with poles and an
36//! equator) so that the mesh's topology matches the exact model's at
37//! tangencies.
38//!
39//! Output is deterministic: the same input gives the same B-rep and the
40//! same STEP bytes on every platform (transcendental functions come from
41//! `libm`, not the platform).
42//!
43//! ```
44//! use meshbrep::{primitives, reconstruct, validate, measure, write_step, Options, StepOptions};
45//! use meshbrep::primitives::Transform;
46//!
47//! let mesh = primitives::frustum(10.0, 5.0, 5.0, 32, &Transform::IDENTITY);
48//! let brep = reconstruct(&mesh, &Options::default()).unwrap();
49//! assert!(validate(&brep, 1e-6).is_valid());
50//! let volume = measure(&brep).unwrap().volume;
51//! assert!((volume - std::f64::consts::PI * 250.0).abs() < 1e-9);
52//! let step = write_step(&brep, &StepOptions::default());
53//! assert!(step.contains("CYLINDRICAL_SURFACE"));
54//! ```
55
56pub 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/// Why reconstruction failed.
87#[derive(Clone, Debug, PartialEq)]
88pub enum Error {
89    /// The input is malformed (lengths, indices, non-finite numbers).
90    InvalidInput(String),
91    /// The mesh is not a closed, consistently oriented 2-manifold.
92    NotManifold(String),
93    /// A triangle names a surface kind not supported yet.
94    Unsupported(&'static str),
95    /// The mesh's topology could not be matched to the exact surfaces.
96    Reconstruction(String),
97    /// The mesh's topology differs from the exact model's: with its
98    /// corners at their exact positions, a face folds over itself (a
99    /// sliver the polygonal approximation left and the exact geometry
100    /// removes), or a corner lands on another edge of its own face (bodies
101    /// touching along an edge, joined on the wrong side by rounding). A
102    /// finer attribution mesh usually cures the first; the caller owns the
103    /// tessellation, so retrying is the caller's.
104    TopologyMismatch(String),
105    /// [`Options::should_stop`] asked reconstruction to stop.
106    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/// Why [`reconstruct_located`] failed, and where.
127#[derive(Clone, Debug, PartialEq)]
128pub struct Failure {
129    /// What went wrong.
130    pub error: Error,
131    /// Input triangles at the failure: the faces whose boundary folds, the
132    /// face that has no frame, the triangles where a boundary walk went
133    /// wrong. Empty when the failure has no place (a mesh that is not
134    /// closed, malformed input). A caller can tag the faces these belong
135    /// to [`Surface::Faceted`] and try again, so that one bad region does
136    /// not cost the whole model its exact surfaces.
137    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
157/// Rebuilds the exact B-rep of a tagged mesh.
158///
159/// The result is checked as it is built, but not validated in full: run
160/// [`validate`] and compare [`measure`] with the mesh's own volume before
161/// trusting it.
162pub fn reconstruct(mesh: &TaggedMesh, options: &Options) -> Result<Brep, Error> {
163    reconstruct_with(mesh, options, true).map_err(|f| f.error)
164}
165
166/// [`reconstruct`], with the input triangles at a failure (see
167/// [`Failure::triangles`]).
168pub 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            // Once per face: each check walks the face's loops, which is
185            // most of the time left on a large model.
186            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        // The first few: a rotated Menger sponge has dozens, and the
200        // message ends up in a user's report.
201        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    // Shells, and which of them are voids.
221    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    // A shell enclosing negative volume (by the mesh, which is cheap and
240    // independent of the exact geometry) is a cavity.
241    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    // Every face passed `face_crossing` above.
256    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
277/// The published form of the working topology: unused vertices dropped,
278/// vertices numbered in order of first use by an edge.
279fn 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    /// The capsule (a cylinder and two spheres, tangent along two
354    /// circles), unioned with Manifold.
355    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    /// `first` minus `rest`, through Manifold, tagged.
405    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    /// A planar face narrower than the tolerance has no trustworthy area
455    /// or orientation (OCCT reads it as a wire crossing itself), and the
456    /// validator says which faces: the four sides of a slab 5e-7 thick.
457    #[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    /// A closed edge belongs in a loop of its own. Inside a longer loop it
468    /// is a hole touching the boundary, which OCCT rejects: here the
469    /// cylinder's top circle, made to go round twice.
470    #[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        // Reconstruction checked every face for crossings, which
475        // `validate` then leaves out.
476        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    /// Holes nest inside their face's outer loop, outside each other: a
495    /// plate's hole marked as the outer loop leaves the square outside it.
496    #[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    /// Without analytic contacts, every vertex on the capsule's tangent
517    /// circles looks like a tangent crossing and splits the circle (the test
518    /// case x02 came out with 16 arcs each); arc merging must join them
519    /// back into one closed circle per side.
520    #[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    /// A closed component of zero volume lying in one plane (four
546    /// triangles over four coplanar points: Manifold leaves these where
547    /// coplanar cuts meet after a rotation) has no exact counterpart. It
548    /// used to fail as "face has no boundary"; it is dropped with a note,
549    /// and the rest reconstructs as if it were not there.
550    #[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        // A doubly covered quadrilateral in the plane z = 5: a
556        // tetrahedron flattened, closed and consistently oriented.
557        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        // With volume it is a real body, not something to drop silently.
586        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    /// A torus touches coaxial planes, cylinders and spheres along
617    /// circles, found from the profiles in its half-plane.
618    #[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            // Its top, its hole and its outside.
629            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            // Crossing, not tangent.
644            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}