ifc-lite-geometry 9.2.0

// This Source Code Form is subject to the terms of the Mozilla Public
// License, v. 2.0. If a copy of the MPL was not distributed with this
// file, You can obtain one at https://mozilla.org/MPL/2.0/.

//! Mesh-closure predicates the analytic cut self-checks its output against.
//!
//! Split out of `prism_cut.rs` to keep it under the module-size ratchet.

use super::{dot, norm, normalize, scale, sub, V3};
use crate::mesh::Mesh;
use rustc_hash::FxHashMap;

/// DIRECTED quantized closed-surface audit (0.1 mm grid): every directed edge
/// must be cancelled by its reverse. Strictly stronger than the undirected
/// 2-manifold check — it catches inconsistent winding and doubled coincident
/// surfaces (two triangles sharing an edge in the SAME direction), not just
/// cracks. Triangles that collapse to a degenerate key on the grid are skipped
/// (their edges net to zero).
pub(crate) fn directed_closed(mesh: &Mesh) -> bool {
    let key = |i: u32| -> (i64, i64, i64) {
        let b = i as usize * 3;
        let q = |v: f32| (v as f64 / 1.0e-4).round() as i64;
        (
            q(mesh.positions[b]),
            q(mesh.positions[b + 1]),
            q(mesh.positions[b + 2]),
        )
    };
    let mut edges: FxHashMap<((i64, i64, i64), (i64, i64, i64)), i64> = FxHashMap::default();
    for tri in mesh.indices.chunks_exact(3) {
        let (ka, kb, kc) = (key(tri[0]), key(tri[1]), key(tri[2]));
        if ka == kb || kb == kc || kc == ka {
            continue;
        }
        for (x, y) in [(ka, kb), (kb, kc), (kc, ka)] {
            *edges.entry((x, y)).or_insert(0) += 1;
            *edges.entry((y, x)).or_insert(0) -= 1;
        }
    }
    !edges.is_empty() && edges.values().all(|&c| c == 0)
}

