Sven Oesau
GeometryFactory
A camel mesh decomposed into 4, 8 and 12 convex volumes.
The upcoming CGAL release 6.2, will introduce the method Approximate Convex Decomposition. Convex decomposition of 3D objects have applications ranging from collision detection and rigid body simulation to motion planning and geometric approximation. While exact convex decomposition algorithms provide strong guarantees, they can produce a large number of components and can be NP-hard if the minimal number of components is required.
The approximate convex decomposition addresses these limitations by partitioning closed triangle meshes into a set of convex components while providing direct control over the approximation quality and the number of components. Instead of enforcing exact convexity, the algorithm iteratively detects highly concave regions and introduces cuts that reduce the overall concavity of the shape. The decomposition output is represented as a collection of submeshes that can easily be reused in applications relying on Surface_mesh or Polygon Mesh Processing.
The method employs a voxel grid to detect concave parts of the objects and follows a hierarchical splitting strategy to decompose the object into a larger number of convex volumes. The final desired number of convex volumes is obtained via an error-driven merging phase that recombines the smaller convex volumes while keeping the volumetric overhead as small as possible.
From left to right: 1) Input mesh, 2) Voxelization, 3) Convex volumes after splitting phase, 4) Final 10 convex volumes.
Status
The method "Approximate Convex Decomposition" is already integrated in CGAL's "main" branch on the CGAL GitHub repository, and will be officially released in the upcoming version of CGAL, CGAL 6.2, scheduled for June 2026.
Documentation of the Approximate Convex Decomposition
CGAL “main” branch on GitHub
