Exact Mesh Arrangements and Booleans in Real-Time ##…
0 reactions
Exact Mesh Arrangements and Booleans in Real-Time
## Problem
Multi-Mesh arrangements require resolving contour crossings, where intersection curves from different mesh pairs meet on the same face. Exact kernels handle this correctly but are too slow for interactive workflows. SoS-based methods perturb coincident geometry, collapsing the very configurations that require resolution.
## Methodology
`trueform` classifies all five intersection types (VV, VE, EE, VF, EF) in their canonical form.
Input coordinates are scaled to integer space. All predicates (`orient3d`, `orient2d`) are computed through an int32 → int64 → int128 -> int256 precision chain.
The arrangement runs in two stages. Stage 1: AABB trees narrow candidates. Pairwise intersections are computed exactly, each edge tagged with its originating face pair. Stage 2: where intersection edges from different mesh pairs cross each other on a shared face, the crossing point is identified by the triplet of three originating faces. This indirect predicate acts as a global identifier while keeping per-face resolution local and parallel.
After splitting, each resulting face must be labeled as inside or outside the other meshes. Faces are grouped into manifold edge-connected components. Each component is classified via a Beta-Bernoulli Bayesian classifier over local wedge observations along its intersection edges. This adds robustness to inconsistent winding in the input.
## Results
Boolean union, Stanford Dragon, 2 × 1.03M polygons. Apple M4 Max, 16 threads.
| Library | Time | Arithmetic | Non-manifold |
|---------|------|-----------|-------------|
| trueform | 27.8 ms | Exact | Handled |
| MeshLib | 161.5 ms | SoS | Auto-deletes |
| CGAL (EPIC) | 2,339 ms | Exact | Requires manifold |
| libigl (EPECK) | 7,735 ms | Exact | Requires manifold |
Full writeup: Exact Mesh Arrangements and Booleans in Real-Time https://polydera.com/algorithms/exact-mesh-arrangements-and-booleans-in-real-time
Live demonstration: Interactive Booleans https://trueform.polydera.com/live-examples/boolean
GitHub https://github.com/polydera/trueform
#technology
## Problem
Multi-Mesh arrangements require resolving contour crossings, where intersection curves from different mesh pairs meet on the same face. Exact kernels handle this correctly but are too slow for interactive workflows. SoS-based methods perturb coincident geometry, collapsing the very configurations that require resolution.
## Methodology
`trueform` classifies all five intersection types (VV, VE, EE, VF, EF) in their canonical form.
Input coordinates are scaled to integer space. All predicates (`orient3d`, `orient2d`) are computed through an int32 → int64 → int128 -> int256 precision chain.
The arrangement runs in two stages. Stage 1: AABB trees narrow candidates. Pairwise intersections are computed exactly, each edge tagged with its originating face pair. Stage 2: where intersection edges from different mesh pairs cross each other on a shared face, the crossing point is identified by the triplet of three originating faces. This indirect predicate acts as a global identifier while keeping per-face resolution local and parallel.
After splitting, each resulting face must be labeled as inside or outside the other meshes. Faces are grouped into manifold edge-connected components. Each component is classified via a Beta-Bernoulli Bayesian classifier over local wedge observations along its intersection edges. This adds robustness to inconsistent winding in the input.
## Results
Boolean union, Stanford Dragon, 2 × 1.03M polygons. Apple M4 Max, 16 threads.
| Library | Time | Arithmetic | Non-manifold |
|---------|------|-----------|-------------|
| trueform | 27.8 ms | Exact | Handled |
| MeshLib | 161.5 ms | SoS | Auto-deletes |
| CGAL (EPIC) | 2,339 ms | Exact | Requires manifold |
| libigl (EPECK) | 7,735 ms | Exact | Requires manifold |
Full writeup: Exact Mesh Arrangements and Booleans in Real-Time https://polydera.com/algorithms/exact-mesh-arrangements-and-booleans-in-real-time
Live demonstration: Interactive Booleans https://trueform.polydera.com/live-examples/boolean
GitHub https://github.com/polydera/trueform
#technology
| 2,000 mlx | |
| 3 | |
| 0 |