Improved Convex Decomposition with Ensembling and Boolean Primitives

Thanks for reading our paper and offering positive feedback.

8. Cost of Ensembling

Please see Tables 1 and 3 for detailed timing breakdowns. Individual models we trained require betewen 0.84 to 2.06 seconds. This is over an order of magnitude faster than prior work (40 seconds), while simultaneously achieving better error metrics. For $K^{total}=12$, our method is more parameter-efficient. We agree that real-time primitives are the future - this work takes a significant step in that direction. While there is a fixed cost in generating primitives and rendering them, applying post-training finetuning dominates the compute time and can be varied in length based on desired latency requirements - see Fig. 6, 13, and 14 for tradeoffs.

9. Optimal Ratio of Negative Primitives in CSG Modeling

In Constructive Solid Geometry (CSG), we represent 3D objects using boolean operations on primitive shapes. For a fixed budget of $K^{total}$ primitives, we aim to determine the optimal ratio of negative primitives ($K^-$) to positive primitives ($K^+$) that maximizes representational efficiency.

A CSG model can be described as: $\text{Object} = (P_1 \cup P_2 \cup ... \cup P_{K^+}) - (N_1 \cup N_2 \cup ... \cup N_{K^-})$

Where $P_i$ are positive primitives and $N_j$ are negative primitives, with $K^+ + K^- = K^{total}$.

Definitions:

• Primitive Interaction: Overlapping volumes creating representational complexity
• PP Interaction: Between two positive primitives
• PN Interaction: Between a positive and negative primitive

Assumptions:

1. Only positive volumes and their modifications by negative primitives are visible in the final result
2. The representational power comes primarily from PP and PN interactions
3. Primitives are distributed to maximize meaningful interactions
4. Optimal representation maximizes visible features per primitive used
5. Assume connected geometry

Mathematical Model:

1. PP Interactions: $\binom{K^+}{2} = \frac{K^+(K^+-1)}{2}$
2. PN Interactions: $K^+ \cdot K^-$

Balancing PP and PN Interactions

For optimal efficiency, PP and PN interactions should be balanced:

$\frac{K^+(K^+-1)}{2} \approx K^+ \cdot K^-$

Substituting $K^+ = K^{total} - K^-$ and simplifying: $\frac{(K^{total} - K^-)(K^{total} - K^- - 1)}{2} \approx (K^{total} - K^-) \cdot K^-$

$\frac{K^{total} - K^- - 1}{2} \approx K^-$

For large $K^{total}$: $\frac{K^{total} - K^-}{2} \approx K^-$

Solving: $K^{total} \approx 3K^-$ $K^- \approx \frac{K^{total}}{3}$

Thus, $K^+ \approx \frac{2K^{total}}{3}$

Verification With this ratio, both interaction types equal approximately $\frac{2(K^{total})^2}{9}$, confirming our balance criterion.

Why This Balance Is Likely Reliable

1. Diminishing Returns: As $K^-$ increases beyond the optimal ratio, each additional negative primitive becomes less effective because:

   • Negative primitives can only remove existing positive volume
   • Available positive volume decreases with fewer positive primitives

2. Complementary Information: PP and PN interactions contribute equally valuable but different information:

   • PP interactions define the overall positive volume
   • PN interactions create necessary concavities and details

3. Maximum Information Content: The ratio $K^- = K^{total}/3$ provides:

   • Sufficient positive primitives to establish base structure
   • Optimal negative primitives to efficiently carve features
   • Maximum meaningful visible interactions per primitive

Empirical Evidence and Practical Verification

Our quantitative evaluation supports an optimal $K^- ≈ K^{total}/3$ in Tables 4-7. Observe how depth and segmentation metrics tend to be highest when $K^{total}/K^-$ are near 36/12, 24/8, and 12/4.

10. Depth Estimation Model

NYUv2 has supervised depth and camera calibration parameters; for our method to work on real-world scenes, we need to extract a point cloud from in-the-wild images. To do so, we select a recent SOTA depth estimation model https://github.com/DepthAnything/Depth-Anything-V2/tree/main/metric_depth. We then make reasonable camera calibration assumptions to obtain a point cloud (see Sec. 4.3). We anticipate as better depth estimation models become available, our model will naturally generate better primitives.

11. Missing References

Primitive fitting is a relatively niche area in the CV community, as compared with hot topics like NeRFs and Diffusion Models. With that said, we cited four papers from 2024. More importantly, we have covered the key references in this area and we perform comparative evaluation on all of the recent works in this topic. We are happy to include any others you feel we have missed.

Thanks for taking the time to look at our work.

7. Value of Negative Primitives

You make a great point - all methods produce good results on average. We don’t claim that quality keeps improving as we increase negative primitives beyond a point. Instead, our aim is to show it’s possible to fit CSG in the first place, and doing so improves the quality of primitive fits on average (e.g. Fig. 7). Notice that most of the time, a solution with boolean primitives is chosen, indicating they are genuinely useful in shape abstraction.

