use std::collections::HashMap;
use crate::core::{BufferAttribute, BufferGeometry};
use crate::math::Matrix4;
use crate::nurbs::v3;
use crate::nurbs::V3;
use super::table::{triangle_normal, triangle_vertices};
use super::{Surface, SurfaceTable};
#[derive(Debug, Clone)]
pub struct Edge {
pub surfaces: (usize, usize),
pub vertices: Vec<usize>,
pub closed: bool,
}
#[derive(Debug, Clone)]
pub struct Face {
pub surface: usize,
pub edges: Vec<usize>,
pub flipped: bool,
pub u_range: (f64, f64),
pub v_range: (f64, f64),
pub u_wraps: bool,
pub v_wraps: bool,
pub loops: Option<Vec<TrimLoop>>,
}
#[derive(Debug, Clone)]
pub struct Body {
surfaces: Vec<Surface>,
vertices: Vec<V3>,
edges: Vec<Edge>,
faces: Vec<Face>,
}
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct BodyReport {
pub faces: usize,
pub edges: usize,
pub vertices: usize,
pub triangles: usize,
pub boundary_edges: usize,
pub carried_through: usize,
}
impl BodyReport {
pub fn is_closed(&self) -> bool {
self.boundary_edges == 0
}
}
impl Body {
pub fn from_parts(
surfaces: Vec<Surface>,
vertices: Vec<V3>,
edges: Vec<Edge>,
faces: Vec<Face>,
) -> Body {
Body {
surfaces,
vertices,
edges,
faces,
}
}
#[cfg(all(test, feature = "brep-kernel"))]
pub(crate) fn faces_mut(&mut self) -> &mut Vec<Face> {
&mut self.faces
}
pub fn surfaces(&self) -> &[Surface] {
&self.surfaces
}
pub fn vertices(&self) -> &[V3] {
&self.vertices
}
pub fn edges(&self) -> &[Edge] {
&self.edges
}
pub fn faces(&self) -> &[Face] {
&self.faces
}
pub fn from_tagged_mesh(geometry: &BufferGeometry) -> Option<Body> {
let table: &SurfaceTable = geometry.surface_table()?;
let boundaries = super::stitch::patch_boundaries(geometry, table);
let extent = {
let pos = geometry.get_attribute("position")?;
let (mut lo, mut hi) = (f64::INFINITY, f64::NEG_INFINITY);
for &c in &pos.array {
lo = lo.min(c as f64);
hi = hi.max(c as f64);
}
if lo.is_finite() {
(hi - lo).max(1.0)
} else {
1.0
}
};
let quantum = extent * 1e-6;
let mut pool: HashMap<[i64; 3], usize> = HashMap::new();
let mut vertices: Vec<V3> = Vec::new();
let mut intern = |p: V3, vertices: &mut Vec<V3>| -> usize {
let key = [
(p[0] / quantum).round() as i64,
(p[1] / quantum).round() as i64,
(p[2] / quantum).round() as i64,
];
*pool.entry(key).or_insert_with(|| {
vertices.push(p);
vertices.len() - 1
})
};
let edges: Vec<Edge> = boundaries
.iter()
.map(|b| Edge {
surfaces: b.surfaces,
vertices: b.points.iter().map(|p| intern(*p, &mut vertices)).collect(),
closed: b.closed,
})
.collect();
let faces = table
.groups()
.into_iter()
.map(|(si, tris)| {
let surface = &table.surfaces()[si];
let mut votes = 0i32;
for tri in &tris {
let Some(v) = triangle_vertices(geometry, *tri) else {
continue;
};
if let (Some(face), Some((u, w))) =
(triangle_normal(&v), surface.invert(centroid(&v)))
&& let Some(sn) = surface.normal(u, w)
{
votes += if v3::dot(face, sn) < 0.0 { -1 } else { 1 };
}
}
let (mut u0, mut u1) = (f64::INFINITY, f64::NEG_INFINITY);
let (mut v0, mut v1) = (f64::INFINITY, f64::NEG_INFINITY);
for tri in &tris {
let Some(v) = triangle_vertices(geometry, *tri) else {
continue;
};
for p in v {
if let Some((pu, pv)) = surface.invert(p) {
u0 = u0.min(pu);
u1 = u1.max(pu);
v0 = v0.min(pv);
v1 = v1.max(pv);
}
}
}
let (pu, pv) = surface.periodic();
let full = std::f64::consts::TAU * 0.75;
let u_wraps = pu && (u1 - u0) > full;
let v_wraps = pv && (v1 - v0) > full;
Face {
surface: si,
edges: (0..edges.len())
.filter(|&e| edges[e].surfaces.0 == si || edges[e].surfaces.1 == si)
.collect(),
flipped: votes < 0,
u_range: (u0, u1),
v_range: (v0, v1),
u_wraps,
v_wraps,
loops: None,
}
})
.collect();
Some(Body {
surfaces: table.surfaces().to_vec(),
vertices,
edges,
faces,
})
}
pub fn refine_edges(&mut self, tolerance: f64) {
let pinned: Vec<bool> = vec![false; self.edges.len()];
for (index, e) in self.edges.iter_mut().enumerate() {
if pinned[index] {
continue;
}
let (a, b) = (&self.surfaces[e.surfaces.0], &self.surfaces[e.surfaces.1]);
let mut out: Vec<usize> = Vec::with_capacity(e.vertices.len());
for w in e.vertices.windows(2) {
out.push(w[0]);
let (p, q) = (self.vertices[w[0]], self.vertices[w[1]]);
subdivide(p, q, a, b, tolerance, 0, &mut self.vertices, &mut out);
}
if let Some(&last) = e.vertices.last() {
out.push(last);
}
e.vertices = out;
}
self.restate_rings();
}
pub(crate) fn restate_rings(&mut self) {
let mut on: HashMap<usize, Vec<(usize, usize)>> = HashMap::new();
for (ei, e) in self.edges.iter().enumerate() {
for (k, v) in e.vertices.iter().enumerate() {
on.entry(*v).or_default().push((ei, k));
}
}
let mut done: Vec<(usize, Vec<TrimLoop>)> = Vec::new();
for (fi, face) in self.faces.iter().enumerate() {
let Some(loops) = face.loops.as_ref().filter(|l| !l.is_empty()) else {
continue;
};
let surface = &self.surfaces[face.surface];
let (pu, pv) = surface.periodic();
let mut out = Vec::with_capacity(loops.len());
for l in loops {
let n = l.vertices.len();
if n < 3 || l.uv.len() != n {
out.push(l.clone());
continue;
}
let mut uv: Vec<[f64; 2]> = Vec::with_capacity(n);
let mut vs: Vec<usize> = Vec::with_capacity(n);
for i in 0..n {
let (a, b) = (l.vertices[i], l.vertices[(i + 1) % n]);
vs.push(a);
uv.push(l.uv[i]);
if a == b {
continue;
}
let mut best: Option<Vec<usize>> = None;
for &(ea, ka) in on.get(&a).into_iter().flatten() {
for &(eb, kb) in on.get(&b).into_iter().flatten() {
if ea != eb || ka == kb {
continue;
}
let path: Vec<usize> = if ka < kb {
self.edges[ea].vertices[ka + 1..kb].to_vec()
} else {
self.edges[ea].vertices[kb + 1..ka]
.iter()
.rev()
.copied()
.collect()
};
let mut walked = 0.0;
let mut at = self.vertices[a];
for &v in path.iter().chain(std::iter::once(&b)) {
walked += v3::dist(at, self.vertices[v]);
at = self.vertices[v];
}
if walked > v3::dist(self.vertices[a], self.vertices[b]) * 1.5 + 1e-9 {
continue;
}
if best.as_ref().is_none_or(|w| path.len() < w.len()) {
best = Some(path);
}
}
}
let mut anchor = l.uv[i];
let mut run: Vec<(usize, [f64; 2])> = Vec::new();
for v in best.into_iter().flatten() {
let Some((u, w)) = surface.invert(self.vertices[v]) else {
continue;
};
let p = [
if pu { near(u, anchor[0]) } else { u },
if pv { near(w, anchor[1]) } else { w },
];
run.push((v, p));
anchor = p;
}
if let Some((_, last)) = run.last().copied() {
let want = l.uv[(i + 1) % n];
let shift = [
if pu {
near(last[0], want[0]) - last[0]
} else {
0.0
},
if pv {
near(last[1], want[1]) - last[1]
} else {
0.0
},
];
for (_, p) in run.iter_mut() {
p[0] += shift[0];
p[1] += shift[1];
}
}
for (v, p) in run {
uv.push(p);
vs.push(v);
}
}
let fresh = TrimLoop {
area: signed_area(&uv),
uv,
vertices: vs,
};
out.push(fresh);
}
done.push((fi, out));
}
for (fi, loops) in done {
self.faces[fi].loops = Some(loops);
}
}
pub fn tessellate(&self, tolerance: f64) -> (BufferGeometry, BodyReport) {
let mut positions: Vec<f32> = Vec::new();
let mut normals: Vec<f32> = Vec::new();
let mut indices: Vec<u32> = Vec::new();
let mut emitted: Vec<u32> = Vec::with_capacity(self.vertices.len());
for p in &self.vertices {
emitted.push((positions.len() / 3) as u32);
positions.extend_from_slice(&[p[0] as f32, p[1] as f32, p[2] as f32]);
normals.extend_from_slice(&[0.0, 0.0, 0.0]); }
let mut carried_through = 0usize;
let mut triangle_face: Vec<u32> = Vec::new();
for (face_index, face) in self.faces.iter().enumerate() {
let surface = &self.surfaces[face.surface];
let before = indices.len();
let trimmed = matches!(face.footprint(), Footprint::Rings(_));
let ok = match surface {
_ if trimmed => self.fill_planar(
face_index,
surface,
tolerance,
&emitted,
&mut positions,
&mut normals,
&mut indices,
),
Surface::Plane { .. } => self.fill_planar(
face_index,
surface,
tolerance,
&emitted,
&mut positions,
&mut normals,
&mut indices,
),
_ => {
let mark = (positions.len(), normals.len(), indices.len());
self.fill_parametric(
face,
surface,
tolerance,
false,
&emitted,
&mut positions,
&mut normals,
&mut indices,
) || {
positions.truncate(mark.0);
normals.truncate(mark.1);
indices.truncate(mark.2);
self.fill_parametric(
face,
surface,
tolerance,
true,
&emitted,
&mut positions,
&mut normals,
&mut indices,
)
} || {
positions.truncate(mark.0);
normals.truncate(mark.1);
indices.truncate(mark.2);
self.fill_planar(
face_index,
surface,
tolerance,
&emitted,
&mut positions,
&mut normals,
&mut indices,
)
}
}
};
if !ok {
carried_through += 1;
continue;
}
for _ in (before..indices.len()).step_by(3) {
triangle_face.push(face_index as u32);
}
}
orient(
&self.surfaces,
&self.faces,
&triangle_face,
&positions,
&mut indices,
);
for (vi, p) in self.vertices.iter().enumerate() {
let mut n = [0.0f64, 0.0, 1.0];
for face in &self.faces {
let s = &self.surfaces[face.surface];
if s.distance(*p) > 1e-6 {
continue;
}
if let Some((u, v)) = s.invert(*p)
&& let Some(sn) = s.normal(u, v)
{
n = if face.flipped {
v3::scale(sn, -1.0)
} else {
sn
};
break;
}
}
let o = emitted[vi] as usize * 3;
normals[o] = n[0] as f32;
normals[o + 1] = n[1] as f32;
normals[o + 2] = n[2] as f32;
}
let boundary_edges = count_boundary_edges(&indices);
if boundary_edges > 0 && std::env::var("THREERS_BREP_DEBUG").is_ok() {
let mut counts: HashMap<(u32, u32), usize> = HashMap::new();
for t in indices.as_chunks::<3>().0 {
for k in 0..3 {
let (a, b) = (t[k], t[(k + 1) % 3]);
*counts.entry((a.min(b), a.max(b))).or_insert(0) += 1;
}
}
let at = |i: u32| {
let o = i as usize * 3;
[positions[o], positions[o + 1], positions[o + 2]]
};
let mut open: Vec<_> = counts
.iter()
.filter(|(_, c)| **c == 1)
.map(|(e, _)| *e)
.collect();
open.sort_unstable();
for (a, b) in open.iter().take(12) {
eprintln!(" [brep] open edge {a}-{b}: {:?} {:?}", at(*a), at(*b));
}
}
let mut g = BufferGeometry::new();
let vertices = positions.len() / 3;
g.set_attribute("position", BufferAttribute::new(positions, 3));
g.set_attribute("normal", BufferAttribute::new(normals, 3));
g.set_index(indices.clone());
(
g,
BodyReport {
faces: self.faces.len(),
edges: self.edges.len(),
vertices,
triangles: indices.len() / 3,
boundary_edges,
carried_through,
},
)
}
#[allow(clippy::too_many_arguments)]
fn fill_planar(
&self,
face_index: usize,
surface: &Surface,
tolerance: f64,
emitted: &[u32],
positions: &mut Vec<f32>,
normals: &mut Vec<f32>,
indices: &mut Vec<u32>,
) -> bool {
let face = &self.faces[face_index];
let loops = self.face_loops(face_index);
if loops.is_empty() {
return false;
}
let Some(outer) = loops.iter().find(|l| l.is_outer()) else {
return false;
};
let holes: Vec<&TrimLoop> = loops.iter().filter(|l| l.is_hole()).collect();
let undoubled = |uv: &Vec<[f64; 2]>| -> Vec<[f64; 2]> {
let n = uv.len();
if n < 8 || !n.is_multiple_of(2) {
return uv.clone();
}
let half = n / 2;
let doubled = (0..half).all(|k| {
let a = surface.point(uv[k][0], uv[k][1]);
let b = surface.point(uv[k + half][0], uv[k + half][1]);
v3::dist(a, b) <= tolerance
});
if doubled {
uv[..half].to_vec()
} else {
uv.clone()
}
};
let hole_uv: Vec<Vec<[f64; 2]>> = holes.iter().map(|h| undoubled(&h.uv)).collect();
let bridged = bridge_holes(&outer.uv, &hole_uv);
if bridged.is_none() && std::env::var("THREERS_BREP_DEBUG").is_ok() {
eprintln!(" [brep] face {face_index}: bridge_holes failed");
}
let (ring_uv, ring_map) = bridged.clone().unwrap_or_else(|| {
let mut uv = outer.uv.clone();
for h in &hole_uv {
uv.extend_from_slice(h);
}
let n = uv.len();
(uv, (0..n).collect())
});
let mut lookup: Vec<Option<usize>> = Vec::new();
let mut lookup_uv: Vec<[f64; 2]> = Vec::new();
let push_loop = |l: &TrimLoop, lookup: &mut Vec<Option<usize>>, uv: &mut Vec<[f64; 2]>| {
for k in 0..l.uv.len() {
lookup.push(l.vertices.get(k).copied());
uv.push(l.uv[k]);
}
};
push_loop(outer, &mut lookup, &mut lookup_uv);
for (h, uv) in holes.iter().zip(&hole_uv) {
if uv.len() == h.uv.len() {
push_loop(h, &mut lookup, &mut lookup_uv);
} else {
for (k, &texcoord) in uv.iter().enumerate() {
lookup.push(h.vertices.get(k).copied());
lookup_uv.push(texcoord);
}
}
}
let mut fresh: HashMap<usize, u32> = HashMap::new();
let mut ring: Vec<u32> = Vec::with_capacity(ring_map.len());
for &i in &ring_map {
let Some(slot) = lookup.get(i) else { break };
match slot.filter(|vi| *vi < emitted.len()) {
Some(vi) => ring.push(emitted[vi]),
None => {
let id = *fresh.entry(i).or_insert_with(|| {
let uv = lookup_uv[i];
let p = surface.point(uv[0], uv[1]);
let mut n = surface.normal(uv[0], uv[1]).unwrap_or([0.0, 0.0, 1.0]);
if face.flipped {
n = v3::scale(n, -1.0);
}
positions.extend_from_slice(&[p[0] as f32, p[1] as f32, p[2] as f32]);
normals.extend_from_slice(&[n[0] as f32, n[1] as f32, n[2] as f32]);
(positions.len() / 3 - 1) as u32
});
ring.push(id);
}
}
}
if ring.len() != ring_uv.len() || ring.len() < 3 {
if std::env::var("THREERS_BREP_DEBUG").is_ok() {
eprintln!(
" [brep] face {face_index}: ring {} vs uv {}",
ring.len(),
ring_uv.len()
);
}
return false;
}
let mut tris = if bridged.is_some() {
earclip(&ring_uv)
} else {
Vec::new()
};
{
let want = signed_area(&outer.uv).abs()
- hole_uv.iter().map(|h| signed_area(h).abs()).sum::<f64>();
let got: f64 = tris
.iter()
.map(|t| {
let (a, b, c) = (ring_uv[t[0]], ring_uv[t[1]], ring_uv[t[2]]);
(((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) / 2.0).abs()
})
.sum();
if want > 0.0 && got < want * 0.99 {
#[cfg(feature = "brep-csg")]
if let Some(t) = constrained_fill(&lookup_uv, outer.uv.len(), &hole_uv, &ring_map) {
tris = t;
}
}
let got: f64 = tris
.iter()
.map(|t| {
let (a, b, c) = (ring_uv[t[0]], ring_uv[t[1]], ring_uv[t[2]]);
(((b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])) / 2.0).abs()
})
.sum();
if want > 0.0 && got < want * 0.99 {
if std::env::var("THREERS_BREP_DEBUG").is_ok() {
eprintln!(
" [brep] face {face_index}: filled {:.1}% of its ring",
got / want * 100.0
);
}
return false;
}
}
let tris = refine_on_surface(
surface,
face.flipped,
&ring_uv,
&ring,
&tris,
tolerance,
positions,
normals,
);
for t in &tris {
let (a, b, c) = (t[0], t[1], t[2]);
if a == b || b == c || c == a {
continue;
}
if face.flipped {
indices.extend_from_slice(&[a, c, b]);
} else {
indices.extend_from_slice(&[a, b, c]);
}
}
true
}
#[allow(clippy::too_many_arguments)]
fn fill_parametric(
&self,
face: &Face,
surface: &Surface,
tolerance: f64,
transpose: bool,
emitted: &[u32],
positions: &mut Vec<f32>,
normals: &mut Vec<f32>,
indices: &mut Vec<u32>,
) -> bool {
let at = |a: f64, b: f64| {
if transpose {
surface.point(b, a)
} else {
surface.point(a, b)
}
};
let nat = |a: f64, b: f64| {
if transpose {
surface.normal(b, a)
} else {
surface.normal(a, b)
}
};
let inv = |p: V3| {
surface
.invert(p)
.map(|(u, v)| if transpose { (v, u) } else { (u, v) })
};
let (a_range, b_range) = if transpose {
(face.v_range, face.u_range)
} else {
(face.u_range, face.v_range)
};
let (a_wraps, b_wraps) = if transpose {
(face.v_wraps, face.u_wraps)
} else {
(face.u_wraps, face.v_wraps)
};
let (pu, pv) = surface.periodic();
let (a_periodic, b_periodic) = if transpose { (pv, pu) } else { (pu, pv) };
let mut rims: Vec<(f64, Vec<usize>)> = Vec::new();
for &e in &face.edges {
let edge = &self.edges[e];
let mut params: Vec<(f64, f64, usize)> = Vec::with_capacity(edge.vertices.len());
for &vi in &edge.vertices {
let Some((u, v)) = inv(self.vertices[vi]) else {
return false;
};
params.push((u, v, vi));
}
let solid: Vec<&(f64, f64, usize)> = params
.iter()
.filter(|p| !surface.parameter_degenerate_at(self.vertices[p.2]))
.collect();
let measured = if solid.len() >= 2 { &solid[..] } else { &[] };
let vs: Vec<f64> = measured.iter().map(|p| p.1).collect();
let us: Vec<f64> = measured.iter().map(|p| p.0).collect();
if vs.is_empty() {
return false; }
let (v_mid, v_spread) = extent_of(&vs, b_periodic);
let (_, u_spread) = extent_of(&us, a_periodic);
if v_spread > u_spread.max(1e-12) * 0.1 {
return false;
}
params.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
params.dedup_by(|a, b| (a.0 - b.0).abs() < 1e-12);
rims.push((v_mid, params.into_iter().map(|p| p.2).collect()));
}
if rims.len() > 2 {
return false; }
rims.sort_by(|a, b| a.0.partial_cmp(&b.0).unwrap());
let column_u: Vec<f64> = match rims.first() {
Some((_, verts)) => {
let us: Vec<f64> = verts
.iter()
.filter_map(|&vi| inv(self.vertices[vi]).map(|(u, _)| u))
.collect();
if us.len() != verts.len() {
return false;
}
us
}
None => {
let (u0, u1) = a_range;
let n = adaptive_steps(
tolerance,
|a, b| {
let m = 0.5 * (a + b);
let v = 0.5 * (b_range.0 + b_range.1);
v3::dist(at(m, v), v3::scale(v3::add(at(a, v), at(b, v)), 0.5))
},
u0,
u1,
);
let columns = if a_wraps { n } else { n + 1 };
(0..columns)
.map(|i| u0 + (u1 - u0) * i as f64 / n as f64)
.collect()
}
};
let n_u = column_u.len();
if n_u < 3 {
return false;
}
let (fv0, fv1) = b_range;
if (fv1 - fv0).abs() < 1e-12 {
return false;
}
let steps = adaptive_steps(
tolerance,
|a, b| {
let mut worst = 0.0f64;
for &u in column_u.iter().take(8) {
worst = worst.max(v3::dist(
at(u, 0.5 * (a + b)),
v3::scale(v3::add(at(u, a), at(u, b)), 0.5),
));
}
worst
},
fv0,
fv1,
);
let rows = if b_wraps { steps } else { steps + 1 };
let row_v: Vec<f64> = (0..rows)
.map(|i| fv0 + (fv1 - fv0) * i as f64 / steps as f64)
.collect();
let near = |a: f64, b: f64| {
let mut d = (a - b).abs();
if b_periodic {
let period = std::f64::consts::TAU;
d = d.min((period - d).abs());
}
d <= (fv1 - fv0).abs() * 1e-3
};
let mut grid: Vec<Vec<u32>> = Vec::with_capacity(row_v.len());
let mut grid_u: Vec<Vec<f64>> = Vec::with_capacity(row_v.len());
for &v in &row_v {
if let Some(rim) = rims.iter().find(|(rv, _)| near(*rv, v)) {
let us: Vec<f64> = rim
.1
.iter()
.filter_map(|&vi| inv(self.vertices[vi]).map(|(u, _)| u))
.collect();
if us.len() == rim.1.len() && us.len() >= 3 {
grid.push(rim.1.iter().map(|&vi| emitted[vi]).collect());
grid_u.push(us);
continue;
}
}
let collapsed = {
let a = at(column_u[0], v);
let b = at(column_u[n_u / 2], v);
v3::dist(a, b) < tolerance * 1e-3
};
let mut push = |u: f64| -> u32 {
let p = at(u, v);
let mut n = nat(u, v).unwrap_or([0.0, 0.0, 1.0]);
if face.flipped {
n = v3::scale(n, -1.0);
}
let id = (positions.len() / 3) as u32;
positions.extend_from_slice(&[p[0] as f32, p[1] as f32, p[2] as f32]);
normals.extend_from_slice(&[n[0] as f32, n[1] as f32, n[2] as f32]);
id
};
if collapsed {
let id = push(column_u[0]);
grid.push(vec![id; n_u]);
} else {
grid.push(column_u.iter().map(|&u| push(u)).collect());
}
grid_u.push(column_u.clone());
}
for end in [0usize, 1] {
let col = |row: &Vec<u32>| if end == 0 { 0 } else { row.len() - 1 };
let param = |row: &Vec<f64>| if end == 0 { row[0] } else { row[row.len() - 1] };
if grid.iter().any(|r| r.is_empty()) {
break;
}
let anchor = at(param(&grid_u[0]), row_v[0]);
let same = grid_u
.iter()
.zip(&row_v)
.all(|(us, &v)| v3::dist(at(param(us), v), anchor) < tolerance * 1e-3);
if !same {
continue;
}
let shared = grid[0][col(&grid[0])];
for row in grid.iter_mut() {
let c = col(row);
row[c] = shared;
}
}
let last_row = if b_wraps { grid.len() } else { grid.len() - 1 };
for r in 0..last_row {
let r2 = (r + 1) % grid.len();
strip(
&grid[r],
&grid_u[r],
&grid[r2],
&grid_u[r2],
a_wraps,
face.flipped,
positions,
indices,
);
}
true
}
}
#[allow(clippy::too_many_arguments)]
fn refine_on_surface(
surface: &Surface,
flipped: bool,
ring_uv: &[[f64; 2]],
ring: &[u32],
tris: &[[usize; 3]],
tolerance: f64,
positions: &mut Vec<f32>,
normals: &mut Vec<f32>,
) -> Vec<[u32; 3]> {
let mut uv: Vec<[f64; 2]> = ring_uv.to_vec();
let mut id: Vec<u32> = ring.to_vec();
let mut faces: Vec<[usize; 3]> = tris.to_vec();
let n = ring_uv.len();
let near = {
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for q in ring_uv {
for k in 0..2 {
lo[k] = lo[k].min(q[k]);
hi[k] = hi[k].max(q[k]);
}
}
(hi[0] - lo[0]).max(hi[1] - lo[1]).max(1e-12) * 1e-9
};
let on_ring = |p: [f64; 2]| {
(0..n).any(|i| {
let (x, y) = (ring_uv[i], ring_uv[(i + 1) % n]);
let (dx, dy) = (y[0] - x[0], y[1] - x[1]);
let len2 = dx * dx + dy * dy;
let t = if len2 <= f64::MIN_POSITIVE {
0.0
} else {
(((p[0] - x[0]) * dx + (p[1] - x[1]) * dy) / len2).clamp(0.0, 1.0)
};
(p[0] - (x[0] + dx * t)).hypot(p[1] - (x[1] + dy * t)) <= near
})
};
let boundary = |a: usize, b: usize| {
if a < n && b < n && ((a + 1) % n == b || (b + 1) % n == a) {
return true;
}
if a < n && b < n {
let mid = [
0.5 * (ring_uv[a][0] + ring_uv[b][0]),
0.5 * (ring_uv[a][1] + ring_uv[b][1]),
];
return on_ring(mid);
}
false
};
if !matches!(surface, Surface::Plane { .. })
{
let flat = |t: &[usize; 3]| {
((uv[t[1]][0] - uv[t[0]][0]) * (uv[t[2]][1] - uv[t[0]][1])
- (uv[t[2]][0] - uv[t[0]][0]) * (uv[t[1]][1] - uv[t[0]][1]))
.abs()
<= near * near
};
let between = |a: usize, b: usize| -> Option<Vec<usize>> {
if a >= n || b >= n || (a + 1) % n == b || (b + 1) % n == a {
return None;
}
let (x, y) = (ring_uv[a], ring_uv[b]);
let (dx, dy) = (y[0] - x[0], y[1] - x[1]);
let len2 = dx * dx + dy * dy;
if len2 <= f64::MIN_POSITIVE {
return None;
}
let on = |p: [f64; 2]| -> Option<f64> {
let t = ((p[0] - x[0]) * dx + (p[1] - x[1]) * dy) / len2;
((0.0..=1.0).contains(&t)
&& (p[0] - (x[0] + dx * t)).hypot(p[1] - (x[1] + dy * t)) <= near)
.then_some(t)
};
for dir in [1isize, -1isize] {
let mut out: Vec<usize> = Vec::new();
let mut i = a;
let mut last = 0.0f64;
while out.len() + 2 <= n {
i = ((i as isize + dir).rem_euclid(n as isize)) as usize;
if i == b {
let (pa, pb) = (
surface.point(ring_uv[a][0], ring_uv[a][1]),
surface.point(ring_uv[b][0], ring_uv[b][1]),
);
let sags = out.iter().any(|&m| {
let q = surface.point(ring_uv[m][0], ring_uv[m][1]);
let (u, w) = (v3::sub(pb, pa), v3::sub(q, pa));
let len2 = v3::dot(u, u);
let t = if len2 > f64::MIN_POSITIVE {
(v3::dot(w, u) / len2).clamp(0.0, 1.0)
} else {
0.0
};
v3::dist(q, v3::add(pa, v3::scale(u, t))) > tolerance
});
return (sags && !out.is_empty()).then_some(out);
}
let Some(t) = on(ring_uv[i]).filter(|t| *t > last) else {
break;
};
last = t;
out.push(i);
}
}
None
};
for _ in 0..4 {
let mut paths: HashMap<(usize, usize), Vec<usize>> = HashMap::new();
for t in faces.iter() {
for k in 0..3 {
let (a, b) = (t[k], t[(k + 1) % 3]);
let key = (a.min(b), a.max(b));
if let std::collections::hash_map::Entry::Vacant(slot) = paths.entry(key)
&& let Some(mid) = between(key.0, key.1)
{
slot.insert(mid);
}
}
}
if paths.is_empty() {
break;
}
let mut run: std::collections::HashSet<usize> = std::collections::HashSet::new();
for ((a, b), mid) in &paths {
run.insert(*a);
run.insert(*b);
run.extend(mid.iter().copied());
}
let mut next: Vec<[usize; 3]> = Vec::with_capacity(faces.len());
for t in &faces {
if flat(t) && t.iter().all(|v| run.contains(v)) {
continue;
}
let hit = (0..3).find_map(|k| {
let (a, b, c) = (t[k], t[(k + 1) % 3], t[(k + 2) % 3]);
paths.get(&(a.min(b), a.max(b))).map(|m| (a, b, c, m))
});
let Some((a, b, c, mid)) = hit else {
next.push(*t);
continue;
};
let walk: Vec<usize> = if a < b {
mid.clone()
} else {
mid.iter().rev().copied().collect()
};
let mut prev = a;
for m in walk {
next.push([prev, m, c]);
prev = m;
}
next.push([prev, b, c]);
}
faces = next;
}
}
let emit = |uv: [f64; 2], positions: &mut Vec<f32>, normals: &mut Vec<f32>| -> u32 {
let p = surface.point(uv[0], uv[1]);
let mut nrm = surface.normal(uv[0], uv[1]).unwrap_or([0.0, 0.0, 1.0]);
if flipped {
nrm = v3::scale(nrm, -1.0);
}
positions.extend_from_slice(&[p[0] as f32, p[1] as f32, p[2] as f32]);
normals.extend_from_slice(&[nrm[0] as f32, nrm[1] as f32, nrm[2] as f32]);
(positions.len() / 3 - 1) as u32
};
for _ in 0..6 {
let mut split: HashMap<(usize, usize), usize> = HashMap::new();
for t in &faces {
for k in 0..3 {
let (a, b) = (t[k], t[(k + 1) % 3]);
if boundary(a, b) {
continue;
}
let key = (a.min(b), a.max(b));
if split.contains_key(&key) {
continue;
}
let mid = [0.5 * (uv[a][0] + uv[b][0]), 0.5 * (uv[a][1] + uv[b][1])];
let chord = v3::scale(
v3::add(
surface.point(uv[a][0], uv[a][1]),
surface.point(uv[b][0], uv[b][1]),
),
0.5,
);
if v3::dist(surface.point(mid[0], mid[1]), chord) <= tolerance {
continue;
}
uv.push(mid);
let vid = emit(mid, positions, normals);
id.push(vid);
split.insert(key, uv.len() - 1);
}
}
if split.is_empty() {
break;
}
let mut next: Vec<[usize; 3]> = Vec::with_capacity(faces.len() * 2);
for t in &faces {
let m: Vec<Option<usize>> = (0..3)
.map(|k| {
let (a, b) = (t[k], t[(k + 1) % 3]);
split.get(&(a.min(b), a.max(b))).copied()
})
.collect();
match (m[0], m[1], m[2]) {
(None, None, None) => next.push(*t),
(Some(x), Some(y), Some(z)) => {
next.push([t[0], x, z]);
next.push([x, t[1], y]);
next.push([z, y, t[2]]);
next.push([x, y, z]);
}
(Some(x), Some(y), None) => {
next.push([t[0], x, t[2]]);
next.push([x, t[1], y]);
next.push([x, y, t[2]]);
}
(None, Some(y), Some(z)) => {
next.push([t[1], y, t[0]]);
next.push([y, t[2], z]);
next.push([y, z, t[0]]);
}
(Some(x), None, Some(z)) => {
next.push([t[2], z, t[1]]);
next.push([z, t[0], x]);
next.push([z, x, t[1]]);
}
(Some(x), None, None) => {
next.push([t[0], x, t[2]]);
next.push([x, t[1], t[2]]);
}
(None, Some(y), None) => {
next.push([t[1], y, t[0]]);
next.push([y, t[2], t[0]]);
}
(None, None, Some(z)) => {
next.push([t[2], z, t[1]]);
next.push([z, t[0], t[1]]);
}
}
}
faces = next;
}
faces
.iter()
.map(|t| [id[t[0]], id[t[1]], id[t[2]]])
.collect()
}
fn extent_of(values: &[f64], periodic: bool) -> (f64, f64) {
if values.is_empty() {
return (0.0, 0.0);
}
let lo = values.iter().cloned().fold(f64::MAX, f64::min);
let hi = values.iter().cloned().fold(f64::MIN, f64::max);
if !periodic {
return (0.5 * (lo + hi), hi - lo);
}
use std::f64::consts::TAU;
let mut sorted = values.to_vec();
sorted.sort_by(|a, b| a.partial_cmp(b).unwrap_or(std::cmp::Ordering::Equal));
let mut gap = sorted[0] + TAU - sorted[sorted.len() - 1];
let mut after = sorted[0];
for w in sorted.windows(2) {
if w[1] - w[0] > gap {
gap = w[1] - w[0];
after = w[1];
}
}
let width = TAU - gap;
let mut mid = after + width * 0.5;
while mid > std::f64::consts::PI {
mid -= TAU;
}
(mid, width)
}
fn orient(
surfaces: &[Surface],
faces: &[Face],
triangle_face: &[u32],
positions: &[f32],
indices: &mut [u32],
) {
let count = indices.len() / 3;
if count == 0 {
return;
}
let mut by_edge: HashMap<(u32, u32), Vec<usize>> = HashMap::new();
for t in 0..count {
let tri = &indices[t * 3..t * 3 + 3];
for k in 0..3 {
let (a, b) = (tri[k], tri[(k + 1) % 3]);
by_edge.entry((a.min(b), a.max(b))).or_default().push(t);
}
}
let mut component = vec![usize::MAX; count];
let mut components = 0usize;
let mut stack = Vec::new();
for seed in 0..count {
if component[seed] != usize::MAX {
continue;
}
component[seed] = components;
stack.push(seed);
while let Some(t) = stack.pop() {
let tri = [indices[t * 3], indices[t * 3 + 1], indices[t * 3 + 2]];
for k in 0..3 {
let (a, b) = (tri[k], tri[(k + 1) % 3]);
let Some(users) = by_edge.get(&(a.min(b), a.max(b))) else {
continue;
};
if users.len() != 2 {
continue;
}
let n = if users[0] == t { users[1] } else { users[0] };
if n == t || component[n] != usize::MAX {
continue;
}
let other = [indices[n * 3], indices[n * 3 + 1], indices[n * 3 + 2]];
let same = (0..3).any(|j| other[j] == a && other[(j + 1) % 3] == b);
if same {
indices.swap(n * 3 + 1, n * 3 + 2);
}
component[n] = components;
stack.push(n);
}
}
components += 1;
}
let get = |k: u32| -> V3 {
let o = k as usize * 3;
[
positions[o] as f64,
positions[o + 1] as f64,
positions[o + 2] as f64,
]
};
let mut vote = vec![0i64; components];
for t in 0..count {
let tri = [indices[t * 3], indices[t * 3 + 1], indices[t * 3 + 2]];
let (a, b, c) = (get(tri[0]), get(tri[1]), get(tri[2]));
let n = v3::cross(v3::sub(b, a), v3::sub(c, a));
if v3::norm(n) < 1e-18 {
continue;
}
let Some(face) = triangle_face.get(t).and_then(|f| faces.get(*f as usize)) else {
continue;
};
let Some(surface) = surfaces.get(face.surface) else {
continue;
};
let centroid = [
(a[0] + b[0] + c[0]) / 3.0,
(a[1] + b[1] + c[1]) / 3.0,
(a[2] + b[2] + c[2]) / 3.0,
];
let Some(outward) = surface
.invert(centroid)
.and_then(|(u, v)| surface.normal(u, v))
else {
continue;
};
let outward = if face.flipped {
v3::scale(outward, -1.0)
} else {
outward
};
vote[component[t]] += if v3::dot(n, outward) > 0.0 { 1 } else { -1 };
}
for t in 0..count {
if vote[component[t]] < 0 {
indices.swap(t * 3 + 1, t * 3 + 2);
}
}
}
pub(crate) fn adaptive_steps(
tolerance: f64,
mut deviation: impl FnMut(f64, f64) -> f64,
a: f64,
b: f64,
) -> usize {
let mut steps = 1usize;
while steps < 512 {
let mut worst = 0.0f64;
for i in 0..steps {
let (p, q) = (
a + (b - a) * i as f64 / steps as f64,
a + (b - a) * (i + 1) as f64 / steps as f64,
);
worst = worst.max(deviation(p, q));
}
if worst <= tolerance {
return steps;
}
steps *= 2;
}
steps
}
#[allow(clippy::too_many_arguments)]
fn subdivide(
p: V3,
q: V3,
a: &Surface,
b: &Surface,
tolerance: f64,
depth: usize,
vertices: &mut Vec<V3>,
out: &mut Vec<usize>,
) {
if depth >= super::settings::settings().max_refine_depth {
return;
}
let mid = v3::scale(v3::add(p, q), 0.5);
if a.distance(mid).max(b.distance(mid)) <= tolerance {
return;
}
let mut m = mid;
for _ in 0..16 {
if a.distance(m) < 1e-12 && b.distance(m) < 1e-12 {
break;
}
let Some((au, av)) = a.invert(m) else { return };
m = a.point(au, av);
let Some((bu, bv)) = b.invert(m) else { return };
m = b.point(bu, bv);
}
if a.distance(m).max(b.distance(m)) > 1e-6 {
return;
}
subdivide(p, m, a, b, tolerance, depth + 1, vertices, out);
vertices.push(m);
out.push(vertices.len() - 1);
subdivide(m, q, a, b, tolerance, depth + 1, vertices, out);
}
fn centroid(v: &[V3; 3]) -> V3 {
[
(v[0][0] + v[1][0] + v[2][0]) / 3.0,
(v[0][1] + v[1][1] + v[2][1]) / 3.0,
(v[0][2] + v[1][2] + v[2][2]) / 3.0,
]
}
fn degenerate_at(positions: &[f32], a: u32, b: u32, c: u32) -> bool {
let g = |k: u32| {
let o = k as usize * 3;
[
positions[o] as f64,
positions[o + 1] as f64,
positions[o + 2] as f64,
]
};
let (pa, pb, pc) = (g(a), g(b), g(c));
let ab = v3::sub(pb, pa);
let ac = v3::sub(pc, pa);
let area = v3::norm(v3::cross(ab, ac));
let scale = v3::norm(ab).max(v3::norm(ac)).max(v3::dist(pb, pc));
area <= 1e-12 * scale * scale
}
fn count_boundary_edges(indices: &[u32]) -> usize {
let mut counts: HashMap<(u32, u32), usize> = HashMap::new();
for t in indices.as_chunks::<3>().0 {
for k in 0..3 {
let (a, b) = (t[k], t[(k + 1) % 3]);
*counts.entry((a.min(b), a.max(b))).or_insert(0) += 1;
}
}
counts.values().filter(|&&c| c == 1).count()
}
#[cfg(test)]
mod tests {
use super::*;
use crate::geometries::{BoxGeometry, CylinderGeometry};
const TAU: f32 = std::f32::consts::PI * 2.0;
#[test]
fn a_capped_cylinder_becomes_a_body_with_three_faces_and_two_edges() {
let g = CylinderGeometry::new(2.0, 2.0, 4.0, 24, 1, false, 0.0, TAU);
let body = Body::from_tagged_mesh(&g).expect("tagged");
assert_eq!(body.faces().len(), 3, "side plus two caps");
assert_eq!(body.edges().len(), 2, "one rim per cap");
for e in body.edges() {
assert!(e.closed);
assert!(e.vertices.len() >= 4);
}
}
#[test]
fn a_capped_cylinder_tessellates_closed() {
let g = CylinderGeometry::new(2.0, 2.0, 4.0, 24, 1, false, 0.0, TAU);
let mut body = Body::from_tagged_mesh(&g).unwrap();
body.refine_edges(1e-3);
let (out, report) = body.tessellate(1e-3);
assert_eq!(report.carried_through, 0, "a face was not filled");
assert!(
report.is_closed(),
"left {} open edges",
report.boundary_edges
);
for c in out
.get_attribute("position")
.unwrap()
.array
.as_chunks::<3>()
.0
{
let r = ((c[0] as f64).powi(2) + (c[2] as f64).powi(2)).sqrt();
assert!(r <= 2.0 + 1e-4, "radius {r}");
assert!((c[1] as f64).abs() <= 2.0 + 1e-4, "y {}", c[1]);
}
}
#[test]
fn a_cone_tessellates_closed() {
let g = CylinderGeometry::new(0.0, 2.0, 4.0, 24, 1, false, 0.0, TAU);
let mut body = Body::from_tagged_mesh(&g).unwrap();
body.refine_edges(1e-3);
let (_, report) = body.tessellate(1e-3);
assert_eq!(report.faces, 2);
assert!(report.is_closed(), "{} open edges", report.boundary_edges);
}
#[test]
fn a_box_tessellates_closed() {
let g = BoxGeometry::new(2.0, 3.0, 4.0);
let mut body = Body::from_tagged_mesh(&g).unwrap();
body.refine_edges(1e-3);
let (_, report) = body.tessellate(1e-3);
assert_eq!(report.faces, 6);
assert_eq!(report.edges, 12);
assert!(report.is_closed(), "{} open edges", report.boundary_edges);
}
#[test]
fn refining_edges_only_inserts_points() {
let g = CylinderGeometry::new(2.0, 2.0, 4.0, 8, 1, false, 0.0, TAU);
let mut body = Body::from_tagged_mesh(&g).unwrap();
let before: Vec<Vec<V3>> = body
.edges()
.iter()
.map(|e| e.vertices.iter().map(|&v| body.vertices()[v]).collect())
.collect();
body.refine_edges(1e-4);
for (e, original) in body.edges().iter().zip(&before) {
let now: Vec<V3> = e.vertices.iter().map(|&v| body.vertices()[v]).collect();
assert!(now.len() >= original.len(), "refinement dropped points");
for p in original {
assert!(
now.iter().any(|q| v3::dist(*p, *q) < 1e-12),
"an original edge point was lost"
);
}
}
}
#[test]
fn a_finer_tolerance_costs_more_triangles_and_stays_closed() {
let g = CylinderGeometry::new(2.0, 2.0, 4.0, 12, 1, false, 0.0, TAU);
let mut last = 0usize;
for &tol in &[1e-1, 1e-2, 1e-3] {
let mut body = Body::from_tagged_mesh(&g).unwrap();
body.refine_edges(tol);
let (_, report) = body.tessellate(tol);
assert!(report.is_closed(), "{tol}: {} open", report.boundary_edges);
assert!(
report.triangles > last,
"{tol}: {} triangles, previous {last}",
report.triangles
);
last = report.triangles;
}
}
#[test]
fn rims_of_different_refinement_still_join() {
let g = CylinderGeometry::new(1.0, 3.0, 4.0, 20, 1, false, 0.0, TAU);
let mut body = Body::from_tagged_mesh(&g).unwrap();
body.refine_edges(1e-3);
let counts: Vec<usize> = body.edges().iter().map(|e| e.vertices.len()).collect();
assert_eq!(counts.len(), 2);
assert_ne!(
counts[0], counts[1],
"the two rims should refine differently; if they stopped, this test \
no longer exercises the walk"
);
let (_, report) = body.tessellate(1e-3);
assert!(
report.is_closed(),
"{} open edges between rims of {} and {} points",
report.boundary_edges,
counts[0],
counts[1]
);
}
#[test]
fn a_boundary_less_face_still_fills() {
use crate::geometries::{SphereGeometry, TorusGeometry};
let cases: Vec<(&str, BufferGeometry, f64)> = vec![
("sphere", SphereGeometry::new(2.0, 20, 12), 2.0),
("torus", TorusGeometry::new(3.0, 1.0, 12, 20, TAU), 4.0),
];
for (name, g, scale) in cases {
let mut body = Body::from_tagged_mesh(&g).unwrap();
body.refine_edges(1e-3);
let (out, report) = body.tessellate(1e-3);
assert_eq!(report.faces, 1, "{name}");
assert_eq!(report.edges, 0, "{name}: a closed surface has no boundary");
assert_eq!(report.carried_through, 0, "{name}: the face was not filled");
assert!(report.triangles > 0, "{name}: empty mesh");
assert!(
report.is_closed(),
"{name}: {} open edges",
report.boundary_edges
);
let surface = &body.surfaces()[0];
for c in out
.get_attribute("position")
.unwrap()
.array
.as_chunks::<3>()
.0
{
let p = [c[0] as f64, c[1] as f64, c[2] as f64];
assert!(
surface.distance(p) < 1e-3 * scale,
"{name}: a vertex is {} off the surface",
surface.distance(p)
);
}
}
}
#[test]
fn an_open_cylinder_stays_open() {
let g = CylinderGeometry::new(1.0, 1.0, 3.0, 16, 1, true, 0.0, TAU);
let mut body = Body::from_tagged_mesh(&g).unwrap();
body.refine_edges(1e-3);
let (_, report) = body.tessellate(1e-3);
assert_eq!(report.faces, 1);
assert_eq!(report.edges, 0);
assert!(report.triangles > 0);
assert!(
!report.is_closed(),
"an open tube should report its two open rims"
);
}
#[test]
fn every_primitive_round_trips_through_a_body() {
use crate::geometries::{SphereGeometry, TorusGeometry};
let cases: Vec<(&str, BufferGeometry, bool)> = vec![
("box", BoxGeometry::new(2.0, 3.0, 4.0), true),
("sphere", SphereGeometry::new(1.5, 24, 14), true),
("torus", TorusGeometry::new(3.0, 1.0, 12, 24, TAU), true),
(
"capped cylinder",
CylinderGeometry::new(2.0, 2.0, 4.0, 20, 1, false, 0.0, TAU),
true,
),
(
"cone",
CylinderGeometry::new(0.0, 2.0, 4.0, 20, 1, false, 0.0, TAU),
true,
),
(
"truncated cone",
CylinderGeometry::new(1.0, 3.0, 4.0, 20, 1, false, 0.0, TAU),
true,
),
(
"open cylinder",
CylinderGeometry::new(1.0, 1.0, 2.0, 16, 1, true, 0.0, TAU),
false,
),
];
for (name, g, should_close) in cases {
let mut body = Body::from_tagged_mesh(&g).unwrap_or_else(|| panic!("{name}: no body"));
body.refine_edges(1e-3);
let (_, report) = body.tessellate(1e-3);
assert_eq!(report.carried_through, 0, "{name}: a face was not filled");
assert!(report.triangles > 0, "{name}: empty");
assert_eq!(
report.is_closed(),
should_close,
"{name}: closed = {}, expected {should_close} ({} open edges)",
report.is_closed(),
report.boundary_edges
);
}
}
#[test]
fn every_primitive_is_a_valid_solid() {
use crate::geometries::{SphereGeometry, TorusGeometry};
let cases: Vec<(&str, BufferGeometry, bool)> = vec![
("box", BoxGeometry::new(2.0, 3.0, 4.0), true),
("sphere", SphereGeometry::new(1.5, 24, 14), true),
("torus", TorusGeometry::new(3.0, 1.0, 12, 24, TAU), true),
(
"capped cylinder",
CylinderGeometry::new(2.0, 2.0, 4.0, 20, 1, false, 0.0, TAU),
true,
),
(
"cone",
CylinderGeometry::new(0.0, 2.0, 4.0, 20, 1, false, 0.0, TAU),
true,
),
(
"truncated cone",
CylinderGeometry::new(1.0, 3.0, 4.0, 20, 1, false, 0.0, TAU),
true,
),
(
"open cylinder",
CylinderGeometry::new(1.0, 1.0, 2.0, 16, 1, true, 0.0, TAU),
false,
),
];
for (name, g, solid) in cases {
let body = Body::from_tagged_mesh(&g).unwrap();
let defects = body.defects(1e-4);
assert_eq!(
body.is_valid_solid(1e-4),
solid,
"{name}: defects {defects:?}"
);
for d in &defects {
assert!(matches!(d, Defect::EdgeFaceCount { .. }), "{name}: {d:?}");
}
}
}
#[test]
fn a_face_may_meet_itself_along_a_seam() {
let mut body = Body::cylinder([0.0; 3], [0.0, 0.0, 1.0], 1.0, 2.0);
assert!(body.is_valid_solid(1e-4), "{:?}", body.defects(1e-4));
let side = body
.faces
.iter()
.position(|f| matches!(body.surfaces[f.surface], Surface::Cylinder { .. }))
.expect("a cylinder has a side");
let surface = body.surfaces[body.faces[side].surface].clone();
let rims = body.faces[side].edges.clone();
assert_eq!(rims.len(), 2, "a capped cylinder's side has two rims");
let start = body.edges[rims[0]].vertices[0];
let u0 = surface.invert(body.vertices[start]).expect("on the side").0;
let end = *body.edges[rims[1]]
.vertices
.iter()
.min_by(|&&a, &&b| {
let d = |v: usize| {
let u = surface.invert(body.vertices[v]).map_or(f64::MAX, |p| p.0);
(u - u0)
.abs()
.min((u - u0).abs() - std::f64::consts::TAU)
.abs()
};
d(a).total_cmp(&d(b))
})
.expect("the far rim has vertices");
let seam = body.edges.len();
body.edges.push(Edge {
surfaces: (body.faces[side].surface, body.faces[side].surface),
vertices: vec![start, end],
closed: false,
});
body.faces[side].edges.push(seam);
body.faces[side].edges.push(seam);
let defects = body.defects(1e-4);
assert!(
defects.is_empty(),
"a seam edge is not a defect: {defects:?}"
);
assert!(
body.shells().iter().all(|s| s.closed),
"adding a seam does not open a shell"
);
body.faces[side].edges.pop();
assert_eq!(
body.defects(1e-4),
vec![Defect::EdgeFaceCount {
edge: seam,
uses: 1
}]
);
}
#[test]
fn euler_characteristic_distinguishes_a_sphere_from_a_torus() {
use crate::geometries::{SphereGeometry, TorusGeometry};
let box_body = Body::from_tagged_mesh(&BoxGeometry::new(2.0, 2.0, 2.0)).unwrap();
let shells = box_body.shells();
assert_eq!(shells.len(), 1);
assert!(shells[0].closed);
assert!(
shells[0].euler_meaningful,
"a box has no periodic face, so nothing is unrepresented"
);
assert_eq!(shells[0].euler, 2, "a box is genus 0");
for (name, g) in [
("sphere", SphereGeometry::new(1.0, 12, 8)),
("torus", TorusGeometry::new(3.0, 1.0, 10, 16, TAU)),
] {
let b = Body::from_tagged_mesh(&g).unwrap();
let sh = &b.shells()[0];
assert_eq!(sh.euler, 1, "{name}");
assert!(
!sh.euler_meaningful,
"{name}: its seam is unrepresented, so 1 is not a genus claim"
);
assert!(sh.closed, "{name}: closed by its own periodicity");
}
}
#[test]
fn a_capped_cylinder_is_one_closed_shell() {
let g = CylinderGeometry::new(2.0, 2.0, 4.0, 16, 1, false, 0.0, TAU);
let body = Body::from_tagged_mesh(&g).unwrap();
let shells = body.shells();
assert_eq!(shells.len(), 1, "side and caps are all connected");
assert_eq!(shells[0].faces.len(), 3);
assert!(shells[0].closed);
assert!(
!shells[0].euler_meaningful,
"a periodic face has an unrepresented seam"
);
}
#[test]
fn an_open_tube_is_reported_as_open_not_as_valid() {
let g = CylinderGeometry::new(1.0, 1.0, 2.0, 12, 1, true, 0.0, TAU);
let body = Body::from_tagged_mesh(&g).unwrap();
assert!(!body.is_valid_solid(1e-4));
}
#[test]
fn a_dangling_reference_is_a_defect_not_a_panic() {
let g = CylinderGeometry::new(2.0, 2.0, 4.0, 12, 1, false, 0.0, TAU);
let mut body = Body::from_tagged_mesh(&g).unwrap();
let n = body.vertices().len();
body.edges[0].vertices.push(n + 99);
let defects = body.defects(1e-4);
assert!(
defects
.iter()
.any(|d| matches!(d, Defect::EdgeVertexMissing { .. })),
"{defects:?}"
);
}
#[test]
fn an_edge_that_is_not_on_its_surfaces_is_caught() {
let g = CylinderGeometry::new(2.0, 2.0, 4.0, 12, 1, false, 0.0, TAU);
let mut body = Body::from_tagged_mesh(&g).unwrap();
let vi = body.edges[0].vertices[0];
body.vertices[vi] = [99.0, 99.0, 99.0];
assert!(body
.defects(1e-4)
.iter()
.any(|d| matches!(d, Defect::EdgeOffSurface { .. })));
}
#[test]
fn authored_bodies_are_valid_solids_and_tessellate_closed() {
let cases: Vec<(&str, Body)> = vec![
("cuboid", Body::cuboid([2.0, 3.0, 4.0])),
("sphere", Body::sphere([0.0; 3], 2.0)),
("torus", Body::torus([0.0; 3], [0.0, 0.0, 1.0], 3.0, 1.0)),
(
"cylinder",
Body::cylinder([0.0; 3], [0.0, 0.0, 1.0], 2.0, 5.0),
),
("cone", Body::cone([0.0; 3], [0.0, 0.0, 1.0], 2.0, 4.0)),
(
"frustum",
Body::frustum([0.0; 3], [0.0, 0.0, 1.0], 3.0, 1.0, 4.0),
),
];
for (name, mut body) in cases {
assert!(
body.is_valid_solid(1e-6),
"{name}: {:?}",
body.defects(1e-6)
);
body.refine_edges(1e-3);
let (out, report) = body.tessellate(1e-3);
assert_eq!(report.carried_through, 0, "{name}: a face was not filled");
assert!(report.triangles > 0, "{name}: empty");
assert!(
report.is_closed(),
"{name}: {} open edges",
report.boundary_edges
);
assert!(out.get_attribute("position").unwrap().count() > 0);
}
}
#[test]
fn an_authored_cuboid_has_the_topology_a_box_has() {
let body = Body::cuboid([2.0, 2.0, 2.0]);
assert_eq!(body.faces().len(), 6);
assert_eq!(body.edges().len(), 12);
assert_eq!(body.vertices().len(), 8);
let shells = body.shells();
assert_eq!(shells.len(), 1);
assert!(shells[0].closed);
assert!(
shells[0].euler_meaningful,
"no periodic face, nothing hidden"
);
assert_eq!(shells[0].euler, 2, "8 − 12 + 6");
}
#[test]
fn a_transformed_body_is_still_a_solid() {
use crate::math::{Matrix4, Quaternion, Vector3};
let body = Body::cuboid([2.0, 4.0, 6.0]);
let m = Matrix4::compose(
Vector3::new(10.0, -3.0, 2.0),
Quaternion::from_axis_angle(Vector3::new(1.0, 1.0, 0.0).normalize(), 0.7),
Vector3::new(1.0, 1.0, 1.0),
);
let moved = body
.transform(&m)
.expect("a rigid motion carries every surface");
assert_eq!(moved.faces().len(), body.faces().len());
assert_eq!(moved.edges().len(), body.edges().len());
assert!(moved.is_valid_solid(1e-6), "{:?}", moved.defects(1e-6));
let (_, report) = {
let mut c = moved.clone();
c.refine_edges(1e-4);
c.tessellate(1e-4)
};
assert!(report.is_closed(), "{} open edges", report.boundary_edges);
}
#[test]
fn a_transform_that_cannot_be_represented_declines() {
use crate::math::{Matrix4, Vector3};
let squash = Matrix4::scale(Vector3::new(1.0, 1.0, 0.5));
assert!(Body::sphere([0.0; 3], 1.0).transform(&squash).is_none());
assert!(Body::cuboid([1.0, 1.0, 1.0]).transform(&squash).is_some());
}
#[test]
fn translating_preserves_volume_and_moves_the_centre() {
let a = Body::cuboid([2.0, 2.0, 2.0]);
let b = a.translated([5.0, 0.0, 0.0]).unwrap();
let bounds = |body: &Body| {
let mut lo = f64::MAX;
let mut hi = f64::MIN;
for v in body.vertices() {
lo = lo.min(v[0]);
hi = hi.max(v[0]);
}
(lo, hi)
};
assert_eq!(bounds(&a), (-1.0, 1.0));
assert_eq!(bounds(&b), (4.0, 6.0));
}
#[test]
fn an_authored_body_matches_the_shape_it_names() {
let mut body = Body::cylinder([0.0; 3], [0.0, 0.0, 1.0], 2.0, 5.0);
body.refine_edges(1e-3);
let (out, _) = body.tessellate(1e-3);
for c in out
.get_attribute("position")
.unwrap()
.array
.as_chunks::<3>()
.0
{
let r = ((c[0] as f64).powi(2) + (c[1] as f64).powi(2)).sqrt();
assert!(r <= 2.0 + 1e-3, "radius {r}");
assert!((-1e-3..=5.0 + 1e-3).contains(&(c[2] as f64)), "z {}", c[2]);
}
let mut sphere = Body::sphere([1.0, -2.0, 0.5], 3.0);
sphere.refine_edges(1e-3);
let (out, _) = sphere.tessellate(1e-3);
for c in out
.get_attribute("position")
.unwrap()
.array
.as_chunks::<3>()
.0
{
let d = v3::dist([c[0] as f64, c[1] as f64, c[2] as f64], [1.0, -2.0, 0.5]);
assert!((d - 3.0).abs() < 1e-3, "radius {d}");
}
}
#[test]
fn an_authored_cone_has_one_cap_not_two() {
let body = Body::cone([0.0; 3], [0.0, 0.0, 1.0], 2.0, 4.0);
assert_eq!(body.faces().len(), 2, "side and one disk");
assert_eq!(body.edges().len(), 1, "one rim");
assert!(body.is_valid_solid(1e-6));
}
#[test]
fn a_face_with_a_hole_is_trimmed_rather_than_filled_solid() {
let mut body = Body::plate_with_hole([10.0, 8.0, 2.0], 2.0).expect("fits");
assert_eq!(body.faces().len(), 7, "six plates and a bore");
assert_eq!(body.edges().len(), 14, "twelve box edges and two rims");
assert!(body.is_valid_solid(1e-6), "{:?}", body.defects(1e-6));
let top = body
.faces()
.iter()
.position(|f| {
matches!(&body.surfaces()[f.surface], Surface::Plane { normal, .. }
if (normal[2] - 1.0).abs() < 1e-9)
})
.expect("a +Z face");
let loops = body.face_loops(top);
assert_eq!(loops.len(), 2, "outer rectangle plus the bore");
assert_eq!(loops.iter().filter(|l| l.is_hole()).count(), 1);
body.refine_edges(1e-3);
let (out, report) = body.tessellate(1e-3);
assert_eq!(report.carried_through, 0, "a face was not filled");
assert!(report.is_closed(), "{} open edges", report.boundary_edges);
let pos = &out.get_attribute("position").unwrap().array;
let idx = out.index.as_ref().unwrap();
for t in idx.as_chunks::<3>().0 {
let mut c = [0.0f64; 3];
for &i in t {
let o = i as usize * 3;
c[0] += pos[o] as f64 / 3.0;
c[1] += pos[o + 1] as f64 / 3.0;
c[2] += pos[o + 2] as f64 / 3.0;
}
let r = (c[0] * c[0] + c[1] * c[1]).sqrt();
let on_a_cap = (c[2].abs() - 1.0).abs() < 1e-6;
assert!(
!(on_a_cap && r < 2.0 - 1e-3),
"a cap triangle sits inside the bore at radius {r}"
);
}
}
#[test]
fn a_hole_that_does_not_fit_is_refused() {
assert!(Body::plate_with_hole([4.0, 4.0, 1.0], 2.0).is_none());
assert!(Body::plate_with_hole([4.0, 4.0, 1.0], 0.0).is_none());
assert!(Body::plate_with_hole([4.0, 4.0, 1.0], 1.9).is_some());
}
#[test]
fn trim_loops_are_oriented_so_a_hole_reads_as_one() {
let body = Body::plate_with_hole([10.0, 8.0, 2.0], 2.0).unwrap();
for fi in 0..body.faces().len() {
let f = &body.faces()[fi];
if f.u_wraps || f.v_wraps {
continue;
}
let loops = body.face_loops(fi);
if loops.is_empty() {
continue;
}
assert_eq!(
loops.iter().filter(|l| l.is_outer()).count(),
1,
"face {fi} has more than one outer loop"
);
let outer = loops.iter().find(|l| l.is_outer()).unwrap();
for h in loops.iter().filter(|l| l.is_hole()) {
assert!(
h.area.abs() < outer.area.abs(),
"face {fi}: a hole is larger than its outer loop"
);
}
}
}
#[test]
fn without_provenance_there_is_no_body() {
let mut g = CylinderGeometry::new(1.0, 1.0, 2.0, 8, 1, false, 0.0, TAU);
g.surfaces = None;
assert!(Body::from_tagged_mesh(&g).is_none());
}
}
#[allow(clippy::too_many_arguments)]
fn strip(
lower: &[u32],
lower_u: &[f64],
upper: &[u32],
upper_u: &[f64],
wraps: bool,
flipped: bool,
positions: &[f32],
indices: &mut Vec<u32>,
) {
if lower.len() < 2 || upper.len() < 2 {
return;
}
let (nl, nu) = (lower.len(), upper.len());
let (steps_l, steps_u) = if wraps { (nl, nu) } else { (nl - 1, nu - 1) };
let (mut i, mut j) = (0usize, 0usize);
let emit = |a: u32, b: u32, c: u32, indices: &mut Vec<u32>| {
if degenerate_at(positions, a, b, c) {
return;
}
if flipped {
indices.extend_from_slice(&[a, c, b]);
} else {
indices.extend_from_slice(&[a, b, c]);
}
};
while i < steps_l || j < steps_u {
let pl = i as f64 / steps_l as f64;
let pu = j as f64 / steps_u as f64;
let take_lower = if i >= steps_l {
false
} else if j >= steps_u {
true
} else {
pl <= pu
};
if take_lower {
let a = lower[i % nl];
let b = lower[(i + 1) % nl];
let c = upper[j % nu];
emit(a, b, c, indices);
i += 1;
} else {
let a = upper[j % nu];
let b = lower[i % nl];
let c = upper[(j + 1) % nu];
emit(a, c, b, indices);
j += 1;
}
}
let _ = (lower_u, upper_u);
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Defect {
EdgeFaceCount { edge: usize, uses: usize },
FaceSurfaceMissing { face: usize, surface: usize },
EdgeVertexMissing { edge: usize, vertex: usize },
EdgeNotClosed { edge: usize },
EdgeOffSurface { edge: usize, deviation_scaled: u64 },
}
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct Shell {
pub faces: Vec<usize>,
pub closed: bool,
pub euler: i64,
pub euler_meaningful: bool,
}
impl Body {
pub fn shells(&self) -> Vec<Shell> {
let mut owner: Vec<Option<usize>> = vec![None; self.faces.len()];
let mut shells: Vec<Shell> = Vec::new();
for seed in 0..self.faces.len() {
if owner[seed].is_some() {
continue;
}
let id = shells.len();
let mut group = vec![seed];
owner[seed] = Some(id);
let mut queue = vec![seed];
while let Some(f) = queue.pop() {
for &e in &self.faces[f].edges {
for (g, other) in self.faces.iter().enumerate() {
if owner[g].is_none() && other.edges.contains(&e) {
owner[g] = Some(id);
group.push(g);
queue.push(g);
}
}
}
}
let mut edges: Vec<usize> = group
.iter()
.flat_map(|&f| self.faces[f].edges.iter().copied())
.collect();
edges.sort_unstable();
edges.dedup();
let edges_shared = edges.iter().all(|&e| {
group
.iter()
.map(|&f| self.faces[f].edges.iter().filter(|&&x| x == e).count())
.sum::<usize>()
== 2
});
let no_free_ends = group.iter().all(|&f| self.face_free_ends(f) == 0);
let closed = edges_shared && no_free_ends;
let euler_meaningful = group.iter().all(|&f| {
let face = &self.faces[f];
!face.u_wraps && !face.v_wraps && self.face_degenerate_ends(f) == 0
});
let mut vertices: Vec<usize> = Vec::new();
let mut segments = 0i64;
for &e in &edges {
let edge = &self.edges[e];
let n = edge.vertices.len();
if n < 2 {
continue;
}
segments += (n - 1) as i64;
let last = if edge.closed { n - 1 } else { n };
vertices.extend(&edge.vertices[..last]);
}
vertices.sort_unstable();
vertices.dedup();
shells.push(Shell {
euler: vertices.len() as i64 - segments + group.len() as i64,
faces: group,
closed,
euler_meaningful,
});
}
shells
}
pub fn face_free_ends(&self, face_index: usize) -> usize {
let face = &self.faces[face_index];
let mut degree: HashMap<usize, usize> = HashMap::new();
for &e in &face.edges {
for w in self.edges[e].vertices.windows(2) {
if w[0] == w[1] {
continue;
}
*degree.entry(w[0]).or_insert(0) += 1;
*degree.entry(w[1]).or_insert(0) += 1;
}
}
if degree.is_empty() {
let wraps_v = face.v_wraps || self.face_degenerate_ends(face_index) == 2;
return if face.u_wraps && wraps_v { 0 } else { 2 };
}
degree.values().filter(|d| *d % 2 == 1).count()
}
pub(crate) fn face_degenerate_ends(&self, face_index: usize) -> usize {
let face = &self.faces[face_index];
let surface = &self.surfaces[face.surface];
[face.v_range.0, face.v_range.1]
.iter()
.filter(|&&end| self.end_is_degenerate(face, surface, end))
.count()
}
fn end_is_degenerate(&self, face: &Face, surface: &Surface, v: f64) -> bool {
let (u0, u1) = face.u_range;
let a = surface.point(u0, v);
let b = surface.point(0.5 * (u0 + u1), v);
let scale = (u1 - u0).abs().max(1.0);
v3::dist(a, b) < scale * 1e-9
}
pub fn defects(&self, tolerance: f64) -> Vec<Defect> {
let mut out = Vec::new();
for (fi, face) in self.faces.iter().enumerate() {
if face.surface >= self.surfaces.len() {
out.push(Defect::FaceSurfaceMissing {
face: fi,
surface: face.surface,
});
}
}
for (ei, edge) in self.edges.iter().enumerate() {
for &v in &edge.vertices {
if v >= self.vertices.len() {
out.push(Defect::EdgeVertexMissing {
edge: ei,
vertex: v,
});
}
}
if edge.closed && edge.vertices.first() != edge.vertices.last() {
out.push(Defect::EdgeNotClosed { edge: ei });
}
let uses: usize = self
.faces
.iter()
.map(|f| f.edges.iter().filter(|&&e| e == ei).count())
.sum();
if uses != 2 {
out.push(Defect::EdgeFaceCount { edge: ei, uses });
}
let (a, b) = (edge.surfaces.0, edge.surfaces.1);
if a < self.surfaces.len() && b < self.surfaces.len() {
let mut worst = 0.0f64;
for &v in &edge.vertices {
if v < self.vertices.len() {
let p = self.vertices[v];
worst = worst
.max(self.surfaces[a].distance(p))
.max(self.surfaces[b].distance(p));
}
}
if worst > tolerance {
out.push(Defect::EdgeOffSurface {
edge: ei,
deviation_scaled: (worst / tolerance) as u64,
});
}
}
}
out
}
pub fn is_valid_solid(&self, tolerance: f64) -> bool {
self.defects(tolerance).is_empty() && self.shells().iter().all(|s| s.closed)
}
}
impl Body {
pub fn transform(&self, m: &Matrix4) -> Option<Body> {
let surfaces: Option<Vec<Surface>> = self.surfaces.iter().map(|s| s.transform(m)).collect();
let a = super::surface::Affine::from_matrix4(m)?;
let vertices = self.vertices.iter().map(|p| a.point(*p)).collect();
Some(Body {
surfaces: surfaces?,
vertices,
edges: self.edges.clone(),
faces: self.faces.clone(),
})
}
pub fn translated(&self, offset: V3) -> Option<Body> {
self.transform(&Matrix4::translation(crate::math::Vector3::new(
offset[0] as f32,
offset[1] as f32,
offset[2] as f32,
)))
}
pub fn cuboid(size: V3) -> Body {
let (hx, hy, hz) = (size[0] * 0.5, size[1] * 0.5, size[2] * 0.5);
let corner = |i: usize| -> V3 {
[
if i & 1 == 0 { -hx } else { hx },
if i & 2 == 0 { -hy } else { hy },
if i & 4 == 0 { -hz } else { hz },
]
};
let vertices: Vec<V3> = (0..8).map(corner).collect();
let surfaces = vec![
Surface::plane([hx, 0.0, 0.0], [1.0, 0.0, 0.0]),
Surface::plane([-hx, 0.0, 0.0], [-1.0, 0.0, 0.0]),
Surface::plane([0.0, hy, 0.0], [0.0, 1.0, 0.0]),
Surface::plane([0.0, -hy, 0.0], [0.0, -1.0, 0.0]),
Surface::plane([0.0, 0.0, hz], [0.0, 0.0, 1.0]),
Surface::plane([0.0, 0.0, -hz], [0.0, 0.0, -1.0]),
];
let spec: [(usize, usize, usize, usize); 12] = [
(0, 2, 3, 7),
(0, 3, 1, 5),
(0, 4, 5, 7),
(0, 5, 1, 3),
(1, 2, 2, 6),
(1, 3, 0, 4),
(1, 4, 4, 6),
(1, 5, 0, 2),
(2, 4, 6, 7),
(2, 5, 2, 3),
(3, 4, 4, 5),
(3, 5, 0, 1),
];
let edges: Vec<Edge> = spec
.iter()
.map(|&(a, b, v0, v1)| Edge {
surfaces: (a.min(b), a.max(b)),
vertices: vec![v0, v1],
closed: false,
})
.collect();
let faces = (0..6)
.map(|si| Face {
surface: si,
edges: (0..edges.len())
.filter(|&e| edges[e].surfaces.0 == si || edges[e].surfaces.1 == si)
.collect(),
flipped: false,
u_range: (-hx.max(hy).max(hz) * 2.0, hx.max(hy).max(hz) * 2.0),
v_range: (-hx.max(hy).max(hz) * 2.0, hx.max(hy).max(hz) * 2.0),
u_wraps: false,
v_wraps: false,
loops: None,
})
.collect();
Body {
surfaces,
vertices,
edges,
faces,
}
}
pub fn sphere(center: V3, radius: f64) -> Body {
Body::single_face(
Surface::sphere(center, radius),
(-std::f64::consts::PI, std::f64::consts::PI),
(-std::f64::consts::FRAC_PI_2, std::f64::consts::FRAC_PI_2),
true,
false,
)
}
pub fn torus(center: V3, axis: V3, major: f64, minor: f64) -> Body {
Body::single_face(
Surface::torus(center, axis, major, minor),
(-std::f64::consts::PI, std::f64::consts::PI),
(-std::f64::consts::PI, std::f64::consts::PI),
true,
true,
)
}
pub fn cylinder(base: V3, axis: V3, radius: f64, height: f64) -> Body {
Body::revolved(base, axis, radius, radius, height)
}
pub fn cone(base: V3, axis: V3, radius: f64, height: f64) -> Body {
Body::revolved(base, axis, 0.0, radius, height)
}
pub fn frustum(base: V3, axis: V3, radius_bottom: f64, radius_top: f64, height: f64) -> Body {
Body::revolved(base, axis, radius_top, radius_bottom, height)
}
fn single_face(
surface: Surface,
u_range: (f64, f64),
v_range: (f64, f64),
u_wraps: bool,
v_wraps: bool,
) -> Body {
Body {
surfaces: vec![surface],
vertices: Vec::new(),
edges: Vec::new(),
faces: vec![Face {
surface: 0,
edges: Vec::new(),
flipped: false,
u_range,
v_range,
u_wraps,
v_wraps,
loops: None,
}],
}
}
fn revolved(base: V3, axis: V3, radius_top: f64, radius_bottom: f64, height: f64) -> Body {
use std::f64::consts::{PI, TAU};
let nominal = super::settings::settings().rim_segments.max(3);
let axis = crate::nurbs::v3::normalize(axis).unwrap_or([0.0, 0.0, 1.0]);
let side = if (radius_top - radius_bottom).abs() < 1e-12 {
Surface::cylinder(base, axis, radius_bottom)
} else {
let y_apex = height * radius_bottom / (radius_bottom - radius_top);
let apex = v3::add(base, v3::scale(axis, y_apex));
let (dir, far_r, far_d) = if radius_bottom > radius_top {
(v3::scale(axis, -1.0), radius_bottom, y_apex)
} else {
(axis, radius_top, height - y_apex)
};
match Surface::cone_from_rim(apex, dir, far_r, far_d.abs()) {
Some(c) => c,
None => Surface::cylinder(base, axis, radius_bottom.max(radius_top)),
}
};
let top_centre = v3::add(base, v3::scale(axis, height));
let mut surfaces = vec![side];
let mut vertices: Vec<V3> = Vec::new();
let mut edges: Vec<Edge> = Vec::new();
let bottom_plane = surfaces.len();
surfaces.push(Surface::plane(base, v3::scale(axis, -1.0)));
let side_surface = surfaces[0].clone();
let rim = |centre: V3, r: f64, vertices: &mut Vec<V3>| -> Vec<usize> {
let s = &side_surface;
let mut ids = Vec::with_capacity(nominal + 1);
for i in 0..nominal {
let u = -PI + TAU * i as f64 / nominal as f64;
let p = match s.invert(v3::add(
centre,
v3::scale(crate::nurbs::construct::perpendicular(axis), r),
)) {
Some((_, v)) => s.point(u, v),
None => centre,
};
vertices.push(p);
ids.push(vertices.len() - 1);
}
ids.push(ids[0]);
ids
};
let bottom = rim(base, radius_bottom, &mut vertices);
edges.push(Edge {
surfaces: (0, bottom_plane),
vertices: bottom,
closed: true,
});
let mut top_plane = None;
if radius_top > 1e-12 {
let plane = surfaces.len();
surfaces.push(Surface::plane(top_centre, axis));
let top = rim(top_centre, radius_top, &mut vertices);
edges.push(Edge {
surfaces: (0, plane),
vertices: top,
closed: true,
});
top_plane = Some(plane);
}
let (v_lo, v_hi) = {
let s = &side_surface;
let a = s.invert(vertices[0]).map(|(_, v)| v).unwrap_or(0.0);
let b = s
.invert(*vertices.last().unwrap())
.map(|(_, v)| v)
.unwrap_or(height);
let apex_v = if radius_top <= 1e-12 { Some(0.0) } else { None };
let lo = a.min(b).min(apex_v.unwrap_or(f64::INFINITY));
let hi = a.max(b).max(apex_v.unwrap_or(f64::NEG_INFINITY));
(lo, hi)
};
let mut faces = vec![Face {
surface: 0,
edges: (0..edges.len()).collect(),
flipped: false,
u_range: (-PI, PI),
v_range: (v_lo, v_hi),
u_wraps: true,
v_wraps: false,
loops: None,
}];
for (plane, edge) in [Some(bottom_plane), top_plane]
.into_iter()
.flatten()
.zip(0..)
{
faces.push(Face {
surface: plane,
edges: vec![edge],
flipped: false,
u_range: (
-radius_bottom.max(radius_top),
radius_bottom.max(radius_top),
),
v_range: (
-radius_bottom.max(radius_top),
radius_bottom.max(radius_top),
),
u_wraps: false,
v_wraps: false,
loops: None,
});
}
Body {
surfaces,
vertices,
edges,
faces,
}
}
}
#[derive(Debug, Clone, PartialEq)]
pub struct TrimLoop {
pub vertices: Vec<usize>,
pub uv: Vec<[f64; 2]>,
pub area: f64,
}
pub enum Footprint<'a> {
Rectangle { u: (f64, f64), v: (f64, f64) },
Rings(&'a [TrimLoop]),
}
impl<'a> Footprint<'a> {
pub fn of(loops: &'a [TrimLoop], u: (f64, f64), v: (f64, f64)) -> Footprint<'a> {
if loops.iter().any(|l| l.is_outer()) {
Footprint::Rings(loops)
} else {
Footprint::Rectangle { u, v }
}
}
}
impl Face {
pub fn footprint(&self) -> Footprint<'_> {
match self.loops.as_deref() {
Some(ls) => Footprint::of(ls, self.u_range, self.v_range),
None => Footprint::Rectangle {
u: self.u_range,
v: self.v_range,
},
}
}
}
impl TrimLoop {
pub fn is_degenerate(&self) -> bool {
if self.uv.len() < 3 {
return true;
}
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for c in &self.uv {
for k in 0..2 {
lo[k] = lo[k].min(c[k]);
hi[k] = hi[k].max(c[k]);
}
}
let flat = (0..2).any(|k| hi[k] - lo[k] <= 1e-12 * (1.0 + lo[k].abs().max(hi[k].abs())));
let extent = (hi[0] - lo[0]) * (hi[1] - lo[1]);
flat || extent <= 0.0 || self.area.abs() <= extent * 1e-9
}
pub fn is_outer(&self) -> bool {
!self.is_degenerate() && self.area > 0.0
}
pub fn is_hole(&self) -> bool {
!self.is_degenerate() && self.area < 0.0
}
pub fn wraps(&self, period: (Option<f64>, Option<f64>)) -> [bool; 2] {
let mut out = [false; 2];
for (k, span) in [period.0, period.1].into_iter().enumerate() {
let Some(span) = span else { continue };
#[allow(clippy::neg_cmp_op_on_partial_ord)]
if !(span > 0.0) || self.uv.len() < 2 {
continue;
}
let mut travel = 0.0;
for i in 0..self.uv.len() {
let step = self.uv[(i + 1) % self.uv.len()][k] - self.uv[i][k];
let folded = step - span * (step / span).round();
travel += folded;
}
out[k] = travel.abs() > span * 0.5;
}
out
}
pub fn contains(&self, p: [f64; 2], period: (Option<f64>, Option<f64>)) -> bool {
let n = self.uv.len();
if n < 3 {
return false;
}
let mid = |k: usize| {
let lo = self.uv.iter().map(|c| c[k]).fold(f64::MAX, f64::min);
let hi = self.uv.iter().map(|c| c[k]).fold(f64::MIN, f64::max);
(lo + hi) * 0.5
};
let fold = |x: f64, k: usize, period: Option<f64>| match period {
Some(t) => x - t * ((x - mid(k)) / t).round(),
None => x,
};
let q = [fold(p[0], 0, period.0), fold(p[1], 1, period.1)];
let mut inside = false;
let mut j = n - 1;
for i in 0..n {
let (a, b) = (self.uv[i], self.uv[j]);
if (a[1] > q[1]) != (b[1] > q[1])
&& q[0] < (b[0] - a[0]) * (q[1] - a[1]) / (b[1] - a[1]) + a[0]
{
inside = !inside;
}
j = i;
}
inside
}
}
impl Body {
pub fn face_loops(&self, face_index: usize) -> Vec<TrimLoop> {
let face = &self.faces[face_index];
if let Some(given) = &face.loops {
return given.clone();
}
let surface = &self.surfaces[face.surface];
let mut segments: Vec<(usize, usize)> = Vec::new();
for &e in &face.edges {
let v = &self.edges[e].vertices;
for w in v.windows(2) {
if w[0] != w[1] {
segments.push((w[0], w[1]));
}
}
}
if segments.is_empty() {
return Vec::new();
}
let mut used = vec![false; segments.len()];
let mut rings: Vec<Vec<usize>> = Vec::new();
for seed in 0..segments.len() {
if used[seed] {
continue;
}
used[seed] = true;
let mut ring = vec![segments[seed].0, segments[seed].1];
loop {
let tail = *ring.last().unwrap();
let Some(i) = (0..segments.len())
.find(|&i| !used[i] && (segments[i].0 == tail || segments[i].1 == tail))
else {
break;
};
used[i] = true;
let (p, q) = segments[i];
ring.push(if p == tail { q } else { p });
}
if ring.len() > 2 && ring[0] == *ring.last().unwrap() {
ring.pop();
rings.push(ring);
}
}
let mut loops: Vec<TrimLoop> = Vec::new();
for ring in rings {
let mut uv: Vec<[f64; 2]> = Vec::with_capacity(ring.len());
let mut ok = true;
let (periodic_u, periodic_v) = surface.periodic();
let mut anchor: Option<[f64; 2]> = None;
for &vi in &ring {
match surface.invert(self.vertices[vi]) {
Some((mut u, mut v)) => {
if let Some(a) = anchor {
if periodic_u {
u = unwrap_near(u, a[0]);
}
if periodic_v {
v = unwrap_near(v, a[1]);
}
}
anchor = Some([u, v]);
uv.push([u, v]);
}
None => {
ok = false;
break;
}
}
}
if !ok || uv.len() < 3 {
continue;
}
let area = signed_area(&uv);
loops.push(TrimLoop {
vertices: ring,
uv,
area,
});
}
if let Some(outer) = loops
.iter()
.enumerate()
.max_by(|a, b| a.1.area.abs().partial_cmp(&b.1.area.abs()).unwrap())
.map(|(i, _)| i)
{
let flip = loops[outer].area < 0.0;
for (i, l) in loops.iter_mut().enumerate() {
if flip {
l.area = -l.area;
l.vertices.reverse();
l.uv.reverse();
}
if i != outer && l.area > 0.0 {
l.area = -l.area;
l.vertices.reverse();
l.uv.reverse();
}
}
}
loops
}
}
fn near(x: f64, anchor: f64) -> f64 {
use std::f64::consts::TAU;
x - TAU * ((x - anchor) / TAU).round()
}
fn signed_area(uv: &[[f64; 2]]) -> f64 {
let n = uv.len();
let mut a = 0.0;
for i in 0..n {
let (p, q) = (uv[i], uv[(i + 1) % n]);
a += p[0] * q[1] - q[0] * p[1];
}
a * 0.5
}
fn unwrap_near(x: f64, anchor: f64) -> f64 {
use std::f64::consts::TAU;
x - TAU * ((x - anchor) / TAU).round()
}
fn bridge_holes(
outer: &[[f64; 2]],
holes: &[Vec<[f64; 2]>],
) -> Option<(Vec<[f64; 2]>, Vec<usize>)> {
let mut ring: Vec<[f64; 2]> = outer.to_vec();
let mut map: Vec<usize> = (0..outer.len()).collect();
let mut offsets: Vec<usize> = vec![0];
for h in holes {
offsets.push(offsets.last().unwrap() + h.len());
}
let mut order: Vec<usize> = (0..holes.len()).collect();
order.sort_by(|&a, &b| {
let ra = holes[a].iter().cloned().fold(f64::MIN, |m, p| m.max(p[0]));
let rb = holes[b].iter().cloned().fold(f64::MIN, |m, p| m.max(p[0]));
rb.partial_cmp(&ra).unwrap()
});
let mut merged: Vec<usize> = Vec::with_capacity(holes.len());
for hi in order {
let hole = &holes[hi];
let mv = (0..hole.len()).max_by(|&a, &b| hole[a][0].partial_cmp(&hole[b][0]).unwrap())?;
let m = mv;
let p = hole[m];
let blocked = |q: [f64; 2], qi: usize| -> bool {
let n = ring.len();
for i in 0..n {
if i == qi || (i + 1) % n == qi {
continue;
}
if crosses(p, q, ring[i], ring[(i + 1) % n]) {
return true;
}
}
for (j, other) in holes.iter().enumerate() {
if merged.contains(&j) {
continue; }
let m = other.len();
for i in 0..m {
if j == hi && (i == mv || (i + 1) % m == mv) {
continue;
}
if crosses(p, q, other[i], other[(i + 1) % m]) {
return true;
}
}
}
false
};
let flat = |a: [f64; 2], b: [f64; 2], c: [f64; 2]| {
let cross = (b[0] - a[0]) * (c[1] - a[1]) - (b[1] - a[1]) * (c[0] - a[0]);
let scale = ((b[0] - a[0]).hypot(b[1] - a[1])).max(1e-12);
(cross / scale).abs() < 1e-9
};
let tangent = |q: [f64; 2], qi: usize| -> bool {
let n = ring.len();
flat(p, ring[(qi + n - 1) % n], q) || flat(p, ring[(qi + 1) % n], q)
};
let mut candidates: Vec<(bool, f64, usize)> = ring
.iter()
.enumerate()
.map(|(i, &q)| {
let outer_vertex = map[i] < outer.len();
(
!outer_vertex,
(q[0] - p[0]).powi(2) + (q[1] - p[1]).powi(2),
i,
)
})
.collect();
candidates.sort_by(|a, b| {
a.0.cmp(&b.0)
.then(a.1.partial_cmp(&b.1).unwrap_or(std::cmp::Ordering::Equal))
});
let ok = |i: usize| !tangent(ring[i], i) && !blocked(ring[i], i);
let bridge = candidates
.iter()
.find(|&&(_, _, i)| ring[i][0] >= p[0] && ok(i))
.or_else(|| candidates.iter().find(|&&(_, _, i)| ok(i)))
.or_else(|| candidates.iter().find(|&&(_, _, i)| !blocked(ring[i], i)))
.map(|&(_, _, i)| i)?;
let mut spliced: Vec<[f64; 2]> = ring[..=bridge].to_vec();
let mut spliced_map: Vec<usize> = map[..=bridge].to_vec();
for k in 0..=hole.len() {
let idx = (m + k) % hole.len();
spliced.push(hole[idx]);
spliced_map.push(outer.len() + offsets[hi] + idx);
}
spliced.extend_from_slice(&ring[bridge..]);
spliced_map.extend_from_slice(&map[bridge..]);
ring = spliced;
map = spliced_map;
merged.push(hi);
}
Some((ring, map))
}
fn crosses(a: [f64; 2], b: [f64; 2], c: [f64; 2], d: [f64; 2]) -> bool {
let side = |p: [f64; 2], q: [f64; 2], r: [f64; 2]| {
(q[0] - p[0]) * (r[1] - p[1]) - (q[1] - p[1]) * (r[0] - p[0])
};
let (d1, d2) = (side(c, d, a), side(c, d, b));
let (d3, d4) = (side(a, b, c), side(a, b, d));
((d1 > 0.0) != (d2 > 0.0)) && ((d3 > 0.0) != (d4 > 0.0))
}
impl Body {
pub fn plate_with_hole(size: V3, radius: f64) -> Option<Body> {
Body::plate_with_holes(size, &[([0.0, 0.0], radius)])
}
pub fn plate_with_holes(size: V3, holes: &[([f64; 2], f64)]) -> Option<Body> {
use std::f64::consts::{PI, TAU};
let nominal = super::settings::settings().rim_segments.max(3);
let (hx, hy, hz) = (size[0] * 0.5, size[1] * 0.5, size[2] * 0.5);
if holes.is_empty() {
return None;
}
for (i, &(c, r)) in holes.iter().enumerate() {
#[allow(clippy::neg_cmp_op_on_partial_ord)]
if !(r > 0.0) || c[0].abs() + r >= hx || c[1].abs() + r >= hy {
return None;
}
for &(d, s) in &holes[i + 1..] {
if ((c[0] - d[0]).powi(2) + (c[1] - d[1]).powi(2)).sqrt() <= r + s {
return None;
}
}
}
let mut surfaces = vec![
Surface::plane([hx, 0.0, 0.0], [1.0, 0.0, 0.0]),
Surface::plane([-hx, 0.0, 0.0], [-1.0, 0.0, 0.0]),
Surface::plane([0.0, hy, 0.0], [0.0, 1.0, 0.0]),
Surface::plane([0.0, -hy, 0.0], [0.0, -1.0, 0.0]),
Surface::plane([0.0, 0.0, hz], [0.0, 0.0, 1.0]),
Surface::plane([0.0, 0.0, -hz], [0.0, 0.0, -1.0]),
];
let first_bore = surfaces.len();
for &(c, r) in holes {
surfaces.push(Surface::cylinder([c[0], c[1], 0.0], [0.0, 0.0, 1.0], r));
}
let corner = |i: usize| -> V3 {
[
if i & 1 == 0 { -hx } else { hx },
if i & 2 == 0 { -hy } else { hy },
if i & 4 == 0 { -hz } else { hz },
]
};
let mut vertices: Vec<V3> = (0..8).map(corner).collect();
let box_spec: [(usize, usize, usize, usize); 12] = [
(0, 2, 3, 7),
(0, 3, 1, 5),
(0, 4, 5, 7),
(0, 5, 1, 3),
(1, 2, 2, 6),
(1, 3, 0, 4),
(1, 4, 4, 6),
(1, 5, 0, 2),
(2, 4, 6, 7),
(2, 5, 2, 3),
(3, 4, 4, 5),
(3, 5, 0, 1),
];
let mut edges: Vec<Edge> = box_spec
.iter()
.map(|&(a, b, v0, v1)| Edge {
surfaces: (a.min(b), a.max(b)),
vertices: vec![v0, v1],
closed: false,
})
.collect();
for b in 0..holes.len() {
let bore = first_bore + b;
for (plane, z) in [(4usize, hz), (5usize, -hz)] {
let mut ids = Vec::with_capacity(nominal + 1);
for i in 0..nominal {
let u = -PI + TAU * i as f64 / nominal as f64;
vertices.push(surfaces[bore].point(u, z));
ids.push(vertices.len() - 1);
}
ids.push(ids[0]);
edges.push(Edge {
surfaces: (plane.min(bore), plane.max(bore)),
vertices: ids,
closed: true,
});
}
}
let big = hx.max(hy).max(hz) * 2.0;
let mut faces: Vec<Face> = (0..6)
.map(|si| Face {
surface: si,
edges: (0..edges.len())
.filter(|&e| edges[e].surfaces.0 == si || edges[e].surfaces.1 == si)
.collect(),
flipped: false,
u_range: (-big, big),
v_range: (-big, big),
u_wraps: false,
v_wraps: false,
loops: None,
})
.collect();
for b in 0..holes.len() {
let bore = first_bore + b;
faces.push(Face {
surface: bore,
edges: (0..edges.len())
.filter(|&e| edges[e].surfaces.0 == bore || edges[e].surfaces.1 == bore)
.collect(),
flipped: true,
u_range: (-PI, PI),
v_range: (-hz, hz),
u_wraps: true,
v_wraps: false,
loops: None,
});
}
Some(Body::from_parts(surfaces, vertices, edges, faces))
}
}
#[cfg(feature = "brep-csg")]
fn constrained_fill(
points: &[[f64; 2]],
outer: usize,
holes: &[Vec<[f64; 2]>],
ring_map: &[usize],
) -> Option<Vec<[usize; 3]>> {
use crate::exact_csg::cdt::triangulate_constrained;
let mut sizes = vec![outer];
sizes.extend(holes.iter().map(|h| h.len()));
if sizes.iter().sum::<usize>() != points.len() {
return None;
}
let (mut lo, mut hi) = ([f64::INFINITY; 2], [f64::NEG_INFINITY; 2]);
for p in points {
for k in 0..2 {
lo[k] = lo[k].min(p[k]);
hi[k] = hi[k].max(p[k]);
}
}
let span = (hi[0] - lo[0]).max(hi[1] - lo[1]).max(1e-12);
let c = [(lo[0] + hi[0]) * 0.5, (lo[1] + hi[1]) * 0.5];
let mut pts = vec![
[c[0] - 20.0 * span, c[1] - 10.0 * span],
[c[0] + 20.0 * span, c[1] - 10.0 * span],
[c[0], c[1] + 20.0 * span],
];
pts.extend_from_slice(points);
let mut constraints = Vec::new();
let mut rings: Vec<Vec<[f64; 2]>> = Vec::new();
let mut start = 0;
for &n in &sizes {
for k in 0..n {
constraints.push([3 + start + k, 3 + start + (k + 1) % n]);
}
rings.push(points[start..start + n].to_vec());
start += n;
}
let tris = triangulate_constrained(&pts, &constraints)?;
let mut at: Vec<Option<usize>> = vec![None; points.len()];
for (j, &k) in ring_map.iter().enumerate() {
if k < at.len() && at[k].is_none() {
at[k] = Some(j);
}
}
let inside = |p: [f64; 2]| {
let mut odd = false;
for r in &rings {
let n = r.len();
for i in 0..n {
let (a, b) = (r[i], r[(i + 1) % n]);
if (a[1] > p[1]) != (b[1] > p[1])
&& p[0] < a[0] + (p[1] - a[1]) / (b[1] - a[1]) * (b[0] - a[0])
{
odd = !odd;
}
}
}
odd
};
let mut out = Vec::with_capacity(tris.len());
for t in tris {
if t.iter().any(|&i| i < 3) {
continue;
}
let (a, b, d) = (pts[t[0]], pts[t[1]], pts[t[2]]);
if !inside([(a[0] + b[0] + d[0]) / 3.0, (a[1] + b[1] + d[1]) / 3.0]) {
continue;
}
let ids = [at[t[0] - 3]?, at[t[1] - 3]?, at[t[2] - 3]?];
let cross = (b[0] - a[0]) * (d[1] - a[1]) - (b[1] - a[1]) * (d[0] - a[0]);
out.push(if cross >= 0.0 {
ids
} else {
[ids[0], ids[2], ids[1]]
});
}
Some(out)
}
fn earclip(points: &[[f64; 2]]) -> Vec<[usize; 3]> {
let n = points.len();
if n < 3 {
return Vec::new();
}
let area2 = |a: [f64; 2], b: [f64; 2], c: [f64; 2]| {
(b[0] - a[0]) * (c[1] - a[1]) - (c[0] - a[0]) * (b[1] - a[1])
};
let mut idx: Vec<usize> = (0..n).collect();
if signed_area(points) < 0.0 {
idx.reverse();
}
let same =
|p: [f64; 2], q: [f64; 2]| (p[0] - q[0]).abs() < 1e-12 && (p[1] - q[1]).abs() < 1e-12;
let inside = |a: [f64; 2], b: [f64; 2], c: [f64; 2], p: [f64; 2]| {
if same(p, a) || same(p, b) || same(p, c) {
return false;
}
area2(a, b, p) > 0.0 && area2(b, c, p) > 0.0 && area2(c, a, p) > 0.0
};
let extent = {
let (mut lo, mut hi) = ([f64::MAX; 2], [f64::MIN; 2]);
for q in points {
for k in 0..2 {
lo[k] = lo[k].min(q[k]);
hi[k] = hi[k].max(q[k]);
}
}
(hi[0] - lo[0]).max(hi[1] - lo[1]).max(1e-12)
};
let near = extent * 1e-9;
let along_ring = |ia: usize, ic: usize| -> bool {
if (ia + 1) % n == ic || (ic + 1) % n == ia {
return false; }
let mid = [
0.5 * (points[ia][0] + points[ic][0]),
0.5 * (points[ia][1] + points[ic][1]),
];
(0..n).any(|k| {
let (x, y) = (points[k], points[(k + 1) % n]);
let (dx, dy) = (y[0] - x[0], y[1] - x[1]);
let len2 = dx * dx + dy * dy;
let t = if len2 <= f64::MIN_POSITIVE {
0.0
} else {
(((mid[0] - x[0]) * dx + (mid[1] - x[1]) * dy) / len2).clamp(0.0, 1.0)
};
(mid[0] - (x[0] + dx * t)).hypot(mid[1] - (x[1] + dy * t)) <= near
})
};
let mut out = Vec::with_capacity(n.saturating_sub(2));
let mut guard = 0usize;
while idx.len() > 3 {
let m = idx.len();
let mut clipped = false;
for i in 0..m {
let (ia, ib, ic) = (idx[(i + m - 1) % m], idx[i], idx[(i + 1) % m]);
let (a, b, c) = (points[ia], points[ib], points[ic]);
let cross = area2(a, b, c);
if cross < 0.0 {
continue; }
if cross > 0.0 {
if along_ring(ia, ic) {
continue;
}
let blocked = idx
.iter()
.any(|&j| j != ia && j != ib && j != ic && inside(a, b, c, points[j]));
if blocked {
continue;
}
}
out.push([ia, ib, ic]);
idx.remove(i);
clipped = true;
break;
}
guard += 1;
if !clipped || guard > n * n + 8 {
break;
}
}
if idx.len() == 3 {
out.push([idx[0], idx[1], idx[2]]);
}
out
}