use crate::nurbs::v3;
use crate::nurbs::V3;
use super::body::{Body, Edge, Face, Footprint, TrimLoop};
use super::{ssi, Curve3d, SsiResult, Surface};
use std::collections::{HashMap, HashSet};
use super::planar;
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum BooleanOp {
Union,
Difference,
Intersection,
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Declined {
NoClosedForm { face_a: usize, face_b: usize },
NeedsArrangement { face: usize },
UnclassifiablePiece { face: usize },
NotWatertight { open_edges: usize },
TangentialContact { face_a: usize, face_b: usize },
NotASolid,
}
type Carried = (u8, usize, Vec<V3>, bool, Vec<usize>);
type RimPart = (u8, usize, (i64, i64, i64), (i64, i64, i64));
type RimCut = ((usize, usize), Vec<usize>);
type EdgeHalf = (Vec<usize>, Vec<usize>);
type Chord = (usize, Vec<[f64; 2]>, Vec<usize>);
struct Piece {
surface: Surface,
loops: Vec<TrimLoop>,
u_range: (f64, f64),
v_range: (f64, f64),
u_wraps: bool,
v_wraps: bool,
flipped: bool,
sample: V3,
shared_wall: Option<(usize, bool)>,
bounding: Vec<usize>,
carried: Vec<Carried>,
}
struct SharedCurve {
vertices: Vec<usize>,
closed: bool,
}
impl Body {
pub fn boolean(&self, other: &Body, op: BooleanOp, tolerance: f64) -> Result<Body, Declined> {
if !self.is_valid_solid(tolerance) || !other.is_valid_solid(tolerance) {
return Err(Declined::NotASolid);
}
let mut curves: Vec<(usize, usize, Vec<Curve3d>)> = Vec::new();
let mut coincident: Vec<(usize, usize, bool)> = Vec::new();
let box_both = {
let (mut lo, mut hi) = ([f64::MAX; 3], [f64::MIN; 3]);
for b in [self, other] {
extent_of(b, &mut lo, &mut hi);
}
let pad = (0..3).map(|k| hi[k] - lo[k]).fold(0.0f64, f64::max) * 0.05 + tolerance;
(
[lo[0] - pad, lo[1] - pad, lo[2] - pad],
[hi[0] + pad, hi[1] + pad, hi[2] + pad],
)
};
for (ia, fa) in self.faces().iter().enumerate() {
for (ib, fb) in other.faces().iter().enumerate() {
let (sa, sb) = (&self.surfaces()[fa.surface], &other.surfaces()[fb.surface]);
match ssi(sa, sb) {
SsiResult::Disjoint => {}
SsiResult::Coincident { opposite } => {
if self.faces_overlap(ia, other, ib, tolerance) {
coincident.push((ia, ib, opposite));
}
}
SsiResult::Unknown => {
let traced = super::intersect::march(sa, sb, box_both, tolerance);
let reaching: Vec<Curve3d> = traced
.into_iter()
.filter(|c| {
self.curve_reaches_face(ia, c, tolerance)
&& other.curve_reaches_face(ib, c, tolerance)
})
.collect();
if reaching.is_empty() {
continue;
}
curves.push((ia, ib, reaching));
}
SsiResult::Curves(cs) => {
let reaching: Vec<Curve3d> = cs
.into_iter()
.filter(|c| {
self.curve_reaches_face(ia, c, tolerance)
&& other.curve_reaches_face(ib, c, tolerance)
})
.collect();
if reaching.iter().any(|c| matches!(c, Curve3d::Point(_))) {
return Err(Declined::TangentialContact {
face_a: ia,
face_b: ib,
});
}
if !reaching.is_empty() {
curves.push((ia, ib, reaching));
}
}
}
}
}
let mut vertices: Vec<V3> = Vec::new();
let mut shared: Vec<SharedCurve> = Vec::new();
let mut by_pair: Vec<(usize, usize, Vec<usize>)> = Vec::new();
for (ia, ib, cs) in &curves {
let mut ids = Vec::with_capacity(cs.len());
for c in cs {
let surface = &self.surfaces()[self.faces()[*ia].surface];
let full = match c {
Curve3d::Sampled { points, closed } => {
(if *closed {
points.len()
} else {
points.len() - 1
}) as f64
}
_ => std::f64::consts::TAU,
};
let all_of_it = |body: &Body, fi: usize| -> bool {
let f = &body.faces()[fi];
let rings = body.face_loops(fi);
if matches!(
Footprint::of(&rings, f.u_range, f.v_range),
Footprint::Rectangle { .. }
) {
return true;
}
body.clip_to_face(fi, c, tolerance).is_some_and(|spans| {
spans.iter().map(|(t0, t1)| t1 - t0).sum::<f64>() >= full * 0.999
})
};
let whole = sample_closed_curve(c, surface, tolerance)
.filter(|_| all_of_it(self, *ia) && all_of_it(other, *ib));
if let Some(uv) = whole {
let start = vertices.len();
for p in &uv {
vertices.push(surface.point(p[0], p[1]));
}
let mut vs: Vec<usize> = (start..vertices.len()).collect();
vs.push(start);
shared.push(SharedCurve {
vertices: vs,
closed: true,
});
ids.push(shared.len() - 1);
continue;
}
let Some(mine) = self.clip_to_face(*ia, c, tolerance) else {
return Err(Declined::NeedsArrangement { face: *ia });
};
let Some(theirs) = other.clip_to_face(*ib, c, tolerance) else {
return Err(Declined::NeedsArrangement { face: *ib });
};
for (a0, a1) in &mine {
for (b0, b1) in &theirs {
let (t0, t1) = (a0.max(*b0), a1.min(*b1));
if t1 - t0 <= tolerance {
continue; }
let pts = sample_open_curve(c, t0, t1, tolerance);
if pts.len() < 2 {
continue;
}
let start = vertices.len();
vertices.extend(pts);
shared.push(SharedCurve {
vertices: (start..vertices.len()).collect(),
closed: false,
});
ids.push(shared.len() - 1);
}
}
}
{
let sa = &self.surfaces()[self.faces()[*ia].surface];
let sb = &other.surfaces()[other.faces()[*ib].surface];
let touching = ids.iter().any(|&id| {
let vs = &shared[id].vertices;
let lean_at = |w: usize| -> Option<(f64, f64)> {
let p = vertices[vs[w]];
let q = vertices[vs[(w + 1) % vs.len()]];
let ((ua, va), (ub, vb)) = (sa.invert(p)?, sb.invert(p)?);
let (na, nb) = (sa.normal(ua, va)?, sb.normal(ub, vb)?);
let x = v3::cross(na, nb);
let step = [q[0] - p[0], q[1] - p[1], q[2] - p[2]];
Some((v3::dot(x, x).sqrt(), v3::dot(x, step)))
};
let last = if shared[id].closed {
vs.len()
} else {
vs.len().saturating_sub(1)
};
let mut before: Option<(f64, f64)> = None;
for w in 0..last {
let Some((sine, lean)) = lean_at(w) else {
before = None;
continue;
};
if sine < 1e-2 {
return true;
}
if let Some((was, dir)) = before {
if dir * lean < 0.0 && was.min(sine) < 0.2 {
return true;
}
}
before = Some((sine, lean));
}
false
});
if touching {
return Err(Declined::TangentialContact {
face_a: *ia,
face_b: *ib,
});
}
}
by_pair.push((*ia, *ib, ids));
}
let classify = {
let span = (0..3)
.map(|k| box_both.1[k] - box_both.0[k])
.fold(0.0f64, f64::max);
tolerance.max(span * 1e-4)
};
let solid_at = |b: &Body| {
let coarse = b.solid_triangles(classify);
if coarse.is_empty() {
b.solid_triangles(tolerance)
} else {
coarse
}
};
let mesh_a = solid_at(self);
let mesh_b = solid_at(other);
if mesh_a.is_empty() || mesh_b.is_empty() {
return Err(Declined::NotASolid);
}
let mut carried_points: HashMap<(u8, usize), Vec<V3>> = HashMap::new();
for (tag, body) in [(0u8, self), (1u8, other)] {
for (i, e) in body.edges().iter().enumerate() {
carried_points.insert(
(tag, i),
e.vertices
.iter()
.map(|&v| *body.vertices().get(v).unwrap_or(&[0.0; 3]))
.collect(),
);
}
}
for &(ia, ib, _) in &coincident {
for (for_a, into, from) in [
(true, (self, ia), (other, ib)),
(false, (other, ib), (self, ia)),
] {
for pts in Body::wall_outline(into.0, into.1, from.0, from.1) {
if pts.len() < 2 {
continue;
}
let closed = v3::dist(pts[0], *pts.last().unwrap()) <= tolerance;
let start = vertices.len();
let n = if closed { pts.len() - 1 } else { pts.len() };
vertices.extend(pts.into_iter().take(n));
let mut vs: Vec<usize> = (start..vertices.len()).collect();
if closed {
vs.push(start);
}
shared.push(SharedCurve {
vertices: vs,
closed,
});
let id = shared.len() - 1;
if for_a {
by_pair.push((ia, usize::MAX, vec![id]));
} else {
by_pair.push((usize::MAX, ib, vec![id]));
}
}
}
}
{
let quantum = tolerance.max(1e-12);
let key = |p: V3| {
let q = |x: f64| (x / quantum).round() as i64;
(q(p[0]), q(p[1]), q(p[2]))
};
let mut first: HashMap<(i64, i64, i64), usize> = HashMap::new();
let mut remap: Vec<usize> = Vec::with_capacity(vertices.len());
for (i, p) in vertices.iter().enumerate() {
let (x, y, z) = key(*p);
let mut found = None;
'search: for dx in -1..=1 {
for dy in -1..=1 {
for dz in -1..=1 {
if let Some(&j) = first.get(&(x + dx, y + dy, z + dz)) {
if v3::dist(*p, vertices[j]) <= quantum {
found = Some(j);
break 'search;
}
}
}
}
}
match found {
Some(j) => remap.push(j),
None => {
first.insert((x, y, z), i);
remap.push(i);
}
}
}
for curve in &mut shared {
for v in &mut curve.vertices {
*v = remap[*v];
}
curve.vertices.dedup();
if curve.closed && curve.vertices.len() > 1 {
let last = curve.vertices.len() - 1;
if curve.vertices[0] != curve.vertices[last] {
curve.vertices.push(curve.vertices[0]);
}
}
}
}
for pts in carried_points.values_mut() {
if pts.len() < 2 {
continue;
}
for curve in &shared {
for &vi in [curve.vertices.first(), curve.vertices.last()]
.into_iter()
.flatten()
{
let Some(&at) = vertices.get(vi) else {
continue;
};
if pts.iter().any(|p| v3::dist(*p, at) <= tolerance) {
continue;
}
let mut best = (f64::MAX, 0usize);
for i in 0..pts.len() - 1 {
let detour = v3::dist(pts[i], at) + v3::dist(at, pts[i + 1])
- v3::dist(pts[i], pts[i + 1]);
if detour < best.0 {
best = (detour, i + 1);
}
}
if best.0 <= tolerance {
pts.insert(best.1, at);
}
}
}
}
let mut seam_origins: HashMap<(u8, usize), f64> = HashMap::new();
let mut seam_cuts: HashMap<(u8, usize), Vec<(f64, usize)>> = HashMap::new();
for (tag, body) in [(0u8, self), (1u8, other)] {
for (fi, face) in body.faces().iter().enumerate() {
if !face.u_wraps {
continue;
}
let mine: Vec<usize> = by_pair
.iter()
.filter(|(a, b, _)| if tag == 0 { *a == fi } else { *b == fi })
.flat_map(|(_, _, ids)| ids.iter().copied())
.collect();
if mine.is_empty() {
continue;
}
let surface = &body.surfaces()[face.surface];
let Some(origin) = seam_origin(face, surface, &mine, &shared, &vertices) else {
continue;
};
for &e in &face.edges {
if let Some(pts) = carried_points.get_mut(&(tag, e)) {
insert_at_u(pts, surface, origin);
}
}
seam_origins.insert((tag, fi), origin);
for &id in &mine {
let across = by_pair.iter().find_map(|(a, b, ids)| {
if !ids.contains(&id) {
return None;
}
let (ours, theirs) = if tag == 0 { (*a, *b) } else { (*b, *a) };
if ours != fi {
return None;
}
let them = if tag == 0 { other } else { self };
them.faces()
.get(theirs)
.map(|f| them.surfaces()[f.surface].clone())
});
if let Some(v) = insert_seam_vertex(
&mut shared[id],
&mut vertices,
surface,
across.as_ref(),
origin,
face.u_range,
) {
seam_cuts.entry((tag, fi)).or_default().push(v);
}
}
}
}
for c in shared.iter_mut() {
if c.closed || c.vertices.len() != 2 {
continue;
}
let (a, b) = (vertices[c.vertices[0]], vertices[c.vertices[1]]);
vertices.push(v3::scale(v3::add(a, b), 0.5));
c.vertices.insert(1, vertices.len() - 1);
}
let mut carried_vertices: HashMap<(u8, usize), Vec<usize>> = HashMap::new();
{
let cell = tolerance.max(1e-12);
let key_of = |p: V3| -> (i64, i64, i64) {
(
(p[0] / cell).round() as i64,
(p[1] / cell).round() as i64,
(p[2] / cell).round() as i64,
)
};
let mut grid: HashMap<(i64, i64, i64), Vec<usize>> = HashMap::new();
for (i, q) in vertices.iter().enumerate() {
grid.entry(key_of(*q)).or_default().push(i);
}
for (&key, pts) in carried_points.iter() {
let mut ids = Vec::with_capacity(pts.len());
for p in pts {
let (x, y, z) = key_of(*p);
let mut found = None;
'search: for dx in -1..=1 {
for dy in -1..=1 {
for dz in -1..=1 {
for &i in grid.get(&(x + dx, y + dy, z + dz)).into_iter().flatten()
{
if v3::dist(*p, vertices[i]) <= tolerance * 0.5 {
found = Some(i);
break 'search;
}
}
}
}
}
ids.push(match found {
Some(v) => v,
None => {
vertices.push(*p);
grid.entry((x, y, z)).or_default().push(vertices.len() - 1);
vertices.len() - 1
}
});
}
carried_vertices.insert(key, ids);
}
}
let mut pieces: Vec<Piece> = Vec::new();
let wall_of_a: HashMap<usize, (usize, bool)> = coincident
.iter()
.map(|&(ia, ib, opposite)| (ia, (ib, !opposite)))
.collect();
let wall_of_b: HashMap<usize, (usize, bool)> = coincident
.iter()
.map(|&(ia, ib, opposite)| (ib, (ia, !opposite)))
.collect();
for (ia, fa) in self.faces().iter().enumerate() {
let mine: Vec<usize> = by_pair
.iter()
.filter(|(a, _, _)| *a == ia)
.flat_map(|(_, _, ids)| ids.iter().copied())
.collect();
let mut made = self.split_face(
0,
ia,
fa,
&mine,
&shared,
&vertices,
tolerance,
&carried_points,
&carried_vertices,
&seam_origins,
&seam_cuts,
)?;
if let Some(&(fj, same_way)) = wall_of_a.get(&ia) {
for piece in &mut made {
if other.point_on_face(fj, piece.sample, tolerance) {
piece.shared_wall = Some((fj, same_way));
}
}
}
pieces.extend(made);
}
let from_a = pieces.len();
for (ib, fb) in other.faces().iter().enumerate() {
let mine: Vec<usize> = by_pair
.iter()
.filter(|(_, b, _)| *b == ib)
.flat_map(|(_, _, ids)| ids.iter().copied())
.collect();
let mut made = other.split_face(
1,
ib,
fb,
&mine,
&shared,
&vertices,
tolerance,
&carried_points,
&carried_vertices,
&seam_origins,
&seam_cuts,
)?;
if let Some(&(fi, same_way)) = wall_of_b.get(&ib) {
for piece in &mut made {
if self.point_on_face(fi, piece.sample, tolerance) {
piece.shared_wall = Some((fi, same_way));
}
}
}
pieces.extend(made);
}
let mut kept: Vec<Piece> = Vec::new();
for (i, mut piece) in pieces.into_iter().enumerate() {
let from_this = i < from_a;
let inside_other = if from_this {
point_in_mesh(&mesh_b, piece.sample)
} else {
point_in_mesh(&mesh_a, piece.sample)
};
let (keep, flip) = match piece.shared_wall {
Some((_, same_way)) => match (op, from_this, same_way) {
(BooleanOp::Union, true, true) => (true, false),
(BooleanOp::Intersection, true, true) => (true, false),
(BooleanOp::Difference, _, true) => (false, false),
(BooleanOp::Difference, true, false) => (true, false),
_ => (false, false),
},
None => match (op, from_this, inside_other) {
(BooleanOp::Union, _, inside) => (!inside, false),
(BooleanOp::Intersection, _, inside) => (inside, false),
(BooleanOp::Difference, true, inside) => (!inside, false),
(BooleanOp::Difference, false, inside) => (inside, true),
},
};
if keep {
piece.flipped ^= flip;
kept.push(piece);
}
}
let result = Body::from_pieces(kept, vertices, shared, tolerance);
let mut check = result.clone();
check.refine_edges(tolerance);
let (_, report) = check.tessellate(tolerance);
if !report.is_closed() || report.carried_through > 0 {
return Err(Declined::NotWatertight {
open_edges: report.boundary_edges,
});
}
Ok(result)
}
fn point_on_face(&self, fi: usize, p: V3, tolerance: f64) -> bool {
let surface = &self.surfaces()[self.faces()[fi].surface];
if surface.distance(p) > tolerance.max(1e-9) {
return false;
}
let Some((u, v)) = surface.invert(p) else {
return false;
};
let loops = self.face_loops(fi);
let face = &self.faces()[fi];
let inside = match Footprint::of(&loops, face.u_range, face.v_range) {
Footprint::Rings(rings) => rings
.iter()
.find(|l| l.is_outer())
.is_some_and(|outer| outer.contains([u, v], surface.period())),
Footprint::Rectangle { u: ur, v: vr } => {
let within = |x: f64, r: (f64, f64), period: Option<f64>| {
let (lo, hi) = (r.0.min(r.1), r.0.max(r.1));
if x >= lo - tolerance && x <= hi + tolerance {
return true;
}
match period {
Some(t) => {
let folded = x - t * ((x - (lo + hi) * 0.5) / t).round();
folded >= lo - tolerance && folded <= hi + tolerance
}
None => false,
}
};
let (pu, pv) = surface.period();
within(u, ur, pu) && within(v, vr, pv)
}
};
inside
&& !loops
.iter()
.filter(|l| l.is_hole())
.any(|h| h.contains([u, v], surface.period()))
}
fn wall_outline(body: &Body, fi: usize, other: &Body, fj: usize) -> Vec<Vec<V3>> {
let surface = &body.surfaces()[body.faces()[fi].surface];
let mine = body.face_loops(fi);
let Some(outer) = mine.iter().find(|l| l.is_outer()) else {
return Vec::new();
};
let mut out = Vec::new();
for ring in other.face_loops(fj) {
if ring.is_hole() {
continue;
}
let mut uv: Vec<[f64; 2]> = ring
.vertices
.iter()
.filter_map(|&v| other.vertices().get(v))
.filter_map(|p| surface.invert(*p))
.map(|(u, v)| [u, v])
.collect();
if uv.len() < 3 {
continue;
}
uv.push(uv[0]);
if same_ring(&outer.uv, &uv) {
continue; }
for run in planar::clip_to_region(&outer.uv, &uv) {
if run.len() < 2 {
continue;
}
out.push(run.iter().map(|p| surface.point(p[0], p[1])).collect());
}
}
out
}
fn faces_overlap(&self, fi: usize, other: &Body, fj: usize, tolerance: f64) -> bool {
let surface = &self.surfaces()[self.faces()[fi].surface];
let mine = self.face_loops(fi);
let theirs = other.face_loops(fj);
let bounded = |ls: &[TrimLoop], f: &Face| {
matches!(Footprint::of(ls, f.u_range, f.v_range), Footprint::Rings(_))
};
if !bounded(&mine, &self.faces()[fi]) || !bounded(&theirs, &other.faces()[fj]) {
let face = &self.faces()[fi];
let (ur, vr) = (face.u_range, face.v_range);
const N: usize = 6;
return (1..N).any(|i| {
(1..N).any(|j| {
let u = ur.0 + (ur.1 - ur.0) * i as f64 / N as f64;
let v = vr.0 + (vr.1 - vr.0) * j as f64 / N as f64;
let p = surface.point(u, v);
self.point_on_face(fi, p, tolerance) && other.point_on_face(fj, p, tolerance)
})
});
}
let (Some(a), Some(b)) = (
mine.iter().find(|l| l.is_outer()),
theirs.iter().find(|l| l.is_outer()),
) else {
return false;
};
let theirs_here: Vec<[f64; 2]> = b
.vertices
.iter()
.filter_map(|&v| other.vertices().get(v))
.filter_map(|p| surface.invert(*p))
.map(|(u, v)| [u, v])
.collect();
if theirs_here.len() < 3 || a.uv.len() < 3 {
return false;
}
for (ring, against) in [(&a.uv, &theirs_here), (&theirs_here, &a.uv)] {
if let Some(p) = interior_point(ring) {
if point_in_ring(against, p) {
return true;
}
}
}
let n = a.uv.len();
let m = theirs_here.len();
for i in 0..n {
for j in 0..m {
if segments_properly_cross(
a.uv[i],
a.uv[(i + 1) % n],
theirs_here[j],
theirs_here[(j + 1) % m],
) {
return true;
}
}
}
let _ = tolerance;
false
}
fn curve_reaches_face(&self, face_index: usize, curve: &Curve3d, tolerance: f64) -> bool {
use std::f64::consts::TAU;
let face = &self.faces()[face_index];
let surface = &self.surfaces()[face.surface];
let loops = self.face_loops(face_index);
let extent = {
let (u0, u1) = face.u_range;
let (v0, v1) = face.v_range;
(u1 - u0).abs().max((v1 - v0).abs()).max(1.0) * 2.0
};
const N: usize = 64;
let sample = |i: usize| -> V3 {
match curve {
Curve3d::Line { .. } => curve.point(-extent + 2.0 * extent * i as f64 / N as f64),
Curve3d::Point(p) => *p,
Curve3d::Sampled { points, closed } => {
let last = if *closed {
points.len()
} else {
points.len() - 1
};
curve.point(last as f64 * i as f64 / N as f64)
}
_ => curve.point(TAU * i as f64 / N as f64),
}
};
for i in 0..=N {
let p = sample(i);
if surface.distance(p) > tolerance.max(1e-9) {
continue;
}
let Some((mut u, mut v)) = surface.invert(p) else {
continue;
};
let (pu, pv) = surface.periodic();
if pu {
u = face.u_range.0 + (u - face.u_range.0).rem_euclid(TAU);
}
if pv {
v = face.v_range.0 + (v - face.v_range.0).rem_euclid(TAU);
}
let in_footprint = u >= face.u_range.0 - 1e-9
&& u <= face.u_range.1 + 1e-9
&& v >= face.v_range.0 - 1e-9
&& v <= face.v_range.1 + 1e-9;
let degenerate_loops = loops.iter().all(|l| l.area.abs() < 1e-12);
if loops.is_empty() || degenerate_loops {
if in_footprint {
return true;
}
continue;
}
let Some(outer) = loops.iter().find(|l| l.is_outer()) else {
continue;
};
if deep_in_ring(&outer.uv, [u, v], ring_margin(&outer.uv))
&& !loops
.iter()
.filter(|l| l.is_hole())
.any(|h| h.contains([u, v], surface.period()))
{
return true;
}
}
false
}
fn clip_to_face(&self, fi: usize, curve: &Curve3d, tolerance: f64) -> Option<Vec<(f64, f64)>> {
use std::f64::consts::TAU;
let face = &self.faces()[fi];
let surface = &self.surfaces()[face.surface];
let loops = self.face_loops(fi);
let outer = loops.iter().find(|l| l.is_outer());
let margin = outer.map(|o| ring_margin(&o.uv)).unwrap_or(0.0);
let (lo, hi) = match curve {
Curve3d::Line { .. } => {
let reach = self
.vertices()
.iter()
.map(|p| v3::norm(v3::sub(*p, curve.point(0.0))))
.fold(0.0f64, f64::max)
.max(1.0)
* 2.0;
(-reach, reach)
}
Curve3d::Point(_) => return None,
Curve3d::Sampled { points, closed } => {
let last = if *closed {
points.len()
} else {
points.len() - 1
};
(0.0, last as f64)
}
_ => (0.0, TAU),
};
let sagging = matches!(curve, Curve3d::Sampled { .. });
let inside = |t: f64| -> bool {
let p = curve.point(t);
if !sagging && surface.distance(p) > tolerance.max(1e-9) {
return false;
}
let Some((mut u, mut v)) = surface.invert(p) else {
return false;
};
let (pu, pv) = surface.periodic();
if pu {
u = face.u_range.0 + (u - face.u_range.0).rem_euclid(std::f64::consts::TAU);
}
if pv {
v = face.v_range.0 + (v - face.v_range.0).rem_euclid(std::f64::consts::TAU);
}
let within = match outer {
Some(o) => deep_in_ring(&o.uv, [u, v], margin),
None => {
let face = &self.faces()[fi];
let pad = 1e-9;
u >= face.u_range.0 - pad
&& u <= face.u_range.1 + pad
&& v >= face.v_range.0 - pad
&& v <= face.v_range.1 + pad
}
};
within
&& !loops
.iter()
.filter(|l| l.is_hole())
.any(|h| h.contains([u, v], surface.period()))
};
const N: usize = 512;
let at = |i: usize| lo + (hi - lo) * i as f64 / N as f64;
let mut runs: Vec<(usize, usize)> = Vec::new();
let mut start: Option<usize> = None;
for i in 0..=N {
if inside(at(i)) {
start.get_or_insert(i);
} else if let Some(s) = start.take() {
runs.push((s, i - 1));
}
}
if let Some(s) = start {
runs.push((s, N));
}
if runs.is_empty() {
return None;
}
let edge = |inside_at: f64, outside_at: f64| -> f64 {
let (mut i, mut o) = (inside_at, outside_at);
let span = (hi - lo).abs().max(1.0);
for _ in 0..80 {
let m = 0.5 * (i + o);
if inside(m) {
i = m;
} else {
o = m;
}
if (i - o).abs() <= span * 1e-14 {
break;
}
}
0.5 * (i + o)
};
let spans: Vec<(f64, f64)> = runs
.into_iter()
.filter_map(|(a, b)| {
let t0 = if a == 0 {
at(0)
} else {
edge(at(a), at(a - 1))
};
let t1 = if b == N {
at(N)
} else {
edge(at(b), at(b + 1))
};
(t1 > t0).then_some((t0, t1))
})
.collect();
(!spans.is_empty()).then_some(spans)
}
#[allow(clippy::too_many_arguments)]
fn split_face(
&self,
tag: u8,
face_index: usize,
face: &Face,
curve_ids: &[usize],
shared: &[SharedCurve],
vertices: &[V3],
tolerance: f64,
carried_points: &HashMap<(u8, usize), Vec<V3>>,
carried_vertices: &HashMap<(u8, usize), Vec<usize>>,
seam_origins: &HashMap<(u8, usize), f64>,
seam_cuts: &HashMap<(u8, usize), Vec<(f64, usize)>>,
) -> Result<Vec<Piece>, Declined> {
let surface = self.surfaces()[face.surface].clone();
let mut loops = self.face_loops(face_index);
for l in &mut loops {
l.vertices = vec![usize::MAX; l.uv.len()];
}
let carried: Vec<Carried> = face
.edges
.iter()
.filter_map(|&e| {
let edge = self.edges().get(e)?;
let pts = carried_points.get(&(tag, e))?.clone();
let ids = carried_vertices.get(&(tag, e)).cloned().unwrap_or_default();
Some((tag, e, pts, edge.closed, ids))
})
.collect();
if curve_ids.is_empty() {
let Some(sample) = self.face_sample(face_index, &surface, &loops) else {
return Err(Declined::UnclassifiablePiece { face: face_index });
};
return Ok(vec![Piece {
surface,
loops: if loops.iter().all(|l| l.area.abs() > 1e-12) {
loops
} else {
Vec::new()
},
u_range: face.u_range,
v_range: face.v_range,
u_wraps: face.u_wraps,
v_wraps: face.v_wraps,
flipped: face.flipped,
sample,
shared_wall: None,
bounding: Vec::new(),
carried,
}]);
}
let mut rings: Vec<(usize, TrimLoop)> = Vec::new();
let mut chords: Vec<Chord> = Vec::new();
for &id in curve_ids {
let closed = shared[id].closed;
let vs = &shared[id].vertices;
let last = if closed { vs.len() - 1 } else { vs.len() };
let mut uv = Vec::with_capacity(last);
let mut anchor: Option<[f64; 2]> = Some([
0.5 * (face.u_range.0 + face.u_range.1),
0.5 * (face.v_range.0 + face.v_range.1),
]);
let (pu, pv) = surface.periodic();
let mut ok = true;
for &vi in &vs[..last] {
match surface.invert(vertices[vi]) {
Some((mut u, mut v)) => {
if let Some(a) = anchor {
if pu {
u = unwrap_near(u, a[0]);
}
if pv {
v = unwrap_near(v, a[1]);
}
}
anchor = Some([u, v]);
uv.push([u, v]);
}
None => {
ok = false;
break;
}
}
}
if !ok || uv.len() < 2 || (closed && uv.len() < 3) {
return Err(Declined::NeedsArrangement { face: face_index });
}
if closed {
let area = ring_area(&uv);
rings.push((
id,
TrimLoop {
vertices: vs[..last].to_vec(),
uv,
area,
},
));
} else {
let order = (0..uv.len()).collect();
chords.push((id, uv, order));
}
}
if matches!(surface, Surface::Plane { .. }) {
return self.split_planar(
face_index, face, &surface, loops, rings, chords, carried, shared, true, vertices,
tolerance,
);
}
if chords.is_empty() {
if let Ok(bands) =
self.split_swept(face_index, face, &surface, rings.clone(), carried.clone())
{
return Ok(bands);
}
}
let chosen_origin = || {
seam_origins
.get(&(tag, face_index))
.copied()
.or_else(|| seam_origin(face, &surface, curve_ids, shared, vertices))
};
let mut face = face.clone();
let mut v_seam: Option<(f64, f64)> = None;
if face.v_wraps {
let period = face.v_range.1 - face.v_range.0;
let used: Vec<f64> = rings
.iter()
.flat_map(|(_, r)| r.uv.iter())
.chain(chords.iter().flat_map(|(_, c, _)| c.iter()))
.map(|p| p[1])
.collect();
if !used.is_empty() {
let origin = widest_gap(&used, face.v_range.0, period);
let fold = |v: f64| origin + (v - origin).rem_euclid(period);
for (_, r) in rings.iter_mut() {
for p in r.uv.iter_mut() {
p[1] = fold(p[1]);
}
r.area = ring_area(&r.uv);
}
for (_, c, _) in chords.iter_mut() {
for p in c.iter_mut() {
p[1] = fold(p[1]);
}
}
face.v_range = (origin, origin + period);
v_seam = Some((origin, period));
}
}
if face.u_wraps {
let period = face.u_range.1 - face.u_range.0;
let mut wrapping: Vec<(usize, Vec<[f64; 2]>)> = Vec::new();
rings.retain(|(id, r)| {
let n = r.uv.len();
let mut turn = 0.0;
for i in 0..n {
let step = r.uv[(i + 1) % n][0] - r.uv[i][0];
turn += step - period * (step / period).round();
}
if turn.abs() < period * 0.5 {
return true;
}
wrapping.push((*id, r.uv.clone()));
false
});
if !wrapping.is_empty() {
let Some(origin) = chosen_origin() else {
return Err(Declined::NeedsArrangement { face: face_index });
};
let cut_open = chords.len();
for (id, uv) in wrapping {
let Some((chord, order)) = seam_chord(&uv, origin, period) else {
return Err(Declined::NeedsArrangement { face: face_index });
};
chords.push((id, chord, order));
}
for (_, r) in rings.iter_mut() {
for p in r.uv.iter_mut() {
p[0] = origin + (p[0] - origin).rem_euclid(period);
}
r.area = ring_area(&r.uv);
}
for (_, c, _) in chords.iter_mut() {
for p in c.iter_mut() {
let folded = origin + (p[0] - origin).rem_euclid(period);
p[0] = if (p[0] - (origin + period)).abs() <= period * 1e-9 {
origin + period
} else {
folded
};
}
}
for (_, c, order) in chords[cut_open..].iter_mut() {
let turn: f64 = c
.windows(2)
.map(|w| {
let d = w[1][0] - w[0][0];
d - period * (d / period).round()
})
.sum();
if turn < 0.0 {
c.reverse();
order.reverse();
}
let last = c.len() - 1;
c[0][0] = origin;
c[last][0] = origin + period;
}
face.u_range = (origin, origin + period);
if let Some((origin, period)) = v_seam {
let mut cut: Vec<Chord> = Vec::new();
for (id, c, order) in chords.drain(..) {
cut.extend(
split_at_seam(&c, &order, origin, period, 1)
.into_iter()
.map(|(uv, order)| (id, uv, order)),
);
}
chords = cut;
}
let known: &[(f64, usize)] = seam_cuts
.get(&(tag, face_index))
.map(|v| v.as_slice())
.unwrap_or(&[]);
let plain = parameter_outline(&face, &surface, tolerance, &carried, known);
let split = self.split_planar(
face_index,
&face,
&surface,
vec![plain],
rings.clone(),
chords.clone(),
carried.clone(),
shared,
false,
vertices,
tolerance,
);
if split.is_ok() {
return split;
}
let seam_cuts: Vec<(f64, usize)> = chords[cut_open..]
.iter()
.flat_map(|(_, c, _)| [c[0][1], c[c.len() - 1][1]])
.map(|v| (v, usize::MAX))
.collect();
if seam_cuts.is_empty() {
return split;
}
let broken = parameter_outline(&face, &surface, tolerance, &carried, &seam_cuts);
return self
.split_planar(
face_index,
&face,
&surface,
vec![broken],
rings,
chords,
carried,
shared,
false,
vertices,
tolerance,
)
.or(split);
}
let origin = chosen_origin().unwrap_or(face.u_range.0);
let fold = |u: f64| origin + (u - origin).rem_euclid(period);
for (_, r) in rings.iter_mut() {
for p in r.uv.iter_mut() {
p[0] = fold(p[0]);
}
r.area = ring_area(&r.uv);
}
let mut cut: Vec<Chord> = Vec::new();
for (id, c, order) in chords.drain(..) {
let folded: Vec<[f64; 2]> = c.iter().map(|p| [fold(p[0]), p[1]]).collect();
cut.extend(
split_at_seam(&folded, &order, origin, period, 0)
.into_iter()
.map(|(uv, order)| (id, uv, order)),
);
}
chords = cut;
face.u_range = (origin, origin + period);
}
if let Some((origin, period)) = v_seam {
let mut cut: Vec<Chord> = Vec::new();
for (id, c, order) in chords.drain(..) {
cut.extend(
split_at_seam(&c, &order, origin, period, 1)
.into_iter()
.map(|(uv, order)| (id, uv, order)),
);
}
chords = cut;
}
let outline = parameter_outline(&face, &surface, tolerance, &carried, &[]);
self.split_planar(
face_index,
&face,
&surface,
vec![outline],
rings,
chords,
carried,
shared,
false,
vertices,
tolerance,
)
}
#[allow(clippy::too_many_arguments)]
fn subdivide_face(
&self,
face_index: usize,
face: &Face,
surface: &Surface,
outer: &TrimLoop,
chords: &[Chord],
already: &[Vec<[f64; 2]>],
shared: &[SharedCurve],
carried: &[Carried],
vertices: &[V3],
tolerance: f64,
) -> Result<Vec<Piece>, Declined> {
let reach = tolerance * 4.0;
let near_curve = |uv: [f64; 2]| -> Option<usize> {
let p = surface.point(uv[0], uv[1]);
let mut best: Option<(f64, usize)> = None;
for (id, _, _) in chords {
for &vi in &shared[*id].vertices {
let Some(q) = vertices.get(vi) else { continue };
let d = v3::dist(p, *q);
if d <= reach && best.is_none_or(|(bd, _)| d < bd) {
best = Some((d, vi));
}
}
}
best.map(|(_, vi)| vi)
};
let mut paths: Vec<Vec<[f64; 2]>> = chords.iter().map(|(_, uv, _)| uv.clone()).collect();
paths.extend(already.iter().cloned());
let regions = planar::subdivide(&outer.uv, &paths)
.ok_or(Declined::NeedsArrangement { face: face_index })?;
if regions.len() < 2 && regions.iter().all(|r| r.holes.is_empty()) {
return Err(Declined::NeedsArrangement { face: face_index });
}
let mut out = Vec::with_capacity(regions.len());
for region in regions {
let vertices: Vec<usize> = region
.outer
.sources
.iter()
.map(|s| match s {
planar::Source::Chord { chord, point } => chords
.get(*chord)
.and_then(|c| c.2.get(*point).map(|k| (c.0, *k)))
.and_then(|(id, k)| shared[id].vertices.get(k))
.copied()
.unwrap_or(usize::MAX),
planar::Source::Boundary(i) => {
outer.vertices.get(*i).copied().unwrap_or(usize::MAX)
}
planar::Source::Crossing => usize::MAX,
})
.collect();
let vertices: Vec<usize> = vertices
.into_iter()
.zip(region.outer.sources.iter().zip(®ion.outer.uv))
.map(|(v, (src, uv))| {
if v == usize::MAX && matches!(src, planar::Source::Crossing) {
near_curve(*uv).unwrap_or(usize::MAX)
} else {
v
}
})
.collect();
let mut along: Vec<usize> = region
.outer
.sources
.iter()
.chain(region.holes.iter().flat_map(|h| h.sources.iter()))
.filter_map(|src| match src {
planar::Source::Chord { chord, .. } => chords.get(*chord).map(|c| c.0),
_ => None,
})
.collect();
along.sort_unstable();
along.dedup();
let ring = TrimLoop {
area: region.area.abs(),
uv: region.outer.uv,
vertices,
};
let mut loops = vec![ring];
for hole in region.holes {
let vertices = hole
.sources
.iter()
.map(|s| match s {
planar::Source::Chord { chord, point } => chords
.get(*chord)
.and_then(|c| c.2.get(*point).map(|k| (c.0, *k)))
.and_then(|(id, k)| shared[id].vertices.get(k))
.copied()
.unwrap_or(usize::MAX),
planar::Source::Boundary(i) => {
outer.vertices.get(*i).copied().unwrap_or(usize::MAX)
}
planar::Source::Crossing => usize::MAX,
})
.collect();
let area = -ring_area(&hole.uv).abs();
loops.push(TrimLoop {
area,
uv: hole.uv,
vertices,
});
}
if surface.kind() == "cylinder" && loops[0].wraps(surface.period()).iter().any(|&w| w) {
return Err(Declined::NeedsArrangement { face: face_index });
}
let Some(sample) = self.sample_between(surface, &loops) else {
return Err(Declined::UnclassifiablePiece { face: face_index });
};
let touching: Vec<Carried> = carried
.iter()
.filter(|(_, _, pts, _, _)| {
pts.iter().any(|p| {
loops.iter().any(|l| {
l.uv.iter()
.any(|q| v3::dist(surface.point(q[0], q[1]), *p) <= tolerance * 4.0)
})
})
})
.cloned()
.collect();
out.push(Piece {
surface: surface.clone(),
loops,
u_range: face.u_range,
v_range: face.v_range,
u_wraps: false,
v_wraps: false,
flipped: face.flipped,
sample,
shared_wall: None,
bounding: along,
carried: touching,
});
}
Ok(out)
}
#[allow(clippy::too_many_arguments)]
fn split_planar(
&self,
face_index: usize,
face: &Face,
surface: &Surface,
loops: Vec<TrimLoop>,
rings: Vec<(usize, TrimLoop)>,
chords: Vec<Chord>,
carried: Vec<Carried>,
shared: &[SharedCurve],
outline_from_edges: bool,
vertices: &[V3],
tolerance: f64,
) -> Result<Vec<Piece>, Declined> {
let Some(outer) = loops.iter().find(|l| l.is_outer()) else {
return Err(Declined::NeedsArrangement { face: face_index });
};
if !chords.is_empty() {
let mut paths = chords;
for (id, r) in rings {
let mut uv = r.uv.clone();
uv.push(uv[0]);
let mut order: Vec<usize> = (0..r.uv.len()).collect();
order.push(0);
paths.push((id, uv, order));
}
let already: Vec<Vec<[f64; 2]>> = loops
.iter()
.filter(|l| l.is_hole())
.map(|l| {
let mut uv = l.uv.clone();
uv.push(uv[0]);
uv
})
.collect();
return self.subdivide_face(
face_index, face, surface, outer, &paths, &already, shared, &carried, vertices,
tolerance,
);
}
let mut rings = rings;
let mut chords = chords;
let (pu_fold, pv_fold) = surface.periodic();
let fold = |p: [f64; 2]| -> [f64; 2] {
let mut q = p;
if pu_fold {
q[0] = face.u_range.0 + (q[0] - face.u_range.0).rem_euclid(std::f64::consts::TAU);
}
if pv_fold {
q[1] = face.v_range.0 + (q[1] - face.v_range.0).rem_euclid(std::f64::consts::TAU);
}
q
};
{
let mut clipped: Vec<Chord> = Vec::new();
rings.retain(|(id, r)| {
if r.uv.iter().all(|p| point_in_ring(&outer.uv, fold(*p))) {
return true;
}
let mut closed = r.uv.clone();
closed.push(closed[0]);
for run in planar::clip_to_region(&outer.uv, &closed) {
if run.len() < 2 {
continue;
}
let order: Vec<usize> = run
.iter()
.map(|p| {
r.uv.iter()
.position(|q| (q[0] - p[0]).hypot(q[1] - p[1]) <= 1e-12)
.unwrap_or(usize::MAX)
})
.collect();
clipped.push((*id, run, order));
}
false
});
chords.extend(clipped);
}
for (_, r) in &rings {
if !r.uv.iter().all(|p| point_in_ring(&outer.uv, fold(*p))) {
return Err(Declined::NeedsArrangement { face: face_index });
}
}
for (_, r) in rings.iter_mut() {
for p in r.uv.iter_mut() {
*p = fold(*p);
}
r.area = ring_area(&r.uv);
}
let mut out = Vec::with_capacity(rings.len() + 1);
let mut outside = loops.clone();
for (_, r) in &rings {
outside.push(oriented(r.clone(), false));
}
let Some(sample) = self.sample_between(surface, &outside) else {
return Err(Declined::UnclassifiablePiece { face: face_index });
};
{
let backed = outline_from_edges && !carried.is_empty();
out.push(Piece {
surface: surface.clone(),
loops: if backed { Vec::new() } else { outside },
u_range: face.u_range,
v_range: face.v_range,
u_wraps: false,
v_wraps: false,
flipped: face.flipped,
sample,
shared_wall: None,
bounding: rings.iter().map(|(id, _)| *id).collect(),
carried: carried.clone(),
});
}
for (id, r) in rings {
let ring = oriented(r, true);
let Some(sample) = self.sample_between(surface, std::slice::from_ref(&ring)) else {
return Err(Declined::UnclassifiablePiece { face: face_index });
};
out.push(Piece {
surface: surface.clone(),
loops: if matches!(surface, Surface::Plane { .. }) {
Vec::new()
} else {
vec![ring.clone()]
},
u_range: face.u_range,
v_range: face.v_range,
u_wraps: false,
v_wraps: false,
flipped: face.flipped,
sample,
shared_wall: None,
bounding: vec![id],
carried: Vec::new(),
});
}
Ok(out)
}
fn split_swept(
&self,
face_index: usize,
face: &Face,
surface: &Surface,
rings: Vec<(usize, TrimLoop)>,
carried: Vec<Carried>,
) -> Result<Vec<Piece>, Declined> {
let range = (face.v_range.1 - face.v_range.0).abs().max(1e-12);
let mut cuts: Vec<(f64, usize)> = Vec::new();
for (id, r) in &rings {
let vs: Vec<f64> = r.uv.iter().map(|p| p[1]).collect();
let spread = vs.iter().cloned().fold(f64::MIN, f64::max)
- vs.iter().cloned().fold(f64::MAX, f64::min);
if spread > range * 1e-3 {
return Err(Declined::NeedsArrangement { face: face_index });
}
let v = vs.iter().sum::<f64>() / vs.len() as f64;
if v > face.v_range.0 + range * 1e-6 && v < face.v_range.1 - range * 1e-6 {
cuts.push((v, *id));
}
}
cuts.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
let bounds: Vec<(f64, Option<usize>)> = if face.v_wraps && cuts.len() >= 2 {
let period = face.v_range.1 - face.v_range.0;
let mut round: Vec<(f64, Option<usize>)> =
cuts.iter().map(|&(v, id)| (v, Some(id))).collect();
let (first_v, first_id) = (round[0].0, round[0].1);
round.push((first_v + period, first_id));
round
} else {
let mut linear: Vec<(f64, Option<usize>)> = vec![(face.v_range.0, None)];
linear.extend(cuts.iter().map(|&(v, id)| (v, Some(id))));
linear.push((face.v_range.1, None));
linear
};
let mut out = Vec::with_capacity(bounds.len() - 1);
for w in bounds.windows(2) {
let mid = 0.5 * (w[0].0 + w[1].0);
let u_mid = 0.5 * (face.u_range.0 + face.u_range.1);
let at_end =
|v: f64| (v - w[0].0).abs() < range * 1e-6 || (v - w[1].0).abs() < range * 1e-6;
let mine: Vec<_> = carried
.iter()
.filter(|(_, _, pts, _, _)| {
let vs: Vec<f64> = pts
.iter()
.filter_map(|p| surface.invert(*p))
.map(|(_, v)| v)
.collect();
if vs.is_empty() {
return false;
}
let pad = range * 1e-6;
at_end(vs.iter().sum::<f64>() / vs.len() as f64)
|| vs.iter().any(|v| *v >= w[0].0 - pad && *v <= w[1].0 + pad)
})
.cloned()
.collect();
out.push(Piece {
surface: surface.clone(),
loops: Vec::new(),
u_range: face.u_range,
v_range: (w[0].0, w[1].0),
u_wraps: face.u_wraps,
v_wraps: false,
flipped: face.flipped,
sample: surface.point(u_mid, mid),
shared_wall: None,
bounding: [w[0].1, w[1].1].into_iter().flatten().collect(),
carried: mine,
});
}
Ok(out)
}
fn face_sample(&self, face_index: usize, surface: &Surface, loops: &[TrimLoop]) -> Option<V3> {
let face = &self.faces()[face_index];
let span = ((face.u_range.1 - face.u_range.0) * (face.v_range.1 - face.v_range.0)).abs();
let enclosing = loops
.iter()
.any(|l| l.area.abs() > span * 1e-9 && l.uv.len() >= 3);
if !enclosing {
return Some(surface.point(
0.5 * (face.u_range.0 + face.u_range.1),
0.5 * (face.v_range.0 + face.v_range.1),
));
}
self.sample_between(surface, loops)
}
fn sample_between(&self, surface: &Surface, loops: &[TrimLoop]) -> Option<V3> {
let outer = loops.iter().find(|l| l.is_outer())?;
let period = surface.period();
let usable = |c: [f64; 2]| -> bool {
outer.contains(c, period)
&& !loops
.iter()
.filter(|l| l.is_hole())
.any(|h| h.contains(c, period))
};
let edge: Vec<V3> = {
let total: usize = loops.iter().map(|l| l.uv.len()).sum();
let stride = total.div_ceil(256).max(1);
loops
.iter()
.flat_map(|l| l.uv.iter())
.step_by(stride)
.map(|q| surface.point(q[0], q[1]))
.collect()
};
let margin = |c: [f64; 2]| -> f64 {
let p = surface.point(c[0], c[1]);
edge.iter()
.map(|b| v3::dist(p, *b))
.fold(f64::MAX, f64::min)
};
let target = {
let (mut lo, mut hi) = ([f64::MAX; 3], [f64::MIN; 3]);
for p in &edge {
for k in 0..3 {
lo[k] = lo[k].min(p[k]);
hi[k] = hi[k].max(p[k]);
}
}
(0..3).map(|k| hi[k] - lo[k]).fold(0.0f64, f64::max) * 0.1
};
let mut best: Option<(f64, [f64; 2])> = None;
let consider = |c: [f64; 2], best: &mut Option<(f64, [f64; 2])>| -> bool {
if !usable(c) {
return false;
}
let m = margin(c);
if best.is_none_or(|(b, _)| m > b) {
*best = Some((m, c));
}
m >= target
};
for i in 1..outer.uv.len().saturating_sub(1) {
let c = [
(outer.uv[0][0] + outer.uv[i][0] + outer.uv[i + 1][0]) / 3.0,
(outer.uv[0][1] + outer.uv[i][1] + outer.uv[i + 1][1]) / 3.0,
];
if consider(c, &mut best) {
return best.map(|(_, c)| surface.point(c[0], c[1]));
}
}
let centroid = {
let n = outer.uv.len().max(1) as f64;
[
outer.uv.iter().map(|p| p[0]).sum::<f64>() / n,
outer.uv.iter().map(|p| p[1]).sum::<f64>() / n,
]
};
for t in [0.05, 0.15, 0.3, 0.5] {
for v in &outer.uv {
let c = [
v[0] + (centroid[0] - v[0]) * t,
v[1] + (centroid[1] - v[1]) * t,
];
if consider(c, &mut best) {
return best.map(|(_, c)| surface.point(c[0], c[1]));
}
}
}
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for p in &outer.uv {
for k in 0..2 {
lo[k] = lo[k].min(p[k]);
hi[k] = hi[k].max(p[k]);
}
}
const N: usize = 24;
for i in 0..N {
for j in 0..N {
let c = [
lo[0] + (hi[0] - lo[0]) * (i as f64 + 0.5) / N as f64,
lo[1] + (hi[1] - lo[1]) * (j as f64 + 0.5) / N as f64,
];
if consider(c, &mut best) {
return best.map(|(_, c)| surface.point(c[0], c[1]));
}
}
}
best.map(|(_, c)| surface.point(c[0], c[1]))
}
fn solid_triangles(&self, tolerance: f64) -> Vec<[V3; 3]> {
let mut body = self.clone();
body.refine_edges(tolerance);
let (mesh, report) = body.tessellate(tolerance);
if !report.is_closed() {
return Vec::new();
}
let Some(pos) = mesh.get_attribute("position") else {
return Vec::new();
};
let Some(idx) = &mesh.index else {
return Vec::new();
};
let v = |i: u32| -> V3 {
let o = i as usize * 3;
[
pos.array[o] as f64,
pos.array[o + 1] as f64,
pos.array[o + 2] as f64,
]
};
idx.chunks_exact(3)
.map(|t| [v(t[0]), v(t[1]), v(t[2])])
.collect()
}
fn from_pieces(
mut pieces: Vec<Piece>,
mut vertices: Vec<V3>,
shared: Vec<SharedCurve>,
tolerance: f64,
) -> Body {
let quantum = tolerance.max(1e-12);
let key = |p: V3| -> (i64, i64, i64) {
let q = |x: f64| (x / quantum).round() as i64;
(q(p[0]), q(p[1]), q(p[2]))
};
let mut welded: HashMap<(i64, i64, i64), usize> = HashMap::new();
for (i, v) in vertices.iter().enumerate() {
welded.entry(key(*v)).or_insert(i);
}
let mut carried_edge: HashMap<RimPart, usize> = HashMap::new();
let mut carried_vertices: Vec<(Vec<usize>, bool)> = Vec::new();
for piece in &pieces {
for (tag, id, pts, closed, _) in &piece.carried {
let (Some(first), Some(last)) = (pts.first(), pts.last()) else {
continue;
};
let slot = (*tag, *id, key(*first), key(*last));
if carried_edge.contains_key(&slot) {
continue;
}
let vs = pts
.iter()
.map(|p| {
*welded.entry(key(*p)).or_insert_with(|| {
vertices.push(*p);
vertices.len() - 1
})
})
.collect();
carried_edge.insert(slot, carried_vertices.len());
carried_vertices.push((vs, *closed));
}
}
for piece in &mut pieces {
for l in &mut piece.loops {
for (slot, uv) in l.vertices.iter_mut().zip(&l.uv) {
if *slot < vertices.len() {
continue;
}
let p = piece.surface.point(uv[0], uv[1]);
*slot = *welded.entry(key(p)).or_insert_with(|| {
vertices.push(p);
vertices.len() - 1
});
}
}
}
let mut surfaces = Vec::with_capacity(pieces.len());
let mut faces = Vec::with_capacity(pieces.len());
let mut edges: Vec<Edge> = Vec::new();
let mut edge_of_curve: Vec<Option<usize>> = vec![None; shared.len()];
let mut edge_of_carried: Vec<Option<usize>> = vec![None; carried_vertices.len()];
for p in pieces {
surfaces.push(p.surface);
let mut face_edges = Vec::with_capacity(p.bounding.len());
for id in p.bounding {
let e = *edge_of_curve[id].get_or_insert_with(|| {
edges.push(Edge {
surfaces: (surfaces.len() - 1, surfaces.len() - 1),
vertices: shared[id].vertices.clone(),
closed: shared[id].closed,
});
edges.len() - 1
});
if edges[e].surfaces.0 == edges[e].surfaces.1 {
edges[e].surfaces.1 = surfaces.len() - 1;
}
face_edges.push(e);
}
for (tag, id, pts, _, _) in &p.carried {
let (Some(first), Some(last)) = (pts.first(), pts.last()) else {
continue;
};
let Some(&slot) = carried_edge.get(&(*tag, *id, key(*first), key(*last))) else {
continue;
};
let e = *edge_of_carried[slot].get_or_insert_with(|| {
let (vs, closed) = carried_vertices[slot].clone();
edges.push(Edge {
surfaces: (surfaces.len() - 1, surfaces.len() - 1),
vertices: vs,
closed,
});
edges.len() - 1
});
if edges[e].surfaces.0 == edges[e].surfaces.1 {
edges[e].surfaces.1 = surfaces.len() - 1;
}
face_edges.push(e);
}
faces.push(Face {
surface: surfaces.len() - 1,
edges: face_edges,
flipped: p.flipped,
u_range: p.u_range,
v_range: p.v_range,
u_wraps: p.u_wraps,
v_wraps: p.v_wraps,
loops: (!p.loops.is_empty()).then_some(p.loops),
});
}
{
let mut claims: Vec<Vec<usize>> = vec![Vec::new(); edges.len()];
for (fi, f) in faces.iter().enumerate() {
for &e in &f.edges {
claims[e].push(fi);
}
}
let hits_of = |vs: &[usize], fi: usize| -> Option<Vec<bool>> {
let ls = faces[fi].loops.as_ref()?;
let s = &surfaces[faces[fi].surface];
let on = |p: V3| {
ls.iter().any(|l| {
let n = l.uv.len();
(0..n).any(|i| {
let (x, y) = (l.uv[i], l.uv[(i + 1) % n]);
let (a, b) = (s.point(x[0], x[1]), s.point(y[0], y[1]));
v3::dist(a, p) + v3::dist(p, b) - v3::dist(a, b) <= tolerance * 4.0
})
})
};
let hits: Vec<bool> = vs.iter().map(|&v| on(vertices[v])).collect();
hits.iter().any(|h| *h).then_some(hits)
};
let mut plan: Vec<(usize, Vec<RimCut>)> = Vec::new();
for e in 0..claims.len() {
if claims[e].len() <= 2 || edges[e].vertices.len() < 3 {
continue;
}
let vs = edges[e].vertices.clone();
let n = if vs.len() > 1 && vs.first() == vs.last() {
vs.len() - 1
} else {
vs.len()
};
let mut rows: Vec<(usize, Vec<bool>)> = Vec::new();
let mut usable = true;
for &fi in &claims[e] {
match hits_of(&vs, fi) {
Some(h) => rows.push((fi, h)),
None => {
usable = false;
break;
}
}
}
if !usable {
continue;
}
let pair_at = |k: usize| -> Option<(usize, usize)> {
let mut it = rows.iter().filter(|(_, h)| h[k]).map(|(fi, _)| *fi);
match (it.next(), it.next(), it.next()) {
(Some(a), Some(b), None) => Some((a.min(b), a.max(b))),
_ => None,
}
};
let first = (0..n).find_map(|k| pair_at(k).map(|p| (k, p)));
let Some((start, first_pair)) = first else {
continue;
};
let next_pair = |from: usize| -> Option<(usize, usize)> {
(1..n).find_map(|d| pair_at((from + d) % n))
};
let mut label: Vec<(usize, usize)> = vec![first_pair; n];
let mut carry = first_pair;
for step in 0..n {
let k = (start + step) % n;
match pair_at(k) {
Some(p) => carry = p,
None => {
if let Some(next) = next_pair(k) {
if next != carry {
carry = next;
}
}
}
}
label[k] = carry;
}
let mut spans: Vec<((usize, usize), usize, usize)> = Vec::new();
let mut at = start;
let mut run_start = start;
for step in 1..=n {
let k = (start + step) % n;
if step == n || label[k] != label[at] {
spans.push((label[at], run_start, (at + 1) % n));
run_start = k;
}
at = k;
}
let mut merged: Vec<((usize, usize), usize, usize)> = Vec::new();
for span in spans {
let len = (span.2 + n - span.1) % n;
match merged.last_mut() {
Some(prev) if len < 2 => prev.2 = span.2,
_ => merged.push(span),
}
}
if merged.len() > 1 {
let last = merged[merged.len() - 1];
if (last.2 + n - last.1) % n < 2 {
merged.remove(merged.len() - 1);
merged[0].1 = last.1;
}
}
let spans = merged;
if spans.len() < 2 {
continue;
}
let cuts: Vec<RimCut> = spans
.iter()
.map(|&((a, b), from, to)| ((from, to), vec![a, b]))
.collect();
plan.push((e, cuts));
}
for (e, groups) in plan {
let vs = edges[e].vertices.clone();
let n = if vs.len() > 1 && vs.first() == vs.last() {
vs.len() - 1
} else {
vs.len()
};
for (i, ((a, b), fs)) in groups.into_iter().enumerate() {
let part: Vec<usize> = {
let mut out = Vec::new();
let mut k = a;
loop {
out.push(vs[k]);
if k == b || out.len() > vs.len() {
break;
}
k = (k + 1) % n;
}
out
};
if part.len() < 2 {
continue;
}
let pair = (faces[fs[0]].surface, faces[fs[1]].surface);
let target = if i == 0 {
edges[e].vertices = part;
edges[e].closed = false;
edges[e].surfaces = pair;
e
} else {
edges.push(Edge {
surfaces: pair,
vertices: part,
closed: false,
});
edges.len() - 1
};
for &fi in &fs {
let mut took = false;
for slot in faces[fi].edges.iter_mut() {
if *slot == e {
*slot = target;
took = true;
}
}
if !took {
faces[fi].edges.push(target);
}
}
}
}
}
{
let mut want: HashMap<(usize, Vec<usize>), Vec<usize>> = HashMap::new();
for (fi, f) in faces.iter().enumerate() {
let Some(ls) = f.loops.as_ref() else { continue };
let named: std::collections::HashSet<usize> =
ls.iter().flat_map(|l| l.vertices.iter().copied()).collect();
for (id, c) in shared.iter().enumerate() {
let run: Vec<usize> = c
.vertices
.iter()
.copied()
.filter(|v| named.contains(v))
.collect();
if run.len() >= 2 {
want.entry((id, run)).or_default().push(fi);
}
}
}
for ((_, run), fs) in want {
if fs.len() != 2 {
continue;
}
let covered = fs.iter().any(|&fi| {
faces[fi].edges.iter().any(|&e| {
run.iter().all(|&v| {
edges[e].vertices.windows(2).any(|w| {
let (a, b) = (vertices[w[0]], vertices[w[1]]);
let p = vertices[v];
v3::dist(a, p) + v3::dist(p, b) - v3::dist(a, b) <= tolerance
})
})
})
});
if covered {
continue;
}
edges.push(Edge {
surfaces: (faces[fs[0]].surface, faces[fs[1]].surface),
vertices: run,
closed: false,
});
let e = edges.len() - 1;
for &fi in &fs {
faces[fi].edges.push(e);
}
}
}
{
let named: Vec<std::collections::HashSet<usize>> = faces
.iter()
.map(|f| {
f.loops
.as_ref()
.map(|ls| ls.iter().flat_map(|l| l.vertices.iter().copied()).collect())
.unwrap_or_default()
})
.collect();
let mut claims: Vec<Vec<usize>> = vec![Vec::new(); edges.len()];
for (fi, f) in faces.iter().enumerate() {
for &e in &f.edges {
claims[e].push(fi);
}
}
let mut stops: Vec<std::collections::HashSet<usize>> =
vec![std::collections::HashSet::new(); faces.len()];
for (e, cs) in claims.iter().enumerate() {
let vs = &edges[e].vertices;
if edges[e].closed || vs.len() < 2 {
continue;
}
for &fi in cs {
stops[fi].insert(vs[0]);
stops[fi].insert(vs[vs.len() - 1]);
}
}
let mut plan: Vec<(usize, Vec<EdgeHalf>)> = Vec::new();
for e in 0..claims.len() {
let vs = edges[e].vertices.clone();
if edges[e].closed || vs.len() < 3 {
continue;
}
let at: Vec<usize> = (1..vs.len() - 1)
.filter(|&k| claims[e].iter().any(|&fi| stops[fi].contains(&vs[k])))
.collect();
if at.is_empty() {
continue;
}
let mut bounds = vec![0usize];
bounds.extend(at);
bounds.push(vs.len() - 1);
let mut halves: Vec<(Vec<usize>, Vec<usize>)> = Vec::new();
let mut clean = true;
for w in bounds.windows(2) {
let part = vs[w[0]..=w[1]].to_vec();
if part.len() < 2 {
continue;
}
let takers: Vec<usize> = (0..faces.len())
.filter(|&fi| {
if !part.iter().all(|v| named[fi].contains(v)) {
return false;
}
let Some(ls) = faces[fi].loops.as_ref() else {
return true;
};
let sf = &surfaces[faces[fi].surface];
part.windows(2).all(|w| {
let mid = v3::scale(v3::add(vertices[w[0]], vertices[w[1]]), 0.5);
ls.iter().any(|l| {
let n = l.uv.len();
(0..n).any(|i| {
let (x, y) = (l.uv[i], l.uv[(i + 1) % n]);
let (a, b) = (sf.point(x[0], x[1]), sf.point(y[0], y[1]));
v3::dist(a, mid) + v3::dist(mid, b) - v3::dist(a, b)
<= tolerance * 4.0
})
})
})
})
.collect();
match takers.len() {
2 => halves.push((part, takers)),
0 => {}
_ => {
clean = false;
break;
}
}
}
if clean && !halves.is_empty() {
plan.push((e, halves));
}
}
for (e, halves) in plan {
for f in faces.iter_mut() {
f.edges.retain(|&x| x != e);
}
for (i, (part, takers)) in halves.into_iter().enumerate() {
let pair = (faces[takers[0]].surface, faces[takers[1]].surface);
let slot = if i == 0 {
edges[e].vertices = part;
edges[e].closed = false;
edges[e].surfaces = pair;
e
} else {
edges.push(Edge {
surfaces: pair,
vertices: part,
closed: false,
});
edges.len() - 1
};
for &fi in &takers {
faces[fi].edges.push(slot);
}
}
}
}
{
let mut claims: Vec<Vec<usize>> = vec![Vec::new(); edges.len()];
for (fi, f) in faces.iter().enumerate() {
for &e in &f.edges {
claims[e].push(fi);
}
}
let lone: Vec<usize> = (0..edges.len()).filter(|&e| claims[e].len() == 1).collect();
let same_span = |x: &[usize], y: &[usize]| -> bool {
if x.len() < 2 || y.len() < 2 {
return false;
}
let ends = |v: &[usize]| (vertices[v[0]], vertices[v[v.len() - 1]]);
let ((a0, a1), (b0, b1)) = (ends(x), ends(y));
(v3::dist(a0, b0) <= tolerance && v3::dist(a1, b1) <= tolerance)
|| (v3::dist(a0, b1) <= tolerance && v3::dist(a1, b0) <= tolerance)
};
for &ring in &lone {
let vs = edges[ring].vertices.clone();
if !edges[ring].closed || vs.len() < 4 {
continue;
}
let parts: Vec<Vec<usize>> = vs.windows(2).map(|w| w.to_vec()).collect();
let matched: Vec<Option<usize>> = parts
.iter()
.map(|part| {
let mut found = None;
for &other in &lone {
if other == ring || !same_span(part, &edges[other].vertices) {
continue;
}
if found.is_some() {
return None;
}
found = Some(other);
}
found
})
.collect();
if matched.iter().any(|m| m.is_none()) {
continue;
}
let holder = claims[ring][0];
faces[holder].edges.retain(|&e| e != ring);
for m in matched.into_iter().flatten() {
faces[holder].edges.push(m);
edges[m].surfaces = (faces[holder].surface, faces[claims[m][0]].surface);
}
}
}
{
let mut used = vec![false; edges.len()];
for f in &faces {
for &e in &f.edges {
used[e] = true;
}
}
if used.iter().any(|u| !u) {
let mut slot = vec![usize::MAX; edges.len()];
let mut kept: Vec<Edge> = Vec::with_capacity(edges.len());
for (e, edge) in edges.into_iter().enumerate() {
if used[e] {
slot[e] = kept.len();
kept.push(edge);
}
}
edges = kept;
for f in faces.iter_mut() {
for e in f.edges.iter_mut() {
*e = slot[*e];
}
}
}
}
settle_shared_vertices(&surfaces, &mut vertices, &mut faces, tolerance);
prune_orphan_vertices(&mut vertices, &mut edges, &mut faces);
materialise_seams(&mut edges, &mut faces);
materialise_seam_steps(&mut edges, &mut faces);
materialise_shared(&mut edges, &mut faces);
split_at_seam_ends(&mut edges, &mut faces);
let mut body = Body::from_parts(surfaces, vertices, edges, faces);
body.restate_rings();
body
}
}
fn seam_origin(
face: &Face,
surface: &Surface,
curve_ids: &[usize],
shared: &[SharedCurve],
vertices: &[V3],
) -> Option<f64> {
let period = face.u_range.1 - face.u_range.0;
if !period.is_finite() || period <= 0.0 {
return None;
}
let v_span = (face.v_range.1 - face.v_range.0).abs().max(1e-12);
let mut wants_seam = false;
for &id in curve_ids {
let uv: Vec<(f64, f64)> = shared[id]
.vertices
.iter()
.filter_map(|&vi| vertices.get(vi))
.filter_map(|p| surface.invert(*p))
.map(|(u, v)| (face.u_range.0 + (u - face.u_range.0).rem_euclid(period), v))
.collect();
if uv.len() < 2 {
continue;
}
let (v_lo, v_hi) = uv.iter().fold((f64::MAX, f64::MIN), |(l, h), (_, v)| {
(l.min(*v), h.max(*v))
});
if v_hi - v_lo <= v_span * 1e-3 {
continue;
}
wants_seam = true;
let us: Vec<f64> = uv.iter().map(|(u, _)| *u).collect();
let mut sorted = us.clone();
sorted.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
let gap = sorted
.windows(2)
.map(|w| w[1] - w[0])
.fold(sorted[0] + period - sorted[sorted.len() - 1], f64::max);
if gap < period * 0.02 {
return Some(us[0]);
}
}
if !wants_seam || !face.u_wraps {
return None;
}
let used: Vec<f64> = curve_ids
.iter()
.flat_map(|&id| shared[id].vertices.iter())
.filter_map(|&vi| vertices.get(vi))
.filter_map(|p| surface.invert(*p))
.map(|(u, _)| u)
.collect();
(!used.is_empty()).then(|| widest_gap(&used, face.u_range.0, period))
}
fn split_at_seam(
uv: &[[f64; 2]],
order: &[usize],
origin: f64,
period: f64,
axis: usize,
) -> Vec<(Vec<[f64; 2]>, Vec<usize>)> {
let other = 1 - axis;
let mut out = Vec::new();
let mut run: (Vec<[f64; 2]>, Vec<usize>) = (Vec::new(), Vec::new());
for i in 0..uv.len() {
run.0.push(uv[i]);
run.1.push(order[i]);
let Some(&next) = uv.get(i + 1) else { continue };
if (next[axis] - uv[i][axis]).abs() <= period * 0.5 {
continue;
}
let shift = if next[axis] > uv[i][axis] {
-period
} else {
period
};
let (a, b) = (uv[i], {
let mut q = next;
q[axis] = next[axis] + shift;
q
});
let edge = if b[axis] > a[axis] {
origin + period
} else {
origin
};
let far = if edge > origin {
origin
} else {
origin + period
};
let eps = period * 1e-6;
let at_seam = if (a[axis] - edge).abs() <= eps {
a[other]
} else if (b[axis] - edge).abs() <= eps {
b[other]
} else {
let t = if (b[axis] - a[axis]).abs() > f64::EPSILON {
((edge - a[axis]) / (b[axis] - a[axis])).clamp(0.0, 1.0)
} else {
0.0
};
a[other] + (b[other] - a[other]) * t
};
if (a[axis] - edge).abs() > eps {
let mut q = a;
q[axis] = edge;
q[other] = at_seam;
run.0.push(q);
run.1.push(order[i + 1]);
}
out.push(std::mem::take(&mut run));
if (next[axis] - far).abs() > eps {
let mut q = a;
q[axis] = far;
q[other] = at_seam;
run.0.push(q);
run.1.push(order[i + 1]);
}
}
if run.0.len() > 1 {
out.push(run);
}
out.retain(|(p, _)| p.len() > 1);
out
}
fn insert_seam_vertex(
curve: &mut SharedCurve,
vertices: &mut Vec<V3>,
surface: &Surface,
across: Option<&Surface>,
origin: f64,
range: (f64, f64),
) -> Option<(f64, usize)> {
let period = range.1 - range.0;
if !period.is_finite() || period <= 0.0 || curve.vertices.len() < 3 {
return None;
}
let fold = |u: f64| origin + (u - origin).rem_euclid(period);
let u_of = |vi: usize| -> Option<f64> {
vertices
.get(vi)
.and_then(|p| surface.invert(*p))
.map(|(u, _)| fold(u))
};
let n = curve.vertices.len();
let last = if curve.closed { n - 1 } else { n };
for i in 0..last {
let j = (i + 1) % last;
let (Some(a), Some(b)) = (u_of(curve.vertices[i]), u_of(curve.vertices[j])) else {
return None;
};
if (b - a).abs() < period * 0.5 {
continue;
}
let (from_a, from_b) = (a - origin, b - origin);
if from_a.min(from_b) <= period * 1e-9 || (period - from_a.max(from_b)) <= period * 1e-9 {
return None; }
let (pa, pb) = (vertices[curve.vertices[i]], vertices[curve.vertices[j]]);
let offset = |t: f64| -> Option<f64> {
let p = v3::add(pa, v3::scale(v3::sub(pb, pa), t));
let (u, _) = surface.invert(p)?;
let mut d = (u - origin).rem_euclid(period);
if d > period * 0.5 {
d -= period;
}
Some(d)
};
let (Some(da), Some(_db)) = (offset(0.0), offset(1.0)) else {
return None;
};
let (mut lo, mut hi) = (0.0f64, 1.0f64);
for _ in 0..60 {
let m = 0.5 * (lo + hi);
let dm = offset(m)?;
if (dm > 0.0) == (da > 0.0) {
lo = m;
} else {
hi = m;
}
if hi - lo <= 1e-14 {
break;
}
}
let t = 0.5 * (lo + hi);
let mid = v3::add(pa, v3::scale(v3::sub(pb, pa), t));
let mid = across
.and_then(|other| {
let on_seam = |v: f64| surface.point(origin, v);
let gap = |v: f64| -> Option<f64> {
let p = on_seam(v);
let (u2, v2) = other.invert(p)?;
let n = other.normal(u2, v2)?;
Some(v3::dot(v3::sub(p, other.point(u2, v2)), n))
};
let (_, va) = surface.invert(pa)?;
let (_, vb) = surface.invert(pb)?;
let (mut lo, mut hi) = (va, vb);
let (ga, gb) = (gap(lo)?, gap(hi)?);
if ga == 0.0 {
return Some(on_seam(lo));
}
if (ga > 0.0) == (gb > 0.0) {
return None; }
for _ in 0..60 {
let m = 0.5 * (lo + hi);
let gm = gap(m)?;
if (gm > 0.0) == (ga > 0.0) {
lo = m;
} else {
hi = m;
}
if (hi - lo).abs() <= 1e-15 {
break;
}
}
Some(on_seam(0.5 * (lo + hi)))
})
.unwrap_or_else(|| {
match surface.invert(mid) {
Some((_, v)) => surface.point(origin, v),
None => mid,
}
});
let cut = surface.invert(mid).map(|(_, v)| (v, vertices.len()));
vertices.push(mid);
curve.vertices.insert(i + 1, vertices.len() - 1);
if curve.closed {
let first = curve.vertices[0];
let end = curve.vertices.len() - 1;
curve.vertices[end] = first;
}
return cut;
}
None
}
fn insert_at_u(points: &mut Vec<V3>, surface: &Surface, u: f64) {
let Some((_, v)) = points.first().and_then(|p| surface.invert(*p)) else {
return;
};
if points
.iter()
.filter_map(|p| surface.invert(*p))
.any(|(_, w)| (w - v).abs() > 1e-9)
{
return;
}
let at = surface.point(u, v);
if points.iter().any(|p| v3::dist(*p, at) <= 1e-9) {
return;
}
let mut best = (f64::MAX, 0usize);
for i in 0..points.len().saturating_sub(1) {
let d = v3::dist(points[i], at) + v3::dist(at, points[i + 1])
- v3::dist(points[i], points[i + 1]);
if d < best.0 {
best = (d, i + 1);
}
}
points.insert(best.1, at);
}
fn seam_chord(uv: &[[f64; 2]], origin: f64, period: f64) -> Option<(Vec<[f64; 2]>, Vec<usize>)> {
let n = uv.len();
if n < 3 {
return None;
}
let fold = |u: f64| origin + (u - origin).rem_euclid(period);
let mut cut = 0usize;
let mut worst = 0.0;
let mut rising = true;
for i in 0..n {
let step = fold(uv[(i + 1) % n][0]) - fold(uv[i][0]);
if step.abs() > worst {
worst = step.abs();
cut = (i + 1) % n;
rising = step < 0.0;
}
}
if worst < period * 0.5 {
return None; }
let step: isize = if rising { 1 } else { -1 };
let mut cut = if rising { cut } else { (cut + n - 1) % n };
let before = ((cut as isize - step).rem_euclid(n as isize)) as usize;
let at_edge = |u: f64| {
let f = fold(u);
(f - origin).min(origin + period - f) <= period * 1e-6
};
if at_edge(uv[before][0]) {
cut = before;
}
let mut out = Vec::with_capacity(n + 1);
let mut idx = Vec::with_capacity(n + 1);
for k in 0..n {
let i = ((cut as isize + step * k as isize).rem_euclid(n as isize)) as usize;
out.push([fold(uv[i][0]), uv[i][1]]);
idx.push(i);
}
out.push([origin + period, out[0][1]]);
idx.push(idx[0]);
Some((out, idx))
}
fn widest_gap(used: &[f64], lo: f64, period: f64) -> f64 {
if used.is_empty() {
return lo;
}
let mut sorted: Vec<f64> = used.iter().map(|u| (u - lo).rem_euclid(period)).collect();
sorted.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
let mut best = (
sorted[0] + period - sorted[sorted.len() - 1],
sorted[sorted.len() - 1],
);
for w in sorted.windows(2) {
if w[1] - w[0] > best.0 {
best = (w[1] - w[0], w[0]);
}
}
lo + best.1 + best.0 * 0.5
}
fn materialise_shared(edges: &mut Vec<Edge>, faces: &mut [Face]) {
let mut covered: HashSet<(usize, usize)> = HashSet::new();
for e in edges.iter() {
for w in e.vertices.windows(2) {
covered.insert((w[0].min(w[1]), w[0].max(w[1])));
}
}
let mut runs: Vec<(usize, Vec<usize>)> = Vec::new();
for (fi, face) in faces.iter().enumerate() {
let Some(loops) = face.loops.as_ref() else {
continue;
};
for ring in loops {
let n = ring.vertices.len();
if n < 2 {
continue;
}
let gap = |i: usize| {
let (a, b) = (ring.vertices[i], ring.vertices[(i + 1) % n]);
a != b && !covered.contains(&(a.min(b), a.max(b)))
};
let Some(start) = (0..n).find(|&i| gap(i) && !gap((i + n - 1) % n)) else {
continue;
};
let mut cur: Vec<usize> = Vec::new();
for step in 0..n {
let i = (start + step) % n;
if gap(i) {
if cur.is_empty() {
cur.push(ring.vertices[i]);
}
cur.push(ring.vertices[(i + 1) % n]);
} else if !cur.is_empty() {
runs.push((fi, std::mem::take(&mut cur)));
}
}
if !cur.is_empty() {
runs.push((fi, cur));
}
}
}
let mut taken = vec![false; runs.len()];
for a in 0..runs.len() {
if taken[a] || runs[a].1.len() < 2 {
continue;
}
for b in (a + 1)..runs.len() {
if taken[b] || runs[b].0 == runs[a].0 {
continue;
}
let same = runs[b].1 == runs[a].1;
let mirrored = runs[b].1.iter().rev().eq(runs[a].1.iter());
if !same && !mirrored {
continue;
}
taken[a] = true;
taken[b] = true;
let (fa, fb) = (runs[a].0, runs[b].0);
let e = edges.len();
edges.push(Edge {
surfaces: (faces[fa].surface, faces[fb].surface),
vertices: runs[a].1.clone(),
closed: false,
});
faces[fa].edges.push(e);
faces[fb].edges.push(e);
break;
}
}
}
fn split_at_seam_ends(edges: &mut Vec<Edge>, faces: &mut [Face]) {
let mut cuts: HashSet<usize> = HashSet::new();
for face in faces.iter() {
for &e in &face.edges {
if face.edges.iter().filter(|&&x| x == e).count() != 2 {
continue;
}
if let Some(edge) = edges.get(e) {
if let (Some(&a), Some(&b)) = (edge.vertices.first(), edge.vertices.last()) {
cuts.insert(a);
cuts.insert(b);
}
}
}
}
if cuts.is_empty() {
return;
}
let mut replace: HashMap<usize, Vec<usize>> = HashMap::new();
for ei in 0..edges.len() {
let v = edges[ei].vertices.clone();
if v.len() < 3 || edges[ei].closed {
continue;
}
let inner: Vec<usize> = (1..v.len() - 1).filter(|&i| cuts.contains(&v[i])).collect();
if inner.is_empty() {
continue;
}
let surfaces = edges[ei].surfaces;
let mut parts: Vec<Vec<usize>> = Vec::new();
let mut start = 0usize;
for &i in &inner {
parts.push(v[start..=i].to_vec());
start = i;
}
parts.push(v[start..].to_vec());
let mut ids = Vec::with_capacity(parts.len());
for (k, part) in parts.into_iter().enumerate() {
if k == 0 {
edges[ei].vertices = part;
ids.push(ei);
} else {
ids.push(edges.len());
edges.push(Edge {
surfaces,
vertices: part,
closed: false,
});
}
}
replace.insert(ei, ids);
}
if replace.is_empty() {
return;
}
for face in faces.iter_mut() {
let mut out = Vec::with_capacity(face.edges.len());
for &e in &face.edges {
match replace.get(&e) {
Some(ids) => out.extend(ids.iter().copied()),
None => out.push(e),
}
}
face.edges = out;
}
}
fn prune_orphan_vertices(vertices: &mut Vec<V3>, edges: &mut [Edge], faces: &mut [Face]) {
let mut used = vec![false; vertices.len()];
for e in edges.iter() {
for v in &e.vertices {
if let Some(slot) = used.get_mut(*v) {
*slot = true;
}
}
}
for f in faces.iter() {
let Some(ls) = f.loops.as_ref() else {
continue;
};
for l in ls {
for v in &l.vertices {
if let Some(slot) = used.get_mut(*v) {
*slot = true;
}
}
}
}
if used.iter().all(|u| *u) {
return;
}
let mut slot = vec![usize::MAX; vertices.len()];
let mut kept: Vec<V3> = Vec::with_capacity(vertices.len());
for (i, keep) in used.iter().enumerate() {
if *keep {
slot[i] = kept.len();
kept.push(vertices[i]);
}
}
*vertices = kept;
for e in edges.iter_mut() {
for v in e.vertices.iter_mut() {
*v = slot.get(*v).copied().unwrap_or(usize::MAX);
}
}
for f in faces.iter_mut() {
let Some(ls) = f.loops.as_mut() else {
continue;
};
for l in ls {
for v in l.vertices.iter_mut() {
*v = slot.get(*v).copied().unwrap_or(usize::MAX);
}
}
}
}
fn materialise_seam_steps(edges: &mut Vec<Edge>, faces: &mut [Face]) {
let mut backed: HashSet<(usize, usize)> = HashSet::new();
for e in edges.iter() {
for w in e.vertices.windows(2) {
backed.insert((w[0], w[1]));
backed.insert((w[1], w[0]));
}
}
for face in faces.iter_mut() {
let Some(loops) = face.loops.as_ref() else {
continue;
};
let poled = loops.iter().any(|r| {
let n = r.vertices.len();
n >= 3 && (0..n).any(|i| r.vertices[i] == r.vertices[(i + 1) % n])
});
if poled {
continue;
}
let mut want: HashMap<(usize, usize), usize> = HashMap::new();
for ring in loops {
let n = ring.vertices.len();
if n < 3 {
continue;
}
for i in 0..n {
let (a, b) = (ring.vertices[i], ring.vertices[(i + 1) % n]);
if a == b || backed.contains(&(a, b)) {
continue;
}
*want.entry((a.min(b), a.max(b))).or_insert(0) += 1;
}
}
for ((a, b), walks) in want {
if walks != 2 {
continue;
}
let id = edges.len();
edges.push(Edge {
surfaces: (face.surface, face.surface),
vertices: vec![a, b],
closed: false,
});
face.edges.push(id);
face.edges.push(id);
backed.insert((a, b));
backed.insert((b, a));
}
}
}
fn materialise_seams(edges: &mut Vec<Edge>, faces: &mut [Face]) {
for face in faces.iter_mut() {
let Some(loops) = face.loops.as_ref() else {
continue;
};
let named: HashSet<usize> = face
.edges
.iter()
.filter_map(|&e| edges.get(e))
.flat_map(|e| e.vertices.iter().copied())
.collect();
let mut found: Vec<Vec<usize>> = Vec::new();
for ring in loops {
let n = ring.vertices.len();
if n < 3 {
continue;
}
let off: Vec<bool> = ring.vertices.iter().map(|v| !named.contains(v)).collect();
let Some(start) = (0..n).find(|&i| off[i] && !off[(i + n - 1) % n]) else {
continue;
};
let mut runs: Vec<Vec<usize>> = Vec::new();
let mut cur: Vec<usize> = Vec::new();
let mut i = start;
for _ in 0..n {
if off[i] {
if cur.is_empty() {
cur.push(ring.vertices[(i + n - 1) % n]);
}
cur.push(ring.vertices[i]);
} else if !cur.is_empty() {
cur.push(ring.vertices[i]);
runs.push(std::mem::take(&mut cur));
}
i = (i + 1) % n;
}
if !cur.is_empty() {
cur.push(ring.vertices[i]);
runs.push(cur);
}
let mut used = vec![false; runs.len()];
for a in 0..runs.len() {
if used[a] || runs[a].len() < 2 {
continue;
}
for b in (a + 1)..runs.len() {
if used[b] {
continue;
}
if runs[b].iter().rev().eq(runs[a].iter()) {
used[a] = true;
used[b] = true;
found.push(runs[a].clone());
break;
}
}
}
}
for run in found {
let e = edges.len();
edges.push(Edge {
surfaces: (face.surface, face.surface),
vertices: run,
closed: false,
});
face.edges.push(e);
face.edges.push(e);
}
}
}
fn parameter_outline(
face: &Face,
surface: &Surface,
tolerance: f64,
carried: &[Carried],
seam_cuts: &[(f64, usize)],
) -> TrimLoop {
let (u0, u1) = face.u_range;
let (v0, v1) = face.v_range;
let period = u1 - u0;
let rim_at = |v: f64, forward: bool| -> Option<(Vec<[f64; 2]>, Vec<usize>)> {
for (_, _, pts, _, names) in carried {
let mut uv: Vec<[f64; 2]> = Vec::with_capacity(pts.len());
let mut ids: Vec<usize> = Vec::with_capacity(pts.len());
let mut ok = true;
for (k, p) in pts.iter().enumerate() {
match surface.invert(*p) {
Some((u, w)) if (w - v).abs() <= (v1 - v0).abs() * 1e-6 => {
uv.push([u0 + (u - u0).rem_euclid(period), w]);
ids.push(names.get(k).copied().unwrap_or(usize::MAX));
}
_ => {
ok = false;
break;
}
}
}
if !ok || uv.len() < 3 {
continue;
}
if uv.len() > 1 && dist2(uv[0], uv[uv.len() - 1]) <= (period * 1e-9).powi(2) {
uv.pop(); ids.pop();
}
let n = uv.len();
if n < 3 {
continue;
}
let (mut cut, mut worst, mut rising) = (0usize, 0.0, true);
for i in 0..n {
let step = uv[(i + 1) % n][0] - uv[i][0];
if step.abs() > worst {
worst = step.abs();
cut = (i + 1) % n;
rising = step < 0.0;
}
}
let dir: isize = if rising { 1 } else { -1 };
let cut = if rising { cut } else { (cut + n - 1) % n };
let mut rotated = Vec::with_capacity(n);
let mut rotated_ids = Vec::with_capacity(n);
for k in 0..n {
let i = ((cut as isize + dir * k as isize).rem_euclid(n as isize)) as usize;
rotated.push(uv[i]);
rotated_ids.push(ids[i]);
}
uv = rotated;
ids = rotated_ids;
if (uv[0][0] - u0).abs() <= period * 1e-9 {
uv.push([u1, uv[0][1]]);
ids.push(ids[0]);
}
if !forward {
uv.reverse();
ids.reverse();
}
return Some((uv, ids));
}
None
};
let along = |a: [f64; 2], b: [f64; 2]| -> Vec<[f64; 2]> {
let n = super::body::adaptive_steps(
tolerance,
|s, t| {
let at = |x: f64| surface.point(a[0] + (b[0] - a[0]) * x, a[1] + (b[1] - a[1]) * x);
let m = 0.5 * (s + t);
v3::dist(at(m), v3::scale(v3::add(at(s), at(t)), 0.5))
},
0.0,
1.0,
);
(0..n)
.map(|i| {
let x = i as f64 / n as f64;
[a[0] + (b[0] - a[0]) * x, a[1] + (b[1] - a[1]) * x]
})
.collect()
};
let seam_run = |a: [f64; 2], b: [f64; 2]| -> Vec<([f64; 2], usize)> {
let mut stops: Vec<(f64, usize)> = seam_cuts
.iter()
.copied()
.filter(|(v, _)| (v - a[1]) * (v - b[1]) < 0.0)
.collect();
stops.sort_by(|x, y| {
(x.0 - a[1])
.abs()
.partial_cmp(&(y.0 - a[1]).abs())
.unwrap_or(std::cmp::Ordering::Equal)
});
let mut out: Vec<([f64; 2], usize)> = Vec::new();
let mut from = a;
for (v, name) in stops {
let to = [a[0], v];
out.extend(along(from, to).into_iter().map(|c| (c, usize::MAX)));
if let Some(last) = out.last_mut() {
if (last.0[1] - v).abs() <= f64::EPSILON {
last.1 = name;
}
}
from = to;
}
out.extend(along(from, b).into_iter().map(|c| (c, usize::MAX)));
out.push((b, usize::MAX));
out
};
let mut pts: Vec<([f64; 2], usize)> = Vec::new();
let unnamed = |v: Vec<[f64; 2]>| -> Vec<([f64; 2], usize)> {
v.into_iter().map(|c| (c, usize::MAX)).collect()
};
match rim_at(v0, true) {
Some((r, ids)) => pts.extend(r.into_iter().zip(ids)),
None => pts.extend(unnamed(along([u0, v0], [u1, v0]))),
}
let degenerate = |v: f64| -> bool {
let at = surface.point(u0, v);
v3::dist(surface.point(u0 + period * 0.5, v), at) <= tolerance * 0.25
&& v3::dist(surface.point(u0 + period * 0.25, v), at) <= tolerance * 0.25
};
let seam = seam_run([u1, v0], [u1, v1]);
{
let forward = seam.clone();
let _ = degenerate(v1);
pts.extend(forward);
}
match rim_at(v1, false) {
Some((r, ids)) => pts.extend(r.into_iter().zip(ids)),
None => pts.extend(unnamed(along([u1, v1], [u0, v1]))),
}
{
let back: Vec<([f64; 2], usize)> =
seam.iter().rev().map(|(c, n)| ([u0, c[1]], *n)).collect();
let _ = degenerate(v0);
pts.extend(back);
}
let same = |a: [f64; 2], b: [f64; 2]| {
if (a[0] - b[0]).abs() > period * 0.5 {
return false;
}
v3::dist(surface.point(a[0], a[1]), surface.point(b[0], b[1])) <= tolerance * 0.25
};
let mut out: Vec<([f64; 2], usize)> = Vec::with_capacity(pts.len());
for (c, id) in pts {
match out.last_mut() {
Some((prev, kept)) if same(*prev, c) => {
if *kept == usize::MAX {
*kept = id;
}
}
_ => out.push((c, id)),
}
}
if out.len() > 2 && same(out[0].0, out[out.len() - 1].0) {
let (_, id) = out.pop().expect("checked non-empty");
if out[0].1 == usize::MAX {
out[0].1 = id;
}
}
let uv: Vec<[f64; 2]> = out.iter().map(|(c, _)| *c).collect();
let vertices: Vec<usize> = out.iter().map(|(_, v)| *v).collect();
let area = ring_area(&uv);
TrimLoop { vertices, uv, area }
}
fn sample_open_curve(curve: &Curve3d, t0: f64, t1: f64, tolerance: f64) -> Vec<V3> {
if let Curve3d::Sampled { points, .. } = curve {
let mut out = vec![curve.point(t0)];
for (i, p) in points.iter().enumerate() {
if (i as f64) > t0 + 1e-9 && (i as f64) < t1 - 1e-9 {
out.push(*p);
}
}
out.push(curve.point(t1));
return out;
}
let radius = match curve {
Curve3d::Circle { radius, .. } => *radius,
Curve3d::Ellipse { a, .. } => *a,
_ => return vec![curve.point(t0), curve.point(t1)],
};
let per = 2.0
* (1.0 - (tolerance / radius.max(1e-12)).min(1.0))
.acos()
.max(1e-6);
let n = (((t1 - t0).abs() / per).ceil() as usize).clamp(2, 512);
(0..=n)
.map(|i| curve.point(t0 + (t1 - t0) * i as f64 / n as f64))
.collect()
}
fn sample_closed_curve(
curve: &Curve3d,
surface: &Surface,
tolerance: f64,
) -> Option<Vec<[f64; 2]>> {
use std::f64::consts::TAU;
if let Curve3d::Sampled { points, closed } = curve {
if !*closed || points.len() < 3 {
return None;
}
let (periodic_u, periodic_v) = surface.periodic();
let mut uv = Vec::with_capacity(points.len());
let mut anchor: Option<[f64; 2]> = None;
for p in points {
let (mut u, mut v) = surface.invert(*p)?;
if let Some(a) = anchor {
if periodic_u {
u = unwrap_near(u, a[0]);
}
if periodic_v {
v = unwrap_near(v, a[1]);
}
}
anchor = Some([u, v]);
uv.push([u, v]);
}
return Some(uv);
}
let radius = match curve {
Curve3d::Circle { radius, .. } => *radius,
Curve3d::Ellipse { a, .. } => *a,
_ => return None,
};
if !radius.is_finite() || radius <= 0.0 {
return None;
}
let n = (((TAU) / (2.0 * (1.0 - (tolerance / radius).min(1.0)).acos().max(1e-6))).ceil()
as usize)
.clamp(12, 512);
let mut uv = Vec::with_capacity(n);
let mut anchor: Option<[f64; 2]> = None;
let (periodic_u, periodic_v) = surface.periodic();
for i in 0..n {
let p = curve.point(TAU * i as f64 / n as f64);
let (mut u, mut v) = surface.invert(p)?;
if let Some(a) = anchor {
if periodic_u {
u = unwrap_near(u, a[0]);
}
if periodic_v {
v = unwrap_near(v, a[1]);
}
}
anchor = Some([u, v]);
uv.push([u, v]);
}
Some(uv)
}
fn settle_shared_vertices(
surfaces: &[Surface],
vertices: &mut [V3],
faces: &mut [Face],
tolerance: f64,
) {
let mut claims: HashMap<usize, Vec<usize>> = HashMap::new();
for f in faces.iter() {
let Some(ls) = f.loops.as_ref() else {
continue;
};
for l in ls {
for &v in &l.vertices {
let e = claims.entry(v).or_default();
if !e.contains(&f.surface) {
e.push(f.surface);
}
}
}
}
let mut moved: HashMap<usize, V3> = HashMap::new();
for (v, ss) in &claims {
if ss.len() != 2 {
continue;
}
let p = vertices[*v];
let (a, b) = (&surfaces[ss[0]], &surfaces[ss[1]]);
let was = a.distance(p).abs().max(b.distance(p).abs());
if was <= 1e-9 {
continue;
}
let Some(q) = crate::brep::intersect::settle(a, b, p, tolerance) else {
continue;
};
if v3::dist(p, q) > tolerance * 4.0 {
continue;
}
if a.distance(q).abs().max(b.distance(q).abs()) >= was {
continue;
}
moved.insert(*v, q);
}
if moved.is_empty() {
return;
}
for (v, q) in &moved {
vertices[*v] = *q;
}
for f in faces.iter_mut() {
let s = &surfaces[f.surface];
let (pu, pv) = s.periodic();
let Some(ls) = f.loops.as_mut() else {
continue;
};
for l in ls {
for k in 0..l.vertices.len() {
let Some(q) = moved.get(&l.vertices[k]) else {
continue;
};
let Some((u, w)) = s.invert(*q) else {
continue;
};
let old = l.uv[k];
l.uv[k] = [
if pu { unwrap_near(u, old[0]) } else { u },
if pv { unwrap_near(w, old[1]) } else { w },
];
}
}
}
}
fn extent_of(b: &Body, lo: &mut V3, hi: &mut V3) {
let mut add = |p: V3| {
for k in 0..3 {
lo[k] = lo[k].min(p[k]);
hi[k] = hi[k].max(p[k]);
}
};
if !b.vertices().is_empty() {
for p in b.vertices() {
add(*p);
}
return;
}
const N: usize = 8;
for f in b.faces() {
let s = &b.surfaces()[f.surface];
for i in 0..=N {
let u = f.u_range.0 + (f.u_range.1 - f.u_range.0) * i as f64 / N as f64;
for j in 0..=N {
let v = f.v_range.0 + (f.v_range.1 - f.v_range.0) * j as f64 / N as f64;
add(s.point(u, v));
}
}
}
}
fn unwrap_near(x: f64, anchor: f64) -> f64 {
use std::f64::consts::TAU;
x - TAU * ((x - anchor) / TAU).round()
}
fn oriented(mut l: TrimLoop, want_outer: bool) -> TrimLoop {
let is_outer = l.area > 0.0;
if is_outer != want_outer {
l.area = -l.area;
l.uv.reverse();
l.vertices.reverse();
}
l
}
fn interior_point(ring: &[[f64; 2]]) -> Option<[f64; 2]> {
let margin = ring_margin(ring);
for i in 1..ring.len().saturating_sub(1) {
let c = [
(ring[0][0] + ring[i][0] + ring[i + 1][0]) / 3.0,
(ring[0][1] + ring[i][1] + ring[i + 1][1]) / 3.0,
];
if deep_in_ring(ring, c, margin) {
return Some(c);
}
}
None
}
fn segments_properly_cross(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2]) -> bool {
let side = |p: [f64; 2], q: [f64; 2], r: [f64; 2]| {
(q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])
};
let (d1, d2) = (side(c, d, a), side(c, d, b));
let (d3, d4) = (side(a, b, c), side(a, b, d));
((d1 > 0.0) != (d2 > 0.0)) && ((d3 > 0.0) != (d4 > 0.0))
}
fn dist2(a: [f64; 2], b: [f64; 2]) -> f64 {
(a[0] - b[0]).powi(2) + (a[1] - b[1]).powi(2)
}
fn same_ring(a: &[[f64; 2]], b: &[[f64; 2]]) -> bool {
let near = ring_margin(a);
let on = |ring: &[[f64; 2]], p: [f64; 2]| {
let n = ring.len();
(0..n).any(|i| {
let (x, y) = (ring[i], ring[(i + 1) % n]);
let (dx, dy) = (y[0] - x[0], y[1] - x[1]);
let len2 = dx * dx + dy * dy;
let t = if len2 <= f64::MIN_POSITIVE {
0.0
} else {
(((p[0] - x[0]) * dx + (p[1] - x[1]) * dy) / len2).clamp(0.0, 1.0)
};
(p[0] - (x[0] + dx * t)).hypot(p[1] - (x[1] + dy * t)) <= near
})
};
b.iter().all(|p| on(a, *p)) && a.iter().all(|p| on(b, *p))
}
fn deep_in_ring(ring: &[[f64; 2]], p: [f64; 2], margin: f64) -> bool {
if !point_in_ring(ring, p) {
return false;
}
let n = ring.len();
(0..n).all(|i| {
let (a, b) = (ring[i], ring[(i + 1) % n]);
let (dx, dy) = (b[0] - a[0], b[1] - a[1]);
let len2 = dx * dx + dy * dy;
let t = if len2 <= f64::MIN_POSITIVE {
0.0
} else {
(((p[0] - a[0]) * dx + (p[1] - a[1]) * dy) / len2).clamp(0.0, 1.0)
};
(p[0] - (a[0] + dx * t)).hypot(p[1] - (a[1] + dy * t)) > margin
})
}
fn ring_margin(ring: &[[f64; 2]]) -> f64 {
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for p in ring {
for k in 0..2 {
lo[k] = lo[k].min(p[k]);
hi[k] = hi[k].max(p[k]);
}
}
(hi[0] - lo[0]).max(hi[1] - lo[1]).max(1e-12) * 1e-9
}
fn ring_area(uv: &[[f64; 2]]) -> f64 {
let n = uv.len();
let mut a = 0.0;
for i in 0..n {
let (p, q) = (uv[i], uv[(i + 1) % n]);
a += p[0] * q[1] - q[0] * p[1];
}
a * 0.5
}
fn point_in_ring(ring: &[[f64; 2]], p: [f64; 2]) -> bool {
let n = ring.len();
let mut inside = false;
let mut j = n - 1;
for i in 0..n {
let (a, b) = (ring[i], ring[j]);
if (a[1] > p[1]) != (b[1] > p[1]) {
let t = (p[1] - a[1]) / (b[1] - a[1]);
if p[0] < a[0] + t * (b[0] - a[0]) {
inside = !inside;
}
}
j = i;
}
inside
}
fn point_in_mesh(tris: &[[V3; 3]], p: V3) -> bool {
let dir = [0.577_215_66, 0.413_255_11, 0.700_113_47];
let mut hits = 0usize;
for t in tris {
if let Some(d) = ray_triangle(p, dir, t) {
if d > 1e-9 {
hits += 1;
}
}
}
hits % 2 == 1
}
fn ray_triangle(origin: V3, dir: V3, t: &[V3; 3]) -> Option<f64> {
let e1 = v3::sub(t[1], t[0]);
let e2 = v3::sub(t[2], t[0]);
let h = v3::cross(dir, e2);
let a = v3::dot(e1, h);
if a.abs() < 1e-14 {
return None;
}
let f = 1.0 / a;
let s = v3::sub(origin, t[0]);
let u = f * v3::dot(s, h);
if !(0.0..=1.0).contains(&u) {
return None;
}
let q = v3::cross(s, e1);
let v = f * v3::dot(dir, q);
if v < 0.0 || u + v > 1.0 {
return None;
}
Some(f * v3::dot(e2, q))
}
#[cfg(test)]
mod tests {
use super::*;
fn volume(body: &Body, tolerance: f64) -> f64 {
let mut b = body.clone();
b.refine_edges(tolerance);
let (mesh, report) = b.tessellate(tolerance);
assert!(report.is_closed(), "{} open edges", report.boundary_edges);
let pos = &mesh.get_attribute("position").unwrap().array;
let idx = mesh.index.as_ref().unwrap();
let v = |i: u32| -> V3 {
let o = i as usize * 3;
[pos[o] as f64, pos[o + 1] as f64, pos[o + 2] as f64]
};
idx.chunks_exact(3)
.map(|t| {
let (a, b, c) = (v(t[0]), v(t[1]), v(t[2]));
v3::dot(a, v3::cross(b, c)) / 6.0
})
.sum::<f64>()
.abs()
}
fn plate_and_drill() -> (Body, Body) {
(
Body::cuboid([10.0, 8.0, 2.0]),
Body::cylinder([0.0, 0.0, -3.0], [0.0, 0.0, 1.0], 2.0, 6.0),
)
}
#[test]
fn a_difference_produces_the_solid_it_should() {
let (plate, drill) = plate_and_drill();
let result = plate
.boolean(&drill, BooleanOp::Difference, 1e-3)
.expect("every pair has a closed form");
assert_eq!(result.faces().len(), 7, "six walls and a bore");
let holed = result
.faces()
.iter()
.filter(|f| result.surfaces()[f.surface].kind() == "plane")
.filter(|f| f.edges.iter().any(|&e| result.edges()[e].closed))
.count();
assert_eq!(holed, 2, "the two faces the bore passes through");
let expected = 160.0 - std::f64::consts::PI * 4.0 * 2.0;
let got = volume(&result, 1e-3);
assert!(
(got - expected).abs() / expected < 0.01,
"volume {got}, expected {expected}"
);
}
#[test]
fn a_difference_is_watertight() {
let (plate, drill) = plate_and_drill();
let mut result = plate.boolean(&drill, BooleanOp::Difference, 1e-3).unwrap();
assert_eq!(result.edges().len(), 14);
for i in 0..result.edges().len() {
let users = result
.faces()
.iter()
.filter(|f| f.edges.contains(&i))
.count();
assert_eq!(users, 2, "edge {i} used by {users} faces");
}
result.refine_edges(1e-3);
let (_, report) = result.tessellate(1e-3);
assert_eq!(report.carried_through, 0);
assert!(report.is_closed(), "{} open edges", report.boundary_edges);
}
#[test]
fn union_and_intersection_give_the_volumes_they_should() {
let (plate, drill) = plate_and_drill();
let bore = std::f64::consts::PI * 4.0 * 2.0; let rod = std::f64::consts::PI * 4.0 * 6.0;
let inter = plate
.boolean(&drill, BooleanOp::Intersection, 1e-3)
.expect("closed form");
let got = volume(&inter, 1e-3);
assert!(
(got - bore).abs() / bore < 0.01,
"intersection {got}, expected {bore}"
);
let union = plate
.boolean(&drill, BooleanOp::Union, 1e-3)
.expect("closed form");
let expected = 160.0 + rod - bore;
let got = volume(&union, 1e-3);
assert!(
(got - expected).abs() / expected < 0.01,
"union {got}, expected {expected}"
);
}
#[test]
fn the_three_operations_are_consistent_with_each_other() {
let (plate, drill) = plate_and_drill();
let a = volume(&plate, 1e-3);
let b = volume(&drill, 1e-3);
let u = volume(
&plate.boolean(&drill, BooleanOp::Union, 1e-3).unwrap(),
1e-3,
);
let i = volume(
&plate
.boolean(&drill, BooleanOp::Intersection, 1e-3)
.unwrap(),
1e-3,
);
let d = volume(
&plate.boolean(&drill, BooleanOp::Difference, 1e-3).unwrap(),
1e-3,
);
assert!(
((a + b) - (u + i)).abs() / (a + b) < 0.01,
"|A|+|B| = {} but |A∪B|+|A∩B| = {}",
a + b,
u + i
);
assert!(
(d - (a - i)).abs() / a < 0.01,
"|A−B| = {d} but |A|−|A∩B| = {}",
a - i
);
}
#[test]
fn a_sphere_drilled_by_a_coaxial_cylinder() {
let ball = Body::sphere([0.0; 3], 3.0);
let drill = Body::cylinder([0.0, 0.0, -5.0], [0.0, 0.0, 1.0], 1.0, 10.0);
let result = ball
.boolean(&drill, BooleanOp::Difference, 1e-3)
.expect("a coaxial sphere and cylinder have a closed form");
let mut r = result.clone();
r.refine_edges(1e-3);
let (_, report) = r.tessellate(1e-3);
assert_eq!(report.carried_through, 0);
let h = (9.0f64 - 1.0).sqrt();
let expected = 4.0 / 3.0 * std::f64::consts::PI * h.powi(3);
let got = volume(&result, 1e-3);
assert!(
(got - expected).abs() / expected < 0.02,
"volume {got}, expected {expected}"
);
}
#[test]
fn a_body_that_is_not_a_solid_has_no_boolean() {
let tube = Body::cylinder([0.0; 3], [0.0, 0.0, 1.0], 1.0, 2.0);
let mut open = tube.clone();
open.faces_mut().truncate(1); let cube = Body::cuboid([4.0, 4.0, 4.0]);
assert!(matches!(
open.boolean(&cube, BooleanOp::Union, 1e-3),
Err(Declined::NotASolid)
));
}
#[test]
fn a_pair_without_a_closed_form_is_traced_not_fitted() {
let torus = Surface::torus([0.0; 3], [0.0, 0.0, 1.0], 4.0, 1.0);
let cyl = Surface::cylinder([4.0, 0.0, 0.0], [0.0, 0.0, 1.0], 0.5);
let curves = super::super::intersect::march(&torus, &cyl, ([-6.0; 3], [6.0; 3]), 1e-3);
assert!(!curves.is_empty(), "the cylinder passes through the tube");
for c in &curves {
let Curve3d::Sampled { points, closed } = c else {
panic!("a quartic has no closed form to return");
};
assert!(closed, "the tube is entered and left");
for p in points {
assert!(
torus.distance(*p) <= 1e-6,
"{} off the torus",
torus.distance(*p)
);
assert!(
cyl.distance(*p) <= 1e-6,
"{} off the cylinder",
cyl.distance(*p)
);
}
}
}
#[test]
fn a_solid_with_itself() {
let a = Body::cuboid([2.0, 2.0, 2.0]);
let b = Body::cuboid([2.0, 2.0, 2.0]);
assert_eq!(
a.boolean(&b, BooleanOp::Union, 1e-3).unwrap().faces().len(),
6
);
assert_eq!(
a.boolean(&b, BooleanOp::Intersection, 1e-3)
.unwrap()
.faces()
.len(),
6
);
assert!(a
.boolean(&b, BooleanOp::Difference, 1e-3)
.unwrap()
.faces()
.is_empty());
}
#[test]
fn ray_parity_agrees_with_the_shape_it_is_asked_about() {
let mut body = Body::sphere([0.0; 3], 2.0);
body.refine_edges(1e-2);
let tris = body.solid_triangles(1e-2);
assert!(!tris.is_empty());
assert!(
point_in_mesh(&tris, [0.0, 0.0, 0.0]),
"the centre is inside"
);
assert!(point_in_mesh(&tris, [1.0, 0.5, -0.5]));
assert!(!point_in_mesh(&tris, [5.0, 0.0, 0.0]), "well outside");
assert!(!point_in_mesh(&tris, [0.0, 0.0, 3.0]));
}
#[test]
fn containment_in_a_ring() {
let square = [[-1.0, -1.0], [1.0, -1.0], [1.0, 1.0], [-1.0, 1.0]];
assert!(point_in_ring(&square, [0.0, 0.0]));
assert!(!point_in_ring(&square, [2.0, 0.0]));
assert!(!point_in_ring(&square, [0.0, -3.0]));
}
}