Simple and Efficient Approximate Convex Decomposition

Please don't post Bullet support questions here, use the above forums instead.
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Simple and Efficient Approximate Convex Decomposition

Post 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?
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Re: Simple and Efficient Approximate Convex Decomposition

Post 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
khaled
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post 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
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Simple and Efficient Approximate Convex Decomposition

Post 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).
ngbinh
Posts: 117
Joined: Fri Aug 12, 2005 3:47 pm
Location: Newyork, USA

Re: Simple and Efficient Approximate Convex Decomposition

Post by ngbinh »

Looks great!

Thanks for the work!
jratcliff63367
Posts: 1
Joined: Fri May 20, 2011 8:22 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post 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
User avatar
dphil
Posts: 237
Joined: Tue Jun 29, 2010 10:27 pm
Contact:

Re: Simple and Efficient Approximate Convex Decomposition

Post 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.
khaled
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post 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
User avatar
dphil
Posts: 237
Joined: Tue Jun 29, 2010 10:27 pm
Contact:

Re: Simple and Efficient Approximate Convex Decomposition

Post by dphil »

Great stuff, thanks Khaled! Looking forward to trying out the improvements.
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Simple and Efficient Approximate Convex Decomposition

Post 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.)
khaled
Posts: 22
Joined: Mon May 02, 2011 3:26 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by khaled »

Thanks. Great demos by the way...
--Khaled
Karrok
Posts: 65
Joined: Fri May 13, 2011 1:11 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post 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.
RBD
Posts: 141
Joined: Tue Sep 16, 2008 11:31 am

Re: Simple and Efficient Approximate Convex Decomposition

Post 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...
Karrok
Posts: 65
Joined: Fri May 13, 2011 1:11 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post by Karrok »

Then the question becomes, where is the above information available from a btCollisionShape, btTriangleMeshShape or btBvhTriangleMeshShape
Flix
Posts: 456
Joined: Tue Dec 25, 2007 1:06 pm

Re: Simple and Efficient Approximate Convex Decomposition

Post 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.
Post Reply