use super::expansion::{
det3_exact, det3_with_precancel_bound, diff_expansion, rescale_for_sign_only,
sign_only_expansion_sign,
};
use super::sign::Sign;
use crate::primitives::Point3;
const ORIENT3D_ERR_BOUND_FACTOR: f64 = 12.0 * f64::EPSILON / 2.0;
pub fn orient3d(a: Point3, b: Point3, c: Point3, d: Point3) -> Sign {
let adx = a.x() - d.x();
let ady = a.y() - d.y();
let adz = a.z() - d.z();
let bdx = b.x() - d.x();
let bdy = b.y() - d.y();
let bdz = b.z() - d.z();
let cdx = c.x() - d.x();
let cdy = c.y() - d.y();
let cdz = c.z() - d.z();
let (det, precancel_bound) =
det3_with_precancel_bound((adx, ady, adz), (bdx, bdy, bdz), (cdx, cdy, cdz));
let bound = ORIENT3D_ERR_BOUND_FACTOR * precancel_bound;
if bound > 0.0 && det.abs() > bound {
return Sign::of(det);
}
orient3d_exact(a, b, c, d)
}
fn orient3d_exact(a: Point3, b: Point3, c: Point3, d: Point3) -> Sign {
let [ax, ay, az, bx, by, bz, cx, cy, cz, dx, dy, dz] = rescale_for_sign_only([
a.x(),
a.y(),
a.z(),
b.x(),
b.y(),
b.z(),
c.x(),
c.y(),
c.z(),
d.x(),
d.y(),
d.z(),
]);
let adx = diff_expansion(ax, dx);
let ady = diff_expansion(ay, dy);
let adz = diff_expansion(az, dz);
let bdx = diff_expansion(bx, dx);
let bdy = diff_expansion(by, dy);
let bdz = diff_expansion(bz, dz);
let cdx = diff_expansion(cx, dx);
let cdy = diff_expansion(cy, dy);
let cdz = diff_expansion(cz, dz);
let det = det3_exact((&adx, &ady, &adz), (&bdx, &bdy, &bdz), (&cdx, &cdy, &cdz));
sign_only_expansion_sign(&det)
}
#[cfg(test)]
mod tests {
use super::*;
fn pt(x: f64, y: f64, z: f64) -> Point3 {
Point3::new(x, y, z).unwrap()
}
#[test]
fn positive_tetrahedron() {
assert_eq!(
orient3d(
pt(0.0, 0.0, 0.0),
pt(0.0, 1.0, 0.0),
pt(1.0, 0.0, 0.0),
pt(0.0, 0.0, 1.0)
),
Sign::Positive
);
}
#[test]
fn negative_tetrahedron() {
assert_eq!(
orient3d(
pt(0.0, 0.0, 0.0),
pt(1.0, 0.0, 0.0),
pt(0.0, 1.0, 0.0),
pt(0.0, 0.0, 1.0)
),
Sign::Negative
);
}
#[test]
fn coplanar_points() {
assert_eq!(
orient3d(
pt(0.0, 0.0, 0.0),
pt(1.0, 0.0, 0.0),
pt(0.0, 1.0, 0.0),
pt(1.0, 1.0, 0.0)
),
Sign::Zero
);
}
#[test]
fn duplicate_point_is_coplanar() {
let p = pt(1.0, 2.0, 3.0);
assert_eq!(
orient3d(p, p, pt(4.0, 5.0, 6.0), pt(7.0, 8.0, 9.0)),
Sign::Zero
);
}
#[test]
fn exact_fallback_does_not_panic_on_near_coplanar() {
let a = pt(0.0, 0.0, 0.0);
let b = pt(1e15, 1.0, 0.0);
let c = pt(0.0, 1e15, 1.0);
let d = pt(1e15, 1e15, 2.0 + 1e-9);
let _ = orient3d(a, b, c, d);
}
}