Convex decomposition

• Also called: approximate convex decomposition, ACD
• Category: Software & tooling › Simulation & twins
• Tags: collision-detection, simulation, geometry-processing, meshes, contact

Splitting a non-convex shape, usually a triangle mesh, into a set of convex pieces whose union approximates it, so that fast convex collision algorithms can be used.

Definition

Convex decomposition breaks a non-convex shape into a collection of convex parts whose union reproduces or approximates the original. In robotics the input is usually a triangle mesh of an object, a gripper or a robot link, and the output is a set of convex hulls used as its collision geometry. The reason is algorithmic: the standard narrow-phase collision and distance routines, such as GJK and EPA, work on convex shapes, and many physics engines either require convex geometry for moving bodies or silently replace a mesh with its single convex hull. A mug represented by one hull has no opening and no handle hole; a decomposition restores those features as several convex pieces.

An exact decomposition of a polyhedron can need a very large number of parts, and finding the minimum number is computationally hard, so practical tools compute an approximate convex decomposition. They split the shape until every piece is convex within a chosen tolerance, measured by a concavity metric such as the distance between a piece and its own convex hull. V-HACD has long been the common choice in simulation pipelines; CoACD is a newer collision-aware method that cuts the mesh directly and tries to preserve features that matter for contact, such as thin walls and openings. Both expose parameters for the concavity threshold and the maximum number of parts.

The result is a trade-off between fidelity and cost. More pieces follow the true surface more closely but slow down collision checking and make contact generation noisier where pieces meet; fewer pieces are fast but fill in concave regions that a gripper finger or a peg may need to enter. Decompositions also inherit the quality of the input mesh: scanned meshes with holes, self-intersections or non-manifold edges often need repair first. Convex decomposition is related to, but distinct from, collision representations such as signed distance fields, bounding-volume hierarchies of triangles, or sphere approximations, which make different trade-offs between speed and accuracy.

Why it matters

Whether a simulated grasp, insertion or pushing task behaves like the real one depends heavily on collision geometry. Convex decomposition is the usual step that turns visual meshes into geometry a physics engine can simulate quickly while keeping the concave features that contact-rich tasks depend on.

Key applications

• Collision meshes for objects and robot links in physics simulators
• Large-scale grasp and manipulation datasets generated in simulation
• Fast collision checking in sampling-based motion planners
• Contact-rich tasks such as insertion, where concave features must be preserved
• Converting CAD or scanned meshes into URDF or MJCF collision geometry

In practice

A team building a grasp dataset in simulation starts from several thousand scanned household object meshes. Each mesh is first repaired to be watertight and normalized in scale, then run through CoACD with a concavity threshold and a cap on the number of parts. The resulting convex pieces are written as separate collision meshes in the object's URDF or MJCF file, while the original mesh is kept for rendering. Before generating grasps, the team visually checks a sample of objects: bowls whose cavities were filled in, or handles merged with the body, get a tighter threshold. They also watch simulation speed, since objects that decompose into many dozens of pieces slow down large parallel environments.

Common misconceptions

• A physics engine collides with the mesh exactly as it is drawn — many engines use the convex hull of each collision mesh, so concave regions vanish unless the mesh is decomposed
• More convex pieces always give a better simulation — extra pieces slow collision checking and can create spurious contacts at the seams between pieces
• Convex decomposition is exact — practical tools are approximate and fill in concavities below the chosen tolerance, which can close small holes or narrow gaps

Who should know this

• Simulation engineers preparing robot and object assets
• Grasping and manipulation researchers building datasets in simulation
• Motion planning engineers working on collision checking
• Makers converting CAD models into URDF or MJCF files

Related technologies

• V-HACD
• CoACD
• GJK Algorithm
• Convex Hull
• MuJoCo
• PhysX

Related terms

• Penalty-Based Contact Model
• Signed Distance Field
• Axis-Aligned Bounding Box
• Graph of Convex Sets
• URDF
• Grasp Quality Metric

Related projects

• GENESIS: World's fastest physics engine: 43M FPS for embodied AI learning
• LeRobot: HuggingFace ML library for real-world robotics in PyTorch
• PyBullet: Python physics simulator for robotics and RL research with fast CPU-based simulation
• RLinf: Scalable infrastructure for post-training foundation models via RL
• Webots: Cross-platform robot simulator with built-in models, sensors, and development environment
• NVIDIA Isaac Sim: NVIDIA Omniverse app for AI-driven robot simulation and testing