trueform: Fast And Robust Mesh CSG Via Topological Aggregation
Computational Geometry
Summary
The authors explain a new way to handle complex 3D shapes made by combining simpler shapes (mesh CSG) without losing precision in the important structural details. Instead of relying on approximate floating-point coordinates, they keep exact relationships by using integer-precise checks and topological rules. This approach helps them create watertight and accurate shapes much faster than previous methods, and it works well even in a web browser. Their method is implemented as a C++ library with easy-to-use bindings for Python and TypeScript.
Authors
Žiga Sajovic, Dejan Knez
Abstract
Mesh CSG output is consumed in floating point: however exact the computation, every emitted coordinate is materialised -- rounded to a representable position -- and the next stage can observe crossings and orderings the exact result never had. Only index-based topology survives materialisation. We keep it exact: within the build, the arrangement's radial structure is ordered by exact predicates on the original input planes -- exact without exact constructions -- and where a decision spans faces, the intended answer is recovered by topological aggregation: a majority vote over the disagreeing geometric observations within their topological unit. We compute the arrangement locally with integer-exact predicates, every stage a graph problem on graphs it never explicitly constructs. Pairwise intersections are classified into five canonical types (VV, VE, VF, EE, EF), each cut face is arranged in its own plane, and a two-level identity keeps the result consistent across faces with no global structure. The arrangement and its domain partition are built once and queried arbitrarily often: a boolean of any arity is a per-domain bit test, volumetric regions read straight off the partition, and open surfaces -- declared as oriented sheets -- cut volumes through the same algebra. The method is implemented in the header-only trueform library, in C++ with Python and TypeScript bindings. Compared to prior art, it produces valid, watertight output while running up to two orders of magnitude faster, and stays interactive in the browser.