1 Introduction↩︎

Constructive Solid Geometry (CSG) on triangulated meshes — encompassing the arrangement of surfaces and the boolean operations that select among them — serves as a foundational tool in geometric modelling, computer-aided design, scientific simulation, and computer graphics. Over the past decades, robust pipelines have been developed, with recent advances enabling interactive performance. In these downstream applications, the output of a CSG pipeline is rarely the final product; it is typically passed to subsequent stages, such as remeshing, finite-element analysis, or file-format conversion. Critically, this output is represented in floating-point arithmetic. Composing CSG stages is therefore hard on two fronts at once: constructing new geometric elements — new vertices, for instance — with exact or inexact representations of their embedding, and controlling the topology between those elements as it passes through the pipeline.

For the geometry, exact predicates have received attention for decades, and several kernels extend exactness through chained constructions [1]–[4]. When computations reach the limits of the floating-point representation, the classical trade-off appears: exact but expensive arbitrary-precision kernels against filtered or approximated but fast ones. Existing techniques push the exact representation as far as possible through the pipeline before either meeting a numerical failure or switching to a costlier representation. Yet exactness inside a stage is not the missing piece. However exact the computation, its result must be materialised — committed to a representable position, whether IEEE double, an integer grid, or a downstream format — to leave one stage and enter the next, and the guarantee stops there. Pushing exactness further postpones this materialisation; it does not remove it.

Besides the geometry, there is the topology — and the topology is what survives. Connected components, the ring of faces around a non-manifold edge, the incidences the user models: these are decided by index adjacency, and they are the same combinatorial objects at any precision, on either side of materialisation. What does not survive are the relations between them. The radial order of faces around a non-manifold edge, or the nesting of one connected component inside another, is a single fact of the intended geometry, yet each is read through exact orient3d evaluations on coordinates that materialisation has already perturbed, so readings of the same relation can disagree (Figure 1). Inside our own build the radial order escapes this entirely — it is decided by exact predicates on the original input planes, never on a constructed coordinate (Section 2.3) — but any consumer of the materialised arrangement, composed pipelines included, faces the disagreement. Our answer is to make exact only what survives — the topology — and to treat every geometric answer as an observation of an intended geometry. Each kind of decision has a natural aggregation scope, its topological unit: a component for orientation, a relation between components for merging, a volumetric domain for classification. Within a unit the intended geometry admits one answer, so a weighted-majority vote across the unit’s observations recovers it. What a CSG stage can still guarantee once its output is materialised, it turns out, is the topology.

The contacts the user modelled — coincident vertices, on-edge points, coplanar faces — are classified exactly and survive intact, never blurred by perturbation. For the same reason, symbolic perturbation (Simulation of Simplicity [5]) is excluded from the arrangement: where contact is intended, perturbation decides topology arbitrarily (Figure 2). Non-manifold input is first-class data: flaps, T-junctions, and isolated edges are units to aggregate over, not exceptions to clean up before processing.

Booleans are classically defined on solids, and an open surface has no inside. Yet cutting by open surfaces is everyday work: a geological horizon splits a volume into strata, a free-form section halves a part. Because classification here is a per-domain bitvector rather than an inside test, open surfaces enter the same algebra directly: declared as sheets — oriented separators whose bit reads “behind the normal” — they cut volumes through the ordinary boolean operators (Figure 9).

The result is a composable CSG stage: an arrangement computed locally — per face pair, per face plane, on a bounded integer kernel — with no global exact structure to maintain, classified by votes into volumetric domains. The build is paid once and any expression over the operands then reads off per domain (Section 2.7), at interactive rates, in C++, Python, and the browser. We position the method against prior work next, and state its contributions in §1.2.

1.1 Related work↩︎

Geometric exactness. The arithmetic-kernel literature has converged on a small set of approaches. Shewchuk’s adaptive floating-point expansions [1] compute a predicate’s sign exactly by accumulating non-overlapping floating-point components, refining only when the filter cascade fails. The Filtered Predicate Generator (FPG) [6] generates such filtered predicates from polynomial expressions. CGAL’s lazy rationals [7] offer the same exactness through arbitrary-precision evaluation. Indirect predicates [2] take a different route: they store constructed points as recipes (line-plane intersections, triple-plane intersections) and fold them into the predicate’s polynomial. Cherchi’s mesh arrangement [8] is built on this. EMBER’s plane-based representation [3], [9], after Campen and Kobbelt [10], [11], uses fixed-width 256-bit integer arithmetic with no filter cascade, delivering exact CSG at interactive rates. Lévy’s recent CSG pipeline [4] implements two exact kernels — Shewchuk expansions and multi-precision floats — and compares them, with the multi-precision kernel the robust default. Extending exactness from one evaluation to chained constructions is where the cost concentrates: expansions can reach tens of thousands of components in degenerate cases [4], and fixed-width representations must widen at each composition or change representation. Interval arithmetic [12] provides the cheap filter all of these depend on. A separate strategy resolves degeneracies rather than computing through them: Simulation of Simplicity (SoS) [5] perturbs inputs symbolically so predicates never return zero, eliminating degenerate cases by construction. The perturbation is deterministic but arbitrary, and not topologically exact (§1). Trueform sits between Attene and EMBER: a fixed three-width integer ladder (T0\(\to\)T1\(\to\)T2), no dynamic allocation, no fallback kernel. Degeneracies are classified exactly through the five-type discipline of Section 2.1, not perturbed away.

Materialisation. Once exact coordinates materialise to IEEE double, new intersections may appear that were not in the exact result. Prior work has taken two responses. The first keeps exactness inside the system as long as possible: EMBER’s bounded-width plane representation [3], [9] guarantees exactness without leaving its kernel, and Lévy’s pipeline [4] keeps exact coordinates throughout (Shewchuk expansions or multi-precision floats). The second rounds back to a tractable representation at materialisation: 3D snap rounding [13], [14], geometric rounding for meshes [15], and Cherchi’s iterated cast-to-float heuristic [8] minimise the damage the round-trip causes. Neither response removes it: EMBER’s own snap-rounding step at materialisation [3] and Lévy explicitly setting the float conversion aside as an open problem [4] mark materialisation as intrinsic to the use case, not a defect of any particular kernel. Trueform takes a third path: the observed disagreements materialisation introduces are inputs to topological aggregation, not noise to be hidden; the intended consistency of each topological unit recovers the answer.

Topology and classification. Prior approaches to classification differ in where the geometric decision lives. Zhou’s pipeline [16] decides globally, building the arrangement with CGAL exact predicates and flooding labels through the resulting topology. Cherchi’s arrangement [8] does the same with indirect predicates and ear-cut triangulation. Lévy [4] also floods globally but over a richer representation: the Weiler 3-map [17] in the language of combinatorial maps [18], with operand-membership bit-vectors as the labels. Cherchi’s 2022 interactive variant [19] localises: a per-patch ray cast decides inside/outside one face patch at a time. Böhm and Runge [20] localise further, sorting incident triangles angularly around each non-manifold edge (a floating-point angular sort, degenerate elements excluded by precondition) and extracting domains per edge — each edge read in isolation, with nothing to reconcile edges whose readings disagree. Generalized winding numbers [21] take an orthogonal path: inside/outside is a scalar field evaluated at any query point, tolerant of non-manifold input but indifferent to combinatorial topology. Trueform places the decision at topological-unit scope (§1): a component or relation that carries disagreeing observations is resolved by a majority vote within it, and domains inherit the result.

Sequences of booleans. A model is rarely one boolean: it is a CSG tree, or a family of queries against the same operands. The classical route evaluates the tree pairwise, materialising every intermediate: CGAL’s Nef polyhedra [22], [23] compose this way robustly at heavy cost, and OpenSCAD [24] inherits the pattern. BSP merging [25] composes trees rather than meshes, at the price of the splitting blow-up. QuickCSG [26] evaluates an \(N\)-ary expression in a single pass over the final arrangement, in floating point and explicitly outside degenerate configurations. EMBER [3] evaluates CSG trees inside its exact plane representation, never materialising an intermediate mesh; Manifold [27] evaluates operation trees lazily, keeping every intermediate as a manifold solid. Zhou [16] and Lévy [4] carry per-operand inclusion bits through one global arrangement, so a single expression needs no intermediates at all. Trueform takes the bit-vector route and splits build from query: the arrangement and its classification are computed once, and any expression over the operands — any arity, arbitrarily many expressions — is a per-domain bit test against the same build (Section 2.7); a sequence costs one arrangement, not one per operation. The three strata of Figure 9 are three such expressions read from one build.

Application context. Mesh CSG drives demanding workflows in geomodelling [28], [29], interactive mechanical modelling [30], and CSG for fabrication [31]. Geomodelling’s defining cut is by open horizon surfaces, yet mesh-boolean pipelines require solid operands — Zhou’s inputs are piecewise-constant winding-number meshes [16], Manifold’s are manifold solids [27] — so the workflow falls to dedicated trimming machinery [29]; trueform admits open surfaces as first-class boolean operands (Section 2.6). All these workflows share the same constraint from §1: CSG output is consumed by another stage in floating point, and that stage cannot tolerate topology drift.

