hypermesh

hypermesh provides exact 3D triangle-mesh Boolean operations for the Hyper geometry stack. It accepts finite, closed, piecewise-winding-number (PWN) meshes, constructs local exact arrangements using an EMBER-style subdivision and BSP pipeline, propagates winding-number evidence, and returns a certified polygon arrangement or an explicit error.

The crate owns mesh validation, intersection, classification, and certified output triangulation. File-format IO, including OBJ parsing and export, belongs in adapter crates such as csgrs.

WASM Demo

The WASM demo is configured for https://timschmidt.github.io/hypermesh/. Its source and Trunk configuration live in examples/hypermesh_ui.

Typical Mesh Problems

Mesh Booleans make topology depend on exact geometric branch decisions: sidedness, coplanarity, segment incidence, polygon overlap, winding transitions, and output edge cancellation. Floating-point disagreement at any of those branches can create cracks, drop faces, invert output, or make a repair loop depend on tolerance choices.

hypermesh routes topology-changing decisions through hyperreal, hyperlattice, and hyperlimit. It does not repair an uncertified result into apparent success. When a required sign, incidence, reference-propagation step, leaf classification, or output closure fact cannot be certified, the operation returns HypermeshError.

Main Types

Precision Model

Native coordinates are hyperreal::Real values carried by hyperlattice::Point3. Planes, intersections, winding transitions, and closure checks retain exact values; primitive floats should remain at explicit import, rendering, or export boundaries.

The supported input model is a non-empty collection of finite, closed, consistently oriented PWN triangle meshes. Disconnected and nested closed components are supported. Empty meshes, invalid indices, degenerate triangles, open surfaces, directed edge imbalances, and arbitrary non-PWN surface collections are rejected.

Completeness applies when every strict predicate required by the finite closed-PWN operation is decidable under the bounded refinement policy. Computable Real values whose required signs cannot be certified remain outside that boundary and produce an error rather than an approximate topology decision.

Algorithm

The Boolean path follows the EMBER architecture:

  1. build_polygon_soup validates each source mesh and converts triangles to exact planar polygons with winding-number transitions.
  2. Adaptive axis-aligned subdivision isolates local arrangements while propagating an outside reference point and its winding vector.
  3. Local BSP trees split intersecting polygons into disjoint fragments.
  4. Exact segment traces classify fragments from front/back winding vectors.
  5. certify_output_polygon_closure verifies singleton-edge absence and exact directed edge cancellation before the operation succeeds.
  6. triangulate_and_resolve_certified triangulates the arrangement, resolves output T-junctions and crossings, and rejects open or zero-volume output.

EmberConfig::default() uses DEFAULT_MAX_DEPTH, currently usize::MAX: there is no caller-selected arbitrary depth cap. A finite max_depth is a certification budget; reaching it before a leaf is certified returns SubdivisionDepthLimit.

Numerical Explosion

hypermesh limits exact-expression growth structurally. Axis-aligned subdivision reduces candidate sets, exact BVH bounds avoid unnecessary polygon tests, plane-based polygons defer affine division through homogeneous intersections, and local BSP trees avoid constructing one global arrangement. Cached plane and edge profiles also reduce repeated exact comparisons during output assembly.

Performance Model

The implementation prioritizes pruning work before invoking expensive exact predicates: AABB and BVH rejection, adaptive subdivision, leaf-level pairwise tests, local winding traces, and operation-specific reachability all constrain the exact work. Every public Boolean call is immediate and operation-scoped. boolean_operation returns certified polygons, while boolean_triangle_soup fuses the same operation with indexed output materialization. Certified-convex variants accept exact facts from mesh owners without exposing intermediate arrangement state. The current implementation is single-process Rust and does not claim the parallel throughput numbers of the EMBER reference implementation.

Current Status

Implemented today:

Current boundaries:

Installation

The Hyper crates are currently developed as sibling repositories:

[dependencies]
hypermesh = { path = "../hypermesh" }
hyperlattice = { path = "../hyperlattice" }
hyperreal = { path = "../hyperreal" }

hypermesh currently has no optional Cargo features.

Usage

use hypermesh::{
    BooleanOp, EmberConfig, InputMesh, Point3, Real, Triangle, boolean_operation,
    triangulate_and_resolve_certified,
};

fn tetrahedron(offset: i64) -> InputMesh {
    let p = |x, y, z| {
        Point3::new(
            Real::from(x + offset),
            Real::from(y),
            Real::from(z),
        )
    };

    InputMesh::new(
        vec![p(0, 0, 0), p(2, 0, 0), p(0, 2, 0), p(0, 0, 2)],
        vec![
            Triangle::new(0, 2, 1),
            Triangle::new(0, 1, 3),
            Triangle::new(1, 2, 3),
            Triangle::new(2, 0, 3),
        ],
    )
}

fn main() -> hypermesh::HypermeshResult<()> {
    let a = tetrahedron(0);
    let b = tetrahedron(3);
    let meshes = [a.as_ref(), b.as_ref()];

    let result = boolean_operation(
        &meshes,
        BooleanOp::Union,
        EmberConfig::default(),
    )?;
    let triangles = triangulate_and_resolve_certified(&result)?;
    let gpu = triangles
        .try_to_gpu_mesh_f32()
        .expect("finite exact output should approximate for the renderer");

    println!("{} exact output triangles", triangles.triangles.len());
    println!("{} GPU indices", gpu.indices.len());
    Ok(())
}

For two meshes, boolean_union, boolean_intersection, boolean_difference, and boolean_symmetric_difference are convenience wrappers. Use boolean_operation for multi-mesh operations and boolean_triangle_soup when indexed triangles are the desired result. Use extract_output when polygon loops are preferable.

Development

Paper-derived optimization experiments and their benchmark, trace, and test evidence are recorded in PERFORMANCE.md.

The pinned competitive suite compares the same Boolean corpus with boolmesh and the pure-Rust Manifold port, then validates HyperMesh output through tri-mesh’s half-edge carrier. Its benchmark also runs all three Boolean operations on two 3,072-triangle closed meshes. Every competitor is additionally wired to the public-domain YeahRight corpus: the Boolean engines clip a deterministically subdivided 4,512-triangle hull, while all four libraries construct their native mesh carrier from that same hull:

cargo test --test competitive
cargo bench --bench competitive

The regular suite keeps the 4,512-triangle YeahRight fixture. Run the ignored memory-pressure stress periodically to instantiate and union the 18,048- and 72,192-triangle variants while retaining all competitor carriers together:

cargo test --release --test competitive larger_yeahright_fixtures_expose_memory_pressure -- --ignored --nocapture

Run the crate checks from this directory:

cargo fmt --check
cargo test --all-targets
cargo clippy --all-targets -- -D warnings
RUSTDOCFLAGS="-D warnings" cargo doc --no-deps
cargo check --examples --benches
cargo run --example basic

Build the browser demo with Trunk and the WebAssembly target installed:

rustup target add wasm32-unknown-unknown
cd examples/hypermesh_ui
trunk build --release --locked

GitHub Actions runs the native crate checks and the locked WASM demo build. The Pages workflow publishes the Trunk output from main when GitHub Pages is configured to use GitHub Actions as its source.

References

Hyper Ecosystem

hypermesh builds on hyperreal, hyperlimit, and hyperlattice. It supplies exact triangle-mesh Booleans to hyperbrep, csgrs, and the other Hyper geometry crates.

This site is open source. Improve this page.