New Implementation of the HACD Algorithm : Julio Jerez

So, it turns out that Julio Jerez, author of the Newton Physics Engine, did his own implementation of Khaled Mamou's HACD algorithm (hierarchical approximate convex decomposition).

The big problem with Khaled's version is that it was extremely slow due to how he went about performing a distance calculation.  Julio's implementation does not suffer from this, and is much, much faster.

In addition, I added my own merge-hulls code as an optional post process step.

You can download the new version from this Google Code Project page.

Once you are synced you can try running say the complex segmented bug model.

Run: TestHACD hornbug.obj

This will produce a 58 convex hull model saved out to the file 'ConvexDecomposition.obj'

If you want one that is even more precision you can try something like:

TestHACD hornbug.obj -c 0.1

This sets the concavity value to 0.1 from the default of 0.2.

This will produce 73 convex hulls.

However, if you want to run the post-process merge phase, you can reduce the number of hulls by the following.

Run: TestHACD hornbug.obj -m 40

That will recursively collapse the convex hulls (starting with the smallest to the largest) until there are no more than 40 hulls left.

Take a look at the resulting file 'ConvexDecomposition.obj' and you will see how nicely the convex hulls were collapsed.

This version is *extremely* fast and can be used even on meshes with high vert counts without taking forever.

While, in general, Julio's implementation seems to be working great, we have found a couple of edge cases it fails on.

In the project you will find two wavefront OBJ files, 'box-thick.obj' and 'cylinder.obj'.

'Box-thick.obj' is a hollowed out box, which Khaled's implementation handles correctly, but Julio's fails on.  Same thing for the cylinder.

Hopefully we can get this tracked down soon. 

To use this source code in your own project, just copy the sources from the sub-directory 'hacd'.  The rest of your application only needs access to the folder 'hacd\public'.

Modify the header file 'PlatformConfigHACD.h' to change the global memory allocation routines if you want them to vector to your own methods.