use std::f64::consts::TAU;
use super::{Curve, NurbsSurface};
use crate::{
math::{Frame, Point3, Transform, Vec2, Vec3},
numeric::solve2,
tol,
};
#[derive(Clone, Debug, PartialEq)]
pub struct Plane {
pub frame: Frame,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Cylinder {
pub frame: Frame,
pub radius: f64,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Cone {
pub frame: Frame,
pub radius: f64,
pub half_angle: f64,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Sphere {
pub frame: Frame,
pub radius: f64,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Torus {
pub frame: Frame,
pub major: f64,
pub minor: f64,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Extrusion {
pub curve: Curve,
pub dir: Vec3,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Revolution {
pub curve: Curve,
pub origin: Point3,
pub axis: Vec3,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Ruled {
pub a: Curve,
pub a_range: (f64, f64),
pub b: Curve,
pub b_range: (f64, f64),
}
#[derive(Clone, Debug, PartialEq)]
pub enum Surface {
Plane(Plane),
Cylinder(Cylinder),
Cone(Cone),
Sphere(Sphere),
Torus(Torus),
Extrusion(Box<Extrusion>),
Revolution(Box<Revolution>),
Ruled(Box<Ruled>),
Nurbs(Box<NurbsSurface>),
}
fn d_radial(f: &Frame, u: f64) -> Vec3 {
f.y * u.cos() - f.x * u.sin()
}
fn angle_of(local: Vec3) -> f64 {
if local.x.abs() < 1e-300 && local.y.abs() < 1e-300 {
0.0
} else {
local.y.atan2(local.x).rem_euclid(TAU)
}
}
impl Surface {
pub fn kind(&self) -> &'static str {
match self {
Surface::Plane(_) => "plane",
Surface::Cylinder(_) => "cylinder",
Surface::Cone(_) => "cone",
Surface::Sphere(_) => "sphere",
Surface::Torus(_) => "torus",
Surface::Extrusion(_) => "extrusion",
Surface::Revolution(_) => "revolution",
Surface::Ruled(_) => "ruled",
Surface::Nurbs(_) => "nurbs",
}
}
pub fn eval(&self, u: f64, v: f64) -> Point3 {
self.d1(u, v).0
}
pub fn d1(&self, u: f64, v: f64) -> (Point3, Vec3, Vec3) {
match self {
Surface::Plane(s) => (s.frame.at(u, v), s.frame.x, s.frame.y),
Surface::Cylinder(s) => {
let f = &s.frame;
let e = f.radial(u);
(
f.origin + e * s.radius + f.z * v,
d_radial(f, u) * s.radius,
f.z,
)
}
Surface::Cone(s) => {
let f = &s.frame;
let (sa, ca) = s.half_angle.sin_cos();
let rho = s.radius + v * sa;
let e = f.radial(u);
(
f.origin + e * rho + f.z * (v * ca),
d_radial(f, u) * rho,
e * sa + f.z * ca,
)
}
Surface::Sphere(s) => {
let f = &s.frame;
let (sv, cv) = v.sin_cos();
let e = f.radial(u);
let r = s.radius;
(
f.origin + (e * cv + f.z * sv) * r,
d_radial(f, u) * (r * cv),
(f.z * cv - e * sv) * r,
)
}
Surface::Torus(s) => {
let f = &s.frame;
let (sv, cv) = v.sin_cos();
let e = f.radial(u);
let rho = s.major + s.minor * cv;
(
f.origin + e * rho + f.z * (s.minor * sv),
d_radial(f, u) * rho,
(f.z * cv - e * sv) * s.minor,
)
}
Surface::Extrusion(s) => {
let (p, d) = s.curve.d1(u);
(p + s.dir * v, d, s.dir)
}
Surface::Revolution(s) => {
let (q, dq) = s.curve.d1(v);
let rot = Transform::rotation(s.origin, s.axis, u);
let p = rot.point(q);
(p, s.axis.cross(p - s.origin), rot.vector(dq))
}
Surface::Ruled(s) => {
let (ta, sa) = (
s.a_range.0 + u * (s.a_range.1 - s.a_range.0),
s.a_range.1 - s.a_range.0,
);
let (tb, sb) = (
s.b_range.0 + u * (s.b_range.1 - s.b_range.0),
s.b_range.1 - s.b_range.0,
);
let (pa, da) = s.a.d1(ta);
let (pb, db) = s.b.d1(tb);
(
pa.lerp(pb, v),
da * (sa * (1.0 - v)) + db * (sb * v),
pb - pa,
)
}
Surface::Nurbs(s) => s.d1(u, v),
}
}
pub fn normal(&self, u: f64, v: f64) -> Vec3 {
match self {
Surface::Plane(s) => s.frame.z,
Surface::Cylinder(s) => s.frame.radial(u),
Surface::Cone(s) => {
let (sa, ca) = s.half_angle.sin_cos();
let rho = s.radius + v * sa;
let n = s.frame.radial(u) * ca - s.frame.z * sa;
if rho < 0.0 { -n } else { n }
}
Surface::Sphere(s) => {
let (sv, cv) = v.sin_cos();
s.frame.radial(u) * cv + s.frame.z * sv
}
Surface::Torus(s) => {
let (sv, cv) = v.sin_cos();
let n = s.frame.radial(u) * cv + s.frame.z * sv;
if s.major + s.minor * cv < 0.0 { -n } else { n }
}
_ => {
let (_, su, sv) = self.d1(u, v);
if let Some(n) = su.cross(sv).unit().filter(|_| su.cross(sv).norm() > 1e-12) {
return n;
}
if let Surface::Nurbs(n) = self {
let ((u0, u1), (v0, v1)) = n.domain();
let [_, su, sv, _, suv, _] = n.d2(u, v);
let (limit, top) = if su.norm() <= sv.norm() {
(suv.cross(sv), v - v0 > v1 - v)
} else {
(su.cross(suv), u - u0 > u1 - u)
};
if let Some(l) = limit.unit() {
return if top { -l } else { l };
}
}
for (du, dv) in [(0.0, 1e-6), (0.0, -1e-6), (1e-6, 0.0), (-1e-6, 0.0)] {
let (_, su, sv) = self.d1(u + du, v + dv);
if let Some(n) = su.cross(sv).unit() {
return n;
}
}
Vec3::ZERO
}
}
}
pub fn u_period(&self) -> Option<f64> {
match self {
Surface::Cylinder(_)
| Surface::Cone(_)
| Surface::Sphere(_)
| Surface::Torus(_)
| Surface::Revolution(_) => Some(TAU),
Surface::Extrusion(s) => s.curve.period(),
Surface::Nurbs(s) => s.u_period(),
Surface::Plane(_) | Surface::Ruled(_) => None,
}
}
pub fn v_period(&self) -> Option<f64> {
match self {
Surface::Torus(_) => Some(TAU),
Surface::Revolution(s) => s.curve.period(),
Surface::Nurbs(s) => s.v_period(),
_ => None,
}
}
pub fn u_breakpoints(&self, u0: f64, u1: f64) -> Vec<f64> {
match self {
Surface::Extrusion(s) => s.curve.breakpoints(u0, u1),
Surface::Ruled(s) => {
let map = |r: (f64, f64), c: &Curve| -> Vec<f64> {
let (lo, hi) = (r.0 + u0 * (r.1 - r.0), r.0 + u1 * (r.1 - r.0));
let (lo, hi) = (lo.min(hi), lo.max(hi));
c.breakpoints(lo, hi)
.into_iter()
.map(|t| (t - r.0) / (r.1 - r.0))
.collect()
};
let mut out = map(s.a_range, &s.a);
out.extend(map(s.b_range, &s.b));
out.sort_by(f64::total_cmp);
out.dedup();
out
}
Surface::Nurbs(s) => s.u_breakpoints(u0, u1),
_ => Vec::new(),
}
}
pub fn v_breakpoints(&self, v0: f64, v1: f64) -> Vec<f64> {
match self {
Surface::Revolution(s) => s.curve.breakpoints(v0, v1),
Surface::Nurbs(s) => s.v_breakpoints(v0, v1),
_ => Vec::new(),
}
}
pub fn transformed(&self, t: &Transform) -> Surface {
match self {
Surface::Plane(s) => Surface::Plane(Plane {
frame: s.frame.transformed(t),
}),
Surface::Cylinder(s) => Surface::Cylinder(Cylinder {
frame: s.frame.transformed(t),
..*s
}),
Surface::Cone(s) => Surface::Cone(Cone {
frame: s.frame.transformed(t),
..*s
}),
Surface::Sphere(s) => Surface::Sphere(Sphere {
frame: s.frame.transformed(t),
..*s
}),
Surface::Torus(s) => Surface::Torus(Torus {
frame: s.frame.transformed(t),
..*s
}),
Surface::Extrusion(s) => Surface::Extrusion(Box::new(Extrusion {
curve: s.curve.transformed(t),
dir: t.vector(s.dir),
})),
Surface::Revolution(s) => Surface::Revolution(Box::new(Revolution {
curve: s.curve.transformed(t),
origin: t.point(s.origin),
axis: t.vector(s.axis),
})),
Surface::Ruled(s) => Surface::Ruled(Box::new(Ruled {
a: s.a.transformed(t),
b: s.b.transformed(t),
..(**s).clone()
})),
Surface::Nurbs(s) => Surface::Nurbs(Box::new(s.transformed(t))),
}
}
pub fn project(&self, p: Point3) -> Vec2 {
match self {
Surface::Plane(s) => {
let l = s.frame.to_local(p);
Vec2::new(l.x, l.y)
}
Surface::Cylinder(s) => {
let l = s.frame.to_local(p);
Vec2::new(angle_of(l), l.z)
}
Surface::Cone(s) => {
let l = s.frame.to_local(p);
let rho = l.x.hypot(l.y);
let (sa, ca) = s.half_angle.sin_cos();
Vec2::new(angle_of(l), (rho - s.radius) * sa + l.z * ca)
}
Surface::Sphere(s) => {
let l = s.frame.to_local(p);
Vec2::new(angle_of(l), l.z.atan2(l.x.hypot(l.y)))
}
Surface::Torus(s) => {
let l = s.frame.to_local(p);
let rho = l.x.hypot(l.y);
Vec2::new(angle_of(l), l.z.atan2(rho - s.major).rem_euclid(TAU))
}
Surface::Extrusion(s) if s.curve.spline().is_some() => {
let (a, b) = s.curve.domain();
let spline = s.curve.spline().expect("checked above");
let u = spline.nearest(p, Some(s.dir), a, b);
let v = (p - s.curve.eval(u)).dot(s.dir);
self.refine_projection(p, std::iter::once(Vec2::new(u, v)))
}
Surface::Extrusion(s) => {
let (a, b) = finite_domain(&s.curve);
let seeds = curve_seeds(&s.curve, a, b)
.into_iter()
.map(|u| Vec2::new(u, (p - s.curve.eval(u)).dot(s.dir)));
self.refine_projection(p, seeds)
}
Surface::Revolution(s) => {
let (a, b) = finite_domain(&s.curve);
let frame = Frame::from_axis(s.origin, s.axis).unwrap_or(Frame::WORLD);
let ang = angle_of(frame.to_local(p));
let seeds = curve_seeds(&s.curve, a, b).into_iter().map(|v| {
let q = frame.to_local(s.curve.eval(v));
Vec2::new((ang - angle_of(q)).rem_euclid(TAU), v)
});
self.refine_projection(p, seeds)
}
Surface::Ruled(_) => {
let seeds = (0..=16)
.flat_map(|i| (0..=4).map(move |j| Vec2::new(i as f64 / 16.0, j as f64 / 4.0)));
self.refine_projection(p, seeds)
}
Surface::Nurbs(s) => s.project(p),
}
}
pub fn project_near(&self, p: Point3, hint: Vec2) -> Vec2 {
self.project_near_at(p, hint).0
}
pub fn project_near_at(&self, p: Point3, hint: Vec2) -> (Vec2, Point3, Vec3) {
let uv = self.project_near_raw(p, hint);
let (q, su, sv) = self.d1(uv.x, uv.y);
let out = self.toward(uv, hint, su);
let n = match self {
Surface::Plane(_)
| Surface::Cylinder(_)
| Surface::Cone(_)
| Surface::Sphere(_)
| Surface::Torus(_) => self.normal(out.x, out.y),
_ => su
.cross(sv)
.unit()
.filter(|_| su.cross(sv).norm() > 1e-12)
.unwrap_or_else(|| self.normal(out.x, out.y)),
};
(out, q, n)
}
pub(crate) fn project_near_d1(&self, p: Point3, hint: Vec2) -> (Vec2, Vec3, Vec3) {
let uv = self.project_near_raw(p, hint);
let (_, su, sv) = match self {
Surface::Nurbs(n) => n.d1_by_polys(uv.x, uv.y),
_ => self.d1(uv.x, uv.y),
};
(self.toward(uv, hint, su), su, sv)
}
fn project_near_raw(&self, p: Point3, hint: Vec2) -> Vec2 {
match self {
Surface::Extrusion(e) if e.curve.spline().is_some() => {
match extrusion_near(e, p, hint.x) {
Some(uv) if self.eval(uv.x, uv.y).dist(p) <= tol::LINEAR => uv,
_ => self.project(p),
}
}
Surface::Extrusion(_) | Surface::Revolution(_) | Surface::Ruled(_) => {
let local = self.refine_projection(p, std::iter::once(hint));
if self.eval(local.x, local.y).dist(p) <= tol::LINEAR {
local
} else {
self.project(p)
}
}
Surface::Nurbs(s) => s.project_near(p, hint),
_ => self.project(p),
}
}
fn toward(&self, uv: Vec2, hint: Vec2, su: Vec3) -> Vec2 {
let shift = |x: f64, h: f64, period: Option<f64>| match period {
Some(t) => x + ((h - x) / t).round() * t,
None => x,
};
let pole = || self.eval(hint.x, uv.y).dist(self.eval(uv.x, uv.y)) <= 1e-3 * tol::LINEAR;
let u = if su.norm() <= tol::LINEAR && pole() {
hint.x
} else {
shift(uv.x, hint.x, self.u_period())
};
Vec2::new(u, shift(uv.y, hint.y, self.v_period()))
}
fn refine_projection(&self, p: Point3, seeds: impl Iterator<Item = Vec2>) -> Vec2 {
let mut best = (f64::INFINITY, Vec2::ZERO);
for s in seeds {
let d = self.eval(s.x, s.y).dist(p);
if d < best.0 {
best = (d, s);
}
}
let mut uv = best.1;
for _ in 0..60 {
let (q, su, sv) = self.d1(uv.x, uv.y);
let r = q - p;
let Some((du, dv)) = solve2(
su.dot(su),
su.dot(sv),
su.dot(sv),
sv.dot(sv),
-su.dot(r),
-sv.dot(r),
) else {
break;
};
let next = Vec2::new(uv.x + du, uv.y + dv);
let done = du.abs() + dv.abs() <= 1e-15 * (1.0 + uv.x.abs() + uv.y.abs());
if self.eval(next.x, next.y).dist(p) > r.norm() * (1.0 + 1e-12) + 1e-15 {
break;
}
uv = next;
if done {
break;
}
}
let wrap = |x: f64, period: Option<f64>, start: f64| match period {
Some(t) => start + (x - start).rem_euclid(t),
None => x,
};
let u0 = match self {
Surface::Extrusion(s) => s.curve.domain().0,
_ => 0.0,
};
let v0 = match self {
Surface::Revolution(s) => s.curve.domain().0,
_ => 0.0,
};
Vec2::new(
wrap(uv.x, self.u_period(), u0),
wrap(uv.y, self.v_period(), v0),
)
}
}
fn extrusion_near(e: &Extrusion, p: Point3, mut u: f64) -> Option<Vec2> {
let flat = |w: Vec3| w - e.dir * w.dot(e.dir);
let mut step = f64::INFINITY;
for _ in 0..30 {
let (c, d1, d2) = e.curve.d2(u);
let (r, d1) = (flat(c - p), flat(d1));
let f = r.dot(d1);
let df = d1.norm2() + r.dot(flat(d2));
if df <= 0.0 {
return None;
}
step = f / df;
u -= step;
if step.abs() <= 1e-15 * (1.0 + u.abs()) {
break;
}
}
(step.abs() <= 1e-9 * (1.0 + u.abs())).then(|| Vec2::new(u, (p - e.curve.eval(u)).dot(e.dir)))
}
fn finite_domain(c: &Curve) -> (f64, f64) {
let (a, b) = c.domain();
(a.max(-1e4), b.min(1e4))
}
fn curve_seeds(c: &Curve, a: f64, b: f64) -> Vec<f64> {
let mut cuts = vec![a];
cuts.extend(c.breakpoints(a, b));
cuts.push(b);
let mut out = Vec::new();
for w in cuts.windows(2) {
for i in 0..8 {
out.push(w[0] + (w[1] - w[0]) * i as f64 / 8.0);
}
}
out.push(b);
out
}
#[cfg(test)]
mod tests {
use super::*;
use crate::geom::{BSpline, Circle};
fn frame() -> Frame {
Frame::new(Vec3::new(1.0, -2.0, 0.5), Vec3::new(0.2, 0.3, 1.0), Vec3::X).unwrap()
}
fn all() -> Vec<Surface> {
let f = frame();
let spline = BSpline::interpolate(&[
Vec3::new(0.0, 0.0, 0.0),
Vec3::new(2.0, 1.0, 0.0),
Vec3::new(4.0, 0.5, 0.0),
Vec3::new(6.0, 2.0, 0.0),
])
.unwrap();
let profile = Curve::BSpline(
BSpline::interpolate(&[
Vec3::new(5.0, 0.0, 0.0),
Vec3::new(6.0, 0.0, 2.0),
Vec3::new(5.5, 0.0, 4.0),
Vec3::new(7.0, 0.0, 6.0),
])
.unwrap(),
);
let circle = Curve::Circle(Circle {
frame: Frame::WORLD,
radius: 3.0,
});
vec![
Surface::Plane(Plane { frame: f }),
Surface::Cylinder(Cylinder {
frame: f,
radius: 4.0,
}),
Surface::Cone(Cone {
frame: f,
radius: 4.0,
half_angle: 0.4,
}),
Surface::Sphere(Sphere {
frame: f,
radius: 4.0,
}),
Surface::Torus(Torus {
frame: f,
major: 6.0,
minor: 2.0,
}),
Surface::Extrusion(Box::new(Extrusion {
curve: Curve::BSpline(spline),
dir: Vec3::new(0.0, 0.6, 0.8),
})),
Surface::Revolution(Box::new(Revolution {
curve: profile,
origin: Vec3::ZERO,
axis: Vec3::Z,
})),
Surface::Ruled(Box::new(Ruled {
a: circle.clone(),
a_range: (0.0, TAU),
b: circle.transformed(&Transform::translation(Vec3::new(0.0, 0.0, 5.0))),
b_range: (0.0, TAU),
})),
]
}
#[test]
fn derivatives_and_normals_match_differences() {
for s in all() {
let (u, v) = (0.7, 0.4);
let h = 1e-6;
let (_, su, sv) = s.d1(u, v);
let fu = (s.eval(u + h, v) - s.eval(u - h, v)) / (2.0 * h);
let fv = (s.eval(u, v + h) - s.eval(u, v - h)) / (2.0 * h);
assert!(su.dist(fu) < 1e-7, "{} su", s.kind());
assert!(sv.dist(fv) < 1e-7, "{} sv", s.kind());
let n = s.normal(u, v);
assert!(
n.dist(su.cross(sv).unit().unwrap()) < 1e-12,
"{} normal",
s.kind()
);
}
}
#[test]
fn a_spline_normal_at_a_pole_is_its_limit() {
let s = crate::geom::octant(2.0);
for u in [0.0, 0.3, 0.5, 1.0] {
let n = s.normal(u, 1.0);
assert!(n.dist(Vec3::Z) < 1e-14, "u {u}: {n:?}");
}
}
#[test]
fn projection_inverts_evaluation() {
for s in all() {
for &(u, v) in &[(0.7, 0.4), (2.5, 0.9), (5.9, 0.1)] {
let (u, v) = match s {
Surface::Ruled(_) => (u / 6.0, v),
Surface::Extrusion(_) | Surface::Revolution(_) => (u, v * 4.0),
_ => (u, v),
};
let p = s.eval(u, v);
let uv = s.project_near(p, Vec2::new(u, v));
assert!(
s.eval(uv.x, uv.y).dist(p) < 1e-9,
"{} at {u},{v}: {uv:?}",
s.kind()
);
assert!(
(uv.x - u).abs() < 1e-7 && (uv.y - v).abs() < 1e-7,
"{}",
s.kind()
);
}
}
}
}