manifold_rust/robust/

mod.rs

// robust/mod.rs — Robust boolean engine for general (possibly non-manifold)
// closed, orientable triangle meshes.
//
// Implements Barki, Guennebaud, Foufou 2015, "Exact, robust, and efficient
// regularized Booleans on general 3D meshes" (docs/Exact, robust, and
// efficient booleans.pdf). This engine is a parallel alternative to the
// ported exact pipeline in src/boolean3.rs: it requires inputs only to be
// geometrically closed and orientable (triangle soup is fine — connectivity
// is never trusted), at the cost of exact rational arithmetic on the hard
// predicate/construction cases.
//
// Selection between the two engines is via `types::BooleanEngine`
// (Exact | Robust | Auto); the exact engine remains the default and its
// behavior is byte-identical to before this module existed.
//
// Submodules (pipeline order):
//   exact              — rational points, filtered predicates, constructions
//   tri_tri            — exact triangle-triangle intersection (narrow phase)
//   arrangement        — per-triangle 2D arrangement of intersection prims
//   cdt                — exact constrained Delaunay triangulation
//   intersection_graph — broad phase, prim distribution, piece emission
//   classify           — ring regularization, coincident-piece binding
//   propagate          — per-mesh component flood fill between cuts
//   ray_shoot          — exact winding numbers (component tags, wall tests)
//   soup               — triangle-soup import (closed/orientable validation)
//
// Classification is winding-number based: each surface component (bounded
// by intersection cuts) is inside or outside the other operand uniformly,
// decided by one exact query; pieces that are interior walls of their own
// operand (self-overlapping or nested sheets, where the winding exceeds 1)
// are detected with an own-mesh query just off the piece's outward side and
// dropped from both outputs — the regularized boolean's boundary only ever
// lies where the total winding steps between 0 and 1.

pub mod arrangement;
pub mod assemble;
pub mod cdt;
pub mod classify;
pub mod exact;
pub mod intersection_graph;
pub mod propagate;
pub mod ray_shoot;
pub mod soup;
pub mod tri_tri;

use crate::cancel::CancelToken;
use crate::impl_mesh::ManifoldImpl;
use crate::linalg::Vec3;
use crate::types::{Error, OpType};

use classify::Tag;
use exact::rational::R3;
use ray_shoot::piece_centroid;

fn is_cancelled(token: Option<&CancelToken>) -> bool {
    token.is_some_and(|t| t.is_cancelled())
}

fn cancelled_impl() -> ManifoldImpl {
    let mut out = ManifoldImpl::new();
    out.make_empty(Error::Cancelled);
    out
}

