use std::f64::consts::{FRAC_PI_2, TAU};
use super::curve::{Curve, angle, dist2, interior_knots};
use super::nurbs::Nurbs2;
use crate::model::{Frame, P3, add, cross, dot, mul, norm, sub, unit};
const NEWTON_STEPS: usize = 60;
const SUFFICIENT_DECREASE: f64 = 0.25;
const FOOT_PRECISION: f64 = 1e-7;
const EXTENSION: f64 = 0.05;
const MAX_STARTS: usize = 4;
const NORMAL_STEP: f64 = 1e-6;
const REVOLUTION_SAMPLES: usize = 16;
const INF: f64 = f64::INFINITY;
#[derive(Debug, Clone, PartialEq)]
pub enum Surface {
Plane(Frame),
Cylinder {
frame: Frame,
r: f64,
},
Cone {
frame: Frame,
r: f64,
half_angle: f64,
},
Sphere {
frame: Frame,
r: f64,
},
Torus {
frame: Frame,
major: f64,
minor: f64,
},
Nurbs(Nurbs2),
Extrusion {
curve: Curve,
dir: P3,
},
Revolution {
curve: Curve,
axis_origin: P3,
axis_dir: P3,
},
Offset {
basis: Box<Surface>,
distance: f64,
},
}
fn ring(f: &Frame, u: f64) -> (P3, P3) {
let (s, c) = u.sin_cos();
(
add(mul(f.x, c), mul(f.y, s)),
add(mul(f.x, -s), mul(f.y, c)),
)
}
fn rotate(p: P3, k: P3, a: f64) -> P3 {
let (s, c) = a.sin_cos();
add(
add(mul(p, c), mul(cross(k, p), s)),
mul(k, dot(k, p) * (1.0 - c)),
)
}
fn nearest(x: f64, period: f64, near: f64) -> f64 {
x + ((near - x) / period).round() * period
}
impl Surface {
pub fn point(&self, u: f64, v: f64) -> P3 {
self.derivs(u, v).0
}
pub fn derivs(&self, u: f64, v: f64) -> (P3, P3, P3) {
match self {
Surface::Plane(f) => (add(f.origin, add(mul(f.x, u), mul(f.y, v))), f.x, f.y),
Surface::Cylinder { frame: f, r } => {
let (e, de) = ring(f, u);
(
add(f.origin, add(mul(e, *r), mul(f.z, v))),
mul(de, *r),
f.z,
)
}
Surface::Cone {
frame: f,
r,
half_angle,
} => {
let (e, de) = ring(f, u);
let t = half_angle.tan();
let rho = r + v * t;
(
add(f.origin, add(mul(e, rho), mul(f.z, v))),
mul(de, rho),
add(mul(e, t), f.z),
)
}
Surface::Sphere { frame: f, r } => {
let (e, de) = ring(f, u);
let (s, c) = v.sin_cos();
(
add(f.origin, add(mul(e, r * c), mul(f.z, r * s))),
mul(de, r * c),
add(mul(e, -r * s), mul(f.z, r * c)),
)
}
Surface::Torus {
frame: f,
major,
minor,
} => {
let (e, de) = ring(f, u);
let (s, c) = v.sin_cos();
let rho = major + minor * c;
(
add(f.origin, add(mul(e, rho), mul(f.z, minor * s))),
mul(de, rho),
add(mul(e, -minor * s), mul(f.z, minor * c)),
)
}
Surface::Nurbs(n) => n.derivs(u, v),
Surface::Extrusion { curve, dir } => {
let (c, dc) = curve.derivs(u);
(add(c, mul(*dir, v)), dc, *dir)
}
Surface::Revolution {
curve,
axis_origin,
axis_dir,
} => {
let (c, dc) = curve.derivs(v);
let q = rotate(sub(c, *axis_origin), *axis_dir, u);
(
add(*axis_origin, q),
cross(*axis_dir, q),
rotate(dc, *axis_dir, u),
)
}
Surface::Offset { basis, distance } => {
let (p, du, dv) = basis.derivs(u, v);
let n = basis.normal(u, v);
let [(u0, u1), (v0, v1)] = basis.param_bounds();
let (nu, nv) = (
basis.normal_change(u, u0, u1, |x| (x, v)),
basis.normal_change(v, v0, v1, |y| (u, y)),
);
(
add(p, mul(n, *distance)),
add(du, mul(nu, *distance)),
add(dv, mul(nv, *distance)),
)
}
}
}
fn normal_change(&self, x: f64, lo: f64, hi: f64, at: impl Fn(f64) -> (f64, f64)) -> P3 {
let span = if (hi - lo).is_finite() {
hi - lo
} else {
1.0 + x.abs()
};
let h = NORMAL_STEP * span;
let (a, b) = ((x - h).max(lo), (x + h).min(hi));
if b <= a {
return [0.0; 3];
}
let (pa, pb) = (at(a), at(b));
mul(
sub(self.normal(pb.0, pb.1), self.normal(pa.0, pa.1)),
1.0 / (b - a),
)
}
pub fn normal(&self, u: f64, v: f64) -> P3 {
let analytic = match self {
Surface::Plane(f) => Some(f.z),
Surface::Cylinder { frame, .. } => Some(ring(frame, u).0),
Surface::Sphere { frame, r } => {
unit(sub(self.point(u, v), frame.origin)).map(|n| mul(n, r.signum()))
}
Surface::Offset { basis, .. } => Some(basis.normal(u, v)),
_ => None,
};
if let Some(n) = analytic {
return n;
}
let (_, du, dv) = self.derivs(u, v);
if let Some(n) = unit(cross(du, dv)) {
return n;
}
let [(u0, u1), (v0, v1)] = self.param_bounds();
let eps = 1e-7;
let (u2, v2) = (
(u + eps).clamp(u0, u1),
if v + eps <= v1 {
v + eps
} else {
(v - eps).max(v0)
},
);
let (_, du, dv) = self.derivs(u2, v2);
unit(cross(du, dv)).unwrap_or([0.0, 0.0, 1.0])
}
pub fn period(&self) -> (Option<f64>, Option<f64>) {
match self {
Surface::Plane(_) => (None, None),
Surface::Cylinder { .. } | Surface::Cone { .. } | Surface::Sphere { .. } => {
(Some(TAU), None)
}
Surface::Torus { .. } => (Some(TAU), Some(TAU)),
Surface::Nurbs(n) => {
let [(u0, u1), (v0, v1)] = n.range();
(
n.closed_along_u().then_some(u1 - u0),
n.closed_along_v().then_some(v1 - v0),
)
}
Surface::Extrusion { curve, .. } => (curve.period(), None),
Surface::Revolution { curve, .. } => (Some(TAU), curve.period()),
Surface::Offset { basis, .. } => basis.period(),
}
}
pub fn breaks(&self) -> [Vec<f64>; 2] {
match self {
Surface::Nurbs(n) => {
let [ru, rv] = n.range();
[interior_knots(&n.ku, ru), interior_knots(&n.kv, rv)]
}
Surface::Extrusion { curve, .. } => [curve.breaks(), Vec::new()],
Surface::Revolution { curve, .. } => [Vec::new(), curve.breaks()],
Surface::Offset { basis, .. } => basis.breaks(),
_ => [Vec::new(), Vec::new()],
}
}
pub fn param_bounds(&self) -> [(f64, f64); 2] {
match self {
Surface::Plane(_) => [(-INF, INF), (-INF, INF)],
Surface::Cylinder { .. } => [(0.0, TAU), (-INF, INF)],
Surface::Cone { r, half_angle, .. } => {
let t = half_angle.tan();
let apex = if t > 0.0 { -r / t } else { -INF };
[(0.0, TAU), (apex, INF)]
}
Surface::Sphere { .. } => [(0.0, TAU), (-FRAC_PI_2, FRAC_PI_2)],
Surface::Torus { .. } => [(0.0, TAU), (0.0, TAU)],
Surface::Nurbs(n) => n.range(),
Surface::Extrusion { curve, .. } => [curve.param_range(), (-INF, INF)],
Surface::Revolution { curve, .. } => [(0.0, TAU), curve.param_range()],
Surface::Offset { basis, .. } => basis.param_bounds(),
}
}
pub fn project(&self, p: P3, hint: Option<(f64, f64)>) -> Option<(f64, f64)> {
let (u, v) = match self {
Surface::Plane(f) => {
let d = sub(p, f.origin);
(dot(d, f.x), dot(d, f.y))
}
Surface::Cylinder { frame: f, .. } => {
(self.azimuth(f, p, hint), dot(sub(p, f.origin), f.z))
}
Surface::Cone {
frame: f,
r,
half_angle,
} => {
let d = sub(p, f.origin);
let h = dot(d, f.z);
let rho = norm(sub(d, mul(f.z, h)));
let t = half_angle.tan();
let v = ((rho - r) * t + h) / (1.0 + t * t);
(self.azimuth(f, p, hint), v.max(self.param_bounds()[1].0))
}
Surface::Sphere { frame: f, .. } => {
let d = sub(p, f.origin);
let h = dot(d, f.z);
let rho = norm(sub(d, mul(f.z, h)));
(self.azimuth(f, p, hint), h.atan2(rho))
}
Surface::Torus {
frame: f, major, ..
} => {
let u = self.azimuth(f, p, hint);
let (e, _) = ring(f, u);
let q = sub(sub(p, f.origin), mul(e, *major));
(u, dot(q, f.z).atan2(dot(q, e)).rem_euclid(TAU))
}
Surface::Offset { basis, .. } => {
let q = basis.project(p, hint)?;
self.newton(p, q).unwrap_or(q)
}
_ => {
let from_hint = hint.and_then(|h| self.newton(p, h));
let near = |q: (f64, f64)| dist2(self.point(q.0, q.1), p);
match from_hint {
Some(q) if near(q) <= 1e-12 * (1.0 + dot(p, p)) => q,
_ => {
let from_grid = self
.starts(p)
.into_iter()
.filter_map(|s| self.newton(p, s))
.min_by(|a, b| near(*a).total_cmp(&near(*b)));
match (from_hint, from_grid) {
(Some(a), Some(b)) => {
if near(a) <= near(b) {
a
} else {
b
}
}
(a, b) => a.or(b)?,
}
}
}
}
};
let (u, v) = self.past_bounds(p, (u, v));
let (pu, pv) = self.period();
Some(match hint {
Some((hu, hv)) => (
pu.map_or(u, |per| nearest(u, per, hu)),
pv.map_or(v, |per| nearest(v, per, hv)),
),
None => (u, v),
})
}
pub fn foot(&self, p: P3, start: (f64, f64)) -> Option<(f64, f64)> {
self.newton_within(p, start, self.extended_bounds())
}
fn extended_bounds(&self) -> [(f64, f64); 2] {
let bounds = self.param_bounds();
let along = match self {
Surface::Nurbs(_) => [true, true],
Surface::Extrusion { .. } => [true, false],
Surface::Revolution { .. } => [false, true],
Surface::Offset { basis, .. } => return basis.extended_bounds(),
_ => [false, false],
};
let widen = |(lo, hi): (f64, f64), extend: bool| {
if extend && (hi - lo).is_finite() {
let margin = EXTENSION * (hi - lo);
(lo - margin, hi + margin)
} else {
(lo, hi)
}
};
[widen(bounds[0], along[0]), widen(bounds[1], along[1])]
}
fn past_bounds(&self, p: P3, q: (f64, f64)) -> (f64, f64) {
let (bounds, wide) = (self.param_bounds(), self.extended_bounds());
let (pu, pv) = self.period();
let held = |x: f64, i: usize| {
wide[i] != bounds[i] && [pu, pv][i].is_none() && (x <= bounds[i].0 || x >= bounds[i].1)
};
if !held(q.0, 0) && !held(q.1, 1) {
return q;
}
let d = dist2(self.point(q.0, q.1), p);
if d.sqrt() <= 1e-9 * (1.0 + norm(p)) {
return q;
}
match self.newton_within(p, q, wide) {
Some(r) if dist2(self.point(r.0, r.1), p) < d => r,
_ => q,
}
}
fn azimuth(&self, f: &Frame, p: P3, hint: Option<(f64, f64)>) -> f64 {
let d = sub(p, f.origin);
let radial = sub(d, mul(f.z, dot(d, f.z)));
if norm(radial) < 1e-12 {
return hint.map_or(0.0, |h| h.0);
}
angle(f, p, 1.0, 1.0)
}
fn starts(&self, p: P3) -> Vec<(f64, f64)> {
if let Surface::Extrusion { curve, dir } = self {
let u = curve.project(p);
return vec![(u, dot(sub(p, curve.point(u)), *dir))];
}
if let Surface::Revolution {
curve,
axis_origin,
axis_dir,
} = self
{
let (t0, t1) = curve.param_range();
let (a, b) = (t0.max(-1.0), t1.min(1.0).max(t0.max(-1.0)));
let off_axis = |q: P3| {
let d = sub(q, *axis_origin);
norm(sub(d, mul(*axis_dir, dot(d, *axis_dir))))
};
let reference = (0..=REVOLUTION_SAMPLES)
.map(|k| curve.point(a + (b - a) * k as f64 / REVOLUTION_SAMPLES as f64))
.max_by(|x, y| off_axis(*x).total_cmp(&off_axis(*y)))
.unwrap_or(*axis_origin);
let frame = Frame::new(*axis_origin, *axis_dir, sub(reference, *axis_origin));
let Some(frame) = frame else {
return vec![(0.0, 0.0)];
};
let turn = angle(&frame, p, 1.0, 1.0);
let v = curve.project(add(
*axis_origin,
rotate(sub(p, *axis_origin), *axis_dir, -turn),
));
let u = turn - angle(&frame, curve.point(v), 1.0, 1.0);
return vec![(u.rem_euclid(TAU), v)];
}
let [(u0, u1), (v0, v1)] = self.param_bounds();
let n = match self {
Surface::Nurbs(s) => (2 * s.ctrl.len().max(s.ctrl[0].len())).max(16),
_ => 32,
};
let mut grid = Vec::with_capacity((n + 1) * (n + 1));
for i in 0..=n {
for j in 0..=n {
let (u, v) = (
u0 + (u1 - u0) * i as f64 / n as f64,
v0 + (v1 - v0) * j as f64 / n as f64,
);
let q = self.point(u, v);
grid.push((dist2(q, p), q, (u, v)));
}
}
grid.sort_by(|a, b| a.0.total_cmp(&b.0));
let mut out: Vec<(P3, (f64, f64))> = Vec::new();
for (_, q, uv) in grid {
if out.len() == MAX_STARTS {
break;
}
if out
.iter()
.all(|(o, _)| dist2(*o, q) > 1e-18 * (1.0 + dot(q, q)))
{
out.push((q, uv));
}
}
out.into_iter().map(|(_, uv)| uv).collect()
}
fn newton(&self, p: P3, start: (f64, f64)) -> Option<(f64, f64)> {
self.newton_within(p, start, self.param_bounds())
}
pub(super) fn approach(&self, p: P3, start: (f64, f64)) -> (f64, f64) {
self.descend(p, start, self.param_bounds()).0
}
fn newton_within(
&self,
p: P3,
start: (f64, f64),
bounds: [(f64, f64); 2],
) -> Option<(f64, f64)> {
let ((u, v), stalled) = self.descend(p, start, bounds);
if stalled {
return None;
}
let [(u0, u1), (v0, v1)] = bounds;
let (pu, pv) = self.period();
let (s, su, sv) = self.derivs(u, v);
let r = sub(p, s);
let nr = norm(r);
if nr <= 1e-6 * (1.0 + norm(p)) {
return Some((u, v));
}
let held =
|x: f64, lo: f64, hi: f64, per: Option<f64>| per.is_none() && (x <= lo || x >= hi);
let (hu, hv) = (held(u, u0, u1, pu), held(v, v0, v1, pv));
let (a, b, c) = (dot(su, su), dot(su, sv), dot(sv, sv));
let (g1, g2) = (dot(su, r), dot(sv, r));
let det = a * c - b * b;
let step = match (hu, hv) {
(true, true) => [0.0; 3],
(true, false) if c > 0.0 => mul(sv, g2 / c),
(false, true) if a > 0.0 => mul(su, g1 / a),
(false, false) if det > 0.0 => add(
mul(su, (c * g1 - b * g2) / det),
mul(sv, (a * g2 - b * g1) / det),
),
_ => return None,
};
(norm(step) <= 1e-9 * (1.0 + norm(p)) + FOOT_PRECISION * nr).then_some((u, v))
}
fn descend(
&self,
p: P3,
(mut u, mut v): (f64, f64),
[(u0, u1), (v0, v1)]: [(f64, f64); 2],
) -> ((f64, f64), bool) {
let (pu, pv) = self.period();
let keep = |x: f64, lo: f64, hi: f64, per: Option<f64>| {
if per.is_some() { x } else { x.clamp(lo, hi) }
};
let pinned = |x: f64, step: f64, lo: f64, hi: f64, per: Option<f64>| {
per.is_none() && ((x <= lo && step < 0.0) || (x >= hi && step > 0.0))
};
let close = 1e-12 * (1.0 + norm(p));
for _ in 0..NEWTON_STEPS {
let (s, su, sv) = self.derivs(u, v);
let r = sub(p, s);
if norm(r) <= close {
return ((u, v), false);
}
let (a, b, c) = (dot(su, su), dot(su, sv), dot(sv, sv));
let (g1, g2) = (dot(su, r), dot(sv, r));
let det = a * c - b * b;
let (mut du, mut dv) = if det > 1e-24 * (a * c).max(1e-300) {
((c * g1 - b * g2) / det, (a * g2 - b * g1) / det)
} else if a >= c && a > 0.0 {
(g1 / a, 0.0)
} else if c > 0.0 {
(0.0, g2 / c)
} else {
return ((u, v), true);
};
if pinned(u, du, u0, u1, pu) {
(du, dv) = (0.0, if c > 0.0 { g2 / c } else { 0.0 });
}
if pinned(v, dv, v0, v1, pv) {
(du, dv) = (
if a > 0.0 && !pinned(u, g1, u0, u1, pu) {
g1 / a
} else {
0.0
},
0.0,
);
}
let before = dot(r, r);
let (mut nu, mut nv) = (u, v);
for _ in 0..30 {
nu = keep(u + du, u0, u1, pu);
nv = keep(v + dv, v0, v1, pv);
let promised =
2.0 * (g1 * du + g2 * dv) - (a * du * du + 2.0 * b * du * dv + c * dv * dv);
let after = dist2(self.point(nu, nv), p);
if after <= before && before - after >= SUFFICIENT_DECREASE * promised {
break;
}
du *= 0.5;
dv *= 0.5;
}
let moved = (nu - u).abs().max((nv - v).abs());
(u, v) = (nu, nv);
if moved <= 1e-13 * (1.0 + u.abs().max(v.abs())) {
break;
}
}
((u, v), false)
}
}