Revision to TestHACD

After making my post last week Khaled Mamou has made some bug fixes to his HACD implementation that takes extended mesh connectivity into account.  In the previous version, if you ran convex decomposition on a single input mesh that was actually comprised of say 10 separate unique sub-meshes (I like to call them 'mesh islands') then it would always produce a minimum of 10 convex hulls.

Khaled fixed this by adding a new option called 'connectivity distance' which will merge mesh islands if they touch within this distance.

I integrated Khaled's changes into my depot as well, and also removed my hack solution which performed hull merging to get around this previous problem.

Right now my code and Khaled's are in sync, but my code drop is significantly refactored since I made it optional to build and run it either with or without the standard template library.  Perhaps we can combine our efforts sometime in the future but, for now, I will just continue to manually integrate changes.

My current check-in adds support for my MeshImporter plugins which can import a wide variety of graphics file formats.  I will have a new MeshImporter plugin that will support COLLADA soon. This is a windows only feature; for non-windows developers there is an option to just compile in Wavefront OBJ support.

Also, my current code drop has the beginnings of the automatic skeleton generation code.  As I find time this week, I will try to complete it.  This code will take an arbitrary triangle mesh, perform HACD on it, and then infer a skeleton at the points wherever two convex hulls touch each other.  As a final option it can auto-generate a skinned mesh from the original non-skinned artwork.  This will allow you to automatically create a ragdoll or psuedo-softbody from any arbitrary mesh.

Here is the link to my depot on Google Code.  TestHACD

Here is the link to Khaled Mamou's official copy of HACD on SourceForge.

HACD : Hierarchical Approximate Convex Decomposition by Khaled Mamou Sample Application

I have just created and made available a test application for people to use/experiment with Khaled Mamou's excellent HACD system.

TestHACD on Google Code

Due to requirements that I have at my job, I had to refactor the code so that it did not use any of the standard template library (STL) and 100% of all memory allocations had to be trapped by a user provided allocator. (i.e. no global new/delete, malloc, free).

One of the more challenging things to factor out regarding the STL was the use of the STL set and map containers.  To accomplish this what I did was refactor a copy of the EASTL (written by Paul Pedriana).  Even though Paul's EASTL is a dramatically smaller code base than the full STL implementation, I went a step further and refactored his code so that I extracted *only* the STL map/set containers and nothing else.  I then put this refactored code into just three small source files where all memory allocations and data types could be trapped and revectored.

There is a single header file in the provided project 'PxSimpleTypes.h'.  You can modify the data types and memory allocation macros in this one header file to make the source conform to the coding standard of your own game engine, or at least it provides a single easy location to do some global find/replace on the source to make it conform to your internal standards.

Khaled's algorithm produces absolutely amazing results much better than my version ever did.  However, one thing I have yet to be able to get his to do is produce just one our two hulls.

With the provided sample mesh no matter what I set the concavity threshold to, no matter how high, I still get 14 convex hulls.  I don't know if this is a limitation of his algorithm or I am not exposing all of the correct parameters at this time.

If you wish to make improvements to this code, please let me know and I will add you to the Google Code project so you can make changes.  Also, sometime in the next week, I am going to revise the code to auto-generate a skeletal deformed mesh from the HACD output.  I will add this to the TestHACD open source project.

Be aware that Khaled's algorithm can be extremely CPU intensive.  With triangle meshes with very large vertex counts; it could possibly take an extremely lengthy period of time.