/// Robust boolean of two impls (manifold or soup). Same observable contract
/// as `boolean3::boolean_with_token`, computed by the Barki 2015 pipeline:
/// intersect exactly, arrange + retriangulate, classify pieces into
/// union/intersection sets by exact winding numbers, assemble the requested
/// one.
///
/// `Subtract` uses the identity P − Q = P ∩ Q^c: Q's winding is flipped on
/// the working copy and the intersection set is assembled; the winding
/// queries interpret the flipped operand as its (unbounded) complement.
pub fn boolean(
    a: &ManifoldImpl,
    b: &ManifoldImpl,
    op: OpType,
    token: Option<&CancelToken>,
) -> ManifoldImpl {
    if is_cancelled(token) {
        return cancelled_impl();
    }
    // Fast paths mirror the exact engine's observable behavior.
    if a.is_empty() {
        return match op {
            OpType::Add => b.clone(),
            OpType::Intersect | OpType::Subtract => ManifoldImpl::new(),
        };
    }
    if b.is_empty() {
        return match op {
            OpType::Add | OpType::Subtract => a.clone(),
            OpType::Intersect => ManifoldImpl::new(),
        };
    }
    let p_tris = soup::impl_to_tris(a);
    let mut q_tris = soup::impl_to_tris(b);
    let p_props = soup::impl_to_corner_props(a);
    let mut q_props = soup::impl_to_corner_props(b);

    if !a.bbox.does_overlap_box(&b.bbox) {
        match op {
            OpType::Add => {
                // Disjoint union: concatenate the soups and re-import. The
                // property context tags the two halves so each keeps its own
                // interpolated properties.
                let mut tris = p_tris.clone();
                tris.extend(q_tris.iter().cloned());
                let mut interner = intersection_graph::VertInterner::default();
                let pieces: Vec<intersection_graph::Piece> = tris
                    .iter()
                    .enumerate()
                    .map(|(i, t)| intersection_graph::Piece {
                        mesh: if i < p_tris.len() { 0 } else { 1 },
                        tri: if i < p_tris.len() { i } else { i - p_tris.len() },
                        vi: [
                            interner.intern_f64(t[0]),
                            interner.intern_f64(t[1]),
                            interner.intern_f64(t[2]),
                        ],
                    })
                    .collect();
                let ctx = assemble::PropCtx {
                    num_prop: [a.num_prop, b.num_prop],
                    tris: [&p_tris, &q_tris],
                    props: [&p_props, &q_props],
                };
                let props = (ctx.out_num_prop() > 0).then_some(&ctx);
                return assemble::assemble(
                    &pieces,
                    &interner.verts,
                    &interner.verts_f64,
                    |_| true,
                    props,
                )
                .into_impl();
            }
            OpType::Intersect => return ManifoldImpl::new(),
            OpType::Subtract => return a.clone(),
        }
    }

    let complement = op == OpType::Subtract;
    if complement {
        let nq = b.num_prop;
        for (ti, t) in q_tris.iter_mut().enumerate() {
            t.swap(1, 2);
            if nq > 0 {
                // Keep the corner-property alignment in step with the swap.
                let base = 3 * ti * nq;
                for k in 0..nq {
                    q_props.swap(base + nq + k, base + 2 * nq + k);
                }
            }
        }
    }

    let graph = intersection_graph::build_graph(&p_tris, &q_tris);
    if is_cancelled(token) {
        return cancelled_impl();
    }
    let t_cls = crate::timing::start();
    let cls = classify::classify_rings(&graph);
    crate::timing::print("robust: classify_rings", t_cls);
    if is_cancelled(token) {
        return cancelled_impl();
    }
    let t_prop = crate::timing::start();
    let prop = propagate::propagate(&graph, &cls);
    crate::timing::print("robust: propagate", t_prop);
    let mut tags = prop.tags;

    // Winding-based classification of every component the coincident-piece
    // binding did not decide. Both windings are constant per component:
    // components never cross an intersection cut, and the graph cuts each
    // mesh along its own self-intersections as well as along the other
    // operand's surface. So per component, one query against the other
    // operand decides ∪ vs ∩, and one query against the component's own
    // operand decides whether it is real boundary or an interior wall.
    // Whole-soup rational tables only exist when winding queries actually
    // run — a pass-through boolean (everything decided by rings/binding)
    // never converts an input triangle to rationals at all.
    let to_rational = |tris: &[[Vec3; 3]]| -> Vec<[R3; 3]> {
        tris.iter()
            .map(|t| [R3::from_vec3(t[0]), R3::from_vec3(t[1]), R3::from_vec3(t[2])])
            .collect()
    };
    let need_windings = !prop.untagged.is_empty();
    let own_rational: [Vec<[R3; 3]>; 2] = if need_windings {
        [to_rational(&p_tris), to_rational(&q_tris)]
    } else {
        [Vec::new(), Vec::new()]
    };
    let tri_boxes = |tris: &[[Vec3; 3]]| -> Vec<crate::types::Box> {
        tris.iter()
            .map(|t| {
                let mut b = crate::types::Box::from_points(t[0], t[1]);
                b.union_point(t[2]);
                b
            })
            .collect()
    };
    let own_boxes: [Vec<crate::types::Box>; 2] = if need_windings {
        [tri_boxes(&p_tris), tri_boxes(&q_tris)]
    } else {
        [Vec::new(), Vec::new()]
    };

    let t_winding = crate::timing::start();
    // BVH per operand, built once for the whole query batch (components can
    // number in the thousands on self-intersecting scans).
    let winding_indexes: Option<[ray_shoot::WindingIndex; 2]> = (!prop.untagged.is_empty())
        .then(|| [ray_shoot::WindingIndex::new(&p_tris), ray_shoot::WindingIndex::new(&q_tris)]);
    for &(root, rep) in &prop.untagged {
        if is_cancelled(token) {
            return cancelled_impl();
        }
        let piece = &graph.pieces[rep];
        let mesh = piece.mesh as usize;
        let indexes = winding_indexes.as_ref().expect("built when untagged is non-empty");
        let (other, other_index, other_is_complement): (&[[Vec3; 3]], _, bool) = if mesh == 0 {
            (&q_tris, &indexes[1], complement)
        } else {
            (&p_tris, &indexes[0], false)
        };
        let pv = graph.piece_verts(rep);
        let w = ray_shoot::winding_number_indexed(&piece_centroid(pv), other, other_index);
        let inside = if other_is_complement { w == 0 } else { w != 0 };
        let tag = if inside { Tag::Inter } else { Tag::Union };
        let own_f64: &[[Vec3; 3]] = if mesh == 0 { &p_tris } else { &q_tris };
        let component_tag =
            on_own_boundary(pv, &own_rational[mesh], own_f64, &own_boxes[mesh]).then_some(tag);
        for pi in 0..graph.pieces.len() {
            if !cls.discarded[pi] && prop.component[pi] == root {
                tags[pi] = component_tag;
            }
        }
    }

    crate::timing::print(
        &format!("robust: winding queries ({} components)", prop.untagged.len()),
        t_winding,
    );

    let want = match op {
        OpType::Add => Tag::Union,
        OpType::Subtract | OpType::Intersect => Tag::Inter,
    };
    let ctx = assemble::PropCtx {
        num_prop: [a.num_prop, b.num_prop],
        tris: [&p_tris, &q_tris],
        props: [&p_props, &q_props],
    };
    let props = (ctx.out_num_prop() > 0).then_some(&ctx);
    let t_asm = crate::timing::start();
    let out = assemble::assemble(
        &graph.pieces,
        &graph.verts,
        &graph.verts_f64,
        |pi| !cls.discarded[pi] && tags[pi] == Some(want),
        props,
    );
    crate::timing::print("robust: assemble+import", t_asm);
    out.into_impl()
}

