Benchmarking Mesh Booleans: Cut and Glue Sphere

This is the fifth case in our boolean benchmark series, and we like to call it "the hardest simple boolean". Instead of a realistic workload, this case isolates a tricky situation that shows up all the time once booleans are chained: exactly overlapping surfaces that the boolean itself produced. Take two overlapping spheres A and B, subtract B from A, then glue the removed piece back onto the result. Mathematically, this is just (A - B) | (A & B) = A, so it does not change A in any way, like computing x - 5 + 5 = x. Even a compiler would optimize that away (for integers, at least; for floats it knows better). We repeat this 30 times in a row, feeding every result into the next cycle as the new A. So this should be easy (but of course it is not, otherwise why write a blog post about it).

In the previous post, the challenge was scale: up to 200,000 iterated operations and ever-growing triangle counts. Here, the meshes do not have to be complex, and most failures show up within the first one or two cycles. Even for spheres with low tessellation (~1,000 triangles each), only 4 of 19 implementations compute the correct result. In this post, we look at why this problem is so hard, how things actually fail, and what it takes for an implementation to survive this operation over and over.

The runner programs are open source: github.com/Open-Boolean-Benchmark/boolean-benchmark-runners

The input meshes and request files for this case, so you can reproduce it yourself, are at github.com/solidean/bench-blog-data.

The case

The geometry consists of two unit spheres whose centers lie one unit apart. Their surfaces meet along a circle, the seam, and every boolean in this test has to cut exactly along it.

Every cycle computes two pieces: the subtraction yields a "dented ball", and the intersection yields the lens-shaped piece that was cut away.

The key observation is that both of those pieces now carry a copy of B's spherical cap. When the two pieces are unioned back together, this cap is inside the solid and has to disappear completely.

For our experiments, we test spheres with different triangle counts: 1k, 4k, 16k, 64k, 256k, and 1M. The ground truth volume and surface area are simply those of the tessellated input sphere A, so we do not have to trust any consensus among the implementations' outputs. That differs from earlier posts, where "canonical" meant that the exact methods agreed.

To consider a result correct, we require the volume to be within 0.01% and the area within 0.1% of the ground truth values. Furthermore, the output has to be a closed 2-manifold.

Sometimes the volume is correct but the area is too high. That means both copies of the cap survived the union: an implementation that does not resolve the touching surfaces exactly leaves a doubled wall inside the solid, with a non-manifold seam. We call this a crack. The next cycle then has to cut through that internal wall as well, and each cycle can add another copy, which is how a harmless-looking crack turns into the state explosions and collapses we show further down.

Results

Every runner gets 1 hour and 30 GiB per sphere size, and a run that crashes, times out, or runs out of memory is not tried at larger sizes. The table shows the largest size each runner passes, with its time and peak memory, and the smallest size at which it fails, with how long it ran and how much memory it used until then. Relative speed is only given for runs that pass at 1M. Time is import plus boolean operations, as in the other posts of this series.

Only Solidean and CGAL (corefine) pass every size. Carve passes everything except 16k, and CGAL (nef) is correct but only gets to 16k within the hour. The last two columns show how the others fail: some crash within a few seconds at a few MiB, others pile up geometry until they hit the 30 GiB cap, and two spin until the hour is up. We look at these failure modes in detail below.

What makes this hard

The input itself is tame: smooth spheres without any slivers, self-intersections, or degeneracies. All the difficulty comes from what the implementation produces in every cycle.

Every implementation is forced to eat its own output. Every flaw in the output of one cycle is part of the input of the next. Errors add up and complicate every subsequent operation.

In the dome carve, every step cut at a new position along the tool path. Here, every cut happens exactly where the previous cut already happened. The vertices along the seam were computed by the previous cycle and lie on B's surface, or within rounding distance of it. Orientation tests against B then land at or very near zero, where rounding decides the sign.

The seam being curved intensifies this further. A planar seam can be represented exactly, so the two copies of the cap match bit for bit and cancel cleanly. On a curved seam, every re-triangulation rounds a little differently. We ran an experiment where A and B were simple subdivided boxes, and 12 implementations passed it at every size, compared to 2 here. That shows the curved seam is what separates the field, not the repetition alone.

Watching it go wrong

For illustration, we re-ran the 4k and 16k sizes and saved triangle count, area, volume, and memory after every cycle. The charts below show 16k. Out of the 19 implementations, 8 die in the first two cycles, before any trend shows. MeshLib shows the crack mentioned earlier: its first union keeps both cap copies, adding 25% to the area, before it crashes in cycle 2.

