Boolean2 is the sole CrossSection implementation. There is no
MANIFOLD_CROSS_SECTION_BACKEND selector and no Clipper2 dependency; Boolean2 is
always built in-tree.
Boolean2 is a manifold-native 2D arrangement pipeline for polygon fill and
Boolean operations. The core library lives in src/boolean2*.{h,cpp}, and the
public CrossSection methods dispatch to it. Sibling utilities provide the
decomposition and offset pieces that cover the rest of the public CrossSection
API.
DisjointSets for vertex equality, and the shared Interpolate
segment helper.CrossSection API and
CrossSection/Manifold round trips.Boolean2 builds a planar arrangement with a sweep line and classifies it by winding:
manifold::Polygons.Steps 5 and 6 run as two lexicographic passes of the same sweep, in
boolean2_sweep.cpp. Offset and containment helpers live in
boolean2_offset.cpp, declared alongside the core API in boolean2.h.
The main dataflow is:
boolean2.h -> boolean2.cpp (conversion -> merge/incidence pre-split ->
sweep driver) -> boolean2_sweep.cpp (sweep-line arrangement + winding) ->
regularized Polygons.
| Layer | Files | Role |
|---|---|---|
| Public core API | boolean2.h, boolean2.cpp (entry points) | Converts Polygons to local vertices plus directed edges, runs one arrangement build, and turns retained edges back into regularized output. |
| Arrangement coordinator | boolean2.cpp (driver section) | Runs vertex merge, edge collapse, the broad phase, and the incidence pre-split, then hands the sub-edges to the sweep. |
| Sweep-line engine | boolean2_sweep.cpp | The maintained-status Bentley-Ottmann sweep: a collect pass that discovers crossings and applies the block rule, and a measure pass that forces residual crossings through and classifies the fill by winding. |
| Geometry leaves | boolean2.cpp (broad phase, vertex merge, edge-vertex list sections), boolean2_predicates.cpp | Local geometric operations and the epsilon predicates used before the sweep. |
| Sibling helpers | boolean2_offset.cpp | Offset and decomposition support for the rest of the CrossSection API. |
Debug and performance tracing live in boolean2_diagnostics.{h,cpp}.
This engine is Julian Smith's 2D simplification sweep
(RobustBoolean.pdf, chapter 7): a Bentley-Ottmann sweep in
rounded arithmetic, with the section 7.6.2 block rule handling degenerate
near-concurrent events by the status order, followed by a winding classification
of the resulting arrangement. A computed intersection point lies within
alpha = sqrt(153)*u*L = 12.37*u*L of both source segments (section 8.2), and
EpsilonFromScale(L, k) is the (k+1)*alpha budget the eps predicates use (the
input feature merge and incidence pre-split use budget 1000).
The architecture differs from the original sketch (issue #289), which used a
broad phase with point-order crossing insertion and exact-distinct vertex
identity - chosen so the broad phase recovers the sweep's O(n log n) and
parallelizes, on the argument that Smith's rounding analysis keeps it robust
without the sweep. An earlier version of this engine followed that sketch. It
handles ordinary inputs, but does not stay consistent across dense
near-concurrent clusters: independent pairwise crossing decisions need not
compose, so the arrangement can become non-manifold and construction trips the
closed-walk assert (or, with asserts off, drops the region). A maintained sweep
order decides those clusters globally, which is why this engine uses the sweep.
Smith reports the same trade-off (section 7.8, where his non-sweep alternatives
either iterate excessively or give too much geometric error) and ties
arrangement validity to the sweep (section 7.6.3).
The remaining implementation notes:
The winding pass keeps a sub-edge iff the requested rule classifies its two sides differently: one side inside the result, the other outside. The internal Boolean2 predicates are:
Add: w > 0, used for union/fill under the default positive-winding rule.Subtract: implemented by appending the second input with negative
multiplicity, then using Add.Intersect: w > 1, which corresponds to both operands covering a side for
normalized unit-winding operands.EvenOdd: w odd, reachable from CrossSection::EvenOdd for input authored
against an even-odd tool. It reads the same signed winding by parity rather
than sign, so unlike Add it fills a lone clockwise contour (w == -1).The rule is not selectable for boolean operations - Boolean2D picks Add or
Intersect from the OpType. It is selectable only where the input's own
winding is first read, which is single-operand construction. What gets stored is
normal-oriented and positive either way, so nothing downstream sees the
difference.
The core operates on manifold::Polygons, which cannot encode isolated
one-dimensional features. Output is therefore regularized: zero-area loops,
collapsed edges, and cancelled opposing sub-edges are dropped.
Epsilon quantization applies to input features - the vertex merge and the incident-vertex pre-split. The sweep itself is tolerance-free: it runs in rounded double arithmetic but with no eps band - crossings are constructed and split by exact sign predicates, and near-concurrent clusters are resolved by the block rule's status order rather than by a distance-based snap. Output vertices around a resolved sub-epsilon tangle may consequently sit closer than epsilon to each other; a subsequent pass fuses them as input features on re-ingest.
Callers may pass an explicit epsilon. A non-positive epsilon asks the core to infer an operation scale and apply the local floating-point budget used by the Boolean2 predicates. Inputs are translated into a local frame before the arrangement is built, then translated back on output.
The core runs one arrangement pass and returns that regularized output. Repeated
Simplify() calls are not part of the public contract: tiny perturbations from
floating-point arithmetic, transforms, or serialization can legitimately change
future cleanup decisions within the epsilon regime.
Build and run the CrossSection regression tests:
cmake -S . -B build -DMANIFOLD_TEST=ON
cmake --build build -j4 --target manifold_test
ctest --test-dir build -R '^CrossSection\.' --output-on-failure
Can you improve this documentation?Edit on GitHub
cljdoc builds & hosts documentation for Clojure/Script libraries
| Ctrl+k | Jump to recent docs |
| ← | Move to previous article |
| → | Move to next article |
| Ctrl+/ | Jump to the search field |