use std::f64::consts::TAU;
use super::hulls;
use crate::{
geom::{
Bezier, Circle, Curve, Cylinder, Extrusion, Line, NurbsSurface, Revolution, Ruled, Surface,
Torus,
},
math::{Aabb, Point3, Vec2, Vec3},
numeric, tol,
};
pub(crate) fn signed_distance(s: &Surface, p: Point3) -> f64 {
match s {
Surface::Plane(pl) => (p - pl.frame.origin).dot(pl.frame.z),
Surface::Cylinder(c) => {
let l = c.frame.to_local(p);
l.x.hypot(l.y) - c.radius
}
Surface::Sphere(sp) => (p - sp.frame.origin).norm() - sp.radius,
Surface::Cone(c) => {
let l = c.frame.to_local(p);
let (sa, ca) = c.half_angle.sin_cos();
(l.x.hypot(l.y) - c.radius) * ca - l.z * sa
}
Surface::Torus(t) => {
let l = t.frame.to_local(p);
(l.x.hypot(l.y) - t.major).hypot(l.z) - t.minor
}
_ => {
let uv = s.project(p);
(p - s.eval(uv.x, uv.y)).dot(s.normal(uv.x, uv.y))
}
}
}
pub(crate) struct Tracker<'a> {
s: &'a Surface,
last: Option<(Point3, Vec2, f64)>,
}
impl<'a> Tracker<'a> {
pub(crate) fn new(s: &'a Surface) -> Tracker<'a> {
Tracker { s, last: None }
}
pub(crate) fn at(&mut self, p: Point3) -> f64 {
let Surface::Nurbs(n) = self.s else {
return signed_distance(self.s, p);
};
let uv = match self.last {
Some((q, uv, d)) if d.abs() + q.dist(p) <= n.near_radius() => n.project_near(p, uv),
_ => n.project(p),
};
let d = (p - n.eval(uv.x, uv.y)).dot(self.s.normal(uv.x, uv.y));
self.last = Some((p, uv, d));
d
}
}
#[derive(Clone, Debug, Default, PartialEq)]
pub(crate) struct Hits {
pub ts: Vec<f64>,
pub on_surface: bool,
}
fn speed(c: &Curve, t: f64) -> f64 {
c.d1(t).1.norm()
}
fn in_range(c: &Curve, t: f64, range: (f64, f64)) -> Option<f64> {
let pt = tol::param(speed(c, t));
if t >= range.0 - pt && t <= range.1 + pt {
Some(t.clamp(range.0, range.1))
} else {
None
}
}
fn angle_in(t: f64, range: (f64, f64)) -> Option<f64> {
let k = ((range.0 - t) / TAU).ceil();
let a = t + k * TAU;
let eps = 1e-14 * (1.0 + a.abs());
if a <= range.1 + eps {
Some(a.min(range.1))
} else if (t + (k - 1.0) * TAU - range.0).abs() <= eps {
Some(range.0)
} else {
None
}
}
fn trig_roots(a: f64, b: f64, c: f64, range: (f64, f64)) -> Hits {
let r = b.hypot(c);
if r <= tol::LINEAR {
return Hits {
ts: Vec::new(),
on_surface: a.abs() <= tol::LINEAR,
};
}
let phi = c.atan2(b);
let mut ts = Vec::new();
if a.abs() >= r - tol::LINEAR {
if a.abs() - r <= tol::LINEAR {
ts.push(if a < 0.0 { phi } else { phi + TAU / 2.0 });
}
} else {
let w = (-a / r).acos();
ts.push(phi + w);
ts.push(phi - w);
}
Hits {
ts: ts.into_iter().filter_map(|t| angle_in(t, range)).collect(),
on_surface: false,
}
}
fn line_cylinder(o: Point3, d: Vec3, cyl: &Cylinder) -> Hits {
let lo = cyl.frame.to_local(o);
let ld = cyl.frame.dir_to_local(d);
let a = ld.x * ld.x + ld.y * ld.y;
if a.sqrt() <= tol::ANGULAR {
return Hits {
ts: Vec::new(),
on_surface: (lo.x.hypot(lo.y) - cyl.radius).abs() <= tol::LINEAR,
};
}
let t_near = -(lo.x * ld.x + lo.y * ld.y) / a;
let m = (lo.x + t_near * ld.x).hypot(lo.y + t_near * ld.y);
let r = cyl.radius;
let ts = if m > r + tol::LINEAR {
Vec::new()
} else if m >= r - tol::LINEAR {
vec![t_near]
} else {
let h = ((r - m) * (r + m) / a).sqrt();
vec![t_near - h, t_near + h]
};
Hits {
ts,
on_surface: false,
}
}
fn line_quadric(o: Point3, d: Vec3, s: &Surface, qa: f64, qb: f64, qc: f64) -> Hits {
let at = |t: f64| signed_distance(s, o + d * t).abs();
if qa.abs() < 1e-300 {
if qb.abs() < 1e-300 {
return Hits {
ts: Vec::new(),
on_surface: at(0.0) <= tol::LINEAR,
};
}
return Hits {
ts: vec![-qc / qb],
on_surface: false,
};
}
let t_near = -qb / (2.0 * qa);
let disc = qb * qb - 4.0 * qa * qc;
let ts = if disc <= 0.0 {
if at(t_near) <= tol::LINEAR {
vec![t_near]
} else {
Vec::new()
}
} else {
let q = -0.5 * (qb + qb.signum() * disc.sqrt());
let (mut t1, mut t2) = (q / qa, qc / q);
if t1 > t2 {
std::mem::swap(&mut t1, &mut t2);
}
if at(t_near) <= tol::LINEAR {
vec![t_near]
} else {
vec![t1, t2]
}
};
Hits {
ts,
on_surface: false,
}
}
fn minimise(f: &mut impl FnMut(f64) -> f64, mut a: f64, mut b: f64) -> f64 {
let g = 0.5 * (5f64.sqrt() - 1.0);
let mut c = b - g * (b - a);
let mut d = a + g * (b - a);
let (mut fc, mut fd) = (f(c), f(d));
for _ in 0..200 {
if (b - a).abs() <= 1e-15 * (1.0 + a.abs()) {
break;
}
if fc < fd {
b = d;
d = c;
fd = fc;
c = b - g * (b - a);
fc = f(c);
} else {
a = c;
c = d;
fc = fd;
d = a + g * (b - a);
fd = f(d);
}
}
0.5 * (a + b)
}
fn stationary(f: &mut impl FnMut(f64) -> f64, a: f64, b: f64) -> Option<f64> {
let h = 1e-3 * (b - a);
let mut slope = |t: f64| f(t + h) - f(t - h);
let (sa, sb) = (slope(a + h), slope(b - h));
((sa < 0.0) != (sb < 0.0) && sa != 0.0 && sb != 0.0)
.then(|| numeric::bisect(&mut slope, a + h, b - h))
}
const TOUCH: f64 = tol::LINEAR;
fn settle(f: &mut impl FnMut(f64) -> f64, t: f64, w: f64, (lo, hi): (f64, f64)) -> f64 {
let (fa, fb) = (f(t - w), f(t + w));
if (fa < 0.0) != (fb < 0.0) || fa.abs().min(fb.abs()) <= tol::LINEAR {
return t;
}
match stationary(f, t - w, t + w) {
Some(s) if f(s).abs() <= TOUCH => s.clamp(lo, hi),
_ => t,
}
}
fn sampled_roots(f: &mut impl FnMut(f64) -> f64, cuts: &[f64], n: usize) -> (Vec<f64>, bool) {
let mut ts = Vec::new();
let mut samples: Vec<(f64, f64)> = Vec::new();
for w in cuts.windows(2) {
for i in 0..n {
let t = w[0] + (w[1] - w[0]) * i as f64 / n as f64;
samples.push((t, f(t)));
}
}
let last = cuts[cuts.len() - 1];
samples.push((last, f(last)));
if samples.iter().all(|s| s.1.abs() <= tol::LINEAR) {
return (Vec::new(), true);
}
for k in 0..samples.len() {
let (t, v) = samples[k];
if v == 0.0 {
ts.push(t);
continue;
}
if k + 1 < samples.len() {
let (t2, v2) = samples[k + 1];
if v2 != 0.0 && (v < 0.0) != (v2 < 0.0) {
let r = numeric::bisect(f, t, t2);
ts.push(settle(f, r, t2 - t, (cuts[0], last)));
}
}
if k > 0 && k + 1 < samples.len() {
let (tp, vp) = samples[k - 1];
let (tn, vn) = samples[k + 1];
let same = (vp < 0.0) == (v < 0.0) && (vn < 0.0) == (v < 0.0);
if same && v.abs() <= vp.abs() && v.abs() <= vn.abs() {
let s = v.signum();
let tm = minimise(&mut |x: f64| s * f(x), tp, tn);
let fm = f(tm);
if fm.abs() <= tol::LINEAR {
ts.push(tm);
} else if (fm < 0.0) != (v < 0.0) {
ts.push(numeric::bisect(f, tp, tm));
ts.push(numeric::bisect(f, tm, tn));
}
}
}
}
ts.sort_by(f64::total_cmp);
ts.dedup_by(|a, b| (*a - *b).abs() <= 1e-12 * (1.0 + a.abs().max(b.abs())));
(ts, false)
}
fn numeric_hits(c: &Curve, range: (f64, f64), s: &Surface) -> Hits {
let mut cuts = vec![range.0];
cuts.extend(c.breakpoints(range.0, range.1));
cuts.push(range.1);
let n = if cuts.len() > 2 { 12 } else { 96 };
let mut track = Tracker::new(s);
let mut f = |t: f64| track.at(c.eval(t));
let Surface::Nurbs(ns) = s else {
let (ts, on) = sampled_roots(&mut f, &cuts, n);
return Hits { ts, on_surface: on };
};
let samples: Vec<f64> = cuts
.windows(2)
.flat_map(|w| (0..n).map(move |i| w[0] + (w[1] - w[0]) * i as f64 / n as f64))
.chain(std::iter::once(range.1))
.collect();
let mut hull = Aabb::EMPTY;
for q in ns.patches() {
hull.union(&q.bbox);
}
let meets = |a: &Aabb, b: &Aabb| {
(0..3).all(|k| a.min[k] <= b.max[k] + tol::LINEAR && b.min[k] <= a.max[k] + tol::LINEAR)
};
let near = |t0: f64, t1: f64| {
let bb = c.bbox(t0, t1);
meets(&bb, &hull) && ns.patches().iter().any(|q| meets(&bb, &q.bbox))
};
let (mut ts, mut on) = (Vec::new(), true);
let mut run: Vec<f64> = Vec::new();
for w in samples.windows(2) {
if near(w[0], w[1]) {
if run.is_empty() {
run.push(w[0]);
}
run.push(w[1]);
continue;
}
on = false;
if !run.is_empty() {
ts.extend(sampled_roots(&mut f, &run, 1).0);
run.clear();
}
}
if !run.is_empty() {
let (r, all) = sampled_roots(&mut f, &run, 1);
ts.extend(r);
on &= all;
}
if on {
return Hits {
ts: Vec::new(),
on_surface: true,
};
}
Hits {
ts,
on_surface: false,
}
}
pub(crate) fn curve_surface(c: &Curve, range: (f64, f64), s: &Surface) -> Hits {
let raw = match (c, s) {
(Curve::Line(l), Surface::Plane(p)) => {
let dn = l.dir.dot(p.frame.z);
let h = (l.origin - p.frame.origin).dot(p.frame.z);
if dn.abs() <= tol::ANGULAR {
Hits {
ts: Vec::new(),
on_surface: h.abs() <= tol::LINEAR,
}
} else {
Hits {
ts: vec![-h / dn],
on_surface: false,
}
}
}
(Curve::Line(l), Surface::Cylinder(cyl)) => line_cylinder(l.origin, l.dir, cyl),
(Curve::Line(l), Surface::Torus(t)) => line_torus(l.origin, l.dir, t, range),
(Curve::Circle(ci), Surface::Sphere(sp)) => return circle_sphere(ci, sp, range),
(Curve::Line(l), Surface::Extrusion(e)) if l.dir.cross(e.dir).norm() <= tol::ANGULAR => {
Hits {
ts: Vec::new(),
on_surface: signed_distance(s, l.origin).abs() <= tol::LINEAR,
}
}
(Curve::Line(l), Surface::Extrusion(e)) => line_extrusion(l.origin, l.dir, e),
(Curve::Line(l), Surface::Revolution(r)) => match line_revolution(l.origin, l.dir, r) {
Some(hits) => hits,
None => return numeric_hits(c, range, s),
},
(Curve::Line(l), Surface::Ruled(r)) => match line_ruled(l.origin, l.dir, r) {
Some(hits) => hits,
None => return numeric_hits(c, range, s),
},
(Curve::Line(l), Surface::Nurbs(ns)) => match line_spline(l.origin, l.dir, ns, range) {
Some(hits) => hits,
None => return numeric_hits(c, range, s),
},
(Curve::Line(l), Surface::Sphere(sp)) => {
let oc = l.origin - sp.frame.origin;
let b = oc.dot(l.dir);
let c0 = oc.norm2() - sp.radius * sp.radius;
line_quadric(l.origin, l.dir, s, 1.0, 2.0 * b, c0)
}
(Curve::Line(l), Surface::Cone(cone)) if cone.half_angle.cos().abs() > 1e-9 => {
let lo = cone.frame.to_local(l.origin);
let ld = cone.frame.dir_to_local(l.dir);
let k = cone.half_angle.tan();
let r0 = cone.radius + k * lo.z;
let qa = ld.x * ld.x + ld.y * ld.y - k * k * ld.z * ld.z;
let qb = 2.0 * (lo.x * ld.x + lo.y * ld.y - k * r0 * ld.z);
let qc = lo.x * lo.x + lo.y * lo.y - r0 * r0;
line_quadric(l.origin, l.dir, s, qa, qb, qc)
}
(Curve::Circle(ci), Surface::Plane(p)) => {
let n = p.frame.z;
let a = (ci.frame.origin - p.frame.origin).dot(n);
return trig_roots(
a,
ci.radius * ci.frame.x.dot(n),
ci.radius * ci.frame.y.dot(n),
range,
);
}
(Curve::Ellipse(e), Surface::Plane(p)) => {
let n = p.frame.z;
let a = (e.frame.origin - p.frame.origin).dot(n);
return trig_roots(
a,
e.major * e.frame.x.dot(n),
e.minor * e.frame.y.dot(n),
range,
);
}
(Curve::Circle(ci), Surface::Cylinder(cyl))
if ci.frame.z.cross(cyl.frame.z).norm() <= tol::ANGULAR =>
{
return circle_parallel_cylinder(ci, cyl, range);
}
_ => return numeric_hits(c, range, s),
};
if raw.on_surface {
return raw;
}
Hits {
ts: raw
.ts
.into_iter()
.filter_map(|t| in_range(c, t, range))
.collect(),
on_surface: false,
}
}
fn circle_parallel_cylinder(ci: &Circle, cyl: &Cylinder, range: (f64, f64)) -> Hits {
let l = ci.frame.to_local(cyl.frame.origin);
coplanar_circles(ci, Vec2::new(l.x, l.y), cyl.radius, range)
}
fn coplanar_circles(ci: &Circle, centre: Vec2, big: f64, range: (f64, f64)) -> Hits {
let d = centre.x.hypot(centre.y);
let r = ci.radius;
if d <= tol::LINEAR {
return Hits {
ts: Vec::new(),
on_surface: (r - big).abs() <= tol::LINEAR,
};
}
if d > r + big + tol::LINEAR || d < (r - big).abs() - tol::LINEAR {
return Hits::default();
}
let toward = centre.y.atan2(centre.x);
let x = (d * d + r * r - big * big) / (2.0 * d);
let touching =
(d - (r + big)).abs() <= tol::LINEAR || (d - (r - big).abs()).abs() <= tol::LINEAR;
let angles = if touching {
vec![if x >= 0.0 { toward } else { toward + TAU / 2.0 }]
} else {
let a = (x / r).clamp(-1.0, 1.0).acos();
vec![toward - a, toward + a]
};
Hits {
ts: angles
.into_iter()
.filter_map(|a| angle_in(a, range))
.collect(),
on_surface: false,
}
}
fn poly(c: &[f64], t: f64) -> f64 {
c.iter().rev().fold(0.0, |acc, &k| acc * t + k)
}
fn derivative(c: &[f64]) -> Vec<f64> {
c.iter()
.enumerate()
.skip(1)
.map(|(i, &k)| k * i as f64)
.collect()
}
fn stationary_points(c: &[f64], lo: f64, hi: f64) -> Vec<f64> {
let d = derivative(c);
if d.len() < 2 {
return Vec::new();
}
let mut knots = vec![lo];
knots.extend(stationary_points(&d, lo, hi));
knots.push(hi);
let mut out = Vec::new();
for w in knots.windows(2) {
let (a, b) = (poly(&d, w[0]), poly(&d, w[1]));
if a == 0.0 && w[0] > lo {
out.push(w[0]);
} else if a != 0.0 && b != 0.0 && (a < 0.0) != (b < 0.0) {
out.push(numeric::bisect(&mut |t| poly(&d, t), w[0], w[1]));
}
}
out
}
fn roots_between(f: &mut impl FnMut(f64) -> f64, knots: &[f64]) -> Vec<f64> {
let side = |v: f64| {
if v > tol::LINEAR {
1
} else if v < -tol::LINEAR {
-1
} else {
0
}
};
let signs: Vec<i8> = knots.iter().map(|&t| side(f(t))).collect();
let mut ts = Vec::new();
for (i, &t) in knots.iter().enumerate() {
if signs[i] == 0 {
ts.push(t);
}
if i + 1 < knots.len() && signs[i] * signs[i + 1] < 0 {
ts.push(numeric::bisect(f, t, knots[i + 1]));
}
}
ts
}
fn fitted(values: &[f64]) -> Option<Vec<f64>> {
let n = values.len();
let mut m: Vec<Vec<f64>> = (0..n)
.map(|j| {
let s = j as f64 / (n - 1).max(1) as f64;
let mut row: Vec<f64> = (0..n).map(|k| s.powi(k as i32)).collect();
row.push(values[j]);
row
})
.collect();
for col in 0..n {
let pivot = (col..n).max_by(|&a, &b| m[a][col].abs().total_cmp(&m[b][col].abs()))?;
if m[pivot][col].abs() < 1e-300 {
return None;
}
m.swap(col, pivot);
let by = m[col].clone();
for (row, values) in m.iter_mut().enumerate() {
if row != col {
let f = values[col] / by[col];
for (x, p) in values.iter_mut().zip(&by).skip(col) {
*x -= f * p;
}
}
}
}
Some((0..n).map(|i| m[i][n] / m[i][i]).collect())
}
struct Piece<'a> {
param: Box<dyn Fn(f64) -> f64 + 'a>,
scale: Box<dyn Fn(f64) -> f64 + 'a>,
degree: usize,
}
fn pieces<'a>(c: &'a Curve, (lo, hi): (f64, f64)) -> Option<Vec<Piece<'a>>> {
let spans = |degree: usize, weight: Option<&'a crate::geom::NurbsCurve>| {
let mut cuts = vec![lo];
cuts.extend(c.breakpoints(lo, hi));
cuts.push(hi);
cuts.windows(2)
.map(|w| {
let (a, b) = (w[0], w[1]);
let param = move |s: f64| a + (b - a) * s;
Piece {
param: Box::new(param),
scale: match weight {
Some(nc) => Box::new(move |s| nc.weight(param(s))),
None => Box::new(|_| 1.0),
},
degree,
}
})
.collect::<Vec<_>>()
};
match c {
Curve::Line(_) | Curve::BSpline(_) | Curve::Nurbs(_)
if !(lo.is_finite() && hi.is_finite()) =>
{
None
}
Curve::Line(_) => Some(spans(1, None)),
Curve::BSpline(b) => Some(spans(b.degree(), None)),
Curve::Nurbs(nc) => Some(spans(nc.degree(), Some(nc))),
Curve::Circle(_) | Curve::Ellipse(_) => Some(
[TAU / 4.0, 3.0 * TAU / 4.0]
.into_iter()
.map(|middle| Piece {
param: Box::new(move |s| middle + 2.0 * (2.0 * s - 1.0).atan()),
scale: Box::new(|s| 1.0 + (2.0 * s - 1.0).powi(2)),
degree: 2,
})
.collect(),
),
Curve::Intersection(_) => None,
}
}
fn piece_roots(
pieces: &[Piece],
order: usize,
raw: &dyn Fn(f64) -> f64,
mm: &mut impl FnMut(f64) -> f64,
) -> (Vec<f64>, bool) {
let (mut roots, mut flat) = (Vec::new(), true);
for piece in pieces {
let n = piece.degree * order;
let at = |j: usize| j as f64 / n.max(1) as f64;
let values: Vec<f64> = (0..=n)
.map(|j| {
let s = at(j);
raw((piece.param)(s)) * (piece.scale)(s).powi(order as i32)
})
.collect();
flat &= (0..=n).all(|j| mm((piece.param)(at(j))).abs() <= tol::LINEAR);
let mut knots = vec![(piece.param)(0.0)];
if let Some(coefficients) = fitted(&values) {
knots.extend(
stationary_points(&coefficients, 0.0, 1.0)
.into_iter()
.map(|s| (piece.param)(s)),
);
}
knots.push((piece.param)(1.0));
roots.extend(roots_between(mm, &knots));
}
(roots, flat)
}
fn in_order(mut ts: Vec<f64>) -> Vec<f64> {
ts.sort_by(f64::total_cmp);
ts.dedup_by(|a, b| (*a - *b).abs() <= 1e-12 * (1.0 + a.abs().max(b.abs())));
ts
}
fn line_extrusion(o: Point3, d: Vec3, e: &Extrusion) -> Hits {
let across = d - e.dir * d.dot(e.dir);
let Some(n) = e.dir.cross(across).unit() else {
return Hits::default();
};
let c = &e.curve;
let height = |u: f64| n.dot(c.eval(u) - o);
let (lo, hi) = c.domain();
let on_profile = match c {
Curve::Circle(ci) => trig_roots(
n.dot(ci.frame.origin - o),
ci.radius * n.dot(ci.frame.x),
ci.radius * n.dot(ci.frame.y),
(0.0, TAU),
),
Curve::Ellipse(el) => trig_roots(
n.dot(el.frame.origin - o),
el.major * n.dot(el.frame.x),
el.minor * n.dot(el.frame.y),
(0.0, TAU),
),
Curve::Line(l) => {
let slope = n.dot(l.dir);
if slope.abs() <= tol::ANGULAR {
Hits {
ts: Vec::new(),
on_surface: n.dot(l.origin - o).abs() <= tol::LINEAR,
}
} else {
Hits {
ts: vec![-n.dot(l.origin - o) / slope],
on_surface: false,
}
}
}
_ => match pieces(c, (lo, hi)) {
Some(pieces) => {
let (ts, flat) = piece_roots(&pieces, 1, &height, &mut |u| height(u));
Hits {
ts: if flat { Vec::new() } else { ts },
on_surface: flat,
}
}
None => {
let mut cuts = vec![lo];
cuts.extend(c.breakpoints(lo, hi));
cuts.push(hi);
let (ts, on) = sampled_roots(&mut |u| height(u), &cuts, 24);
Hits { ts, on_surface: on }
}
},
};
if on_profile.on_surface {
return on_profile;
}
let ts = on_profile
.ts
.into_iter()
.map(|u| (c.eval(u) - o).dot(across) / across.norm2())
.collect();
Hits {
ts: in_order(ts),
on_surface: false,
}
}
fn line_revolution(o: Point3, d: Vec3, r: &Revolution) -> Option<Hits> {
let c = &r.curve;
let pieces = pieces(c, c.domain())?;
let rel = o - r.origin;
let (z0, dz) = (rel.dot(r.axis), d.dot(r.axis));
let (a, b, c0) = (
1.0 - dz * dz,
2.0 * (rel.dot(d) - z0 * dz),
rel.norm2() - z0 * z0,
);
let ring = |v: f64| {
let q = c.eval(v) - r.origin;
let z = q.dot(r.axis);
(z, q.norm2() - z * z)
};
if dz.abs() > tol::ANGULAR {
let at = |v: f64| (ring(v).0 - z0) / dz;
let line2 = |t: f64| (a * t + b) * t + c0;
let raw = |v: f64| line2(at(v)) - ring(v).1;
let mut mm = |v: f64| line2(at(v)).max(0.0).sqrt() - ring(v).1.max(0.0).sqrt();
let (vs, flat) = piece_roots(&pieces, 2, &raw, &mut mm);
return Some(Hits {
ts: if flat {
Vec::new()
} else {
in_order(vs.into_iter().map(at).collect())
},
on_surface: flat,
});
}
let level = |v: f64| ring(v).0 - z0;
let (vs, flat) = piece_roots(&pieces, 1, &level, &mut |v| level(v));
if flat {
return Some(Hits {
ts: Vec::new(),
on_surface: true,
});
}
let mut ts = Vec::new();
for v in vs {
let radius = ring(v).1.max(0.0).sqrt();
let (near, at) = ((c0 - b * b / (4.0 * a)).max(0.0).sqrt(), -b / (2.0 * a));
if radius < near - tol::LINEAR {
continue;
}
let half = ((radius * radius - near * near).max(0.0) / a).sqrt();
if half <= tol::LINEAR {
ts.push(at);
} else {
ts.extend([at - half, at + half]);
}
}
Some(Hits {
ts: in_order(ts),
on_surface: false,
})
}
fn line_ruled(o: Point3, d: Vec3, r: &Ruled) -> Option<Hits> {
let poly = |c: &Curve| matches!(c, Curve::Line(_) | Curve::BSpline(_) | Curve::Nurbs(_));
if !poly(&r.a) || !poly(&r.b) {
return None;
}
let (pa, pb) = (pieces(&r.a, r.a_range)?, pieces(&r.b, r.b_range)?);
let on_a = |u: f64| r.a_range.0 + u * (r.a_range.1 - r.a_range.0);
let on_b = |u: f64| r.b_range.0 + u * (r.b_range.1 - r.b_range.0);
let back = |t: f64, (lo, hi): (f64, f64)| (t - lo) / (hi - lo);
let mut cuts: Vec<f64> = vec![0.0, 1.0];
cuts.extend(pa.iter().map(|p| back((p.param)(0.0), r.a_range)));
cuts.extend(pb.iter().map(|p| back((p.param)(0.0), r.b_range)));
cuts.retain(|u| (0.0..=1.0).contains(u));
cuts.sort_by(f64::total_cmp);
cuts.dedup_by(|x, y| (*x - *y).abs() <= 1e-12);
let weight = |c: &Curve, t: f64| match c {
Curve::Nurbs(nc) => nc.weight(t),
_ => 1.0,
};
let degree = pa[0].degree + pb[0].degree;
let both: Vec<Piece> = cuts
.windows(2)
.map(|w| {
let (lo, hi) = (w[0], w[1]);
let param = move |s: f64| lo + (hi - lo) * s;
Piece {
param: Box::new(param),
scale: Box::new(move |s| {
let u = param(s);
weight(&r.a, on_a(u)) * weight(&r.b, on_b(u))
}),
degree,
}
})
.collect();
let ruling = |u: f64| {
let foot = r.a.eval(on_a(u));
(foot, r.b.eval(on_b(u)) - foot)
};
let raw = |u: f64| {
let (foot, step) = ruling(u);
(foot - o).dot(step.cross(d))
};
let mut mm = |u: f64| {
let (foot, step) = ruling(u);
let span = step.cross(d);
let area = span.norm();
if area > 0.0 {
(foot - o).dot(span) / area
} else {
0.0
}
};
let (us, flat) = piece_roots(&both, 1, &raw, &mut mm);
if flat {
return Some(Hits {
ts: Vec::new(),
on_surface: true,
});
}
let ts = us
.into_iter()
.filter_map(|u| {
let (foot, step) = ruling(u);
let span = d.cross(step);
(span.norm2() > tol::ANGULAR * tol::ANGULAR * step.norm2())
.then(|| (foot - o).cross(step).dot(span) / span.norm2())
})
.collect();
Some(Hits {
ts: in_order(ts),
on_surface: false,
})
}
const SPLINE_RUN: usize = 64;
const SPLINE_PATCHES: usize = 20_000;
fn line_spline(o: Point3, d: Vec3, ns: &NurbsSurface, range: (f64, f64)) -> Option<Hits> {
let side = if d.x.abs() < 0.9 { Vec3::X } else { Vec3::Y };
let e1 = d.cross(side).unit()?;
let e2 = d.cross(e1);
let own = |q: [f64; 4]| -> [f64; 4] {
let rel = Vec3::new(q[0], q[1], q[2]) - o * q[3];
[rel.dot(e1), rel.dot(e2), rel.dot(d), q[3]]
};
let clear = |patch: &Bezier| {
let pts = patch.points();
let beyond = |f: &dyn Fn(&[f64; 4]) -> f64| pts.iter().all(|q| f(q) > 0.0);
(0..2).any(|c| {
beyond(&|q| q[c] - tol::LINEAR * q[3]) || beyond(&|q| -q[c] - tol::LINEAR * q[3])
}) || beyond(&|q| q[2] - (range.1 + tol::LINEAR) * q[3])
|| beyond(&|q| (range.0 - tol::LINEAR) * q[3] - q[2])
};
let mut open: Vec<Bezier> = ns
.beziers()
.iter()
.filter(|b| line_passes(o, d, &b.bbox(), range))
.map(|b| b.mapped(own))
.filter(|b| !clear(b))
.collect();
let mut ts: Vec<f64> = Vec::new();
let mut small: Vec<(f64, f64, Vec2)> = Vec::new();
let mut opened = 0;
while let Some(patch) = open.pop() {
opened += 1;
if opened > SPLINE_PATCHES {
return None;
}
if let Some(t) = only_crossing(&patch) {
if t >= range.0 - tol::LINEAR && t <= range.1 + tol::LINEAR {
ts.push(t);
}
continue;
}
let bb = patch.bbox();
let span = patch.hi - patch.lo;
let spent = span.x.abs().max(span.y.abs()) <= 1e-14;
if bb.diagonal() <= tol::LINEAR || spent {
small.push((bb.min.z, bb.max.z, (patch.lo + patch.hi) * 0.5));
if small.len() > SPLINE_RUN {
return None;
}
continue;
}
open.extend(
patch
.halves(patch.longer_in_u())
.into_iter()
.filter(|h| !clear(h)),
);
}
small.sort_by(|x, y| x.0.total_cmp(&y.0));
let mut stretches: Vec<(f64, f64, Vec2)> = Vec::new();
for (a, b, uv) in small {
match stretches.last_mut() {
Some(last) if a <= last.1 + tol::LINEAR => last.1 = last.1.max(b),
_ => stretches.push((a, b, uv)),
}
}
for (a, b, hint) in stretches {
let mut last = hint;
let mut height = |t: f64| {
let q = o + d * t;
let uv = ns.project_near(q, last);
last = uv;
let (at, su, sv) = ns.d1(uv.x, uv.y);
match su.cross(sv).unit() {
Some(n) => (q - at).dot(n),
None => q.dist(at),
}
};
let (a, b) = (
(a - tol::LINEAR).max(range.0),
(b + tol::LINEAR).min(range.1),
);
let steps = (((b - a) / tol::LINEAR).ceil() as usize).clamp(2, 32);
ts.extend(sampled_roots(&mut height, &[a, b], steps).0);
}
ts.sort_by(f64::total_cmp);
ts.dedup_by(|a, b| (*a - *b).abs() <= 1e-3 * tol::LINEAR);
Some(Hits {
ts,
on_surface: false,
})
}
fn line_passes(o: Point3, d: Vec3, bb: &Aabb, range: (f64, f64)) -> bool {
let (mut lo, mut hi) = range;
for k in 0..3 {
let (mn, mx) = (bb.min[k] - tol::LINEAR, bb.max[k] + tol::LINEAR);
if d[k].abs() < 1e-300 {
if o[k] < mn || o[k] > mx {
return false;
}
continue;
}
let (a, b) = ((mn - o[k]) / d[k], (mx - o[k]) / d[k]);
lo = lo.max(a.min(b));
hi = hi.min(a.max(b));
}
hi >= lo
}
fn only_crossing(patch: &Bezier) -> Option<f64> {
let slopes = [patch.slopes(0), patch.slopes(1)];
let mid = |r: (f64, f64)| 0.5 * (r.0 + r.1);
let m = [
[mid(slopes[0][0]), mid(slopes[0][1])],
[mid(slopes[1][0]), mid(slopes[1][1])],
];
let det = m[0][0] * m[1][1] - m[0][1] * m[1][0];
let size = m[0][0].abs().max(m[0][1].abs()) * m[1][0].abs().max(m[1][1].abs());
if det.abs() <= 1e-9 * size || size == 0.0 {
return None;
}
let turn = [
[m[1][1] / det, -m[0][1] / det],
[-m[1][0] / det, m[0][0] / det],
];
let mixed = |x: f64, a: (f64, f64), y: f64, b: (f64, f64)| {
let part = |k: f64, r: (f64, f64)| (k * r.0).min(k * r.1)..=(k * r.0).max(k * r.1);
let (p, q) = (part(x, a), part(y, b));
(p.start() + q.start(), p.end() + q.end())
};
let turned =
|row: usize, col: usize| mixed(turn[row][0], slopes[0][col], turn[row][1], slopes[1][col]);
let (a, b, c, e) = (turned(0, 0), turned(0, 1), turned(1, 0), turned(1, 1));
let off = b.0.abs().max(b.1.abs()) + c.0.abs().max(c.1.abs());
if !(a.0 > 0.0 && e.0 > 0.0 && off * off < 4.0 * a.0 * e.0) {
return None;
}
let (mut s, mut t) = (0.5, 0.5);
for _ in 0..40 {
let [q, qs, qt] = patch.at(s, t);
let (ds, dt) = numeric::solve2(qs[0], qt[0], qs[1], qt[1], -q[0], -q[1])?;
(s, t) = (s + ds, t + dt);
if !(-0.5..=1.5).contains(&s) || !(-0.5..=1.5).contains(&t) {
return None;
}
if ds.abs().max(dt.abs()) <= 1e-14 {
break;
}
}
let inside = |x: f64| (-1e-9..=1.0 + 1e-9).contains(&x);
if !inside(s) || !inside(t) {
return None;
}
let [q, ..] = patch.at(s.clamp(0.0, 1.0), t.clamp(0.0, 1.0));
let off = q[0].hypot(q[1]) / q[3];
(off <= 1e-3 * tol::LINEAR * (1.0 + (q[2] / q[3]).abs())).then_some(q[2] / q[3])
}
fn line_torus(o: Point3, d: Vec3, t: &Torus, range: (f64, f64)) -> Hits {
let (lo, ld) = (t.frame.to_local(o), t.frame.dir_to_local(d));
let (big, small) = (t.major, t.minor);
let (b, c) = (lo.dot(ld), lo.dot(lo) - (big + small).powi(2));
let disc = b * b - c;
if disc < 0.0 {
return Hits::default();
}
let (t0, t1) = (
(-b - disc.sqrt()).max(range.0),
(-b + disc.sqrt()).min(range.1),
);
if t0 > t1 {
return Hits::default();
}
let k = big * big - small * small;
let sq = [lo.dot(lo) + k, 2.0 * b, 1.0];
let rho = [
lo.x * lo.x + lo.y * lo.y,
2.0 * (lo.x * ld.x + lo.y * ld.y),
ld.x * ld.x + ld.y * ld.y,
];
let mut q = [0.0; 5];
for i in 0..3 {
for j in 0..3 {
q[i + j] += sq[i] * sq[j];
}
q[i] -= 4.0 * big * big * rho[i];
}
let mut knots = vec![t0];
knots.extend(stationary_points(&q, t0, t1));
knots.push(t1);
let mut f = |s: f64| {
let p = lo + ld * s;
let rho = p.x.hypot(p.y);
let (near, far) = (
(rho - big).hypot(p.z) - small,
(rho + big).hypot(p.z) - small,
);
if near.abs() <= far.abs() {
near * far.signum()
} else {
far * near.signum()
}
};
Hits {
ts: roots_between(&mut f, &knots),
on_surface: false,
}
}
fn circle_sphere(ci: &Circle, sp: &crate::geom::Sphere, range: (f64, f64)) -> Hits {
let l = ci.frame.to_local(sp.frame.origin);
let rho2 = (sp.radius - l.z.abs()) * (sp.radius + l.z.abs());
if rho2 < 0.0 {
let gap = l.z.abs() - sp.radius;
let d = l.x.hypot(l.y);
return if gap <= tol::LINEAR && (d - ci.radius).abs() <= tol::LINEAR {
Hits {
ts: angle_in(l.y.atan2(l.x), range).into_iter().collect(),
on_surface: false,
}
} else {
Hits::default()
};
}
coplanar_circles(ci, Vec2::new(l.x, l.y), rho2.sqrt(), range)
}
fn conic_plane(c: &Curve) -> Option<crate::math::Frame> {
match c {
Curve::Circle(ci) => Some(ci.frame),
Curve::Ellipse(e) => Some(e.frame),
_ => None,
}
}
pub(crate) fn curve_distance(c: &Curve, range: (f64, f64), p: Point3) -> (f64, f64) {
let t = c.project(p, range.0, range.1);
(c.eval(t).dist(p), t)
}
pub(crate) fn within(c: &Curve, range: (f64, f64), p: Point3, reach: f64) -> bool {
if let Some(pieces) = hulls::pieces(c, range) {
let mut bb = Aabb::EMPTY;
bb.add(p);
if pieces.iter().all(|q| hulls::gap(&q.2, &bb) > reach) {
return false;
}
}
curve_distance(c, range, p).0 <= reach
}
pub(crate) const GRAZE_GAP: f64 = 1e-5;
pub(crate) fn grazing(c1: &Curve, r1: (f64, f64), c2: &Curve, r2: (f64, f64)) -> Vec<Point3> {
const SAMPLES: usize = 64;
let gap = |t: f64| curve_distance(c2, r2, c1.eval(t)).0;
let ts: Vec<f64> = (0..=SAMPLES)
.map(|k| r1.0 + (r1.1 - r1.0) * k as f64 / SAMPLES as f64)
.collect();
let reach = hulls::near(c1, r1, c2, r2, GRAZE_GAP + 2.0 * tol::LINEAR);
if reach.as_ref().is_some_and(Vec::is_empty) {
return Vec::new();
}
let ds: Vec<f64> = ts
.iter()
.map(|&t| match &reach {
Some(r) if !r.iter().any(|&(lo, hi)| lo <= t && t <= hi) => f64::INFINITY,
_ => gap(t),
})
.collect();
let mut out = Vec::new();
for k in 1..SAMPLES {
let (lo, hi) = (ds[k - 1].min(ds[k + 1]), ds[k - 1].max(ds[k + 1]));
if ds[k] > ds[k - 1] || ds[k] > ds[k + 1] || hi > GRAZE_GAP || lo <= 1e-3 * tol::LINEAR {
continue;
}
let (mut a, mut b) = (ts[k - 1], ts[k + 1]);
let g = 0.5 * (5f64.sqrt() - 1.0);
for _ in 0..100 {
let (x1, x2) = (b - g * (b - a), a + g * (b - a));
if gap(x1) <= gap(x2) {
b = x2;
} else {
a = x1;
}
}
let t = 0.5 * (a + b);
let offset = |s: f64| {
let p = c1.eval(s);
c2.eval(curve_distance(c2, r2, p).1) - p
};
let crosses = offset(ts[k - 1]).dot(offset(ts[k + 1])) < 0.0;
if gap(t) <= 0.5 * tol::LINEAR && crosses {
out.push(c1.eval(t));
}
}
out
}
pub(crate) fn curve_curve(c1: &Curve, r1: (f64, f64), c2: &Curve, r2: (f64, f64)) -> Vec<Point3> {
let on2 = |p: Point3| within(c2, r2, p, tol::LINEAR);
let on1 = |p: Point3| within(c1, r1, p, tol::LINEAR);
match (c1, c2) {
(Curve::Line(a), Curve::Line(b)) => {
let w = a.origin - b.origin;
let c = a.dir.dot(b.dir);
let den = 1.0 - c * c;
if den.sqrt() <= tol::ANGULAR {
return Vec::new();
}
let (d, e) = (a.dir.dot(w), b.dir.dot(w));
let s = (c * e - d) / den;
let t = (e - c * d) / den;
let (p, q) = (a.origin + a.dir * s, b.origin + b.dir * t);
if p.dist(q) <= tol::LINEAR
&& in_range(c1, s, r1).is_some()
&& in_range(c2, t, r2).is_some()
{
vec![p.lerp(q, 0.5)]
} else {
Vec::new()
}
}
(Curve::Line(_), _) if conic_plane(c2).is_some() => line_conic(c1, r1, c2, r2),
(_, Curve::Line(_)) if conic_plane(c1).is_some() => line_conic(c2, r2, c1, r1),
(Curve::Circle(a), Curve::Circle(b))
if a.frame.z.cross(b.frame.z).norm() <= tol::ANGULAR
&& (b.frame.origin - a.frame.origin).dot(a.frame.z).abs() <= tol::LINEAR =>
{
let l = a.frame.to_local(b.frame.origin);
let d = l.x.hypot(l.y);
let (ra, rb) = (a.radius, b.radius);
if d <= tol::LINEAR {
return Vec::new();
}
if d > ra + rb + tol::LINEAR || d < (ra - rb).abs() - tol::LINEAR {
return Vec::new();
}
let ex = Vec3::new(l.x / d, l.y / d, 0.0);
let ey = Vec3::new(-ex.y, ex.x, 0.0);
let x = (d * d + ra * ra - rb * rb) / (2.0 * d);
let touching =
(d - (ra + rb)).abs() <= tol::LINEAR || (d - (ra - rb).abs()).abs() <= tol::LINEAR;
let pts: Vec<Vec3> = if touching {
vec![ex * x.clamp(-ra, ra)]
} else {
let y = (ra * ra - x * x).max(0.0).sqrt();
vec![ex * x + ey * y, ex * x - ey * y]
};
pts.into_iter()
.map(|q| a.frame.to_world(q))
.filter(|&p| on1(p) && on2(p))
.collect()
}
_ => {
if let Some(f) = conic_plane(c2) {
let plane = Surface::Plane(crate::geom::Plane { frame: f });
let h = curve_surface(c1, r1, &plane);
if !h.on_surface {
return h
.ts
.iter()
.map(|&t| c1.eval(t))
.filter(|&p| on2(p))
.collect();
}
}
if let Some(f) = conic_plane(c1) {
let plane = Surface::Plane(crate::geom::Plane { frame: f });
let h = curve_surface(c2, r2, &plane);
if !h.on_surface {
return h
.ts
.iter()
.map(|&t| c2.eval(t))
.filter(|&p| on1(p))
.collect();
}
}
generic_curve_curve(c1, r1, c2, r2)
}
}
}
pub(crate) fn curve_curve_near(
c: &Curve,
rc: (f64, f64),
e: &Curve,
re: (f64, f64),
p: Point3,
t: f64,
through: Option<&Surface>,
) -> Option<(Point3, f64, f64)> {
let (mut s, mut t) = (c.project(p, rc.0, rc.1), t);
for _ in 0..40 {
let ((a, da), (b, db)) = (c.d1(s), e.d1(t));
let r = a - b;
let (aa, ab, bb) = (da.dot(da), -da.dot(db), db.dot(db));
let (ds, dt) = numeric::solve2(aa, ab, ab, bb, -da.dot(r), db.dot(r))?;
let (ns, nt) = ((s + ds).clamp(rc.0, rc.1), (t + dt).clamp(re.0, re.1));
let still =
(ns - s).abs() <= 1e-15 * (1.0 + s.abs()) && (nt - t).abs() <= 1e-15 * (1.0 + t.abs());
(s, t) = (ns, nt);
if still {
break;
}
}
let (a, b) = (c.eval(s), e.eval(t));
let (da, db) = (c.d1(s).1.unit_or_zero(), e.d1(t).1.unit_or_zero());
let sine = da.cross(db).norm();
if a.dist(b) > tol::LINEAR || sine <= tol::TANGENT {
return None;
}
let on = through.and_then(|surf| {
let s = onto_surface(c, rc, s, surf)?;
let q = c.eval(s);
let (d, tq) = curve_distance(e, re, q);
(d <= tol::LINEAR).then_some((q, tq))
});
Some(match on {
Some((q, tq)) => (q, tq, sine),
None => (a.lerp(b, 0.5), t, sine),
})
}
pub(crate) fn on_three(surfs: [&Surface; 3], p: Point3) -> Option<Point3> {
let planes = |p: Point3| {
surfs.map(|s| {
let uv = s.project(p);
let n = s.normal(uv.x, uv.y);
(n, (p - s.eval(uv.x, uv.y)).dot(n))
})
};
let mut p = p;
for _ in 0..30 {
let [(n0, d0), (n1, d1), (n2, d2)] = planes(p);
let det = n0.dot(n1.cross(n2));
if det.abs() <= tol::TANGENT {
return None;
}
let step = (n1.cross(n2) * -d0 + n2.cross(n0) * -d1 + n0.cross(n1) * -d2) * (1.0 / det);
p += step;
if step.norm() <= 1e-15 * (1.0 + p.norm()) {
break;
}
}
planes(p)
.iter()
.all(|&(_, d)| d.abs() <= 1e-3 * tol::LINEAR)
.then_some(p)
}
fn onto_surface(c: &Curve, rc: (f64, f64), s0: f64, surf: &Surface) -> Option<f64> {
let mut s = s0;
for _ in 0..30 {
let (p, dp) = c.d1(s);
let uv = surf.project(p);
let slope = surf.normal(uv.x, uv.y).dot(dp);
if slope.abs() <= tol::TANGENT * dp.norm() {
return None;
}
let next = (s - signed_distance(surf, p) / slope).clamp(rc.0, rc.1);
let still = (next - s).abs() <= 1e-15 * (1.0 + s.abs());
s = next;
if still {
break;
}
}
(signed_distance(surf, c.eval(s)).abs() <= 1e-3 * tol::LINEAR).then_some(s)
}
fn line_conic(line: &Curve, rl: (f64, f64), conic: &Curve, rc: (f64, f64)) -> Vec<Point3> {
let Curve::Line(l) = line else {
return Vec::new();
};
let frame = conic_plane(conic).expect("conic has a plane");
let in_plane = l.dir.dot(frame.z).abs() <= tol::ANGULAR
&& (l.origin - frame.origin).dot(frame.z).abs() <= tol::LINEAR;
let on_conic = |p: Point3| curve_distance(conic, rc, p).0 <= tol::LINEAR;
if !in_plane {
let plane = Surface::Plane(crate::geom::Plane { frame });
return curve_surface(line, rl, &plane)
.ts
.into_iter()
.map(|t| line.eval(t))
.filter(|&p| on_conic(p))
.collect();
}
let ts = match conic {
Curve::Circle(ci) => {
line_cylinder(
l.origin,
l.dir,
&Cylinder {
frame: ci.frame,
radius: ci.radius,
},
)
.ts
}
_ => {
let Curve::Ellipse(e) = conic else {
return Vec::new();
};
let lo = e.frame.to_local(l.origin);
let ld = e.frame.dir_to_local(l.dir);
let (ox, oy) = (lo.x / e.major, lo.y / e.minor);
let (dx, dy) = (ld.x / e.major, ld.y / e.minor);
let a = dx * dx + dy * dy;
let t_near = -(ox * dx + oy * dy) / a;
let disc = 1.0 - ((ox + dx * t_near).powi(2) + (oy + dy * t_near).powi(2));
let near = line.eval(t_near);
if on_conic(near) {
vec![t_near]
} else if disc > 0.0 {
let h = (disc / a).sqrt();
vec![t_near - h, t_near + h]
} else {
Vec::new()
}
}
};
ts.into_iter()
.filter_map(|t| in_range(line, t, rl))
.map(|t| line.eval(t))
.filter(|&p| on_conic(p))
.collect()
}
struct CurveIndex<'a> {
curve: &'a Curve,
spans: Vec<(f64, f64, crate::math::Aabb)>,
}
impl<'a> CurveIndex<'a> {
fn new(curve: &'a Curve, range: (f64, f64)) -> CurveIndex<'a> {
let mut cuts = vec![range.0];
cuts.extend(curve.breakpoints(range.0, range.1));
cuts.push(range.1);
if cuts.len() < 9 {
cuts = (0..=16)
.map(|i| range.0 + (range.1 - range.0) * i as f64 / 16.0)
.collect();
}
let spans = cuts
.windows(2)
.map(|w| {
let n = 8;
let pts: Vec<Point3> = (0..=n)
.map(|i| curve.eval(w[0] + (w[1] - w[0]) * i as f64 / n as f64))
.collect();
let mut bb = crate::math::Aabb::EMPTY;
let mut chord: f64 = 0.0;
for (i, &p) in pts.iter().enumerate() {
bb.add(p);
if i > 0 {
chord = chord.max(p.dist(pts[i - 1]));
}
}
let pad = Vec3::new(chord, chord, chord);
bb.min -= pad;
bb.max += pad;
(w[0], w[1], bb)
})
.collect();
CurveIndex { curve, spans }
}
fn distance(&self, p: Point3) -> (f64, f64) {
let gap = |bb: &crate::math::Aabb| {
let d = Vec3::new(
(bb.min.x - p.x).max(p.x - bb.max.x).max(0.0),
(bb.min.y - p.y).max(p.y - bb.max.y).max(0.0),
(bb.min.z - p.z).max(p.z - bb.max.z).max(0.0),
);
d.norm()
};
let gaps: Vec<f64> = self.spans.iter().map(|s| gap(&s.2)).collect();
let first = (0..gaps.len())
.min_by(|&a, &b| gaps[a].total_cmp(&gaps[b]))
.expect("an index has spans");
let (a, b, _) = self.spans[first];
let bound = curve_distance(self.curve, (a, b), p).0;
let mut order: Vec<(f64, usize)> = gaps
.iter()
.enumerate()
.filter(|&(_, &g)| g <= bound)
.map(|(i, &g)| (g, i))
.collect();
order.sort_by(|a, b| a.0.total_cmp(&b.0));
let mut best = (f64::INFINITY, self.spans[0].0);
for (g, i) in order {
if g > best.0 {
break;
}
let (a, b, _) = self.spans[i];
let r = curve_distance(self.curve, (a, b), p);
if r.0 < best.0 {
best = r;
}
}
best
}
}
fn generic_curve_curve(c1: &Curve, r1: (f64, f64), c2: &Curve, r2: (f64, f64)) -> Vec<Point3> {
sampled_curve_curve(c1, r1, c2, r2, true)
}
fn sampled_curve_curve(
c1: &Curve,
r1: (f64, f64),
c2: &Curve,
r2: (f64, f64),
prune: bool,
) -> Vec<Point3> {
const N: usize = 16;
let mut cuts = vec![r1.0];
cuts.extend(c1.breakpoints(r1.0, r1.1));
cuts.push(r1.1);
let mut ts: Vec<f64> = Vec::with_capacity(N * (cuts.len() - 1) + 1);
for w in cuts.windows(2) {
ts.extend((0..N).map(|i| w[0] + (w[1] - w[0]) * i as f64 / N as f64));
}
ts.push(cuts[cuts.len() - 1]);
let n = ts.len();
let near = |reach: &[(f64, f64)]| {
let mut k = 0;
let mut want = vec![false; n];
for &(lo, hi) in reach {
while k < n && ts[(k + 1).min(n - 1)] < lo {
k += 1;
}
let mut j = k;
while j < n && ts[j.saturating_sub(1)] <= hi {
want[j] = true;
j += 1;
}
}
want
};
let reach = prune
.then(|| hulls::near(c1, r1, c2, r2, 2.0 * tol::LINEAR))
.flatten();
let wanted = match reach {
Some(r) if r.is_empty() => return Vec::new(),
Some(r) => near(&r),
None => vec![true; n],
};
let index = CurveIndex::new(c2, r2);
let mut samples: Vec<Option<f64>> = vec![None; n];
for k in (0..n).filter(|&k| wanted[k]) {
for j in k.saturating_sub(1)..(k + 2).min(n) {
if samples[j].is_none() {
samples[j] = Some(index.distance(c1.eval(ts[j])).0);
}
}
}
let value = |k: usize| {
(
ts[k],
samples[k].expect("a wanted sample's neighbours are sampled"),
)
};
let mut out: Vec<Point3> = Vec::new();
for k in (0..n).filter(|&k| wanted[k]) {
let at = value(k);
let lo = if k > 0 { value(k - 1) } else { at };
let hi = if k + 1 < n { value(k + 1) } else { at };
if at.1 > lo.1 || at.1 > hi.1 {
continue;
}
if (k > 0 && lo.1 <= tol::LINEAR) || (k + 1 < n && hi.1 <= tol::LINEAR) {
continue;
}
let t = minimise(&mut |t: f64| index.distance(c1.eval(t)).0, lo.0, hi.0);
let p = c1.eval(t);
let (d, s) = index.distance(p);
if d <= tol::LINEAR {
let q = p.lerp(c2.eval(s), 0.5);
if !out.iter().any(|o| o.dist(q) <= tol::LINEAR) {
out.push(q);
}
}
}
out
}
pub(crate) fn ray_surface(s: &Surface, p: Point3, d: Vec3, t_max: f64) -> Vec<f64> {
let quad = |a: f64, b: f64, c: f64| -> Vec<f64> {
let disc = b * b - 4.0 * a * c;
if a.abs() < 1e-300 || disc < 0.0 {
return if a.abs() < 1e-300 && b.abs() > 1e-300 {
vec![-c / b]
} else {
Vec::new()
};
}
let q = -0.5 * (b + b.signum() * disc.sqrt());
let mut v = vec![q / a];
if q.abs() > 1e-300 {
v.push(c / q);
}
v
};
match s {
Surface::Plane(pl) => {
let dn = d.dot(pl.frame.z);
if dn.abs() < 1e-300 {
Vec::new()
} else {
vec![(pl.frame.origin - p).dot(pl.frame.z) / dn]
}
}
Surface::Cylinder(c) => {
let lo = c.frame.to_local(p);
let ld = c.frame.dir_to_local(d);
quad(
ld.x * ld.x + ld.y * ld.y,
2.0 * (lo.x * ld.x + lo.y * ld.y),
lo.x * lo.x + lo.y * lo.y - c.radius * c.radius,
)
}
Surface::Sphere(sp) => {
let oc = p - sp.frame.origin;
quad(1.0, 2.0 * oc.dot(d), oc.norm2() - sp.radius * sp.radius)
}
Surface::Cone(cone) if cone.half_angle.cos().abs() > 1e-9 => {
let lo = cone.frame.to_local(p);
let ld = cone.frame.dir_to_local(d);
let k = cone.half_angle.tan();
let r0 = cone.radius + k * lo.z;
quad(
ld.x * ld.x + ld.y * ld.y - k * k * ld.z * ld.z,
2.0 * (lo.x * ld.x + lo.y * ld.y - k * r0 * ld.z),
lo.x * lo.x + lo.y * lo.y - r0 * r0,
)
}
_ => {
let line = Curve::Line(Line { origin: p, dir: d });
curve_surface(&line, (0.0, t_max), s).ts
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{
geom::{Circle, Line, Plane},
math::Frame,
};
fn line(o: [f64; 3], d: [f64; 3]) -> Curve {
Curve::Line(Line {
origin: Vec3::from_array(o),
dir: Vec3::from_array(d).unit().unwrap(),
})
}
fn rippled_prism() -> (crate::geom::BSpline, Surface) {
let mut ctrl: Vec<Vec3> = Vec::new();
for k in 0..16 {
let x = 5.0 + if k % 2 == 0 { 0.004 } else { -0.004 };
ctrl.push(Vec3::new(x, -0.075 + 0.01 * k as f64, 0.0));
}
for k in 1..8 {
let a = TAU / 4.0 + TAU / 2.0 * k as f64 / 8.0;
ctrl.push(Vec3::new(5.0 + 4.0 * a.cos(), 4.0 * a.sin(), 0.0));
}
let n = ctrl.len();
ctrl.extend_from_within(..3);
let knots = (0..n + 7).map(|i| i as f64 - 3.0).collect();
let curve = crate::geom::BSpline::periodic_cubic(knots, ctrl).unwrap();
let surface = Surface::Extrusion(Box::new(crate::geom::Extrusion {
curve: Curve::BSpline(curve.clone()),
dir: Vec3::Z,
}));
(curve, surface)
}
#[test]
fn a_line_along_an_extrusions_ripples_meets_it_at_every_crossing() {
let (curve, surface) = rippled_prism();
let (u0, u1) = curve.domain();
let steps = 400_000;
let at = |i: usize| u0 + (u1 - u0) * i as f64 / steps as f64;
for shift in [0.0, 0.001, -0.001] {
let o = Vec3::new(5.0 + shift, -20.0, -3.0);
let d = Vec3::new(0.0, 1.0, 0.2).unit().unwrap();
let l = Curve::Line(Line { origin: o, dir: d });
let side = |u: f64| curve.eval(u).x - (5.0 + shift);
let mut want = Vec::new();
for i in 0..steps {
let (a, b) = (side(at(i)), side(at(i + 1)));
if (a < 0.0) != (b < 0.0) {
let u = numeric::bisect(&mut |u| side(u), at(i), at(i + 1));
want.push((curve.eval(u) - o).y / d.y);
}
}
want.sort_by(f64::total_cmp);
assert!(want.len() >= 10, "shift {shift}: {} crossings", want.len());
let got = curve_surface(&l, (-100.0, 100.0), &surface);
assert!(!got.on_surface);
let mut ts = got.ts.clone();
ts.sort_by(f64::total_cmp);
assert_eq!(
ts.len(),
want.len(),
"shift {shift}: {ts:?} against {want:?}"
);
for (t, w) in ts.iter().zip(&want) {
assert!(
(t - w).abs() < 1e-7,
"shift {shift}: {ts:?} against {want:?}"
);
}
}
}
fn passings(profile: &Curve, at: f64, o: Vec3, d: Vec3) -> Vec<f64> {
let (u0, u1) = profile.domain();
let steps = 400_000;
let u = |i: usize| u0 + (u1 - u0) * i as f64 / steps as f64;
let side = |t: f64| profile.eval(t).x - at;
let mut out = Vec::new();
for i in 0..steps {
let (a, b) = (side(u(i)), side(u(i + 1)));
if (a < 0.0) != (b < 0.0) {
let t = numeric::bisect(&mut |t| side(t), u(i), u(i + 1));
out.push((profile.eval(t) - o).y / d.y);
}
}
out.sort_by(f64::total_cmp);
out
}
#[test]
fn a_line_along_a_rational_extrusions_ripples_meets_it_at_every_crossing() {
let ctrl: Vec<Vec3> = (0..20)
.map(|k| {
let x = 5.0 + if k % 2 == 0 { 0.004 } else { -0.004 };
Vec3::new(x, -0.1 + 0.01 * k as f64, 0.0)
})
.collect();
let weights = (0..20).map(|k| 1.0 + 0.7 * (k % 3) as f64).collect();
let mut knots = vec![0.0; 4];
knots.extend((1..17).map(|i| i as f64));
knots.extend([17.0; 4]);
let nurbs = crate::geom::NurbsCurve::new(3, knots, ctrl, Some(weights)).unwrap();
let profile = Curve::Nurbs(Box::new(nurbs));
let surface = Surface::Extrusion(Box::new(crate::geom::Extrusion {
curve: profile.clone(),
dir: Vec3::Z,
}));
for shift in [0.0, 0.0007, -0.0005] {
let o = Vec3::new(5.0 + shift, -20.0, -3.0);
let d = Vec3::new(0.0, 1.0, 0.2).unit().unwrap();
let want = passings(&profile, 5.0 + shift, o, d);
assert!(want.len() >= 4, "shift {shift}: {} crossings", want.len());
let got = curve_surface(
&Curve::Line(Line { origin: o, dir: d }),
(-100.0, 100.0),
&surface,
);
let mut ts = got.ts.clone();
ts.sort_by(f64::total_cmp);
assert_eq!(
ts.len(),
want.len(),
"shift {shift}: {ts:?} against {want:?}"
);
for (t, w) in ts.iter().zip(&want) {
assert!(
(t - w).abs() < 1e-7,
"shift {shift}: {ts:?} against {want:?}"
);
}
}
}
#[test]
fn a_line_meets_an_extrusion_three_times_within_a_fraction_of_one_piece() {
let (a, b, c) = (0.505, 0.515, 0.525);
let k = 300.0;
let power = [
-k * a * b * c,
k * (a * b + b * c + c * a),
-k * (a + b + c),
k,
];
let bezier = [
power[0],
power[0] + power[1] / 3.0,
power[0] + 2.0 * power[1] / 3.0 + power[2] / 3.0,
power[0] + power[1] + power[2] + power[3],
];
let ctrl: Vec<Vec3> = (0..4)
.map(|i| Vec3::new(5.0 + bezier[i], 10.0 * i as f64 / 3.0, 0.0))
.collect();
let knots = vec![0.0, 0.0, 0.0, 0.0, 1.0, 1.0, 1.0, 1.0];
for weights in [None, Some(vec![1.0, 2.0, 4.0, 8.0])] {
let nurbs = crate::geom::NurbsCurve::new(3, knots.clone(), ctrl.clone(), weights);
let profile = Curve::Nurbs(Box::new(nurbs.unwrap()));
let surface = Surface::Extrusion(Box::new(crate::geom::Extrusion {
curve: profile.clone(),
dir: Vec3::Z,
}));
let o = Vec3::new(5.0, -20.0, -3.0);
let d = Vec3::new(0.0, 1.0, 0.2).unit().unwrap();
let want = passings(&profile, 5.0, o, d);
assert_eq!(want.len(), 3);
let line = Curve::Line(Line { origin: o, dir: d });
let mut ts = curve_surface(&line, (-100.0, 100.0), &surface).ts;
ts.sort_by(f64::total_cmp);
assert_eq!(ts.len(), 3, "{ts:?} against {want:?}");
for (t, w) in ts.iter().zip(&want) {
assert!((t - w).abs() < 1e-7, "{ts:?} against {want:?}");
}
}
}
fn rippled_meridian() -> Curve {
let ctrl: Vec<Vec3> = (0..20)
.map(|k| {
let r = 5.0 + if k % 2 == 0 { 0.004 } else { -0.004 };
Vec3::new(r, 0.0, -0.1 + 0.01 * k as f64)
})
.collect();
let mut knots = vec![0.0; 4];
knots.extend((1..17).map(|i| i as f64));
knots.extend([17.0; 4]);
Curve::Nurbs(Box::new(
crate::geom::NurbsCurve::new(3, knots, ctrl, None).unwrap(),
))
}
fn ring_passings(profile: &Curve, o: Vec3, d: Vec3) -> Vec<f64> {
let (u0, u1) = profile.domain();
let steps = 400_000;
let u = |i: usize| u0 + (u1 - u0) * i as f64 / steps as f64;
let line_at = |z: f64| (z - o.z) / d.z;
let side = |t: f64| {
let q = profile.eval(t);
let x = o + d * line_at(q.z);
x.x.hypot(x.y) - q.x.hypot(q.y)
};
let mut out = Vec::new();
for i in 0..steps {
let (a, b) = (side(u(i)), side(u(i + 1)));
if (a < 0.0) != (b < 0.0) {
let t = numeric::bisect(&mut |t| side(t), u(i), u(i + 1));
out.push(line_at(profile.eval(t).z));
}
}
out.sort_by(f64::total_cmp);
out
}
#[test]
fn a_line_along_a_revolved_surfaces_ripples_meets_it_at_every_crossing() {
let profile = rippled_meridian();
let surface = Surface::Revolution(Box::new(crate::geom::Revolution {
curve: profile.clone(),
origin: Vec3::ZERO,
axis: Vec3::Z,
}));
for (o, d) in [
(Vec3::new(5.0, 0.0, -30.0), Vec3::Z),
(Vec3::new(3.0, 4.0005, -30.0), Vec3::Z),
(
Vec3::new(5.0 - 0.3, 0.4, -30.0),
Vec3::new(0.01, -0.013, 1.0),
),
] {
let d = d.unit().unwrap();
let want = ring_passings(&profile, o, d);
assert!(want.len() >= 6, "{o:?}: {} crossings", want.len());
let line = Curve::Line(Line { origin: o, dir: d });
let mut ts = curve_surface(&line, (0.0, 100.0), &surface).ts;
ts.sort_by(f64::total_cmp);
assert_eq!(ts.len(), want.len(), "{o:?}: {ts:?} against {want:?}");
for (t, w) in ts.iter().zip(&want) {
assert!((t - w).abs() < 1e-7, "{o:?}: {ts:?} against {want:?}");
}
}
}
#[test]
fn a_line_square_to_a_revolved_surfaces_axis_meets_its_ring_twice() {
let profile = rippled_meridian();
let surface = Surface::Revolution(Box::new(crate::geom::Revolution {
curve: profile.clone(),
origin: Vec3::ZERO,
axis: Vec3::Z,
}));
let z = 0.0312;
let (u0, u1) = profile.domain();
let u = numeric::bisect(&mut |t| profile.eval(t).z - z, u0, u1);
let ring = profile.eval(u).x;
let (o, d) = (Vec3::new(-20.0, 1.5, z), Vec3::X);
let half = (ring * ring - 1.5 * 1.5).sqrt();
let line = Curve::Line(Line { origin: o, dir: d });
let mut ts = curve_surface(&line, (0.0, 100.0), &surface).ts;
ts.sort_by(f64::total_cmp);
assert_eq!(ts.len(), 2, "{ts:?}");
assert!((ts[0] - (20.0 - half)).abs() < 1e-7 && (ts[1] - (20.0 + half)).abs() < 1e-7);
}
#[test]
fn a_line_along_a_ruled_surfaces_ripples_meets_it_at_every_crossing() {
let near = rippled_meridian();
let far = match &near {
Curve::Nurbs(n) => Curve::Nurbs(Box::new(n.transformed(
&crate::math::Transform::translation(Vec3::new(0.0, 3.0, 0.0)),
))),
_ => unreachable!(),
};
let range = near.domain();
let surface = Surface::Ruled(Box::new(crate::geom::Ruled {
a: near.clone(),
a_range: range,
b: far,
b_range: range,
}));
for shift in [0.0, 0.0007, -0.0005] {
let o = Vec3::new(5.0 + shift, 1.0, -30.0);
let d = Vec3::new(0.0, 0.02, 1.0).unit().unwrap();
let steps = 400_000;
let u = |i: usize| range.0 + (range.1 - range.0) * i as f64 / steps as f64;
let side = |t: f64| near.eval(t).x - (5.0 + shift);
let mut want = Vec::new();
for i in 0..steps {
let (a, b) = (side(u(i)), side(u(i + 1)));
if (a < 0.0) != (b < 0.0) {
let t = numeric::bisect(&mut |t| side(t), u(i), u(i + 1));
want.push((near.eval(t).z - o.z) / d.z);
}
}
want.sort_by(f64::total_cmp);
assert!(want.len() >= 6, "shift {shift}: {} crossings", want.len());
let line = Curve::Line(Line { origin: o, dir: d });
let mut ts = curve_surface(&line, (0.0, 100.0), &surface).ts;
ts.sort_by(f64::total_cmp);
assert_eq!(
ts.len(),
want.len(),
"shift {shift}: {ts:?} against {want:?}"
);
for (t, w) in ts.iter().zip(&want) {
assert!(
(t - w).abs() < 1e-7,
"shift {shift}: {ts:?} against {want:?}"
);
}
}
}
#[test]
fn a_line_through_a_torus_whose_tube_reaches_its_axis_meets_both_its_sheets() {
let torus = Surface::Torus(Torus {
frame: Frame::WORLD,
major: 1.0,
minor: 2.0,
});
let line = |o: [f64; 3], d: [f64; 3]| line(o, d);
let mut ts = curve_surface(
&line([-10.0, 0.0, 0.0], [1.0, 0.0, 0.0]),
(0.0, 100.0),
&torus,
)
.ts;
ts.sort_by(f64::total_cmp);
assert_eq!(ts.len(), 4, "{ts:?}");
for (t, w) in ts.iter().zip([7.0, 9.0, 11.0, 13.0]) {
assert!((t - w).abs() < 1e-9, "{ts:?}");
}
let (o, d) = (
Vec3::new(-9.0, 0.3, -0.4),
Vec3::new(1.0, 0.02, 0.05).unit().unwrap(),
);
let sheet = |t: f64, sign: f64| {
let q = o + d * t;
(q.x.hypot(q.y) + sign).hypot(q.z) - 2.0
};
let both = |t: f64| sheet(t, -1.0) * sheet(t, 1.0);
let steps = 2_000_000;
let changes = (0..steps)
.filter(|&i| {
let (a, b) = (
20.0 * i as f64 / steps as f64,
20.0 * (i + 1) as f64 / steps as f64,
);
(both(a) < 0.0) != (both(b) < 0.0)
})
.count();
let ts = curve_surface(
&Curve::Line(Line { origin: o, dir: d }),
(0.0, 20.0),
&torus,
)
.ts;
assert_eq!(ts.len(), changes, "{ts:?}");
for &t in &ts {
assert!(sheet(t, -1.0).abs().min(sheet(t, 1.0).abs()) < 1e-9, "{t}");
}
}
fn rippled_sheet() -> crate::geom::NurbsSurface {
let n = 24;
let mut knots = vec![0.0; 4];
knots.extend((1..n - 3).map(|i| i as f64 / (n - 3) as f64));
knots.extend([1.0; 4]);
let greville = |i: usize| (knots[i + 1] + knots[i + 2] + knots[i + 3]) / 3.0;
let mut ctrl = Vec::new();
for i in 0..n {
for j in 0..n {
let z = if i % 2 == 0 { 0.004 } else { -0.004 };
ctrl.push(Vec3::new(0.24 * greville(i), 0.24 * greville(j), z));
}
}
crate::geom::NurbsSurface::new((3, 3), (knots.clone(), knots), (n, n), ctrl, None).unwrap()
}
#[test]
fn a_line_skimming_a_spline_sheets_ripples_meets_it_at_every_crossing() {
let sheet = rippled_sheet();
let surface = Surface::Nurbs(Box::new(sheet.clone()));
for (o, d) in [
(Vec3::new(-1.0, 0.1, 0.0), Vec3::new(1.0, 0.0, 0.0)),
(Vec3::new(-1.0, 0.05, 0.0003), Vec3::new(1.0, 0.05, 0.0)),
(Vec3::new(-1.0, 0.2, 0.004), Vec3::new(1.0, -0.02, -0.0035)),
] {
let d = d.unit().unwrap();
let above = |t: f64| {
let q = o + d * t;
q.z - sheet.eval(q.x / 0.24, q.y / 0.24).z
};
let over = |t: f64| {
let q = o + d * t;
(0.0..=0.24).contains(&q.x) && (0.0..=0.24).contains(&q.y)
};
let steps = 1_000_000;
let at = |i: usize| 8.0 * i as f64 / steps as f64;
let mut want = Vec::new();
for i in 0..steps {
if over(at(i))
&& over(at(i + 1))
&& (above(at(i)) < 0.0) != (above(at(i + 1)) < 0.0)
{
want.push(numeric::bisect(&mut |t| above(t), at(i), at(i + 1)));
}
}
assert!(want.len() >= 6, "{o:?}: {} crossings", want.len());
let line = Curve::Line(Line { origin: o, dir: d });
let mut ts = curve_surface(&line, (0.0, 8.0), &surface).ts;
ts.sort_by(f64::total_cmp);
assert_eq!(
ts.len(),
want.len(),
"{o:?}: {} against {}",
ts.len(),
want.len()
);
for (t, w) in ts.iter().zip(&want) {
assert!((t - w).abs() < 1e-6, "{o:?}: {t} against {w}");
}
}
}
fn cylinder(r: f64) -> Surface {
Surface::Cylinder(Cylinder {
frame: Frame::WORLD,
radius: r,
})
}
#[test]
fn a_line_touching_a_torus_within_rounding_meets_it_once_where_it_touches() {
let torus = Surface::Torus(crate::geom::Torus {
frame: Frame::WORLD,
major: 5.5,
minor: 1.5,
});
let hits = curve_surface(
&line([4.0 + 3e-11, 0.0, 0.0], [0.0, 0.0, 1.0]),
(-5.0, 5.0),
&torus,
);
assert_eq!(hits.ts.len(), 1, "{hits:?}");
assert!(hits.ts[0].abs() < 1e-7, "{hits:?}");
}
#[test]
fn a_line_cutting_a_tube_between_two_samples_meets_it_twice() {
let torus = Surface::Torus(crate::geom::Torus {
frame: Frame::WORLD.translated(Vec3::new(0.0, 0.0, 0.05)),
major: 5.5,
minor: 1.5,
});
let d = 1.5 - (1.5f64 * 1.5 - 0.04 * 0.04).sqrt();
let hits = curve_surface(
&line([4.0 + d, 0.0, 0.0], [0.0, 0.0, 1.0]),
(-5.0, 5.0),
&torus,
);
assert_eq!(hits.ts.len(), 2, "{hits:?}");
assert!((hits.ts[0] - 0.01).abs() < 1e-9, "{hits:?}");
assert!((hits.ts[1] - 0.09).abs() < 1e-9, "{hits:?}");
}
#[test]
fn line_meets_cylinder_twice_once_or_never() {
let s = cylinder(5.0);
let two = curve_surface(
&line([-10.0, 4.999999, 0.0], [1.0, 0.0, 0.0]),
(0.0, 20.0),
&s,
);
assert_eq!(two.ts.len(), 2);
let gap = (two.ts[1] - two.ts[0]).abs();
assert!((gap - 2.0 * (5.0f64.powi(2) - 4.999999f64.powi(2)).sqrt()).abs() < 1e-12);
let touch = curve_surface(&line([-10.0, 5.0, 0.0], [1.0, 0.0, 0.0]), (0.0, 20.0), &s);
assert_eq!(touch.ts, vec![10.0]);
let miss = curve_surface(
&line([-10.0, 5.000001, 0.0], [1.0, 0.0, 0.0]),
(0.0, 20.0),
&s,
);
assert!(miss.ts.is_empty() && !miss.on_surface);
let along = curve_surface(&line([5.0, 0.0, 0.0], [0.0, 0.0, 1.0]), (0.0, 20.0), &s);
assert!(along.on_surface);
}
#[test]
fn circle_meets_plane_in_closed_form() {
let c = Curve::Circle(Circle {
frame: Frame::WORLD,
radius: 5.0,
});
let at = |x: f64| {
Surface::Plane(Plane {
frame: Frame::new(Vec3::new(x, 0.0, 0.0), Vec3::X, Vec3::Y).unwrap(),
})
};
assert_eq!(curve_surface(&c, (0.0, TAU), &at(3.0)).ts.len(), 2);
let touch = curve_surface(&c, (0.0, TAU), &at(-5.0)).ts;
assert_eq!(touch.len(), 1);
assert!((touch[0] - TAU / 2.0).abs() < 1e-12);
assert!(
curve_surface(
&c,
(0.0, TAU),
&Surface::Plane(Plane {
frame: Frame::WORLD
})
)
.on_surface
);
}
#[test]
fn a_round_touching_its_pillar_meets_it_at_the_touching_point() {
for k in 0..64 {
let a = 0.1 * k as f64;
let axis = Vec3::new(20.0 * a.sin(), 0.0, 20.0 * (1.3 * a).cos());
let out = Vec3::new(a.cos(), 0.0, a.sin());
let c = Curve::Circle(Circle {
frame: Frame::new(
axis + out * 4.5 - Vec3::Y * 16.0,
out.cross(Vec3::Y),
Vec3::Y,
)
.unwrap(),
radius: 3.0,
});
let pillar = Surface::Cylinder(Cylinder {
frame: Frame::new(axis, -Vec3::Y, out).unwrap(),
radius: 1.5,
});
let touch = axis + out * 1.5 - Vec3::Y * 16.0;
let end = (0..4)
.map(|k| k as f64 * TAU / 4.0)
.find(|&t| c.eval(t).dist(touch) <= 1e-12)
.unwrap();
for t in curve_surface(&c, (end - TAU / 4.0, end), &pillar).ts {
let d = c.eval(t).dist(touch);
assert!(d <= 1e-9, "{k} {d}");
}
}
}
#[test]
fn a_ray_clipping_a_lobe_of_an_extruded_outline_meets_it_twice() {
let r = |a: f64| 30.0 + 3.0 * (9.0 * a).cos();
let pts: Vec<Vec3> = (0..360)
.map(|i| {
let a = TAU * i as f64 / 360.0;
Vec3::new(r(a) * a.cos(), r(a) * a.sin(), 0.0)
})
.collect();
let curve = Curve::BSpline(crate::geom::BSpline::interpolate_periodic(&pts).unwrap());
let wall = Surface::Extrusion(Box::new(crate::geom::Extrusion {
curve: curve.clone(),
dir: Vec3::Z,
}));
let (t0, t1) = curve.domain();
let dense: Vec<Vec3> = (0..=400_000)
.map(|k| curve.eval(t0 + (t1 - t0) * k as f64 / 400_000.0))
.collect();
let tip = dense.iter().map(|p| p.x).fold(f64::NEG_INFINITY, f64::max);
for delta in [1e-4, 3e-4, 1e-3, 3e-3, 1e-2] {
let x = tip - delta;
let o = Vec3::new(x, -70.0, 1.0);
let want = dense
.windows(2)
.filter(|w| (w[0].x - x) * (w[1].x - x) < 0.0)
.count();
assert!(want >= 2, "δ = {delta}");
let hits = ray_surface(&wall, o, Vec3::Y, 140.0);
assert_eq!(hits.len(), want, "δ = {delta}: {hits:?}");
for t in hits {
assert!(signed_distance(&wall, o + Vec3::Y * t).abs() < 1e-9);
}
}
}
#[test]
fn numeric_hits_find_a_circle_crossing_a_cylinder() {
let c = Curve::Circle(Circle {
frame: Frame::new(Vec3::new(4.0, 0.0, 0.0), Vec3::Z, Vec3::X).unwrap(),
radius: 3.0,
});
let h = curve_surface(&c, (0.0, TAU), &cylinder(5.0));
assert_eq!(h.ts.len(), 2);
for t in h.ts {
assert!(signed_distance(&cylinder(5.0), c.eval(t)).abs() < 1e-12);
}
}
#[test]
fn coplanar_circles_and_lines_cross() {
let a = Curve::Circle(Circle {
frame: Frame::WORLD,
radius: 5.0,
});
let b = Curve::Circle(Circle {
frame: Frame::new(Vec3::new(6.0, 0.0, 0.0), Vec3::Z, Vec3::X).unwrap(),
radius: 3.0,
});
let pts = curve_curve(&a, (0.0, TAU), &b, (0.0, TAU));
assert_eq!(pts.len(), 2);
let l = line([0.0, -10.0, 0.0], [0.0, 1.0, 0.0]);
assert_eq!(curve_curve(&a, (0.0, TAU), &l, (0.0, 20.0)).len(), 2);
let tangent = line([5.0, -10.0, 0.0], [0.0, 1.0, 0.0]);
assert_eq!(curve_curve(&a, (0.0, TAU), &tangent, (0.0, 20.0)).len(), 1);
}
#[test]
fn rays_hit_quadrics() {
let hits = ray_surface(&cylinder(5.0), Vec3::ZERO, Vec3::X, 100.0);
assert_eq!(hits.len(), 2);
assert!(hits.iter().any(|&t| (t - 5.0).abs() < 1e-12));
}
fn helix(r: f64, per_turn: usize, (a, b): (f64, f64), mirror: bool) -> Curve {
let n = ((b - a) * per_turn as f64).round() as usize;
let pts: Vec<Vec3> = (0..=n)
.map(|i| {
let turn = a + (b - a) * i as f64 / n as f64;
let th = TAU * turn;
Vec3::new(r * th.cos(), r * th.sin(), turn)
})
.collect();
let s = crate::geom::BSpline::interpolate(&pts).unwrap();
if !mirror {
return Curve::BSpline(s);
}
let flip: Vec<Vec3> = s
.control_points()
.iter()
.map(|p| Vec3::new(p.x, -p.y, p.z))
.collect();
Curve::BSpline(crate::geom::BSpline::new(s.degree(), s.knots().to_vec(), flip).unwrap())
}
#[test]
fn a_helix_crosses_its_mirror_image_every_half_turn() {
let a = helix(5.0, 360, (-0.25, 3.25), false);
let b = helix(5.0, 360, (-0.25, 3.25), true);
let (ra, rb) = (a.domain(), b.domain());
let mut got = curve_curve(&a, ra, &b, rb);
got.sort_by(|p, q| p.z.total_cmp(&q.z));
assert_eq!(got.len(), 7, "{got:?}");
for (k, p) in got.iter().enumerate() {
let want = Vec3::new(if k % 2 == 0 { 5.0 } else { -5.0 }, 0.0, 0.5 * k as f64);
assert!(p.dist(want) <= 1e-9, "{k}: {p:?}");
}
}
#[test]
fn pruning_by_hulls_keeps_every_meeting_of_spline_curves() {
let h = helix(5.0, 40, (-0.25, 2.25), false);
let up = crate::math::Transform::translation(Vec3::Z * (0.5 * tol::LINEAR));
let post = Curve::BSpline(
crate::geom::BSpline::interpolate(&[
Vec3::new(5.0, 0.0, -0.6),
Vec3::new(5.0, 0.0, 0.7),
Vec3::new(5.0, 0.0, 1.4),
Vec3::new(5.0, 0.0, 2.6),
])
.unwrap(),
);
let cases = [
(h.clone(), helix(5.0, 40, (-0.25, 2.25), true), 5),
(h.clone(), helix(5.15, 40, (-0.25, 2.25), false), 0),
(h.clone(), post, 3),
(h.clone(), h.transformed(&up), 0),
];
for (i, (a, b, n)) in cases.iter().enumerate() {
let (ra, rb) = (a.domain(), b.domain());
let full = sampled_curve_curve(a, ra, b, rb, false);
let pruned = sampled_curve_curve(a, ra, b, rb, true);
assert_eq!(pruned, full, "case {i}");
assert_eq!(pruned.len(), *n, "case {i}: {pruned:?}");
}
}
#[test]
fn within_agrees_with_the_distance() {
let h = helix(5.0, 40, (-0.25, 2.25), false);
let r = h.domain();
for (out, want) in [(0.0, true), (0.5, true), (1.5, false), (3.0, false)] {
let p = Vec3::new(5.0 + out * tol::LINEAR, 0.0, 1.0);
assert_eq!(within(&h, r, p, tol::LINEAR), want, "{out}");
assert_eq!(curve_distance(&h, r, p).0 <= tol::LINEAR, want, "{out}");
}
assert!(!within(&h, r, Vec3::new(0.0, 0.0, 1.0), tol::LINEAR));
}
}