💻 computer science

Improved Convex Decomposition with Ensembling and Negative Primitives

This paper proposes an improved convex decomposition method that utilizes ensembling to dynamically determine the number of primitives and incorporates negative primitives via set-differencing, achieving substantial improvements in depth representation and segmentation accuracy over state-of-the-art methods on both NYUv2 and LAION datasets.

Original authors: Vaibhav Vavilala, Florian Kluger, Seemandhar Jain, Bodo Rosenhahn, Anand Bhattad, David Forsyth

Published 2026-03-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vaibhav Vavilala, Florian Kluger, Seemandhar Jain, Bodo Rosenhahn, Anand Bhattad, David Forsyth

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are looking at a messy room and trying to describe it to a robot so it can clean it up. You could say, "There's a chair, a table, a lamp, and a hole in the floor." But if you tried to describe that room using only simple, solid blocks (like Lego bricks), you'd run into a problem: How do you describe a hole?

If you only have solid blocks, you'd have to build the chair around the hole, using dozens of tiny blocks to carve out the empty space. It would be clumsy, inefficient, and inaccurate.

This paper introduces a new way for computers to "see" and describe 3D worlds. It solves the "hole problem" and makes the computer's description much smarter and more accurate. Here is the breakdown using simple analogies:

1. The Problem: The "Solid Block" Limitation

Previous methods tried to describe a scene using only positive primitives (solid shapes like boxes, cylinders, or pyramids).

The Analogy: Imagine trying to sculpt a statue of a person holding a cup. If you only have clay (positive shapes), you have to build the whole arm and then try to mold the cup out of the clay. It's hard to get the details right, and you might end up with a weird, lumpy arm.
The Result: The computer's description of the room was often "blobby" or missed details like holes in donuts, gaps between chair legs, or the space under a desk.

2. The Solution: Introducing "Negative Primitives" (The Cookie Cutter)

This paper's big breakthrough is adding Negative Primitives.

The Analogy: Instead of just having clay, you now have cookie cutters. You can build a big block of clay (a positive primitive) and then use a cookie cutter (a negative primitive) to punch a hole in it.
How it works: The computer builds a solid shape and then "subtracts" other shapes from it. This allows it to perfectly describe concave shapes (like a bowl) or holes (like the center of a donut) using very few pieces.
The Benefit: It's like going from building a house with thousands of tiny bricks to building it with a few large walls and a few precise cutters. The result is a much cleaner, more accurate 3D model.

3. The "Taste-Test" Strategy (Ensembling)

One of the hardest questions in this field is: "How many shapes do I need to describe this specific room?"

The Old Way: The computer had to guess a fixed number (e.g., "I will always use 20 blocks"). If the room was simple, it used too many. If the room was complex, it used too few.
The New Way (Ensembling): The authors trained 18 different "experts" (neural networks). Each expert is an expert at using a different number of shapes (some use 12, some 24, some 36).
The Process: When the computer looks at a new image, it asks all 18 experts to build a model. Then, it acts like a taste-tester:
1. It checks which model fits the photo best (like tasting 18 different cookies to see which one is the sweetest).
2. It picks the winner.
3. It gives that winner a little bit of "polishing" (fine-tuning) to make it perfect.
The Result: The computer automatically adapts. A simple room gets a simple model; a complex room gets a complex model. It finds the "Goldilocks" zone every time.

4. Why Does This Matter?

This isn't just about making pretty pictures. It has real-world uses:

Robotics: If a robot wants to pick up a cup, it needs to know exactly where the cup is and where the empty space is so it doesn't crash. This method gives the robot a much clearer map.
Image Editing: Imagine you want to move a chair in a photo to the left. If the computer understands the chair as a simple 3D object, it can move it easily. If it just sees pixels, moving it is a nightmare. This method makes editing photos feel like moving physical objects.
Efficiency: Because the computer uses "cookie cutters" (negative primitives), it can describe complex scenes with fewer total pieces, saving computing power.

Summary

Think of this paper as teaching a computer to be a master sculptor instead of a clumsy brick-layer.

Negative Primitives: It learned to use "subtractive" tools (like chisels) to carve out holes and curves, not just add blocks.
Ensembling: It learned to hire a team of specialists and pick the one who did the best job for the specific task at hand.

The result is a system that can look at a messy photo of a room and instantly build a highly accurate, 3D digital twin of it, understanding not just what is there, but also what is missing (the holes and gaps).

1. Problem Statement

The paper addresses the challenge of 3D scene decomposition, which involves representing complex scenes as a collection of simple, geometric primitives (e.g., convex polytopes). This is a fundamental problem in computer vision with applications in image editing, motion planning, and robotic grasping.

Existing methods face three primary limitations:

Fixed Complexity: Most approaches predict a fixed number of primitives, failing to adapt to scenes of varying complexity (some scenes require few primitives, others many).
Geometric Limitations: Traditional methods rely on positive primitives (unions of convex shapes). This makes it difficult to efficiently model concavities, holes, or voids (e.g., the hole in a donut or the space under a chair) without using an excessive number of primitives, leading to over-segmentation.
Fitting Difficulty: Current state-of-the-art (SOTA) methods often struggle with initialization, getting stuck in local minima, or lacking the precision to tightly fit specific input geometries.