1.2 Contributions↩︎

The method is one pipeline, but its contributions separate along four subtasks: the predicates that classify contact, the construction that arranges it, the classification that absorbs uncertainty, and the sequences of booleans one build answers.

1. Predicates: exact contact classification without perturbation. Pairwise intersections are classified into five canonical types (VV, VE, VF, EE, EF) by exact predicates on a single bounded integer kernel, before any point is constructed and without Simulation of Simplicity [5] (Section 2.1). Coincident vertices, on-edge points, and coplanar faces survive classification intact, and an optional tolerance band leaves the five-type partition invariant.

2. Construction: a locally computed arrangement with no global structure. Each cut face is arranged in its own 2D plane (Section 2.2, Figure 4), and a two-level identity scheme — a topological identity naming each point by the primitives that meet there, plus a geometric merge for distinct identities landing at one coordinate — keeps the arrangement consistent across faces without escalating precision. The radial order around every constructed intersection edge is decided by exact sign tests on the original input planes alone — the constructed edge lies in every incident plane, so no materialised coordinate enters the comparison, and two faces tie exactly when their planes truly coincide. The arrangement’s radial structure is exact without exact constructions — the guarantee Lévy obtains by escalating to exact homogeneous coordinates [4]. Every stage operates on graphs that are never explicitly constructed: flat arrays indexed by lookup, whose reduced graph carries the combinatorial content of Lévy’s Weiler 3-map [4], [17] with no half-edge structure to maintain (Section 2.3). The same path handles two meshes, \(N\) meshes, and polygon-soup self-arrangement, with non-manifold flaps, T-junctions, and isolated edges first-class.

3. Classification: uncertainty aggregated across topological units. Where a 3D decision spans faces — the orientation of a component, the nesting of one connected component inside another, the radial order at a non-manifold edge once the arrangement is consumed materialised or the input sheets are inconsistently wound — individual exact orient3d observations that should agree can disagree. Each is resolved within its topological unit by a weighted-majority vote, the maximum-a-posteriori estimate of the unit’s intended outcome (Section 2.4, Appendix 6). The resulting bitvector admits open surfaces as first-class operands, declared sheets (Section 2.6, Figure 9).

4. Sequences: one build, arbitrarily many booleans. Classification yields a domain partition carrying per-domain operand-inclusion bitvectors, so a boolean expression of any arity is a per-domain bit test (Section 2.7). The arrangement is paid once; a whole family of CSG queries — a tree, a sweep of parameters, an interactive session — reads from the same build (Figure [fig:teaser]).

The pipeline ships as a header-only C++ library with Python (nanobind) and TypeScript (WebAssembly) bindings (Section 3). The same exact kernel runs on x86, ARM, and in the browser at interactive speeds, and the codebase is freely available for academic and research use [32]. To our knowledge, no prior CSG library is interactive in the browser at these scales.

1.3 Algorithm overview↩︎

The pipeline is a single forward pass — arrangement, then topological aggregation, then output — built once and reused across CSG queries (Figure 3).

Arrangement. Stage one intersects every candidate face pair in parallel (Sections 2.1, 2.2). Each intersection point’s topological identity is the pair of input primitives that produced it (one of VV, VE, VF, EE, EF): same identity means same point by construction. A geometric merge additionally unifies distinct identities landing at the same coordinate. Each intersection edge is then defined by its two endpoint identities, independent of any containing face. Stage two computes each cut face’s 2D arrangement independently in its local plane. Every point created here is registered on the canonical intersection edges it lies on, and therefore on every face containing them. Identification proceeds at the same two levels. Topologically: stage-one identities carry through, and a new crossing is named by its face triple — the faces meeting there. Each face containing a crossing detects it locally through a different pair of canonical edges; the triple is the name those observations share. Where coplanar contact makes a triple ambiguous — one face pair meeting in several canonical edges — the canonical edge pair refines it (§2.2). Geometrically: distinct identities at the same parametric position on a shared canonical edge merge. The arrangement is topologically consistent across faces despite being computed locally on each, without escalating precision. Edge adjacency is built only for the new cut sub-faces; non-intersected original faces reuse the input mesh’s manifold-edge link directly. Together these form the implicit reduced graph that subsequent steps operate on.

Topological aggregation. When 3D decisions span faces, individual geometric observations of one intended fact may disagree — orientation and nesting read materialised intersection points; the radial order, exact in-build, is perturbed when re-read from materialised geometry or presented inconsistently by the input. Components aggregate orientation votes. Relations between components aggregate wedge-merge votes; union-find on the reduced graph then propagates those decisions into a domain partition. Domains inherit inside/outside from the relations’ seeds (Sections 2.4, 2.5). Both votes are weighted-majority over exact orient3d observations. Disagreeing observations within a unit are resolved by majority; ambiguous ones are skipped, with faces inheriting their unit’s label. Domains carrying no seeds fall back to exact SoS-perturbed segment-casting on the integer kernel.

Output. A boolean expression of any arity over the operands — closed volumes or declared sheets (Section 2.6) — selects domains by classification: each domain carries an inclusion bitvector, and selection evaluates the expression per domain. Selected uncut original faces pass through directly; selected cut sub-faces are Delaunay-triangulated into the output.

2 The algorithm↩︎

Everything below serves one invariant: combinatorics kept exact over coordinates that are merely grid-rounded. The kernel classifies contact before any point is constructed (§2.1), the arrangement names every point it does construct (§2.2), the implicit graphs carry those names into topological units (§2.3), and the votes over those units partition space into domains (§2.4).

2.1 Topologically exact predicates on convex polygons↩︎

The kernel is a bounded integer ladder over snapped coordinates. Input floats are mapped onto an integer grid. Predicate expressions promote width as needed: subtractions cost one bit (T0\(\to\)T1), products of differences double width (T1\(\times\)T1\(\to\)T2). The ladder closes after T2. Every predicate the pipeline uses — orient2d, orient3d, and the cross/dot work that feeds them — is a polynomial of total degree at most three. The library exposes two ladders, \(32{\to}64{\to}128\) and \(64{\to}128{\to}256\) bits; the user picks based on input precision and resolution. The kernel is the substrate; Attene’s indirect predicates [2] carry the same accounting via stored expressions, EMBER [3] via fixed-width 256-bit planes. Trueform works in between, with a fixed promotion ladder of exactly known widths and no dynamic allocation.

