use super::boundary::Outline;
use super::*;
use crate::common::barycentric::{barycentric, barycentric_grid, barycentric_point};
use crate::geom3::half_edge3::decimate::replacement;
use crate::{Point3, Vector3};
use alum::FH;
#[derive(Debug, Clone, Copy)]
struct Patch {
p: [Point3; 3],
e: [f64; 3],
}
impl Patch {
fn radius(&self, w: [f64; 3]) -> f64 {
self.e[0] * w[0] + self.e[1] * w[1] + self.e[2] * w[2]
}
fn radius_at(&self, z: &Point3) -> f64 {
self.radius(barycentric(&self.p[0], &self.p[1], &self.p[2], z))
}
fn negated(&self) -> Self {
Self {
p: self.p,
e: [-self.e[0], -self.e[1], -self.e[2]],
}
}
}
fn best_cover_on(patch: &Patch, q: &Point3) -> f64 {
let (a, b, c) = (patch.p[0], patch.p[1], patch.p[2]);
let Some(n) = (b - a).cross(&(c - a)).try_normalize(1.0e-14) else {
return f64::NEG_INFINITY; };
let f = |z: &Point3| patch.radius_at(z) - (q - z).norm();
let mut best = f64::NEG_INFINITY;
for (u, v) in [(a, b), (b, c), (c, a)] {
best = best.max(ternary_max(&u, &v, &f));
}
let d = n.dot(&(q - a));
let qp = q - n * d;
if let Some(g) = radius_gradient(patch, &n) {
let gm = g.norm();
if gm < 1.0 {
let step = gm * d.abs() / (1.0 - gm * gm).sqrt();
let z = if gm > 0.0 { qp + g * (step / gm) } else { qp };
let w = barycentric(&a, &b, &c, &z);
if w.iter().all(|x| *x >= 0.0) {
best = best.max(f(&z));
}
}
}
best
}
fn radius_gradient(patch: &Patch, n: &Vector3) -> Option<Vector3> {
let u = patch.p[1] - patch.p[0];
let v = patch.p[2] - patch.p[0];
let m = crate::na::Matrix3::from_rows(&[u.transpose(), v.transpose(), n.transpose()]);
let rhs = Vector3::new(patch.e[1] - patch.e[0], patch.e[2] - patch.e[0], 0.0);
m.lu().solve(&rhs)
}
fn ternary_max(u: &Point3, v: &Point3, f: &impl Fn(&Point3) -> f64) -> f64 {
let at = |t: f64| Point3::from(u.coords * (1.0 - t) + v.coords * t);
let (mut lo, mut hi) = (0.0f64, 1.0f64);
for _ in 0..60 {
let m1 = lo + (hi - lo) / 3.0;
let m2 = hi - (hi - lo) / 3.0;
if f(&at(m1)) < f(&at(m2)) {
lo = m1;
} else {
hi = m2;
}
}
f(&at(0.5 * (lo + hi))).max(f(u)).max(f(v))
}
fn invariant_gaps(old: &[Patch], new: &[Patch], spacing: f64) -> (f64, f64) {
let mut cover = 0.0f64;
let mut reach = 0.0f64;
for patch in old.iter() {
for w in barycentric_grid(&patch.p[0], &patch.p[1], &patch.p[2], spacing) {
let x = barycentric_point(&patch.p[0], &patch.p[1], &patch.p[2], w);
let have = new
.iter()
.map(|n| best_cover_on(n, &x))
.fold(f64::NEG_INFINITY, f64::max);
cover = cover.max(patch.radius(w) - have);
}
}
for patch in new.iter() {
for w in barycentric_grid(&patch.p[0], &patch.p[1], &patch.p[2], spacing) {
let y = barycentric_point(&patch.p[0], &patch.p[1], &patch.p[2], w);
let need = old
.iter()
.map(|o| -best_cover_on(&o.negated(), &y))
.fold(f64::INFINITY, f64::min);
reach = reach.max(need - patch.radius(w));
}
}
(cover, reach)
}
#[derive(Debug, Clone, Copy, Default)]
struct Strip {
warp: f64,
notch: f64,
}
impl Strip {
fn flat() -> Self {
Self::default()
}
fn warped() -> Self {
Self {
warp: 0.25,
notch: 0.0,
}
}
fn bent() -> Self {
Self {
warp: 0.0,
notch: 0.4,
}
}
}
fn strip(shape: Strip) -> (Vec<Point3>, Vec<[u32; 3]>) {
let mut points = Vec::new();
for j in 0..3 {
for i in 0..4 {
let x = i as f64;
let y = j as f64
+ if j == 0 && (i == 1 || i == 2) {
shape.notch
} else {
0.0
};
points.push(Point3::new(x, y, shape.warp * (x - 1.5) * (y - 1.0)));
}
}
let mut faces = Vec::new();
for j in 0..2u32 {
for i in 0..3u32 {
let (a, b) = (j * 4 + i, (j + 1) * 4 + i);
faces.push([a, a + 1, b + 1]);
faces.push([a, b + 1, b]);
}
}
(points, faces)
}
struct Fixture {
star: Vec<StarFace>,
new: Vec<[Point3; 3]>,
points: Vec<Vector3>,
e: Vec<f64>,
v1: VH,
v2: VH,
p0: Vector3,
}
impl Fixture {
fn new(shape: Strip, v1: u32, v2: u32, p0: Point3, radius: f64) -> Self {
let (points, faces) = strip(shape);
let (hv1, hv2) = (VH::from(v1), VH::from(v2));
let star: Vec<StarFace> = faces
.iter()
.filter(|f| f.contains(&v1) || f.contains(&v2))
.enumerate()
.map(|(i, f)| StarFace {
f: FH::from(i as u32),
v: [VH::from(f[0]), VH::from(f[1]), VH::from(f[2])],
p: [
points[f[0] as usize],
points[f[1] as usize],
points[f[2] as usize],
],
normal: None,
vanishing: f.contains(&v1) && f.contains(&v2),
})
.collect();
let coords: Vec<Vector3> = points.iter().map(|q| q.coords).collect();
let new = star
.iter()
.map(|f| replacement(f, hv1, hv2, p0.coords, &coords))
.collect();
Self {
star,
new,
e: vec![radius; points.len()],
points: coords,
v1: hv1,
v2: hv2,
p0: p0.coords,
}
}
fn outline(&self) -> Outline {
boundary_chain(&self.star, self.v1, self.v2)
}
fn old_patches(&self) -> Vec<Patch> {
self.star
.iter()
.map(|f| Patch {
p: f.p,
e: [0, 1, 2].map(|k| self.e[f.v[k].index() as usize]),
})
.collect()
}
fn new_patches(&self, radius: f64) -> Vec<Patch> {
self.star
.iter()
.zip(self.new.iter())
.filter(|(f, _)| !f.vanishing)
.map(|(f, q)| Patch {
p: *q,
e: [0, 1, 2].map(|k| {
let h = f.v[k];
if h == self.v1 || h == self.v2 {
radius
} else {
self.e[h.index() as usize]
}
}),
})
.collect()
}
fn collapse(&self) -> Collapse<'_> {
self.at(self.outline())
}
fn at(&self, outline: Outline) -> Collapse<'_> {
Collapse {
star: &self.star,
new: &self.new,
points: &self.points,
e: &self.e,
v1: self.v1,
v2: self.v2,
p0: self.p0,
outline,
}
}
fn gaps(&self, radius: f64) -> (f64, f64) {
invariant_gaps(&self.old_patches(), &self.new_patches(radius), 0.15)
}
}
const SLACK: f64 = 1.0e-9;
fn outline_of(v1: u32, v2: u32) -> Outline {
Fixture::new(Strip::flat(), v1, v2, Point3::origin(), 0.0).outline()
}
#[test]
fn an_interior_edge_has_a_closed_outline() {
assert!(matches!(outline_of(5, 6), Outline::Closed));
}
#[test]
fn a_type_two_edge_gives_a_three_vertex_chain() {
let Outline::Open(chain) = outline_of(1, 5) else {
panic!("expected an open outline for a Type II edge");
};
let got: Vec<u32> = chain.iter().map(|(v, _)| v.index()).collect();
assert_eq!(got, vec![0, 1, 2], "the run should be 0 - 1 - 2");
}
#[test]
fn a_type_one_edge_gives_a_four_vertex_chain() {
let Outline::Open(chain) = outline_of(1, 2) else {
panic!("expected an open outline for a Type I edge");
};
let got: Vec<u32> = chain.iter().map(|(v, _)| v.index()).collect();
assert_eq!(got, vec![0, 1, 2, 3], "the run should be 0 - 1 - 2 - 3");
}
#[test]
fn a_type_three_edge_is_refused() {
assert!(matches!(outline_of(4, 9), Outline::Unsupported));
}
#[test]
fn a_chain_only_moves_when_a_vertex_it_carries_does() {
let Outline::Open(chain) = outline_of(1, 5) else {
panic!("expected an open outline");
};
assert!(!chain.moves_under(Vector3::new(1.0, 0.0, 0.0)));
assert!(chain.moves_under(Vector3::new(1.0, 0.1, 0.0)));
assert!(chain.moves_under(Vector3::new(1.5, 0.0, 0.0)));
}
#[test]
fn the_invariant_check_agrees_with_contraction() {
for shape in [Strip::flat(), Strip::warped()] {
for (v1, v2) in [(5, 6), (1, 5), (1, 2)] {
let c = Fixture::new(shape, v1, v2, Point3::new(1.4, 0.45, 0.1), 0.03);
let ErrorBound::Bound(r) = Contraction.bound(&c.collapse()) else {
panic!("contraction always produces a bound");
};
let (cover, reach) = c.gaps(r);
assert!(
cover <= SLACK && reach <= SLACK,
"contraction flagged on shape={shape:?} edge ({v1},{v2}): cover {cover:e}, \
reach {reach:e}"
);
}
}
}
#[test]
fn the_invariant_check_agrees_with_the_face_map() {
for shape in [Strip::flat(), Strip::warped()] {
for (v1, v2) in [(5, 6), (1, 5), (1, 2)] {
let c = Fixture::new(shape, v1, v2, Point3::new(1.4, 0.45, 0.1), 0.03);
let ErrorBound::Bound(r) = AffineFaceMap.bound(&c.collapse()) else {
panic!("the face map refused shape={shape:?} edge ({v1},{v2})");
};
let (cover, reach) = c.gaps(r);
assert!(
cover <= SLACK && reach <= SLACK,
"the face map flagged on shape={shape:?} edge ({v1},{v2}): cover {cover:e}, \
reach {reach:e}"
);
}
}
}
#[test]
fn the_invariant_check_agrees_with_the_overlay_on_a_closed_outline() {
for shape in [Strip::flat(), Strip::warped()] {
let c = Fixture::new(shape, 5, 6, Point3::new(1.4, 1.15, 0.1), 0.03);
assert!(matches!(c.outline(), Outline::Closed));
let ErrorBound::Bound(r) = ProjectedOverlay.bound(&c.at(Outline::Closed)) else {
panic!("the overlay had nothing to say about an interior collapse at shape={shape:?}");
};
let (cover, reach) = c.gaps(r);
assert!(
cover <= SLACK && reach <= SLACK,
"the overlay flagged on an interior collapse at shape={shape:?}: cover {cover:e}, \
reach {reach:e}"
);
}
}
#[test]
fn the_invariant_check_catches_the_overlay_on_a_moving_outline() {
let c = Fixture::new(Strip::bent(), 1, 2, Point3::new(1.5, 0.5, 0.0), 0.03);
assert!(
matches!(c.outline(), Outline::Open(_)),
"edge (1,2) should be a Type I boundary edge"
);
let ErrorBound::Bound(r) = ProjectedOverlay.bound(&c.at(Outline::Closed)) else {
panic!("expected the overlay to produce a bound when told the outline holds still");
};
let (cover, reach) = c.gaps(r);
assert!(
cover.max(reach) > r,
"the check missed an undercharge it should not have: radius {r:e}, cover {cover:e}, \
reach {reach:e}"
);
let ErrorBound::Bound(sound) = AffineFaceMap.bound(&c.collapse()) else {
panic!("the face map should judge this collapse");
};
assert!(
sound > 3.0 * r,
"expected the sound radius to dwarf the overlay's, got {sound:e} against {r:e}"
);
let ErrorBound::Bound(fixed) = ProjectedOverlay.bound(&c.collapse()) else {
panic!("expected the overlay to judge a moving outline rather than decline it");
};
let (cover, reach) = c.gaps(fixed);
assert!(
cover <= SLACK && reach <= SLACK,
"the overlay still undercharges a moving outline: radius {fixed:e}, cover {cover:e}, \
reach {reach:e}"
);
assert!(
fixed < sound,
"expected the overlay to beat the face map, got {fixed:e} against {sound:e}"
);
}