use super::arrangement::{
boolean, difference_all, difference_all_lenient, union_all, BoolOp, Tri,
};
use super::signed_volume::signed_volume6;
use crate::mesh::Mesh;
pub(crate) const SNAP_GRID: f64 = 1.0 / 65536.0;
#[inline]
fn snap(c: f64) -> f64 {
(c / SNAP_GRID).round() * SNAP_GRID
}
use super::near_band::NearBand;
pub fn mesh_to_tris(m: &Mesh) -> Vec<Tri> {
let vertex = |i: u32| -> Option<[f64; 3]> {
let b = (i as usize) * 3;
let c = [
*m.positions.get(b)? as f64,
*m.positions.get(b + 1)? as f64,
*m.positions.get(b + 2)? as f64,
];
if !c.iter().all(|v| v.is_finite()) {
return None;
}
Some([snap(c[0]), snap(c[1]), snap(c[2])])
};
m.indices
.chunks_exact(3)
.filter_map(|c| Some([vertex(c[0])?, vertex(c[1])?, vertex(c[2])?]))
.collect()
}
fn face_normal(t: &Tri) -> [f32; 3] {
let e1 = [t[1][0] - t[0][0], t[1][1] - t[0][1], t[1][2] - t[0][2]];
let e2 = [t[2][0] - t[0][0], t[2][1] - t[0][1], t[2][2] - t[0][2]];
let n = [
e1[1] * e2[2] - e1[2] * e2[1],
e1[2] * e2[0] - e1[0] * e2[2],
e1[0] * e2[1] - e1[1] * e2[0],
];
let len = (n[0] * n[0] + n[1] * n[1] + n[2] * n[2]).sqrt();
if len > 0.0 {
[(n[0] / len) as f32, (n[1] / len) as f32, (n[2] / len) as f32]
} else {
[0.0, 0.0, 1.0]
}
}
pub fn tris_to_mesh(tris: &[Tri]) -> Mesh {
let mut m = Mesh::with_capacity(tris.len() * 3, tris.len() * 3);
for t in tris {
let n = face_normal(t);
let base = (m.positions.len() / 3) as u32;
for p in t {
m.positions
.extend_from_slice(&[p[0] as f32, p[1] as f32, p[2] as f32]);
m.normals.extend_from_slice(&n);
}
m.indices.extend_from_slice(&[base, base + 1, base + 2]);
}
m
}
pub(crate) fn orient_outward(mut tris: Vec<Tri>) -> Vec<Tri> {
if signed_volume6(&tris) < 0.0 {
for t in &mut tris {
t.swap(1, 2);
}
}
tris
}
fn promote_cutter_verts_onto_host_faces(cutter: &mut [Tri], host: &[Tri]) {
if cutter.is_empty() || host.is_empty() {
return;
}
let mut band = NearBand::default();
band.observe_tris(cutter);
band.observe_tris(host);
struct Face {
t0: [f64; 3],
t1: [f64; 3],
t2: [f64; 3],
n: [f64; 3], nn: f64, band2: f64,
}
let faces: Vec<Face> = host
.iter()
.filter_map(|t| {
let e1 = [t[1][0] - t[0][0], t[1][1] - t[0][1], t[1][2] - t[0][2]];
let e2 = [t[2][0] - t[0][0], t[2][1] - t[0][1], t[2][2] - t[0][2]];
let n = [
e1[1] * e2[2] - e1[2] * e2[1],
e1[2] * e2[0] - e1[0] * e2[2],
e1[0] * e2[1] - e1[1] * e2[0],
];
let nn = n[0] * n[0] + n[1] * n[1] + n[2] * n[2];
if nn <= 0.0 || !nn.is_finite() {
return None; }
let band2 = band.scaled_band2(n, nn) / nn;
Some(Face { t0: t[0], t1: t[1], t2: t[2], n, nn, band2 })
})
.collect();
for t in cutter.iter_mut() {
for v in t.iter_mut() {
let mut best: Option<(f64, &Face)> = None; for f in &faces {
let d = (v[0] - f.t0[0]) * f.n[0]
+ (v[1] - f.t0[1]) * f.n[1]
+ (v[2] - f.t0[2]) * f.n[2];
if d == 0.0 {
continue; }
let d2 = (d * d) / f.nn;
if d2 > f.band2 {
continue; }
if let Some((bd2, _)) = best {
if d2 >= bd2 {
continue;
}
}
best = Some((d2, f));
}
if let Some((_, f)) = best {
if let Some(w) = exact_on_plane_weld(*v, f.t0, f.t1, f.t2) {
*v = w;
}
}
}
}
}
fn exact_on_plane_weld(v: [f64; 3], t0: [f64; 3], t1: [f64; 3], t2: [f64; 3]) -> Option<[f64; 3]> {
const Q: f64 = 1_048_576.0; const S16: f64 = 65_536.0; const S36: f64 = 68_719_476_736.0; let u = [t1[0] - t0[0], t1[1] - t0[1], t1[2] - t0[2]];
let w = [t2[0] - t0[0], t2[1] - t0[1], t2[2] - t0[2]];
let p = [v[0] - t0[0], v[1] - t0[1], v[2] - t0[2]];
let dot = |a: &[f64; 3], b: &[f64; 3]| a[0] * b[0] + a[1] * b[1] + a[2] * b[2];
let (uu, ww, uw) = (dot(&u, &u), dot(&w, &w), dot(&u, &w));
let (pu, pw) = (dot(&p, &u), dot(&p, &w));
let det = uu * ww - uw * uw;
if det == 0.0 || !det.is_finite() {
return None; }
let alpha = ((ww * pu - uw * pw) / det * Q).round();
let beta = ((uu * pw - uw * pu) / det * Q).round();
if !alpha.is_finite() || !beta.is_finite() || alpha.abs() > 8.0 * Q || beta.abs() > 8.0 * Q {
return None;
}
let (ai, bi) = (alpha as i128, beta as i128);
let mut out = [0.0f64; 3];
for k in 0..3 {
let (s0, s1, s2) = (t0[k] * S16, t1[k] * S16, t2[k] * S16);
for s in [s0, s1, s2] {
if s.fract() != 0.0 || s.abs() >= 9.0e18 {
return None;
}
}
let (i0, i1, i2) = (s0 as i128, s1 as i128, s2 as i128);
let r36 = (i0 << 20) + ai * (i1 - i0) + bi * (i2 - i0);
let rf = r36 as f64;
if rf as i128 != r36 {
return None; }
out[k] = rf / S36; }
Some(out)
}
pub fn subtract(host: &Mesh, cutter: &Mesh) -> Mesh {
#[cfg(feature = "csg_capture")]
crate::csg_capture::record_single(host, cutter);
let h = orient_outward(mesh_to_tris(host));
let mut c = mesh_to_tris(cutter);
promote_cutter_verts_onto_host_faces(&mut c, &h);
let c = orient_outward(c);
tris_to_mesh(&boolean(&h, &c, BoolOp::Difference))
}
pub fn subtract_many(host: &Mesh, cutters: &[&Mesh]) -> Option<Mesh> {
#[cfg(feature = "csg_capture")]
crate::csg_capture::record_many(host, cutters);
let h = orient_outward(mesh_to_tris(host));
let comp_tris: Vec<Vec<Tri>> = cutters
.iter()
.map(|m| {
let mut c = mesh_to_tris(m);
promote_cutter_verts_onto_host_faces(&mut c, &h);
orient_outward(c)
})
.collect();
let refs: Vec<&[Tri]> = comp_tris.iter().map(|c| c.as_slice()).collect();
if let Some(r) = difference_all(&h, &refs) {
return Some(tris_to_mesh(&r));
}
let batch = difference_all_lenient(&h, &refs);
let budget_snap = super::budget::snapshot_counters();
let mut inter_sum = 0.0f64;
let mut oracle_tripped = false;
for c in &comp_tris {
super::budget::begin();
let i = boolean(&h, c, BoolOp::Intersection);
if super::budget::tripped() {
oracle_tripped = true;
break;
}
inter_sum += signed_volume6(&i).abs();
}
super::budget::restore_counters(budget_snap);
if oracle_tripped {
return None;
}
let host_v = signed_volume6(&h).abs();
let batch_removed = host_v - signed_volume6(&batch).abs();
let tol = inter_sum.abs().max(1.0e-9) * 0.01;
if (batch_removed - inter_sum).abs() <= tol {
Some(tris_to_mesh(&batch))
} else {
None
}
}
pub fn union(a: &Mesh, b: &Mesh) -> Mesh {
super::budget::begin();
let a = orient_outward(mesh_to_tris(a));
let b = orient_outward(mesh_to_tris(b));
let out = boolean(&a, &b, BoolOp::Union);
if super::budget::tripped() {
return Mesh::new();
}
tris_to_mesh(&out)
}
pub fn union_many(meshes: &[&Mesh]) -> Mesh {
super::budget::begin();
let tri_lists: Vec<Vec<Tri>> =
meshes.iter().map(|m| orient_outward(mesh_to_tris(m))).collect();
let refs: Vec<&[Tri]> = tri_lists.iter().map(|t| t.as_slice()).collect();
let (out, conforming) = union_all(&refs);
if super::budget::tripped() {
return Mesh::new();
}
let _ = conforming;
tris_to_mesh(&out)
}
pub fn intersection_tris(a: &Mesh, b: &Mesh) -> Vec<Tri> {
super::budget::begin();
let a = orient_outward(mesh_to_tris(a));
let b = orient_outward(mesh_to_tris(b));
let out = boolean(&a, &b, BoolOp::Intersection);
if super::budget::tripped() {
return Vec::new();
}
out
}
pub fn intersection(a: &Mesh, b: &Mesh) -> Mesh {
tris_to_mesh(&intersection_tris(a, b))
}
#[cfg(test)]
#[path = "mesh_bridge_tests.rs"]
mod tests;