Five canonical configurations carry the local topology forward: vertex-vertex (VV), vertex-edge (VE), vertex-face (VF), edge-edge (EE), and edge-face (EF). Each emitted intersection is exactly one of these five, named by the simplex pair that produced it. The same kind of simplex-pair taxonomy lives in Lévy [4] as \((\sigma, \sigma')\) pairs over a triangle’s seven open simplices; trueform generalises to convex polygons.

Convex polygons are the input scope because they fan-triangulate trivially online from any vertex \(A_0\). There is no separate constrained Delaunay triangulation (CDT), no auxiliary index, no triangulation queue. The fan triangulation is what makes the rest of the section possible. Input polygons cannot be assumed to be in general position; three or more collinear vertices occur in practice. A fan triangle is the right unit of work. A non-degenerate triangle classifies cleanly via the zero-pattern below; a degenerate one (three collinear vertices) contributes nothing to that slice, and the loop advances. Non-convex face primitives are rare in mesh CSG inputs, so the convex scope captures the practical case at minimal cost.

The classifier evaluates three orient3d signs per fan triangle. For fan triangle \(t = (A_0, A_{t+1}, A_{t+2})\) and segment \((D, E)\), the signs are \[\begin{align} v_1 &= \mathrm{orient3d}(A_0, A_{t+1}, D, E),\\ v_2 &= \mathrm{orient3d}(A_{t+1}, A_{t+2}, D, E),\\ v_3 &= \mathrm{orient3d}(A_0, A_{t+2}, D, E). \end{align}\] The zero-pattern decides the type (Table 1). No zeros and a sign disagreement on the fan triangle: EF (the segment crosses the face’s interior). One zero on a real polygon edge: EE (the segment crosses a real edge at an interior point of both). Two zeros at a shared fan vertex: VE (the segment passes through a face vertex). Fan diagonals — the edges \(A_0 A_{t+1}\) for \(t > 0\) and \(A_0 A_{t+2}\) for \(t + 3 < n\) — are not real polygon edges. A zero on one of them is geometrically real but topologically a fan-interior point, classified as EF, never as EE. The real-edge predicate \((v_1 = 0 \land t = 0) \lor (v_2 = 0) \lor (v_3 = 0 \land t + 3 = n)\) is the only place the fan triangulation leaks structural information; the rest is rotation-symmetric.

Two complementary routines run over this decomposition. The first processes edges that strictly cross the opposing plane, emitting EF, EE, or VE from the fan zero-pattern above. The second processes on-plane primitives — any vertex whose plane-side sign is zero — and emits VV, coplanar VE, or coplanar EE. A third routine emits VF. The three are not mutually exclusive: for a pair where some vertices cross and some touch the plane, all three may fire. The partition into types is still exact — every real contact is emitted once, from one routine.

Degenerate polygons are not a special case. A chain of collinear vertices is a polygon that has shrunk to an edge. When the chain lies in the opposing plane, every vertex reads sign zero. The on-plane routine then catches all its contacts as the same VV/VE/EE primitives a real edge would produce. Convexity makes the geometry simple; the classifier makes the topology uniform. The five-type discipline preserves what SoS [5] discards; the classifier perturbs nothing.

Tolerance band.

Users often want to declare a tolerance length within which near-coincident features in the input should be classified as coincident. The kernel accepts this length, but the predicates do not operate in length: orient3d returns a volume, orient2d an area. Each predicate therefore derives its own band per call from the user’s length. The five-type partition is unchanged. The band is used only by the classifier: in stage one and in stage two’s segment-arrangement phase (Section 2.2). Region extraction and all subsequent stages run on exact predicates.

2.2 Two-stage local arrangement↩︎

The arrangement is computed in two stages. Stage one intersects every candidate face pair in parallel, emitting tagged intersection records keyed by simplex pair on each face. Stage two arranges each cut face’s records independently in its local 2D plane. Both stages follow the same two-level identification pattern (§1.3): a topological identity that establishes same-point-by-construction, plus a geometric merge that additionally unifies distinct identities landing at the same coordinate. The implementation exposes the arrangement either over a collection of meshes or over a polygon soup; the algorithm is the same, only the candidate set differs.

Stage one — pairwise intersection records↩︎

Candidate face pairs come from a parallel AABB-tree descent — dual across two trees for the multi-mesh case, self over a single tree for polygon soup. Each surviving pair invokes the predicates of Section 2.1. The output is a flat tuple per intersection: which mesh, which polygon, which polygon on the other side, the simplex pair on each, the point identity. No edges, no per-face geometry yet — just identities.

The stream is globally unique without any dedup pass. Two mechanisms ensure this. Within a pair, the decision tree of Section 2.1 fires exactly one type per real contact — no overlapping sub-simplex queries like Lévy’s [4], which require a sort + unique pass. Across pairs, each vertex and edge of a mesh has one designated owner face, picked up front from the face-membership list and the manifold-edge link. During traversal, only the owner emits records for that primitive; the other faces that share it skip it. Together the two mechanisms keep every contact recorded exactly once, regardless of how many adjacent faces share the primitive.

Construction is decoupled from classification. VV, VE, and VF reuse input-vertex identities directly. Only EE and EF compute a new point, via barycentric-weighted div_round on the integer endpoints. The point is a grid integer, but a rounded one. div_round snaps the true intersection to the nearest T2 cell: exact as a grid coordinate, inexact as a point. Its topological identity is exact regardless — the pair of input primitives that produced it, (edge, edge) for EE, (edge, face) for EF, a global key independent of where it was computed.

A parallel sort by key \((\text{tag}, \text{polygon}, \text{tag}', \text{polygon}')\) groups records. Offset-blocks on the prefix \((\text{tag}, \text{polygon})\) place every record in a contiguous slice belonging to one face. Stage two runs over these slices in parallel.

Stage two — per-face planar arrangement↩︎

Per-face processing has three phases: segment extraction, segment arrangements, and region extraction. The first two build a per-face segment graph; the third walks regions out of it.

All work happens in the local 2D plane of each face. Every intersection point — stage-one outputs and the new crossings stage two produces — carries a canonical identity and a 2D copy in each face that contains it. These per-face 2D copies let per-face arithmetic stay exact: coplanarity holds within each plane by construction, and the integer planar predicates of §2.1 apply without further constraint.

Segment extraction.

Extraction proceeds in two passes. The first inserts the face’s intersection points into its base loop, ordered around the perimeter. The result is the cut base loop. The second walks the face’s slice. The stage-one sort ordered records by \((\text{tag}, \text{polygon}, \text{tag}', \text{polygon}')\), so records sharing a cross-face context are already contiguous — the grouping is the linear sequence itself. Each run classifies in \(O(1)\) from its size: one record means no edge; two, a single intersection edge; three or more, a closed coplanar polygon-of-contact, which is a contiguous subset of the other polygon’s cut base loop. The subset is traced linearly through the triplet identities of its points; no geometric check is needed. Each intersection edge has a canonical identity given by its two endpoint identities. The same canonical edge appears in every face that contains it; updates to the edge propagate to all containing faces by lookup.

Segment arrangements.

A per-face planar arrangement resolves crossings among the extracted segments. Each crossing produces a new intersection point, and its identity must be the same on every face that sees it. A crossing where three faces meet is detected independently on each of them: face \(A\) as a crossing of \((e_{AB}, e_{AC})\), face \(B\) as \((e_{AB}, e_{BC})\), face \(C\) as \((e_{AC}, e_{BC})\). No pair of canonical edges is shared by all three observations; the face triple is, and it names the junction identically from every face (Figure 4). The triple fails in exactly one configuration: coplanar contact. There a single face pair meets in several canonical edges — the boundary of its polygon-of-contact — and one triple then spans several distinct crossings: an edge transversal to the contact crosses several contact edges at distinct points, all carrying the same triple. The ambiguity is recognised topologically, with no geometry consulted: extraction knows which edges it emitted from a polygon-of-contact, and a triple whose crossings involve two or more distinct contact edges is refined by the canonical edge pair, which keeps the pack’s crossings distinct. Both decisions are scoped to the triple and all its observations, so every face keys a given crossing identically.

Faces with fewer than 32 segments run a quadratic crossing check; larger faces build a segment tree and find crossings in \(O(n \log n)\). Each new crossing is classified by three types (VV, VE, EE), the 2D restriction of the five-type discipline of stage one. Topological exactness of the three types ensures point and segment uniqueness: coincident endpoints — points landing on the same integer-grid cell — collapse into a single point as VV, and overlapping segments collapse into one canonical segment. The records on any single face are typically a handful, occasionally a few dozen — bounded by the local cut geometry — so \(n\) is small. What scales in real workloads is the number of cut faces, parallelised across threads. The strategy is deliberate: keep the heavy algorithmic step inside a small per-face set, and ride throughput on face-level parallelism rather than per-face triangulation.

Identity stays globally consistent through a canonicalisation step — stage two’s geometric merge level — that sorts every edge instance by canonical endpoint pair and groups all per-face copies of the same intersection edge into a single offset block. This is the reverse map from canonical edges to containing faces, built by structure alone. Each canonical intersection edge is then processed once, in parallel across blocks, to absorb the crossings naming it: crossings are sorted by parametric position \(t\) along the segment, the segment is split into sub-segments at the sorted positions, and two crossings landing at the same \(t\) merge into a single point by the same VV mechanism. The split rebuilds the shared buffer in place; every face’s slice then sees the new sub-segments by lookup. Point identities are remapped in a single parallel pass over the buffer, so the next phase sees a globally consistent segment graph on every face. Cross-face consistency follows from identity, not from coordinate comparison: any point created on any face propagates to every face containing its canonical edge.

Region extraction.

With the segment graph in place, regions of the cut face follow from a path classification. Segments form paths in the graph. A path is a crossing when both endpoints sit on the cut base loop. It is non-crossing when its terminus is an internal junction of degree three or more — a condition that arises only at points where three or more faces meet, or at non-manifold edge junctions. The majority of faces produce only crossing paths.

Region extraction dispatches on this distinction. When every path is a crossing, regions are extracted in linear time by dividing the cut base loop at each crossing into sub-loops. The trivial common case — a single crossing edge — yields two sub-loops with no predicate work at all. When non-crossing paths are present, an exact planar walk runs on the full edge set: half-edges at each vertex are placed in radial order by an exact orient2d comparator, and the regions are walked.

Closed paths and dangling cut paths are patched into the regions that contain them by an exact point-in-region test. The output of stage two is the set of sub-loops belonging to each cut face.

2.3 Implicit graph structures↩︎

Every stage of the pipeline is a graph problem on graphs that are never explicitly constructed; the next three subsections define the implicit graph that the domain partition and classification operate on (Section 2.4).

Two implementation primitives appear throughout: connected-component labelling and a dense equivalence-class mapping that replaces pointer-based union-find. Below we use “union-find” generically for the latter; their low-level implementations are not material to the CSG algorithm.¹

The reduced graph: components as nodes↩︎

The domain partition and classification (Section 2.4) operate on connected components of the manifold-edge link (MEL components) of the full arrangement. Running an MEL flood-fill directly on the whole arrangement would work but throw away the structure already built — uncut faces inherit the input mesh’s manifold-edge link, and cut sub-loops carry the per-face cut graph from stage two of the arrangement (Section 2.2). We compute on the two sets separately and join.

Non-intersected MEL components flood-fill through the input manifold-edge link with intersected faces masked out. Intersected MEL components flood-fill through the per-face cut graph, in which coincident sub-loops from coplanar contacts are collapsed to a single face. The collapse means coplanar overlaps end up in one intersected component automatically. A union-find then joins the two sets across the cut/uncut interface: each cut sub-loop edge on the original face boundary contributes a pair with its uncut neighbour through the input manifold-edge link, and the dense equivalence-class map collapses the pairs. The result is the MEL components of the full arrangement. Components are not instantiated as explicit data structures: we keep two label arrays — one over original faces, one over cut sub-loops — each entry holding its MEL-component id, queried by lookup.

The reduced graph has these MEL components as nodes. Edges between nodes are the non-manifold edges shared by their faces in the arrangement — the relations of the next subsection. Within each component the winding is consistent: coherent by construction where no coplanar pack was collapsed, and where one was — collapsing it keeps a single loop with arbitrary winding — the component is re-oriented to the area-weighted majority of its faces, the orientation vote of Section 2.4. The per-face side map (stored-orientation side, reversed side) is then globally coherent.

Component relations and the radial permutation↩︎

Around the directed axis of a non-manifold edge \(e\), the incident faces have a well-defined cyclic order; listing them in this order yields a cyclic sequence \(\rho_e\) of MEL-component labels, computed by exact sign predicates on the integer kernel (Section 2.1). The choice of axis direction is arbitrary, and reversing it reverses \(\rho_e\). The non-manifold edges of an arrangement form polylines under shared-vertex adjacency — maximal chains whose internal vertices have non-manifold-edge degree two. The canonical permutation of \(e\) is the unique linear realisation of \(\rho_e\): (i) inherit the axis direction from \(e\)’s polyline traversal, so every edge of one polyline reads its \(\rho_e\) from the same side; (ii) start at the smallest label. The first step fixes the axis, the second the rotation.

Every angular comparison is an exact sign test on the original input planes alone. The intersection edge lies in every incident original plane, so each incident face’s wedge direction is exactly perpendicular to the fan’s carrier line; comparing two wedges reduces to signs of degree-two products of original plane coefficients, and no constructed coordinate enters the comparison. Two wedges tie precisely when their original planes coincide — exactly the coplanarity the contact classification has already decided (Section 2.1) — so materialisation can neither create nor destroy an ordering: within the build, \(\rho_e\) is exact. The per-apex perturbations of Figure 1 — a near-coplanar pair swapping, a near-axial apex flipping — arise only when the order is read back from materialised geometry, as when an arrangement is consumed as a mesh (§3). The materialised endpoints are consulted in exactly one place: a single sign aligning the ring’s direction with the stored edge. A wrong sign mirrors the ring; cyclic adjacency is preserved, the canonical-permutation equivalence below is order-blind, and the per-polyline alignment keeps the choice consistent, so the merging vote (Section 2.4) absorbs it.

Two canonical permutations are equivalent when they sort to the same sequence — deliberately order-blind: equivalence only groups observations of the same relation; the merging vote settles their order. A fan containing a degenerate incident face — one whose original vertices admit no plane — cannot be ordered and is flagged invalid whole: it contributes no observation to the merging vote (Section 2.4), and the components it touches participate through the relation’s other non-manifold edges. The same guard rejects fans whose member planes do not all contain one line, as when snapping merges two distinct intersection edges.

A relation between components is an equivalence class of non-manifold edges sharing both a polyline and a set of incident components. Within a relation, multiple canonical radial permutations may be observed; the merging vote of Section 2.4 aggregates these disagreeing observations into a single intended permutation. Lévy organises the radial structure as a radial polyline [4] and runs one radial sort per chain. This is correct on closed-manifold input, where a polyline carries one relation by construction. Non-manifold flaps — open MEL components attached partway along a polyline — raise the incident-component set on the edges they meet without breaking the chain: the polyline still walks as one structure but now carries two relations, one per distinct incident-component set. Our framing handles both cases uniformly: every (polyline, component-set) pair is a relation with its own vote. Even when the chain carries a single relation, the vote remains a distribution over canonical radial permutations rather than one sort, so an edge whose reading is disturbed — a materialised re-reading, a mirrored direction sign, an inconsistently wound input sheet — is absorbed by the majority.

Computing the equivalence classes. Non-manifold edges are grouped into polylines by a single union-find on shared endpoints, with edge axes aligned to the polyline’s traversal direction so that canonical radial permutations are well-defined within the polyline. For each non-manifold edge we store two contiguous blocks: the incident face IDs in canonical-permutation order, and the corresponding MEL-component labels in sorted form. These form two flat arrays of total incident-face length, indexed by offsets over the non-manifold edges. An argsort over the key (polyline id, sorted incident-component set) then groups non-manifold edges into contiguous relations; a polyline carrying multiple distinct component sets contributes one relation per set.

In applications like geomodelling, an arrangement mixes closed primitives (volumes, intrusions) with partial cuts, fault surfaces, and probe geometry. Open patches sometimes form valid domain separators (a fault that fully cuts the model) and sometimes are intrusion artefacts: a half-inserted patch sits inside an otherwise closed body without splitting it, leaving a non-manifold fin in the domain’s boundary. The application chooses the policy.

An open MEL component, one carrying a boundary edge, does not separate two volumes: its two sides are the same region, joined around the boundary, so we always fuse them into one domain (\(d_0 = d_1\)) via the merge pairs of Section 2.4. A fin never splits the region it sits in. The modes differ only in whether the fused component is then kept or discarded. Mode 2, the default, keeps it: the intrusion’s interior stays a single non-manifold domain with the fin as part of its boundary (Figure 6). Mode 1 discards it: the open component’s faces are dropped from the radial votes and all open components collapse into one outer domain, so an intrusion with a half-inserted patch returns to a single closed manifold domain with the fin gone.²

Equivalence to the Weiler 3-map↩︎

The Weiler 3-map [4], [17], in the language of combinatorial maps [18], stores three per-dart links over a duplicated triangle set: \(\sigma_1\) within a triangle, \(\alpha_2\) across an edge within the same sheet, \(\alpha_3\) across the same edge in the twin sheet. We carry the same content without storage: \(\sigma_1\) in each face’s vertex order, \(\alpha_2\) in the manifold-edge link and cut graph (Sections 2.1, 2.2), \(\alpha_3\) as the cyclic adjacency at each non-manifold edge derived from its canonical permutation. The orbits map one-to-one onto our structures: \(\langle\sigma_1, \alpha_2\rangle\), Lévy’s shell, is our MEL component; \(\langle\alpha_2, \alpha_3\rangle\), Lévy’s bundle, is our wedge ring around a non-manifold edge — wedge rings sharing a polyline and incident-component set form a relation; and \(\langle\sigma_1, \alpha_2, \alpha_3\rangle\), Lévy’s connected component, is our connected component, generated by our merge pairs (§2.5).

2.4 Domain partition↩︎

Each relation is observed once per non-manifold edge, and the observations can disagree: within the build only through the aligned direction sign or input sheets inconsistently wound (Section 2.3); read back from a materialised arrangement, through every rounded coordinate — and any materialisation downstream only widens the spread. Prior pipelines handle it implicitly — Lévy by raising precision until it vanishes, per-edge methods by trusting one reading [4], [20]; we make the per-unit majority the explicit rule — topological aggregation — which Appendix 6 casts as maximum-a-posteriori estimation. The pipeline of Section 2.3 groups non-manifold edges into relations by (polyline, incident-component set), and within each relation collects the canonical radial permutations observed on its edges (Figure 5). Each relation votes its canonical radial permutation (Figure 7) and emits merge pairs over fragment-sides, each a \((\text{component id}, \text{side bit})\) pair whose side bit selects a component’s stored-orientation side or its reverse. A dense equivalence-class map consumes the merge buffer, assigning one domain id per fragment-side. The final per-face per-side labels follow by lookup in one parallel pass: \(\text{labels}[f][s] = \text{domain\_of}[2c + s]\) for face \(f\) in MEL component \(c\). The whole pipeline operates on the reduced graph (buffers proportional to the number of MEL components), not on per-face data.

The relation-merge vote↩︎

Distribution. Offsets over the argsort of Section 2.3 demarcate each relation as a parallel slice. Within each slice we sort by canonical radial permutation and count runs of identical permutation. The run lengths form the distribution of canonical radial permutations within the relation.

Vote. The relation’s canonical permutation is the longest run — the majority. One linear walk per slice tracks the longest run seen so far and its representative non-manifold edge (Algorithm [alg:vote]). Figure 7 illustrates the vote on a polyline whose edges fall into two relations. The reduction extends to weights with no structural change. Each observation’s weight is the minimum area of the faces incident to its non-manifold edge. Near-degenerate slivers (Figure 1, \(T_4\) flip) contribute less.

Merge pairs. The voted permutation’s representative edge emits merge pairs once for the entire relation: in a consistent configuration every edge in the relation would emit identical pairs, so the representative suffices. At every pair of cyclic-adjacent positions in the voted permutation, the two fragment-sides bounding the wedge between them are joined into one pair. Mode-2 MEL components carrying boundary edges (Section 2.3) contribute one extra pair \((c, 0) \leftrightarrow (c, 1)\).

For a single connected component this partition is final. Geometrically disjoint connected components, and the operand inclusion a boolean selects on, are taken up in classification (Section 2.5).

2.5 Classification↩︎

The domain partition (Section 2.4) tells each face-side which region it bounds. CSG asks a different question of the same partition: not which region a face bounds, but whether a boolean expression selects it. The answer is one operand-inclusion bitvector per domain, \(b(d) \in \{0,1\}^N\), with bit \(i\) set iff domain \(d\) lies inside operand \(i\). Crossing a surface toggles membership in exactly the operands that surface carries, and the boolean reads the result. Inclusion bitvectors as labels go back to Lévy [4], who seeds them with a ray per connected component; we read the seeds off the votes of Section 2.4 instead, leaving a single geometric test for the cross-component nesting below, a closed connected component nested inside another with no surface contact.

The inclusion potential. Crossing one MEL component \(c\) between its two incident domains toggles membership in the operands whose surface \(c\) carries: \(b(d') = b(d) \oplus B(c)\), where \(B(c)\) is the OR of \(c\)’s own operand bit and any coplanar duplicate folded into it (Section 2.3). Inclusion is therefore a potential on the domain-adjacency graph: known increments \(B(c)\) on every edge, fixed once anchors pin the absolute values.

Local seeds carry the aggregation. At each wedge the interior side of a component’s loop lies inside that component’s operand, so the interior-side domain \(\text{domain\_of}[2c+1]\) takes the bit directly; a coplanar duplicate sets the side its winding selects. The wedge that places this bit is read off the voted radial permutation of Section 2.4 (Figure 7). Because that permutation is the relation’s majority vote over its (possibly disagreeing) per-edge observations, the seed already carries the aggregated answer: the uncertainty is absorbed where the seed is set, not repaired afterward. This fixes every domain reachable by surface contact, the whole partition for a single connected component, with no ray and no per-component seeding pass.

Anchoring across connected components. The wedge seeds reach only within a connected component, the equivalence class of MEL components joined by shared non-manifold edges; they say nothing about how one connected component sits inside another with no surface contact between them (Lévy’s “internal-boundary” [4]; Figure 8). Per-domain signed volumes follow by scatter from per-component integer-exact contributions, and each connected component’s outer-environment domain is its most-negative-volume incident domain. The connected component whose outer-environment is the most negative of all cannot be contained in anything, so that domain anchors at \(b = \mathbf{0}\), inside nothing, with no ray. Every other connected component’s outer-environment may lie inside some operands. We cast an SoS-perturbed segment from any vertex of the connected component to a fixed far point past the global bounding box; SoS here decides no topology, only steering the ray clear of grazing contacts without changing the crossing parity. The cast runs only against operands whose bounding box overlaps the connected component’s: an operand that cannot enclose it contributes no crossings and is skipped before any ray. The parity of the crossings against the rest, per operand, fixes the outer-environment’s bitvector. Open patches not declared sheets (Section 2.6) are transparent to the cast: the front and back of such an open component are fused into one domain (Section 2.4, \(d_0 = d_1\)), so a ray crossing a fin flips no parity, with no geometric test needed. The cast crosses every enclosing domain in one pass, so an outer connected component with several interior domains, such as a cube split by an internal plane, is resolved in that pass.

The flood. A single connected component is already fully seeded; with disjoint connected components a multi-source XOR-BFS carries each ray-anchored outer-environment inward, every unvisited domain taking \(b(d') = b(d) \oplus B(c)\) from a fixed neighbour across component \(c\). One pass over the domain adjacencies leaves every domain’s inclusion bitvector exact.

2.6 Open operands: sheets↩︎

A volume operand’s bit means inside. An open surface has no inside, but it has sides: an operand declared a sheet is an oriented separator whose bit means behind its normal. Nothing downstream changes — domains carry the same bitvectors and expressions evaluate unchanged — so intersection against a sheet keeps what lies behind it, difference keeps what lies in front, and the result is capped by the sheet faces it crosses (Figure 9). A clean closed mesh declared a sheet behaves identically to the volume it bounds: behind its outward normals is its inside, so the two readings coincide and the semantics strictly generalise.

Three local rules implement this. A sheet is exempt from the open-patch fusion: where an ordinary open component’s two sides merge into one domain (Section 2.4), a sheet’s sides stay distinct, so its fragments always separate their neighbourhood. Its bit is anchored, per region of the sheet, to the side behind its normal. And a connected component the sheet never touches — a floater above or below a horizon — takes its side from the sign of the sheet’s generalized winding number [21] evaluated at the component: the crossing-parity cast of Section 2.5 is meaningless against a surface a path can walk around, but the sign of the summed solid angle is not. The generality costs nothing measurable: on the \(1000\) corpus pairs (§4.3) run with one operand declared a sheet, outputs are identical and build times agree within \(2\%\) (untabulated).

2.7 Selection and output↩︎

The inclusion bitvectors are the per-domain truth the arrangement was built to produce. A boolean expression reads them; the result is the boundary between selected and unselected domains.

Evaluating the expression. The expression is an arbitrary tree of merge (union), intersection, difference, and complement over operand leaves, of any arity. It selects each domain by one evaluation against that domain’s bitvector, \(\text{in}(d) = E(b(d))\). Compiling the tree collapses every chain of like-kind leaves into a single per-word mask: a union or intersection of \(k\) operands becomes one masked compare per occupied word of the bitvector, not \(k\) leaf tests, so cost scales with the number of occupied words rather than with operand count. Each expression is then a single linear pass over the domains.

Output. A face lies on the result boundary when its two sides fall in different selection classes, and it is emitted oriented from the selected side outward. Selected uncut original faces pass through unchanged; selected cut sub-faces are Delaunay-triangulated. The output coordinates materialise to IEEE double here.

Volumetric regions. If only the regions are wanted, not a boolean over them, the same partition yields them directly: reading the cross-component nesting as a merge rather than a seed collapses each inner connected component’s outer-environment into its container, and the domains become volumetric regions. This skips the inclusion flood and the expression entirely. One construction serves both reads.

3 Implementation↩︎

The pipeline is part of trueform [32], a header-only C++17 geometry library. tf::make_csg_graph builds the arrangement once into a reusable graph that holds the domain partition and the per-domain inclusion bitvectors (Sections 2.4, 2.5); each boolean expression is then one tf::make_csg_mesh call — a per-domain evaluation and a boundary extraction (Section 2.7) — or one tf::make_csg_domains call for its volumetric domains, so a family of such queries over the same operands shares a single arrangement. Trueform runs in one of two precision modes, chosen from the input coordinate type (Table 2): float input uses the int32 kernel, with exact predicates in \(128\)-bit arithmetic, and double the int64 kernel, exact in \(256\)-bit. The wider kernel is forced on float input with tf::make_csg_graph<tf::exact::int64>. The output coordinate type is the input’s by default and is set per query: tf::make_csg_mesh<double> materialises to double, while an integer output returns the kernel’s integer-grid coordinates directly, with no floating-point round-trip.

The pipeline is also exposed as separable stages. tf::make_mesh_arrangements materialises the arrangement: the co-refined, intersection-tagged mesh on floating-point coordinates, or the intersection curves alone. tf::make_domain_labels then partitions any such arrangement into per-face per-side domains, and tf::split_into_domains emits the per-domain meshes. This labeller still evaluates exact predicates internally. The difference is that materialisation has already happened upstream, so the predicates read materialised coordinates rather than building from exact ones. It also takes a bare arrangement with no provenance, so it cannot reach back to the original planes of Section 2.3 and relies on the relation vote alone. The vote already absorbs disagreement (Section 2.4), so the partition stays correct on such input. This is what makes the float entry point viable, and lets a caller who already holds an arrangement recover its domains without adopting our arithmetic. The library exposes the pipeline through idiomatic bindings in two further languages: in Python meshes are NumPy arrays, and in TypeScript operations are asynchronous calls over a WebAssembly runtime that runs in the browser and in Node.js. The browser runtime backs Lunar³, an in-browser mesh editor that surfaces booleans, arrangements, and the rest of trueform as interactive UI, with all computation running client-side in the WebAssembly build.

Examples. Both the C++ and Python distributions ship interactive examples built on VTK, runnable on the reader’s own meshes: one operand is dragged through another while the boolean is re-evaluated each frame and a rolling average reports the per-operation time. The C++ examples are in vtk/examples/ (among them boolean.cpp) and the Python ones in python/examples/vtk/ (boolean_difference.py) — the desktop counterpart of the browser demo of Section 4.2.

4 Results↩︎

We evaluate three properties in turn: the robustness of the relation vote that underwrites correctness (Section 4.1), performance as the operand count grows and the build/extract split that amortises a family of booleans (Section 4.2), and comparison against prior art (Section 4.3).

4.1 Robustness of the relation vote↩︎

The pipeline’s correctness rests on one decision: a relation aggregates the radial observations of all its non-manifold edges into a single voted permutation (Section 2.4), rather than trusting any edge alone. In the intended geometry the radial order is constant along a non-manifold polyline, so each edge is one noisy reading of a single shared order — an observation we share with Lévy [4], whose pipeline sorts once per polyline on the strength of it. The radial sort is common to all three approaches; they differ in how they treat the uncertainty in it. Böhm and Runge [20] take one reading and assume it exact: correct when it is, as on the given meshes their domain extraction targets, with nothing to fall back on when it is not. Lévy eliminates the uncertainty — exact homogeneous-coordinate constructions make every reading agree, so one sort is provably right — but needs exact provenance to redo the arithmetic, which a materialised or composed arrangement no longer carries, and pays the precision-escalation cost. We do both, each where it is cheap: within the build the sort is decided on the original input planes and is exact without exact constructions (Section 2.3); beyond the build — an arrangement already materialised, a composed pipeline, input sheets inconsistently wound — the majority over the polyline’s many readings recovers the shared order with no exact provenance to lean on. The vote is the per-edge sort generalised — when the readings are unanimous it returns the permutation a single edge would, and it degrades gracefully only as they disagree. We measure it against per-edge on the materialised reading, where construction alone already disagrees — from a controlled two-sphere probe through a real geomodelling workflow to the Thingi10K corpus — and under the error a composition injects.

What we measure. A relation is partitioned correctly when its extracted merges match the consistent (intended) partition. The baseline, per-edge, is the vote with its aggregation removed — the same pipeline reading the merges off each edge’s own radial sort, the zero-uncertainty case of Böhm and Runge [20]. It requires every edge of the relation to agree; the vote requires only the majority. Per-edge therefore mispartitions a relation precisely when its edges’ sorts disagree. Within the build the sorts cannot disagree (Section 2.3); the measurements that follow read the arrangement the way any consumer of its output must — from materialised coordinates — where construction alone causes disagreement even before any perturbation.

A controlled probe. The mechanism is visible on the simplest geometry there is: two UV spheres of unit radius, one offset by \(d\) along the pole axis, arranged as \(d\) is swept (Figure 11). Their intersection is a single circle. At most offsets every reading agrees, but where the circle grazes a latitude vertex ring — near \(d = 2\cos(\pi k/32)\) — the constructions on different edges of the circle round to different radial orders: reading the order from the materialised, snap-rounded geometry splits the relation’s edges at \(54\) of \(191\) offsets, construction alone, before any perturbation. Per-edge mispartitions the circle at every one of them; the vote, taking the majority, is correct at all \(191\). Ordering from the original planes splits none — the failures are not in the arrangement but in its materialised reading. Nothing here is degenerate by design: two clean, convex, watertight spheres, and the materialised reading still disagrees at more than a quarter of all offsets — the faces whose radial sort flips are full near-coplanar triangles, not slivers a quality filter could remove.

Native failures on real geometry. The same failure appears unprompted in practice, at \(\varepsilon = 0\) with nothing injected. The geological arrangement (Figure 10) — eleven geomodelling surfaces sharing a bounding box and grazing one another, dense with coplanar contacts — splits four of its \(220\) relations under native materialisation alone, with overwhelming majorities (\(9{:}1\) up to \(267{:}2\)); per-edge misses them, the vote recovers all (Table 3). On the Thingi10K dataset [33] — the standard corpus of real, self-intersecting 3D-printing models — self-arranging each of \(59\) models splits \(178\) of their \(704\) relations, across \(25\) of the \(59\); per-edge mispartitions every one, the vote none. This is not an artefact of double precision: materialising onto an integer grid instead of to double splits the geological relations the same way — the disagreement follows materialisation itself, whatever the target representation. Per-edge fails on real data the moment the arrangement is read from its coordinates; the vote does not.

Under perturbation. Native failure is the floor; any composition adds more. An arrangement materialised to floating point, remeshed, and re-extracted accumulates construction error with no exact provenance to recover (Section 3); once the arrangement exists only as coordinates, the radial order is the one cross-face decision a construction’s rounding can reach (Section 2.3). We model the round-trip by perturbing the materialised non-manifold-edge endpoints by a uniform box of half-width \(\varepsilon\), relative to the bounding box, redrawn over \(1000\) trials, and re-running the sort — single-precision rounding sits near \(10^{-7}\) of that scale, double near \(10^{-16}\). We sweep \(\varepsilon\) over twenty-two configurations spanning fifteen standard meshes (CAD, organic, and scanned), each arranged against a \(30^\circ\)-rotated copy and, for seven, as dense random-rotation clusters. At \(\varepsilon = 0\) the pairs tie: on generic transversal contact the vote invents no false splits; it is never worse than per-edge. Under added error every configuration behaves the same way (Figure 12): per-edge collapses to nothing by \(\varepsilon \approx 10^{-3}\), at a model-dependent rate, while the vote stays correct on \(78\) to \(100\%\) of relations there — two to three orders of magnitude more construction error before the partition breaks, on every model. The advantage tracks construction error, not the model.

Composition after materialisation. This margin is what lets operations chain: the materialised entry points of Section 3 hand the labeller an arrangement stripped of its exact history, and the vote alone keeps its partition correct — the regime Lévy’s exact constructions cannot enter.

4.2 Performance↩︎

The pipeline builds one arrangement and answers a whole family of booleans from it (Section 2.7). We measure both halves — the build, which scales with the input, and the per-expression extraction, which does not — in two ways. A broad random sample of arbitrary \(N\)-ary unions isolates how the build scales with operand count. A controlled swarm of Stanford bunnies then exposes the amortisation, where one build answers a whole family of booleans. All timings are on an Apple M4 Max (\(12\) performance and \(4\) efficiency cores, arm64, \(64\) GB), multi-threaded over TBB. We report the minimum over repeated runs of each deterministic case. The minimum strips operating-system scheduling noise, which only ever inflates a run.

Scaling with operand count. How does the build scale as operands multiply, apart from raw geometry? To answer without bias, we generalise the EMBER protocol [3] to \(N\) operands. EMBER benchmarks a boolean by drawing random Thingi10K meshes, normalising each to unit size, and placing them with overlapping bounding boxes. We do the same, but with \(N\) operands rather than two. Crucially, each configuration draws its operand count and its total triangle budget independently, sampling operands from a size-diverse pool of \(369\) meshes (\(1\) k–\(1\) M triangles each). Decoupling count from size fills the (operands, total-triangles) plane, where equal-size operands would trace only a single diagonal. Figure 13 plots the build time of \(1989\) such unions against total input triangles, each point coloured by its operand count \(N\). Triangle count alone is a weak predictor: it accounts for only \(27\%\) of the variance in build time. Operand count is what orders the cloud. At every fixed total the points fan out and stratify by \(N\), the \(N{=}2\) configurations tracing a clean geometry floor along the bottom. The dependence on operand count is sub-linear: at a fixed \(\approx\!1\) M-triangle budget, raising the operand count from \(2\) to \(128\) — a \(64\)-fold increase — lifts the build only about \(10\)-fold. The per-domain build cost stays flat to mildly falling, from \(\approx\!380\) to \(\approx\!115\) \(\mu\)s per domain across \(N{=}2\to128\). The machinery does not degrade with arity. The build grows only because there are more domains, each of which stays cheap.

Amortising a family of booleans. The broad sample varies the operands. The swarm instead fixes them and varies the query, exposing the build/extract split. We place \(N\) scaled Stanford bunnies on a Fibonacci lattice over a sphere (the swarm of Figure [fig:teaser], right), taking the sphere as operand \(0\). This gives \(N{+}1\) operands and \(\approx\!112\text{k}\,N\) input triangles, with \(N\) ranging over fourteen values from \(25\) to \(500\) (\(2.8\) M to \(56\) M triangles). One arrangement is built over all operands, and a fixed family of five extractions is read from it (Table 4). The build scales with the input, from \(78\) ms at \(N{=}25\) to \(1.68\) s at \(N{=}500\), at \(33\) to \(44\) million triangles per second. The AABB-tree broadphase holds the in-principle-quadratic pairwise intersection sub-quadratic in practice. Pairwise intersection dominates the build throughout (\(52\)–\(59\%\)), and only classification grows with the domain count, from \(7\%\) to \(23\%\) (Figure 15). Each extraction then reads the per-domain inclusion bitvectors and walks the boundary between selected and unselected domains. Its cost follows the output size, not the operand count. It ranges from \(2\) to \(45\) ms for the sphere only surface up to \(5\) to \(132\) ms for the full union, \(13\) to \(37\times\) below the build at every \(N\) (Figure 14). A set of \(k\) expressions therefore costs \(\text{build} + k\,\text{extract}\) rather than \(k\,(\text{build} + \text{extract})\), the arrangement and its bitvectors built once and reused. Peak memory is linear in the input, \(0.21\) to \(1.3\) GB, also paid once and shared across extractions.

Volumetric domains. The same build answers a different read entirely — volumetric regions rather than a boolean (Section 2.7). The cellular fracture of Figure [fig:teaser] (left) — a Stanford bunny against \(60\) axis-aligned cutting planes, \(112\)k input triangles — is arranged and partitioned into its \(8665\) bounded domains in \(59\) ms (arrangement \(25\) ms, cleanup \(6\) ms, domain labelling \(28\) ms); the \(3459\) cells interior to the bunny are then read straight from the partition, with no boolean and no per-cell work. This figure is produced by a repository example csg_fracture.cpp [32].

Interactive in the browser. The WebAssembly build runs the same pipeline client-side in the browser. A live demo⁴ differences a Stanford dragon against a sphere, \(\approx\!550\)k triangles, re-evaluating the boolean every frame as the sphere is dragged through the dragon. Each frame rebuilds the arrangement and re-extracts the difference in \(12\) ms on an M4 Max, on desktop and mobile alike.

4.3 Comparison with prior art↩︎

We measure performance against representatives spanning the prior approaches: Geogram [4], [34] (exact predicates and constructions), EMBER [3] (exact constructions via octree-embedded BSP, specialised for iterated CSG; implementation [35]), CGAL [7] corefinement [36] (exact predicates, inexact constructions), the mesh-arrangement booleans of Cherchi et al. [19] (exact via indirect predicates; implementation [37]), MeshLib [38] (Simulation of Simplicity for degeneracy handling; proprietary core), and Manifold [27] (deterministic floating point, degeneracies resolved by symbolic perturbation on exact equality); for the in-browser comparison we run our own and Manifold’s WebAssembly builds and add three-bvh-csg [39], the CSG evaluator for three.js. We compare on three fronts: a single pairwise boolean (Section 4.3.1), \(N\)-ary and iterated booleans (Section 4.3.2), and the same operations run client-side in the browser (Section 4.3.3).

Scope. The baselines all compute booleans only between closed, manifold solids: each operand must bound a volume. The comparison is therefore confined to that case — the booleans every library supports. The remainder of our pipeline — domain extraction against open surfaces, arrangements of triangle soup, \(N\)-mesh cuts, embedded curves on non-manifold input — has no counterpart to compare against and is demonstrated in Sections 4.1–4.2; we restrict the head-to-head to the operations the prior art is built for, and report them on the same machine and inputs for all libraries.

Protocol. Each method receives, for every operand, a vertex-coordinate array (float triples) and a triangle-index array (integer triples) — the form its own import entry point accepts — and is timed until it returns the result as that same pair of arrays. Everything between is inside the timer: import, the construction of whatever spatial and topological structures the algorithm uses, the boolean, classification, and the emission of the result’s coordinate and index arrays — the result first exists only inside the library’s own representation, and emitting it to arrays is part of the measured work. Only file I/O — parsing the OBJ into the input arrays — is outside, and no method amortises: each rebuilds every structure on every operation, ours included. The one relaxation is the \(N\)-ary and iterated comparison (Section 4.3.2), where a method that supports it may keep its result inside its own representation across the chain of operations and emit the arrays only once, at the end. We report the minimum of \(K\) repetitions per operation. All runs are on an Apple M4 Max with multithreading enabled for every implementation; the drivers are compiled with clang -O3 -mcpu=native. Library versions: our method is trueform \(0.9.8\) [32]; Geogram \(1.10\), CGAL \(6.1\) (the EPICK kernel — exact predicates, double constructions — the fast configuration used for corefinement), Cherchi et al.(reference implementation [37]), MeshLib \(3.1\), Manifold (manifold3d) \(3.5\), EMBER (Solidean Community [35], preview build 2026-04-07-be517c). Each baseline is built and run as shipped on the host above.

Rationale. A mesh-boolean library is staged: it ingests the input, builds the internal representation its algorithm needs — spatial acceleration, topological connectivity, an exact-arithmetic context — runs the boolean, and emits an output mesh. “The boolean” can name the whole path or only the middle, with the structures already in hand, and prior comparisons rarely say which. The difference is a factor, not a rounding: for our method the spatial and topological structures alone are \(20\)–\(40\%\) of a single pairwise boolean (\(28\%\) at the geometric mean, untabulated), and they are reusable — built once, they serve a whole sequence of operations over moving geometry. The output is the same ambiguity at the other end: every method holds its result in an internal representation before emitting it — ours an implicit arrangement graph from which the surface is extracted — and charging or not charging that emission again moves the number. Anchoring the timed boundary at the data — arrays in, arrays out — removes both: there is no internal stage to include or omit, and every method is measured over the identical, complete task a user performs. Several libraries could do less if we let them — Manifold builds its collider at construction, MeshLib can cache half-edge connectivity, EMBER can pre-build its exact operands, and we can reuse our structures — but the head-to-head denies that to all uniformly; the \(N\)-ary relaxation is the one place where staying inside the representation reflects the operation itself, not a measurement choice.

Validity. Every output is graded by one oracle on the emitted floating-point arrays: the result must be a watertight solid — closed and consistently oriented — whose signed volume and surface area match the boolean’s reference values to floating-point tolerance. Every method computes the same solid, so the grade turns on whether each returns it as a closed, watertight mesh. “Valid” in the tables below means the output meets this bar, and the same oracle grades every comparison.

Corpus. Following the EMBER protocol [3], we draw random pairs of solid, manifold, non-self-intersecting Thingi10K [33] meshes, normalise each to unit extent, apply an independent random rotation, and offset the second so the bounding boxes overlap. Each pair is assigned a random operation — union, intersection, or difference — that every method computes. We sample at industrial resolution — \(100\mathrm{k}\) to \(1\mathrm{M}\) triangles per operand — the scale at which mesh booleans are a real cost in production pipelines. Pairs are baked to indexed OBJ so every driver reads byte-identical input.

4.3.1 Pairwise booleans↩︎

Figure 16 reports the per-boolean wall-clock distribution over the corpus [32]. Our method is fastest on every one of the \(1000\) pairs. At the geometric mean it runs \(5.5\times\) faster than MeshLib, \(7.6\times\) faster than Manifold, \(10.4\times\) faster than EMBER, \(29\times\) faster than Cherchi et al., \(32\times\) faster than CGAL, and \(100\times\) faster than Geogram.

Every method computes the same solid: the signed volumes and areas agree to floating-point tolerance on every pair, and each returns it as a watertight mesh (Table 5). Validity does not separate the methods here — only MeshLib misses, on a single pair, and CGAL on the one pair it fails to finish within the cap (below). The comparison turns on speed.

Completion is not guaranteed either. CGAL’s corefinement can blow up super-polynomially on near-degenerate contacts, its exact predicates falling repeatedly to expensive exact evaluation: on one corpus pair — Thingi10K models \(844209\) and \(518083\), \(0.86\) M input triangles — CGAL ran for over five hours (\(315\) minutes of CPU on a single core) without producing a result before we terminated it, while our method returned the same result, watertight, in \(20\) ms. We therefore cap each operation at \(120\) s and exclude from a method’s distribution any pair it fails to finish within it; CGAL timed out on this one pair, and every other method on none.

4.3.2 N-ary and iterated booleans↩︎

A single \(N\)-ary boolean measures how a method scales in the number of operands. For our method it is one arrangement build: all \(N\) operands are arranged together and the result is read from the resulting domain inclusion (Section 4.2), so its cost follows the sub-linear scaling reported there. A library with no native \(N\)-ary operator chains \(N{-}1\) pairwise booleans, the result accumulating one operand at a time; the native-\(N\)-ary engines — Manifold, Cherchi, and Geogram — arrange all operands at once, as we do. EMBER sits between: it accumulates pairwise, but keeps each intermediate inside its own representation across the chain — the relaxation the protocol grants (Section 4.3) — so it re-imports no growing mesh and tracks the native engines rather than climbing with the chain.

We draw \(40\) random \(N\)-operand sets for each \(N \in \{4, 16, 64\}\) from the Thingi10K pool [32], each operand randomly rotated and placed in an overlapping cluster, and time the single boolean of each set under the protocol of Section 4.3 (full geometry-to-output, best of \(K\), \(120\) s cap, multithreading enabled). CGAL, like MeshLib, has no native \(N\)-ary operator and accumulates pairwise; at this scale it is too slow to complete the sweep within the cap, so it is omitted here and its pairwise cost reported in Section 4.3.1.

Figure 17 reports each method’s median operation time relative to ours as \(N\) grows; Table 6 gives the absolute medians (printed to the millisecond; quoted factors use the unrounded values) and validity. Three methods stay near a fixed factor across the range. EMBER is the closest to us, \(10\) to \(14\times\): it accumulates pairwise but keeps its intermediates internal, so it does not grow with the chain. Of the native-\(N\)-ary engines, Manifold and Cherchi hold their factor too, at \(12\) to \(14\times\) and \(44\) to \(69\times\). The accumulator that carries a materialised mesh climbs with the chain: MeshLib runs \(39\times\) slower than ours at \(N{=}4\) and \(138\times\) at \(N{=}64\), the mesh it re-imports growing at every step. Geogram, though it arranges all operands at once, scales worst in absolute terms, from \(113\times\) at \(N{=}4\) to \(648\times\) at \(N{=}64\), as its exact arithmetic grows with the combined complexity. All methods agree on signed volume and area on every set, so each computes the same solid, and every method returns a watertight solid on every set at every \(N\) — save MeshLib, on two sets at \(N{=}16\) and three at \(N{=}64\) (Table 6). As in the pairwise case (Section 4.3.1), validity does not separate the methods; the comparison is one of speed.

4.3.3 In the browser↩︎

The same pipeline runs client-side in the WebAssembly build (Section 4.2). We measure it against the two booleans deployed for the browser: Manifold [27], whose WebAssembly build is a common in-browser solid-modelling kernel, and three-bvh-csg [39], the BVH-based CSG evaluator for three.js. Each is built and run as shipped. We run the pairwise corpus of Section 4.3 (\(100\)k–\(1\)M triangles per operand), one boolean per pair, in Chrome \(148\) on the same Apple M4 Max, and grade every output with the oracle of Section 4.3.

Figure 18 and Table 7 report the per-operation wall-clock and validity. Our method is fastest; at the geometric mean it runs \(12.6\times\) faster than Manifold and \(41.2\times\) faster than three-bvh-csg. Running in WebAssembly rather than native costs our method about \(1.4\times\) (\(15.7\) ms native to \(21.9\) ms in the browser on the same corpus), so the desktop ranking carries over and the exact pipeline stays interactive client-side. In fact, our method is faster in the browser than any baseline runs natively: its \(21.9\) ms median sits below MeshLib’s native median (\(86\) ms), the fastest of the prior methods. Validity separates them here. Our method and Manifold return a watertight solid on all \(1000\) pairs; three-bvh-csg on only \(22\) — on the other \(978\) it returns an open mesh, not a closed solid at all.

5 Conclusions↩︎

We have presented a mesh-CSG pipeline organised around a single fact: a CSG result loses exactness the moment it materialises, so a stage meant to compose with the rest of a pipeline can keep only its topology exact. The arrangement is computed locally with integer-exact predicates, every stage a graph problem on graphs it never explicitly constructs; where a decision spans faces, the disagreeing orient3d observations that materialisation perturbs are resolved by topological aggregation — a weighted-majority vote within their topological unit, the maximum-a-posteriori estimate of the unit’s intended outcome. The arrangement and its domain partition are built once, and a boolean of any arity is then a per-domain bit test, so a single build answers a whole family of CSG queries. The trueform implementation runs the same exact kernel in C++, Python, and the browser.

The vote is what makes the stage composable. An exact-construction pipeline cannot redo its arithmetic on a materialised arrangement — the regime in which a CSG step actually composes — whereas the vote keeps the partition correct from the observations alone: it tolerates two to three orders of magnitude more construction error than per-edge extraction, and recovers the failures construction alone already causes when the order is read from materialised coordinates on clean, watertight input — failures the build itself no longer makes, its radial order decided on the original planes without exact constructions. Against prior art the pipeline is the fastest method in the comparison — \(5.5\times\) to \(100\times\) at the geometric mean, depending on the baseline, and, compiled to WebAssembly, faster in the browser than any baseline runs natively.

5.1 Limitations and future work↩︎

The kernel operates on convex faces, fan-triangulated online; non-convex inputs, rare in mesh CSG, are triangulated upstream. Coordinates are snapped onto one of two integer grids (int32 or int64), chosen from the input type, so inputs beyond the wider grid’s range must be rescaled.

Two limitations are intrinsic to the approach. First, the vote resolves the partition — which domain each face bounds — from observations that have already been materialised; it does not constrain the geometry on the far side of materialisation. Materialising the output can introduce self-intersections the exact arrangement did not have: the partition stays correct as a combinatorial object, but the coordinates carrying it are not guaranteed crossing-free, and a stage that re-arranges the result may find new intersections. We make the topology robust to the crossing; we do not remove the crossing itself. Second, the vote is a majority estimator, and its guarantee is statistical, not worst-case. It recovers the intended order when the corrupted observations are a minority within their unit — the right model for construction error, which flips a few edges of a relation — but a configuration can be built to defeat it: a near-coplanar interface engineered so that, once materialised, more than half of a relation’s edges round to the wrong side leaves the majority itself corrupted, and the vote returns the wrong order. The method is robust against the error a real pipeline injects, not against an adversary who controls the geometry.

Making materialisation lossless is the natural next step: a snap-rounding of the output that introduces no new intersections, bounding the first limitation above, would let exactness and composability hold together rather than trade off. It is the open problem Lévy [4] and Cherchi [19] both leave standing, and the one piece our approach does not yet supply.

Acknowledgements↩︎

We thank Luna Sajovic for her help designing the figures, David Coeurjolly for his early review of the manuscript, and Philip Trettner for providing the Solidean preview binary used in our comparison.

6 Aggregation as maximum-a-posteriori estimation↩︎

The aggregation of Sections 2.4 and 2.5 is an estimator, and writing it as one makes precise why the majority is the right rule. Per-face exact predicates lift into a globally trusted topology, the reduced graph \(\mathcal{R}\) (Section 2.3), which is exact and fixed. The geometric relations between its wedges — the radial order at each non-manifold edge, the nesting between disjoint connected components — are not: each is an observation, a categorical reading of one intended topological outcome.

Model.

Fix a topological unit with a finite categorical space \(\mathcal{C}\) of size \(K\): for a component the candidate orientations, for a relation the canonical radial permutations. The unit has one intended category, the latent \(c^\star \in \mathcal{C}\). Its \(n\) observations \(g_1, \dots, g_n \in \mathcal{C}\) are independent categorical reads of an unknown category distribution \(\theta \in \Delta^{K-1}\) whose mode is \(c^\star\); the noise perturbs the reads, not the intent — for the radial vote, a materialised re-reading, a mirrored direction sign, or an inconsistently wound input sheet. With \(N_k = \lvert\{\, i : g_i = k \,\}\rvert\) the count of category \(k\), the likelihood is \[P(G \mid \theta) \;=\; \prod_{k=1}^{K} \theta_k^{\,N_k}.\]

Prior and posterior.

A symmetric Dirichlet prior \(\theta \sim \mathrm{Dir}(\alpha, \dots, \alpha)\) favours no category, \[P(\theta) \;\propto\; \prod_{k=1}^{K} \theta_k^{\,\alpha - 1},\] and conjugacy makes the posterior a Dirichlet whose parameters are the counts plus the prior, \[P(\theta \mid G) \;=\; \mathrm{Dir}\!\bigl(N_1 + \alpha, \dots, N_K + \alpha\bigr).\] The intended category is the most probable one, estimated at the posterior mode \[\hat{\theta}_k \;=\; \frac{N_k + \alpha - 1}{\,n + K(\alpha - 1)\,}, \qquad \hat{c} \;=\; \arg\max_k \hat{\theta}_k \;=\; \arg\max_k N_k .\] For \(\alpha \ge 1\) this expression applies; the normaliser and the constant \(\alpha - 1\) are then common to every category, so they leave the argmax untouched: the MAP category is the count argmax, the majority, independent of \(\alpha\).

Weights.

Replacing each unit count by a weighted count \(W_k = \sum_{i :\, g_i = k} w_i\) scales the pseudocounts with weight and leaves the form unchanged, \(\hat{c} = \arg\max_k W_k\). Trueform weights each radial observation by the minimum area of the faces incident to its non-manifold edge, so near-degenerate slivers — the reads most likely to be wrong — contribute least, and observations from invalid fans carry \(w_i = 0\) and drop out.

Epistemic status.

The Dirichlet model is a subjective prior: it makes the pipeline’s uncertainty over a relation’s intended permutation precise, and identifies the majority as the coherent estimate under it. It claims nothing about objective chances, and none is needed — the operative guarantee is definitional: the vote returns the intended permutation exactly when a majority of the relation’s observations carry it.

Scope.

The framing adds no machinery to the algorithms of Sections 2.4 and 2.5: the MAP estimate under a uniform Dirichlet is the weighted majority they already compute, run on two nested units — a component (orientation) and a relation (merging) — each instantiating \(\mathcal{C}\); the domain inherits its inside/outside from the voted wedges that bound it, with no further estimate. Its value is in stating the assumption plainly: the intended geometry is a single latent category per unit, and materialisation’s perturbations are independent categorical noise around it. The independence is an idealisation — adjacent edges of a relation share an endpoint, so neighbouring reads are weakly correlated — but the correlation is local and does not bias the majority, which aggregates over all the relation’s edges. Prior pipelines treat the same observations differently: Lévy raises precision until they agree [4], Böhm and Runge trust each edge in isolation [20]; naming the rule as estimation is what lets one vote serve orientation and merging alike, with the domain classification inheriting from them.

References↩︎

---

1. Available as tf::label_connected_components and tf::make_dense_equivalence_class_map in the trueform implementation.↩︎

2. Selectable in the trueform implementation via the tf::domain_config flag set: tf::domain_config::ignore_open_fragments for Mode 1, omitted for Mode 2 (the default).↩︎

3. lunar.polydera.com↩︎

4. trueform.polydera.com/live-examples/boolean↩︎