/// Is this piece on the boundary of the solid its own operand bounds, or an
/// interior wall (a sheet with material on both sides)?
///
/// With the solid defined as `{winding ≠ 0}` (and its complement, for the
/// orientation-flipped subtraction operand, as `{winding == 0}`), membership
/// changes across the piece exactly when the winding just off its outward
/// side is 0 or −1: crossing the piece adds 1 to the winding, and only the
/// 0↔1 and −1↔0 steps change either membership predicate. Anything else —
/// e.g. a 1↔2 step inside a self-overlapping operand, or the inner of two
/// nested same-orientation shells — is an interior wall that no regularized
/// boolean output may contain.
fn on_own_boundary(
    pv: [&R3; 3],
    own: &[[R3; 3]],
    own_f64: &[[Vec3; 3]],
    own_boxes: &[crate::types::Box],
) -> bool {
    let normal = pv[1].sub(pv[0]).cross(&pv[2].sub(pv[0]));
    let w = ray_shoot::winding_off_surface(
        &piece_centroid(pv),
        &normal,
        own,
        own_f64,
        own_boxes,
    );
    w == 0 || w == -1
}

/// Import a raw triangle list as a boolean result (used by
/// `boolean3::compose_meshes` when any input is a soup; positions only —
/// the property-aware disjoint-union path in `boolean` builds its own
/// tagged pieces).
pub(crate) fn assemble_all(tris: &[[Vec3; 3]]) -> ManifoldImpl {
    let mut interner = intersection_graph::VertInterner::default();
    let pieces: Vec<intersection_graph::Piece> = tris
        .iter()
        .enumerate()
        .map(|(i, t)| intersection_graph::Piece {
            mesh: 0,
            tri: i,
            vi: [
                interner.intern_f64(t[0]),
                interner.intern_f64(t[1]),
                interner.intern_f64(t[2]),
            ],
        })
        .collect();
    assemble::assemble(&pieces, &interner.verts, &interner.verts_f64, |_| true, None).into_impl()
}

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

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

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

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

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