Paying for Editability: A Compilation Map for Learned Boolean Solids

Shapes that a neural network learns to describe as a combination of simple solids, called constructive solid geometry (CSG: a shape built by taking unions, intersections and differences of primitives such as boxes, quadrics and half-spaces), are the most CAD-like neural representations we have. Even so, the networks that learn them optimize for one thing, which is reproducing the shape with few primitives. They give no guarantee that the result can be edited locally, that its volume can be computed exactly, or that it can be combined with another solid cheaply. Logic researchers studied the same tension decades ago. In knowledge compilation, compact formats make questions about a formula hard to answer, and formats that make those questions easy cost extra size. That body of work catalogued which structural restrictions buy which guarantees.

This note proposes to carry that catalogue over to learned solids. It focuses on two restrictions. The first is determinism: the children of every "OR" node occupy disjoint regions of space. The second is structure: every solid splits space along a shared hierarchy of partitions, similar to a learned, non-axis-aligned octree. We then measure what these restrictions cost in size and accuracy on real CAD data, and what they buy in edit locality, exact volume, and cheap Boolean combination. A first theoretical observation reframes the whole question. In three dimensions, the exponential separations that dominate the logic literature largely collapse into polynomial ones. The real question is therefore the practical price of tractability, together with a test of whether learning under the restriction pays less than compiling afterwards.

Core Claim

Learned CSG models such as CSG-Stump and D²CSG are, in the language of A Knowledge Compilation Map, unrestricted Boolean circuits over "inside primitive $i$" literals:

  • CSG-Stump is a union of intersections of possibly complemented primitives, which is the geometric analogue of disjunctive normal form.
  • D²CSG is a difference of two such forms.

Neither enforces determinism, so editing one part of a union changes every overlapping part. Volume is not additive across children. Conjoining two learned solids gives no control over the size of the result.

We claim three things.

  1. Determinism is the formal property behind edit locality. It is enforced by making every OR node a sentential decision in the sense of the decision diagrams of SDDs Are Exponentially More Succinct than OBDDs, with "primes" that partition space and "subs" that are solids inside each part.
  2. A shared partition hierarchy plays the role of a variable tree. Under it, two solids can be intersected cell by cell, with output size bounded by the product of input sizes. This mirrors the polynomial-time conjoin of New Compilation Languages Based on Structured Decomposability.
  3. The price of these guarantees is polynomial in the number of primitives, not exponential, and it is lower when the structure is learned than when it is imposed afterwards.

The third claim is the empirical heart of the proposal and the one that could fail.

Where the Theory Actually Lands

The research file suggests that flattening CSG for gradient stability, as CSG-Stump does, might incur the exponential penalty that Bova proved for decision diagrams. On that result, the Hidden Weighted Bit function needs $2^{\Omega(n)}$ nodes as an ordered binary decision diagram but $O(n^3)$ as a sentential decision diagram.

We think this transfer is wrong, and saying so sharpens the project. Primitive literals in 3D are not independent Boolean variables. Every primitive is a function of the same three coordinates, so most of the $2^k$ truth assignments over $k$ primitives are geometrically impossible. A standard arrangement-counting argument from computational geometry shows that $k$ surfaces of bounded algebraic degree cut 3D space into $O(k^3)$ cells. Every Boolean solid over those primitives is therefore a union of at most $O(k^3)$ cells.

It follows that a deterministic, partition-structured representation never needs more than roughly cubically many pieces over the flat one. Neither flat nor structured forms can be exponentially separated in primitive count. The trade-off is real but polynomial.

That bound is no comfort in practice. D²CSG's 28.62 primitives on average could in the worst case imply tens of thousands of cells. Whether learned shapes sit near this worst case or near linear overhead is the open empirical question. A secondary theoretical goal is to characterize which shape families attain the cubic bound, such as interpenetrating overlaps and nested shells, and which admit linear-size deterministic forms. This would give a geometric counterpart to the separation results of A Lower Bound on the Size of Decomposable Negation Normal Form.

Research Program

The representation. We build a partitioned Boolean solid: a tree whose internal nodes split space with a learned function.

  • Splits are planes in the base version and quadrics in an extended version. A node is either a two-way split or a $k$-way soft-max partition.
  • Its leaves are small flat CSG blocks of the CSG-Stump kind, each confined to its cell.
  • By construction, the cells partition space. Every OR in the circuit is therefore deterministic, and the tree depth stays fixed. This addresses CSG-Stump's concern about irregular depth harming gradients.
  • Training follows D²CSG's unsupervised occupancy fitting on sampled points. Partition boundaries start as soft sigmoids and are annealed to hard assignments, and importance-based dropout prunes leaf primitives.
  • A compactness penalty counts total circuit nodes, not just primitives, because node count is the quantity the compilation map measures.

Tractable operations. We implement and analyze four operations against this representation.

  • Point membership is linear in tree depth plus leaf size.
  • Volume is the sum of per-cell volumes. When splits and leaf primitives are planar, each cell is a convex polytope and the sum is exact. With quadrics, it is computed by per-cell quadrature with an error bound attached to each cell.
  • Local edits replace or delete one leaf's sub-solid. Occupancy outside that cell is untouched by construction.
  • Boolean combination intersects two solids, or carves one with the complement of a tool solid. When both solids share a partition tree, this runs cell by cell. When they do not, we measure the refinement blowup, mirroring the gap between structured and unstructured decomposable circuits.

