Benchmarking Mesh Booleans: Iterated Cube Grid

This is the third case in our public mesh boolean benchmark. The first one was a friendly iterated CSG chain, and the second was a long, coplanar-seam terrain carve. This one is different in flavor: it is synthetic, regular, and a little Minecraft-esque.

We take a 10x10x10 grid of unit cubes. First we union in all the "even" cubes (checkerboard parity), one cube per operation. Then we union in all the "odd" cubes, which in an ideal world leaves one solid 10x10x10 block. Then we take it all apart again: difference out the even cubes, then the odd cubes, one at a time. That is 1999 consecutive boolean operations, each one ingesting the mesh the previous step produced.

The nice part is the target. The cubes are integer-aligned, so adding a set of them and then subtracting exactly the same set leaves nothing. The correct result for this case is simply the empty set: area = 0, volume = 0. There is no ambiguity to argue about and the only question is whether an implementation actually gets back to nothing, or leaves something behind along the way. (Or cannot handle all the degenerate cases that crop up because this has a lot of collinear edges and touching vertices.)

We added a new version of geogram, so now had 18 runners to compare against. Half of them produced the canonical result (and correct intermediate results). Among the runs that reached the canonical result, the timing spread is about 2200x.

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 1999-step chain (fill the grid, then empty it) 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 two posts. Because the grid is integer-aligned, the correct shape after every single operation is known exactly, so this time we can write a cheap oracle and check not just the final result but all 1999 intermediate steps along the way. A run is canonical only if it matches the expected shape at every step.

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, collapsed early, or stopped after a few operations), so a relative time or throughput number for it would compare against a different problem and just mislead. Rows marked with * crashed or diverged mid-chain, so even their raw time only covers the operations they managed before failing, and is not comparable to runs that finished.

Compared to the previous post, we extended our lineup a bit. Geogram appears twice, in versions 1.9.8 and 1.10.0. Our runner repo (now hosted under the Open Boolean Benchmark org) is continuously updated: when a library ships a major new version, or its maintainers tell us they made a big improvement and want the bump, we re-wrap it. We cannot keep every minor version around, but we do track the major ones. Geogram is the example this time: between the last case and this one it went from 1.9.8 to 1.10.0 with a large performance improvement, from about 37 minutes down to 112 seconds on this exact case. So we show both versions here to make that jump visible.

What makes this hard

There are two stressors in this case, and they are slightly different from the first two posts.

Non-manifold, but still solid

When we union in all the even cubes, something subtle happens. Because of the checkerboard parity, those cubes never share a full face. In this first phase they only touch along edges and at corners. So nothing actually merges, the result keeps all of the original faces, and it is now highly non-manifold in the classical sense: every shared edge is surrounded by 4 faces instead of 2. From the perspective of booleans this is not a problem at all. You can split it into sub-manifolds later if you want, but geometrically it is completely watertight and solid.

In Solidean's terms this is exactly the solid vs. supersolid distinction: the result of a boolean is always geometrically Solid, and what happens topologically is purely a question of how you choose to export it. Solidean works internally with exact geometry and only reconstructs topology on output, which is something we extended from the original EMBER publication. That means non-manifold intermediate states like the half-filled grid are not special cases internally; they are just solids.

The interesting consequences show up at export time. exportToIndexedTrianglesF32 properly resolves all t-junctions and welds all vertices, which is perfect for a rendering setup and fixes a common criticism of EMBER, namely that you lose your guarantees the moment you leave the exact representation. You still lose some guarantees here (it is no longer an exact result, because the rounding to float is necessary), but you keep fully valid topology: even if the rounding introduces new self-intersections, the output is always what we call topologically supersolid, so you can always re-import it as a Supersolid mesh. And if you need a specific output format, exportMesh lets you pick it, including halfedge structures and guaranteed 2-manifold results via ExportOption::Manifold, which duplicates vertices to force a topologically 2-manifold mesh, much like the Manifold library does.

Iteration with no self-healing

The second stressor is the one we have seen before: iteration. Each operation's output is the next operation's input, across all 1999 steps, so the chain cannot be parallelized and there is nothing to pull an error back. A single misclassified face while filling becomes a hole or a stray wall that every later step has to cut into, and the error propagates and grows. Though this time, the pathological integer setup was arguably the harder stressor for the methods.

Watching it go wrong