2. Methodology

The authors propose a hybrid approach combining neural regression, test-time optimization, and Constructive Solid Geometry (CSG) operations.

A. Negative Primitives and CSG

The core innovation is the introduction of negative primitives.

Concept: Instead of only adding shapes (unions), the model can subtract shapes (set differencing).
Representation: The scene volume $O(x)$ is defined as the difference between positive primitives $O_+(x)$ and negative primitives $O_-(x)$ :
$O(x) = \text{relu}(O_+(x) - O_-(x))$
Benefit: This allows the model to "carve out" complex concavities and holes using very few parameters. Theoretically, a shape with a hole can be represented by 1 positive and 1 negative primitive, whereas a convex-only approach might require 5+ primitives to approximate the same geometry.

B. Test-Time Ensembling for Model Selection

To solve the problem of choosing the optimal number of primitives ( $K_{total}$ ) and the ratio of negative primitives ( $K_-$ ) for a specific scene, the authors employ an ensembling strategy:

Training: They train 18 distinct models, each targeting a different combination of total primitives ( $K_{total} \in \{12, 24, 36\}$ ) and negative primitives ( $K_- \in \{0, 4, \dots, K_{total}-4\}$ ).
Inference Strategies:
- S $\to$ R (Select then Refine): Run all 18 models, select the one with the best initial prediction based on a fast metric, and refine it.
- R $\to$ S (Refine then Select): Refine all 18 models using test-time optimization, then select the one with the lowest error.
Adaptive Selection: This data-driven approach dynamically selects the level of abstraction (number of primitives) best suited for the input image, rather than relying on a fixed hyperparameter.

C. Hybrid Optimization (Regression + Descent)

The method uses a "regress-then-descent" pipeline:

Regression: A ResNet-18 based CNN predicts initial parameters for the primitives from an RGBD input.
Polishing (Test-Time Descent): The predicted primitives are further optimized using gradient descent against the input depth map.
- Key Finding: The network initialization is crucial. Starting from a random point requires ~1000 iterations to converge, whereas starting from the network prediction requires only ~200 iterations to achieve superior accuracy.
- Optimization: The authors use AdamW and specific sampling strategies to refine the geometry, achieving high precision without getting stuck in poor local minima.

3. Key Contributions

First CSG Fitting for In-the-Wild Scenes: The paper presents the first method capable of fitting CSG models (including set differencing/negative primitives) to raw, unsegmented RGB-D images of real-world scenes.
Test-Time Ensembling: A novel procedure that dynamically selects the optimal number of positive and negative primitives for each scene, outperforming any single fixed-count model.
State-of-the-Art Accuracy: The method achieves significant error reductions (over 50% relative error reduction in depth) compared to prior SOTA on the NYUv2 benchmark.
Large-Scale Viability: The authors demonstrate the method's scalability by successfully fitting primitives to over 1.8 million images from the LAION dataset, showing strong generalization to "in-the-wild" data.

4. Results

The method was evaluated on NYUv2 (indoor scenes) and LAION (in-the-wild images).

Quantitative Performance (NYUv2):
- Depth: Achieved an AbsRel of 0.0417 (best ensemble), significantly outperforming the previous SOTA (Vavilala & Forsyth [62] at 0.098 and Kluger et al. [29] at 0.098).
- Segmentation: Improved SegAcc from 0.618 (SOTA) to 0.756.
- Normals: Reduced mean angle error to 31.9°.
- Efficiency: Despite the ensembling cost, the method is faster than prior SOTA (29.9s vs. 40s for the full ensemble vs. previous methods).
Qualitative Findings:
- Negative Primitives: The ensemble frequently selects models with negative primitives (optimal ratio found empirically to be $K_- \approx K_{total}/3$ ). These are essential for modeling holes, undercuts, and complex furniture.
- Adaptability: The system successfully handles simple scenes with few primitives and complex cluttered scenes with many, avoiding the "one-size-fits-all" failure of fixed-count models.
- LAION Performance: The method generalizes well to natural images, achieving even lower depth errors (AbsRel ~0.019) on LAION, likely due to the larger and more diverse training data.

5. Significance

This work represents a significant leap in 3D scene understanding by bridging the gap between compact geometric representations and high-fidelity accuracy.

Theoretical Insight: It provides a theoretical and empirical proof that set differencing is exponentially more efficient for representing concave geometries than unions of convex shapes alone.
Practical Application: By enabling accurate, compact, and editable 3D representations, the method facilitates advanced applications such as image editing (moving objects in a scene), robotic grasping (understanding voids and occlusions), and motion planning.
Scalability: Demonstrating success on 1M+ images suggests that primitive-based scene decomposition is a viable path for large-scale 3D understanding, moving beyond controlled indoor datasets to the open web.

In summary, the paper solves the "complexity vs. accuracy" trade-off in 3D decomposition by using negative primitives to handle concavity and ensembling to adapt model complexity to the scene, resulting in a robust, high-accuracy system that outperforms all existing baselines.