use std::collections::{BTreeSet, HashMap};
use super::adjust::{Target, adjust};
use super::topology::{Raw, edge_range, param_of};
use crate::{
Error, Result,
geom::{BSpline, Curve, IntersectionCurve, Surface, refine_onto_both},
math::{Point3, Vec3},
numeric::solve_dense,
tol,
};
const MAX_MOVE: f64 = 0.5;
const MOVE_PER_GAP: f64 = 10.0;
fn fail<T>(id: u64, what: &str) -> Result<T> {
Err(Error::InvalidInput(format!("STEP #{id}: {what}")))
}
fn surface_gap(s: &Surface, p: Point3) -> f64 {
let uv = s.project(p);
s.eval(uv.x, uv.y).dist(p)
}
const CHECK_SAMPLES: usize = 16;
fn sample_params(c: &Curve, r: (f64, f64), per_span: usize) -> Vec<f64> {
let mut cuts = vec![r.0];
cuts.extend(c.breakpoints(r.0, r.1));
cuts.push(r.1);
let per = if matches!(c, Curve::Line(_)) {
2
} else {
per_span.max(16 / (cuts.len() - 1))
};
let mut ts = Vec::new();
for w in cuts.windows(2) {
for k in 0..per {
ts.push(w[0] + (w[1] - w[0]) * k as f64 / per as f64);
}
}
if per > 2 {
ts.extend((1..CHECK_SAMPLES).map(|k| r.0 + (r.1 - r.0) * k as f64 / CHECK_SAMPLES as f64));
ts.sort_by(f64::total_cmp);
}
ts.push(r.1);
ts
}
fn edge_fits(raw: &Raw, e: usize, range: Option<(f64, f64)>) -> bool {
let Some(r) = range else { return false };
let edge = &raw.edges[e];
let c = &edge.curve;
if c.eval(r.0).dist(raw.points[edge.start]) > tol::LINEAR
|| c.eval(r.1).dist(raw.points[edge.end]) > tol::LINEAR
{
return false;
}
let ts = sample_params(c, r, 4);
let mut faces = edge.faces.clone();
faces.dedup();
faces.iter().all(|&f| {
let s = &raw.faces[f].surface;
let mut hint = s.project(c.eval(ts[0]));
ts.iter().all(|&t| {
let p = c.eval(t);
let uv = s.project_near(p, hint);
hint = uv;
s.eval(uv.x, uv.y).dist(p) <= tol::LINEAR
})
})
}
enum On<'a> {
Surface(&'a Surface),
Curve(&'a Curve),
Plane(Point3, Vec3),
}
const MEET_REACH: f64 = 0.05;
fn solve_vertex(p0: Point3, on: &[On], reach: Option<f64>) -> Option<Point3> {
let mut x = p0;
let mut reach = reach;
let mut best = (f64::INFINITY, p0);
for _ in 0..100 {
let mut rows: Vec<(Vec3, f64)> = Vec::new();
for c in on {
match c {
On::Surface(s) => {
let uv = s.project(x);
let q = s.eval(uv.x, uv.y);
let d = x - q;
let n = d
.unit()
.filter(|_| d.norm() > 1e-14)
.unwrap_or(s.normal(uv.x, uv.y));
rows.push((n, n.dot(d)));
}
On::Curve(c) => {
let t = param_of(c, x);
let (q, tan) = c.d1(t);
let d = x - q;
let tan = tan.unit_or_zero();
let e1 = (d - tan * d.dot(tan))
.unit()
.filter(|_| d.norm() > 1e-14)
.unwrap_or(tan.any_perpendicular().unit_or_zero());
let e2 = tan.cross(e1);
rows.push((e1, e1.dot(d)));
rows.push((e2, e2.dot(d)));
}
On::Plane(o, n) => rows.push((*n, n.dot(x - *o))),
}
}
let worst = rows.iter().map(|r| r.1.abs()).fold(0.0, f64::max);
let reach = *reach.get_or_insert((MOVE_PER_GAP * (worst + tol::LINEAR)).min(MAX_MOVE));
if worst < best.0 {
best = (worst, x);
}
if worst <= 1e-3 * tol::LINEAR {
break;
}
let mut a = vec![0.0; 9];
let mut b = vec![0.0; 3];
for (n, r) in &rows {
let n = n.to_array();
for i in 0..3 {
for j in 0..3 {
a[i * 3 + j] += n[i] * n[j];
}
b[i] -= n[i] * r;
}
}
let trace = a[0] + a[4] + a[8];
let mut damp = 1e-10 * trace + 1e-300;
let step = loop {
let mut ad = a.clone();
for i in 0..3 {
ad[i * 3 + i] += damp;
}
let st = solve_dense(ad, b.clone(), 3, 1).ok()?;
let st = Vec3::new(st[0], st[1], st[2]);
if (x + st).dist(p0) <= reach || damp > trace {
break st;
}
damp *= 100.0;
};
if (x + step).dist(p0) > reach {
break;
}
x += step;
if step.norm() <= 1e-16 * (1.0 + x.norm()) {
break;
}
}
let x = best.1;
let worst = on
.iter()
.map(|c| match c {
On::Surface(s) => surface_gap(s, x),
On::Curve(c) => c.eval(param_of(c, x)).dist(x),
On::Plane(o, n) => n.dot(x - *o).abs(),
})
.fold(0.0, f64::max);
(worst <= 0.25 * tol::LINEAR && x.dist(p0) <= reach.unwrap_or(0.0)).then_some(x)
}
const MAX_REFIT_POINTS: usize = 4096;
fn onto_both(a: &Surface, b: &Surface, same: bool, p: Point3, along: Vec3) -> Option<Point3> {
let ok = |x: Point3| {
surface_gap(a, x) <= 0.25 * tol::LINEAR && surface_gap(b, x) <= 0.25 * tol::LINEAR
};
if same {
let uv = a.project(p);
return Some(a.eval(uv.x, uv.y));
}
if ok(p) {
return Some(p);
}
if let Some(x) = refine_onto_both(a, b, p).filter(|&x| ok(x)) {
return Some(x);
}
let mut x = p;
let (mut ha, mut hb) = (a.project(x), b.project(x));
for _ in 0..400 {
ha = a.project_near(x, ha);
x = a.eval(ha.x, ha.y);
hb = b.project_near(x, hb);
let y = b.eval(hb.x, hb.y);
let moved = y.dist(x);
x = y;
if moved <= 1e-3 * tol::LINEAR {
break;
}
}
if ok(x) {
return Some(x);
}
let along = along.unit()?;
let on = [On::Surface(a), On::Surface(b), On::Plane(p, along)];
solve_vertex(p, &on, Some(MEET_REACH))
}
fn chord_params(points: &[Point3], closed: bool) -> Vec<f64> {
let n = points.len();
let count = if closed { n } else { n - 1 };
let mut params = vec![0.0];
for i in 0..count {
params.push(params[i] + points[i].dist(points[(i + 1) % n]));
}
params
}
fn refit(
raw: &Raw,
e: usize,
range: Option<(f64, f64)>,
samples: Option<&Vec<Point3>>,
) -> std::result::Result<(Curve, (f64, f64)), String> {
let edge = &raw.edges[e];
let mut faces = edge.faces.clone();
faces.sort_unstable();
if faces.len() != 2 {
return Err(format!("the edge is used by {} faces, not 2", faces.len()));
}
let (a, b) = (&raw.faces[faces[0]].surface, &raw.faces[faces[1]].surface);
let same = faces[0] == faces[1];
let closed = edge.start == edge.end;
let (ps, pe) = (raw.points[edge.start], raw.points[edge.end]);
let c = &edge.curve;
let r = match range {
Some(r) => r,
None => {
let (t0, t1) = (param_of(c, ps), param_of(c, pe));
match c.period() {
Some(p) if closed => (t0, t0 + p),
Some(p) => (t0, t0 + (t1 - t0).rem_euclid(p)),
None => (t0.min(t1), t0.max(t1)),
}
}
};
let length: f64 = {
let ts = sample_params(c, r, 8);
ts.windows(2).map(|w| c.eval(w[0]).dist(c.eval(w[1]))).sum()
};
let n = ((length / (100.0 * tol::LINEAR)) as usize).clamp(1, 8);
let placed = samples.filter(|s| !s.is_empty());
let mut pts = match placed {
Some(s) => {
let mut p = vec![ps];
p.extend(s.iter().copied());
if !closed {
p.push(pe);
}
p
}
None => {
let mut p = bent(c, r, n, (ps, pe));
if closed {
p.pop();
}
p
}
};
if closed && pts.len() < 3 {
return Err("the closed edge is too short to refit".into());
}
let kinds = format!("{} and {}", a.kind(), b.kind());
let refine = |p: Point3, along: Vec3| onto_both(a, b, same, p, along);
let last = pts.len() - 1;
let count = pts.len();
let before = pts.clone();
for (i, p) in pts.iter_mut().enumerate() {
if closed || (i != 0 && i != last) {
let t = r.0 + (r.1 - r.0) * i as f64 / (if closed { count } else { last }) as f64;
let along = match placed {
Some(_) => before[(i + 1) % count] - before[(i + count - 1) % count],
None => c.d1(t).1,
};
*p = refine(*p, along)
.ok_or_else(|| format!("its {kinds} faces do not meet near it"))?;
}
}
for _ in 0..16 {
let approx = if closed {
BSpline::interpolate_periodic(&pts).ok()
} else {
BSpline::interpolate(&pts).ok()
};
let Some(approx) = approx else {
return Err("its points on both faces could not be interpolated".into());
};
let params = chord_params(&pts, closed);
let n_seg = params.len() - 1;
let err: Vec<f64> = (0..n_seg)
.map(|i| {
[0.25, 0.5, 0.75]
.iter()
.map(|f| {
let m = approx.eval(params[i] + (params[i + 1] - params[i]) * f);
surface_gap(a, m).max(surface_gap(b, m))
})
.fold(0.0, f64::max)
})
.collect();
if err.iter().all(|&x| x <= 0.5 * tol::LINEAR) {
let dom = approx.domain();
let on_both = (0..n_seg).all(|i| {
(1..8).all(|k| {
let m = approx.eval(params[i] + (params[i + 1] - params[i]) * k as f64 / 8.0);
surface_gap(a, m).max(surface_gap(b, m)) <= 0.5 * tol::LINEAR
})
}) && (1..CHECK_SAMPLES).all(|k| {
let m = approx.eval(dom.0 + (dom.1 - dom.0) * k as f64 / CHECK_SAMPLES as f64);
surface_gap(a, m).max(surface_gap(b, m)) <= 0.5 * tol::LINEAR
});
let curve = if on_both {
Curve::BSpline(approx)
} else {
Curve::Intersection(Box::new(IntersectionCurve {
approx,
surfaces: [a.clone(), b.clone()],
}))
};
return Ok((curve, dom));
}
let mut next = Vec::with_capacity(pts.len() * 2);
for i in 0..n_seg {
next.push(pts[i]);
if err[i] > 0.125 * tol::LINEAR {
let m = approx.eval(0.5 * (params[i] + params[i + 1]));
let along = pts[(i + 1) % pts.len()] - pts[i];
let q =
refine(m, along).ok_or_else(|| format!("its {kinds} faces part along it"))?;
if q.dist(pts[i]) <= 4.0 * tol::LINEAR
|| q.dist(pts[(i + 1) % pts.len()]) <= 4.0 * tol::LINEAR
{
return Err(format!(
"its {kinds} faces meet {:.1e} mm off the curve through its ends",
err[i]
));
}
next.push(q);
}
}
if !closed {
next.push(pts[pts.len() - 1]);
}
pts = next;
if pts.len() > MAX_REFIT_POINTS {
break;
}
}
Err(format!(
"no curve through {} points stays within tolerance of its {kinds} faces, which touch \
rather than cross",
pts.len()
))
}
fn range_near(raw: &Raw, e: usize, old: (f64, f64)) -> (f64, f64) {
let edge = &raw.edges[e];
let c = &edge.curve;
let near = |p: Point3, to: f64| {
let t = param_of(c, p);
match c.period() {
Some(per) => t + ((to - t) / per).round() * per,
None => t,
}
};
let t0 = near(raw.points[edge.start], old.0);
match c.period() {
Some(per) if edge.start == edge.end => (t0, t0 + per),
_ => (t0, near(raw.points[edge.end], old.1)),
}
}
#[derive(Clone, Debug, PartialEq)]
pub struct Healed {
pub moved: f64,
pub at: Point3,
pub what: String,
pub surfaces: f64,
}
pub(super) type Ranges = (Vec<(f64, f64)>, Option<Healed>);
pub const MAX_HEAL: f64 = 0.05;
const ADJUST_ROUNDS: usize = 3;
enum Failure {
Vertex(usize, String),
Edge(usize, String),
}
fn range_of(raw: &Raw, e: usize) -> Option<(f64, f64)> {
let edge = &raw.edges[e];
edge_range(
&edge.curve,
raw.points[edge.start],
raw.points[edge.end],
edge.start == edge.end,
)
}
fn attempt(
raw: &mut Raw,
start: &HashMap<usize, Point3>,
samples: &HashMap<usize, Vec<Point3>>,
loose: bool,
) -> std::result::Result<Vec<(f64, f64)>, Vec<Failure>> {
let ranges: Vec<Option<(f64, f64)>> = (0..raw.edges.len()).map(|e| range_of(raw, e)).collect();
let fits: Vec<bool> = (0..raw.edges.len())
.map(|e| edge_fits(raw, e, ranges[e]))
.collect();
let mut at_vertex: Vec<Vec<usize>> = vec![Vec::new(); raw.points.len()];
for (e, edge) in raw.edges.iter().enumerate() {
at_vertex[edge.start].push(e);
if edge.end != edge.start {
at_vertex[edge.end].push(e);
}
}
let mut failures = Vec::new();
let mut moved = raw.points.clone();
let mut stuck = vec![false; raw.points.len()];
for (v, edges) in at_vertex.iter().enumerate() {
let p0 = start.get(&v).copied().unwrap_or(raw.points[v]);
if edges.iter().all(|&e| fits[e]) && p0 == raw.points[v] {
continue;
}
let mut faces: Vec<usize> = edges
.iter()
.flat_map(|&e| raw.edges[e].faces.iter().copied())
.collect();
faces.sort_unstable();
faces.dedup();
let mut on: Vec<On> = faces
.iter()
.map(|&f| On::Surface(&raw.faces[f].surface))
.collect();
let surfaces_only = on.len();
on.extend(
edges
.iter()
.filter(|&&e| fits[e])
.map(|&e| On::Curve(&raw.edges[e].curve)),
);
let p =
solve_vertex(p0, &on, None).or_else(|| solve_vertex(p0, &on[..surfaces_only], None));
match p {
Some(p) => moved[v] = p,
None => {
let gap = faces
.iter()
.map(|&f| surface_gap(&raw.faces[f].surface, p0))
.fold(0.0, f64::max);
stuck[v] = true;
failures.push(Failure::Vertex(
v,
format!(
"the {} faces at an end of this edge have no common point near it (the \
file's vertex is {gap:.1e} mm off one)",
faces.len()
),
));
}
}
}
let before = std::mem::replace(&mut raw.points, moved);
let ends_close = |raw: &Raw, e: usize, r: Option<(f64, f64)>| {
let edge = &raw.edges[e];
r.is_some_and(|r| {
[(r.0, edge.start), (r.1, edge.end)].iter().all(|&(t, v)| {
raw.points[v] == before[v]
|| edge.curve.eval(t).dist(raw.points[v]) <= 0.25 * tol::LINEAR
})
})
};
let mut out = Vec::with_capacity(raw.edges.len());
for (e, &old) in ranges.iter().enumerate() {
let edge = &raw.edges[e];
if !loose && (stuck[edge.start] || stuck[edge.end]) {
out.push((0.0, 0.0));
continue;
}
let r = match old {
Some(old) => Some(range_near(raw, e, old)),
None => range_of(raw, e),
};
if edge_fits(raw, e, r) && ends_close(raw, e, r) {
out.push(r.unwrap_or((0.0, 0.0)));
continue;
}
let rf = match samples.get(&e) {
Some(s) => {
refit(raw, e, r.or(old), Some(s)).or_else(|_| refit(raw, e, r.or(old), None))
}
None => refit(raw, e, r.or(old), None),
};
match rf {
Ok((curve, r)) => {
raw.edges[e].curve = curve;
out.push(r);
}
Err(why) => {
failures.push(Failure::Edge(e, why));
out.push((0.0, 0.0));
}
}
}
if failures.is_empty() {
Ok(out)
} else {
Err(failures)
}
}
fn curve_range(raw: &Raw, e: usize) -> (f64, f64) {
if let Some(r) = range_of(raw, e) {
return r;
}
let edge = &raw.edges[e];
let c = &edge.curve;
let (t0, t1) = (
param_of(c, raw.points[edge.start]),
param_of(c, raw.points[edge.end]),
);
match c.period() {
Some(p) if edge.start == edge.end => (t0, t0 + p),
Some(p) => (t0, t0 + (t1 - t0).rem_euclid(p)),
None => (t0.min(t1), t0.max(t1)),
}
}
fn inner_samples(raw: &Raw, e: usize, count: usize) -> Vec<Point3> {
let c = &raw.edges[e].curve;
let r = curve_range(raw, e);
(1..=count)
.map(|i| c.eval(r.0 + (r.1 - r.0) * i as f64 / (count + 1) as f64))
.collect()
}
fn bent(c: &Curve, r: (f64, f64), n: usize, ends: (Point3, Point3)) -> Vec<Point3> {
let (d0, d1) = (ends.0 - c.eval(r.0), ends.1 - c.eval(r.1));
let mut pts: Vec<Point3> = (0..=n)
.map(|i| {
let s = i as f64 / n as f64;
c.eval(r.0 + (r.1 - r.0) * s) + d0 * (1.0 - s) + d1 * s
})
.collect();
pts[0] = ends.0;
pts[n] = ends.1;
pts
}
fn targets(
raw: &Raw,
faces: &BTreeSet<usize>,
failing: &BTreeSet<usize>,
start: &HashMap<usize, Point3>,
) -> Vec<Target> {
let mut out = Vec::new();
let mut vertices = BTreeSet::new();
let mut at_vertex: HashMap<usize, Vec<usize>> = HashMap::new();
for (e, edge) in raw.edges.iter().enumerate() {
at_vertex.entry(edge.start).or_default().push(e);
at_vertex.entry(edge.end).or_default().push(e);
if !edge.faces.iter().any(|f| faces.contains(f)) {
continue;
}
vertices.insert(edge.start);
vertices.insert(edge.end);
let mut fs = edge.faces.clone();
fs.sort_unstable();
fs.dedup();
let count = if failing.contains(&e) {
let r = curve_range(raw, e);
(4 * (edge.curve.breakpoints(r.0, r.1).len() + 1)).clamp(33, 96)
} else {
3
};
let at = |v: usize| start.get(&v).copied().unwrap_or(raw.points[v]);
let pts = bent(
&edge.curve,
curve_range(raw, e),
count + 1,
(at(edge.start), at(edge.end)),
);
for i in 1..=count {
out.push(Target::sample(
raw,
pts[i],
fs.clone(),
e,
pts[i + 1] - pts[i - 1],
));
}
}
for v in vertices {
let mut fs: Vec<usize> = at_vertex[&v]
.iter()
.flat_map(|&e| raw.edges[e].faces.iter().copied())
.collect();
fs.sort_unstable();
fs.dedup();
out.push(Target::vertex(
raw,
start.get(&v).copied().unwrap_or(raw.points[v]),
fs,
v,
));
}
out
}
fn movement(file: &Raw, healed: &Raw, faces: &BTreeSet<usize>) -> Option<Healed> {
let mut best: Option<Healed> = None;
let mut surfaces: f64 = 0.0;
let mut note = |moved: f64, at: Point3, what: String| {
if moved > best.as_ref().map_or(0.0, |b| b.moved) {
best = Some(Healed {
moved,
at,
what,
surfaces: 0.0,
});
}
};
for (v, (&a, &b)) in file.points.iter().zip(&healed.points).enumerate() {
note(a.dist(b), b, format!("vertex #{}", file.vertex_ids[v]));
}
for &f in faces {
let (s0, s1) = (&file.faces[f].surface, &healed.faces[f].surface);
for (e, edge) in file.edges.iter().enumerate() {
if !edge.faces.contains(&f) {
continue;
}
for p in inner_samples(file, e, 5) {
let uv = s0.project(p);
let a = s0.eval(uv.x, uv.y);
let uv = s1.project_near(a, uv);
let b = s1.eval(uv.x, uv.y);
surfaces = surfaces.max(a.dist(b));
note(
a.dist(b),
b,
format!("the surface of face #{}", file.faces[f].id),
);
}
}
}
for (e, (a, b)) in file.edges.iter().zip(&healed.edges).enumerate() {
if a.curve == b.curve {
continue;
}
for p in inner_samples(healed, e, 7) {
let q = a.curve.eval(param_of(&a.curve, p));
note(p.dist(q), p, format!("edge #{}", a.id));
}
}
best.map(|b| Healed { surfaces, ..b })
}
pub(super) fn heal(raw: &mut Raw) -> Result<Ranges> {
let ranges: Vec<Option<(f64, f64)>> = (0..raw.edges.len()).map(|e| range_of(raw, e)).collect();
if (0..raw.edges.len()).all(|e| edge_fits(raw, e, ranges[e])) {
let ranges = ranges
.into_iter()
.map(|r| r.unwrap_or((0.0, 0.0)))
.collect();
return Ok((ranges, None));
}
let file = raw.clone();
let mut surfaces: Vec<Surface> = file.faces.iter().map(|f| f.surface.clone()).collect();
let mut chosen = BTreeSet::new();
let mut failing = BTreeSet::new();
let mut start = HashMap::new();
let mut samples: HashMap<usize, Vec<Point3>> = HashMap::new();
let mut settled = true;
let with_surfaces = |surfaces: &[Surface]| {
let mut r = file.clone();
for (f, s) in r.faces.iter_mut().zip(surfaces) {
f.surface = s.clone();
}
r
};
for round in 0..=ADJUST_ROUNDS {
let mut work = with_surfaces(&surfaces);
let failures = match attempt(&mut work, &start, &samples, false) {
Ok(ranges) => {
let healed = movement(&file, &work, &chosen);
if let Some(h) = healed.as_ref().filter(|h| h.moved > MAX_HEAL) {
return fail(
file.edges.first().map_or(0, |e| e.id),
&format!(
"healing would move {} {:.1e} mm, more than the {MAX_HEAL} mm allowed",
h.what, h.moved
),
);
}
*raw = work;
return Ok((ranges, healed));
}
Err(f) => f,
};
let before = chosen.len();
for f in &failures {
match f {
Failure::Vertex(v, _) => {
for edge in file.edges.iter().filter(|e| e.start == *v || e.end == *v) {
chosen.extend(edge.faces.iter().copied());
}
}
Failure::Edge(e, _) => {
failing.insert(*e);
chosen.extend(file.edges[*e].faces.iter().copied());
}
}
}
let stuck = round > 0 && chosen.len() == before && !settled;
if round == ADJUST_ROUNDS || stuck {
let (id, why) = match &failures[0] {
Failure::Vertex(v, why) => (
file.edges
.iter()
.find(|e| e.start == *v || e.end == *v)
.map_or(0, |e| e.id),
why.clone(),
),
Failure::Edge(e, why) => (file.edges[*e].id, why.clone()),
};
return fail(id, &why);
}
let mut shaped = with_surfaces(&surfaces);
let mut pts = targets(&file, &chosen, &failing, &start);
let faces: Vec<usize> = chosen.iter().copied().collect();
let (at, met) = adjust(&mut shaped, &faces, &mut pts);
settled = met;
surfaces = shaped.faces.into_iter().map(|f| f.surface).collect();
start = at;
samples.clear();
for t in &pts {
if let Some(e) = t.edge.filter(|e| failing.contains(e)) {
samples.entry(e).or_default().push(t.at);
}
}
}
unreachable!("the last round returns")
}
pub(super) fn heal_loosely(raw: &mut Raw) -> Option<Healed> {
let file = raw.clone();
let _ = attempt(raw, &HashMap::new(), &HashMap::new(), true);
movement(&file, raw, &BTreeSet::new())
}
pub(super) struct Tolerated {
pub ranges: Vec<(f64, f64)>,
pub vertices: Vec<f64>,
pub edges: Vec<f64>,
}
const GAP_MARGIN: f64 = 1.5;
fn file_range(raw: &Raw, e: usize) -> Option<(f64, f64)> {
let edge = &raw.edges[e];
let c = &edge.curve;
if let Some(r) = range_of(raw, e) {
return Some(r);
}
let (t0, t1) = (
param_of(c, raw.points[edge.start]),
param_of(c, raw.points[edge.end]),
);
let r = match c.period() {
Some(p) if edge.start == edge.end => (t0, t0 + p),
Some(p) => (t0, t0 + (t1 - t0).rem_euclid(p)),
None if edge.start == edge.end => c.domain(),
None => (t0.min(t1), t0.max(t1)),
};
(r.0.is_finite() && r.1.is_finite() && r.1 > r.0).then_some(r)
}
fn curve_gap(c: &Curve, r: (f64, f64), s: &Surface) -> f64 {
let mut ts = sample_params(c, r, 8);
ts.extend((1..64).map(|k| r.0 + (r.1 - r.0) * k as f64 / 64.0));
ts.sort_by(f64::total_cmp);
ts.dedup();
let mid = ts.len() / 2;
let start = s.project(c.eval(ts[mid]));
let mut worst: f64 = 0.0;
for half in [&ts[mid..], &ts[..=mid]] {
let mut hint = start;
let walk: Vec<f64> = if std::ptr::eq(half.as_ptr(), ts[mid..].as_ptr()) {
half.to_vec()
} else {
half.iter().rev().copied().collect()
};
for t in walk {
let p = c.eval(t);
hint = s.project_near(p, hint);
let d = s.eval(hint.x, hint.y).dist(p);
let d = if d > tol::LINEAR {
d.min(surface_gap(s, p))
} else {
d
};
worst = worst.max(d);
}
}
worst
}
fn midway(raw: &Raw, e: usize, r: (f64, f64)) -> Option<Curve> {
let edge = &raw.edges[e];
let mut faces = edge.faces.clone();
faces.sort_unstable();
faces.dedup();
let [fa, fb] = faces.as_slice() else {
return None;
};
let (a, b) = (&raw.faces[*fa].surface, &raw.faces[*fb].surface);
let closed = edge.start == edge.end;
let mut ts = sample_params(&edge.curve, r, 8);
ts.sort_by(f64::total_cmp);
ts.dedup_by(|x, y| (*x - *y).abs() <= 1e-9 * (r.1 - r.0));
if ts.len() < 2 {
return None;
}
let last = ts.len() - 1;
let mut pts: Vec<Point3> = ts
.iter()
.enumerate()
.map(|(i, &t)| match i {
0 => raw.points[edge.start],
i if i == last => raw.points[edge.end],
_ => {
let mut p = edge.curve.eval(t);
for _ in 0..50 {
let (ua, ub) = (a.project(p), b.project(p));
let (qa, qb) = (a.eval(ua.x, ua.y), b.eval(ub.x, ub.y));
let next = qa + (qb - qa) * 0.5;
let done = next.dist(p) <= 1e-12;
p = next;
if done {
break;
}
}
p
}
})
.collect();
let spline = if closed {
pts.pop();
BSpline::interpolate_periodic(&pts)
} else {
BSpline::interpolate(&pts)
};
spline.ok().map(Curve::BSpline)
}
const MAX_SHARE: f64 = 0.25;
fn edge_length(c: &Curve, r: (f64, f64)) -> f64 {
let at = |k: usize| c.eval(r.0 + (r.1 - r.0) * k as f64 / 32.0);
(0..32).map(|k| at(k).dist(at(k + 1))).sum()
}
pub(super) fn tolerate(
raw: &mut Raw,
stated: Option<f64>,
) -> std::result::Result<Tolerated, String> {
let mut ranges = Vec::with_capacity(raw.edges.len());
let mut edges = Vec::with_capacity(raw.edges.len());
let mut vertices = vec![tol::LINEAR; raw.points.len()];
let mut shortest = vec![f64::INFINITY; raw.points.len()];
let widened = |gap: f64| {
if gap <= tol::LINEAR {
tol::LINEAR
} else {
GAP_MARGIN * gap
}
};
for e in 0..raw.edges.len() {
let Some(mut r) = file_range(raw, e) else {
return Err(format!(
"edge #{} has no stretch between its vertices",
raw.edges[e].id
));
};
let mut faces = raw.edges[e].faces.clone();
faces.sort_unstable();
faces.dedup();
let gap_of = |c: &Curve, r: (f64, f64)| {
faces
.iter()
.map(|&f| curve_gap(c, r, &raw.faces[f].surface))
.fold(0.0, f64::max)
};
let mut gap = gap_of(&raw.edges[e].curve, r);
if gap > stated.unwrap_or(tol::LINEAR)
&& let Some(c) = midway(raw, e, r)
{
let (rm, gm) = (c.domain(), gap_of(&c, c.domain()));
if gm < gap {
(r, gap) = (rm, gm);
raw.edges[e].curve = c;
}
}
let edge = &raw.edges[e];
let length = edge_length(&edge.curve, r);
let t = widened(gap);
if t > tol::LINEAR && t > MAX_SHARE * length {
return Err(format!(
"edge #{} misses its faces by {gap:.1e} mm, too far for an edge {length:.1e} mm long",
edge.id
));
}
for (v, at) in [(edge.start, r.0), (edge.end, r.1)] {
let p = raw.points[v];
let far = faces
.iter()
.map(|&f| surface_gap(&raw.faces[f].surface, p))
.fold(edge.curve.eval(at).dist(p), f64::max);
vertices[v] = vertices[v].max(t).max(widened(far));
shortest[v] = shortest[v].min(length);
}
ranges.push(r);
edges.push(t);
}
for (v, &t) in vertices.iter().enumerate() {
if t > tol::LINEAR && t > MAX_SHARE * shortest[v] {
return Err(format!(
"vertex #{} lies {:.1e} mm off its edges and faces, too far for an edge {:.1e} mm \
long that ends at it",
raw.vertex_ids[v],
t / GAP_MARGIN,
shortest[v]
));
}
}
Ok(Tolerated {
ranges,
vertices,
edges,
})
}