CGAL users discussion list

["David Lariviere" <>]

Hi Maik,

One academic work on this problem is Lien and Amato's Approximate Convex
Decomposition (see http://www.cs.gmu.edu/~jmlien/research/app-cd/ ). While
the 2D binaries are provided, the 3D version is not yet released.

I've been trying to implement ACD using CGAL for the last 5 months, but have
been struggling with it, a lot of which has been related to restrictions on
the meshes within Polyhedron_3. 

The only open source implementation related is John Ratcliff's method (see
http://codesuppository.blogspot.com/2006/04/approximate-convex-decomposition
.html ), designed with similar applications in mind. He initially set out to
implement ACD as described by Lien and Amato as well, but eventually
utilized a simpler method of first iteratively splitting meshes using the
longest edge of an oriented bounding box until the concavity measure is
below some threshold, and then applying a post processing algorithm to
restitch nearby pieces. 

If I ever get my CGAL-based implementation working, I'll drop you a note. 

- David

-----Original Message-----
From: Maik Schulze 
[mailto:]
 
Sent: Tuesday, April 01, 2008 10:25 AM
To: 

Subject: [cgal-discuss] Convex Decomposition of Polyhedron inside CGAL or
elsewhere?

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
-- 
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss