use std::collections::{HashMap, HashSet};
use std::f64::consts::{FRAC_PI_2, FRAC_PI_4, PI, TAU};
use crate::nurbs::construct::perpendicular;
use crate::nurbs::{v3, V3};
use super::body::{Body, Edge, Face, TrimLoop};
use super::Surface;
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum BlendDeclined {
NotASolid,
BadSize,
NoSuchEdge { edge: usize },
UnsupportedEdge { edge: usize },
UnsupportedVertex { vertex: usize },
MixedConvexity { vertex: usize },
UnequalSetback { vertex: usize },
TooLarge { edge: usize },
TrimmedFace { face: usize },
NotWatertight { defects: usize },
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum Kind {
Chamfer,
Fillet,
}
impl Body {
pub fn fillet(
&self,
edges: &[usize],
radius: f64,
tolerance: f64,
) -> Result<Body, BlendDeclined> {
blend(self, edges, radius, Kind::Fillet, tolerance)
}
pub fn chamfer(
&self,
edges: &[usize],
distance: f64,
tolerance: f64,
) -> Result<Body, BlendDeclined> {
blend(self, edges, distance, Kind::Chamfer, tolerance)
}
}
struct Parts {
surfaces: Vec<Surface>,
vertices: Vec<V3>,
edges: Vec<Edge>,
faces: Vec<Face>,
}
impl Parts {
fn of(body: &Body) -> Parts {
Parts {
surfaces: body.surfaces().to_vec(),
vertices: body.vertices().to_vec(),
edges: body.edges().to_vec(),
faces: body.faces().to_vec(),
}
}
fn body(&self) -> Body {
Body::from_parts(
self.surfaces.clone(),
self.vertices.clone(),
self.edges.clone(),
self.faces.clone(),
)
}
fn vertex(&mut self, p: V3) -> usize {
self.vertices.push(p);
self.vertices.len() - 1
}
fn compact(&mut self) {
let mut used = vec![false; self.vertices.len()];
for e in &self.edges {
for &v in &e.vertices {
used[v] = true;
}
}
for l in self.faces.iter().filter_map(|f| f.loops.as_ref()).flatten() {
for &v in &l.vertices {
used[v] = true;
}
}
let mut renamed = vec![usize::MAX; self.vertices.len()];
let mut kept = Vec::with_capacity(self.vertices.len());
for (old, p) in self.vertices.iter().enumerate() {
if used[old] {
renamed[old] = kept.len();
kept.push(*p);
}
}
self.vertices = kept;
for e in &mut self.edges {
for v in &mut e.vertices {
*v = renamed[*v];
}
}
for l in self
.faces
.iter_mut()
.filter_map(|f| f.loops.as_mut())
.flatten()
{
for v in &mut l.vertices {
*v = renamed[*v];
}
}
}
}
fn blend(
body: &Body,
selection: &[usize],
size: f64,
kind: Kind,
tolerance: f64,
) -> Result<Body, BlendDeclined> {
if !(size > 0.0 && size.is_finite() && tolerance > 0.0 && tolerance.is_finite()) {
return Err(BlendDeclined::BadSize);
}
let mut selection = selection.to_vec();
selection.sort_unstable();
selection.dedup();
if let Some(&edge) = selection.iter().find(|&&e| e >= body.edges().len()) {
return Err(BlendDeclined::NoSuchEdge { edge });
}
if !body.is_valid_solid(tolerance) {
return Err(BlendDeclined::NotASolid);
}
if selection.is_empty() {
return Ok(body.clone());
}
let (rims, straight): (Vec<usize>, Vec<usize>) =
selection.iter().partition(|&&e| body.edges()[e].closed);
let mut parts = if straight.is_empty() {
Parts::of(body)
} else {
blend_straight(body, &straight, size, kind, tolerance)?
};
for &rim in &rims {
blend_rim(&mut parts, rim, size, kind, tolerance)?;
}
parts.compact();
let out = parts.body();
let defects = out.defects(tolerance);
if !defects.is_empty() || !out.shells().iter().all(|s| s.closed) {
return Err(BlendDeclined::NotWatertight {
defects: defects.len(),
});
}
Ok(out)
}
fn extent(vertices: &[V3]) -> f64 {
let (mut lo, mut hi) = ([f64::MAX; 3], [f64::MIN; 3]);
for p in vertices {
for k in 0..3 {
lo[k] = lo[k].min(p[k]);
hi[k] = hi[k].max(p[k]);
}
}
if vertices.is_empty() {
1.0
} else {
v3::dist(lo, hi).max(1e-12)
}
}
fn pair(a: usize, b: usize) -> (usize, usize) {
(a.min(b), a.max(b))
}
fn plane_normals(body: &Body, face: usize) -> Option<(V3, V3)> {
let f = &body.faces()[face];
match &body.surfaces()[f.surface] {
Surface::Plane { normal, .. } => Some((
*normal,
if f.flipped {
v3::scale(*normal, -1.0)
} else {
*normal
},
)),
_ => None,
}
}
fn straight_edge(body: &Body, edge: usize, eps: f64) -> Option<(usize, usize, V3, f64)> {
let e = &body.edges()[edge];
if e.closed || e.vertices.len() < 2 {
return None;
}
let (first, last) = (e.vertices[0], *e.vertices.last()?);
let (p, q) = (body.vertices()[first], body.vertices()[last]);
let length = v3::dist(p, q);
let dir = v3::normalize(v3::sub(q, p))?;
if first == last || length <= eps {
return None;
}
for &v in &e.vertices[1..e.vertices.len() - 1] {
let d = v3::sub(body.vertices()[v], p);
let off = v3::sub(d, v3::scale(dir, v3::dot(d, dir)));
if v3::norm(off) > eps {
return None;
}
}
Some((first, last, dir, length))
}
struct Sides<'a> {
body: &'a Body,
loops: HashMap<usize, Vec<TrimLoop>>,
}
impl Sides<'_> {
fn inward(&mut self, face: usize, edge: usize) -> Option<V3> {
let body = self.body;
let (normal, _) = plane_normals(body, face)?;
let e = &body.edges()[edge];
let (p, q) = (*e.vertices.first()?, *e.vertices.get(1)?);
let loops = self
.loops
.entry(face)
.or_insert_with(|| body.face_loops(face));
let mut sign = 0.0;
'rings: for l in loops.iter() {
let n = l.vertices.len();
for i in 0..n {
let step = (l.vertices[i], l.vertices[(i + 1) % n]);
if step == (p, q) {
sign = 1.0;
break 'rings;
}
if step == (q, p) {
sign = -1.0;
break 'rings;
}
}
}
if sign == 0.0 {
return None;
}
let along = v3::sub(body.vertices()[q], body.vertices()[p]);
v3::normalize(v3::scale(v3::cross(normal, along), sign))
}
}
struct Chosen {
edge: usize,
ends: [usize; 2],
dir: V3,
faces: [usize; 2],
normals: [V3; 2],
convex: f64,
setback: f64,
surface: usize,
boundary: Vec<usize>,
}
struct Corner {
vertex: usize,
edges: [usize; 3],
dirs: [V3; 3],
faces: [usize; 3],
selected: [bool; 3],
ends: [Option<usize>; 3],
points: [Option<usize>; 3],
}
impl Corner {
fn point_on(&self, face: usize) -> Option<usize> {
(0..3)
.find(|&i| self.faces[i] == face)
.and_then(|i| self.points[i])
}
}
fn segment_meets_box(p: [f64; 2], q: [f64; 2], lo: [f64; 2], hi: [f64; 2]) -> bool {
let (mut enter, mut leave) = (0.0f64, 1.0f64);
for k in 0..2 {
let d = q[k] - p[k];
if d.abs() < 1e-300 {
if p[k] < lo[k] || p[k] > hi[k] {
return false;
}
continue;
}
let (a, b) = ((lo[k] - p[k]) / d, (hi[k] - p[k]) / d);
enter = enter.max(a.min(b));
leave = leave.min(a.max(b));
if enter > leave {
return false;
}
}
true
}
fn solve3(rows: [V3; 3], rhs: V3) -> Option<V3> {
let det = v3::dot(rows[0], v3::cross(rows[1], rows[2]));
if det.abs() < 1e-12 {
return None;
}
let x = v3::add(
v3::add(
v3::scale(v3::cross(rows[1], rows[2]), rhs[0]),
v3::scale(v3::cross(rows[2], rows[0]), rhs[1]),
),
v3::scale(v3::cross(rows[0], rows[1]), rhs[2]),
);
Some(v3::scale(x, 1.0 / det))
}
fn section(
cylinder: &Surface,
origin: V3,
normal: V3,
from: V3,
to: V3,
tolerance: f64,
parts: &mut Parts,
) -> Option<Vec<usize>> {
let Surface::Cylinder { axis, radius, .. } = cylinder else {
return None;
};
let lean = v3::dot(*axis, normal);
if lean.abs() < 1e-9 {
return None;
}
let (ua, _) = cylinder.invert(from)?;
let (ub, _) = cylinder.invert(to)?;
let at = |u: f64| {
let p = cylinder.point(u, 0.0);
v3::add(
p,
v3::scale(*axis, v3::dot(v3::sub(origin, p), normal) / lean),
)
};
let slack = 1e-7 * (1.0 + radius + v3::dist(from, to));
if v3::dist(at(ua), from) > slack || v3::dist(at(ub), to) > slack {
return None;
}
let u = |k: f64, n: usize| ua + (ub - ua) * k / n as f64;
let mut n = 2usize;
while n < 2048 {
let worst = (0..n)
.map(|s| {
let (a, b) = (at(u(s as f64, n)), at(u(s as f64 + 1.0, n)));
v3::dist(at(u(s as f64 + 0.5, n)), v3::scale(v3::add(a, b), 0.5))
})
.fold(0.0, f64::max);
if worst <= tolerance {
break;
}
n *= 2;
}
Some((1..n).map(|s| parts.vertex(at(u(s as f64, n)))).collect())
}
fn blend_straight(
body: &Body,
selection: &[usize],
size: f64,
kind: Kind,
tolerance: f64,
) -> Result<Parts, BlendDeclined> {
let eps = 1e-9 * extent(body.vertices());
let mut parts = Parts::of(body);
let mut sides = Sides {
body,
loops: HashMap::new(),
};
let mut edge_faces: Vec<Vec<usize>> = vec![Vec::new(); body.edges().len()];
for (fi, f) in body.faces().iter().enumerate() {
for &e in &f.edges {
edge_faces[e].push(fi);
}
}
let mut ending_at: HashMap<usize, Vec<usize>> = HashMap::new();
let mut passed_through: HashSet<usize> = HashSet::new();
for (ei, e) in body.edges().iter().enumerate() {
let n = e.vertices.len();
if e.closed || n < 2 {
passed_through.extend(e.vertices.iter().copied());
continue;
}
ending_at.entry(e.vertices[0]).or_default().push(ei);
ending_at.entry(e.vertices[n - 1]).or_default().push(ei);
passed_through.extend(e.vertices[1..n - 1].iter().copied());
}
let mut chosen: Vec<Chosen> = Vec::with_capacity(selection.len());
let mut chosen_at: HashMap<usize, usize> = HashMap::new();
for &edge in selection {
let unsupported = BlendDeclined::UnsupportedEdge { edge };
let (first, last, dir, _) = straight_edge(body, edge, eps).ok_or(unsupported.clone())?;
let &[a, b] = edge_faces[edge].as_slice() else {
return Err(unsupported);
};
if a == b {
return Err(unsupported);
}
let (Some((_, na)), Some((_, nb))) = (plane_normals(body, a), plane_normals(body, b))
else {
return Err(unsupported);
};
let cos = v3::dot(na, nb);
if cos.abs() > 1.0 - 1e-9 {
return Err(unsupported);
}
let side = v3::dot(sides.inward(a, edge).ok_or(unsupported.clone())?, nb);
if side.abs() < 1e-9 {
return Err(unsupported);
}
let setback = match kind {
Kind::Chamfer => size,
Kind::Fillet => size * ((1.0 - cos) / (1.0 + cos)).sqrt(),
};
chosen_at.insert(edge, chosen.len());
chosen.push(Chosen {
edge,
ends: [first, last],
dir,
faces: [a, b],
normals: [na, nb],
convex: if side < 0.0 { 1.0 } else { -1.0 },
setback,
surface: usize::MAX,
boundary: Vec::new(),
});
}
let mut touched: Vec<usize> = chosen.iter().flat_map(|c| c.ends).collect();
touched.sort_unstable();
touched.dedup();
let mut corners: Vec<Corner> = Vec::with_capacity(touched.len());
let mut corner_at: HashMap<usize, usize> = HashMap::new();
let mut cut_back: HashMap<usize, f64> = HashMap::new();
for &vertex in &touched {
let unsupported = BlendDeclined::UnsupportedVertex { vertex };
let at = body.vertices()[vertex];
let Some(&[e0, e1, e2]) = ending_at.get(&vertex).map(Vec::as_slice) else {
return Err(unsupported);
};
if passed_through.contains(&vertex) {
return Err(unsupported);
}
let edges = [e0, e1, e2];
let mut dirs = [[0.0; 3]; 3];
for i in 0..3 {
let (first, _, dir, _) =
straight_edge(body, edges[i], eps).ok_or(unsupported.clone())?;
dirs[i] = if first == vertex {
dir
} else {
v3::scale(dir, -1.0)
};
}
let mut faces = [0usize; 3];
for (i, face) in faces.iter_mut().enumerate() {
let (j, k) = ((i + 1) % 3, (i + 2) % 3);
let mut common = edge_faces[edges[j]]
.iter()
.filter(|f| edge_faces[edges[k]].contains(f));
let (Some(&f), None) = (common.next(), common.next()) else {
return Err(unsupported);
};
if plane_normals(body, f).is_none() {
return Err(unsupported);
}
*face = f;
}
if faces[0] == faces[1] || faces[1] == faces[2] || faces[2] == faces[0] {
return Err(unsupported);
}
let selected = [0, 1, 2].map(|i| chosen_at.contains_key(&edges[i]));
let of = |i: usize| &chosen[chosen_at[&edges[i]]];
let mut turn = (0..3).filter(|&i| selected[i]).map(|i| of(i).convex);
let first_turn = turn.next().unwrap_or(1.0);
if turn.any(|t| t != first_turn) {
return Err(BlendDeclined::MixedConvexity { vertex });
}
let mut ends = [None; 3];
for k in 0..3 {
if selected[k] {
continue;
}
let (i, j) = ((k + 1) % 3, (k + 2) % 3);
let mut depth: Option<f64> = None;
for (face, other) in [(faces[i], j), (faces[j], i)] {
if !selected[other] {
continue;
}
let into = sides
.inward(face, edges[other])
.ok_or(unsupported.clone())?;
let reach = v3::dot(dirs[k], into);
if reach < 1e-6 {
return Err(unsupported);
}
let d = of(other).setback / reach;
if depth.is_some_and(|prev| (prev - d).abs() > 1e-7 * (1.0 + d.abs())) {
return Err(BlendDeclined::UnequalSetback { vertex });
}
depth = Some(d);
}
if let Some(d) = depth {
*cut_back.entry(edges[k]).or_insert(0.0) += d;
ends[k] = Some(parts.vertex(v3::add(at, v3::scale(dirs[k], d))));
}
}
let mut points = [None; 3];
for i in 0..3 {
let (j, k) = ((i + 1) % 3, (i + 2) % 3);
points[i] = match (selected[j], selected[k]) {
(true, true) => {
let into_j = sides
.inward(faces[i], edges[j])
.ok_or(unsupported.clone())?;
let into_k = sides
.inward(faces[i], edges[k])
.ok_or(unsupported.clone())?;
let (along_j, along_k) = (v3::dot(dirs[j], into_k), v3::dot(dirs[k], into_j));
if along_j.abs() < 1e-6 || along_k.abs() < 1e-6 {
return Err(unsupported);
}
let p = v3::add(
at,
v3::add(
v3::scale(dirs[j], of(k).setback / along_j),
v3::scale(dirs[k], of(j).setback / along_k),
),
);
Some(parts.vertex(p))
}
(true, false) => ends[k],
(false, true) => ends[j],
(false, false) => None,
};
}
corner_at.insert(vertex, corners.len());
corners.push(Corner {
vertex,
edges,
dirs,
faces,
selected,
ends,
points,
});
}
for (&edge, &cut) in &cut_back {
let (_, _, _, length) =
straight_edge(body, edge, eps).ok_or(BlendDeclined::UnsupportedEdge { edge })?;
if cut >= length - eps {
return Err(BlendDeclined::TooLarge { edge });
}
}
let rail = |c: &Chosen, side: usize| -> Option<[usize; 2]> {
Some([
corners[corner_at[&c.ends[0]]].point_on(c.faces[side])?,
corners[corner_at[&c.ends[1]]].point_on(c.faces[side])?,
])
};
for c in &chosen {
for side in 0..2 {
let [p, q] = rail(c, side).ok_or(BlendDeclined::UnsupportedEdge { edge: c.edge })?;
let run = v3::dot(v3::sub(parts.vertices[q], parts.vertices[p]), c.dir);
if run <= eps {
return Err(BlendDeclined::TooLarge { edge: c.edge });
}
}
}
for c in &chosen {
let declined = BlendDeclined::TooLarge { edge: c.edge };
let from = body.vertices()[c.ends[0]];
let length = v3::dist(from, body.vertices()[c.ends[1]]);
let mut own: Vec<usize> = c
.ends
.iter()
.flat_map(|v| corners[corner_at[v]].edges)
.collect();
own.push(c.edge);
for &face in &c.faces {
let into = sides
.inward(face, c.edge)
.ok_or(BlendDeclined::UnsupportedEdge { edge: c.edge })?;
let flat = |v: usize| {
let d = v3::sub(body.vertices()[v], from);
[v3::dot(d, c.dir), v3::dot(d, into)]
};
for &e in &body.faces()[face].edges {
if own.contains(&e) {
continue;
}
for w in body.edges()[e].vertices.windows(2) {
if segment_meets_box(
flat(w[0]),
flat(w[1]),
[eps, -eps],
[length - eps, c.setback + eps],
) {
return Err(declined);
}
}
}
}
}
for c in &mut chosen {
let unsupported = BlendDeclined::UnsupportedEdge { edge: c.edge };
let [na, nb] = c.normals;
let between = v3::add(na, nb);
let surface = match kind {
Kind::Chamfer => {
let [pa, _] = rail(c, 0).ok_or(unsupported.clone())?;
let [pb, _] = rail(c, 1).ok_or(unsupported.clone())?;
let (pa, pb) = (parts.vertices[pa], parts.vertices[pb]);
let n = v3::normalize(v3::cross(c.dir, v3::sub(pb, pa))).ok_or(unsupported)?;
let n = if v3::dot(n, between) < 0.0 {
v3::scale(n, -1.0)
} else {
n
};
Surface::plane(pa, n)
}
Kind::Fillet => {
let cos = v3::dot(na, nb);
let origin = v3::sub(
body.vertices()[c.ends[0]],
v3::scale(between, c.convex * size / (1.0 + cos)),
);
Surface::cylinder(origin, c.dir, size).with_x_dir(v3::scale(between, c.convex))
}
};
parts.surfaces.push(surface);
c.surface = parts.surfaces.len() - 1;
}
for corner in &corners {
for k in 0..3 {
let Some(end) = corner.ends[k] else { continue };
let e = &mut parts.edges[corner.edges[k]];
let (first, last) = (e.vertices[0], e.vertices[e.vertices.len() - 1]);
e.vertices = if first == corner.vertex {
vec![end, last]
} else {
vec![first, end]
};
}
}
for c in &mut chosen {
let unsupported = BlendDeclined::UnsupportedEdge { edge: c.edge };
let [a, b] = c.faces;
let (sa, sb) = (body.faces()[a].surface, body.faces()[b].surface);
let (ra, rb) = (
rail(c, 0).ok_or(unsupported.clone())?,
rail(c, 1).ok_or(unsupported)?,
);
parts.edges[c.edge] = Edge {
surfaces: pair(sa, c.surface),
vertices: ra.to_vec(),
closed: false,
};
parts.edges.push(Edge {
surfaces: pair(sb, c.surface),
vertices: rb.to_vec(),
closed: false,
});
let rail_b = parts.edges.len() - 1;
for slot in parts.faces[b].edges.iter_mut() {
if *slot == c.edge {
*slot = rail_b;
}
}
c.boundary = vec![c.edge, rail_b];
}
let mut fresh: Vec<usize> = Vec::new();
for corner in &corners {
let vertex = corner.vertex;
let unsupported = BlendDeclined::UnsupportedVertex { vertex };
let at = body.vertices()[vertex];
let which = |i: usize| chosen_at[&corner.edges[i]];
let count = corner.selected.iter().filter(|s| **s).count();
let convex = (0..3)
.find(|&i| corner.selected[i])
.map_or(1.0, |i| chosen[which(i)].convex);
let centre = || -> Option<V3> {
let n = [0, 1, 2].map(|i| plane_normals(body, corner.faces[i]).map(|(_, out)| out));
let w = solve3([n[0]?, n[1]?, n[2]?], [1.0; 3])?;
Some(v3::sub(at, v3::scale(w, convex * size)))
};
match count {
1 => {
let i = (0..3).find(|&i| corner.selected[i]).unwrap_or(0);
let (j, k) = ((i + 1) % 3, (i + 2) % 3);
let ci = which(i);
let (Some(from), Some(to)) = (corner.points[j], corner.points[k]) else {
return Err(unsupported);
};
let third = corner.faces[i];
let (normal, _) = plane_normals(body, third).ok_or(unsupported.clone())?;
let between = match kind {
Kind::Chamfer => Vec::new(),
Kind::Fillet => section(
&parts.surfaces[chosen[ci].surface].clone(),
at,
normal,
parts.vertices[from],
parts.vertices[to],
tolerance,
&mut parts,
)
.ok_or(unsupported)?,
};
let mut vertices = vec![from];
vertices.extend(between);
vertices.push(to);
parts.edges.push(Edge {
surfaces: pair(chosen[ci].surface, body.faces()[third].surface),
vertices,
closed: false,
});
let e = parts.edges.len() - 1;
parts.faces[third].edges.push(e);
chosen[ci].boundary.push(e);
}
2 => {
let k = (0..3).find(|&k| !corner.selected[k]).unwrap_or(0);
let (i, j) = ((k + 1) % 3, (k + 2) % 3);
let (ci, cj) = (which(i), which(j));
let (Some(from), Some(to)) = (corner.points[k], corner.ends[k]) else {
return Err(unsupported);
};
let between = match kind {
Kind::Chamfer => Vec::new(),
Kind::Fillet => {
let unequal = BlendDeclined::UnequalSetback { vertex };
let o = centre().ok_or(unsupported)?;
let (p, q) = (parts.vertices[from], parts.vertices[to]);
let off = |m: V3| {
v3::normalize(m).map_or(f64::MAX, |m| {
v3::dot(v3::sub(p, o), m).abs() + v3::dot(v3::sub(q, o), m).abs()
})
};
let (plus, minus) = (
v3::add(corner.dirs[i], corner.dirs[j]),
v3::sub(corner.dirs[i], corner.dirs[j]),
);
let normal = if off(plus) < off(minus) { plus } else { minus };
let normal = v3::normalize(normal).ok_or(unequal.clone())?;
section(
&parts.surfaces[chosen[ci].surface].clone(),
o,
normal,
p,
q,
tolerance,
&mut parts,
)
.ok_or(unequal)?
}
};
let mut vertices = vec![from];
vertices.extend(between);
vertices.push(to);
parts.edges.push(Edge {
surfaces: pair(chosen[ci].surface, chosen[cj].surface),
vertices,
closed: false,
});
let e = parts.edges.len() - 1;
chosen[ci].boundary.push(e);
chosen[cj].boundary.push(e);
}
_ => match kind {
Kind::Chamfer
if super::settings::settings().chamfer_corner
== super::settings::ChamferCorner::Facet =>
{
let mut at = [0usize; 3];
for (k, slot) in at.iter_mut().enumerate() {
*slot = corner.points[k].ok_or(unsupported.clone())?;
}
let p = at.map(|v| parts.vertices[v]);
let normal = v3::normalize(v3::cross(v3::sub(p[1], p[0]), v3::sub(p[2], p[0])))
.ok_or(unsupported.clone())?;
let gone = v3::sub(parts.vertices[vertex], p[0]);
let outward = if v3::dot(normal, gone) * convex >= 0.0 {
normal
} else {
v3::scale(normal, -1.0)
};
parts.surfaces.push(Surface::plane(p[0], outward));
let facet = parts.surfaces.len() - 1;
let mut around = Vec::with_capacity(3);
for k in 0..3 {
let (i, j) = ((k + 1) % 3, (k + 2) % 3);
let ck = which(k);
parts.edges.push(Edge {
surfaces: pair(chosen[ck].surface, facet),
vertices: vec![at[i], at[j]],
closed: false,
});
let e = parts.edges.len() - 1;
chosen[ck].boundary.push(e);
around.push(e);
}
fresh.push(parts.faces.len());
parts.faces.push(Face {
surface: facet,
edges: around,
flipped: false,
u_range: (0.0, 0.0),
v_range: (0.0, 0.0),
u_wraps: false,
v_wraps: false,
loops: None,
});
}
Kind::Chamfer => {
let mut rows = [[0.0; 3]; 3];
let mut rhs = [0.0; 3];
for i in 0..3 {
let Surface::Plane { origin, normal, .. } =
&parts.surfaces[chosen[which(i)].surface]
else {
return Err(unsupported);
};
rows[i] = *normal;
rhs[i] = v3::dot(*normal, *origin);
}
let apex = solve3(rows, rhs).ok_or(unsupported.clone())?;
let apex = parts.vertex(apex);
for k in 0..3 {
let (i, j) = ((k + 1) % 3, (k + 2) % 3);
let (ci, cj) = (which(i), which(j));
let to = corner.points[k].ok_or(unsupported.clone())?;
parts.edges.push(Edge {
surfaces: pair(chosen[ci].surface, chosen[cj].surface),
vertices: vec![apex, to],
closed: false,
});
let e = parts.edges.len() - 1;
chosen[ci].boundary.push(e);
chosen[cj].boundary.push(e);
}
}
Kind::Fillet => {
let o = centre().ok_or(unsupported.clone())?;
let mut towards = [0.0; 3];
for i in 0..3 {
let (_, out) =
plane_normals(body, corner.faces[i]).ok_or(unsupported.clone())?;
towards = v3::add(towards, v3::scale(out, convex));
}
let towards = v3::normalize(towards).ok_or(unsupported.clone())?;
for i in 0..3 {
let (_, out) =
plane_normals(body, corner.faces[i]).ok_or(unsupported.clone())?;
if v3::dot(towards, out) * convex < 0.2 {
return Err(unsupported);
}
}
parts.surfaces.push(
Surface::sphere(o, size)
.with_axis(perpendicular(towards))
.with_x_dir(towards),
);
let sphere = parts.surfaces.len() - 1;
let mut around = Vec::with_capacity(3);
for i in 0..3 {
let (j, k) = ((i + 1) % 3, (i + 2) % 3);
let ci = which(i);
let (Some(from), Some(to)) = (corner.points[j], corner.points[k]) else {
return Err(unsupported);
};
let cylinder = parts.surfaces[chosen[ci].surface].clone();
let Surface::Cylinder { axis, .. } = &cylinder else {
return Err(unsupported);
};
let between = section(
&cylinder,
o,
*axis,
parts.vertices[from],
parts.vertices[to],
tolerance,
&mut parts,
)
.ok_or(unsupported.clone())?;
let mut vertices = vec![from];
vertices.extend(between);
vertices.push(to);
parts.edges.push(Edge {
surfaces: pair(chosen[ci].surface, sphere),
vertices,
closed: false,
});
let e = parts.edges.len() - 1;
chosen[ci].boundary.push(e);
around.push(e);
}
fresh.push(parts.faces.len());
parts.faces.push(Face {
surface: sphere,
edges: around,
flipped: convex < 0.0,
u_range: (0.0, 0.0),
v_range: (0.0, 0.0),
u_wraps: false,
v_wraps: false,
loops: None,
});
}
},
}
}
for c in &chosen {
fresh.push(parts.faces.len());
parts.faces.push(Face {
surface: c.surface,
edges: c.boundary.clone(),
flipped: kind == Kind::Fillet && c.convex < 0.0,
u_range: (0.0, 0.0),
v_range: (0.0, 0.0),
u_wraps: false,
v_wraps: false,
loops: None,
});
}
let mut retrimmed: Vec<usize> = corners.iter().flat_map(|c| c.faces).collect();
retrimmed.sort_unstable();
retrimmed.dedup();
for &f in &retrimmed {
parts.faces[f].loops = None;
}
let probe = parts.body();
for &f in &retrimmed {
if !probe.face_loops(f).iter().any(|l| l.is_outer()) {
return Err(BlendDeclined::TrimmedFace { face: f });
}
}
for &f in &fresh {
let loops = probe.face_loops(f);
let [ring] = loops.as_slice() else {
return Err(BlendDeclined::NotWatertight { defects: 0 });
};
if !ring.is_outer() {
return Err(BlendDeclined::NotWatertight { defects: 0 });
}
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for c in &ring.uv {
for k in 0..2 {
lo[k] = lo[k].min(c[k]);
hi[k] = hi[k].max(c[k]);
}
}
let face = &mut parts.faces[f];
face.u_range = (lo[0], hi[0]);
face.v_range = (lo[1], hi[1]);
if !matches!(parts.surfaces[face.surface], Surface::Plane { .. }) {
face.loops = Some(loops);
}
}
Ok(parts)
}
fn blend_rim(
parts: &mut Parts,
edge: usize,
size: f64,
kind: Kind,
tolerance: f64,
) -> Result<(), BlendDeclined> {
let unsupported = BlendDeclined::UnsupportedEdge { edge };
let too_large = BlendDeclined::TooLarge { edge };
let eps = 1e-9 * extent(&parts.vertices);
let users: Vec<usize> = (0..parts.faces.len())
.filter(|&f| parts.faces[f].edges.contains(&edge))
.collect();
let &[f0, f1] = users.as_slice() else {
return Err(unsupported);
};
let is_plane = |f: usize| {
matches!(
parts.surfaces[parts.faces[f].surface],
Surface::Plane { .. }
)
};
let (cap, wall) = if is_plane(f0) { (f0, f1) } else { (f1, f0) };
let (
Surface::Plane {
origin: cap_origin,
normal: cap_normal,
..
},
Surface::Cylinder {
origin,
axis,
x_dir,
radius,
},
) = (
parts.surfaces[parts.faces[cap].surface].clone(),
parts.surfaces[parts.faces[wall].surface].clone(),
)
else {
return Err(unsupported);
};
if v3::dot(cap_normal, axis).abs() < 1.0 - 1e-9 {
return Err(unsupported);
}
if parts.faces[wall].loops.is_some() {
return Err(BlendDeclined::TrimmedFace { face: wall });
}
if !parts.faces[wall].u_wraps {
return Err(unsupported);
}
let height = v3::dot(v3::sub(cap_origin, origin), axis);
let (v0, v1) = parts.faces[wall].v_range;
let near_end = if (v0 - height).abs() <= (v1 - height).abs() {
0
} else {
1
};
let far = if near_end == 0 { v1 } else { v0 };
let into_wall = if far > height { 1.0 } else { -1.0 };
if (far - height).abs() <= size + eps {
return Err(too_large);
}
let cap_out = if parts.faces[cap].flipped {
v3::scale(cap_normal, -1.0)
} else {
cap_normal
};
let convex = if v3::dot(axis, cap_out) * into_wall < 0.0 {
1.0
} else {
-1.0
};
let shaft = if parts.faces[wall].flipped { -1.0 } else { 1.0 };
let grows = -shaft * convex;
let cap_radius = radius + grows * size;
let wall_height = height + into_wall * size;
if cap_radius <= eps {
return Err(too_large);
}
let on_axis = |h: f64| v3::add(origin, v3::scale(axis, h));
let (inner, outer) = (radius.min(cap_radius), radius.max(cap_radius));
let hub = on_axis(height);
for &e in &parts.faces[cap].edges {
if e == edge {
continue;
}
for w in parts.edges[e].vertices.windows(2) {
let (p, q) = (parts.vertices[w[0]], parts.vertices[w[1]]);
let pq = v3::sub(q, p);
let t = (v3::dot(v3::sub(hub, p), pq) / v3::dot(pq, pq).max(1e-300)).clamp(0.0, 1.0);
let nearest = v3::dist(hub, v3::add(p, v3::scale(pq, t)));
let farthest = v3::dist(hub, p).max(v3::dist(hub, q));
if nearest < outer + eps && farthest > inner - eps {
return Err(too_large);
}
}
}
let (surface, v_range, flipped) = match kind {
Kind::Chamfer => {
let widens = if cap_radius > radius {
-into_wall
} else {
into_wall
};
let apex = on_axis(wall_height - widens * radius);
(
Surface::cone(apex, v3::scale(axis, widens), FRAC_PI_4).with_x_dir(x_dir),
(radius.min(cap_radius), radius.max(cap_radius)),
shaft < 0.0,
)
}
Kind::Fillet => {
let at_cap = -into_wall * FRAC_PI_2;
let at_wall = if grows < 0.0 { 0.0 } else { -into_wall * PI };
(
Surface::torus(on_axis(wall_height), axis, cap_radius, size).with_x_dir(x_dir),
(at_cap.min(at_wall), at_cap.max(at_wall)),
convex < 0.0,
)
}
};
let widest = radius.max(cap_radius);
let n = if tolerance < widest {
((PI / (1.0 - tolerance / widest).acos()).ceil() as usize).clamp(16, 4096)
} else {
16
};
let y_dir = v3::cross(axis, x_dir);
let ring = |h: f64, r: f64, parts: &mut Parts| -> Vec<usize> {
let mut ids: Vec<usize> = (0..n)
.map(|i| {
let (s, c) = (-PI + TAU * i as f64 / n as f64).sin_cos();
let radial = v3::add(v3::scale(x_dir, c), v3::scale(y_dir, s));
parts.vertex(v3::add(on_axis(h), v3::scale(radial, r)))
})
.collect();
ids.push(ids[0]);
ids
};
let cap_rim = ring(height, cap_radius, parts);
let wall_rim = ring(wall_height, radius, parts);
parts.surfaces.push(surface);
let blend = parts.surfaces.len() - 1;
let (cap_surface, wall_surface) = (parts.faces[cap].surface, parts.faces[wall].surface);
parts.edges[edge] = Edge {
surfaces: pair(cap_surface, blend),
vertices: cap_rim,
closed: true,
};
parts.edges.push(Edge {
surfaces: pair(wall_surface, blend),
vertices: wall_rim,
closed: true,
});
let wall_edge = parts.edges.len() - 1;
let face = &mut parts.faces[wall];
for slot in face.edges.iter_mut() {
if *slot == edge {
*slot = wall_edge;
}
}
if near_end == 0 {
face.v_range.0 = wall_height;
} else {
face.v_range.1 = wall_height;
}
parts.faces[cap].loops = None;
parts.faces.push(Face {
surface: blend,
edges: vec![edge, wall_edge],
flipped,
u_range: (-PI, PI),
v_range,
u_wraps: true,
v_wraps: false,
loops: None,
});
if !parts.body().face_loops(cap).iter().any(|l| l.is_outer()) {
return Err(BlendDeclined::TrimmedFace { face: cap });
}
Ok(())
}