use super::{BlendEdge, BlendError, BlendFace, BlendSpec, End, Mesh, Path, Profile, Section};
use crate::bspline;
use crate::math::*;
use crate::model::{BSpline, BSplineSurface, Surface};
use crate::spline;
const MAX_STEPS: usize = 20_000;
const MAX_FIT: usize = 8193;
const FIT: f64 = 1e-9;
#[derive(Clone, Copy, Debug)]
pub(super) enum Field {
Plane {
o: V,
n: V,
},
Cyl {
o: V,
a: V,
r: f64,
s: f64,
},
Cone {
apex: V,
a: V,
k: f64,
s: f64,
},
Sphere {
c: V,
r: f64,
s: f64,
},
Torus {
c: V,
a: V,
big: f64,
r: f64,
s: f64,
},
}
fn sign(convex: bool) -> f64 {
if convex { 1.0 } else { -1.0 }
}
impl Field {
pub(super) fn of(f: &BlendFace) -> Field {
match *f {
BlendFace::Plane { origin, normal } => Field::Plane {
o: V::from(origin),
n: V::from(normal).norm(),
},
BlendFace::Cylinder {
origin,
axis,
radius,
convex,
} => Field::Cyl {
o: V::from(origin),
a: V::from(axis).norm(),
r: radius,
s: sign(convex),
},
BlendFace::Cone {
apex,
axis,
slope,
convex,
} => Field::Cone {
apex: V::from(apex),
a: V::from(axis).norm(),
k: slope,
s: sign(convex),
},
BlendFace::Sphere {
center,
radius,
convex,
} => Field::Sphere {
c: V::from(center),
r: radius,
s: sign(convex),
},
BlendFace::Torus {
center,
axis,
major_radius,
minor_radius,
convex,
} => Field::Torus {
c: V::from(center),
a: V::from(axis).norm(),
big: major_radius,
r: minor_radius,
s: sign(convex),
},
}
}
pub(super) fn f(&self, p: V) -> f64 {
match *self {
Field::Plane { o, n } => (p - o).dot(n),
Field::Cyl { o, a, r, s } => s * ((p - o).reject(a).len() - r),
Field::Cone { apex, a, k, s } => {
let q = p - apex;
let h = q.dot(a);
let rho = (q - a * h).len();
s * (rho - k * h) / (1.0 + k * k).sqrt()
}
Field::Sphere { c, r, s } => s * ((p - c).len() - r),
Field::Torus { c, a, big, r, s } => {
let q = p - c;
let tube = c + q.reject(a).norm() * big;
s * ((p - tube).len() - r)
}
}
}
pub(super) fn grad(&self, p: V) -> V {
match *self {
Field::Plane { n, .. } => n,
Field::Cyl { o, a, s, .. } => (p - o).reject(a).norm() * s,
Field::Cone { apex, a, k, s } => {
let q = p - apex;
let radial = q.reject(a).norm();
(radial - a * k) * (s / (1.0 + k * k).sqrt())
}
Field::Sphere { c, s, .. } => (p - c).norm() * s,
Field::Torus { c, a, big, s, .. } => {
let q = p - c;
let tube = c + q.reject(a).norm() * big;
(p - tube).norm() * s
}
}
}
fn radius_near(&self, p: V) -> Option<f64> {
match *self {
Field::Plane { .. } => None,
Field::Cyl { r, .. } | Field::Sphere { r, .. } => Some(r),
Field::Cone { apex, a, k, .. } => {
let q = p - apex;
Some(q.reject(a).len() * (1.0 + k * k).sqrt())
}
Field::Torus { r, .. } => Some(r),
}
}
fn on_part(&self, p: V) -> bool {
match *self {
Field::Cone { apex, a, .. } => (p - apex).dot(a) > 0.0,
Field::Torus { c, a, .. } => (p - c).reject(a).len() > 0.0,
_ => true,
}
}
}
fn solve(fields: &[Field; 2], h: [f64; 2], x0: V, o: V, n: V, scale: f64, reach: f64) -> Option<V> {
let mut x = x0;
let tiny = 1e-15 * scale;
for _ in 0..60 {
let g = [fields[0].grad(x), fields[1].grad(x)];
let mut a = [
[g[0].x, g[0].y, g[0].z],
[g[1].x, g[1].y, g[1].z],
[n.x, n.y, n.z],
];
let mut b = [
h[0] - fields[0].f(x),
h[1] - fields[1].f(x),
-(x - o).dot(n),
];
let d = solve_dense(&mut a, &mut b, 3)?;
let dx = v(d[0], d[1], d[2]);
if !dx.is_finite() {
return None;
}
x = x + dx;
if (x - x0).len() > reach {
return None;
}
if dx.len() <= tiny {
break;
}
}
let ok = (0..2).all(|k| (fields[k].f(x) - h[k]).abs() <= 1e-10 * scale)
&& (x - o).dot(n).abs() <= 1e-10 * scale;
ok.then_some(x)
}
fn offset_point(fields: &[Field; 2], h: [f64; 2], c: V, t: V, scale: f64, reach: f64) -> Option<V> {
const STEPS: usize = 8;
let start = [fields[0].f(c), fields[1].f(c)];
let mut x = c;
for j in 1..=STEPS {
let w = j as f64 / STEPS as f64;
let target = [
start[0] + (h[0] - start[0]) * w,
start[1] + (h[1] - start[1]) * w,
];
let g = [fields[0].grad(x), fields[1].grad(x)];
let mut a = [
[g[0].x, g[0].y, g[0].z],
[g[1].x, g[1].y, g[1].z],
[t.x, t.y, t.z],
];
let mut b = [
target[0] - fields[0].f(x),
target[1] - fields[1].f(x),
-(x - c).dot(t),
];
let y = solve_dense(&mut a, &mut b, 3)?;
let guess = x + v(y[0], y[1], y[2]);
x = solve(fields, target, guess, c, t, scale, reach)?;
}
Some(x)
}
pub(super) struct Rolled {
pub index: usize,
fields: [Field; 2],
h: [f64; 2],
mu: [f64; 2],
size: f64,
chamfer: bool,
convex: bool,
scale: f64,
points: Vec<V>,
closed: bool,
facets: [Option<Facets>; 2],
cuts: [Option<(V, V, Surface)>; 2],
margin: f64,
}
fn direction(p: &[V], i: usize) -> V {
let n = p.len();
let (a, b) = if i + 1 < n {
(p[i], p[i + 1])
} else {
(p[n - 2], p[n - 1])
};
(b - a).norm()
}
impl Rolled {
pub(super) fn new(spec: &BlendSpec, i: usize) -> Result<Rolled, BlendError> {
let e = &spec.edges[i];
let Path::Curve { points, facets } = &e.path else {
return Err(BlendError::Invalid(format!("edge {i} is not a curve")));
};
let size = spec.size;
if !(size > 0.0 && size.is_finite()) {
return Err(BlendError::Invalid("the size must be positive".into()));
}
let mut pts: Vec<V> = points.iter().map(|p| V::from(*p)).collect();
pts.dedup();
if pts.len() < 2 || pts.iter().any(|p| !p.is_finite()) {
return Err(BlendError::Invalid(format!(
"edge {i}: a curve needs at least two points"
)));
}
let closed = e.from == e.to;
if closed && pts.len() > 2 && pts[0] == pts[pts.len() - 1] {
pts.pop();
}
if closed && pts.len() < 3 {
return Err(BlendError::Invalid(format!(
"edge {i}: a closed curve needs at least three points"
)));
}
let fields = [Field::of(&e.faces[0]), Field::of(&e.faces[1])];
if fields.iter().all(|f| matches!(f, Field::Plane { .. })) {
return Err(BlendError::Invalid(format!(
"edge {i}: two planes meet in a line"
)));
}
let sigma = sign(e.convex);
let chamfer = spec.profile == Profile::Chamfer;
let h = if chamfer {
[0.0; 2]
} else {
[-sigma * size; 2]
};
let length: f64 = pts.windows(2).map(|w| (w[1] - w[0]).len()).sum::<f64>()
+ if closed {
(pts[0] - pts[pts.len() - 1]).len()
} else {
0.0
};
let scale = length + size;
let mut margin = size;
for f in &fields {
if let Some(r) = f.radius_near(pts[0]) {
margin = margin.min(0.5 * r);
}
}
if let Some(c) = e.margin
&& c > 0.0
{
margin = margin.min(c);
}
let mut mu = [0.0; 2];
for k in 0..2 {
mu[k] = if e.convex {
margin
} else if e.faces[k].curved() {
-margin
} else {
0.0
};
}
let facets = [
Facets::new(fields[0], &facets[0]),
Facets::new(fields[1], &facets[1]),
];
let mut r = Rolled {
index: i,
fields,
h,
mu,
size,
chamfer,
convex: e.convex,
scale,
points: pts,
closed,
facets,
cuts: [None, None],
margin,
};
if !closed {
for end in 0..2 {
r.cuts[end] = Some(r.cut(e, end)?);
}
}
Ok(r)
}
fn cut(&self, e: &BlendEdge, end: usize) -> Result<(V, V, Surface), BlendError> {
let p = &self.points;
let (at, d_out) = if end == 0 {
(p[0], direction(p, 0) * -1.0)
} else {
(p[p.len() - 1], direction(p, p.len() - 2))
};
let ext = 0.25 * (self.size + self.margin);
match &e.ends[end] {
End::Plane { origin, normal } => {
let n = V::from(*normal).norm();
Ok((
V::from(*origin),
n,
Surface::Plane {
origin: *origin,
normal: n.arr(),
},
))
}
End::Open { face } => {
let (o, n) = match face {
Some((o, n)) => {
let n = V::from(*n).norm();
(V::from(*o) + n * ext, n)
}
None => (at + d_out * ext, d_out),
};
Ok((
o,
n,
Surface::Plane {
origin: o.arr(),
normal: n.arr(),
},
))
}
_ => Err(BlendError::Invalid(format!(
"edge {}: a blend along a curve ends only on a plane or in the air",
self.index
))),
}
}
fn tangent(&self, x: V) -> V {
self.fields[0].grad(x).cross(self.fields[1].grad(x))
}
fn spine_in(&self, guess: V, o: V, n: V, reach: f64) -> Option<V> {
solve(&self.fields, self.h, guess, o, n, self.scale, reach)
}
fn spine_at_edge(&self, e: V, d: V) -> Option<V> {
offset_point(
&self.fields,
self.h,
e,
d,
self.scale,
4.0 * (self.size + self.margin) + self.scale * 0.25,
)
}
fn feet(&self, c: V) -> Option<[V; 2]> {
if !self.chamfer {
let f = [
c - self.fields[0].grad(c) * self.h[0],
c - self.fields[1].grad(c) * self.h[1],
];
return (self.fields[0].on_part(f[0]) && self.fields[1].on_part(f[1])).then_some(f);
}
let t = self.tangent(c).norm();
let g = [self.fields[0].grad(c), self.fields[1].grad(c)];
let mut out = [V::default(); 2];
for k in 0..2 {
let w = g[k].cross(t).norm();
let s = w.dot(g[1 - k]);
let w = if (self.convex && s > 0.0) || (!self.convex && s < 0.0) {
w * -1.0
} else {
w
};
let d = self.size;
let mut x = c + w * d;
let mut ok = false;
for _ in 0..60 {
let gk = self.fields[k].grad(x);
let r = x - c;
let mut a = [
[gk.x, gk.y, gk.z],
[t.x, t.y, t.z],
[2.0 * r.x, 2.0 * r.y, 2.0 * r.z],
];
let mut b = [-self.fields[k].f(x), -r.dot(t), d * d - r.dot(r)];
let dx = solve_dense(&mut a, &mut b, 3)?;
let dx = v(dx[0], dx[1], dx[2]);
x = x + dx;
if !x.is_finite() || (x - c).len() > 4.0 * d {
return None;
}
if dx.len() <= 1e-15 * self.scale {
ok = true;
break;
}
}
if !ok && self.fields[k].f(x).abs() > 1e-10 * self.scale {
return None;
}
if !self.fields[k].on_part(x) || (x - c).dot(w) <= 0.0 {
return None;
}
out[k] = x;
}
Some(out)
}
fn corner(&self, c: V, t: V) -> Option<V> {
let e = if self.chamfer {
c
} else {
offset_point(
&self.fields,
[0.0; 2],
c,
t,
self.scale,
4.0 * (self.size + self.margin) + 0.25 * self.scale,
)?
};
let g = [self.fields[0].grad(e), self.fields[1].grad(e)];
let mut a = [
[g[0].x, g[0].y, g[0].z],
[g[1].x, g[1].y, g[1].z],
[t.x, t.y, t.z],
];
let mut b = [
self.mu[0] - self.fields[0].f(e),
self.mu[1] - self.fields[1].f(e),
0.0,
];
let y = solve_dense(&mut a, &mut b, 3)?;
let q = e + v(y[0], y[1], y[2]);
q.is_finite().then_some(q)
}
fn ring_exact(&self, c: V, n: usize, sides: [usize; 2]) -> Option<Vec<V>> {
let feet = self.feet(c)?;
let t = self.tangent(c).norm();
let mut ring = Vec::with_capacity(n + 8);
if self.chamfer {
ring.push(feet[0]);
ring.push(feet[1]);
} else {
let (ma, mb) = ((feet[0] - c).norm(), (feet[1] - c).norm());
let th = atan2(ma.cross(mb).len(), ma.dot(mb));
let w = (mb - ma * ma.dot(mb)).norm();
ring.push(feet[0]);
for j in 1..n {
let a = th * j as f64 / n as f64;
ring.push(c + (ma * cos(a) + w * sin(a)) * self.size);
}
ring.push(feet[1]);
}
ring.extend(self.rest(c, t, feet, sides, [None, None])?);
Some(ring)
}
fn rest(
&self,
c: V,
t: V,
feet: [V; 2],
sides: [usize; 2],
inner: [Option<f64>; 2],
) -> Option<Vec<V>> {
let q = self.corner(c, t)?;
let beside = |k: usize| feet[k] + self.fields[k].grad(feet[k]) * self.mu[k];
let near =
|k: usize, d: f64| feet[k] + self.fields[k].grad(feet[k]) * (self.mu[k].signum() * d);
let along = |k: usize, from: V, to: V, out: &mut Vec<V>| {
let n = sides[k];
for j in 1..=n {
let x = from + (to - from) * (j as f64 / (n + 1) as f64);
let f = &self.fields[k];
out.push(x - f.grad(x) * (f.f(x) - self.mu[k]));
}
};
let mut out = Vec::new();
let pb = if self.mu[1] != 0.0 {
if let Some(d) = inner[1] {
out.push(near(1, d));
}
let p = beside(1);
out.push(p);
p
} else {
feet[1]
};
along(1, pb, q, &mut out);
out.push(q);
let pa = if self.mu[0] != 0.0 {
beside(0)
} else {
feet[0]
};
let mut tail = Vec::new();
along(0, q, pa, &mut tail);
out.extend(tail);
if self.mu[0] != 0.0 {
out.push(pa);
if let Some(d) = inner[0] {
out.push(near(0, d));
}
}
Some(out)
}
fn inner(&self) -> [Option<f64>; 2] {
[0, 1].map(|k| {
let f = self.facets[k].as_ref()?;
(self.mu[k] != 0.0 && 0.5 * f.band < self.mu[k].abs()).then_some(0.5 * f.band)
})
}
fn sides_at(&self, c: V) -> [usize; 2] {
let mut out = [0; 2];
let (Some(feet), Some(q)) = (self.feet(c), self.corner(c, self.tangent(c).norm())) else {
return out;
};
for k in 0..2 {
if self.mu[k] == 0.0 || matches!(self.fields[k], Field::Plane { .. }) {
continue;
}
let (n0, n1) = (self.fields[k].grad(feet[k]), self.fields[k].grad(q));
let ang = atan2(n0.cross(n1).len(), n0.dot(n1));
out[k] = ((ang / (PI / 16.0)).ceil() as usize)
.saturating_sub(1)
.min(16);
}
out
}
fn past(&self, c: V, end: usize) -> bool {
let Some((o, n, _)) = &self.cuts[end] else {
return false;
};
let sides = [8, 8];
match self.ring_exact(c, 4, sides) {
Some(r) => r.iter().all(|p| (*p - *o).dot(*n) > 1e-9 * self.scale),
None => false,
}
}
fn march(
&self,
x0: V,
d0: V,
close: bool,
stop: &dyn Fn(V, f64) -> bool,
) -> Result<Vec<V>, BlendError> {
let step_max = (self.scale / 48.0).min(0.5 * self.size + 0.25 * self.margin);
let step_min = 1e-7 * self.scale;
let max_len = 4.0 * self.scale + 40.0 * (self.size + self.margin);
let mut out = Vec::new();
let mut x = x0;
let mut dir = d0;
let mut step = step_max;
let mut travelled = 0.0;
loop {
let t0 = self.tangent(x).norm();
let t0 = if t0.dot(dir) < 0.0 { t0 * -1.0 } else { t0 };
if t0.len() < 0.5 {
return Err(self.too_large());
}
if close && travelled > 2.0 * step_max {
let back = x0 - x;
if back.dot(t0) > 0.0 && back.len() <= 1.25 * step {
return Ok(out);
}
}
let pred = x + t0 * step;
let next = self.spine_in(pred, pred, t0, 0.5 * step).and_then(|y| {
let t1 = self.tangent(y).norm();
let t1 = if t1.dot(t0) < 0.0 { t1 * -1.0 } else { t1 };
let turn = atan2(t0.cross(t1).len(), t0.dot(t1));
let moved = (y - x).len();
(turn <= 0.2 && (y - pred).len() <= 0.25 * step && moved >= 0.5 * step)
.then_some((y, t1, turn, moved))
});
match next {
Some((y, t1, turn, moved)) => {
out.push(y);
travelled += moved;
x = y;
dir = t1;
if turn < 0.05 {
step = (step * 1.5).min(step_max);
}
if !close && stop(x, travelled) {
return Ok(out);
}
}
None => {
step *= 0.5;
if step < step_min {
return Err(self.too_large());
}
}
}
if out.len() > MAX_STEPS || travelled > max_len {
return Err(BlendError::Invalid(format!(
"edge {}: its spine does not {}",
self.index,
if close { "close" } else { "reach its ends" }
)));
}
}
}
fn too_large(&self) -> BlendError {
BlendError::TooLarge(self.index)
}
pub(super) fn marched(&self) -> Result<Vec<V>, BlendError> {
let p = &self.points;
let d0 = direction(p, 0);
let x0 = self
.spine_at_edge(p[0], d0)
.ok_or_else(|| self.too_large())?;
if self.closed {
let mut out = vec![x0];
out.extend(self.march(x0, d0, true, &|_, _| false)?);
if out.len() < 4 {
return Err(BlendError::Invalid(format!(
"edge {}: its spine is too short to close",
self.index
)));
}
return Ok(out);
}
let n = p.len();
let (e0, e1) = (p[0], p[n - 1]);
let (d_start, d_end) = (d0, direction(p, n - 2));
let length: f64 = p.windows(2).map(|w| (w[1] - w[0]).len()).sum();
let ahead = self.march(x0, d0, false, &|x, gone| {
gone > 0.5 * length && (x - e1).dot(d_end) > 0.0 && self.past(x, 1)
})?;
let behind = self.march(x0, d0 * -1.0, false, &|x, _| {
(x - e0).dot(d_start) < 0.0 && self.past(x, 0)
})?;
let mut out: Vec<V> = behind.into_iter().rev().collect();
out.push(x0);
out.extend(ahead);
Ok(out)
}
}
struct Guide {
curve: BSpline<3>,
deriv: BSpline<3>,
range: [f64; 2],
}
fn guide(pts: &[V], closed: bool) -> Result<Guide, BlendError> {
let n = pts.len();
let mut ts = vec![0.0; n];
for k in 1..n {
ts[k] = ts[k - 1] + (pts[k] - pts[k - 1]).len();
}
let (all, params, range) = if closed {
let l = ts[n - 1] + (pts[0] - pts[n - 1]).len();
let mut all = Vec::with_capacity(3 * n + 1);
let mut params = Vec::with_capacity(3 * n + 1);
for (shift, last) in [(-l, false), (0.0, false), (l, true)] {
for k in 0..n {
all.push(pts[k].arr());
params.push(ts[k] + shift);
}
if last {
all.push(pts[0].arr());
params.push(2.0 * l);
}
}
(all, params, [0.0, l])
} else {
(
pts.iter().map(|p| p.arr()).collect(),
ts.clone(),
[0.0, ts[n - 1]],
)
};
let curve = spline::interpolate_curve(&all, ¶ms).map_err(BlendError::Invalid)?;
let deriv = bspline::derivative(&curve);
Ok(Guide {
curve,
deriv,
range,
})
}
struct Piece {
range: [f64; 2],
curves: Vec<BSpline<3>>,
patch: BSplineSurface,
eval: spline::Evaluator,
}
#[derive(Clone, Copy)]
struct Station {
t: f64,
c: V,
}
fn fit(r: &Rolled, g: &Guide, bounds: &[[f64; 2]]) -> Result<(Vec<Piece>, f64), BlendError> {
let (first, last) = (bounds[0][0], bounds[bounds.len() - 1][1]);
let spine = |t: f64| -> V {
let t = if r.closed && t >= last { first } else { t };
let o = V::from(bspline::eval(&g.curve, t));
let d = V::from(bspline::eval(&g.deriv, t)).norm();
r.spine_in(o, o, d, 0.25 * (r.size + r.margin) + 1e-6 * r.scale)
.unwrap_or(v(f64::NAN, f64::NAN, f64::NAN))
};
let foot = |k: usize, t: f64| -> V {
let c = spine(t);
match r.feet(c) {
Some(f) => f[k],
None => v(f64::NAN, f64::NAN, f64::NAN),
}
};
let s_fn = |t: f64| spine(t).arr();
let a_fn = |t: f64| foot(0, t).arr();
let b_fn = |t: f64| foot(1, t).arr();
let mut pieces = Vec::new();
let mut worst: f64 = 0.0;
for &range in bounds {
let mut tol = FIT * r.scale;
let mut tries = 0;
loop {
let fs: [&dyn Fn(f64) -> [f64; 3]; 3] = [&s_fn, &a_fn, &b_fn];
let fitted = spline::fit_curves(&fs, range, tol, MAX_FIT).map_err(|e| {
BlendError::Invalid(format!(
"edge {}: its spine could not be fitted: {e}",
r.index
))
})?;
if fitted
.curves
.iter()
.any(|c| c.control.iter().flatten().any(|x| !x.is_finite()))
{
return Err(r.too_large());
}
let (patch, err) = if r.chamfer {
let p = spline::ruled_surface(&fitted.curves[1], &fitted.curves[2])
.map_err(BlendError::Invalid)?;
(p, fitted.error)
} else {
let c = spline::canal_surface(
&fitted.curves[0],
&fitted.curves[1],
&fitted.curves[2],
r.size,
)
.map_err(|e| BlendError::Invalid(format!("edge {}: {e}", r.index)))?;
(c.surface, c.error.max(fitted.error))
};
if err > 10.0 * FIT * r.scale && tries < 2 {
tol *= 0.125;
tries += 1;
continue;
}
worst = worst.max(err);
let eval = spline::Evaluator::new(&patch).map_err(BlendError::Invalid)?;
pieces.push(Piece {
range,
curves: fitted.curves,
patch,
eval,
});
break;
}
}
Ok((pieces, worst))
}
fn splits(r: &Rolled, marched: &[V], l: f64) -> Vec<[f64; 2]> {
let n = marched.len();
let mut ts = vec![0.0; n];
for k in 1..n {
ts[k] = ts[k - 1] + (marched[k] - marched[k - 1]).len();
}
let mut cross: Vec<f64> = Vec::new();
for k in 0..2 {
let Some(f) = &r.facets[k] else {
continue;
};
let mut pts: Vec<(f64, V)> = Vec::with_capacity(n + 1);
for j in 0..=n {
let (t, c) = if j == n {
(l, marched[0])
} else {
(ts[j], marched[j])
};
if let Some(feet) = r.feet(c) {
pts.push((t, feet[k]));
}
}
cross.extend(f.rough_crossings(&pts));
}
if cross.is_empty() {
return vec![[0.0, 0.5 * l], [0.5 * l, l]];
}
cross.sort_by(f64::total_cmp);
let m = cross.len();
let gaps: Vec<(f64, f64)> = (0..m)
.map(|i| {
let (a, b) = (
cross[i],
if i + 1 < m {
cross[i + 1]
} else {
cross[0] + l
},
);
let mid = 0.5 * (a + b);
(if mid >= l { mid - l } else { mid }, b - a)
})
.collect();
let best = |from: f64, to: f64| -> Option<f64> {
gaps.iter()
.flat_map(|g| [(g.0 - l, g.1), (g.0, g.1), (g.0 + l, g.1)])
.filter(|g| g.0 >= from && g.0 <= to)
.fold(None, |acc: Option<(f64, f64)>, g| match acc {
Some(a) if a.1 >= g.1 => Some(a),
_ => Some(g),
})
.map(|g| g.0)
};
let s1 = best(0.0, l).filter(|&t| t < l).unwrap_or(0.0);
let s1 = if s1 > 0.5 * l { s1 - l } else { s1 };
let s2 = best(s1 + 0.3 * l, s1 + 0.7 * l).unwrap_or(s1 + 0.5 * l);
vec![[s1, s2], [s2, s1 + l]]
}
fn median_gap(ts: &[f64]) -> f64 {
let mut g: Vec<f64> = ts.windows(2).map(|w| w[1] - w[0]).collect();
if g.is_empty() {
return 0.0;
}
g.sort_by(f64::total_cmp);
g[g.len() / 2]
}
fn piece_of(pieces: &[Piece], t: f64) -> &Piece {
pieces
.iter()
.find(|p| t <= p.range[1])
.unwrap_or(&pieces[pieces.len() - 1])
}
fn base_stations(pieces: &[Piece], sag: f64) -> Vec<f64> {
let mut out = Vec::new();
for p in pieces {
let at = |t: f64| -> [V; 3] { [0, 1, 2].map(|k| V::from(bspline::eval(&p.curves[k], t))) };
let [a, b] = p.range;
let mut ts = Vec::new();
fn split(
at: &dyn Fn(f64) -> [V; 3],
t0: f64,
t1: f64,
sag: f64,
depth: u32,
out: &mut Vec<f64>,
) {
let (p0, p1, pm) = (at(t0), at(t1), at(0.5 * (t0 + t1)));
let far = (0..3).any(|k| {
let mid = (p0[k] + p1[k]) * 0.5;
(pm[k] - mid).len() > sag
});
if far && depth < 10 {
split(at, t0, 0.5 * (t0 + t1), sag, depth + 1, out);
split(at, 0.5 * (t0 + t1), t1, sag, depth + 1, out);
} else {
out.push(t1);
}
}
ts.push(a);
for k in 0..8 {
let t0 = a + (b - a) * k as f64 / 8.0;
let t1 = if k == 7 {
b
} else {
a + (b - a) * (k + 1) as f64 / 8.0
};
split(&at, t0, t1, sag, 0, &mut ts);
}
out.extend(ts);
}
out.sort_by(f64::total_cmp);
out.dedup();
out
}
struct Facets {
field: Field,
tris: Vec<[V; 3]>,
creases: Vec<(V, V, V)>,
band: f64,
grid: Grid,
}
struct Grid {
lo: V,
cell: f64,
dims: [usize; 3],
cells: Vec<Vec<u32>>,
}
fn bbox(pts: &[V]) -> (V, V) {
let mut lo = v(f64::INFINITY, f64::INFINITY, f64::INFINITY);
let mut hi = v(f64::NEG_INFINITY, f64::NEG_INFINITY, f64::NEG_INFINITY);
for p in pts {
lo = v(lo.x.min(p.x), lo.y.min(p.y), lo.z.min(p.z));
hi = v(hi.x.max(p.x), hi.y.max(p.y), hi.z.max(p.z));
}
(lo, hi)
}
impl Grid {
fn new(tris: &[[V; 3]]) -> Grid {
let all: Vec<V> = tris.iter().flatten().copied().collect();
let (lo, hi) = bbox(&all);
let d = hi - lo;
let cell = (d.x.max(d.y).max(d.z) / 48.0).max(1e-9);
let dims = [d.x, d.y, d.z].map(|x| ((x / cell) as usize + 1).min(64));
let mut g = Grid {
lo,
cell,
dims,
cells: vec![Vec::new(); dims[0] * dims[1] * dims[2]],
};
for (i, t) in tris.iter().enumerate() {
let (a, b) = bbox(t);
let (i0, i1) = (g.index(a), g.index(b));
for x in i0[0]..=i1[0] {
for y in i0[1]..=i1[1] {
for z in i0[2]..=i1[2] {
let c = (x * g.dims[1] + y) * g.dims[2] + z;
g.cells[c].push(i as u32);
}
}
}
}
g
}
fn index(&self, p: V) -> [usize; 3] {
let q = p - self.lo;
let at = |x: f64, d: usize| {
let i = (x / self.cell).floor();
if i.is_nan() || i < 0.0 {
0
} else {
(i as usize).min(d - 1)
}
};
[
at(q.x, self.dims[0]),
at(q.y, self.dims[1]),
at(q.z, self.dims[2]),
]
}
fn near(&self, pts: &[V]) -> Vec<u32> {
let (lo, hi) = bbox(pts);
let (i0, i1) = (self.index(lo), self.index(hi));
let mut out = Vec::new();
for x in i0[0]..=i1[0] {
for y in i0[1]..=i1[1] {
for z in i0[2]..=i1[2] {
out.extend(&self.cells[(x * self.dims[1] + y) * self.dims[2] + z]);
}
}
}
out.sort_unstable();
out.dedup();
out
}
}
fn ray_triangle(o: V, d: V, t: &[V; 3]) -> Option<f64> {
let e1 = t[1] - t[0];
let e2 = t[2] - t[0];
let p = d.cross(e2);
let det = e1.dot(p);
if det.abs() <= 1e-300 {
return None;
}
let inv = 1.0 / det;
let s = o - t[0];
let u = s.dot(p) * inv;
let q = s.cross(e1);
let w = d.dot(q) * inv;
let eps = 1e-9;
if u < -eps || w < -eps || u + w > 1.0 + eps {
return None;
}
Some(e2.dot(q) * inv)
}
impl Facets {
fn new(field: Field, given: &[[[f64; 3]; 3]]) -> Option<Facets> {
if matches!(field, Field::Plane { .. }) || given.is_empty() {
return None;
}
let tris: Vec<[V; 3]> = given
.iter()
.map(|t| t.map(V::from))
.filter(|t| (t[1] - t[0]).cross(t[2] - t[0]).len() > 0.0)
.collect();
if tris.is_empty() {
return None;
}
let mut depth: f64 = 0.0;
for t in &tris {
for p in [
(t[0] + t[1] + t[2]) * (1.0 / 3.0),
(t[0] + t[1]) * 0.5,
(t[1] + t[2]) * 0.5,
(t[2] + t[0]) * 0.5,
] {
depth = depth.max(field.f(p).abs());
}
}
let key = |p: V| [p.x.to_bits(), p.y.to_bits(), p.z.to_bits()];
let mut edges: std::collections::BTreeMap<([u64; 3], [u64; 3]), Vec<usize>> =
std::collections::BTreeMap::new();
for (i, t) in tris.iter().enumerate() {
for k in 0..3 {
let (a, b) = (key(t[k]), key(t[(k + 1) % 3]));
let e = if a < b { (a, b) } else { (b, a) };
edges.entry(e).or_default().push(i);
}
}
let normal = |t: &[V; 3]| (t[1] - t[0]).cross(t[2] - t[0]).norm();
let mut creases = Vec::new();
for ((a, b), ts) in &edges {
if ts.len() != 2 {
continue;
}
let (n0, n1) = (normal(&tris[ts[0]]), normal(&tris[ts[1]]));
if n0.cross(n1).len() <= 1e-9 {
continue;
}
let p = v(
f64::from_bits(a[0]),
f64::from_bits(a[1]),
f64::from_bits(a[2]),
);
let q = v(
f64::from_bits(b[0]),
f64::from_bits(b[1]),
f64::from_bits(b[2]),
);
let m = (p + q) * 0.5;
let plane = (q - p).cross(field.grad(m)).norm();
if plane.len() > 0.5 {
creases.push((p, q, plane));
}
}
let grid = Grid::new(&tris);
Some(Facets {
field,
tris,
creases,
band: (4.0 * depth).max(1e-12),
grid,
})
}
fn depth(&self, foot: V) -> f64 {
let n = self.field.grad(foot);
let l = self.band;
let ends = [foot - n * l, foot + n * l];
let mut best: Option<f64> = None;
for i in self.grid.near(&ends) {
if let Some(s) = ray_triangle(foot, n * -1.0, &self.tris[i as usize])
&& s.abs() <= l
&& best.is_none_or(|b| s.abs() < b.abs())
{
best = Some(s);
}
}
best.unwrap_or(0.0)
}
fn warp(&self, x: V) -> V {
let h = self.field.f(x);
let w = 1.0 - h.abs() / self.band;
if w <= 0.0 {
return x;
}
let n = self.field.grad(x);
let foot = x - n * h;
x - n * (self.depth(foot) * w)
}
fn crossings(&self, c: &dyn Fn(f64) -> V, ts: &[f64], out: &mut Vec<(f64, V, usize)>) {
if self.creases.is_empty() {
return;
}
let short = self
.creases
.iter()
.map(|cr| (cr.1 - cr.0).len())
.fold(f64::INFINITY, f64::min);
let step = 0.25 * short;
let pad = self.band;
let mut samples: Vec<(f64, V)> = Vec::new();
for w in ts.windows(2) {
let (t0, t1) = (w[0], w[1]);
let (p0, p1) = (c(t0), c(t1));
let k = (((p1 - p0).len() / step).ceil() as usize).clamp(1, 64);
if samples.is_empty() {
samples.push((t0, p0));
}
for j in 1..k {
let t = t0 + (t1 - t0) * j as f64 / k as f64;
samples.push((t, c(t)));
}
samples.push((t1, p1));
}
for w in samples.windows(2) {
let ((ta, pa), (tb, pb)) = (w[0], w[1]);
let (lo, hi) = bbox(&[pa, pb]);
let (lo, hi) = (lo - v(pad, pad, pad), hi + v(pad, pad, pad));
for (ci, &(p, q, nrm)) in self.creases.iter().enumerate() {
let (clo, chi) = bbox(&[p, q]);
if clo.x > hi.x
|| clo.y > hi.y
|| clo.z > hi.z
|| chi.x < lo.x
|| chi.y < lo.y
|| chi.z < lo.z
{
continue;
}
let (da, db) = ((pa - p).dot(nrm), (pb - p).dot(nrm));
if !((da < 0.0 && db >= 0.0) || (da > 0.0 && db <= 0.0)) {
continue;
}
let (mut lo_t, mut hi_t) = (ta, tb);
let side = da > 0.0;
for _ in 0..60 {
let m = 0.5 * (lo_t + hi_t);
if ((c(m) - p).dot(nrm) > 0.0) == side {
lo_t = m;
} else {
hi_t = m;
}
}
let t = 0.5 * (lo_t + hi_t);
let x = c(t);
let e = q - p;
let n = self.field.grad(x);
let (a, b, cc) = (e.dot(e), e.dot(n), n.dot(n));
let w0 = p - x;
let (d, ee) = (e.dot(w0), n.dot(w0));
let den = a * cc - b * b;
if den.abs() <= 1e-300 {
continue;
}
let s = (b * ee - cc * d) / den;
if !(-1e-9..=1.0 + 1e-9).contains(&s) {
continue;
}
out.push((t, p + e * s.clamp(0.0, 1.0), ci));
}
}
out.sort_by(|a, b| a.0.total_cmp(&b.0));
let near = 1e-9 * (ts[ts.len() - 1] - ts[0]).abs().max(1e-300);
out.dedup_by(|a, b| (a.0 - b.0).abs() <= near);
}
fn rough_crossings(&self, pts: &[(f64, V)]) -> Vec<f64> {
let mut out = Vec::new();
for w in pts.windows(2) {
let ((ta, pa), (tb, pb)) = (w[0], w[1]);
for &(p, q, nrm) in &self.creases {
let (da, db) = ((pa - p).dot(nrm), (pb - p).dot(nrm));
if !((da < 0.0 && db >= 0.0) || (da > 0.0 && db <= 0.0)) {
continue;
}
let f = da / (da - db);
let x = pa + (pb - pa) * f;
let e = q - p;
let s = (x - p).dot(e) / e.dot(e);
if (-0.01..=1.01).contains(&s) && (x - (p + e * s)).len() <= 4.0 * self.band + 1e-9
{
out.push(ta + (tb - ta) * f);
}
}
}
out
}
}
type Row = Vec<(f64, V)>;
fn rows_exact(
r: &Rolled,
stations: &[Station],
n: usize,
sides: [usize; 2],
) -> Result<Vec<Row>, BlendError> {
let mut out: Vec<Row> = Vec::new();
for (si, s) in stations.iter().enumerate() {
let ring = r
.ring_exact(s.c, if r.chamfer { 1 } else { n }, sides)
.ok_or_else(|| r.too_large())?;
if si == 0 {
out = vec![Vec::with_capacity(stations.len()); ring.len()];
}
if ring.len() != out.len() {
return Err(BlendError::Invalid(format!(
"edge {}: its sections differ",
r.index
)));
}
for (j, p) in ring.into_iter().enumerate() {
out[j].push((s.t, p));
}
}
Ok(out)
}
fn cut_row(row: &Row, o: V, n: V, end: usize) -> Option<Row> {
let d = |p: V| (p - o).dot(n);
let m = row.len();
if end == 0 {
let i = (0..m.saturating_sub(1)).find(|&i| d(row[i].1) > 0.0 && d(row[i + 1].1) <= 0.0)?;
let (a, b) = (row[i], row[i + 1]);
let (da, db) = (d(a.1), d(b.1));
let s = da / (da - db);
let p = (a.0 + (b.0 - a.0) * s, a.1 + (b.1 - a.1) * s);
let mut out = vec![p];
out.extend(row[i + 1..].iter().copied().filter(|x| x.0 > p.0));
Some(out)
} else {
let i = (0..m.saturating_sub(1))
.rev()
.find(|&i| d(row[i].1) <= 0.0 && d(row[i + 1].1) > 0.0)?;
let (a, b) = (row[i], row[i + 1]);
let (da, db) = (d(a.1), d(b.1));
let s = da / (da - db);
let p = (a.0 + (b.0 - a.0) * s, a.1 + (b.1 - a.1) * s);
let mut out: Row = row[..=i].iter().copied().filter(|x| x.0 < p.0).collect();
out.push(p);
Some(out)
}
}
fn zip(a: &Row, b: &Row) -> Vec<[(bool, usize); 3]> {
let (mut i, mut j) = (0usize, 0usize);
let mut out = Vec::with_capacity(a.len() + b.len());
while i + 1 < a.len() || j + 1 < b.len() {
let adv_a = if i + 1 >= a.len() {
false
} else if j + 1 >= b.len() {
true
} else {
let (na, nb) = (a[i + 1].0, b[j + 1].0);
if na != nb {
na < nb
} else {
(a[i + 1].1 - b[j].1).len() <= (b[j + 1].1 - a[i].1).len()
}
};
if adv_a {
out.push([(true, i), (true, i + 1), (false, j)]);
i += 1;
} else {
out.push([(true, i), (false, j + 1), (false, j)]);
j += 1;
}
}
out
}
fn zip_marked(
a: &Row,
b: &Row,
ma: &[(f64, (usize, usize))],
mb: &[(f64, (usize, usize))],
) -> Vec<[(bool, usize); 3]> {
let index = |row: &Row, t: f64| row.iter().position(|x| x.0 == t);
let mut pairs: Vec<(usize, usize)> = Vec::new();
for &(ta, id) in ma {
let Some(&(tb, _)) = mb.iter().find(|x| x.1 == id) else {
continue;
};
let (Some(ia), Some(ib)) = (index(a, ta), index(b, tb)) else {
continue;
};
if pairs.last().is_none_or(|&(pa, pb)| ia > pa && ib > pb) {
pairs.push((ia, ib));
}
}
if pairs.is_empty() {
return zip(a, b);
}
let mut out = Vec::new();
let mut from = (0usize, 0usize);
pairs.push((a.len() - 1, b.len() - 1));
for &(ia, ib) in &pairs {
if ia < from.0 || ib < from.1 {
continue;
}
let sa: Row = a[from.0..=ia].to_vec();
let sb: Row = b[from.1..=ib].to_vec();
for t in zip(&sa, &sb) {
out.push(t.map(|(first, i)| {
if first {
(true, i + from.0)
} else {
(false, i + from.1)
}
}));
}
from = (ia, ib);
}
out
}
pub(super) struct Built {
pub blends: Vec<u32>,
pub fit: f64,
}
fn shape(r: &Rolled, marched: &[V], segments: &dyn Fn(f64) -> u32) -> (usize, [usize; 2], f64) {
let mut sweep: f64 = 0.0;
let mut sides = [0usize; 2];
let step = (marched.len() / 16).max(1);
for c in marched.iter().step_by(step) {
if let Some(f) = r.feet(*c) {
let (ma, mb) = ((f[0] - *c).norm(), (f[1] - *c).norm());
sweep = sweep.max(atan2(ma.cross(mb).len(), ma.dot(mb)));
}
let s = r.sides_at(*c);
sides = [sides[0].max(s[0]), sides[1].max(s[1])];
}
let n = if r.chamfer {
1
} else {
segments(sweep.max(1e-3)).max(1) as usize
};
let ang = if r.chamfer {
PI / 2.0 / segments(PI / 2.0).max(1) as f64
} else {
sweep.max(1e-3) / n as f64
};
let sag = r.size * (1.0 - cos(0.5 * ang));
(n, sides, sag.max(1e-9 * r.scale))
}
pub(super) fn check(spec: &BlendSpec, i: usize) -> Result<(), BlendError> {
let r = Rolled::new(spec, i)?;
let marched = r.marched()?;
folds(&r, &marched)?;
let stations: Vec<Station> = stations_exact(&r, &marched)?;
let (n, sides, _) = shape(&r, &marched, &|_| 4);
let rws = rows_exact(&r, &stations, n, sides)?;
if !r.closed {
cut_all(&r, &rws)?;
}
Ok(())
}
fn stations_exact(r: &Rolled, marched: &[V]) -> Result<Vec<Station>, BlendError> {
let mut t = 0.0;
let mut out = Vec::with_capacity(marched.len());
for (k, &c) in marched.iter().enumerate() {
if k > 0 {
t += (c - marched[k - 1]).len();
}
r.feet(c).ok_or_else(|| r.too_large())?;
out.push(Station { t, c });
}
Ok(out)
}
fn folds(r: &Rolled, marched: &[V]) -> Result<(), BlendError> {
let n = marched.len();
for k in 0..n {
let c = marched[k];
let feet = r.feet(c).ok_or_else(|| r.too_large())?;
if r.chamfer {
continue;
}
let (ma, mb) = ((feet[0] - c).norm(), (feet[1] - c).norm());
if ma.dot(mb) <= -1.0 + 1e-6 {
return Err(r.too_large());
}
let (prev, next) = if r.closed {
(marched[(k + n - 1) % n], marched[(k + 1) % n])
} else if k == 0 || k + 1 == n {
continue;
} else {
(marched[k - 1], marched[k + 1])
};
let (u, w) = (c - prev, next - c);
let (lu, lw) = (u.len(), w.len());
if lu <= 0.0 || lw <= 0.0 {
continue;
}
let chord = next - prev;
let kappa = 2.0 * u.cross(w).len() / (lu * lw * chord.len());
let toward = ((prev + next) * 0.5 - c).reject(chord.norm()).norm();
let kv = toward * kappa;
let th = atan2(ma.cross(mb).len(), ma.dot(mb));
let wv = (mb - ma * ma.dot(mb)).norm();
for j in 0..=8 {
let a = th * j as f64 / 8.0;
let m = ma * cos(a) + wv * sin(a);
if r.size * kv.dot(m) >= 0.95 {
return Err(r.too_large());
}
}
}
Ok(())
}
fn cut_all(r: &Rolled, rws: &[Row]) -> Result<Vec<Row>, BlendError> {
let mut out = Vec::with_capacity(rws.len());
for row in rws {
let mut row = row.clone();
for end in 0..2 {
let Some((o, n, _)) = &r.cuts[end] else {
continue;
};
row = cut_row(&row, *o, *n, end).ok_or(BlendError::TooShort(r.index))?;
}
if row.len() < 2 || row[0].0 >= row[row.len() - 1].0 {
return Err(BlendError::TooShort(r.index));
}
out.push(row);
}
Ok(out)
}
pub(super) fn tool_into(
m: &mut Mesh,
spec: &BlendSpec,
i: usize,
segments: &dyn Fn(f64) -> u32,
) -> Result<Built, BlendError> {
let r = Rolled::new(spec, i)?;
let marched = r.marched()?;
folds(&r, &marched)?;
let g = guide(&marched, r.closed)?;
let bounds = if r.closed {
splits(&r, &marched, g.range[1])
} else {
vec![g.range]
};
let (pieces, fit_error) = fit(&r, &g, &bounds)?;
let (start, end) = (bounds[0][0], bounds[bounds.len() - 1][1]);
let (n, sides, sag) = shape(&r, &marched, segments);
let arc_rows = if r.chamfer { 2 } else { n + 1 };
let mut ts = base_stations(&pieces, sag);
let spans = ts.clone();
if r.closed {
ts.retain(|&t| t < end);
}
let inner = r.inner();
let ring_at = |t: f64| -> Option<Vec<V>> {
let p = piece_of(&pieces, t);
let c = V::from(bspline::eval(&p.curves[0], t));
let feet = [
V::from(bspline::eval(&p.curves[1], t)),
V::from(bspline::eval(&p.curves[2], t)),
];
let mut ring: Vec<V> = (0..arc_rows)
.map(|j| V::from(p.eval.eval(j as f64 / (arc_rows - 1) as f64, t)))
.collect();
ring.extend(r.rest(c, r.tangent(c).norm(), feet, sides, inner)?);
Some(ring)
};
type Pt = (f64, V, [bool; 2], Option<(usize, usize)>);
let mut table: Vec<Vec<Pt>> = Vec::new();
for (si, &t) in ts.iter().enumerate() {
let ring = ring_at(t).ok_or_else(|| r.too_large())?;
if si == 0 {
table = vec![Vec::with_capacity(ts.len()); ring.len()];
}
if ring.len() != table.len() {
return Err(BlendError::Invalid(format!(
"edge {}: its sections differ",
r.index
)));
}
for (j, x) in ring.into_iter().enumerate() {
table[j].push((t, x, [false; 2], None));
}
}
let near = 0.2 * median_gap(&ts);
let bounds_at: Vec<f64> = bounds.iter().flat_map(|b| *b).collect();
for k in 0..2 {
let Some(fac) = &r.facets[k] else { continue };
let contact_row = if k == 0 { 0 } else { arc_rows - 1 };
for (j, row) in table.iter_mut().enumerate() {
let within = row.iter().any(|x| r.fields[k].f(x.1).abs() < fac.band);
if j != contact_row && !within {
continue;
}
let mut cross: Vec<(f64, V, usize)> = Vec::new();
if j == contact_row {
let contact =
|t: f64| V::from(bspline::eval(&piece_of(&pieces, t).curves[1 + k], t));
fac.crossings(&contact, &spans, &mut cross);
} else {
let curve =
|t: f64| ring_at(t).map_or(v(f64::NAN, f64::NAN, f64::NAN), |ring| ring[j]);
fac.crossings(&curve, &spans, &mut cross);
for c in &mut cross {
c.1 = fac.warp(curve(c.0));
}
}
if r.closed {
cross.retain(|c| c.0 < end);
}
if cross.is_empty() {
continue;
}
let ct: Vec<f64> = cross.iter().map(|c| c.0).collect();
let close = |t: f64| {
let i = ct.partition_point(|&c| c < t);
[i.checked_sub(1), Some(i)]
.into_iter()
.flatten()
.filter_map(|i| ct.get(i))
.any(|&c| (c - t).abs() < near)
};
row.retain(|x| bounds_at.contains(&x.0) || x.2.iter().any(|&p| p) || !close(x.0));
for c in cross {
if !row.iter().any(|x| x.0 == c.0) {
let mut placed = [false; 2];
placed[k] = true;
row.push((c.0, c.1, placed, Some((k, c.2))));
}
}
row.sort_by(|a, b| a.0.total_cmp(&b.0));
}
for row in table.iter_mut() {
for x in row.iter_mut() {
if !x.2[k] {
x.1 = fac.warp(x.1);
}
}
}
}
let marks: Vec<Vec<(f64, (usize, usize))>> = table
.iter()
.map(|row| row.iter().filter_map(|x| x.3.map(|c| (x.0, c))).collect())
.collect();
let mut rws: Vec<Row> = table
.into_iter()
.map(|row| row.into_iter().map(|x| (x.0, x.1)).collect())
.collect();
if r.closed {
for row in &mut rws {
let first = row[0];
if first.0 != start {
return Err(BlendError::Invalid(format!(
"edge {}: a row misses the spine's start",
r.index
)));
}
row.push((end, first.1));
}
} else {
rws = cut_all(&r, &rws)?;
}
let blends: Vec<u32> = pieces
.iter()
.map(|p| m.surf(Surface::BSpline(p.patch.clone())))
.collect();
let faceted = m.surf(Surface::Faceted);
let e = &spec.edges[i];
let k = rws.len();
let plane_side = |face: usize| -> Option<u32> {
(r.mu[face] == 0.0 && !e.faces[face].curved()).then_some(face as u32)
};
let mut face_surf: [Option<u32>; 2] = [None, None];
for face in 0..2 {
if plane_side(face).is_some() {
face_surf[face] = Some(m.surf(super::face_surface(&e.faces[face])));
}
}
for j in 0..k {
let j1 = (j + 1) % k;
let surf = if j + 1 < arc_rows {
None
} else if j == arc_rows - 1 && r.mu[1] == 0.0 {
face_surf[1].or(Some(faceted))
} else if j1 == 0 && r.mu[0] == 0.0 {
face_surf[0].or(Some(faceted))
} else {
Some(faceted)
};
for tri in zip_marked(&rws[j], &rws[j1], &marks[j], &marks[j1]) {
let pts = tri.map(|(first, idx)| if first { rws[j][idx] } else { rws[j1][idx] });
let s = match surf {
Some(s) => s,
None => {
let lo = pts.iter().map(|x| x.0).fold(f64::INFINITY, f64::min);
let hi = pts.iter().map(|x| x.0).fold(f64::NEG_INFINITY, f64::max);
let mid = 0.5 * (lo + hi);
let pi = pieces
.iter()
.position(|p| mid <= p.range[1])
.unwrap_or(pieces.len() - 1);
blends[pi]
}
};
let ids = pts.map(|x| m.vert(x.1));
m.tri(ids, s);
}
}
if !r.closed {
for end in 0..2 {
let Some((_, _, cap)) = &r.cuts[end] else {
continue;
};
let pts: Vec<V> = rws
.iter()
.map(|row| {
if end == 0 {
row[0].1
} else {
row[row.len() - 1].1
}
})
.collect();
let s = m.surf(cap.clone());
cap_into(m, &pts, s)?;
}
}
Ok(Built {
blends,
fit: fit_error,
})
}
fn cap_into(m: &mut Mesh, pts: &[V], s: u32) -> Result<(), BlendError> {
let ids: Vec<u32> = pts.iter().map(|p| m.vert(*p)).collect();
let n = ids.len();
let mut forward = 0i32;
for k in 0..n {
let (a, b) = (ids[k], ids[(k + 1) % n]);
if a == b {
continue;
}
for t in &m.m.triangles {
for e in 0..3 {
if t[e] == a && t[(e + 1) % 3] == b {
forward += 1;
} else if t[e] == b && t[(e + 1) % 3] == a {
forward -= 1;
}
}
}
}
let order: Vec<V> = if forward > 0 {
pts.iter().rev().copied().collect()
} else {
pts.to_vec()
};
let mut nrm = V::default();
for k in 0..order.len() {
nrm = nrm + order[k].cross(order[(k + 1) % order.len()]);
}
m.polygon(&order, nrm.norm(), s)
}
pub(super) fn sections(
spec: &BlendSpec,
i: usize,
fracs: &[f64],
) -> Result<Vec<(V, V, Section)>, BlendError> {
let r = Rolled::new(spec, i)?;
let p = &r.points;
let mut cum = vec![0.0; p.len()];
for k in 1..p.len() {
cum[k] = cum[k - 1] + (p[k] - p[k - 1]).len();
}
let total = cum[p.len() - 1];
let mut out = Vec::with_capacity(fracs.len());
for &f in fracs {
let s = f.clamp(0.0, 1.0) * total;
let k = cum.partition_point(|&c| c < s).clamp(1, p.len() - 1);
let (a, b) = (p[k - 1], p[k]);
let seg = cum[k] - cum[k - 1];
let x = if seg > 0.0 {
(s - cum[k - 1]) / seg
} else {
0.0
};
let e = a + (b - a) * x;
let d = (b - a).norm();
let c = r.spine_at_edge(e, d).ok_or_else(|| r.too_large())?;
let feet = r.feet(c).ok_or_else(|| r.too_large())?;
let widths = [(feet[0] - e).len(), (feet[1] - e).len()];
out.push((
e,
d,
Section {
center: (!r.chamfer).then_some(c.arr()),
tangents: [feet[0].arr(), feet[1].arr()],
widths,
},
));
}
Ok(out)
}