CGAL users discussion list

[Peter Hachenberger <>]

Hi Maik,

I have exactly what you want, but it's not in CGAL, yet. It's working
nicely and is scheduled for the next CGAL release. I guess that is a bit
late for you.

Peter

On Tue, 2008-04-01 at 16:25 +0200, Maik Schulze wrote:
> 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