The structure question. In the "structured" setting, a partition tree is learned once per category, for example ShapeNet chairs, and shared across shapes. This tests whether a common spatial hierarchy can stand in for the shared variable tree without destroying accuracy.

Baselines

The naive reference point is D²CSG used as-is and edited the only way it allows: change the user-specified region's target occupancy and re-optimize the whole tree. D²CSG reports about 5 minutes per shape on an RTX 2080 Ti. This baseline shows what unrestricted circuits cost when an edit has to stay local.

The strongest existing method for compact learned CSG is D²CSG. On ABC it reports a Chamfer Distance of 0.069 with 28.62 primitives on average, against CAPRI-Net's 0.177 and 66.26 and BSP-Net's 359.38 primitives. On ShapeNet we compare against CSG-Stump, which reports a Chamfer Distance of 1.505 across 13 categories. The file reports no D²CSG number on ShapeNet. We rerun both baselines on identical point samples and the same shape splits, with matched per-shape optimization time and equal hyperparameter search budgets.

Beating D²CSG does not mean lower Chamfer Distance. It means three things together:

  • Chamfer Distance within about 10 percent of D²CSG's.
  • Total node count within a small constant factor, which the experiments will quantify.
  • Exact locality, exact or bounded volume, and conjoin cost that D²CSG cannot match.

The key ablation is a post-hoc compiler. It takes D²CSG's output and converts it into a deterministic partition form by refining the primitive arrangement, then merging cells with equal labels. If this compiler yields circuits as small as our learned ones at equal accuracy, the learning component adds nothing. A second ablation keeps our architecture but replaces the partition with overlapping soft children combined by union. This removes determinism alone and shows how much locality and volume accuracy depend on it.

A structured spatial baseline is an NSVF-style sparse octree, following Neural Sparse Voxel Fields. We put the same small CSG blocks at its leaves instead of feature vectors. This is deterministic and structured but axis-aligned and uniformly refined, so it tests whether learned split surfaces are needed at all.

Why not just…?

Why not just fit D²CSG and compile its output afterwards? This is the most serious threat. Classical conversion from CSG to cell decompositions exists, and the arrangement bound says the result is at most cubically larger. Our hypothesis is that unrestricted learned trees place primitives with many incidental overlaps, so compilation inflates them far beyond the size a structure-aware learner would produce. The post-hoc ablation measures exactly this, as node count versus Chamfer Distance on ABC. If the two curves coincide, we will report that tractability can be bolted on afterwards. The contribution then narrows to the compilation map and the operations, which remain useful.

Why not just use an octree, which is already deterministic and structured? It is, and that is why it is a baseline. NSVF's own account stresses the trade-off between resolution and memory. Axis-aligned splits must subdivide repeatedly to follow a slanted or curved CAD boundary that one learned plane or quadric captures. The octree-with-CSG-leaves comparison will show whether learned splits reduce node count at equal accuracy, and on which shape families. We expect the gain to be largest on ABC parts with oblique features and smallest on boxy furniture.

Why not just extract a mesh and use mesh Booleans and mesh volume? Meshes give exact volume, but they discard the compact parametric description that makes CSG useful for CAD. Discretizing smooth CAD geometry also degrades it: ABC reports learned normal estimators on meshed CAD lagging simple averaging by 8 to 10 degrees. We include marching-cubes meshes with a standard Boolean library as a reference for volume error and conjoin time, and we report their size in faces next to our node counts.

Why not just edit continuously with boundary sensitivity? Neural Implicit Shape Editing using Boundary Sensitivity handles small deformations well and even enforces volume constraints by projection. It is first-order, though, so it cannot drill a hole or join two parts. Our evaluation of topological edits covers exactly that regime. Where the edits are small, we compare deformations directly.

Proposed Experiments

Price of tractability. We fit all methods to the ABC test split used by D²CSG and to the 13 ShapeNet categories used by CSG-Stump. For each method we report:

  • Chamfer Distance.
  • Primitive count and total node count.
  • Fitting time, with all methods on the same GPU.

The decisive plot is node count against Chamfer Distance for four methods: our learned partitioned solid, the compiled D²CSG, the octree-leaf baseline, and the no-determinism ablation.

Worst-case families. On synthetic shapes with a controlled number $k$ of primitives, we test whether the deterministic size grows as $k^3$ or near-linearly. The families are random overlapping unions, nested shells, and interpenetrating lattices. This checks the polynomial-collapse prediction directly.

Volume. Ground-truth volumes come from ABC's boundary-representation models. We compare our per-cell sums against Monte Carlo estimation on D²CSG at equal compute.

Locality. We apply 500 scripted edits per method to ABC shapes. Each edit deletes a feature, carves a hole, or adds a boss. We measure the change in occupancy outside the edited region, using IoU between unedited regions before and after the edit, along with edit latency. Our method should show exactly zero change outside the region. The re-optimized baseline will show measurable drift; the file has no reported number on Lacuna for edit drift of D²CSG or CSG-Stump.

Boolean combination. For pairs of ShapeNet shapes within a category, we intersect and subtract them under a shared partition tree and under separate trees. We report output size against the product bound and wall-clock time.

The project succeeds if three things hold. The learned representation's node count stays within a small constant of D²CSG at comparable Chamfer Distance. It is clearly smaller than the post-hoc compiled baseline. The shared-tree Booleans stay near the product bound while separate-tree Booleans blow up. If compiled D²CSG matches us, the learning claim fails cleanly and the compilation map stands on its own.