/// Closed-surface audit with a HAIRLINE tolerance: the surface passes when
/// every unpaired directed edge (0.1 mm grid) is collinearly COVERED by
/// unpaired edges of the opposite net sign — the signature of two adjacent
/// faces subdividing a shared boundary line differently (a T-junction chain,
/// invisible sub-grid gap), NOT of a missing surface. A genuine hole leaves a
/// boundary loop whose edges have nothing opposite along them and fails. The
/// exact kernel's own output is routinely NOT even undirected-watertight on
/// these hosts, so this gate is still far stricter than the status quo.
pub(crate) fn closed_or_hairline(mesh: &Mesh) -> bool {
    type K = (i64, i64, i64);
    let key = |i: u32| -> K {
        let b = i as usize * 3;
        let q = |v: f32| (v as f64 / 1.0e-4).round() as i64;
        (
            q(mesh.positions[b]),
            q(mesh.positions[b + 1]),
            q(mesh.positions[b + 2]),
        )
    };
    let mut edges: FxHashMap<(K, K), i64> = FxHashMap::default();
    for tri in mesh.indices.chunks_exact(3) {
        let (ka, kb, kc) = (key(tri[0]), key(tri[1]), key(tri[2]));
        if ka == kb || kb == kc || kc == ka {
            continue;
        }
        for (x, y) in [(ka, kb), (kb, kc), (kc, ka)] {
            *edges.entry((x, y)).or_insert(0) += 1;
            *edges.entry((y, x)).or_insert(0) -= 1;
        }
    }
    if edges.is_empty() {
        return false;
    }
    // Canonicalize to undirected segments with a net sign.
    //
    // Sorted by endpoint key, NOT left in `edges` iteration order: `FxHashMap`
    // iterates target-dependently, and the grouping below is greedy, so an
    // arbitrary seed order could reach a different verdict on native than on
    // wasm32. This sort closes that: `edges` is keyed by `(K, K)`, so every
    // `(a, b)` pushed here is unique and the sort key is tie-free -- an unstable
    // sort with a tie-free key yields one deterministic sequence whatever order
    // the map was walked in. The length sort that seeds the grouping is a total
    // order too, by its own index tie-break; see the comment there.
    let mut bad: Vec<(K, K, i64)> = Vec::new();
    for (&(a, b), &c) in edges.iter() {
        if c > 0 {
            bad.push((a, b, c));
        }
    }
    bad.sort_unstable_by_key(|&(a, b, _)| (a, b));
    if bad.is_empty() {
        return true;
    }
    if bad.len() > 64 {
        return false; // way past hairline territory
    }
    let p = |k: K| [k.0 as f64, k.1 as f64, k.2 as f64]; // grid units (0.1 mm)

    // Rigorous hairline test. A hairline (T-junction) boundary is one where the
    // uncancelled directed edges, viewed as a 1-D SIGNED measure along each
    // supporting line, net to ZERO everywhere: every stretch covered by an edge
    // running one way is covered the SAME number of times by edges running the
    // other way (two adjacent faces subdividing a shared line differently). A
    // genuine hole — or a boundary edge only PARTIALLY covered, or covered the
    // wrong number of times — leaves a stretch with nonzero net coverage and
    // fails. This is strictly stronger than the old midpoint-proximity test,
    // which a LONG unmatched edge could spoof merely by having a SHORT reverse
    // edge sit near its midpoint (the short edge "covered" a single point, never
    // the whole interval, and multiplicity was ignored entirely).
    const COLLINEAR_TOL: f64 = 2.0; // grid units (~0.2 mm) perpendicular slack
    const T_EPS: f64 = 1.0e-6; // grid units: ignore sub-interval slivers

    struct Seg {
        a: V3,
        b: V3,
        m: i64,
    }
    let segs: Vec<Seg> = bad
        .iter()
        .map(|&(a, b, c)| Seg {
            a: p(a),
            b: p(b),
            m: c,
        })
        .collect();

    // Perpendicular distance from point `x` to the infinite line `(o, dir)`
    // (`dir` unit). Perp distance is convex along a segment, so if BOTH
    // endpoints of a segment are within tol of a line, the whole segment is —
    // that is our collinearity-coincidence test (no separate parallel check
    // needed, and it correctly rejects a segment that merely crosses the line).
    let perp = |x: V3, o: V3, dir: V3| -> f64 {
        let w = sub(x, o);
        let along = dot(w, dir);
        norm(sub(w, scale(dir, along)))
    };

    struct Line {
        o: V3,
        dir: V3,
        members: Vec<usize>,
    }
    // Seed lines from the LONGEST segments first: a long edge fixes a stable
    // direction, so its collinear short neighbours join it rather than each
    // spawning a slightly-rotated line of its own (greedy fragmentation would
    // split a genuinely-covered boundary across groups and report phantom gaps).
    let mut order: Vec<usize> = (0..segs.len()).collect();
    order.sort_by(|&i, &j| {
        let li = dot(sub(segs[i].b, segs[i].a), sub(segs[i].b, segs[i].a));
        let lj = dot(sub(segs[j].b, segs[j].a), sub(segs[j].b, segs[j].a));
        // `total_cmp` + index tie-break: a total order, so the seed sequence is a
        // pure function of `bad` (already canonically sorted above).
        lj.total_cmp(&li).then(i.cmp(&j))
    });
    let mut lines: Vec<Line> = Vec::new();
    'seg: for si in order {
        let s = &segs[si];
        let Some(sdir) = normalize(sub(s.b, s.a)) else {
            // Degenerate (zero-length) bad edge: cannot seal anything → defer.
            return false;
        };
        for line in lines.iter_mut() {
            if perp(s.a, line.o, line.dir) <= COLLINEAR_TOL
                && perp(s.b, line.o, line.dir) <= COLLINEAR_TOL
            {
                line.members.push(si);
                continue 'seg;
            }
        }
        lines.push(Line {
            o: s.a,
            dir: sdir,
            members: vec![si],
        });
    }

    // Sweep each line's signed multiplicity coverage. At every point along the
    // line the signed count of covering edges (this line's `+dir` edges minus
    // its `-dir` edges, weighted by multiplicity) must net to ZERO — the exact
    // T-junction signature. We track the longest CONTIGUOUS mis-covered run and
    // reject once it exceeds `GAP_TOL`: a hole, a partially-covered long edge,
    // or a multiply-covered stretch leaves a macroscopic run, whereas the ≤0.2mm
    // sub-grid jitter of a genuine hairline stays inside the same quantization
    // slack the collinearity grouping already allows. (This deliberately still
    // admits the hosts whose exact-kernel meshing is itself not undirected-
    // watertight — the documented reason the hairline gate exists — while the
    // old midpoint test's spoof, a long edge grazed only near its midpoint by a
    // short reverse edge, leaves a run of nearly the whole edge and is rejected.)
    const GAP_TOL: f64 = COLLINEAR_TOL; // 2 grid units (~0.2 mm)
    for line in &lines {
        let mut ints: Vec<(f64, f64, i64)> = Vec::with_capacity(line.members.len());
        let mut breaks: Vec<f64> = Vec::with_capacity(line.members.len() * 2);
        for &si in &line.members {
            let s = &segs[si];
            let ta = dot(sub(s.a, line.o), line.dir);
            let tb = dot(sub(s.b, line.o), line.dir);
            let sign = if tb >= ta { 1 } else { -1 };
            ints.push((ta.min(tb), ta.max(tb), sign * s.m));
            breaks.push(ta);
            breaks.push(tb);
        }
        // `total_cmp`, matching the seed sort above: a non-finite coordinate here
        // must reject the cut, not abort the process.
        breaks.sort_by(|x, y| x.total_cmp(y));
        let mut run = 0.0_f64;
        for w in breaks.windows(2) {
            let (lo, hi) = (w[0], w[1]);
            let len = hi - lo;
            if len <= T_EPS {
                continue;
            }
            let mid = 0.5 * (lo + hi);
            let mut sum = 0i64;
            for &(ilo, ihi, sm) in &ints {
                if ilo - T_EPS <= mid && mid <= ihi + T_EPS {
                    sum += sm;
                }
            }
            if sum != 0 {
                run += len;
                if run > GAP_TOL {
                    return false;
                }
            } else {
                run = 0.0;
            }
        }
    }
    true
}

