CGAL users discussion list

[Maik Schulze <>]

Hello,
I'm a student working on a computer game project at the university. I'm 
currently working on collision geometry. Computing the convex hulls of 
the point clouds of our vehicle models proved to be insufficient. And to 
keep things simple for the artists I thought the following might be the 
way to go.

The artist builds a concave, closed polyhedron and runs a program that 
computes the convex decomposition of the polyhedron. The resulting 
convex polyhedra can then directly be handled by the physics engine. Or 
if the artist would like to do so, he can decrease the amount of the 
convex polyhedra by computing a common convex hull for two or more of 
them. For the last step, I can easily use CGAL functionality.

The problem is the convex decomposition. Is there an algorithm or 
library that computes the convex decomposition for a closed polyhedron? 
Since it is not necessary to compute the optimal solution, I thought 
there might be something like the Greene's approximation for 3D? As such 
computations are only performed once on every model, the running time 
and memory consumption can be quite high. Meaning the program could use 
up to 4GB of RAM and run for 30 minutes on a current high-end consumer 
processor with an input polyhedron with 20.000 vertices.

Is there such an algorithm, maybe even inside CGAL? Or could you provide 
me with some information on that matter? Unfortunately, Google wasn't 
very helpful on this issue for me. Please excuse my possible lack of 
knowledge about the theory behind this computational problem.

Regards
Maik Schulze