use std::collections::{HashMap, HashSet};
use std::fmt;
use crate::{
boolean::{
classify,
csi::{curve_surface, signed_distance},
domain::Domain,
face_domain,
},
geom::{Curve, Surface, distance_to},
math::{Aabb, Point3, Vec2, Vec3},
measure, tol,
topo::{Brep, CoedgeId, EdgeId, FaceId, FaceMemo, ShellId, SolidId, VertexId},
};
#[derive(Clone, Debug, PartialEq)]
pub struct Issue {
pub message: String,
}
impl fmt::Display for Issue {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.write_str(&self.message)
}
}
const SAMPLES: usize = 16;
const SLIVER_AREA: f64 = 1e-3;
pub(crate) fn coedge_params(b: &Brep, c: CoedgeId, n: usize) -> Vec<f64> {
let co = b.coedge(c);
let (t0, t1) = b.edge(co.edge).range;
let (a, z) = if co.reversed { (t1, t0) } else { (t0, t1) };
(0..=n).map(|i| a + (z - a) * i as f64 / n as f64).collect()
}
pub(crate) fn fold(c: &Curve, range: (f64, f64)) -> Option<crate::math::Point3> {
let Curve::Intersection(ic) = c else {
return None;
};
let sp = &ic.approx;
let (t0, t1) = range;
let mut cuts: Vec<f64> = vec![t0];
cuts.extend(sp.breakpoints(t0, t1));
cuts.push(t1);
cuts.dedup();
let mut prev: Option<crate::math::Vec3> = None;
for w in cuts.windows(2) {
for j in 0..4 {
let t = w[0] + (w[1] - w[0]) * j as f64 / 4.0;
let [p, d] = {
let [p, d, _] = sp.eval_ders(t, 1);
[p, d]
};
if d.norm() <= 1e-12 {
continue;
}
if prev.is_some_and(|q| q.dot(d) < 0.0) {
return Some(p);
}
prev = Some(d);
}
}
None
}
fn uv_gap(b: &Brep, face: FaceId, p: Vec2, q: Vec2) -> f64 {
let (_, su, sv) = b.face(face).surface.d1(p.x, p.y);
let (a, c) = (su.norm(), sv.norm());
let wu = if a <= 1e-9 * c { c } else { a };
let wv = if c <= 1e-9 * a { a } else { c };
(p.x - q.x).abs() * wu + (p.y - q.y).abs() * wv
}
pub fn check(b: &Brep) -> Vec<Issue> {
check_with(b, false, None, true)
}
pub(crate) fn check_structure(b: &Brep) -> Vec<Issue> {
check_with(b, false, None, false)
}
pub fn self_crossings(b: &Brep) -> Vec<SelfCrossing> {
crossings(b, None, true)
.into_iter()
.map(|x| SelfCrossing {
a: x.a,
b: x.b,
at: x.at,
depth: depth(b, x.a, x.b).max(depth(b, x.b, x.a)),
})
.collect()
}
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct SelfCrossing {
pub a: FaceId,
pub b: FaceId,
pub at: Point3,
pub depth: f64,
}
fn depth(b: &Brep, fa: FaceId, fb: FaceId) -> f64 {
let s = &b.face(fb).surface;
let (mut above, mut below) = (0.0f64, 0.0f64);
for &lp in &b.face(fa).loops {
for &c in &b.lp(lp).coedges {
let e = b.edge(b.coedge(c).edge);
let pts: Vec<Point3> = match &e.curve {
Some(cv) => (0..=8)
.map(|k| cv.eval(e.range.0 + (e.range.1 - e.range.0) * k as f64 / 8.0))
.collect(),
None => vec![b.vertex(e.start).point],
};
for p in pts {
let d = signed_distance(s, p);
above = above.max(d);
below = below.max(-d);
}
}
}
above.min(below)
}
pub fn check_each(b: &Brep) -> Vec<Issue> {
check_with(b, true, None, true)
}
pub(crate) fn check_cut(b: &Brep, sides: &[Option<usize>]) -> Vec<Issue> {
check_with(b, false, Some(sides), true)
}
fn vertex_shells(b: &Brep) -> HashMap<VertexId, ShellId> {
let mut out = HashMap::new();
for f in b.face_ids() {
let Some(sh) = b.face(f).shell else { continue };
for &lp in &b.face(f).loops {
for &c in &b.lp(lp).coedges {
let e = b.edge(b.coedge(c).edge);
out.insert(e.start, sh);
out.insert(e.end, sh);
}
}
}
out
}
fn check_with(b: &Brep, each: bool, sides: Option<&[Option<usize>]>, crossing: bool) -> Vec<Issue> {
let mut out = Vec::new();
let found = std::cell::Cell::new(0usize);
let mut issue = |m: String| {
found.set(found.get() + 1);
out.push(Issue { message: m });
};
for e in b.edge_ids() {
let edge = b.edge(e);
if edge.range.0.partial_cmp(&edge.range.1) != Some(std::cmp::Ordering::Less) {
issue(format!("edge {} has an empty range", e.index()));
continue;
}
if let Some(c) = &edge.curve {
if let Some(p) = fold(c, edge.range) {
issue(format!(
"edge {} turns back on itself near ({:.6}, {:.6}, {:.6})",
e.index(),
p.x,
p.y,
p.z
));
}
for (t, v) in [(edge.range.0, edge.start), (edge.range.1, edge.end)] {
let d = c.eval(t).dist(b.vertex(v).point);
if d > b.vertex_tolerance(v) {
issue(format!(
"edge {} ends {d:e} mm from vertex {}",
e.index(),
v.index()
));
}
}
}
}
for v in b.vertex_ids() {
let p = b.vertex(v).point;
if !(p.x.is_finite() && p.y.is_finite() && p.z.is_finite()) {
issue(format!("vertex {} is not a finite point", v.index()));
}
}
let solid_of = Some(vertex_shells(b));
let apart = |v: VertexId, w: VertexId| {
solid_of
.as_ref()
.is_some_and(|m| m.get(&v).is_some() && m.get(&v) != m.get(&w))
};
for (v, w) in coincident_vertices(b) {
if apart(v, w) {
continue;
}
issue(format!(
"vertices {} and {} are within the tolerance, so the same point",
v.index(),
w.index()
));
}
for e in b.edge_ids() {
let edge = b.edge(e);
let Some(c) = &edge.curve else { continue };
let ts: Vec<f64> = (0..=SAMPLES)
.map(|i| edge.range.0 + (edge.range.1 - edge.range.0) * i as f64 / SAMPLES as f64)
.collect();
let len: f64 = ts.windows(2).map(|w| c.eval(w[0]).dist(c.eval(w[1]))).sum();
if len.is_nan() || len <= tol::LINEAR {
issue(format!(
"edge {} is {len:e} mm long, within the tolerance",
e.index()
));
}
}
for e in b.edge_ids() {
let u = b.edge_uses(e);
if b.edge(e).is_degenerate() {
if u.len() != 1 {
issue(format!(
"degenerate edge {} is used {} times",
e.index(),
u.len()
));
}
continue;
}
if u.len() < 2 || !u.len().is_multiple_of(2) {
issue(format!(
"edge {} is used by {} coedges, not 2 or pairs of them",
e.index(),
u.len()
));
continue;
}
for &c in u {
let Some(p) = b.partner(c).filter(|&p| b.partner(p) == Some(c)) else {
issue(format!(
"edge {} is used by {} coedges without pairing them",
e.index(),
u.len()
));
break;
};
if c > p {
continue;
}
if b.coedge(c).reversed == b.coedge(p).reversed {
issue(format!(
"edge {} is used twice in the same direction",
e.index()
));
}
if b.face(b.coedge_face(c)).shell != b.face(b.coedge_face(p)).shell {
issue(format!(
"edge {} joins faces of different shells",
e.index()
));
}
}
}
for f in b.face_ids() {
let face = b.face(f);
if face.loops.is_empty() {
issue(format!("face {} has no loops", f.index()));
}
match face.shell {
None => issue(format!("face {} is in no shell", f.index())),
Some(s) if b.shell(s).solid.is_none() => {
issue(format!("shell {} is in no solid", s.index()))
}
_ => {}
}
let memo = b.memo(f);
let has_pole = face.loops.iter().any(|&lp| {
b.lp(lp)
.coedges
.iter()
.any(|&c| b.edge(b.coedge(c).edge).is_degenerate())
});
let sampled = has_pole || memo.clean.get().is_none();
let before = found.get();
for (li, &lp) in face.loops.iter().enumerate() {
let cs = &b.lp(lp).coedges;
if cs.is_empty() {
issue(format!("face {} loop {li} is empty", f.index()));
continue;
}
for (k, &c) in cs.iter().enumerate() {
let next = cs[(k + 1) % cs.len()];
if b.coedge_end(c) != b.coedge_start(next) {
issue(format!(
"face {} loop {li} breaks after coedge {}",
f.index(),
c.index()
));
}
}
if !sampled {
continue;
}
let mut ends: Vec<(Vec2, Vec2)> = Vec::new();
let mut ring: Vec<Vec2> = Vec::new();
for &c in cs {
let ts = coedge_params(b, c, SAMPLES);
let uvs = b.coedge_uvs(c, &ts);
ring.extend_from_slice(&uvs[..uvs.len() - 1]);
let e = b.coedge(c).edge;
let edge = b.edge(e);
let within = match edge.curve {
Some(_) => b.edge_tolerance(e),
None => b.vertex_tolerance(edge.start),
};
for (t, uv) in ts.iter().zip(&uvs) {
let want = match &edge.curve {
Some(curve) => curve.eval(*t),
None => b.vertex(edge.start).point,
};
let d = face.surface.eval(uv.x, uv.y).dist(want);
if !tol::within(d, within, want) {
issue(format!(
"coedge {} of face {} is {d:e} mm off its surface",
c.index(),
f.index()
));
break;
}
}
ends.push((uvs[0], uvs[uvs.len() - 1]));
}
for k in 0..ends.len() {
let (end, start) = (ends[k].1, ends[(k + 1) % ends.len()].0);
let mut spread = 2.0 * (b.vertex_tolerance(b.coedge_end(cs[k])) - tol::LINEAR);
if spread > 0.0 {
let (_, su, sv) = face.surface.d1(end.x, end.y);
let slowest = su.norm().min(sv.norm()).clamp(1e-12, 1.0);
spread *= std::f64::consts::SQRT_2 / slowest;
}
if uv_gap(b, f, end, start) > 10.0 * tol::LINEAR + spread {
issue(format!(
"face {} ({}) loop {li} does not close in parameters after coedge {}: \
({:.6}, {:.6}) to ({:.6}, {:.6})",
f.index(),
face.surface.kind(),
cs[k].index(),
end.x,
end.y,
start.x,
start.y
));
}
}
let area: f64 = (0..ring.len())
.map(|i| ring[i].cross(ring[(i + 1) % ring.len()]))
.sum();
let perimeter: f64 = (0..ring.len())
.map(|i| ring[i].dist(ring[(i + 1) % ring.len()]))
.sum();
let area = if area.abs() < SLIVER_AREA * perimeter * perimeter {
crate::measure::loop_area(b, lp)
} else {
area
};
let want_positive = (li == 0) != face.reversed;
if !b.is_vertex_loop(lp) && (area > 0.0) != want_positive {
issue(format!("face {} loop {li} runs the wrong way", f.index()));
}
}
if sampled
&& !has_pole
&& found.get() == before
&& face.loops.len() > 1
&& let Some(li) = stray_loop(b, f)
{
issue(format!(
"face {} loop {li} lies outside the region its other loops bound",
f.index()
));
}
if sampled && !has_pole && found.get() == before {
let _ = memo.clean.set(());
}
}
for s in b.solid_ids() {
if b.solid(s).shells.is_empty() {
issue(format!("solid {} has no shells", s.index()));
}
}
if out.is_empty() {
for s in b.solid_ids() {
let v = measure::solid_volume_sign(b, s);
if v.is_nan() || v <= 0.0 {
out.push(Issue {
message: format!("solid {} has volume {v}", s.index()),
});
}
}
}
if out.is_empty() {
for (s, sh, outer) in turned_shells(b) {
let what = if outer { "an outer sheet" } else { "a void" };
out.push(Issue {
message: format!(
"shell {} of solid {} is {what} turned inside out",
sh.index(),
s.index()
),
});
}
}
if out.is_empty() && crossing {
let inside = |f: FaceId, p: Point3| {
matches!(
face_domain(b, f).locate(p),
crate::boolean::domain::Where::Inside(_)
)
};
let overlaps = |f: FaceId, g: FaceId| {
let d = face_domain(b, f);
d.interior_point()
.is_some_and(|uv| inside(g, d.surface.eval(uv.x, uv.y)))
};
let touching = |x: &Crossing| {
b.face(x.a).shell != b.face(x.b).shell
&& depth(b, x.a, x.b).max(depth(b, x.b, x.a)) <= tol::LINEAR
&& !(crate::boolean::ssi::same_domain(&b.face(x.a).surface, &b.face(x.b).surface)
&& (inside(x.a, x.at)
|| inside(x.b, x.at)
|| overlaps(x.a, x.b)
|| overlaps(x.b, x.a)))
};
for x in crossings(b, sides, each)
.into_iter()
.filter(|x| !touching(x))
{
out.push(Issue {
message: format!(
"faces {} and {} share no edge but meet at ({:.6}, {:.6}, {:.6}): the solid \
passes through itself",
x.a.index(),
x.b.index(),
x.at.x,
x.at.y,
x.at.z
),
});
}
}
if out.is_empty() {
for (s, sh) in stray_voids(b) {
out.push(Issue {
message: format!(
"void shell {} of solid {} lies outside its outer shell",
sh.index(),
s.index()
),
});
}
}
if out.is_empty() && !each {
for (s, t) in nested(b) {
out.push(Issue {
message: format!("solid {} lies inside solid {}", s.index(), t.index()),
});
}
}
out
}
fn stray_loop(b: &Brep, f: FaceId) -> Option<usize> {
let d = face_domain(b, f);
let periods = [d.surface.u_period(), d.surface.v_period()];
let wraps = d.samples().iter().any(|l| {
let mut run = [0.0f64; 2];
for pl in l {
let (a, z) = (pl[0], pl[pl.len() - 1]);
run[0] += z.x - a.x;
run[1] += z.y - a.y;
}
(0..2).any(|k| periods[k].is_some_and(|p| run[k].abs() > 0.5 * p))
});
if wraps {
return None;
}
(1..d.loops.len()).find(|&li| {
let pl = &d.samples()[li][0];
!d.inside_without(pl[pl.len() / 2], li)
})
}
fn stray_voids(b: &Brep) -> Vec<(SolidId, ShellId)> {
let mut out = Vec::new();
for s in b.solid_ids() {
let shells = &b.solid(s).shells;
let n_outer = b.solid(s).outer;
if shells.len() <= n_outer {
continue;
}
let outer: Vec<(Domain, Aabb)> = shells[..n_outer]
.iter()
.flat_map(|&sh| b.shell(sh).faces.iter())
.map(|&f| (face_domain(b, f), padded_box(measure::face_box(b, f))))
.collect();
let faces: Vec<(&Domain, Aabb)> = outer.iter().map(|(d, bb)| (d, *bb)).collect();
for &sh in &shells[n_outer..] {
let probe = b.shell(sh).faces.iter().find_map(|&f| {
let d = face_domain(b, f);
d.interior_point().map(|uv| d.surface.eval(uv.x, uv.y))
});
if probe.is_some_and(|p| classify::contains(&faces, p) == Some(false)) {
out.push((s, sh));
}
}
}
out
}
pub(crate) fn turned_shells(b: &Brep) -> Vec<(SolidId, ShellId, bool)> {
let mut out = Vec::new();
for s in b.solid_ids() {
let solid = b.solid(s);
for (k, &sh) in solid.shells.iter().enumerate() {
let outer = k < solid.outer;
let v = measure::enclosed_volume_sign(b, &b.shell(sh).faces);
if (v > 0.0) != outer {
out.push((s, sh, outer));
}
}
}
out
}
pub(crate) fn void_hosts(b: &Brep, s: SolidId) -> Vec<usize> {
let shells = &b.solid(s).shells;
let n_outer = b.solid(s).outer;
let sheets: Vec<Vec<(Domain, Aabb)>> = shells[..n_outer]
.iter()
.map(|&sh| {
b.shell(sh)
.faces
.iter()
.map(|&f| (face_domain(b, f), padded_box(measure::face_box(b, f))))
.collect()
})
.collect();
shells[n_outer..]
.iter()
.map(|&sh| {
let probe = b.shell(sh).faces.iter().find_map(|&f| {
let d = face_domain(b, f);
d.interior_point().map(|uv| d.surface.eval(uv.x, uv.y))
});
let inside = |k: &usize| {
let faces: Vec<(&Domain, Aabb)> =
sheets[*k].iter().map(|(d, bb)| (d, *bb)).collect();
probe.is_some_and(|p| classify::contains(&faces, p) == Some(true))
};
(0..n_outer).find(inside).unwrap_or(0)
})
.collect()
}
fn nested(b: &Brep) -> Vec<(SolidId, SolidId)> {
let solids: Vec<SolidId> = b.solid_ids().collect();
if solids.len() < 2 {
return Vec::new();
}
let parts: Vec<Vec<(Domain, Aabb)>> = solids
.iter()
.map(|&s| {
b.solid_faces(s)
.into_iter()
.map(|f| (face_domain(b, f), padded_box(measure::face_box(b, f))))
.collect()
})
.collect();
let boxes: Vec<Aabb> = parts
.iter()
.map(|fs| {
fs.iter().fold(Aabb::EMPTY, |mut acc, (_, bb)| {
acc.union(bb);
acc
})
})
.collect();
let mut out = Vec::new();
for (i, inner) in parts.iter().enumerate() {
let Some(probe) = inner
.iter()
.find_map(|(d, _)| d.interior_point().map(|uv| d.surface.eval(uv.x, uv.y)))
else {
continue;
};
for (j, outer) in parts.iter().enumerate() {
if i == j || !in_box(probe, &boxes[j]) {
continue;
}
let faces: Vec<(&Domain, Aabb)> = outer.iter().map(|(d, bb)| (d, *bb)).collect();
if classify::contains(&faces, probe) == Some(true) {
out.push((solids[i], solids[j]));
}
}
}
out
}
struct Crossing {
a: FaceId,
b: FaceId,
at: Point3,
}
fn padded_box(bb: Aabb) -> Aabb {
let pad = Vec3::new(tol::LINEAR, tol::LINEAR, tol::LINEAR);
Aabb {
min: bb.min - pad,
max: bb.max + pad,
}
}
fn boxes_meet(a: &Aabb, b: &Aabb) -> bool {
(0..3).all(|k| a.min[k] <= b.max[k] && b.min[k] <= a.max[k])
}
fn in_box(p: Point3, bb: &Aabb) -> bool {
(0..3).all(|k| p[k] >= bb.min[k] && p[k] <= bb.max[k])
}
#[derive(Default)]
struct PairCache {
domains: HashMap<FaceId, Domain>,
edge_boxes: HashMap<EdgeId, Aabb>,
meetings: HashMap<(EdgeId, FaceId), Option<Point3>>,
}
impl PairCache {
fn edge_box(&mut self, b: &Brep, e: EdgeId) -> Option<Aabb> {
let edge = b.edge(e);
let curve = edge.curve.as_ref()?;
Some(
*self
.edge_boxes
.entry(e)
.or_insert_with(|| padded_box(curve.bbox(edge.range.0, edge.range.1))),
)
}
fn face_box(&mut self, b: &Brep, f: FaceId) -> Aabb {
if let Some(bb) = b.memo(f).loose_box.get() {
return padded_box(*bb);
}
let s = &b.face(f).surface;
let mut bb = match s {
Surface::Plane(_) | Surface::Cylinder(_) | Surface::Cone(_) | Surface::Extrusion(_) => {
Aabb::EMPTY
}
Surface::Nurbs(n) => n.hull_box(),
Surface::Sphere(sp) => {
let r = Vec3::new(sp.radius, sp.radius, sp.radius);
Aabb {
min: sp.frame.origin - r,
max: sp.frame.origin + r,
}
}
Surface::Torus(t) => {
let r = t.major + t.minor;
let r = Vec3::new(r, r, r);
Aabb {
min: t.frame.origin - r,
max: t.frame.origin + r,
}
}
_ => return padded_box(measure::face_box(b, f)),
};
for &lp in &b.face(f).loops {
for &c in &b.lp(lp).coedges {
let e = b.coedge(c).edge;
match self.edge_box(b, e) {
Some(eb) => bb.union(&eb),
None => bb.add(b.vertex(b.edge(e).start).point),
}
}
}
padded_box(bb)
}
}
fn crossings(b: &Brep, sides: Option<&[Option<usize>]>, each: bool) -> Vec<Crossing> {
let faces: Vec<FaceId> = b.face_ids().collect();
let solid_of = |f: FaceId| b.face(f).shell.and_then(|s| b.shell(s).solid);
let mut cache = PairCache::default();
let boxes: Vec<Aabb> = faces.iter().map(|&f| cache.face_box(b, f)).collect();
let mut order: Vec<usize> = (0..faces.len()).collect();
order.sort_by(|&i, &j| boxes[i].min.x.total_cmp(&boxes[j].min.x));
let mut by_edge: HashMap<EdgeId, Vec<FaceId>> = HashMap::new();
let mut verts: HashMap<FaceId, Vec<VertexId>> = HashMap::new();
for &f in &faces {
let vs = verts.entry(f).or_default();
for &lp in &b.face(f).loops {
for &c in &b.lp(lp).coedges {
let e = b.coedge(c).edge;
by_edge.entry(e).or_default().push(f);
vs.push(b.edge(e).start);
vs.push(b.edge(e).end);
}
}
}
let adjacent: HashSet<(FaceId, FaceId)> = by_edge
.values()
.flat_map(|fs| fs.iter().flat_map(|&x| fs.iter().map(move |&y| (x, y))))
.collect();
let apart = |ma: &FaceMemo, mb: &FaceMemo| {
for (m, other) in [(ma, mb.id), (mb, ma.id)] {
if let Ok(mut s) = m.apart.lock() {
s.insert(other);
}
}
};
let mut out = Vec::new();
for (k, &i) in order.iter().enumerate() {
for &j in &order[k + 1..] {
if boxes[j].min.x > boxes[i].max.x {
break;
}
let (fa, fb) = (faces[i], faces[j]);
if !boxes_meet(&boxes[i], &boxes[j])
|| adjacent.contains(&(fa, fb))
|| (each && solid_of(fa) != solid_of(fb))
{
continue;
}
let (ma, mb) = (b.memo(fa), b.memo(fb));
if sides.is_some_and(|s| s[fa.index()].is_some() && s[fa.index()] == s[fb.index()]) {
apart(ma, mb);
continue;
}
if ma.apart.lock().is_ok_and(|s| s.contains(&mb.id)) {
continue;
}
let (sa, sb) = (&b.face(fa).surface, &b.face(fb).surface);
if (analytic(sb) && clear_of(&boxes[i], sb))
|| (analytic(sa) && clear_of(&boxes[j], sa))
{
apart(ma, mb);
continue;
}
let mut hit = None;
'pair: for (x, y, ybox) in [(fa, fb, &boxes[j]), (fb, fa, &boxes[i])] {
for &lp in &b.face(x).loops {
for &c in &b.lp(lp).coedges {
let e = b.coedge(c).edge;
let Some(eb) = cache.edge_box(b, e) else {
continue;
};
if !boxes_meet(&eb, ybox) {
continue;
}
hit = match cache.meetings.get(&(e, y)) {
Some(&m) => m,
None => {
let m = edge_meets_face(b, e, y, ybox, &verts[&y], &mut cache);
cache.meetings.insert((e, y), m);
m
}
};
if hit.is_some() {
break 'pair;
}
}
}
}
match hit {
Some(at) => out.push(Crossing { a: fa, b: fb, at }),
None => apart(ma, mb),
}
}
}
out
}
fn gap(s: &Surface, p: Point3) -> f64 {
match s {
Surface::Plane(_)
| Surface::Cylinder(_)
| Surface::Cone(_)
| Surface::Sphere(_)
| Surface::Torus(_) => signed_distance(s, p).abs(),
_ => distance_to(s, p),
}
}
fn analytic(s: &Surface) -> bool {
matches!(
s,
Surface::Plane(_)
| Surface::Cylinder(_)
| Surface::Cone(_)
| Surface::Sphere(_)
| Surface::Torus(_)
)
}
fn clear_of(bb: &Aabb, s: &Surface) -> bool {
let reach = match s {
Surface::Plane(p) => {
let h = (bb.max - bb.min) * 0.5;
let n = p.frame.z;
n.x.abs() * h.x + n.y.abs() * h.y + n.z.abs() * h.z
}
_ => 0.5 * bb.diagonal(),
};
gap(s, (bb.min + bb.max) * 0.5) > reach + tol::LINEAR
}
fn near_ranges(
curve: &Curve,
range: (f64, f64),
whole: Aabb,
s: &Surface,
bound: &Aabb,
) -> Vec<(f64, f64)> {
fn halve(
c: &Curve,
(t0, t1): (f64, f64),
bb: Aabb,
depth: u32,
s: &Surface,
bound: &Aabb,
out: &mut Vec<(f64, f64)>,
) {
if !boxes_meet(&bb, bound) || (analytic(s) && clear_of(&bb, s)) {
return;
}
let m = 0.5 * (t0 + t1);
let p = c.eval(m);
let g = gap(s, p);
if !analytic(s) {
let mut reach: f64 = 0.0;
for k in 0..8 {
let corner = Vec3::new(
if k & 1 == 0 { bb.min.x } else { bb.max.x },
if k & 2 == 0 { bb.min.y } else { bb.max.y },
if k & 4 == 0 { bb.min.z } else { bb.max.z },
);
reach = reach.max(corner.dist(p));
}
if g > reach + tol::LINEAR {
return;
}
}
if depth == 0 || g <= tol::LINEAR {
match out.last_mut() {
Some(last) if last.1 == t0 => last.1 = t1,
_ => out.push((t0, t1)),
}
return;
}
for r in [(t0, m), (m, t1)] {
let bb = padded_box(c.bbox(r.0, r.1));
halve(c, r, bb, depth - 1, s, bound, out);
}
}
let mut out = Vec::new();
halve(curve, range, whole, 8, s, bound, &mut out);
out
}
fn edge_meets_face(
b: &Brep,
e: EdgeId,
y: FaceId,
bound: &Aabb,
own: &[VertexId],
cache: &mut PairCache,
) -> Option<Point3> {
let edge = b.edge(e);
let curve = edge.curve.as_ref()?;
let whole = cache.edge_box(b, e)?;
let s = &b.face(y).surface;
let ends: Vec<(f64, Point3, f64)> = [(edge.range.0, edge.start), (edge.range.1, edge.end)]
.into_iter()
.filter(|(_, v)| own.contains(v))
.map(|(t, v)| (t, b.vertex(v).point, b.vertex_tolerance(v)))
.collect();
let along = b.edge_tolerance(e);
let at_shared = |t: f64, p: Point3| {
ends.iter().any(|&(tv, q, within)| {
q.dist(p) <= within
|| (0..=8).all(|k| {
let x = curve.eval(t + (tv - t) * k as f64 / 8.0);
signed_distance(s, x).abs() <= along
})
})
};
let near_end = |p: Point3| ends.iter().any(|&(_, q, within)| q.dist(p) <= within);
let mut found: Vec<Point3> = Vec::new();
for range in near_ranges(curve, edge.range, whole, s, bound) {
let hits = curve_surface(curve, range, s);
if !hits.on_surface {
found.extend(
hits.ts
.iter()
.map(|&t| (t, curve.eval(t)))
.filter(|&(t, p)| !at_shared(t, p))
.map(|(_, p)| p),
);
continue;
}
found.extend((1..4).map(|k| curve.eval(range.0 + (range.1 - range.0) * k as f64 / 4.0)));
}
let reach = 10.0 * along.max(tol::LINEAR);
found.retain(|&p| in_box(p, bound) && !near_end(p) && gap(s, p) <= reach);
if found.is_empty() {
return None;
}
let dom = cache.domains.entry(y).or_insert_with(|| face_domain(b, y));
found
.into_iter()
.find(|&p| dom.on_boundary(p) || dom.exact_side(p).is_some())
}
fn coincident_vertices(b: &Brep) -> Vec<(VertexId, VertexId)> {
let cell = |x: f64| (x / (4.0 * tol::LINEAR)).floor() as i64;
let mut grid: HashMap<[i64; 3], Vec<VertexId>> = HashMap::new();
let mut out = Vec::new();
for v in b.vertex_ids() {
let p = b.vertex(v).point;
if !(p.x.is_finite() && p.y.is_finite() && p.z.is_finite()) {
continue;
}
let c = [cell(p.x), cell(p.y), cell(p.z)];
for dx in -1..=1 {
for dy in -1..=1 {
for dz in -1..=1 {
for &w in grid
.get(&[c[0] + dx, c[1] + dy, c[2] + dz])
.into_iter()
.flatten()
{
if b.vertex(w).point.dist(p) <= tol::LINEAR {
out.push((w, v));
}
}
}
}
}
grid.entry(c).or_default().push(v);
}
let (tolerant, _) = b.tolerant();
if tolerant.is_empty() {
return out;
}
let widest = tolerant.iter().map(|&(_, t)| t).fold(tol::LINEAR, f64::max);
let mut by_x: Vec<(f64, VertexId)> = b
.vertex_ids()
.map(|v| (b.vertex(v).point.x, v))
.filter(|(x, _)| x.is_finite())
.collect();
by_x.sort_by(|a, b| a.0.total_cmp(&b.0));
for &(v, tv) in &tolerant {
let p = b.vertex(v).point;
let reach = tol::between(tv, widest);
let from = by_x.partition_point(|&(x, _)| x < p.x - reach);
for &(x, w) in &by_x[from..] {
if x > p.x + reach {
break;
}
if w == v || (b.vertex_tolerance(w) > tol::LINEAR && w < v) {
continue;
}
let d = b.vertex(w).point.dist(p);
if d > tol::LINEAR && d <= tol::between(tv, b.vertex_tolerance(w)) {
out.push((v.min(w), v.max(w)));
}
}
}
out
}
pub(crate) fn vertex_fans(b: &Brep) -> HashMap<VertexId, usize> {
fans_at_vertices(b)
.into_iter()
.map(|(v, fs)| (v, fs.len()))
.collect()
}
pub(crate) fn fans_at_vertices(b: &Brep) -> HashMap<VertexId, Vec<Vec<CoedgeId>>> {
let mut corners: HashMap<VertexId, Vec<(CoedgeId, CoedgeId)>> = HashMap::new();
for lp in b.loop_ids() {
let cs = &b.lp(lp).coedges;
for k in 0..cs.len() {
let (a, n) = (cs[k], cs[(k + 1) % cs.len()]);
let v = b.coedge_end(a);
if b.coedge_start(n) == v {
corners.entry(v).or_default().push((a, n));
}
}
}
let mut out = HashMap::new();
for (&v, cs) in &corners {
let by_arrival: HashMap<CoedgeId, usize> =
cs.iter().enumerate().map(|(i, &(a, _))| (a, i)).collect();
let mut seen = vec![false; cs.len()];
let mut fans = Vec::new();
for start in 0..cs.len() {
if seen[start] {
continue;
}
let mut fan = Vec::new();
let mut i = start;
while !seen[i] {
seen[i] = true;
fan.push(cs[i].0);
let leaving = cs[i].1;
let mate = if b.edge(b.coedge(leaving).edge).is_degenerate() {
Some(leaving)
} else {
b.partner(leaving).filter(|&m| b.coedge_end(m) == v)
};
match mate.and_then(|m| by_arrival.get(&m)) {
Some(&j) => i = j,
None => break,
}
}
fans.push(fan);
}
out.insert(v, fans);
}
out
}
pub(crate) fn contacts(b: &Brep) -> (HashSet<EdgeId>, HashSet<VertexId>) {
let edges: HashSet<EdgeId> = b.radial_edges().collect();
let mut vertices: HashSet<VertexId> = vertex_fans(b)
.into_iter()
.filter(|&(_, n)| n > 1)
.map(|(v, _)| v)
.collect();
for &e in &edges {
vertices.extend([b.edge(e).start, b.edge(e).end]);
}
(edges, vertices)
}
pub(crate) fn faces_at_contacts(b: &Brep, faces: impl IntoIterator<Item = FaceId>) -> Vec<FaceId> {
let (edges, vertices) = contacts(b);
if edges.is_empty() && vertices.is_empty() {
return Vec::new();
}
faces
.into_iter()
.filter(|&f| {
b.face(f).loops.iter().any(|&lp| {
b.lp(lp).coedges.iter().any(|&c| {
edges.contains(&b.coedge(c).edge) || vertices.contains(&b.coedge_start(c))
})
})
})
.collect()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::geom::{BSpline, IntersectionCurve, Plane};
use crate::math::{Frame, Vec3};
fn fitted(points: &[Vec3]) -> Curve {
let plane = |z: Vec3| {
Surface::Plane(Plane {
frame: Frame::from_axis(Vec3::ZERO, z).unwrap(),
})
};
Curve::Intersection(Box::new(IntersectionCurve {
approx: BSpline::interpolate(points).unwrap(),
surfaces: [plane(Vec3::Z), plane(Vec3::Y)],
}))
}
#[test]
fn a_fitted_curve_that_doubles_back_folds_and_one_that_bends_does_not() {
let zigzag: Vec<Vec3> = [0.0, 1.0, 2.0, 1.9, 3.0, 4.0]
.iter()
.enumerate()
.map(|(i, &x)| Vec3::new(x, 0.01 * i as f64, 0.0))
.collect();
let bend: Vec<Vec3> = (0..=8)
.map(|k| {
let a = std::f64::consts::FRAC_PI_2 * k as f64 / 8.0;
Vec3::new(a.cos(), a.sin(), 0.0)
})
.collect();
for (pts, folds) in [(zigzag, true), (bend, false)] {
let c = fitted(&pts);
let knots = c.spline().unwrap().knots();
let range = (knots[0], knots[knots.len() - 1]);
assert_eq!(fold(&c, range).is_some(), folds);
}
}
}