/// Per-undirected-edge MULTIPLICITY defects, the class both predicates above
/// are structurally blind to.
///
/// [`directed_closed`] and [`closed_or_hairline`] both count edges with a
/// SIGNED tally (`+1` forward, `-1` reverse) and pass when everything nets to
/// zero. Cancellation is the point there — it is what makes a hairline
/// T-junction chain forgivable — but it also erases multiplicity: an edge used
/// by FOUR triangles, two each way, nets to exactly zero and reads as closed.
/// That is a doubled coincident surface, not a solid boundary, and no amount of
/// tolerance tuning on a signed tally can see it.
///
/// So this counts UNSIGNED uses per undirected edge and reports the two
/// defects a signed tally cannot represent:
///
/// * `over_used` — an undirected edge with MORE than two triangle uses
///   (non-manifold: a fin, a doubled skin, or self-intersecting output).
/// * `same_direction` — an undirected edge with exactly two uses that run the
///   SAME way round (inconsistent winding: one of the two neighbours is
///   flipped).
///
/// An edge used ONCE is deliberately NOT a defect here. That is an open
/// boundary, which is what the two closure predicates above already measure,
/// and it is the reading that T-junction tessellation trips constantly. Keeping
/// it out is what lets a caller gate on this without inheriting that class's
/// false-positive rate.
///
/// # Why this one is EXACT and its neighbours are not
///
/// The two predicates above snap vertices to a 0.1 mm grid. That is right for
/// them: they ask whether a surface CLOSES, and two corners a hair apart
/// should close. It is wrong here, and not by a little. Snapping merges two
/// distinct vertices closer than a grid cell into one key, and the moment two
/// distinct edges collapse onto one key their uses ADD — so two perfectly
/// manifold surfaces sitting 0.03 mm apart report a four-use edge that exists
/// in neither of them. Measured on the snapped key this replaced: the two
/// closed bipyramids in `closure_checks_tests.rs`, offset 0.03 mm, report
/// `over_used = 12`, and the 0.05 mm slab there reports `over_used = 1` — both
/// entirely manufactured by the snap, and both clean under exact keys.
///
/// That failure mode is fatal for a REJECTION predicate in a way it is not for
/// a closure one. A snap that wrongly closes a hairline gap errs toward
/// accepting; a snap that wrongly fuses two surfaces errs toward throwing away
/// geometry that was never wrong. So the keys here are the vertex coordinates
/// EXACTLY, bit for bit (with `-0.0` folded to `0.0` so the two spellings of
/// zero are one point). Two positions are the same point only if they are the
/// same position.
///
/// The cost is a miss, not a false positive: a genuine non-manifold edge whose
/// endpoints differ in the last bit reads as two separate edges and is not
/// reported. That is the right trade for a predicate whose job is to discard a
/// kernel result — and it is cheap in practice, because the kernel interns
/// coincident corners, so a real shared edge in its output is bit-identical at
/// both ends.
// The three items below are consumed by `csg::topology_diagnostic`'s
// `manifold_gate_reject`, which only exists under `csg_manifold_gate`, and by
// this module's own tests. `allow(dead_code)` rather than a `cfg` on the
// predicate itself: the tests must keep running in the default build, since
// they are what proves the predicate still reads what its doc says before the
// gate is ever turned on.
#[cfg_attr(not(feature = "csg_manifold_gate"), allow(dead_code))]
#[derive(Debug, Default, PartialEq, Eq)]
pub(crate) struct EdgeMultiplicityDefects {
    /// Undirected edges used by more than two triangles.
    pub over_used: usize,
    /// Undirected edges used exactly twice, both uses running the same way.
    pub same_direction: usize,
}