State explosion

Manifold, Mesh Arrangements, and Trueform 0.9.7 share a pattern: the volume stays correct, but the internal state grows every cycle until it blows up. Manifold's result has the exact volume in every cycle, but the area creeps up and is 0.5% too high by cycle 6. Then cycle 7 alone multiplies the triangle count by 77, from 27k to 2.08M.

Mesh Arrangements and Trueform 0.9.7 produce non-manifold output after a few cycles, even though Mesh Arrangements keeps area and volume exact and Trueform's volume is only 0.05% off. Mesh Arrangements gets slower with every cycle and times out after four, and Trueform runs out of memory. This again shows that volume alone is not a strong enough metric for boolean correctness, and why we also check that the output is a closed 2-manifold.

In all three, the triangle count grows faster and faster. A likely explanation: leftover geometry at the seam lies exactly on B's surface, so every following cycle cuts it again and adds more triangles.

Wrong geometry

Both Blender solvers and Trueform 0.10.5 leave the correct result early and never come back. Blender (exact) passes cycle 1, but its cycle-2 union collapses to a tiny, zero-volume mesh (22 triangles). From there on it keeps producing zero-volume geometry that grows with every cycle, to 43k triangles by cycle 5, until it runs out of memory after about 11 minutes.

Trueform 0.10.5, the newest release, fails in the same way, just without running out of memory. Cycle 1 is correct, but the cycle-2 union collapses to a zero-volume mesh (204 triangles), which it then carries through the remaining cycles in well under a second. We could reproduce this outside the chain: loaded fresh from disk, the cycle-1 result still gives a correct difference and intersection with B, and only their union collapses, which is exactly the step where the two cap copies have to cancel.

Blender (fast) cracks right away: its first union keeps both cap copies, so the area is 25% too high while the volume is still almost correct. That 25% is exactly one extra cap: for two unit spheres one radius apart, B's cap has an area of pi, a quarter of the full sphere's 4 pi (MeshLib's crack above shows the same number). From there the volume error grows to +15% by cycle 7, the result falls apart in cycle 8, and the run hits the one-hour limit at 624k triangles.

Finished, but wrong

Two more implementations make it through all 30 cycles at every size with something that still looks like a sphere, and still do not pass. QuickCSG's volume is 3.6% too low right after the first cycle, and after a few cycles the error settles and stays flat (the flat line in the drift chart above). So this is not accumulation: the first cut on this geometry is already classified wrong, and the following cycles just carry that result along. Across sizes, the final error jumps between 2.5% and 21.5%, always on the low side, and the output is non-manifold throughout.

Carve is the mild form of the crack. It passes 5 of the 6 sizes, but at 16k its output is non-manifold from the first cycle on. Area and volume stay exact, and the triangle count stays at exactly 16,952 for all 30 cycles, so no cap copy is left behind and nothing grows. Not every crack escalates, but a result that is not a closed 2-manifold is still not a valid solid.

Survivors

At 4k and 16k, Solidean, CGAL (corefine), and CGAL (nef) return the same result in every cycle: triangle count, area, and volume do not change from cycle 1 to cycle 30, which are the flat lines in the triangle chart above. This is what a boolean identity should look like: once the first cycle has placed the seam, every following cycle reproduces it. At 16k, Solidean needs about 18 ms per cycle.

CGAL (nef) is the only implementation that returns exactly the triangle count of the input sphere (16,128 at 16k), so it removes the seam again completely. It pays for that with about 15 s per cycle: the 16k case takes 15.4 min, and 64k does not finish within the hour.

Conclusion

Looking at the survivors and the failures side by side, two properties decide whether an implementation makes it through this loop. The classification against the seam has to be exact, or the orientation tests near B's surface come out inconsistently, which is where the crashes, collapses, and wrong volumes above come from. And the output has to be clean: one solid, with the interior cap removed and the seam welded into a closed 2-manifold, because any duplicate geometry that survives a union becomes input for the next cycle.

Exact arithmetic inside a single operation is not enough, though. As an example, Blender (exact) computes each boolean exactly, but stores the intermediate result as a 32-bit float mesh. Mesh Arrangements is in a similar situation in our setup: libigl computes each boolean exactly, but our runner converts the result to double coordinates between operations. The next cycle then starts from rounded seam vertices, and the exactness of the previous step is gone. The three survivors keep exact coordinates from one operation to the next and only round when the result is exported.

Carve shows why guarantees matter. It passes at 4k and at 64k, and fails at 16k, in between. Nothing about the 16k input is special, and nothing warns you in advance: without exactness guarantees, you only find out which inputs break an implementation by running into them. Tests can show that a method worked on the cases you tried, not that it will work on the next one.

Exact arithmetic turns that around: every decision is made on the exact geometry, so the result follows from the input, not from how the rounding happened to fall. CGAL is the other winner of this case: CGAL (corefine) passes every size, and CGAL (nef) is the only implementation that removes the seam again completely. Solidean gives the same guarantee and gets there 7x to 45x faster than CGAL (corefine). Internally, it keeps the solid as convex polygons whose coordinates are exact with a bounded bit width, so the only rounding happens at import and export. A seam vertex computed in one cycle is therefore still exactly where it was in the next. If your pipeline chains booleans, as CSG trees, iterative modeling, or lattice and support generation do, that is exactly the property you need.

None of this makes the other libraries bad tools: this case was built to be hard. Manifold keeps its output a valid, closed manifold with exactly the right volume in every cycle it completes. MeshLib and Trueform both passed the planar box version of this test at every size, which shows that they are generally well equipped for this kind of problem. It is the curved seam that pushes them over the edge. Both have also shipped several releases since we ran that box test, and we will keep testing new versions as they come out.

Toward a public benchmark

This is case five. The earlier posts covered an easy chain, deep iteration with coplanar seams, a grid-aligned fill-and-empty, and a long carve pushed to extreme step counts. This one strips the workload down to an identity and asks whether an implementation can hand back what it was given. More cases are coming, with different geometries, operation types, and stress patterns.

The runner infrastructure and build scripts are open source under the Open Boolean Benchmark org, at github.com/Open-Boolean-Benchmark/boolean-benchmark-runners. Each runner is a small standalone program that reads a JSON task description, calls the library, and writes back timings and result meshes. Adding a library means writing one wrapper.

Missing your favorite boolean library, or maintaining one yourself? We would like to include it, in the next posts and, where it makes sense, by re-running this case as well. Open an issue or a pull request in the runner repository, or get in touch. The existing wrappers are around 300 lines each, and we are happy to help with yours.

Notes

(This is "boring data" meant for reproducibility)

The case is two UV spheres of radius 1, centered at (0,0,0) and (1,0,0), with float64 vertices stored as OBJ. One run is 30 cycles of cur = (cur - B) | (cur & B), which is 90 boolean operations plus 2 mesh loads in a single request, with meshes kept in memory between operations. We test 1k, 4k, 16k, 64k, 256k, and 1M triangles per sphere.

The reference values are sphere A's own discrete area and volume at each size. A run passes if the final volume is within 0.01% and the area within 0.1% of these values, and the output is a closed 2-manifold on its own vertex indices. Right volume with excess area or non-manifold output is a crack, and a completed run with the wrong volume is wrong. We do not expect (or require) the result to be exactly A again: the seam introduced by the cut usually survives the union, even though it is not needed geometrically. For the 16k spheres, for example, Solidean returns 17,200 triangles instead of the 16,128 of the input, and then exactly 17,200 again in every cycle.

The reference values, per size (area, volume):

• 1k: 12.477164, 4.129531
• 4k: 12.542658, 4.172997
• 16k: 12.560063, 4.184586
• 64k: 12.564769, 4.187722
• 256k: 12.565970, 4.188523
• 1M: 12.566268, 4.188722

Each (runner, size) runs in its own process, with the working set of the process tree sampled every 25 ms and capped at 30 GiB. The initial budget was 300 s per run, and every run that timed out was re-run with 3600 s. All numbers in this post come from those runs. "Time" is the engine-reported import plus boolean operation time, summed over all operations, with no process startup and no file IO. "Peak mem" is the peak working set of the process tree. For the per-cycle charts, we re-ran the 4k and 16k sizes and recorded triangle count, area, volume, and memory after every cycle.

All libraries run with default settings. Mesh Arrangements runs through libigl's mesh_boolean, with double-precision output between operations. The measurement definition, system specs, and licensing are unchanged from the first benchmark post. See its Notes section for the full details.

This is a single test case with specific library versions and default configurations. Results may differ for other geometries, operation counts, or library settings.