HACD : Hierarchical Approximate Convex Decomposition by Khaled Mamou

Many people come to this weblog because they are searching on terms for 'Convex Decomposition'.  This blog post is to announce that there is a much, much, better open source implementation than the one I did.  I suppose I can take some tiny credit as my work appears to have inspired the authors of the new algorithm but that's not really saying much.  All credit where credit is due and the open source implementation released by Khaled Mamou is vastly superior to the brute force approach that mine took.  His is much more elegant and also solves a lot of extremely hard problems; such as objects with holes in them (something my algorithm could not deal with).  His also does not suffer with the problem mine had with excessive recursion depths producing hollow interiors.

You can find the paper for this algorithm at this location:

ftp://ftp.elet.polimi.it/users/Stefano.Tubaro/ICIP_USB_Proceedings_v2/pdfs/0003501.pdf


You can download the source to HACD from this location on SourceForge

http://sourceforge.net/projects/hacd/

With this announcement I will no longer be supporting my legacy ConvexDecomposition code in any way.  I am switching to using HADC in all of my projects.  I recommend you do the same.

Congratulations to Khaled and Faouzi who have done a fantastic job on an important problem.

One thing I will volunteer to the community is that sometime soon, I will create an open source tool using HACD that will auto-generate skeletal deformed meshes.

If you simply look at these various screenshots you will notice that the convex decomposition naturally produces a logical skeleton for an arbitrary piece of geometry.  Obviously, that skeleton isn't perfect compared to what an artist would create but it is certainly a useful approximate skeleton.

From previous work I have done on the 'create dynamics' project, I know that you can not only synthesize a skeleton but you can also auto-generate skinned bone weightings.  If you then create physical collision shapes which are constrained at these joint locations you can get an extremely convincing looking softbody object; with accurate collisions, in a very CPU cheap fashion.