#[cfg_attr(not(feature = "csg_manifold_gate"), allow(dead_code))]
impl EdgeMultiplicityDefects {
    /// True when the mesh carries neither defect.
    pub(crate) fn is_clean(&self) -> bool {
        self.over_used == 0 && self.same_direction == 0
    }
}

/// Count the [`EdgeMultiplicityDefects`] of `mesh`. O(triangles) hash sweep,
/// the same shape and cost as [`directed_closed`] — but keyed EXACTLY, for the
/// reason spelled out on [`EdgeMultiplicityDefects`].
#[cfg_attr(not(feature = "csg_manifold_gate"), allow(dead_code))]
pub(crate) fn edge_multiplicity_defects(mesh: &Mesh) -> EdgeMultiplicityDefects {
    // Exact vertex identity: the raw f32 bits of the three coordinates, with
    // `-0.0` normalised to `0.0` (they compare equal but have different bit
    // patterns, and they are the same point). Non-finite coordinates cannot
    // reach here — every caller runs `validate_mesh` first — so no NaN key can
    // split a vertex from itself.
    type K = (u32, u32, u32);
    let key = |i: u32| -> K {
        let b = i as usize * 3;
        let q = |v: f32| (if v == 0.0 { 0.0f32 } else { v }).to_bits();
        (
            q(mesh.positions[b]),
            q(mesh.positions[b + 1]),
            q(mesh.positions[b + 2]),
        )
    };
    // Undirected edge (lo, hi) -> (uses running lo->hi, uses running hi->lo).
    let mut edges: FxHashMap<(K, K), (u32, u32)> = FxHashMap::default();
    for tri in mesh.indices.chunks_exact(3) {
        let (ka, kb, kc) = (key(tri[0]), key(tri[1]), key(tri[2]));
        // A triangle with two corners at the SAME point contributes a
        // zero-length edge and two coincident ones; it bounds no area and its
        // uses would be noise. Skipped, matching what the signed predicates do
        // with their own (grid-scale) degenerates.
        if ka == kb || kb == kc || kc == ka {
            continue;
        }
        for (x, y) in [(ka, kb), (kb, kc), (kc, ka)] {
            let (lo, hi, forward) = if x <= y { (x, y, true) } else { (y, x, false) };
            let slot = edges.entry((lo, hi)).or_insert((0, 0));
            if forward {
                slot.0 += 1;
            } else {
                slot.1 += 1;
            }
        }
    }
    let mut defects = EdgeMultiplicityDefects::default();
    for &(fwd, rev) in edges.values() {
        match fwd + rev {
            0 | 1 => {}
            2 if fwd == 1 && rev == 1 => {}
            2 => defects.same_direction += 1,
            _ => defects.over_used += 1,
        }
    }
    defects
}

#[cfg(test)]
#[path = "closure_checks_tests.rs"]
mod closure_checks_tests;