use super::{aabb, aabb_overlap, cross, dot, sub, triangles, V3};
use crate::core::BufferGeometry;
fn lerp(p: V3, q: V3, t: f64) -> V3 {
[
p[0] + (q[0] - p[0]) * t,
p[1] + (q[1] - p[1]) * t,
p[2] + (q[2] - p[2]) * t,
]
}
fn plane(tri: &[V3; 3]) -> (V3, f64) {
let n = cross(sub(tri[1], tri[0]), sub(tri[2], tri[0]));
(n, dot(n, tri[0]))
}
fn tri_plane_chord(tri: &[V3; 3], n: V3, d: f64) -> Option<(V3, V3)> {
let dist = [dot(n, tri[0]) - d, dot(n, tri[1]) - d, dot(n, tri[2]) - d];
let mut pts: Vec<V3> = Vec::new();
for (i, j) in [(0, 1), (1, 2), (2, 0)] {
let (di, dj) = (dist[i], dist[j]);
if (di > 0.0 && dj < 0.0) || (di < 0.0 && dj > 0.0) {
let t = di / (di - dj);
pts.push(lerp(tri[i], tri[j], t));
}
}
if pts.len() == 2 {
Some((pts[0], pts[1]))
} else {
None
}
}
pub fn tri_tri_segment(a: &[V3; 3], b: &[V3; 3]) -> Option<(V3, V3)> {
let (na, da) = plane(a);
let (nb, db) = plane(b);
let dir = cross(na, nb);
if dot(dir, dir) < 1e-20 {
return None; }
let ca = tri_plane_chord(a, nb, db)?;
let cb = tri_plane_chord(b, na, da)?;
let s = |p: V3| dot(p, dir);
let order = |c: (V3, V3)| {
let (p, q) = ((s(c.0), c.0), (s(c.1), c.1));
if p.0 <= q.0 {
(p, q)
} else {
(q, p)
}
};
let (a_lo, a_hi) = order(ca);
let (b_lo, b_hi) = order(cb);
let lo = if a_lo.0 >= b_lo.0 { a_lo } else { b_lo };
let hi = if a_hi.0 <= b_hi.0 { a_hi } else { b_hi };
if lo.0 > hi.0 + 1e-12 {
return None; }
Some((lo.1, hi.1))
}
pub fn intersection_segments(a: &BufferGeometry, b: &BufferGeometry) -> Vec<(V3, V3)> {
let ta = triangles(a);
let tb = triangles(b);
let boxes_b: Vec<(V3, V3)> = tb.iter().map(aabb).collect();
let mut segs = Vec::new();
for ai in &ta {
let ba = aabb(ai);
for (bj, bb) in tb.iter().zip(&boxes_b) {
if !aabb_overlap(&ba, bb) {
continue;
}
if let Some(seg) = tri_tri_segment(ai, bj)
&& dot(sub(seg.1, seg.0), sub(seg.1, seg.0)) > 1e-18
{
segs.push(seg);
}
}
}
segs
}
#[cfg(test)]
mod tests {
use super::*;
use crate::cube;
fn approx(p: V3, q: V3) -> bool {
dot(sub(p, q), sub(p, q)) < 1e-9
}
fn is_endpoint(seg: &(V3, V3), p: V3) -> bool {
approx(seg.0, p) || approx(seg.1, p)
}
#[test]
fn segment_of_two_crossing_triangles() {
let a = [[0.0, 0.0, 0.0], [2.0, 0.0, 0.0], [0.0, 2.0, 0.0]];
let b = [[0.5, 0.5, -1.0], [0.5, 0.5, 1.0], [1.5, 0.5, 1.0]];
let seg = tri_tri_segment(&a, &b).expect("triangles cross");
assert!(is_endpoint(&seg, [0.5, 0.5, 0.0]));
assert!(is_endpoint(&seg, [1.0, 0.5, 0.0]));
}
#[test]
fn no_segment_when_apart() {
let a = [[0.0, 0.0, 0.0], [2.0, 0.0, 0.0], [0.0, 2.0, 0.0]];
let apart = [[0.5, 0.5, 1.0], [0.5, 0.5, 2.0], [1.5, 0.5, 2.0]];
assert!(tri_tri_segment(&a, &apart).is_none());
}
#[test]
fn overlapping_solids_produce_a_cut_loop() {
let a = cube([2.0, 2.0, 2.0]).to_geometry();
let b = crate::sphere(1.3).to_geometry();
let segs = intersection_segments(&a, &b);
assert!(
!segs.is_empty(),
"sphere through box must yield cut segments"
);
for s in &segs {
assert!(
dot(sub(s.1, s.0), sub(s.1, s.0)) > 1e-18,
"no coincident-point segs"
);
}
}
}