We captured the chain for every runner. The clean reference run is the Solidean video at the top of the post: the grid fills up to the solid block and then empties back out to nothing. Below are the two failures that are interesting rather than just a nondescript crash from one step to the next. None of this is meant to dunk on these libraries: they are good tools on a deliberately hard, synthetic case. (Though synthetic doesn't really exclude real use case here. If you want to build a Minecraft-esque world using mesh booleans to support smooth editing and crisp block semantics, then this is exactly what you need.)

Blender (fast)

The fast solver is correct for almost the entire fill phase and looks right at the halfway point, the full cube. The trouble starts when we remove the cubes again: some, but not all, of the walls stay behind as zero-volume, double-sided regions. Once those walls are in the running mesh, the later subtractions have nothing clean to cut against, so the artifacts persist instead of being cleared, and the final result is far from empty. It is a good illustration of the iteration problem: the fill phase is fine, but a handful of faces that should have cancelled during removal do not, and there is no later step that recognizes and deletes them.

CGAL (corefine, EPEC)

CGAL's corefine backend is one of the methods we normally trust as an exact-construction reference, so it is worth explaining why it is in the red here. It returns false (no result) on operation 5, the first time a newly added cube touches two already-placed cubes at once.

The frame above is upscaled from the capture to show the configuration: because of the checkerboard parity, the incoming cube does not share a full face with anything, it only meets its two neighbors along edges. The union of those cubes is a perfectly valid solid, but a non-manifold one, with an edge surrounded by four faces.

And that turns out to be the whole point, so this is not a CGAL bug. The corefinement-based booleans are documented to require a manifold output, and the CGAL manual is explicit about it:

First, the input meshes must be manifold triangulated surfaces bounding volumes. In particular, this means that they should not self-intersect. Second, the operation is only possible if the output can be bounded by a manifold triangulated surface mesh. In particular, this means that the output volume must not contain regions of zero thickness. Mathematically, the intersection with an infinitesimally small ball centered at any point of the output volume must be a topological ball. At the surface level, this means that no non-manifold vertex or edge is allowed in the output. For example, it is not possible to compute the union of two cubes that are disjoint but share an edge. If such scenarios arise, consider using the package 3D Boolean Operations on Nef Polyhedra.

That last example is exactly our operation 5. A CGAL maintainer confirms the same for a tangency-along-an-edge case: the inputs are not invalid, there is simply nothing to fix.

This is CGAL corefine's stance, and it is a perfectly reasonable one. We just take a more general one. By duplicating vertices on output, Solidean can always bound a result by a collection of non-intersecting manifold meshes: they may touch geometrically, but they are topologically disjoint. That is what we define as Solid, and booleans are closed under that definition. So where corefine sees an output it cannot represent, we see an ordinary solid.

The practical upshot is closure, and we consider it one of the most important properties a boolean kernel can have. You can check each input independently for whether it is solid or supersolid, and if Solidean says yes, then every boolean combination of those inputs will succeed (subject only to CPU and memory limits), fully independent of how you combine them. There is no way to start from valid inputs and boolean your way into an unsupported state. If that ever happened it would be a bug, and we have not had one of these in over three years.

This is what makes booleans fearless. Once your inputs are valid, you can build whatever pipeline you like, with however many intermediate steps, and it will not fall over partway through for a reason you cannot see coming and do not control. That is especially important in interactive and automated systems. You would not want to ship a DCC tool that has to warn its users "please do not arrange your objects so that the result is not bounded by an ordinary 2-manifold," and you cannot reasonably ask a procedural pipeline to avoid configurations it does not even know it will generate. Closure is what lets you stop thinking about it.

Among the CGAL backends, only Nef has that closure on this case, which is why Nef finishes the chain and corefine stops at operation 5.

Toward a public benchmark

This is the third case we have written up properly, with images, videos, and tables. Behind it sits a much larger corpus of test cases we already run internally. We are steadily cleaning those up, writing dedicated posts for the noteworthy ones, and folding in real-world cases together with examples contributed by the various boolean libraries and their users. The published posts so far span an easy chain, deep iteration with coplanar seams, and now regular grid-aligned contact along faces, edges, and corners, with non-manifold intermediate states and a target that happens to be the empty set.

The runner infrastructure and build scripts are open source under the Open Boolean Benchmark org, at github.com/Open-Boolean-Benchmark/boolean-benchmark-runners. That org is where we will eventually collect and publish the full benchmark corpus and the interesting cases we run into along the way. 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. More cases are coming, with different geometries, operation types, and stress patterns.

Notes

The final result for this case is the empty mesh: the cubes are integer-aligned and the chain differences exactly the same set it unioned, so the solid is empty by construction. Because the grid is integer-aligned, the expected shape after each of the 1999 operations is also known exactly, so we run a per-step oracle and mark a run canonical only if it matches the expected shape at every step. Anything else is marked wrong. The Solidean baseline is 980.39 ms for the full chain (operation plus import).

The operation sequence is a 10x10x10 grid of unit cubes:

• result_0 = the first cube
• union in the rest of the even-parity cubes, one per step
• union in the odd-parity cubes, one per step (the grid is now a solid block)
• difference out the even-parity cubes, then the odd-parity cubes, one per step

That is 1999 boolean operations in total, and the running result of each operation is the input to the next, so the chain itself cannot be parallelized and errors accumulate.

As before, "Time" covers only the import (indexed triangle mesh to internal structure) and the boolean operations, no file IO and no export (which would be empty here at the end anyways). The measurement definition, system specs, library versions, and licensing are unchanged from the first benchmark post; see its Notes section for the full details. The one lineup change is Geogram, which now appears in versions 1.9.8 and 1.10.0 as described above.

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.