Fig. 7: we should have been more clear about our central claim: we do not claim that quality keeps improving as we replace replace positive primitives with boolean primitives. Theory, intuition, and experimentation instead support some optimal intermediate value with a mixture of boolean and positive primitives near $K^-=K^{total}/3$. Therefore, Fig. 7 actually makes our point: different scenes require different numbers of primitives, but on average having some boolean primitives is helpful.

You pointed out that the normals got slightly worse with more boolean primitives. We investigated and found that we did not align the methodologies to compute normals. For GT Normals, we computed finite differences of the point cloud. For predicted normals from the primitives, we calculated the gradient of the SDF at the intersection point consistent with [1]. This is now fixed, with finite difference being used for normal computation everywhere. Updated Table 1 above shows the corrected metrics; we will update all tables in the paper accordingly. Observe how depth and normals get better with boolean primitives and ensembling.

While Figs. 4, 5, and 10 demonstrate some boolean primitive examples, here are a few more results emphasizing boolean primitives. The headers of each column indicate $K^{total}/K^-$. The normals make it clear that the boolean primitives are carving away geometry and significantly enrich the shapes we can encode. https://drive.google.com/file/d/18hkwD4UdkCe97U8yFoZEjZaXLVvw-Atk/view.

You made an important observation about our results. Boolean primitives are a mechanism for increasing the types of shapes we can encode, but we can just increase the total number of primitives in lieu of making some of the primitives negative. Thus, intuition would suggest that at higher primitive counts, boolean primitives don’t offer as much of an advantage than at smaller primitive counts, because having lots of primitives available is already quite expressive. This is precisely what we observe on NYUv2, where at $K^{total} = 36$, models with and without boolean primitives perform comparably well as you noticed. At smaller primitive counts ($K^{total} \in {\{12,24\}}$), having some of the primitives be negative helps on average. In fact, in Table 7 in our paper, at all primitive counts boolean primitives are helpful on average. For $K^{total}=12$, picking 4 booleans improved AbsRel 0.0719 -> 0.0659. For 24 primitives, having 4 or 8 booleans reduced AbsRel 0.059 -> 0.0525.

On LAION, Table 5 in our paper, there is more data to supervise the larger primitive count and we do see an improvement for 36 total primitives if we let 16 of them be boolean (0.0771 -> 0.0719).

Of critical note, our method works on "in-the-wild" natural images, which can be incredibly diverse. It’s hard to know in advance what is the best number of primitives for a given test image. That’s why ensembling is so valuable because we don’t need to just use one model that gives the best AbsRel on average; we can run a few models with different mixtures of $K^{total}$ and $K^-$ and choose the best one. Given all the performance improvements we made to primitive detection, ensembling is quite feasible, depending on the use-case.

Thanks for identifying this point and we will make this clear in the final version.

Additionally, there is a bias-variance tradeoff in our work. Adding primitives reduces bias (you can encode things more accurately) but increases variance (harder to get all the primitives right). But adding a negative primitive significantly reduces bias and also significantly increases variance -- as above, one negative can be worth several positives. This means that the best setting likely has a mixture of positive and negative primitives, with positives favored. Adding negative primitives yields better results but adding too many quickly creates variance problems.

[1] Vavilala, V. and Forsyth, D., 2023. Convex decomposition of indoor scenes. In Proceedings of the IEEE/CVF International Conference on Computer Vision (pp. 9176-9186).

Additional Notes

Thanks for the suggestions to polish the writing - we will do so for the final version. Note that we evaluate against "Cuboids Revisited" in Table 4; "Robust Shape Fitting..." is the journal version that has identical error metrics. Also, please see 1. Global Comment & 3. Analysis of Downstream Tasks above.

Thanks for reviewing our paper.

4. Theoretical Analysis

Multiple reviewers expressed interest in theoretical justification as to why boolean primitives are advantageous in fitting complex real-world scenes. We provided qualitative evidence in Fig. 3, in which we model a cube with a hole punched in it. Intuitively, one positive and one negative primitive are sufficient to model it perfectly (2 total primitives). Without CSG, approx. 5 primitives may be required, which is less parameter-efficient. Based on that, we can sketch a theoretical argument as to why having a vocabulary of mixed positive and negative primitives is expected to yield more accurate representations than the same number of positive-only primitives.

Kolmogorov Complexity Perspective

For many objects, the description length (Kolmogorov complexity) using mixed primitives is significantly shorter than using positive-only primitives: For a shape S:

Let K₊(S) = minimum description length using only positive primitives Let K±(S) = minimum description length using mixed primitives

Theoretical result: For many shapes with concavities, K±(S) << K₊(S)

Example: A simple cube with a hole requires just 2 primitives with mixed CSG (1 positive cube, 1 negative cube) but would require numerous small positive primitives to approximate the concavity with positive-only CSG.

