Page 1 of 3

Simple and Efficient Approximate Convex Decomposition

Posted: Fri Apr 08, 2011 1:23 pm
by RBD
Has anyone tried to implement K. Mamou's "A Simple and Efficient Approach for 3D Mesh Approximate Convex Decomposition"?
Described in Game Programming Gems 8 - Chapter 2.8, p.202
First published in ICIP 2009 proceedings: A Simple and Efficient Approach for 3D Mesh Approximate Convex Decomposition (PDF)

Thoughts?

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Sat Apr 09, 2011 4:48 am
by Erwin Coumans
That looks interesting. I contacted the author and asked for his source code.

There is a good chance that we can add it to a future Bullet SDK, as improved convex decomposition is valuable.
Thanks for the link!
Erwin

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Mon May 02, 2011 3:56 pm
by khaled
Dear all,
You can find an implementation of the Hierarchical Approximate Convex Decomposition (HACD) here http://sourceforge.net/projects/hacd

The code is available under a BSD license.

It is a first version and I am still working on it. If you find any bugs/problems or if you are interested in improving the library do not hesitate to contact me

You can find below some results:
http://sourceforge.net/projects/hacd/fi ... /bunny.jpg
http://sourceforge.net/projects/hacd/fi ... s/foot.jpg
http://sourceforge.net/projects/hacd/fi ... /Homer.jpg
http://sourceforge.net/projects/hacd/fi ... ts/pig.jpg
http://sourceforge.net/projects/hacd/fi ... s/egea.jpg
http://sourceforge.net/projects/hacd/fi ... eature.jpg
http://sourceforge.net/projects/hacd/fi ... s/dilo.jpg
http://sourceforge.net/projects/hacd/fi ... s/dino.jpg
http://sourceforge.net/projects/hacd/fi ... ts/elk.jpg
http://sourceforge.net/projects/hacd/fi ... feline.jpg
http://sourceforge.net/projects/hacd/fi ... s/fish.jpg
http://sourceforge.net/projects/hacd/fi ... s/hand.jpg
http://sourceforge.net/projects/hacd/fi ... /horse.jpg
http://sourceforge.net/projects/hacd/fi ... ctopus.jpg
http://sourceforge.net/projects/hacd/fi ... rabbit.jpg

Comparative results HACD vs. John Ratcliff's ACD (http://codesuppository.blogspot.com/200 ... y-now.html):
http://sourceforge.net/projects/hacd/fi ... ctopus.jpg
http://sourceforge.net/projects/hacd/fi ... p_hand.jpg
http://sourceforge.net/projects/hacd/fi ... p_dino.jpg
http://sourceforge.net/projects/hacd/fi ... _bunny.jpg

--Khaled

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Thu May 12, 2011 6:57 pm
by RBD
Hi khaled, that is wonderful, thanks for sharing this as open source. I trust it will come in very handy for physics simulations. I personally would also be interested in trying some things with HACD and Blender; I look forward to playing with / testing your HACD project resources in the near future (unfortunately, I cannot at this time; but I do want to acknowledge and thank you for it).

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Thu May 12, 2011 11:49 pm
by ngbinh
Looks great!

Thanks for the work!

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Fri May 20, 2011 8:25 pm
by jratcliff63367
I just wanted to confirm that I have had time to review the work of Khaled and it is amazing. He has done an incredible job; especially in providing this code open source to the development community.

I made an announcement on my blog that the old approximate convex decomposition work that I did is now considered completely deprecated and I will no longer be using it myself any more.

http://codesuppository.blogspot.com/201 ... onvex.html

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Mon Jul 18, 2011 6:31 am
by dphil
This is great! With the help of some code posted by Flix (http://bulletphysics.org/Bullet/phpBB3/ ... f=9&t=7063), I have incorporated HACD with bullet in my simulations. I like how nicely it handles an object like this:

Image Image Image
Original (3600 triangles), decomposed (134 clusters), and Bullet debug line drawing of the associated btHACDCompoundShape, respectively.

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Fri Oct 07, 2011 4:54 am
by khaled
Dear all,
A new HACD version is available http://sourceforge.net/projects/hacd/
Have a look at my blog for the details http://kmamou.blogspot.com/

--Khaled

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Fri Oct 07, 2011 6:00 am
by dphil
Great stuff, thanks Khaled! Looking forward to trying out the improvements.

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Sat Dec 24, 2011 1:24 pm
by RBD
khaled, I've finally been playing around with HACD and it's working really well; it's quite impressive. Also the new decimation feature is really handy (even works with non-manifold meshes, great) and your recent blog post on the HACD parameters has been very useful as well.
Thanks, much appreciated!
(BTW I posted one of my first HACD tests with Blender & Bullet Physics as a p.s. to a recent (voronoi) video to spread the word on your great tool: real-time, rendered.)

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Mon Dec 26, 2011 8:43 am
by khaled
Thanks. Great demos by the way...
--Khaled

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Tue Jan 03, 2012 2:40 pm
by Karrok
How can I decouple this from wavefront?

Starting with a simple btBvhTriangleMeshShape for example.

How can I use convex decomposition on this shape?
Currently the demo only shows the case where a wavefront object is loaded with a lot of data that is not present in the btBvhTriangleMeshShape.

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Tue Jan 03, 2012 9:45 pm
by RBD
Karrok wrote:How can I decouple this from wavefront?
The HACD class is not coupled to any format. You simply point it to your vertices and triangles using SetPoints()/SetNPoints() and SetTriangles()/SetNTriangles(), then (set params and) call the Compute() method...

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Wed Jan 04, 2012 2:47 pm
by Karrok
Then the question becomes, where is the above information available from a btCollisionShape, btTriangleMeshShape or btBvhTriangleMeshShape

Re: Simple and Efficient Approximate Convex Decomposition

Posted: Sun Jan 08, 2012 8:26 am
by Flix
Karrok wrote:Then the question becomes, where is the above information available from a btCollisionShape, btTriangleMeshShape or btBvhTriangleMeshShape
In the btStridingMeshInterface. I've posted the source code here: http://bulletphysics.org/Bullet/phpBB3/ ... =17&t=7159.