Certified Boolean Assembly for Mesh-to-CAD Reconstruction

Programs that turn a scanned or meshed part back into an editable CAD model usually work in two stages. First they propose many candidate shape operations, such as extruded sketches and revolved profiles. Then they decide which of those candidates to add, which to cut away, and in what order. The strongest current system does the second stage greedily: it repeatedly picks the operation that most improves overlap with the target, then prunes. This proposal replaces that greedy step with an exact integer program.

The key observation is simple. Fix the candidate pool, and write the solid in a bounded alternating form: add some candidates, cut some, add some more, cut some more. Then whether any small piece of space ends up filled is a linear-constraint function of 0/1 selection variables. So the whole assembly problem becomes an integer linear program. Its objective is the misclassified volume plus a price per operation. The program can be solved exactly for typical pool sizes. Its linear programming relaxation, which lets each selection variable take fractional values between 0 and 1, gives a lower bound. That bound certifies how far any assembly, greedy or otherwise, is from the best assembly the pool admits.

This yields three things greedy search cannot give. It yields better reconstructions when cuts interact with several earlier additions. It yields a per-shape optimality certificate. And it removes the geometry kernel from the inner search loop. Kernel calls are the main reason current hybrid systems take minutes per shape.

Core Claim

The claim is that, given a fixed candidate pool, the combinatorial part of mesh-to-CAD reconstruction can be solved to certified optimality, or to within a certified gap, in seconds, and that doing so measurably improves accuracy and conciseness over greedy assembly on hard parts. The file contains no existing work that formulates CAD operation assembly as a mathematical program.

The closest system is CADFit. It generates sketch candidates, sweeps their continuous parameters against a one-sided Chamfer distance, and then selects UNION and CUT operations greedily by volumetric overlap (intersection over union, IoU), followed by backward pruning. CADFit motivates this work because it shows that kernel-in-the-loop fitting gives 0% invalid programs. Its selection step, however, is myopic and carries no guarantee.

Inferring CAD Modeling Sequences Using Zone Graphs is the closest structural ancestor. It cuts space into atomic "zones" by extending the faces of the input model into infinite surfaces, so that every modeling step becomes a choice of zones. We borrow this discretization. The difference is that we assign cells from candidate primitives rather than from the final model's faces, and we solve the selection with a mathematical program instead of a search guided by a graph neural network.

D2CSG supplies the representational idea that a solid can be written as a cover minus a residual. We generalize this to a bounded number of add/cut alternations and turn its heuristic dropout pruning into an explicit per-operation cost.

The Formulation

We sample the target's bounding box densely and record, for each sample point, which candidates contain it. Points that share the same membership pattern form one cell. Each cell carries the volume weight of its points and a target label: inside the target mesh, outside, or mixed.

This step needs only point-in-solid tests. It is done once, and it replaces the thousands of Boolean kernel evaluations that greedy search performs. The number of distinct cells is bounded by the number of distinct membership patterns, not by the sample count.

The assembly has $K$ levels, with $K$ equal to 2 or 3. Level $k$ has two kinds of 0/1 variables:

  • $a_{jk}$, which equals 1 when candidate $j$ is added at level $k$;
  • $r_{jk}$, which equals 1 when candidate $j$ is cut at level $k$.

Cell $c$ has occupancy variables $z_{ck}$ after each level, starting from $z_{c0} = 0$. For each level, the occupancy is linearized as follows. Adding can only switch a cell on, and only if the cell was already on or some selected added candidate contains it. Cutting switches the cell off if any selected cut candidate contains it. Each of these relations becomes a handful of linear inequalities, $O(|c|)$ per level in total, in the standard way for linearizing OR and AND over 0/1 variables.

The objective is

$$\min \; \sum_c w_c \,\big|z_{cK} - t_c\big| \;+\; \lambda \sum_{j,k} \big(a_{jk} + r_{jk}\big),$$

where $w_c$ is the cell's volume, $t_c \in \{0,1\}$ is its target label, and $\lambda$ is the price of one operation. Because $t_c$ is fixed, the absolute value is linear. The first term is the misclassified volume, which maps directly to IoU. The second term plays the role of the conciseness score in Fusion 360 Gallery.

Choosing $K=1$ recovers D2CSG's cover-minus-residual form. Choosing $K \geq 2$ handles designs such as a boss placed inside a pocket, which a single cover-minus-residual cannot represent.

The file suggests borrowing a different formulation, which we are not adopting. It suggests submodular maximization with swap rounding, from the nearly-linear knapsack algorithm and from EQUATOR. Cut operations make the overlap objective non-monotone and non-submodular. As a result, the $(1-1/e)$ guarantees of that literature do not transfer, and claiming them would be dishonest.

We therefore replace the a-priori guarantee with an a-posteriori one. The linear program's value bounds the best achievable objective from below. We take swap rounding only as a mechanism. When a hard budget on the number of operations is imposed, swap rounding turns fractional selections into 0/1 selections while keeping that budget exactly. It preserves each variable's marginal probability, and we draw several rounded samples and keep the best one.

