Exact Mesh Arrangements and Booleans in Real-Time

Mesh arrangements decompose overlapping geometry into classified regions — splitting faces along intersection curves so every face belongs to exactly one region. Mesh booleans select which regions to keep: union, intersection, difference.

Real meshes are not ideal manifolds. They carry non-manifold flaps, inconsistent winding, coplanar faces, and accumulated pipeline artifacts. trueform handles all of them.

Exactness

Two kinds of exactness matter in mesh arrangements: geometric and topological.

Geometric exactness

Input coordinates are scaled to exact integer space. All predicates — orientation tests, intersection points, determinants — are computed with exact integer arithmetic through a precision chain. No floating-point operation participates in any geometric decision.

orient3d_sign returns −1, 0, or +1 — exactly. Zero means coplanar, not "close to coplanar."

Topological exactness

An intersection point can land on a vertex, on an edge, or at the meeting point of two coplanar edges. Five distinct configurations:

Geometric exactness without topological exactness is typically paired with Simulation of Simplicity (SoS). SoS perturbs input so all configurations collapse to EF — deterministic but arbitrary. A square placed into a cube with edges on faces might produce no intersections, partial, or all, depending on perturbation order. These configurations are not edge cases to avoid — they define contour crossings in multi-mesh arrangements.

trueform classifies all five exactly — orient3d_sign separates coplanar from non-coplanar, orient2d_sign resolves the coplanar cases. Each configuration is resolved to its canonical form.

Arrangements

Arrangements resolve multiple mutually intersecting meshes simultaneously.

Indirect predicates

An intersection edge is defined by its originating face pair. An intersection point between two edges is defined by the union of their face pair IDs — a unique triplet of three faces. This identifies points topologically, avoiding geometric ambiguity. Coordinates are computed from the triplet via orient2d-based interpolation in integer arithmetic, only when needed.

Indirect predicates allow the arrangement to be formulated in two stages: compute pairwise intersection contours between all mesh pairs, then intersect those contours within each face.

Stage 1: pairwise intersection contours

An AABB tree narrows candidates to overlapping face pairs. For each pair, intersections are computed exactly. Each intersection produces an edge on both faces, tagged with its originating face pair.

Stage 2: per-face contour intersections

Each intersected face carries a small number of edges from different mesh pairs — typically 2–5. These are projected to the face plane and intersected with topological exactness: VV, VE, and EE configurations classified via orient2d. The result is an intersection graph embedded in the face, defining how it will be split.

Each face has few edges — trivial to process. Each face is independent — all processed in parallel. Points are identified across faces via their triplets.

Booleans

A boolean is an arrangement with a classification step. After splitting faces along intersection curves, each resulting face must be labeled as inside or outside the other mesh. The boolean operation selects which labels to keep.

Components

Faces are grouped into manifold edge-connected components. Two faces belong to the same component if they share a manifold edge that is not an intersection edge. Non-manifold edges and intersection edges act as barriers — they prohibit crossing between components. Each component receives a single label.

Wedge classification

For each intersection edge in a component, the two same-mesh faces sharing that edge form a wedge. A test point from the opposite-mesh neighbor is classified against this wedge using exact orient3d:

Coplanar face pairs are classified directly as aligned or opposing boundary based on normal direction.

Bayesian classification

Each intersection edge contributes an observation to its component — inside or outside. The per-component label is determined by a Beta-Bernoulli classifier over these observations: inside, outside, aligned boundary, or opposing boundary. Components with no intersection edges fall back to signed distance or ray-based containment tests.

Operation mapping

Comparison with existing SDKs

Four libraries are commonly used for mesh booleans: CGAL, libigl, MeshLib, and trueform. This is how they compare.

Capabilities

Performance

Stanford Dragon at varying resolutions. Linear scaling is maintained through 2M+ polygons.

Apple M4 Max 16 threads Clang -O3 mimalloc

Boolean union

trueform uses exact predicates and canonical topology. MeshLib uses SoS with int32. CGAL uses EPIC kernel. libigl uses EPECK (GMP).

Polygon arrangements

Two copies concatenated into a single self-intersecting mesh. MeshLib not benchmarked — refuses nested contour crossings.

Intersection curves

Standalone extraction of crossing polylines. Most SDKs only provide curves as a side-effect of a full boolean operation.

Interactive charts, full methodology, and source code: trueform benchmarks.

Try it live · Documentation · GitHub · Open Lunar

@article{polydera:exact-mesh-arrangements-and-booleans-in-real-time,
  title={Exact Mesh Arrangements and Booleans in Real-Time},
  author={Sajovic, {\v{Z}}iga, Polydera},
  year={2026},
  url={https://polydera.com/algorithms/exact-mesh-arrangements-and-booleans-in-real-time},
  organization={Polydera}
}