use std::collections::{BTreeSet, HashMap};
use std::f64::consts::TAU;
use crate::{
Error, Result, check,
error::invalid,
geom::{Cone, Curve, Cylinder, Line, Plane, Sphere, Surface, Torus},
math::{Frame, Point3, Transform, Vec2, Vec3},
numeric::solve_dense,
tol,
topo::{Brep, CoedgeSpec, EdgeId, FaceId, PCurve, VertexId},
};
fn vertex_faces(b: &Brep) -> HashMap<VertexId, BTreeSet<FaceId>> {
let mut out: HashMap<VertexId, BTreeSet<FaceId>> = HashMap::new();
for f in b.face_ids() {
for &lp in &b.face(f).loops {
for &c in &b.lp(lp).coedges {
let e = b.edge(b.coedge(c).edge);
out.entry(e.start).or_default().insert(f);
out.entry(e.end).or_default().insert(f);
}
}
}
out
}
fn meet(planes: &[(Vec3, f64)]) -> Option<Point3> {
let mut a = vec![0.0; 9];
let mut r = vec![0.0; 3];
for &(n, d) in planes {
let n = n.to_array();
for i in 0..3 {
for j in 0..3 {
a[i * 3 + j] += n[i] * n[j];
}
r[i] += n[i] * d;
}
}
let det = a[0] * (a[4] * a[8] - a[5] * a[7]) - a[1] * (a[3] * a[8] - a[5] * a[6])
+ a[2] * (a[3] * a[7] - a[4] * a[6]);
if det.abs() < 1e-12 {
return None;
}
let x = solve_dense(a, r, 3, 1).ok()?;
let p = Vec3::new(x[0], x[1], x[2]);
planes
.iter()
.all(|&(n, d)| (n.dot(p) - d).abs() <= tol::LINEAR)
.then_some(p)
}
fn plane_of(s: &Surface) -> Option<Frame> {
match s {
Surface::Plane(p) => Some(p.frame),
_ => None,
}
}
fn affine_on(frame: &Frame, line: &Line) -> PCurve {
let l = frame.to_local(line.origin);
PCurve::Affine {
origin: Vec2::new(l.x, l.y),
dir: Vec2::new(line.dir.dot(frame.x), line.dir.dot(frame.y)),
}
}
fn unsupported<T>(why: &str) -> Result<T> {
Err(Error::Unsupported(why.to_string()))
}
fn clear_of_contacts<'a>(b: &Brep, faces: impl IntoIterator<Item = &'a FaceId>) -> Result<()> {
if crate::check::faces_at_contacts(b, faces.into_iter().copied()).is_empty() {
return Ok(());
}
unsupported("moving a face up to where the solid touches itself")
}
pub fn draft(b: &Brep, faces: &[FaceId], neutral: &Frame, angle: f64) -> Result<Brep> {
let k = neutral.z;
let mut moved = HashMap::new();
let mut cones = HashMap::new();
for &g in faces {
let face = b.face(g);
if let Surface::Cylinder(c) = &face.surface
&& c.frame.z.cross(k).norm() <= tol::ANGULAR
{
let level = (neutral.origin - c.frame.origin).dot(k) / c.frame.z.dot(k);
let frame = Frame::new(c.frame.origin + c.frame.z * level, k, c.frame.x)?;
let half_angle = if face.reversed { angle } else { -angle };
cones.insert(
g,
Surface::Cone(Cone {
frame,
radius: c.radius,
half_angle,
}),
);
continue;
}
let Some(fr) = plane_of(&face.surface) else {
return unsupported(&format!("drafting a {} face", face.surface.kind()));
};
let n = if face.reversed { -fr.z } else { fr.z };
let (Some(level), Some(up)) = ((n - k * n.dot(k)).unit(), (k - n * n.dot(k)).unit()) else {
return Err(Error::InvalidInput(
"a face parallel to the neutral plane has no draft".into(),
));
};
let hinge = fr.origin + up * ((neutral.origin - fr.origin).dot(k) / up.dot(k));
let tilted = level * angle.cos() + k * angle.sin();
let z = if face.reversed { -tilted } else { tilted };
moved.insert(g, Frame::new(hinge, z, fr.x)?);
}
let mut paths: HashMap<FaceId, through::Path> = HashMap::new();
for (&g, &to) in &moved {
let from = plane_of(&b.face(g).surface).expect("drafted planes are planes");
paths.insert(
g,
Box::new(move |s| {
Ok(Surface::Plane(Plane {
frame: through::pencil(&from, &to, s)?,
}))
}),
);
}
for (&g, cone) in &cones {
let Surface::Cone(cone) = cone.clone() else {
unreachable!("a drafted cylinder is a cone")
};
paths.insert(g, Box::new(move |s| Ok(through::opening(&cone, s))));
}
let direct = if cones.is_empty() {
planes_or_faces(b, &moved)
} else {
let mut surfaces = cones.clone();
for (&g, &frame) in &moved {
surfaces.insert(g, Surface::Plane(Plane { frame }));
}
move_faces(b, &surfaces)
};
direct.or_else(|e| through::through(b, &paths).map_err(|_| e))
}
pub(crate) fn planes_or_faces(b: &Brep, moved: &HashMap<FaceId, Frame>) -> Result<Brep> {
match move_planes(b, moved) {
Err(Error::Unsupported(_)) => {
let surfaces = moved
.iter()
.map(|(&f, &frame)| (f, Surface::Plane(Plane { frame })))
.collect();
move_faces(b, &surfaces)
}
r => r,
}
}
pub fn offset_faces(b: &Brep, by: &HashMap<FaceId, f64>) -> Result<Brep> {
offset_kept(b, by).or_else(|e| {
let mut paths: HashMap<FaceId, through::Path> = HashMap::new();
for (&f, &d) in by {
let face = b.face(f);
let natural = if face.reversed { -d } else { d };
let (surface, bounds) = (face.surface.clone(), face_box(b, f));
paths.insert(
f,
Box::new(move |s| match offset_surface(&surface, s * natural) {
Err(Error::Unsupported(_)) => offset_fitted(&surface, s * natural, bounds),
r => r,
}),
);
}
through::through(b, &paths).map_err(|_| e)
})
}
fn offset_kept(b: &Brep, by: &HashMap<FaceId, f64>) -> Result<Brep> {
let mut planes = HashMap::new();
let mut surfaces = HashMap::new();
for (&f, &d) in by {
let face = b.face(f);
let natural = if face.reversed { -d } else { d };
if let Some(fr) = plane_of(&face.surface) {
planes.insert(f, fr.translated(fr.z * natural));
}
let moved = match offset_surface(&face.surface, natural) {
Err(Error::Unsupported(_)) => offset_fitted(&face.surface, natural, face_box(b, f))?,
r => r?,
};
surfaces.insert(f, moved);
}
if planes.len() == surfaces.len() {
return planes_or_faces(b, &planes);
}
move_faces(b, &surfaces)
}
pub(crate) fn move_planes(b: &Brep, moved: &HashMap<FaceId, Frame>) -> Result<Brep> {
clear_of_contacts(b, moved.keys())?;
for (&f, fr) in moved {
let Some(old) = plane_of(&b.face(f).surface) else {
return unsupported("moving a face that is not a plane");
};
if old.z.dot(fr.z) <= 0.0 {
return Err(Error::InvalidInput(
"a moved plane must face the way the old one did".into(),
));
}
}
let frame_of = |f: FaceId| moved.get(&f).copied().or(plane_of(&b.face(f).surface));
let around = vertex_faces(b);
let mut out = Brep::new();
let mut shifted = vec![false; b.vertex_ids().count()];
let mut verts = Vec::new();
for v in b.vertex_ids() {
let faces = around.get(&v).cloned().unwrap_or_default();
let p = b.vertex(v).point;
if !faces.iter().any(|f| moved.contains_key(f)) {
verts.push(out.add_vertex(p));
continue;
}
let mut planes = Vec::new();
for &f in &faces {
let Some(fr) = frame_of(f) else {
return unsupported("moving a corner where a curved face meets the planes");
};
planes.push((fr.z, fr.z.dot(fr.origin)));
}
let Some(q) = meet(&planes) else {
return unsupported("moving a corner whose planes do not meet at one point");
};
shifted[v.index()] = q.dist(p) > 0.0;
verts.push(out.add_vertex(q));
}
let mut edge_faces: HashMap<EdgeId, Vec<FaceId>> = HashMap::new();
for f in b.face_ids() {
for &lp in &b.face(f).loops {
for &c in &b.lp(lp).coedges {
edge_faces.entry(b.coedge(c).edge).or_default().push(f);
}
}
}
let mut rebuilt = vec![false; b.edge_ids().count()];
let mut edges = Vec::new();
for e in b.edge_ids() {
let x = b.edge(e);
let (s, t) = (verts[x.start.index()], verts[x.end.index()]);
let touched = edge_faces
.get(&e)
.is_some_and(|fs| fs.iter().any(|f| moved.contains_key(f)))
|| shifted[x.start.index()]
|| shifted[x.end.index()];
let id = match &x.curve {
Some(Curve::Line(old)) if touched => {
let (a, z) = (out.vertex(s).point, out.vertex(t).point);
let Some((line, len)) = Line::through(a, z) else {
return Err(Error::InvalidResult(vec![
"a moved edge shrinks to nothing".into(),
]));
};
if line.dir.dot(old.dir) <= 0.0 {
return Err(Error::InvalidResult(vec![
"a moved edge runs backwards: a face turns inside out".into(),
]));
}
rebuilt[e.index()] = true;
out.add_edge(Curve::Line(line), (0.0, len), s, t)
}
_ if touched => {
return unsupported("moving a face bounded by a curved edge");
}
Some(c) => out.add_edge(c.clone(), x.range, s, t),
None => out.add_degenerate_edge(s, x.range),
};
edges.push(id);
}
let mut faces = Vec::new();
for f in b.face_ids() {
let face = b.face(f);
let surface = match moved.get(&f) {
Some(&frame) => Surface::Plane(Plane { frame }),
None => face.surface.clone(),
};
let plane = plane_of(&surface);
let nf = out.add_face(surface, face.reversed, face.names.clone());
for &lp in &face.loops {
let specs = b
.lp(lp)
.coedges
.iter()
.map(|&c| {
let co = b.coedge(c);
let edge = edges[co.edge.index()];
let pcurve = match (&out.edge(edge).curve, plane) {
(Some(Curve::Line(l)), Some(fr))
if rebuilt[co.edge.index()] || moved.contains_key(&f) =>
{
affine_on(&fr, l)
}
_ => co.pcurve.clone(),
};
CoedgeSpec {
edge,
reversed: co.reversed,
pcurve,
}
})
.collect();
out.add_loop(nf, specs);
}
faces.push((f, nf));
}
for sh in b.shell_ids() {
let ids = b
.shell(sh)
.faces
.iter()
.map(|f| faces[f.index()].1)
.collect();
let _ = out.add_shell(ids);
}
for so in b.solid_ids() {
out.add_solid_of(b.solid(so).shells.clone(), b.solid(so).outer);
}
out.pair_radial();
let issues = check::check(&out);
if issues.is_empty() {
Ok(out)
} else {
Err(Error::InvalidResult(
issues.into_iter().map(|i| i.to_string()).collect(),
))
}
}
const OFFSET_FIT: f64 = 0.1 * tol::LINEAR;
const OFFSET_SAMPLES: usize = 1 << 13;
fn derivative(f: &dyn Fn(f64) -> Point3, t: f64, h: f64, (t0, t1): (f64, f64)) -> Vec3 {
if t - 2.0 * h >= t0 && t + 2.0 * h <= t1 {
return ((f(t + h) - f(t - h)) * 8.0 - (f(t + 2.0 * h) - f(t - 2.0 * h))) / (12.0 * h);
}
let s = if t - 2.0 * h < t0 { h } else { -h };
let at = |k: f64| f(t + s * k);
(at(0.0) * -25.0 + at(1.0) * 48.0 - at(2.0) * 36.0 + at(3.0) * 16.0 - at(4.0) * 3.0)
/ (12.0 * s)
}
fn fit_offset_curve(
true_at: &dyn Fn(f64) -> Point3,
(t0, t1): (f64, f64),
period: Option<f64>,
breaks: &[f64],
) -> Result<crate::geom::BSpline> {
let closed = period.filter(|&p| t1 - t0 >= p - 1e-12);
let (t0, t1) = match closed {
Some(p) => (t0, t0 + p),
None => (t0, t1),
};
let mut cuts: Vec<f64> = vec![t0];
cuts.extend(
breaks
.iter()
.copied()
.filter(|&b| b > t0 + 1e-12 && b < t1 - 1e-12),
);
cuts.push(t1);
let h = 1e-4 * (t1 - t0) / cuts.len() as f64;
let mut per = 2;
while (cuts.len() - 1) * per <= OFFSET_SAMPLES {
let mut nodes: Vec<f64> = Vec::new();
for w in cuts.windows(2) {
for k in 0..per {
nodes.push(w[0] + (w[1] - w[0]) * k as f64 / per as f64);
}
}
nodes.push(t1);
let pts: Vec<Point3> = nodes.iter().map(|&t| true_at(t)).collect();
let dirs: Vec<Vec3> = nodes
.iter()
.map(|&t| {
derivative(
true_at,
t,
h,
if closed.is_some() {
(f64::MIN, f64::MAX)
} else {
(t0, t1)
},
)
})
.collect();
let m = nodes.len() - 1;
let step = |j: usize| nodes[j + 1] - nodes[j];
let fit = if closed.is_some() {
let hs: Vec<f64> = (0..m).map(step).collect();
let minus = |j: usize| pts[j] - dirs[j] * (hs[(j + m - 1) % m] / 3.0);
let plus = |j: usize| pts[j] + dirs[j] * (hs[j] / 3.0);
let mut ctrl = vec![plus(m - 1)];
for j in 0..m {
ctrl.push(minus(j));
if j + 1 < m {
ctrl.push(plus(j));
}
}
for k in 0..3 {
ctrl.push(ctrl[k]);
}
let n = 2 * m;
let period = t1 - t0;
let s = |k: isize| -> f64 {
let q = k.rem_euclid(n as isize) as usize;
nodes[q / 2] + period * k.div_euclid(n as isize) as f64
};
let knots: Vec<f64> = (-3..=(n as isize + 3)).map(s).collect();
crate::geom::BSpline::periodic_cubic(knots, ctrl)?
} else {
let mut full = vec![pts[0]];
for j in 0..m {
full.push(pts[j] + dirs[j] * (step(j) / 3.0));
full.push(pts[j + 1] - dirs[j + 1] * (step(j) / 3.0));
}
full.push(pts[m]);
let mut knots = vec![t0; 4];
for &t in &nodes[1..m] {
knots.push(t);
knots.push(t);
}
knots.extend([t1; 4]);
crate::geom::BSpline::new(3, knots, full)?
};
let worst = nodes
.windows(2)
.map(|w| {
let t = 0.5 * (w[0] + w[1]);
fit.eval(t).dist(true_at(t))
})
.fold(0.0f64, f64::max);
if worst <= OFFSET_FIT {
return Ok(fit);
}
per *= 2;
}
unsupported("offsetting a face whose offset no spline holds to the tolerance")
}
fn offset_fitted(s: &Surface, d: f64, (u, v): ((f64, f64), (f64, f64))) -> Result<Surface> {
let at = |a: f64, b: f64| s.eval(a, b) + s.normal(a, b) * d;
match s {
Surface::Extrusion(e) => {
let breaks = e.curve.breakpoints(u.0, u.1);
let fit = fit_offset_curve(&|t| at(t, 0.0), u, e.curve.period(), &breaks)?;
Ok(Surface::Extrusion(Box::new(crate::geom::Extrusion {
curve: Curve::BSpline(fit),
dir: e.dir,
})))
}
Surface::Revolution(r) => {
let breaks = r.curve.breakpoints(v.0, v.1);
let fit = fit_offset_curve(&|t| at(0.0, t), v, r.curve.period(), &breaks)?;
Ok(Surface::Revolution(Box::new(crate::geom::Revolution {
curve: Curve::BSpline(fit),
origin: r.origin,
axis: r.axis,
})))
}
_ => {
let mut n = 9;
while n <= 257 {
let us: Vec<f64> = (0..n)
.map(|k| u.0 + (u.1 - u.0) * k as f64 / (n - 1) as f64)
.collect();
let vs: Vec<f64> = (0..n)
.map(|k| v.0 + (v.1 - v.0) * k as f64 / (n - 1) as f64)
.collect();
let mut rows = Vec::with_capacity(n);
for &b in &vs {
let pts: Vec<Point3> = us.iter().map(|&a| at(a, b)).collect();
rows.push(crate::geom::BSpline::interpolate_at(&pts, &us)?);
}
let ku = rows[0].knots().to_vec();
let mut cols = Vec::with_capacity(n);
for i in 0..n {
let pts: Vec<Point3> = rows.iter().map(|r| r.control_points()[i]).collect();
cols.push(crate::geom::BSpline::interpolate_at(&pts, &vs)?);
}
let kv = cols[0].knots().to_vec();
let (pu, pv) = (rows[0].degree(), cols[0].degree());
let ctrl: Vec<Point3> = cols
.iter()
.flat_map(|c| c.control_points().iter().copied())
.collect();
let fit = crate::geom::NurbsSurface::new((pu, pv), (ku, kv), (n, n), ctrl, None)?;
let mut worst = 0.0f64;
for w in us.windows(2) {
for z in vs.windows(2) {
for (a, b) in [
(0.5 * (w[0] + w[1]), 0.5 * (z[0] + z[1])),
(0.5 * (w[0] + w[1]), z[0]),
(w[0], 0.5 * (z[0] + z[1])),
] {
worst = worst.max(fit.eval(a, b).dist(at(a, b)));
}
}
}
if worst <= OFFSET_FIT {
return Ok(Surface::Nurbs(Box::new(fit)));
}
n = 2 * n - 1;
}
unsupported("offsetting a face whose offset no spline holds to the tolerance")
}
}
}
fn face_box(b: &Brep, f: FaceId) -> ((f64, f64), (f64, f64)) {
let face = b.face(f);
let s = &face.surface;
let (mut lo, mut hi) = (
Vec2::new(f64::INFINITY, f64::INFINITY),
Vec2::new(f64::NEG_INFINITY, f64::NEG_INFINITY),
);
for &lp in &face.loops {
let mut last = None;
for &c in &b.lp(lp).coedges {
let x = b.edge(b.coedge(c).edge);
let Some(cv) = &x.curve else { continue };
for k in 0..=16 {
let p = cv.eval(x.range.0 + (x.range.1 - x.range.0) * k as f64 / 16.0);
let uv = near_uv(s, p, last);
last = Some(uv);
lo = Vec2::new(lo.x.min(uv.x), lo.y.min(uv.y));
hi = Vec2::new(hi.x.max(uv.x), hi.y.max(uv.y));
}
}
}
let grow = |a: f64, z: f64| {
let m = 0.1 * (z - a).max(1e-6);
(a - m, z + m)
};
let (mut u, mut v) = (grow(lo.x, hi.x), grow(lo.y, hi.y));
let clamp = |r: (f64, f64), dom: (f64, f64)| (r.0.max(dom.0), r.1.min(dom.1));
match s {
Surface::Extrusion(e) => u = clamp(u, e.curve.domain()),
Surface::Revolution(r) => v = clamp(v, r.curve.domain()),
Surface::Nurbs(n) => {
let (du, dv) = n.domain();
u = clamp(u, du);
v = clamp(v, dv);
}
_ => {}
}
(u, v)
}
pub(crate) fn offset_surface(s: &Surface, d: f64) -> Result<Surface> {
let positive = |r: f64, what: &str| {
if r > tol::LINEAR {
Ok(r)
} else {
Err(Error::InvalidInput(format!(
"an offset of {d} mm closes a {what} to nothing"
)))
}
};
Ok(match s {
Surface::Plane(p) => Surface::Plane(Plane {
frame: p.frame.translated(p.frame.z * d),
}),
Surface::Cylinder(c) => Surface::Cylinder(Cylinder {
frame: c.frame,
radius: positive(c.radius + d, "cylinder")?,
}),
Surface::Cone(c) => {
let (sa, ca) = c.half_angle.sin_cos();
Surface::Cone(Cone {
frame: c.frame.translated(c.frame.z * (-d * sa)),
radius: c.radius + d * ca,
half_angle: c.half_angle,
})
}
Surface::Sphere(sp) => Surface::Sphere(Sphere {
frame: sp.frame,
radius: positive(sp.radius + d, "sphere")?,
}),
Surface::Torus(t) => Surface::Torus(Torus {
frame: t.frame,
major: t.major,
minor: positive(t.minor + d, "torus")?,
}),
other => return unsupported(&format!("offsetting a {} face", other.kind())),
})
}
fn settle(p: Point3, on: &[&Surface]) -> Option<Point3> {
let mut x = p;
for _ in 0..60 {
let rows: Vec<(Vec3, f64)> = on
.iter()
.map(|s| {
let uv = s.project(x);
let q = s.eval(uv.x, uv.y);
let n = s.normal(uv.x, uv.y);
(n, n.dot(q - x))
})
.collect();
if rows.iter().all(|r| r.1.abs() <= 1e-3 * tol::LINEAR) {
return Some(x);
}
let mut kept: Vec<(Vec3, f64)> = Vec::new();
for r in rows {
if !kept.iter().any(|q| q.0.cross(r.0).norm() <= 1e-9) {
kept.push(r);
}
}
let rows = kept;
let k = rows.len();
let step = if k <= 3 {
let mut a = vec![0.0; k * k];
for i in 0..k {
for j in 0..k {
a[i * k + j] = rows[i].0.dot(rows[j].0);
}
}
let y = solve_dense(a, rows.iter().map(|r| r.1).collect(), k, 1).ok()?;
rows.iter()
.zip(&y)
.fold(Vec3::ZERO, |acc, (r, &yi)| acc + r.0 * yi)
} else {
let mut a = vec![0.0; 9];
let mut rhs = vec![0.0; 3];
for (n, r) in &rows {
let n = n.to_array();
for i in 0..3 {
for j in 0..3 {
a[i * 3 + j] += n[i] * n[j];
}
rhs[i] += n[i] * r;
}
}
let s = solve_dense(a, rhs, 3, 1).ok()?;
Vec3::new(s[0], s[1], s[2])
};
if !(step.x.is_finite() && step.y.is_finite() && step.z.is_finite()) {
return None;
}
x += step;
}
None
}
fn circle_through(a: Point3, b: Point3, c: Point3) -> Option<crate::geom::Circle> {
let (ab, ac) = (b - a, c - a);
let n = ab.cross(ac);
let n2 = n.norm2();
if n2 <= 1e-24 {
return None;
}
let centre = a + (n.cross(ab) * ac.norm2() + ac.cross(n) * ab.norm2()) * (0.5 / n2);
let radius = centre.dist(a);
let frame = Frame::new(centre, n, a - centre).ok()?;
Some(crate::geom::Circle { frame, radius })
}
fn near_uv(s: &Surface, p: Point3, last: Option<Vec2>) -> Vec2 {
let uv = s.project(p);
let Some(to) = last else { return uv };
let shift = |x: f64, t: f64, per: Option<f64>| per.map_or(x, |q| x + ((t - x) / q).round() * q);
Vec2::new(
shift(uv.x, to.x, s.u_period()),
shift(uv.y, to.y, s.v_period()),
)
}
pub fn move_faces(b: &Brep, moved: &HashMap<FaceId, Surface>) -> Result<Brep> {
move_faces_pinned(b, moved, &HashMap::new())
}
pub fn move_faces_by(b: &Brep, faces: &[FaceId], motion: &Transform) -> Result<Brep> {
let r = motion.r;
let dot = |i: usize, j: usize| (0..3).map(|k| r[k][i] * r[k][j]).sum::<f64>();
let square = (0..3)
.all(|i| (0..3).all(|j| (dot(i, j) - f64::from(u8::from(i == j))).abs() <= tol::ANGULAR));
let det = r[0][0] * (r[1][1] * r[2][2] - r[1][2] * r[2][1])
- r[0][1] * (r[1][0] * r[2][2] - r[1][2] * r[2][0])
+ r[0][2] * (r[1][0] * r[2][1] - r[1][1] * r[2][0]);
if !square || (det - 1.0).abs() > tol::ANGULAR {
return invalid("faces move by a rigid motion: a rotation and a shift");
}
let moved = faces
.iter()
.map(|&f| (f, b.face(f).surface.transformed(motion)))
.collect();
move_faces(b, &moved)
}
pub(crate) fn move_faces_pinned(
b: &Brep,
moved: &HashMap<FaceId, Surface>,
pins: &HashMap<VertexId, Point3>,
) -> Result<Brep> {
clear_of_contacts(b, moved.keys())?;
let surface_of = |f: FaceId| moved.get(&f).unwrap_or(&b.face(f).surface);
let around = vertex_faces(b);
let mut edge_faces: HashMap<EdgeId, Vec<FaceId>> = HashMap::new();
for f in b.face_ids() {
for &lp in &b.face(f).loops {
for &c in &b.lp(lp).coedges {
edge_faces.entry(b.coedge(c).edge).or_default().push(f);
}
}
}
let mut poles: HashMap<VertexId, Point3> = HashMap::new();
for c in b.coedge_ids() {
let co = b.coedge(c);
let edge = b.edge(co.edge);
let f = b.coedge_face(c);
if edge.curve.is_some() || !moved.contains_key(&f) {
continue;
}
if let PCurve::Affine { origin, dir } = &co.pcurve {
let uv = *origin + *dir * edge.range.0;
poles.insert(edge.start, surface_of(f).eval(uv.x, uv.y));
}
}
let mut out = Brep::new();
let mut shifted = vec![false; b.vertex_ids().count()];
let mut verts = Vec::new();
for v in b.vertex_ids() {
let faces = around.get(&v).cloned().unwrap_or_default();
let p = b.vertex(v).point;
if !faces.iter().any(|f| moved.contains_key(f)) {
verts.push(out.add_vertex(p));
continue;
}
let on: Vec<&Surface> = faces.iter().map(|&f| surface_of(f)).collect();
let pinned = pins.get(&v).or(poles.get(&v)).copied().filter(|&q| {
on.iter()
.all(|s| crate::boolean::csi::signed_distance(s, q).abs() <= 1e-2 * tol::LINEAR)
});
let Some(q) = pinned.or_else(|| settle(p, &on)) else {
return unsupported("moving a corner whose faces' new surfaces do not meet near it");
};
shifted[v.index()] = q.dist(p) > 0.0;
verts.push(out.add_vertex(q));
}
let mut flipped = vec![false; b.edge_ids().count()];
let mut rebuilt = vec![false; b.edge_ids().count()];
let mut edges = Vec::new();
for e in b.edge_ids() {
let x = b.edge(e);
let (s, t) = (verts[x.start.index()], verts[x.end.index()]);
let mut faces = edge_faces.get(&e).cloned().unwrap_or_default();
faces.sort();
faces.dedup();
let touched = faces.iter().any(|f| moved.contains_key(f))
|| shifted[x.start.index()]
|| shifted[x.end.index()];
let Some(old) = &x.curve else {
edges.push(out.add_degenerate_edge(s, x.range));
continue;
};
if !touched {
edges.push(out.add_edge(old.clone(), x.range, s, t));
continue;
}
rebuilt[e.index()] = true;
let on: Vec<&Surface> = faces.iter().map(|&f| surface_of(f)).collect();
let lies_on = |c: &Curve, r: (f64, f64)| {
(1..8).all(|k| {
let p = c.eval(r.0 + (r.1 - r.0) * k as f64 / 8.0);
on.iter()
.all(|sf| crate::boolean::csi::signed_distance(sf, p).abs() <= tol::LINEAR)
})
};
let (a, z) = (out.vertex(s).point, out.vertex(t).point);
if let (Curve::Line(old_line), Some((line, len))) = (old, Line::through(a, z))
&& lies_on(&Curve::Line(line.clone()), (0.0, len))
{
if line.dir.dot(old_line.dir) <= 0.0 {
return Err(Error::InvalidResult(vec![
"a moved edge runs backwards: a face turns inside out".into(),
]));
}
edges.push(out.add_edge(Curve::Line(line), (0.0, len), s, t));
continue;
}
if on.len() != 2 {
let (Some(&f), true) = (faces.first(), faces.len() == 1) else {
return unsupported("moving a curved edge of three faces");
};
let (from, to) = (&b.face(f).surface, surface_of(f));
let fractions: &[f64] = if x.start == x.end {
&[0.0, 1.0 / 3.0, 2.0 / 3.0]
} else {
&[0.0, 0.5, 1.0]
};
let pts: Vec<Point3> = fractions
.iter()
.map(|&k| {
let q = old.eval(x.range.0 + (x.range.1 - x.range.0) * k);
let uv = from.project(q);
to.eval(uv.x, uv.y)
})
.collect();
let ends = if x.start == x.end {
[a, pts[1], pts[2]]
} else {
[a, pts[1], z]
};
let pts = ends;
let Some(circle) = circle_through(pts[0], pts[1], pts[2]) else {
return unsupported("moving a seam that is not a circle");
};
let c = Curve::Circle(circle);
let lo = c.project(pts[0], 0.0, TAU);
let hi = if x.start == x.end {
lo + TAU
} else {
let mut h = c.project(pts[2], 0.0, TAU);
while h <= lo {
h += TAU;
}
h
};
let (old_mid, old_dir) = old.d1(0.5 * (x.range.0 + x.range.1));
let _ = old_mid;
let mid_t = 0.5 * (lo + hi);
if c.d1(mid_t).1.dot(old_dir) <= 0.0 && x.start != x.end {
return unsupported("moving a seam that turns the other way");
}
edges.push(out.add_edge(c, (lo, hi), s, t));
continue;
}
let mid_t = 0.5 * (x.range.0 + x.range.1);
let (old_mid, old_dir) = old.d1(mid_t);
let Some(mid) = settle(old_mid, &on) else {
return unsupported("moving an edge whose faces' new surfaces do not meet near it");
};
let mut region = old.bbox(x.range.0, x.range.1);
region.add(a);
region.add(z);
region.add(mid);
let reach = old_mid.dist(mid) + a.dist(b.vertex(x.start).point) + 1.0;
let pad = Vec3::new(reach, reach, reach);
let region = crate::math::Aabb {
min: region.min - pad,
max: region.max + pad,
};
let ssi = crate::boolean::ssi::intersect(on[0], on[1], ®ion, &mut || vec![mid])?;
let crate::boolean::ssi::Ssi::Curves { curves, .. } = ssi else {
return unsupported("moving an edge between faces that come to coincide");
};
let Some(best) = curves
.iter()
.map(|sc| {
let tm = sc.curve.project(mid, sc.range.0, sc.range.1);
(sc.curve.eval(tm).dist(mid), sc)
})
.filter(|(d, _)| *d <= 10.0 * tol::LINEAR)
.min_by(|p, q| p.0.total_cmp(&q.0))
.map(|(_, sc)| sc)
else {
return unsupported("moving an edge whose new faces meet nowhere near it");
};
let c = &best.curve;
let (r0, r1) = best.range;
let ts = c.project(a, r0, r1);
let te = c.project(z, r0, r1);
let tm = c.project(mid, r0, r1);
let along = if x.start == x.end {
let (_, d1, d2) = old.d2(mid_t);
let (_, e1, e2) = c.d2(tm);
d1.cross(d2).dot(e1.cross(e2)) > 0.0
} else {
c.d1(tm).1.dot(old_dir) > 0.0
};
let period = c.period();
let span = |from: f64, to: f64| -> (f64, f64) {
match period {
Some(p) => {
let mut hi = to;
while hi <= from + 1e-12 {
hi += p;
}
while hi - from > p + 1e-12 {
hi -= p;
}
(from, hi)
}
None => (from, to),
}
};
let closed = x.start == x.end;
let (lo, hi, start, end) = if along {
let (lo, hi) = if closed {
(ts, ts + period.unwrap_or(r1 - r0))
} else {
span(ts, te)
};
(lo, hi, s, t)
} else {
let (lo, hi) = if closed {
(ts, ts + period.unwrap_or(r1 - r0))
} else {
span(te, ts)
};
flipped[e.index()] = true;
(lo, hi, t, s)
};
if hi - lo <= 0.0
|| c.eval(lo).dist(out.vertex(start).point) > tol::LINEAR
|| c.eval(hi).dist(out.vertex(end).point) > tol::LINEAR
{
return unsupported("moving an edge whose new curve does not run between its vertices");
}
edges.push(out.add_edge(c.clone(), (lo, hi), start, end));
}
let mut faces = Vec::new();
for f in b.face_ids() {
let face = b.face(f);
let surface = surface_of(f).clone();
let changed = moved.contains_key(&f)
|| face.loops.iter().any(|&lp| {
b.lp(lp)
.coedges
.iter()
.any(|&c| rebuilt[b.coedge(c).edge.index()])
});
let nf = out.add_face(surface.clone(), face.reversed, face.names.clone());
for &lp in &face.loops {
let mut last: Option<Vec2> = b.lp(lp).coedges.first().map(|&c| {
let ts = check::coedge_params(b, c, 1);
b.coedge_uvs(c, &ts[..1])[0]
});
let specs = b
.lp(lp)
.coedges
.iter()
.map(|&c| {
let co = b.coedge(c);
let edge = edges[co.edge.index()];
let reversed = co.reversed != flipped[co.edge.index()];
let x = out.edge(edge);
if x.curve.is_none() {
if let PCurve::Affine { origin, dir } = &co.pcurve {
let t = if reversed { x.range.0 } else { x.range.1 };
last = Some(*origin + *dir * t);
}
return CoedgeSpec {
edge,
reversed,
pcurve: co.pcurve.clone(),
};
}
let pcurve = if changed || rebuilt[co.edge.index()] {
let from = if reversed { x.end } else { x.start };
let mut seed = near_uv(&surface, out.vertex(from).point, last);
if let Some(cv) = &x.curve {
let (t0, t1) = if reversed {
(x.range.1, x.range.0)
} else {
x.range
};
let hint = last.unwrap_or(seed);
seed = crate::topo::pcurve::project_on(&surface, cv, t0, t1, hint);
}
let mut uv = seed;
if let Some(cv) = &x.curve {
let (t0, t1) = if reversed {
(x.range.1, x.range.0)
} else {
x.range
};
for k in 1..=32 {
let p = cv.eval(t0 + (t1 - t0) * k as f64 / 32.0);
uv = near_uv(&surface, p, Some(uv));
}
}
last = Some(uv);
PCurve::Projected { seed }
} else {
co.pcurve.clone()
};
CoedgeSpec {
edge,
reversed,
pcurve,
}
})
.collect();
out.add_loop(nf, specs);
}
faces.push((f, nf));
}
for sh in b.shell_ids() {
let ids = b
.shell(sh)
.faces
.iter()
.map(|f| faces[f.index()].1)
.collect();
let _ = out.add_shell(ids);
}
for so in b.solid_ids() {
out.add_solid_of(b.solid(so).shells.clone(), b.solid(so).outer);
}
out.pair_radial();
let issues = check::check(&out);
if issues.is_empty() {
Ok(out)
} else {
Err(Error::InvalidResult(
issues.into_iter().map(|i| i.to_string()).collect(),
))
}
}
#[cfg(test)]
mod tests;
mod through;