For large pools, we solve the linear program, fix the variables that come out integral, and hand the small remaining fractional core to an exact solver. This is a practical cousin of the "controlled fractionality" idea in Ene and Nguyen. It keeps only a few variables fractional, and it avoids their impractically large constants.

Research Program

We will first rebuild a CADFit-style candidate generator. It uses planar slicing and face clustering for sketches, parameter sweeps for extrusion and revolution, and OpenCascade through CadQuery for execution. If CADFit's code is released, we will reuse it directly, so that the candidate pool is identical across all assembly methods.

On top of that pool we build four things:

  • the cell construction;
  • the $K$-level integer program, solved with an open-source mixed-integer solver;
  • the linear relaxation with fix-and-solve;
  • the swap-rounding variant.

The final selection is executed once in the kernel. This keeps CADFit's validity guarantee, because every emitted program is a real kernel construction. Fillets and chamfers are applied afterward, exactly as in CADFit.

The analysis has two parts. First, we measure the empirical integrality gap on real parts: how often the linear program is already integral, and how large the fractional core is. Second, we measure how often greedy assembly is provably suboptimal.

Baselines

The naive reference points are two simple assemblies from the same candidate pool. The first is the single best candidate. The second is the union of all candidates with positive marginal overlap and no cuts. These show how much of the problem the candidate pool alone solves.

The strongest existing method is CADFit's greedy IoU assembly with backward pruning, run on exactly the same candidates, with a matched wall-clock budget and CADFit's published pruning rule. The file's quantitative claims about CADFit are relative. It more than doubled the median IoU of CAD-Recode on ABC Hard. It had a 0% invalid rate, while baselines reached up to 39%. It outperformed CAD-Coder by over 50% in IoU on easy image-to-CAD shapes.

No reported absolute median IoU for CADFit on any split was found on Lacuna. We will therefore rerun it rather than quote it. Beating it means two things on ABC Hard and on the DeepCAD complex subset: a higher median IoU at equal or lower operation count, and a statistically significant win on paired per-shape comparisons.

On Fusion 360 Gallery, the external reference is the zone-graph method. It reports 80% exact reconstruction, 0.72% median error, and 242 s per model on its 440-model test split, all from Inferring CAD Modeling Sequences Using Zone Graphs. We will evaluate on that split and report exact reconstruction and conciseness.

Two ablations isolate the key ingredient. The first is linear-programming solution followed by independent thresholding at 0.5, which mimics CSG-Stump-style hard thresholding. The second varies $K$ over 1, 2, and 3. We will also run a greedy variant that shares our cell-based fast objective. This separates the gain from exact optimization from the gain from simply removing kernel calls.

Why not just…?

Why not just keep greedy with backward pruning, since it already works? This is a real threat, and the experiment settles it directly. On every shape we compute the linear-programming lower bound, so we can report the certified gap of CADFit's greedy solution. If greedy sits within about 1% of the bound on most ABC Hard shapes, the headline becomes "greedy is near-optimal, and here is the certificate." We would then recommend the formulation mainly for its speed and its verification value.

We expect greedy to be clearly suboptimal where cuts interact with several additions. D2CSG's high-genus ABC subset, where it reports 0.069 Chamfer distance and 28.62 primitives versus CAPRI-Net's 0.177 and 66.26, is where we will look for this effect.

Why not just use beam search or simulated annealing over the same pool? These are cheap to run on the fast cell objective, so we will run both at matched time budgets. They yield good solutions but no bound. The comparison shows whether exact solving buys accuracy beyond what extra search buys. It also shows whether the certificate is the main contribution.

Why not just use soft Boolean relaxations as in CSG-Stump? CSG-Stump replaces min and max with weighted softmax and thresholds the result, reaching 1.505 Chamfer distance on ShapeNet. Its relaxation is non-convex and gives no bound. Our thresholding ablation measures what ad-hoc rounding costs relative to exact solving.

Why not just let an LLM emit the program, as in CAD-Recode? This is complementary rather than competing. Its output can seed the candidate pool. The file's evidence of invalid ratios up to 39%, and of CADFit doubling CAD-Recode's IoU on hard shapes, argues against using it as the assembler.

Proposed Experiments

We will use the ABC stratified splits (Easy, Medium, and Hard by face count) from the ABC dataset, the DeepCAD complex subset from DeepCAD, and the Fusion 360 zone-graph test split. The metrics are:

  • IoU and Chamfer distance;
  • invalid rate;
  • operation count and conciseness;
  • wall-clock time and number of kernel calls;
  • the certified optimality gap.

The first decisive check is the distribution of greedy's certified gap on ABC Hard, which answers whether the problem is worth solving exactly. The second is an oracle-pool experiment. We inject the ground-truth operations into the candidate pool and test whether the integer program recovers them, while greedy does not. This separates assembly failures from candidate-generation failures.

The third check is scaling. We record solve time and fractional-core size against pool size, to establish where fix-and-solve and swap rounding become necessary.

Finally, we sweep $K$ to measure how much order dependence matters on real designs. If $K=1$ matches $K=2$ on nearly all shapes, the cover-minus-residual form of D2CSG is empirically sufficient for assembly. That would be a clean and useful result in its own right.