Has anyone had positive experiences using automatic convex decomposition methods for complex models in video games? Several of you have suggested that most video game developers don't rely on automatic techniques, but perform the decomposition by hand.
I know that creating an optimal set of convex pieces is NP-Complete, but assuming an optimal automatic technique did exist, would it be safe for me to assume that game developers still wouldn't use the results, on the grounds that collision geometry is often required to be much more simplified?
I'm also curious if anyone has had success with user-assisted convex decomposition techniques. I'm not aware of any techniques.
Thanks!
Convex Decomposition Methods
-
Erwin Coumans
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
One way to do convex decomposition is to break the mesh into pieces, and then join the pieces, while maintaining convexity. You could calculate a tetrahedralization first, see Tetgen ( http://tetgen.berlios.de )
For practical use, the artist should have access to some basic parameters to control the quality of the convex decomposition.
A similar approach is described by John Ratcliff ( http://codesuppository.blogspot.com/200 ... ition.html), he first breaks up the mesh into best fitting boxes, spheres or convex hulls, and then joins pieces together.
This new Bullet Convex Decomposition demo uses this:
http://www.continuousphysics.com/ftp/pu ... sition.zip
Use <spacebar> and keys I and S (help text on screen).
Sources are in SVN, and it will be in the next Bullet release.
For practical use, the artist should have access to some basic parameters to control the quality of the convex decomposition.
A similar approach is described by John Ratcliff ( http://codesuppository.blogspot.com/200 ... ition.html), he first breaks up the mesh into best fitting boxes, spheres or convex hulls, and then joins pieces together.
This new Bullet Convex Decomposition demo uses this:
http://www.continuousphysics.com/ftp/pu ... sition.zip
Use <spacebar> and keys I and S (help text on screen).
Sources are in SVN, and it will be in the next Bullet release.
-
Erwin Coumans
- Site Admin
- Posts: 4221
- Joined: Sun Jun 26, 2005 6:43 pm
- Location: California, USA
It would be interesting to do some research in this area and find relevant literature/papers.
A few links here:
http://parasol.tamu.edu/groups/amatogro ... ch/app-cd/
http://citeseer.ist.psu.edu/belov02modified.html
C. Bajaj and T. K. Dey. Convex decomposition of polyhedra and robustness. SIAM J. Comp., 21:339?364, 1992. 2 models: a survey. Proc. IMA Conf. on Mathematics of Surfaces, 37?56, 1998. 1
B. Chazelle. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comp., 13:488?507, 1984. 2 Automation, pages 1008?1014, 1991. 2, 3
B. Chazelle and L. Palios. Triangulating a non-convex polytope. Discrete Comp. Geom., 5:505?526, 1990. 2
A. Rappoport. The extended convex differences tree (ECDT) representation for N-dimensional polyhedra. Int. Journ. on Comp. Geom. & Apps., 1(3):227?241, 1991.
J. Ruppert and R. Seidel. On the difficulty of triangulating three-dimensional non-convex polyhedra. Discrete Comp. Geom., 7:227?253, 1992.
If you use convex decomposition for pre-fracturing it would be good to use material information. A lot of objects don't have uniform material distribution. A lot of walls would collapse along brick boundaries for example (mortar has different properties then bricks).
A few links here:
http://parasol.tamu.edu/groups/amatogro ... ch/app-cd/
http://citeseer.ist.psu.edu/belov02modified.html
C. Bajaj and T. K. Dey. Convex decomposition of polyhedra and robustness. SIAM J. Comp., 21:339?364, 1992. 2 models: a survey. Proc. IMA Conf. on Mathematics of Surfaces, 37?56, 1998. 1
B. Chazelle. Convex partitions of polyhedra: a lower bound and worst-case optimal algorithm. SIAM J. Comp., 13:488?507, 1984. 2 Automation, pages 1008?1014, 1991. 2, 3
B. Chazelle and L. Palios. Triangulating a non-convex polytope. Discrete Comp. Geom., 5:505?526, 1990. 2
A. Rappoport. The extended convex differences tree (ECDT) representation for N-dimensional polyhedra. Int. Journ. on Comp. Geom. & Apps., 1(3):227?241, 1991.
J. Ruppert and R. Seidel. On the difficulty of triangulating three-dimensional non-convex polyhedra. Discrete Comp. Geom., 7:227?253, 1992.
If you use convex decomposition for pre-fracturing it would be good to use material information. A lot of objects don't have uniform material distribution. A lot of walls would collapse along brick boundaries for example (mortar has different properties then bricks).
-
koz
- Posts: 7
- Joined: Thu Apr 20, 2006 5:50 pm
Awesome demo!
After seeing the ACD link, it reminded me of this paper.
http://www.ee.technion.ac.il/~ayellet/Ps/0325_ayt.pdf
It also seems to do a good job of breaking down meshes into "near" convex pieces.
I wonder if either of these approximate techniques combined with a simple convex hull computation would have any merit.
After seeing the ACD link, it reminded me of this paper.
http://www.ee.technion.ac.il/~ayellet/Ps/0325_ayt.pdf
It also seems to do a good job of breaking down meshes into "near" convex pieces.
I wonder if either of these approximate techniques combined with a simple convex hull computation would have any merit.
-
dog
- Posts: 40
- Joined: Fri Jul 22, 2005 8:00 pm
- Location: Santa Monica
What I do is:
* Ensure my mesh is manifold - sometimes this involves shrink-wrapping the model, and is currently the most awkward part of the process. I'm experimenting with a voxel based approach to this in my spare time.
* Decompose my mesh into a solid leafy bsp.
* Find all adjacent leaves the same way one would find portals.
* Find the convex hulls of each pair of leaves - if the actual geometry is within a small tolerance of the hull then I mark that pair as collapsable.
* Repeat the process with merged pairs etc..
* Try some sample merge runs on the tree of collapsable nodes and pick the one that yields the least number of parts (I start from 8 random locations right now). This appears to approach an optimal solution without actual doing full brute force calculations.
By changing the acceptable tolerance, and using the convex hull geometry I can dial in the cost of the final model.
I really should get round to writing a paper on this.
* Ensure my mesh is manifold - sometimes this involves shrink-wrapping the model, and is currently the most awkward part of the process. I'm experimenting with a voxel based approach to this in my spare time.
* Decompose my mesh into a solid leafy bsp.
* Find all adjacent leaves the same way one would find portals.
* Find the convex hulls of each pair of leaves - if the actual geometry is within a small tolerance of the hull then I mark that pair as collapsable.
* Repeat the process with merged pairs etc..
* Try some sample merge runs on the tree of collapsable nodes and pick the one that yields the least number of parts (I start from 8 random locations right now). This appears to approach an optimal solution without actual doing full brute force calculations.
By changing the acceptable tolerance, and using the convex hull geometry I can dial in the cost of the final model.
I really should get round to writing a paper on this.