Benchmarking Mesh Booleans: Terrain Carving

This is the second case in our public mesh boolean benchmark. The first one was deliberately friendly: 9 subtractions of clean primitives, and 12 of 17 implementations came out correct or close to it. This one is a harder counterpart.

The setup is a single cube workpiece that we carve down with a long chain of sphere-sweep subtractions, following a heightmap. 223 subtractions in total, each one taking the result of the previous step as its input. Each sphere-sweep tool is tiny, only about 380 triangles, so no individual subtraction is heavy. Because consecutive sweeps meet exactly where the previous one ended, the operations keep running into coplanar faces, even though the total triangle count never gets large. Even at a moderate triangle count, once the operations are iterated, and once the case forces a certain amount of coplanarity on you, most methods bail out fast. Staying completely robust through a chain like this is genuinely hard.

This is the full 223-step carve, run by Solidean from the cube down to the final shape. We treat its area = 6.1648, volume = 0.5477 as the canonical result because both CGAL methods and Solidean agree on it, and these three are the only methods here that use exact constructions, not just exact predicates. When the methods that actually compute exact geometry agree, that is the number we measure everyone else against.

We ran the same 17 implementations as before. This time only 4 reproduced the canonical result: Solidean, Manifold, and both CGAL variants (corefine and Nef). 6 implementations completed the chain but returned wrong geometry: wrong area, an inverted solid, a degenerate near-empty mesh, or an empty result. The remaining 7 crashed partway through or produced no result at all.

Among the correct results, the timing spread is about 1600x.

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

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

Results

Each runner executes the same 223-step subtraction chain and reports per-operation time. "Time" is the sum of operation time and import time (input mesh to internal representation), the same measure we used in the first post. Correctness is checked against a reference area and volume (see Notes). This case has essentially no "almost correct" bucket. The closest is Carve, which inserts doubled-up, double-sided triangles, so it keeps the right volume but reports too much area.

The "Rel." column is runtime relative to Solidean, and Mtris/s is throughput over the chain (input triangles per second). We only report these for runs that reached the canonical result. A wrong or crashed run often computed something easier (it bailed out, inverted the solid, or stopped early), so a relative time or throughput number for it would compare against a different problem and just mislead. For the same reason, rows marked with * crashed mid-chain, so even their raw time only covers the operations they managed before dying.

Two things stand out compared to the first case.

First, the correct set shrank from 12 to 4. Several implementations that handled the easy chain cleanly, including ones that are quite fast, now drift into wrong geometry on this case. The inputs are not more complex per operation; the chain is just longer and the configurations are nastier.

Second, the outcomes are much more binary than before. In the first case the off results were at least close. Here a run is either exactly canonical or so far gone that the mesh is not salvageable: inverted, degenerate, or empty. That is the curse of iteration: an error introduced early has hundreds of steps to spread, and nothing downstream pulls it back.

What makes this hard

The individual operations are not exotic and a cube minus one swept sphere is a routine subtraction. The difficulty comes from the same place as in the first case, iteration, plus one new ingredient.

The new ingredient is coplanarity, and a fairly tame kind at that. There are no near-coplanar faces, no partial overlaps, and no large coplanar regions to speak of. The terrain is uneven, so the only coplanarity comes from how consecutive sweeps meet: each sweep starts exactly where the previous one ended, and the construction lines those seams up on purpose, so that no slivers or geometric cruft are left between steps. Even so, that puts exactly coplanar faces in front of the classifier, which is the classic stress test for boolean classification: deciding which side of a shared plane a face belongs to is exactly where an implementation either does the careful exact work or guesses.

Then iteration takes over. Each operation's output mesh is the next operation's input. A single misclassified face in step 40 does not stay a local glitch. It becomes a hole, a flipped patch, or an inverted shell that step 41 has to cut into, and the error propagates and grows. We see essentially no self-healing: once an implementation introduces a real topological error, the rest of the chain faithfully carries it forward, often amplifying it.

That is the point we want to make with this case. A boolean that is "almost right" on a single operation is not almost right on a 223-step chain. Small local errors become global, permanent corruption that no amount of later cleanup can recover, because the geometry the later steps needed is already gone.

Watching it go wrong

We captured the chain for every runner, but the interesting ones are below: the cases that go wrong in a structured, telling way rather than just crashing from one step to the next. The clean reference run is the video at the top of the post; here are the same 223 steps where things drift off. None of this is meant to dunk on these libraries: they are good tools, and this is a deliberately hard-but-realistic case. What these videos show well is how a result goes wrong, and why it is usually impossible to fix after the fact.

Carve

Carve gets the volume exactly right (0.5477) but the surface area is about 10% too high (6.8216 vs 6.1648). In the video you can see polygonal patches of the input that Carve duplicates into two coincident, oppositely-facing copies, which is the z-fighting flicker on those faces. Some of these get cleaned up again, but many survive scattered across the surface, which is where the extra area comes from. This is the closest any method here gets to graceful degradation: the solid is still basically right, just carrying redundant double-sided geometry. Whether you could actually repair it after the fact is not obvious to us. (Carve is also effectively dead: unmaintained, with the last release back in 2014.)

QuickCSG

Here the volume goes negative (-0.4388). QuickCSG classifies individual triangles, and a single misclassification is enough to seed the breakdown: it turns into holes and floating bits of geometry that then confuse the classification of everything downstream. Because the decisions are per-triangle, the resulting artifacts are almost unstructured, a scatter of stray surface rather than one clean wrong patch, and once that is in the running mesh the rest of the chain only makes it worse.

Trueform

Trueform ends up kind of inverted (area 16.28, volume -0.8181), and it is the most interesting one to watch. Its algorithm is quite robust and, as we understand it, works hard to keep whole patches consistent rather than deciding triangle by triangle. So it stays in the happy case for a long time, until a single triangle goes missing. The sweeps keep carving correctly for a while, but the next time the path comes back over that spot, a whole patch is suddenly misclassified, and that is where the real breakdown starts. From then on, every time a sweep returns to a damaged region the artifact grows. It is a good reminder that local consistency is not enough: one unrecovered error is all it takes.

Trueform is under active and rapid development, and this run was version 0.7.0. We have let the developer know about this case, so a later version may well behave differently here.

Blender (fast)

The fast solver (area 3.71, volume -0.15) breaks early and never recovers. It is fast enough that there is already a lot of missing surface after just the first few steps, and that hole is never filled back in. The solver seems strongly biased toward not emitting a face rather than emitting one where it does not belong, so the errors all fall the same way: missing geometry. The result is a basically open mesh, which is why both the area and the volume come out far too low.

Toward a public benchmark

This is case two. The first was an easy chain to establish a baseline; this one adds deep iteration and exact coplanar seams to separate "works on clean inputs" from "stays correct under accumulation." More cases are coming, with different geometries, operation types, and stress patterns.

The runner infrastructure and build scripts are open source 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.

Notes

The reference ("canonical") result for this case is area = 6.1648, volume = 0.5477. Results matching to 4 decimal places are marked canonical; anything else is marked wrong. The Solidean baseline is 205.19 ms for the full chain.

The case is a single cube workpiece carved by 223 iterated sphere-sweep differences, following a heightmap pattern. The running result of each operation is the input to the next, so the chain cannot be parallelized and errors accumulate.

The measurement definition, system specs, library versions, and licensing are unchanged from the first benchmark post; see its Notes section for the full details. As before, "Time" covers only the import (indexed triangle mesh to internal structure) and the boolean operations, no file IO.

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