SolidCraft: an open-source parametric 3D CAD application built in pure Rust. Desktop, web, and automation through MCP.
//! SolidCraft's mesher: each face of a schema 4 record ([`brep::Brep`]) triangulated in its own
//! parameters, with every edge sampled once so neighbouring faces share their boundary points
//! exactly, handed over as a [`TessPlan`] for the CPU or GPU evaluator. A boundary node's
//! parameters on each face come from that face's exact pcurve of the edge, at the node's curve
//! parameter: nothing is projected, and a seam's two sides are its two pcurves.
//!
//! Per face:
//! 1. a cheaper layout where the face suits one: planar faces whose boundary runs along their
//! parameter box, and curved ones, take a structured grid zipped to the edge nodes; a
//! four-cornered face whose sides are not parameter lines (mitred fillet strips, cross hole
//! walls) a Coons blend of its four sides; a trimmed face the patches of its cuts or the
//! iso-line grid cut along its motorcycle traces;
//! 2. otherwise, the general method for every face: constrained Delaunay in the face's (u, v),
//! with interior seeds and Ruppert refinement, every node then evaluated on the exact
//! surface (and refined where a triangle sags off it);
//! 3. a face even that refuses because its loops cross in (u, v) (a cusp, a sliver whose sides
//! sag across each other) is still a defect upstream, in the record's pcurves or seams, and is
//! named in the plan's stats ([`PlanStats::lenient`], with why it was refused) so it is
//! reported and fixed there; it is filled leniently in (u, v) (the sides crossing one already
//! kept are left out, see [`Lenient`]) so the display has no hole. A face that refuses even
//! that (its loops do not close in (u, v), or wind round a seam or pole) is left out of the
//! plan with no triangles and named in [`PlanStats::unmeshed`], and the rest of the body is
//! meshed; there is no other mesher to fall back to. A face whose pcurves do not lie on its edges is an error naming the face and
//! the edge, as is a body none of whose faces can be planned.
pub(crate) mod cdt;
pub(crate) mod collar;
pub(crate) mod coons;
pub(crate) mod cutgrid;
pub(crate) mod edges;
pub(crate) mod grid;
pub(crate) mod motorcycle;
pub(crate) mod pieces;
pub(crate) mod sag;
pub(crate) mod seam;
pub(crate) mod size;
pub(crate) mod surface;
pub(crate) mod tangle;
pub(crate) mod uv;
use solidcraft_geom::prelude::*;
use std::collections::HashMap;
use solidcore_record::Vec3;
use solidcore_record::brep::{self, Curve, Loop, Shell};
use solidcraft_geom::tess::{EvalSurface, FacePlan, TessPlan};
use crate::{KernelError, Result};
/// Whether [`plan_face`] may leave out of its constrained Delaunay the boundary sides that cross
/// a side already kept, and not hold the triangles to every side: the last resort for a face
/// that crosses itself in (u, v) (a cusp, a sliver whose sides sag across each other), so the
/// display has no hole. Its points stay in (u, v), so a curved face is still drawn on its
/// surface. Such a face is named in [`PlanStats::lenient`]: its pcurves or seams are wrong.
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
enum Lenient {
No,
Yes,
}
/// How the faces of a plan were meshed.
#[derive(Clone, Debug, Default, PartialEq, Eq)]
pub struct PlanStats {
pub planar: usize,
pub structured: usize,
pub delaunay: usize,
/// Faces every method refused, filled leniently in (u, v) (see [`Lenient`]) so the display
/// has no hole: each still a defect upstream, in its pcurves or seams.
pub lenient: Vec<RefusedFace>,
/// Faces even the lenient fill refused: left out of the plan (no triangles), so the rest of
/// the body is still meshed, each with why it could not be planned.
pub unmeshed: Vec<RefusedFace>,
}
/// A face a method refused: its index in the record and why.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct RefusedFace {
pub face: usize,
pub reason: String,
}
/// Curved faces from which their sizes are worked out on the worker pool.
const PARALLEL_SIZES: usize = 8;
/// Curved faces from which faces are planned on the worker pool (measured on the oracle
/// parts: two curved faces plan faster serially, four break even, six run twice as fast).
const PARALLEL_FACES: usize = 4;
/// Intersection curves (a Newton solve per point), or edges of any kind, from which edges are
/// sampled on the worker pool.
const PARALLEL_CURVES: usize = 2;
const PARALLEL_EDGES: usize = 256;
/// Most lines a curved face's grid gets in one direction: a turn's worth for each of the many
/// turns a coil's or a thread's wall winds (the grid as a whole stays within
/// [`grid::MAX_FACE_GRID`]).
const MAX_LINES: usize = 8192;
/// Most points Ruppert refinement may add to one face, beyond its seeds.
const MAX_REFINE: usize = 20_000;
/// Most rounds of splitting the edge segments where a face's sampled boundary crosses itself:
/// each round halves them, so their chords sag a quarter as far.
const MAX_UNTANGLE: u32 = 16;
fn unsupported(what: impl std::fmt::Display) -> KernelError {
KernelError::Failed(format!("not supported yet: tessellation: {what}"))
}
/// The surface kind of a face, for an error that names it.
fn kind(s: &brep::Surface) -> &'static str {
match s {
brep::Surface::Plane { .. } | brep::Surface::PlaneThrough { .. } => "plane",
brep::Surface::Cylinder { .. } => "cylinder",
brep::Surface::Cone { .. } => "cone",
brep::Surface::Sphere { .. } => "sphere",
brep::Surface::BallPatch { .. } => "ball patch",
brep::Surface::Torus { .. } => "torus",
brep::Surface::Spline { .. } => "spline",
brep::Surface::RationalSpline { .. } => "rational spline",
brep::Surface::PlacedRevolution { .. } => "revolution",
}
}
/// Whether each face's normal is its surface's natural normal, as the shell that uses it says
/// (a face no shell lists keeps its surface's).
fn forward_faces(b: &brep::Brep) -> Vec<bool> {
let mut forward = vec![true; b.faces.len()];
for shell in &b.shells {
if let Shell::Faces { faces, .. } = shell {
for f in faces {
if let Some(slot) = forward.get_mut(f.face as usize) {
*slot = f.forward;
}
}
}
}
forward
}
/// The edges of each face's loops, in loop order.
fn face_edges(f: &brep::Face) -> impl Iterator<Item = &brep::OrientedEdge> {
f.loops.iter().flat_map(|l| match l {
Loop::Edges { edges } => edges.as_slice(),
Loop::Vertex { .. } => &[],
})
}
/// Plan the tessellation of `b` with chord tolerance `tol` and, when given, a facet angle no
/// facet may turn more than (where it sags above the angle's floor). Faces and edges are the
/// record's, in its order.
pub(crate) fn plan(b: &brep::Brep, tol: f64, turn: Option<size::Turn>) -> Result<(TessPlan, PlanStats)> {
let faces = &b.faces;
let forward = forward_faces(b);
// The faces each edge bounds, each once, in the order of the edge's uses.
let edge_faces: Vec<Vec<usize>> = b
.edges
.iter()
.map(|e| {
let mut fs: Vec<usize> = Vec::with_capacity(e.uses.len());
for u in &e.uses {
if !fs.contains(&(u.face as usize)) {
fs.push(u.face as usize);
}
}
fs
})
.collect();
let rules = size::Rules::new(tol, size::extent(b.vertices.iter().map(|v| Vec3::new(v.point[0], v.point[1], v.point[2]))), turn);
// Each face's surface and target side length, then every edge once at the smaller size of
// its faces; faces then read their nodes. A planar face costs microseconds and a curved
// one about a hundred, so the pool is used only where curved faces (or intersection
// curves) make up the work.
let evals: Vec<(EvalSurface, surface::Params)> = faces
.iter()
.enumerate()
.map(|(fi, f)| surface::eval_surface(f.parameters(), f.domain).map_err(|e| unsupported(format!("face {fi} ({}): {e}", kind(&f.surface)))))
.collect::<Result<_>>()?;
let (evals, params): (Vec<EvalSurface>, Vec<surface::Params>) = evals.into_iter().unzip();
let curved = evals.iter().filter(|e| !matches!(e, EvalSurface::Plane { .. })).count();
let sizes: Vec<(f64, [f64; 2])> =
crate::par::map("face sizes", &evals, curved >= PARALLEL_SIZES, |s| Ok(size::face_size(s, &uv::domain(s), &rules)))
.into_iter()
.collect::<Result<_>>()?;
let face_h = |f: usize| sizes.get(f).map_or(rules.max_len, |(h, _)| *h);
let edge_h: Vec<f64> = edge_faces.iter().map(|fs| fs.iter().map(|&f| face_h(f)).fold(rules.max_len, f64::min)).collect();
let jobs: Vec<(usize, f64)> = edge_h.into_iter().enumerate().collect();
let solved = b.edges.iter().filter(|e| matches!(e.curve, Curve::SurfaceIntersection { .. })).count();
let mut nodes: Vec<edges::Nodes> = crate::par::map("edge nodes", &jobs, solved >= PARALLEL_CURVES || jobs.len() >= PARALLEL_EDGES, |(e, h)| {
edges::sample_edge(b, *e, &rules, *h)
})
.into_iter()
.collect::<Result<_>>()?;
relax_crowded_faces(b, &jobs, &rules, &mut nodes)?;
split_thin_loops(b, &mut nodes)?;
let indexed: Vec<usize> = (0..faces.len()).collect();
let face_boundary = |fi: usize, nodes: &[edges::Nodes]| {
let (Some(face), Some(eval), Some(map)) = (faces.get(fi), evals.get(fi), params.get(fi)) else {
return Err(unsupported(format!("face {fi}: missing")));
};
boundary(b, fi, face, eval, map, nodes, &rules)
};
let mut boundaries: Vec<Boundary> =
crate::par::map("face boundaries", &indexed, curved >= PARALLEL_FACES, |&fi| face_boundary(fi, &nodes)).into_iter().collect::<Result<_>>()?;
let tangled = untangle(b, &evals, &edge_faces, rules.tol, &mut nodes, &mut boundaries, &face_boundary)?;
let planned = crate::par::map("face tessellation", &indexed, curved >= PARALLEL_FACES, |&fi| {
let (Some(face), Some(eval), Some(size), Some(fb)) = (faces.get(fi), evals.get(fi), sizes.get(fi), boundaries.get(fi)) else {
return Err(unsupported(format!("face {fi}: missing")));
};
let refused = tangled.iter().find(|(f, _)| *f == fi).map(|(_, why)| why.as_str());
let (fp, stats) = plan_or_fill(fi, kind(face.parameters()), eval, &fb.loops, &rules, *size, fb.reach, refused)?;
let fwd = forward.get(fi).copied().unwrap_or(true);
let fp =
FacePlan { flip: !fwd, triangles: if fwd { fp.triangles } else { fp.triangles.into_iter().map(|[a, b, c]| [a, c, b]).collect() }, ..fp };
Ok((fp, stats))
});
let mut plan = TessPlan::default();
let mut stats = PlanStats::default();
// A face no method plans is left out, named in the stats, and the rest of the body is
// meshed; a body none of whose faces plan is the first face's error.
let mut first_error: Option<KernelError> = None;
for (fi, (r, eval)) in planned.into_iter().zip(evals).enumerate() {
let surface = u32::try_from(plan.surfaces.len()).map_err(|_| unsupported("too many faces"))?;
plan.surfaces.push(eval);
let (fp, s) = match r {
Ok(done) => done,
Err(e) => {
stats.unmeshed.push(RefusedFace { face: fi, reason: e.to_string() });
first_error.get_or_insert(e);
(FacePlan { face: u32::try_from(fi).unwrap_or(u32::MAX), ..FacePlan::default() }, PlanStats::default())
}
};
plan.faces.push(FacePlan { surface: Some(surface), ..fp });
stats.planar += s.planar;
stats.structured += s.structured;
stats.delaunay += s.delaunay;
stats.lenient.extend(s.lenient);
}
if let Some(e) = first_error
&& stats.unmeshed.len() == faces.len()
{
return Err(e);
}
plan.edges = nodes.into_iter().map(|n| n.points).collect();
plan.edge_faces = edge_faces.into_iter().map(|fs| fs.into_iter().map(|f| u32::try_from(f).unwrap_or(u32::MAX)).collect()).collect();
Ok((plan, stats))
}
/// Face `fi`'s boundary, loop by loop: the shared edge nodes (each edge's last node is the next
/// edge's first) and their parameters on the face's surface, from each edge use's exact pcurve
/// at the node's curve parameter. A seam edge's two uses on one face have their own pcurves, so
/// its two sides are told apart. A pcurve runs on continuously; where one edge meets the next, a
/// pcurve that starts a whole period along from where the previous one ended is moved back by
/// it, except in a direction the meeting point is a pole of (or lies on a patch side collapsed
/// to within its vertex's tolerance, see [`Boundary::reach`]): there the parameter is free, and
/// the two pcurves' own values are where the face's boundary runs along the pole from and to
/// (a meridian revolved half a turn meets the other at the pole half a period away; unwrapped,
/// its loop would wind round the surface). Each loop then starts at a node off every pole whose
/// predecessor is off them too, so the step from its last node to its first, which
/// [`seam::drift`] takes as the nearest copy, never crosses a pole. A vertex loop (a pole)
/// bounds no area and has no nodes of its own. Where the face's loops pass a vertex more than once
/// (two holes touching at a point, a loop through another's corner), the pcurves of the edges from
/// it give its parameters apart by their rounding, and two nodes 1e-14 apart put crossing
/// constraints into the triangulation: a pass whose parameters agree with the first pass's to
/// that rounding (1e-9 relative) takes the first's. Farther apart they are two places of the
/// surface (a seam's two sides, a closed spline's ends). A pcurve that does not cover its edge's
/// interval, or puts a node farther off the edge than the tolerances allow, is an error naming
/// the face and edge: the record is wrong there.
fn boundary(
b: &brep::Brep,
fi: usize,
face: &brep::Face,
s: &EvalSurface,
map: &surface::Params,
nodes: &[edges::Nodes],
rules: &size::Rules,
) -> Result<Boundary> {
let dom = uv::domain(s);
let fail = |e: u32, why: String| unsupported(format!("face {fi} ({}): edge {e}: {why}", kind(&face.surface)));
// How near a pole a node is one: the tolerance of a vertex of the face that lies on a patch
// side collapsed to within it, not to a point, as the record check takes a loop's pole; at
// most the chord tolerance, finer than which the mesh resolves nothing (a vertex tolerance
// as large as the surface's features would make a pole of every node near one).
let mut reach: f64 = 0.0;
for oe in face_edges(face) {
let (Some(edge), Some([p0, p1])) = (b.edges.get(oe.edge as usize), oe.pcurve.interval()) else { continue };
let tol = edge.vertices.get(usize::from(!oe.forward)).and_then(|v| b.vertices.get(*v as usize)).map_or(0.0, |v| v.tolerance.min(rules.tol));
let Some(q) = solidcraft_geom::brep::pcurve::eval(&oe.pcurve, if oe.forward { p0 } else { p1 }).map(|q| map.to_eval(q)) else { continue };
if tol.is_finite() && tol > reach && (0..2).any(|d| uv::degenerate_within(s, &dom, q, d, tol)) {
reach = tol;
}
}
let pole_along = |q: [f64; 2], d: usize| uv::degenerate_within(s, &dom, q, d, reach);
let mut out = Boundary { loops: Vec::with_capacity(face.loops.len()), segments: Vec::with_capacity(face.loops.len()), reach };
// Each vertex's parameters, from the first edge use of the face to start there.
let mut at_vertex: std::collections::HashMap<u32, [f64; 2]> = std::collections::HashMap::new();
// The vertex pairs an edge of the face joins.
let joined: std::collections::HashSet<(u32, u32)> = face_edges(face)
.filter_map(|oe| b.edges.get(oe.edge as usize))
.map(|e| (e.vertices[0].min(e.vertices[1]), e.vertices[0].max(e.vertices[1])))
.collect();
let vertex_point = |v: u32| b.vertices.get(v as usize).map(|x| (Vec3::new(x.point[0], x.point[1], x.point[2]), x.tolerance.max(0.0)));
// Each loop's nodes that are another edge's node (see [`edges::snap`]).
let mut snapped: Vec<Vec<bool>> = Vec::with_capacity(face.loops.len());
for l in &face.loops {
let Loop::Edges { edges } = l else { continue };
let (mut pts, mut uvs): (Vec<Vec3>, Vec<[f64; 2]>) = (Vec::new(), Vec::new());
let mut segs: Vec<(u32, u32)> = Vec::new();
let mut shared: Vec<bool> = Vec::new();
// Where the previous edge ended, and the periods its pcurve was moved by.
let (mut end, mut shift): (Option<[f64; 2]>, [f64; 2]) = (None, [0.0; 2]);
for oe in edges {
let n = nodes.get(oe.edge as usize).ok_or_else(|| fail(oe.edge, "no nodes".into()))?;
let edge = b.edges.get(oe.edge as usize).ok_or_else(|| fail(oe.edge, "no such edge".into()))?;
let [t0, t1] = edge.interval;
let [p0, p1] = oe.pcurve.interval().ok_or_else(|| fail(oe.edge, "a malformed pcurve".into()))?;
let slack = 1e-9 * (t1 - t0).abs().max(t0.abs()).max(t1.abs()).max(1.0);
if (p0 - t0).abs() > slack || (p1 - t1).abs() > slack {
return Err(fail(oe.edge, format!("its pcurve spans [{p0}, {p1}], the edge [{t0}, {t1}]")));
}
// The edge's own tolerance: how far its curve may stand off the face.
let accept = (rules.tol * 10.0).max(1e-6) + edge.tolerance.max(0.0);
let mut ep: Vec<Vec3> = n.points.clone();
let mut es: Vec<bool> = n.params.iter().map(|t| n.snapped.contains(t)).collect();
let mut eq: Vec<[f64; 2]> = Vec::with_capacity(ep.len());
for (k, (t, p)) in n.params.iter().zip(&n.points).enumerate() {
let q = solidcraft_geom::brep::pcurve::eval(&oe.pcurve, t.clamp(p0, p1))
.ok_or_else(|| fail(oe.edge, format!("its pcurve does not evaluate at t = {t}")))?;
let q = map.to_eval(q);
let on =
s.derivs(q[0], q[1]).map(|d| d.0).ok_or_else(|| fail(oe.edge, format!("node {k}: the surface does not evaluate at {q:?}")))?;
if !(on.dist(*p) <= accept) {
return Err(fail(oe.edge, format!("node {k}: its pcurve is {} mm off the edge at t = {t}", on.dist(*p))));
}
eq.push(q);
}
if !oe.forward {
ep.reverse();
eq.reverse();
es.reverse();
}
if let (Some(e), Some(&start)) = (end, eq.first()) {
for d in 0..2 {
let Some(per) = dom.period[d] else { continue };
if !(pole_along(e, d) || pole_along(start, d)) {
shift[d] = per * ((e[d] - start[d]) / per).round();
}
}
}
for q in &mut eq {
q[0] += shift[0];
q[1] += shift[1];
}
if let (Some(&v), Some(q)) = (edge.vertices.get(usize::from(!oe.forward)), eq.first_mut()) {
match at_vertex.get(&v) {
Some(first) => {
if (0..2).all(|d| (first[d] - q[d]).abs() <= 1e-9 * first[d].abs().max(q[d].abs()).max(1.0)) {
*q = *first;
}
}
None => {
// Another vertex of the face within the tolerance of both (and of the
// chord tolerance), and not joined to this one by an edge (which makes
// them two points however near: a step that small), is the same point:
// the record's corners a hair apart (a planar boolean's, where a cut-out's
// corner touches another loop's corner) are one point of the face, so its
// loops touch there instead of crossing.
let same = vertex_point(v).and_then(|(p, tv)| {
at_vertex.iter().filter(|(w, _)| **w != v && !joined.contains(&(v.min(**w), v.max(**w)))).find_map(|(w, wq)| {
let (pw, tw) = vertex_point(*w)?;
(p.dist(pw) <= tv.max(tw).min(rules.tol)).then_some(*wq)
})
});
if let Some(mut w) = same.filter(|w| !(0..2).any(|d| pole_along(*w, d) || pole_along(*q, d))) {
for d in 0..2 {
w[d] = uv::unwrap(w[d], q[d], dom.period[d]);
}
*q = w;
}
at_vertex.insert(v, *q);
}
}
}
end = eq.last().copied();
ep.pop();
eq.pop();
es.pop();
// The segment from each node on: the edge's own, counted from its start.
let m = ep.len() as u32;
segs.extend((0..m).map(|j| (oe.edge, if oe.forward { j } else { m - 1 - j })));
pts.extend(ep);
uvs.extend(eq);
shared.extend(es);
}
let n = uvs.len();
let pole = |q: &[f64; 2]| (0..2).any(|d| pole_along(*q, d));
let off = |k: usize| uvs.get(k).is_some_and(|q| !pole(q));
// A node off the poles whose predecessor is off them too; failing that (a whole sphere's
// seam in two segments: pole, equator, pole), one whose predecessor is a pole on the same
// edge, so the step into it is the edge's own and the step into that pole, from the
// edge before, is in the loop where it is unwrapped like any other.
let same_edge = |k: usize| segs.get((k + n - 1) % n).zip(segs.get(k)).is_some_and(|(a, b)| a.0 == b.0);
let start = (0..n).find(|&k| off(k) && off((k + n - 1) % n)).or_else(|| (0..n).find(|&k| off(k) && same_edge(k)));
if let Some(k) = start {
uvs.rotate_left(k);
pts.rotate_left(k);
segs.rotate_left(k);
shared.rotate_left(k);
}
if pts.len() >= 2 {
out.loops.push(seam::Loop { uv: uvs, pts });
out.segments.push(segs);
snapped.push(shared);
}
}
// A node snapped from another edge is that edge's node, the same point: where the face runs
// that edge too, the node takes the other's parameters, so the face's boundary passes one
// point of its (u, v) twice (a pinch) and does not cross itself there. Its own pcurve puts it
// within the chord tolerance of that point, not on it.
for (l, flags) in snapped.iter().enumerate() {
for (k, _) in flags.iter().enumerate().filter(|(_, f)| **f) {
let Some((&p, &q)) = out.loops.get(l).and_then(|lp| lp.pts.get(k).zip(lp.uv.get(k))) else { continue };
let partner = out
.loops
.iter()
.zip(&snapped)
.flat_map(|(lp, fs)| lp.pts.iter().zip(&lp.uv).zip(fs))
.filter(|((r, _), f)| !**f && **r == p)
.map(|((_, w), _)| *w)
.min_by(|a, b| (a[0] - q[0]).hypot(a[1] - q[1]).total_cmp(&(b[0] - q[0]).hypot(b[1] - q[1])));
if let (Some(mut w), Some(slot)) = (partner, out.loops.get_mut(l).and_then(|lp| lp.uv.get_mut(k))) {
for d in 0..2 {
if dom.period[d].is_some() {
w[d] = uv::unwrap(w[d], q[d], dom.period[d]);
}
}
*slot = w;
}
}
}
Ok(out)
}
/// A face's boundary loops, and for each loop node the edge segment that starts there: the
/// edge, and the segment's place along it from its start vertex. `reach`: how near a pole a
/// point of the face is taken as one (see [`uv::degenerate_within`]): the tolerance of a vertex
/// of it on a patch side collapsed to within that tolerance, else 0.
struct Boundary {
loops: Vec<seam::Loop>,
segments: Vec<Vec<(u32, u32)>>,
reach: f64,
}
/// Edges are sampled to the chord tolerance each on its own, so where two curves of one face
/// run closer than their chords sag (the two arcs of a thin lune, a sliver cap between two
/// cylinders), the chords may cross although the curves do not, and no triangulation follows
/// such a boundary. The edge segments whose chords cross another of the face (in its loop or
/// another, see [`tangle::crossing`]) are halved at their curve parameter's middle, on the edge,
/// so every face of the edge gets the new nodes; the faces of every edge split are checked again,
/// until no chords cross. Boundaries that still cross after [`MAX_UNTANGLE`] rounds, or would
/// put more than [`edges::MAX_EDGE_NODES`] on an edge, are an error naming the face and edges.
#[allow(clippy::too_many_arguments)]
fn untangle(
b: &brep::Brep,
evals: &[EvalSurface],
edge_faces: &[Vec<usize>],
tol: f64,
nodes: &mut [edges::Nodes],
boundaries: &mut [Boundary],
face_boundary: &(dyn Fn(usize, &[edges::Nodes]) -> Result<Boundary> + Sync),
) -> Result<Vec<(usize, String)>> {
let crossing = |fi: usize, fb: &Boundary| -> Vec<(u32, u32)> {
let Some(s) = evals.get(fi) else { return Vec::new() };
tangle::crossing(s, fb.reach, &fb.loops).into_iter().filter_map(|(l, k)| fb.segments.get(l)?.get(k).copied()).collect()
};
let indexed: Vec<usize> = (0..boundaries.len()).collect();
let curved = evals.iter().filter(|e| !matches!(e, EvalSurface::Plane { .. })).count();
let found: Vec<Vec<(u32, u32)>> = crate::par::map("boundary crossings", &indexed, curved >= PARALLEL_FACES, |&fi| {
Ok(boundaries.get(fi).map_or_else(Vec::new, |fb| crossing(fi, fb)))
})
.into_iter()
.collect::<Result<_>>()?;
let mut tangled: Vec<(usize, Vec<(u32, u32)>)> = found.into_iter().enumerate().filter(|(_, c)| !c.is_empty()).collect();
for round in 0..=MAX_UNTANGLE {
if tangled.is_empty() {
return Ok(Vec::new());
}
if round == MAX_UNTANGLE {
// Halving cannot part two curves that touch or cross: where they come within the chord
// tolerance of each other, they share nodes.
let faces: Vec<usize> = tangled.iter().map(|(fi, _)| *fi).collect();
tangled = snap_touches(evals, edge_faces, tol, nodes, boundaries, face_boundary, &faces)?;
// Each face still crossing, with why: planned leniently, and named (`plan_or_fill`).
return Ok(tangled
.iter()
.map(|(fi, c)| {
let mut es: Vec<u32> = c.iter().map(|(e, _)| *e).collect();
es.sort_unstable();
es.dedup();
let kind = b.faces.get(*fi).map_or("?", |f| kind(&f.surface));
(*fi, format!("face {fi} ({kind}): boundary crosses itself: edges {es:?} run closer together than their chords can follow after {MAX_UNTANGLE} halvings"))
})
.collect());
}
let mut split: Vec<(u32, u32)> = tangled.iter().flat_map(|(_, c)| c.iter().copied()).collect();
split.sort_unstable();
split.dedup();
let mut redo: Vec<usize> = Vec::new();
for run in split.chunk_by(|a, c| a.0 == c.0) {
let Some(&(e, _)) = run.first() else { continue };
let segs: Vec<u32> = run.iter().map(|(_, k)| *k).collect();
let Some(slot) = nodes.get_mut(e as usize) else { continue };
edges::split_segments(b, e as usize, slot, &segs)?;
redo.extend(edge_faces.get(e as usize).into_iter().flatten().copied());
}
redo.sort_unstable();
redo.dedup();
tangled.clear();
for fi in redo {
let fb = face_boundary(fi, nodes)?;
let c = crossing(fi, &fb);
if let Some(slot) = boundaries.get_mut(fi) {
*slot = fb;
}
if !c.is_empty() {
tangled.push((fi, c));
}
}
}
Ok(Vec::new())
}
/// Rounds of [`snap_touches`] before a face that still crosses itself is refused.
const MAX_SNAP: u32 = 8;
/// The faces `faces` whose boundaries cross themselves where two curves touch or cross (halving
/// their chords does not part them, see [`untangle`]), with every node that lies within the chord
/// tolerance `tol` of a crossing chord of another edge put onto that edge as well (see
/// [`edges::snap`]): the two edges share the point, the face's boundary passes it twice (a pinch,
/// as at a vertex two loops share), and the chords meet there instead of crossing. Where the
/// curves run within the tolerance of each other for a stretch (a sliver between two touches),
/// the nodes on either side are shared in turn, so the boundary runs out and back along one
/// polyline there: a slit, which bounds the face on neither side. A node is not snapped where the
/// pinch would turn part of its loop inside out by more than the tolerance (two curves crossing
/// at an angle: the boundary is wrong there, not within the tolerance). Every face of a changed
/// edge has its boundary built again. Returns the faces whose boundaries still cross, with the
/// crossing segments.
#[allow(clippy::too_many_arguments)]
fn snap_touches(
evals: &[EvalSurface],
edge_faces: &[Vec<usize>],
tol: f64,
nodes: &mut [edges::Nodes],
boundaries: &mut [Boundary],
face_boundary: &(dyn Fn(usize, &[edges::Nodes]) -> Result<Boundary> + Sync),
faces: &[usize],
) -> Result<Vec<(usize, Vec<(u32, u32)>)>> {
let crossing = |fi: usize, fb: &Boundary| -> Vec<(usize, usize)> {
let Some(s) = evals.get(fi) else { return Vec::new() };
tangle::crossing(s, fb.reach, &fb.loops)
};
let mut tangled: Vec<usize> = faces.to_vec();
for _ in 0..MAX_SNAP {
let mut add: HashMap<u32, Vec<(f64, Vec3)>> = HashMap::new();
for &fi in &tangled {
let Some(fb) = boundaries.get(fi) else { continue };
for (l, k) in crossing(fi, fb) {
let Some(&(e, j)) = fb.segments.get(l).and_then(|s| s.get(k)) else { continue };
if let Some((t, p)) = touch(fb, nodes, (l, k), (e, j), tol) {
add.entry(e).or_default().push((t, p));
}
}
}
if add.is_empty() {
break;
}
let mut redo: Vec<usize> = Vec::new();
for (e, points) in &add {
let Some(slot) = nodes.get_mut(*e as usize) else { continue };
edges::snap(*e as usize, slot, points)?;
redo.extend(edge_faces.get(*e as usize).into_iter().flatten().copied());
}
redo.extend(tangled.iter().copied());
redo.sort_unstable();
redo.dedup();
tangled.clear();
for fi in redo {
let fb = face_boundary(fi, nodes)?;
let crosses = !crossing(fi, &fb).is_empty();
if let Some(slot) = boundaries.get_mut(fi) {
*slot = fb;
}
if crosses {
tangled.push(fi);
}
}
if tangled.is_empty() {
return Ok(Vec::new());
}
}
Ok(tangled
.into_iter()
.filter_map(|fi| {
let fb = boundaries.get(fi)?;
let c: Vec<(u32, u32)> = crossing(fi, fb).into_iter().filter_map(|(l, k)| fb.segments.get(l)?.get(k).copied()).collect();
(!c.is_empty()).then_some((fi, c))
})
.collect())
}
/// The node of face boundary `fb` nearest the crossing chord `at` (loop, node) of its boundary,
/// segment `seg` (edge, segment from its start) of that edge, within `tol` of the chord strictly
/// between its ends, on another edge, and not yet on this one; with the parameter on the edge
/// where it projects onto the chord. `None` when there is none, or snapping it would turn part
/// of its loop inside out by more than the tolerance (see [`snap_touches`]).
fn touch(fb: &Boundary, nodes: &[edges::Nodes], at: (usize, usize), seg: (u32, u32), tol: f64) -> Option<(f64, Vec3)> {
let (e, j) = seg;
let n = nodes.get(e as usize)?;
let j = j as usize;
let (a, c) = (*n.points.get(j)?, *n.points.get(j + 1)?);
let (ta, tc) = (*n.params.get(j)?, *n.params.get(j + 1)?);
let ac = c - a;
let len2 = ac.dot(ac);
if !(len2 > 0.0) {
return None;
}
let mut best: Option<(f64, f64, Vec3)> = None;
for (l, lp) in fb.loops.iter().enumerate() {
let segs = fb.segments.get(l)?;
let m = lp.pts.len();
for (k, &p) in lp.pts.iter().enumerate() {
// The node's edges: the segment starting at it and the one ending there.
let edges_at = [segs.get(k).map(|s| s.0), segs.get((k + m - 1) % m).map(|s| s.0)];
if edges_at.contains(&Some(e)) || n.points.contains(&p) {
continue;
}
let f = (p - a).dot(ac) / len2;
let d = p.dist_to_segment(a, c);
if !(f > 1e-6 && f < 1.0 - 1e-6 && d <= tol) || best.is_some_and(|(bd, _, _)| bd <= d) {
continue;
}
if l == at.0 && inside_out(lp, at.1, k, tol) {
continue;
}
best = Some((d, ta + f * (tc - ta), p));
}
}
best.map(|(_, t, p)| (t, p))
}
/// Whether pinching loop `lp` at node `k` and a new node (the same point) on its chord from node
/// `at` would turn either part inside out by more than `tol`: a part whose winding in (u, v) is
/// against the loop's, and whose area is more than `tol` across (twice its area in 3D over its
/// length).
fn inside_out(lp: &seam::Loop, at: usize, k: usize, tol: f64) -> bool {
let m = lp.uv.len();
if m < 3 {
return false;
}
// The two parts: from the node after the chord's start round to `k`, and from `k` round to the
// chord's start.
let part = |from: usize, to: usize| -> Vec<usize> {
let mut out = Vec::new();
let mut i = from % m;
loop {
out.push(i);
if i == to % m || out.len() > m {
break;
}
i = (i + 1) % m;
}
out
};
let whole = area2(&lp.uv);
[part(at + 1, k), part(k, at)].iter().any(|ids| {
let uv: Vec<[f64; 2]> = ids.iter().filter_map(|&i| lp.uv.get(i).copied()).collect();
let pts: Vec<Vec3> = ids.iter().filter_map(|&i| lp.pts.get(i).copied()).collect();
if uv.len() < 3 || area2(&uv) * whole >= 0.0 {
return false;
}
// Newell's vector: twice the area of the polygon in 3D.
let twice = pts.iter().zip(pts.iter().cycle().skip(1)).fold(Vec3::ZERO, |acc, (p, q)| acc + p.cross(*q)).len();
let length: f64 = pts.iter().zip(pts.iter().cycle().skip(1)).map(|(p, q)| p.dist(*q)).sum();
twice > tol * length
})
}
/// Bounded work for the facet angle: a face whose boundary would get more than
/// [`size::MAX_ANGLE_BOUNDARY`] segments has its curved edges sampled again at twice the angle,
/// as often as it takes, down to the tolerance alone (a plate with a thousand small holes is
/// not worth a hundred times the work to draw each hole round). An edge keeps one set of nodes
/// for both its faces, at the coarser of their levels, so every rim of a crowded face gets the
/// Segments an edge loop needs to enclose an area in its face's (u, v).
const MIN_LOOP_SEGMENTS: usize = 3;
/// Every edge loop with fewer than [`MIN_LOOP_SEGMENTS`] segments has its edges' segments halved
/// until it has them: two short arcs (a lens), each within the chord tolerance and so one
/// segment, would otherwise be two chords on one line, a boundary of no area. The new nodes are
/// on the edges' curves and shared by every face that runs them, as all edge nodes are.
fn split_thin_loops(b: &brep::Brep, nodes: &mut [edges::Nodes]) -> Result<()> {
for f in &b.faces {
for l in &f.loops {
let brep::Loop::Edges { edges: uses } = l else { continue };
let mut es: Vec<usize> = uses.iter().map(|u| u.edge as usize).collect();
es.sort_unstable();
es.dedup();
let count = |nodes: &[edges::Nodes]| -> usize {
uses.iter().map(|u| nodes.get(u.edge as usize).map_or(0, |n| n.points.len().saturating_sub(1))).sum()
};
// Each round at least doubles every edge's segments: a few rounds always do.
for _ in 0..MIN_LOOP_SEGMENTS {
if count(nodes) >= MIN_LOOP_SEGMENTS {
break;
}
for &e in &es {
let Some(slot) = nodes.get_mut(e) else { continue };
let segs: Vec<u32> = (0..slot.points.len().saturating_sub(1)).filter_map(|k| u32::try_from(k).ok()).collect();
edges::split_segments(b, e, slot, &segs)?;
}
}
}
}
Ok(())
}
/// same share whatever the order of the faces.
fn relax_crowded_faces(b: &brep::Brep, jobs: &[(usize, f64)], rules: &size::Rules, nodes: &mut [edges::Nodes]) -> Result<()> {
let Some(turn) = rules.turn else { return Ok(()) };
let boundaries: Vec<Vec<usize>> = b.faces.iter().map(|f| face_edges(f).map(|oe| oe.edge as usize).collect()).collect();
let curved = |e: usize| b.edges.get(e).is_some_and(|e| !matches!(e.curve, Curve::Line { .. }));
let mut level: Vec<u8> = vec![0; nodes.len()];
for l in 1..=size::MAX_RELAX {
let segments = |e: &usize| nodes.get(*e).map_or(0, |n| n.points.len().saturating_sub(1));
let mut crowded: Vec<usize> = boundaries
.iter()
.filter(|es| es.iter().map(segments).sum::<usize>() > size::MAX_ANGLE_BOUNDARY)
.flatten()
.filter(|e| level.get(**e).copied().unwrap_or(0) < l && curved(**e))
.copied()
.collect();
crowded.sort_unstable();
crowded.dedup();
if crowded.is_empty() {
break;
}
let relaxed = size::Rules { turn: turn.relaxed(l), ..*rules };
for e in crowded {
let Some(&(_, h)) = jobs.get(e) else { continue };
if let Some(slot) = nodes.get_mut(e) {
*slot = edges::sample_edge(b, e, &relaxed, h)?;
}
if let Some(slot) = level.get_mut(e) {
*slot = l;
}
}
}
Ok(())
}
/// Twice the signed area of a parameter polygon.
fn area2(uv: &[[f64; 2]]) -> f64 {
let n = uv.len();
(0..n).map(|k| uv.get(k).zip(uv.get((k + 1) % n)).map_or(0.0, |(a, b)| a[0] * b[1] - b[0] * a[1])).sum()
}
/// A loop through both poles that turns straight back at one of them (it runs along a seam
/// and back: a whole sphere bounded by its meridian, or a sphere face whose split meridian it
/// uses both ways) retraces that seam once projected, since the periodic parameter carries on
/// unchanged across the pole. Across a pole it may jump by any amount, so the run from the
/// second pole back to the first is moved one period along, whichever way keeps the loop
/// within one period with a positive area: the seam's two uses then lie a period apart.
fn open_pole_to_pole(s: &EvalSurface, dom: &uv::Domain, reach: f64, l: &mut seam::Loop) {
let n = l.uv.len();
let poles: Vec<usize> = (0..n).filter(|&k| l.uv.get(k).is_some_and(|q| (0..2).any(|d| uv::degenerate_within(s, dom, *q, d, reach)))).collect();
let [p0, p1] = poles.as_slice() else { return };
for d in 0..2 {
let Some(per) = dom.period[d] else { continue };
let near =
|a: Option<&[f64; 2]>, b: Option<&[f64; 2]>| a.zip(b).is_some_and(|(a, b)| (a[0] - b[0]).abs().max((a[1] - b[1]).abs()) <= 1e-9 * per);
let turns_back = [*p0, *p1].iter().any(|&p| near(l.uv.get((p + n - 1) % n), l.uv.get((p + 1) % n)));
if !turns_back {
continue;
}
// Along the seam the periodic parameter is constant between the poles.
let second: Vec<usize> = (0..n).filter(|k| (k > p1 || k < p0) && *k != *p0 && *k != *p1).collect();
if second.is_empty() {
continue;
}
for sign in [1.0, -1.0] {
let mut moved = l.uv.clone();
for &k in &second {
if let Some(q) = moved.get_mut(k) {
q[d] += sign * per;
}
}
// The poles as the planner splits them: one copy at each neighbour's parameter.
let mut ring = Vec::with_capacity(n + 2);
for k in 0..n {
let (Some(q), Some(a), Some(b)) = (moved.get(k), moved.get((k + n - 1) % n), moved.get((k + 1) % n)) else { continue };
if k == *p0 || k == *p1 {
let (mut qa, mut qb) = (*q, *q);
qa[d] = a[d];
qb[d] = b[d];
ring.extend([qa, qb]);
} else {
ring.push(*q);
}
}
let (lo, hi) = ring.iter().fold((f64::INFINITY, f64::NEG_INFINITY), |(a, b), q| (a.min(q[d]), b.max(q[d])));
if hi - lo <= per * (1.0 + 1e-9) && area2(&ring) > 0.0 {
l.uv = moved;
return;
}
}
}
}
/// The poles of a loop where it turns straight back along a seam: the nodes either side have
/// the same parameters.
fn turning_poles(s: &EvalSurface, dom: &uv::Domain, reach: f64, per: f64, uv: &[[f64; 2]]) -> Vec<usize> {
let n = uv.len();
let near = |a: Option<&[f64; 2]>, b: Option<&[f64; 2]>| a.zip(b).is_some_and(|(a, b)| (a[0] - b[0]).abs().max((a[1] - b[1]).abs()) <= 1e-9 * per);
(0..n)
.filter(|&k| uv.get(k).is_some_and(|q| (0..2).any(|d| uv::degenerate_within(s, dom, *q, d, reach))))
.filter(|&k| near(uv.get((k + n - 1) % n), uv.get((k + 1) % n)))
.collect()
}
/// A loop with one pole, where it turns straight back along a seam, that winds once around the
/// periodic direction as projected: a half sphere's rim, then its seam down to the pole and up
/// again. Unwrapped along the loop, both runs of the seam lie on one parameter line, and the
/// period the loop is short of is closed by the rim's jump back. The face lies between the
/// seam's two uses a period apart, so the loop is unwrapped from the node after the pole round
/// to the pole, and starts at the node before it: the seam's uses then bound the face's parameter box on either side, and share
/// their nodes as every other edge does. Kept as it was unless the opened loop spans at most a
/// period with a positive area.
fn open_at_pole(s: &EvalSurface, dom: &uv::Domain, reach: f64, l: &mut seam::Loop) {
let n = l.uv.len();
if n < 4 || l.pts.len() != n {
return;
}
for d in 0..2 {
let Some(per) = dom.period[d] else { continue };
if (seam::drift(l, d, per).abs() - per).abs() > per * 1e-6 {
continue;
}
let [pole] = turning_poles(s, dom, reach, per, &l.uv)[..] else { continue };
// From the node after the pole round to the pole, unwrapped along the way.
let order: Vec<usize> = (1..=n).map(|i| (pole + i) % n).collect();
let mut uv: Vec<[f64; 2]> = Vec::with_capacity(n);
for &k in &order {
let Some(mut q) = l.uv.get(k).copied() else { return };
if let Some(pr) = uv.last() {
for e in 0..2 {
q[e] = uv::unwrap(q[e], pr[e], dom.period[e]);
}
}
uv.push(q);
}
// The pole's free parameter: its predecessor's (the poles are split from it later).
if let (Some(prev), Some(q)) = (uv.len().checked_sub(2).and_then(|i| uv.get(i)).copied(), uv.last_mut()) {
q[d] = prev[d];
}
let (lo, hi) = uv.iter().fold((f64::INFINITY, f64::NEG_INFINITY), |(a, b), q| (a.min(q[d]), b.max(q[d])));
// Started at the node before the pole, so the loop closes without a jump.
let mut opened = seam::Loop { uv, pts: order.iter().filter_map(|&k| l.pts.get(k).copied()).collect() };
opened.uv.rotate_right(2);
opened.pts.rotate_right(2);
if opened.pts.len() == n && hi - lo <= per * (1.0 + 1e-9) && area2(&opened.uv) > 0.0 && !seam::winds(std::slice::from_ref(&opened), d, per) {
*l = opened;
return;
}
}
}
/// Each loop is projected on its own, so along a closed direction a hole can come out a whole
/// period away from the outer loop: a dome's outer loop opened at its pole spans v in [-1, 0]
/// while the hole projects into [0, 1], outside it (tangency-labs/solidcore#433). Every other
/// loop is moved by whole periods to the copy whose middle is nearest the outer loop's (the
/// loop of largest area); a face that does not wind lies within one period, so that is the
/// copy inside it.
fn holes_beside_outer(dom: &uv::Domain, loops: &mut [seam::Loop]) {
let Some(outer) = loops.iter().map(|l| area2(&l.uv).abs()).enumerate().max_by(|a, b| a.1.total_cmp(&b.1)).map(|(i, _)| i) else { return };
let middle = |l: &seam::Loop, d: usize| {
let (lo, hi) = l.uv.iter().fold((f64::INFINITY, f64::NEG_INFINITY), |(a, b), q| (a.min(q[d]), b.max(q[d])));
0.5 * (lo + hi)
};
for d in 0..2 {
let Some(per) = dom.period[d] else { continue };
let Some(centre) = loops.get(outer).map(|l| middle(l, d)) else { continue };
for (i, l) in loops.iter_mut().enumerate() {
let k = ((middle(l, d) - centre) / per).round();
if i == outer || !k.is_finite() || k == 0.0 {
continue;
}
for q in &mut l.uv {
q[d] -= k * per;
}
}
}
}
/// One face, planned by [`plan_face`]; a face it refuses because its loops cross in (u, v) is
/// planned once more leniently (see [`Lenient`]) and named in the stats with the first refusal,
/// so the defect upstream is still reported. When the lenient fill refuses too, the first
/// refusal is the error (and [`plan`] leaves the face out, named). `refused`: a face whose
/// boundary still crosses itself after [`untangle`] (two edges meeting tangentially at a cusp,
/// whose chords cross however often they are halved), filled leniently straight away with that
/// reason.
fn plan_or_fill(
fi: usize,
kind: &str,
s: &EvalSurface,
loops: &[seam::Loop],
rules: &size::Rules,
size: (f64, [f64; 2]),
reach: f64,
refused: Option<&str>,
) -> Result<(FacePlan, PlanStats)> {
let mut stats = PlanStats::default();
let strict = match refused {
Some(why) => Err(unsupported(why.to_string())),
None => plan_face(fi, kind, s, loops, rules, size, reach, &mut stats, Lenient::No),
};
match strict {
Ok(fp) => Ok((fp, stats)),
Err(first) => {
let mut stats = PlanStats::default();
match plan_face(fi, kind, s, loops, rules, size, reach, &mut stats, Lenient::Yes) {
Ok(fp) => {
stats.lenient.push(RefusedFace { face: fi, reason: first.to_string() });
Ok((fp, stats))
}
Err(_) => Err(first),
}
}
}
}
/// One face: boundary loops in 3D (shared edge nodes) to parameters and triangles.
/// `size`: the face's target side length (mm) and the surface's mean speed along u and v.
/// `reach`: how near a pole a point is taken as one ([`Boundary::reach`]). `lenient`: the last resort
/// for a face no method could plan (see [`Lenient`]).
#[allow(clippy::too_many_arguments)]
fn plan_face(
fi: usize,
kind: &str,
s: &EvalSurface,
loops: &[seam::Loop],
rules: &size::Rules,
size: (f64, [f64; 2]),
reach: f64,
stats: &mut PlanStats,
lenient: Lenient,
) -> Result<FacePlan> {
let tol = rules.tol;
let (h, speed) = size;
let dom = uv::domain(s);
let fail = |why: &str| unsupported(format!("face {fi} ({kind}): {why}"));
let mut projected: Vec<seam::Loop> = loops.to_vec();
// A loop that winds around a periodic direction does not close in (u, v): the face is cut
// along a parameter line into one period (a seamless cylinder face, a helical trim).
// A loop that runs up a seam from a pole and straight back down it (a half sphere bounded
// by its rim and its seam used both ways) winds once as projected: it is opened at the pole.
for l in projected.iter_mut() {
open_at_pole(s, &dom, reach, l);
}
let wound: Vec<usize> = (0..2).filter(|&d| dom.period[d].is_some_and(|per| seam::winds(&projected, d, per))).collect();
// A face cut along a seam is a long winding strip whose sides are the cut lines and the
// boundary in turn: Delaunay with sag refinement meshes it (the patch layouts below assume
// boundary all round, and leave fans across the strip's corners off the surface).
let seamed = !wound.is_empty();
match wound.as_slice() {
[] => {}
[d] => {
let per = dom.period[*d].unwrap_or(std::f64::consts::TAU);
projected = seam::cut(s, &projected, *d, per, rules, h).ok_or_else(|| fail("boundary winds around the surface"))?;
}
_ => return Err(fail("boundary winds around the surface both ways")),
}
// A loop from pole to pole and back along one seam (a whole sphere as one face, as another
// kernel writes it) projects onto one parameter line: its second run is a period along.
if !seamed {
for l in projected.iter_mut() {
open_pole_to_pole(s, &dom, reach, l);
}
holes_beside_outer(&dom, &mut projected);
}
// Split poles.
let mut fixed: Vec<Vec3> = Vec::new();
let mut uvs: Vec<[f64; 2]> = Vec::new();
let mut ranges: Vec<std::ops::Range<usize>> = Vec::new();
for seam::Loop { uv: luv, pts } in &projected {
let start = uvs.len();
let n = luv.len();
for (k, (q, p)) in luv.iter().zip(pts).enumerate() {
// At a pole the parameter along the degenerate direction is free: one copy with
// the previous node's value, one with the next node's.
let (prev, next) = (luv.get((k + n - 1) % n).copied(), luv.get((k + 1) % n).copied());
let pole = (0..2).find(|&d| uv::degenerate_within(s, &dom, *q, d, reach));
match (pole, prev, next) {
(Some(d), Some(a), Some(b)) => {
let mut qa = *q;
let mut qb = *q;
qa[d] = a[d];
qb[d] = b[d];
uvs.push(qa);
fixed.push(*p);
if (qa[d] - qb[d]).abs() > 1e-12 {
uvs.push(qb);
fixed.push(*p);
}
}
_ => {
uvs.push(*q);
fixed.push(*p);
}
}
}
ranges.push(start..uvs.len());
}
if uvs.len() < 3 {
return Err(fail("degenerate boundary"));
}
let mut bbox = [(f64::MAX, f64::MIN); 2];
for p in &uvs {
for d in 0..2 {
bbox[d] = (bbox[d].0.min(p[d]), bbox[d].1.max(p[d]));
}
}
// Constrained Delaunay in (u, v) scaled to millimetres: equilateral seeds of side `h`,
// refined where triangles leave the surface, are too long or bend too much, then shaped by
// Ruppert refinement.
let polys: Vec<&[[f64; 2]]> = ranges.iter().filter_map(|r| uvs.get(r.clone())).collect();
let step = [h / speed[0], h / speed[1]];
let delaunay = || {
let seeds = cdt::lattice(bbox, step, &polys, speed);
let eval = |u: f64, v: f64| s.derivs(u, v).map(|(p, su, sv)| (p, su.cross(sv).normalized()));
let sag = cdt::Sag { eval: &eval, tol, h, turn: rules.turn, scale: speed };
let fill = cdt::Fill {
seeds: &seeds,
refine: Some((sag, MAX_REFINE)),
shape: !matches!(s, EvalSurface::Plane { .. }),
lenient: lenient == Lenient::Yes,
};
cdt::triangulate(&uvs, &ranges, fill).ok_or_else(|| fail("boundary crosses itself"))
};
// Planar and curved faces alike: a structured grid where the boundary runs along the
// parameter box (a rectangle, a cylinder half), a Coons grid on four corners, else Delaunay.
let planar = matches!(s, EvalSurface::Plane { .. });
// The lenient fill is the constrained Delaunay alone: the caller names the face in the stats.
let (extra, triangles) = if lenient == Lenient::Yes {
delaunay()?
} else {
let mut us = uv::divide(s, 0, bbox[0], bbox[1], rules, h, MAX_LINES);
let mut vs = uv::divide(s, 1, bbox[1], bbox[0], rules, h, MAX_LINES);
grid::thin(&mut us, &mut vs, grid::MAX_FACE_GRID);
let structured = match (ranges.len(), if seamed { None } else { grid::quad(&uvs) }) {
(1, Some(q)) => {
// Interior lines: the boundary's own where opposite sides agree (refined where the
// surface turns more between them inside the face), else the division.
let lines = |d: usize, div: &Vec<f64>| {
let inner = |l: Vec<f64>| l.into_iter().filter(|x| *x > bbox[d].0 && *x < bbox[d].1).collect::<Vec<f64>>();
match grid::aligned_lines(&uvs, &q, d) {
Some(aligned) => {
let ends: Vec<f64> = std::iter::once(bbox[d].0).chain(aligned).chain(std::iter::once(bbox[d].1)).collect();
inner(uv::refine(s, d, &ends, bbox[1 - d], rules, h, MAX_LINES))
}
None => inner(div.clone()),
}
};
let (lu, lv) = (lines(0, &us), lines(1, &vs));
let strip = match (lu.is_empty(), lv.is_empty()) {
(false, true) => grid::strip(&uvs, &q, 0),
(true, false) => grid::strip(&uvs, &q, 1),
_ => None,
};
strip.map(|t| (Vec::new(), t)).or_else(|| grid::structured(&uvs, &q, &grid::interior(lu, bbox[0]), &grid::interior(lv, bbox[1])))
}
_ => None,
};
let structured = match structured {
None if ranges.len() == 1 && !seamed => {
let fine = |a: [f64; 2], b: [f64; 2]| uv::fine_between(s, rules, h, a, b);
coons::coons(&uvs, &fixed, speed, grid::MAX_FACE_GRID, h, Some(&fine))
}
other => other,
};
match structured {
Some(r) => {
if planar {
stats.planar += 1;
} else {
stats.structured += 1;
}
r
}
None => {
// A curved face neither box nor four-cornered: cut into four-sided patches, else
// the iso-line grid cut along its motorcycle traces and trimmed by its boundary,
// else Delaunay. A plane: the butterfly of a round face, else Delaunay (a plane
// is shaded the same by any triangles, and its Delaunay needs no refinement).
// A curved strip, straight and within a side across one parameter (its division
// there has no line inside) and with no room for a point of its own (a thread's
// root band, which runs out obliquely so it has no four corners), is its boundary
// nodes alone, refined where the surface leaves them: patches and grid lines
// across it would only crowd it (the butterfly's cuts run lengthwise through a
// long strip, seeded the whole way). A strip curved across (a fillet narrower
// than a side) keeps the layouts that follow its curvature.
let face = Region { s, uvs: &uvs, fixed: &fixed, ranges: &ranges, rules, h, speed, us: &us, vs: &vs };
let strip = !planar && (us.len() <= 2 || vs.len() <= 2) && !cdt::has_room(bbox, step, &polys, speed);
let trimmed = if seamed || strip {
None
} else if planar {
if ranges.len() == 1 { plan_pieces(&face) } else { None }
} else {
plan_pieces(&face).or_else(|| {
let traces = motorcycle::traces(&uvs, &ranges, speed, 0.25 * h);
cutgrid::cut_grid(&uvs, &ranges, &us, &vs, &traces, speed)
})
};
match trimmed {
Some(r) => {
stats.structured += 1;
r
}
None => {
if planar {
stats.planar += 1;
} else {
stats.delaunay += 1;
}
delaunay()?
}
}
}
}
};
// At a pole the boundary has two copies of one node: a triangle on both copies has two
// corners at one point and no area (its other two sides are one segment both ways).
let pole_pair = |i: u32, j: u32| i != j && fixed.get(i as usize).zip(fixed.get(j as usize)).is_some_and(|(p, q)| p == q);
let mut triangles = triangles;
triangles.retain(|t| !(pole_pair(t[0], t[1]) || pole_pair(t[1], t[2]) || pole_pair(t[2], t[0])));
// A lenient fill leaves out the sides that cross: the boundary is followed everywhere else.
if lenient == Lenient::No && !closed_boundary(&ranges, &fixed, &uvs, &triangles) {
return Err(fail("triangulation does not follow the boundary"));
}
let mut all = uvs;
all.extend(extra);
// Whatever the layout, no triangle leaves the surface by more than the tolerance.
if !planar {
sag::refine(s, tol, reach, &fixed, &mut all, &mut triangles, MAX_REFINE);
sag::flip(s, tol, reach, &fixed, &all, &mut triangles);
}
// Both evaluators take a closed spline's parameters inside its active interval.
for q in &mut all {
*q = s.wrap(*q);
}
Ok(FacePlan { face: u32::try_from(fi).unwrap_or(u32::MAX), surface: None, uv: all, fixed, normals: Vec::new(), flip: false, triangles })
}
/// A face's (u, v) region and what meshing it needs.
struct Region<'a> {
s: &'a EvalSurface,
uvs: &'a [[f64; 2]],
fixed: &'a [Vec3],
ranges: &'a [std::ops::Range<usize>],
rules: &'a size::Rules,
h: f64,
speed: [f64; 2],
us: &'a [f64],
vs: &'a [f64],
}
/// A trimmed face cut into patches (squares round its holes or a butterfly in a round face,
/// joined to the outer loop by motorcycle traces), each meshed on its own (a Coons blend on its
/// best four corners; else the trimmed grid; else Delaunay), all sharing the cuts' nodes. The
/// cut nodes and patch interiors follow the boundary nodes. `None` when the cuts do not make
/// patches.
fn plan_pieces(f: &Region) -> Option<(Vec<[f64; 2]>, Vec<[u32; 3]>)> {
// The face's global seed: one spacing in every direction, the finest its size rules ask for
// along either parameter (the median gap between the grid lines they give, in mm). On a
// cylinder that is the spacing round it, which the cuts along its axis then get too.
let median_gap = |lines: &[f64], speed: f64| -> f64 {
let mut gaps: Vec<f64> = lines.windows(2).filter_map(|w| Some((w.get(1)? - w.first()?) * speed)).filter(|g| *g > 0.0).collect();
gaps.sort_by(f64::total_cmp);
gaps.get(gaps.len() / 2).copied().unwrap_or(f64::INFINITY)
};
let seed = median_gap(f.us, f.speed[0]).min(median_gap(f.vs, f.speed[1])).min(f.h);
let segments = collar::segments(f.uvs, f.ranges, f.speed, seed, matches!(f.s, EvalSurface::Plane { .. }))?;
let s = f.s;
let fine = |a: [f64; 2], b: [f64; 2]| uv::fine_between(s, f.rules, f.h, a, b);
// A cut's seeds: spaced from the boundary's own spacing at each end, growing geometrically
// between them, never wider than the global seed, and split further wherever the surface
// between two seeds fails the size rules.
let seeds = |a: [f64; 2], b: [f64; 2], sa: f64, sb: f64| -> Vec<f64> { graded(a, b, sa, sb, seed, f.speed, &fine) };
let (cut_uv, pieces) = pieces::cut(f.uvs, f.ranges, &segments, f.speed, &seeds)?;
let n = f.uvs.len();
let mut uv_all: Vec<[f64; 2]> = f.uvs.to_vec();
uv_all.extend_from_slice(&cut_uv);
let mut pos: Vec<Vec3> = f.fixed.to_vec();
for q in &cut_uv {
pos.push(s.derivs(q[0], q[1])?.0);
}
let mut extra: Vec<[f64; 2]> = cut_uv;
let mut tris: Vec<[u32; 3]> = Vec::new();
for pc in &pieces {
// The patch's own loops, numbered from zero.
let mut ids: Vec<u32> = pc.ring.to_vec();
let mut ranges = vec![std::ops::Range { start: 0, end: pc.ring.len() }];
for hole in &pc.holes {
ranges.push(ids.len()..ids.len() + hole.len());
ids.extend_from_slice(hole);
}
let luv: Vec<[f64; 2]> = ids.iter().map(|&k| uv_all.get(k as usize).copied()).collect::<Option<_>>()?;
let lpos: Vec<Vec3> = ids.iter().map(|&k| pos.get(k as usize).copied()).collect::<Option<_>>()?;
let mut bbox = [(f64::MAX, f64::MIN); 2];
for p in &luv {
for d in 0..2 {
bbox[d] = (bbox[d].0.min(p[d]), bbox[d].1.max(p[d]));
}
}
let clip = |lines: &[f64], (a, b): (f64, f64)| -> Vec<f64> {
std::iter::once(a).chain(lines.iter().copied().filter(|x| *x > a && *x < b)).chain(std::iter::once(b)).collect()
};
// A patch whose outline changes between boundary and cut at exactly four nodes (a
// quarter of a ring, a butterfly wing round a hole) takes those as its corners, so each
// side is all boundary or all cut; any other patch takes the best four of its corners.
let is_cut = |a: u32, b: u32| -> bool {
let (a, b) = (a as usize, b as usize);
a >= n || b >= n || !f.ranges.iter().any(|r| r.contains(&a) && r.contains(&b) && (a.abs_diff(b) == 1 || a.abs_diff(b) == r.len() - 1))
};
let ring = &pc.ring;
let switches: Vec<usize> = ring.corners().enumerate().filter(|&(_, (&p, &c, &x))| is_cut(p, c) != is_cut(c, x)).map(|(k, _)| k).collect();
// The patch is a rectangle in (u, v) with corners cut by free boundary (Lyon et al. §4;
// completed virtually in §4.2): its bounding box. A grid needs four real sides, so each
// corner is the node furthest out towards the box's corner (in the box's own
// proportions): an uncut corner is the corner itself, and on an arc cutting a corner it
// is the arc's 45° point, so the arc becomes a rounded corner shared by two sides.
let completed = || -> Option<[usize; 4]> {
let m = ring.len();
let at = |k: usize| luv.get(k).map(|q| [q[0] * f.speed[0], q[1] * f.speed[1]]);
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for k in 0..m {
let q = at(k)?;
for d in 0..2 {
lo[d] = lo[d].min(q[d]);
hi[d] = hi[d].max(q[d]);
}
}
let (w, h) = (hi[0] - lo[0], hi[1] - lo[1]);
if !(w > 0.0 && h > 0.0) {
return None;
}
let mut pick = [0usize; 4];
for (slot, dir) in pick.iter_mut().zip([[-1.0, -1.0], [1.0, -1.0], [1.0, 1.0], [-1.0, 1.0]]) {
*slot = (0..m).max_by(|&x, &y| {
let reach = |k: usize| at(k).map_or(f64::MIN, |q| dir[0] * (q[0] - lo[0]) / w + dir[1] * (q[1] - lo[1]) / h);
reach(x).total_cmp(&reach(y))
})?;
}
// Four distinct corners in the loop's (counter-clockwise) order.
let start = pick[0];
let rel = pick.map(|k| (k + m - start) % m);
(rel[0] < rel[1] && rel[1] < rel[2] && rel[2] < rel[3]).then_some(pick)
};
let quad = if pc.holes.is_empty() {
// Every patch is four-sided by construction: its corners are where its outline turns.
coons::coons(&luv, &lpos, f.speed, grid::MAX_FACE_GRID, f.h, None).or_else(|| {
match switches[..] {
[a, b, c, d] => coons::coons_at(&luv, &lpos, [a, b, c, d], grid::MAX_FACE_GRID, f.h, None),
_ => None,
}
.or_else(|| completed().and_then(|c| coons::coons_at(&luv, &lpos, c, grid::MAX_FACE_GRID, f.h, None)))
})
} else {
None
};
let local = quad
.or_else(|| if pc.holes.is_empty() { coons::coons_best(&luv, &lpos, f.speed, grid::MAX_FACE_GRID, f.h) } else { None })
.or_else(|| cutgrid::cut_grid(&luv, &ranges, &clip(f.us, bbox[0]), &clip(f.vs, bbox[1]), &[], f.speed))
.or_else(|| {
let polys: Vec<&[[f64; 2]]> = ranges.iter().filter_map(|r| luv.get(r.clone())).collect();
let seeds = cdt::lattice(bbox, [f.h / f.speed[0], f.h / f.speed[1]], &polys, f.speed);
let eval = |u: f64, v: f64| s.derivs(u, v).map(|(p, su, sv)| (p, su.cross(sv).normalized()));
let sag = cdt::Sag { eval: &eval, tol: f.rules.tol, h: f.h, turn: f.rules.turn, scale: f.speed };
cdt::triangulate(&luv, &ranges, cdt::Fill { seeds: &seeds, refine: Some((sag, MAX_REFINE)), shape: true, lenient: false })
})?;
let (lextra, ltris) = local;
let base = u32::try_from(n + extra.len()).ok()?;
let m = ids.len();
for t in ltris {
let map = |i: u32| -> Option<u32> {
let i = i as usize;
if i < m { ids.get(i).copied() } else { base.checked_add(u32::try_from(i - m).ok()?) }
};
tris.push([map(t[0])?, map(t[1])?, map(t[2])?]);
}
extra.extend(lextra);
}
Some((extra, tris))
}
/// Seeds on the segment `a`–`b` in (u, v) (fractions strictly between 0 and 1): node spacing
/// `sa` at `a` and `sb` at `b` (in the metric `speed`, each at most `h`), growing geometrically
/// between them (sizes `sa · q^k` summing to the length), then each interval split in half while
/// `fine` fails between its ends.
fn graded(a: [f64; 2], b: [f64; 2], sa: f64, sb: f64, h: f64, speed: [f64; 2], fine: &dyn Fn([f64; 2], [f64; 2]) -> bool) -> Vec<f64> {
let len = ((b[0] - a[0]) * speed[0]).hypot((b[1] - a[1]) * speed[1]);
let cap = |x: f64| {
if x.is_finite() && x > 0.0 {
x.min(if h > 0.0 { h } else { f64::INFINITY })
} else if h > 0.0 {
h
} else {
len
}
};
let (sa, sb) = (cap(sa), cap(sb));
let mut cuts: Vec<f64> = Vec::new();
if len.is_finite() && len > sa.max(sb) && sa > 0.0 && sb > 0.0 {
let q = (len - sa) / (len - sb);
let sizes: Vec<f64> = if (q - 1.0).abs() < 1e-3 || !(q > 0.0) || !q.is_finite() {
// Even spacing at the mean of the two.
let k = (len / (0.5 * (sa + sb))).round().clamp(1.0, 4096.0) as usize;
vec![len / k as f64; k]
} else {
let k = (1.0 + (sb / sa).ln() / q.ln()).round().clamp(1.0, 4096.0) as usize;
let raw: Vec<f64> = (0..k).map(|j| sa * q.powi(j as i32)).collect();
let total: f64 = raw.iter().sum();
raw.into_iter().map(|x| x * len / total).collect()
};
let mut at = 0.0;
for s in sizes.iter().take(sizes.len().saturating_sub(1)) {
at += s;
cuts.push(at / len);
}
}
// The size rules between seeds (sag, facet angle).
let point = |t: f64| [a[0] + (b[0] - a[0]) * t, a[1] + (b[1] - a[1]) * t];
let mut all: Vec<f64> = std::iter::once(0.0).chain(cuts).chain(std::iter::once(1.0)).collect();
for _ in 0..12 {
let mut next = Vec::with_capacity(all.len() * 2);
let mut split = false;
for w in all.windows(2) {
let (Some(&x), Some(&y)) = (w.first(), w.get(1)) else { continue };
next.push(x);
if !fine(point(x), point(y)) {
next.push(0.5 * (x + y));
split = true;
}
}
next.push(1.0);
all = next;
if !split || all.len() > 4096 {
break;
}
}
all.into_iter().filter(|t| *t > 0.0 && *t < 1.0).collect()
}
/// Every boundary segment (consecutive nodes of a loop) is the side of exactly one triangle (two
/// for a slit the loops run along both ways):
/// the face covers its boundary with nothing missing or doubled, so it meets its neighbours
/// exactly. Some boundary nodes are one vertex, a side ending on any of them the same side: pole
/// copies of one node (consecutive in a loop, at one point, the segment between them of no
/// length), and nodes at the very same (u, v), which the triangulation takes as one point: two
/// loops touching at a vertex they share (a ring standing on a perforated plate, tangent to the
/// holes beside it). A seam's two uses are at one point in space but a period apart in (u, v),
/// and stay two.
fn closed_boundary(ranges: &[std::ops::Range<usize>], fixed: &[Vec3], uvs: &[[f64; 2]], triangles: &[[u32; 3]]) -> bool {
let mut one: Vec<u32> = (0..fixed.len() as u32).collect();
let root = |one: &[u32], mut i: u32| {
while let Some(&j) = one.get(i as usize).filter(|j| **j != i) {
i = j;
}
i
};
let segment = |r: &std::ops::Range<usize>, k: usize| ((r.start + k) as u32, (r.start + (k + 1) % r.len()) as u32);
let join = |one: &mut [u32], a: u32, b: u32| {
let (ra, rb) = (root(one, a), root(one, b));
if let Some(x) = one.get_mut(rb.max(ra) as usize) {
*x = ra.min(rb);
}
};
for r in ranges {
for k in 0..r.len() {
let (a, b) = segment(r, k);
if fixed.get(a as usize).zip(fixed.get(b as usize)).is_some_and(|(p, q)| p == q) {
join(&mut one, a, b);
}
}
}
// By value: −0.0 and 0.0 are one point.
let key = |q: &[f64; 2]| [(q[0] + 0.0).to_bits(), (q[1] + 0.0).to_bits()];
let mut first: HashMap<[u64; 2], u32> = HashMap::with_capacity(uvs.len());
for (i, q) in uvs.iter().enumerate().take(fixed.len()) {
let i = i as u32;
let f = *first.entry(key(q)).or_insert(i);
if f != i {
join(&mut one, f, i);
}
}
let side = |a: u32, b: u32| {
let (a, b) = (root(&one, a), root(&one, b));
(a != b).then_some((a.min(b), a.max(b)))
};
let mut sides: HashMap<(u32, u32), u32> = HashMap::with_capacity(triangles.len() * 3);
for t in triangles {
for e in 0..3 {
if let Some(k) = side(t[e], t[(e + 1) % 3]) {
*sides.entry(k).or_default() += 1;
}
}
}
// Each boundary side has a triangle for every time the loops run along it: one, or two for
// a slit (a side run out and back, where the face meets itself along a line: a hole's wall
// touching the wall round it), one triangle either side.
let mut runs: HashMap<(u32, u32), u32> = HashMap::new();
for r in ranges {
for k in 0..r.len() {
let (a, b) = segment(r, k);
if let Some(k) = side(a, b) {
*runs.entry(k).or_default() += 1;
}
}
}
runs.iter().all(|(k, n)| sides.get(k).copied() == Some(*n))
}
#[cfg(test)]
mod tests;