5. Error Propagation

You raise an important point: in the absence of GT depth/normals for in-the-wild images like LAION, we use a pretrained network to estimate depth, from which we use a standard heuristic (finite differences) to obtain GT normals. Single image depth predictors are very strong and reasonable choices when GT is not available. Our convex decomposition procedure uses this inferred depth when generating primitives (RGBD input), and we evaluate the quality of these primitives based on the provided depth. In effect, the claim that we make in this work is that our model gives the user what was asked for. When we report low AbsRel, it means our model adheres to the input depth.

As better depth estimation models become available, our procedure will naturally get better, although a small amount of finetuning may be required if switching depth estimation models due to differences in the statistics of each depth predictor’s output.

6. Ambiguity in Face Labeling

When computing segmentation accuracy with boolean primitives, we compute the triple ($f_i,K^+_j,K^-_k$) at each ray intersection point, where $i$ is the face index, $j$ is the index of the positive primitive we hit, and $k$ is the index of the (potentially) negative primitive we hit. Each unique triple can get its own face label. Thus, given a fixed primitive budget $K^{total}$, replacing a pure positive primitive representation with a mixture of positives and negatives can yield more unique faces. For example, $K^+/K^-$ = $12/0$ maxes out at $12f$ unique faces; $K^+/K^-$ = $6/6$ maxes out at $42f$ faces. Note that $f\times K^+ \times (1+K^-)$ is the theoretical maximum of unique labels, as practical scenes do not involve every primitive touching every other primitive.

Additional Notes

Please see 1. Global Comment & 3. Analysis of Downstream Tasks above and 8. Cost of Ensembling & 9. Optimal Ratio of Negative Primitives below.

Thanks for the feedback on our paper.

1. Global Comment

We'd like to refresh the reviewers with a summary of our contributions:

1. We depart from the limited NYUv2 dataset used in existing primitive-fitting papers and show how to make primitive-fitting work on real-world natural images via a portion of the LAION dataset. We can compute primitives for almost any natural image.
2. We are the first (to our knowledge) to fit CSG to natural images and demonstrate that a mixture of positive and negative primitives is advantageous on average.
3. As discussed in the method section, we analyze every aspect of data generation and training, including hyperparameter tuning, such that every model we train (even without boolean primitives and ensembling) outperforms existing work on established benchmarks -- often while using fewer primitives and less compute.
4. We are the first to use ensembling to find the optimal number of primitives for a given test image, which simultaneously improves geometric accuracy.
5. By analyzing and improving our post-training finetuning process, we are the first to show that it's possible to fit 3D primitives to data without a neural network to predict a start point.
6. The authors commit to open-source the training and inference code.

2. Missing Ablations

We ablated and analyzed key components of our method, including sweeps of $K^{total}$ and $K^-$ (Tables 1, 4, 5), two forms of ensembling ($S\rightarrow R$ and $R\rightarrow S$) in Tables 2, 4, and 5; the number of faces per primitive (we do both the traditional 6-faced cuboid and show that extending to higher-faced polytopes e.g. 12-faced helps in Table 2). We also analyze the time and memory of individual networks and different forms of ensembling, including breakdowns of each stage of our pipeline, in Tables 1 & 3.

Further, we analyze both the benchmark NYUv2 dataset and, for the first time in 3D primitive generation, natural LAION images in-the-wild (Fig. 5).

Another key ablation is network start vs. optimizing primitives directly (Fig. 6). We aggressively analyzed and improved the optimization process of 3D primitives from data, such that, for the first time to our knowledge, we can get good 3D primitives from RGB images without a neural network providing a start point. However, having a network start is advantageous in terms of quality and speed.

We are happy to add more ablations that the reviewers feel would be helpful.

3. Analysis of Downstream Tasks

We present qualitative examples of using primitive abstractions to edit images (that is part of a separate, concurrent work) in Figures 8, 15, and 16. It's helpful to grab and move objects in a scene. Primitives are a great candidate to simplify user-interaction especially in cluttered real-world environments [1]. For robotics, we are aware of 3D primitives used for fast collision checking, sampling-based planning, physics simulations, robotic manipulation, procedural scene generation and shape approximation (and likely much more).

For both image generation and robotics, we want primitives that are accurate, fast, and can be generated from in-the-wild data. Our paper specifically improves accuracy, speed, and real-world generalization. To evaluate, we use established depth, normal, and segmentation error metrics, which are reasonable for downstream use-cases we can envision right now. Given the scope of this project focused on obtaining better primitives, investigating these downstream use-cases is future work.

[1] Bhat, S.F., Mitra, N. and Wonka, P., 2024, July. Loosecontrol: Lifting controlnet for generalized depth conditioning. In ACM SIGGRAPH 2024 Conference Papers (pp. 1-11).

Additional Notes

Please see 4. Theoretical Analysis, 7. Value of Negative Primitives, and 11. Missing References below.

Updated Table 1