use std::collections::BTreeMap;
use crate::{
Result,
math::{Aabb, Point3, Vec3},
measure,
mesh::{
MeshOptions,
bvh::{Bvh, ray_triangle},
tessellate,
},
numeric,
topo::{Brep, FaceId},
};
#[derive(Clone, Debug, PartialEq)]
pub struct Narrow {
pub face: FaceId,
pub width: f64,
pub area: f64,
pub perimeter: f64,
pub at: Point3,
}
#[derive(Clone, Debug, PartialEq)]
pub struct Thin {
pub faces: (FaceId, FaceId),
pub material: bool,
pub min: f64,
pub area: f64,
pub at: Point3,
}
const FACING: f64 = -0.98;
fn face_perimeter(b: &Brep, f: FaceId) -> (f64, Option<Point3>) {
let mut total = 0.0;
let mut at = None;
let face = b.face(f);
let mut uses: BTreeMap<usize, usize> = BTreeMap::new();
for &l in &face.loops {
for &c in &b.lp(l).coedges {
*uses.entry(b.coedge(c).edge.index()).or_default() += 1;
}
}
for &l in &face.loops {
for &c in &b.lp(l).coedges {
let e = b.edge(b.coedge(c).edge);
if uses[&b.coedge(c).edge.index()] > 1 {
continue;
}
let Some(curve) = &e.curve else { continue };
let (t0, t1) = e.range;
let len = numeric::integrate(&mut |t| curve.d1(t).1.norm(), t0, t1, 1e-9);
total += len;
at.get_or_insert_with(|| curve.eval(0.5 * (t0 + t1)));
}
}
(total, at)
}
pub fn narrow_faces(b: &Brep, below: f64) -> Vec<Narrow> {
let mut out = Vec::new();
for f in b.face_ids() {
let (perimeter, at) = face_perimeter(b, f);
let Some(at) = at else { continue };
if perimeter <= 0.0 {
continue;
}
let area = measure::face_area(b, f);
let width = 2.0 * area / perimeter;
if width < below {
out.push(Narrow {
face: f,
width,
area,
perimeter,
at,
});
}
}
out
}
const MESHES: [MeshOptions; 3] = [
MeshOptions {
linear: 0.002,
angular: 0.1,
},
MeshOptions {
linear: 0.01,
angular: 0.2,
},
MeshOptions {
linear: 0.05,
angular: 0.5,
},
];
fn on_face(b: &Brep, f: FaceId, p: Point3) -> (Point3, Vec3) {
let face = b.face(f);
let uv = face.surface.project(p);
let n = face.surface.normal(uv.x, uv.y);
let n = if face.reversed { -n } else { n };
(face.surface.eval(uv.x, uv.y), n)
}
pub fn thin_places(b: &Brep, below: f64) -> Result<Vec<Thin>> {
let mut last = None;
let mut mesh = None;
for opt in MESHES {
match tessellate(b, &opt) {
Ok(m) => {
mesh = Some((m, opt.linear));
break;
}
Err(e) => last = Some(e),
}
}
let Some((mesh, chord)) = mesh else {
return Err(last.expect("a mesh was tried"));
};
let mut face_of = Vec::with_capacity(mesh.triangles.len());
for (f, r) in &mesh.faces {
face_of.resize(r.end.max(face_of.len()), *f);
}
let bvh = Bvh::new(&mesh);
let reach = below + 2.0 * chord;
let mut found: BTreeMap<(FaceId, FaceId, bool), Thin> = BTreeMap::new();
let mut near = Vec::new();
for (f, range) in &mesh.faces {
for ti in range.clone() {
let [i, j, k] = mesh.triangles[ti].map(|i| mesh.positions[i as usize]);
let area = 0.5 * (j - i).cross(k - i).norm();
if area <= 0.0 {
continue;
}
let (p, n) = on_face(b, *f, (i + j + k) * (1.0 / 3.0));
let mut q = Aabb::EMPTY;
q.add(p + n * reach);
q.add(p - n * reach);
bvh.query(&q, &mut near);
let mut best: [Option<(f64, usize)>; 2] = [None, None];
for &u in &near {
if u == ti {
continue;
}
let [a, bb, c] = mesh.triangles[u].map(|i| mesh.positions[i as usize]);
let Some(t) = ray_triangle(p, n, a, bb, c) else {
continue;
};
let tn = (bb - a).cross(c - a);
let other = face_of[u];
let (_, on) = on_face(b, other, p + n * t);
if on.dot(n) > FACING || tn.norm() == 0.0 {
continue;
}
let side = usize::from(t < 0.0);
if t.abs() <= reach && best[side].is_none_or(|(s, _)| t.abs() < s) {
best[side] = Some((t.abs(), u));
}
}
for (side, hit) in best.into_iter().enumerate() {
let Some((t, u)) = hit else { continue };
let other = face_of[u];
let dir = if side == 0 { n } else { -n };
let (q, _) = on_face(b, other, p + dir * t);
let gap = (q - p).norm();
if gap >= below || gap <= crate::tol::LINEAR {
continue;
}
let e = found.entry((*f, other, side == 1)).or_insert(Thin {
faces: (*f, other),
material: side == 1,
min: gap,
area: 0.0,
at: p,
});
e.area += area;
if gap < e.min {
e.min = gap;
e.at = p;
}
}
}
}
let mut out: Vec<Thin> = Vec::new();
for t in found.into_values() {
let (a, c) = t.faces;
match out
.iter_mut()
.find(|o| o.faces == (c, a) && o.material == t.material)
{
Some(o) => {
if t.area > o.area {
let min = o.min.min(t.min);
*o = t;
o.min = min;
} else {
o.min = o.min.min(t.min);
}
}
None => out.push(t),
}
}
Ok(out)
}
#[cfg(test)]
mod tests {
use super::*;
use crate::{
boolean::{self, Op},
math::{Frame, Transform, Vec2},
profile::Profile,
sweep,
};
fn block(x0: f64, x1: f64, y0: f64, y1: f64, z0: f64, h: f64) -> Brep {
let p = Profile::polygon(
&[
Vec2::new(x0, y0),
Vec2::new(x1, y0),
Vec2::new(x1, y1),
Vec2::new(x0, y1),
],
&["a", "b", "c", "d"],
);
let mut b = sweep::extrude(&p, &Frame::WORLD, h, "f-block").unwrap();
b.transform(&Transform::translation(Vec3::new(0.0, 0.0, z0)));
b
}
#[test]
fn a_hairline_slot_is_a_gap_and_its_floor_a_narrow_face() {
let body = block(0.0, 10.0, 0.0, 10.0, 0.0, 5.0);
let slot = block(3.0, 3.001, -1.0, 11.0, 3.0, 3.0);
let cut = boolean::boolean(&body, &slot, Op::Difference).unwrap();
let narrow = narrow_faces(&cut, 0.05);
assert_eq!(narrow.len(), 1, "{narrow:?}");
assert!(
(narrow[0].width - 2.0 * 0.01 / 20.002).abs() < 1e-12,
"{narrow:?}"
);
let thin = thin_places(&cut, 0.01).unwrap();
assert_eq!(thin.len(), 1, "{thin:?}");
assert!(!thin[0].material);
assert!((thin[0].min - 0.001).abs() < 1e-9, "{thin:?}");
assert!((thin[0].area - 20.0).abs() < 1e-6, "{thin:?}");
}
#[test]
fn a_wall_two_microns_thick_is_a_sliver() {
let body = block(0.0, 10.0, 0.0, 10.0, 0.0, 5.0);
let left = block(1.0, 4.999, 1.0, 9.0, 3.0, 3.0);
let right = block(5.001, 9.0, 1.0, 9.0, 3.0, 3.0);
let cut = boolean::boolean(&body, &left, Op::Difference).unwrap();
let cut = boolean::boolean(&cut, &right, Op::Difference).unwrap();
let thin = thin_places(&cut, 0.01).unwrap();
assert_eq!(thin.len(), 1, "{thin:?}");
assert!(thin[0].material);
assert!((thin[0].min - 0.002).abs() < 1e-9, "{thin:?}");
assert!((thin[0].area - 16.0).abs() < 1e-6, "{thin:?}");
assert!(narrow_faces(&cut, 0.05).is_empty());
}
#[test]
fn a_block_has_no_thin_places() {
let b = block(0.0, 10.0, 0.0, 10.0, 0.0, 5.0);
assert!(narrow_faces(&b, 0.05).is_empty());
assert!(thin_places(&b, 0.01).unwrap().is_empty());
}
}