Convex Decomposition Library now available on Google Code

***NOTICE ** NOTICE ** My convex decomposition library is now deprecated.

Please see this blog post for further details.

Today I refactored my convex decomposition code into the form of a 'drop in' library that people can use. Here is a link to the Google Code repository.

You need only include a single header file 'NvConvexDecomposition.h' to use the tool.

What is convex decomposition?

Convex decomposition is the process of taking an arbitrarily complex concave triangle mesh and approximating it as a collection of convex objects.

See the image above to for an example of how an approximate convex decomposition can, depending on the recursion depth and other factors, accurately represent a collision model for a triangle mesh. There are no hard and cold set of parameters to use for all triangle meshes; how detailed you make the approximate decomposition is always going be dependent on your specific use case.

Why do I need it?

Most physics engines will not allow you to represent arbitrary triangle meshes as dynamic objects. Even if the physics/collision engine does support arbitrary triangle mesh collision, it always comes at a major cost in terms of performance and memory.

Therefore, if you have complex triangle meshes that you wish to be realistically simulated in a dynamic world the best solution is to substitute it for a collection of compound convex hulls.

The physics engine will see the collection of convex hulls for collision while the graphics displays the original source triangle mesh for the viewer. Depending on how accurately your compound convex hulls match the source graphics you may, or may not, see some small artifacts. The choice of how detailed to make the approximation is almost always a design decision based on your specific use case.

How do I use it?

I am providing the Convex Decomposition library as a relatively small collection of source code that resides in its own namespace. The source code is C++ and is in the namespace 'CONVEX_DECOMPOSITION'. Even though there are a number of CPP and header files you only need to include a single header file to use the library.

Simply include 'NvConvexDecomposition.h'

Create an instance of the library:

CONVEX_DECOMPOSITION::iConvexDecomposition *ic = CONVEX_DECOMPOSITION::createConvexDecomposition();

Next, add the triangles from the original raw triangle mesh you wish to approximate.

You add them one triangle at a time, passing in three const float pointers, each representing a single X,Y,Z co-ordinate in the original triangle mesh.

Example:

for (NxU32 i=0; iaddTriangle( tris[i].p0, tris[i].p1, tris[i].p2 );

Once you have added all of the triangles you can compute the convex decomposition as follows:

ic->computeConvexDecomposition(skinWidth,
decompositionDepth,
maxHullVertices,
concavityThresholdPercent,
mergeThresholdPercent,
volumeSplitThresholdPercent,
useInitialIslandGeneration,
useIslandGeneration,
useBackgroundThreads);

The convex decomposition process can take a very long time. For this reason the default behavior is to perform the computation in a background thread.

You will have to query: 'isComputeComplete' to know when it has finished.

If you want to interrupt the computation before it is done you can call 'cancelCompute'

To find out how many convex hulls were produced you call: 'getHullCount'

You can then iterate through the hull results and grab each one as needed: 'getConvexHullResult'

When you are finished using the library, simply call:

CONVEX_DECOMPOSITION::releaseConvexDecomposition(ic);

What are the current limitations of this implementation?

The code is functional but could use the following improvements:

(1) The convex hull generator, originally written by Stan Melax, could use some major code cleanup.

(2) The code to remove T-junctions appears to have a bug in it. This code was working fine before, but I haven't had time to debug why it stopped working.

(3) Island generation once the mesh has been split is currently disabled due to the fact that the Remove Tjunctions functionality has a bug in it.

(4) The code to perform a raycast against a triangle mesh does not currently use any acceleration data structures.

(5) When a split is performed, the surface that got split is not 'capped'. This causes a problem if you use a high recursion depth on your convex decomposition. It will cause the object to be modelled as if it had a hollow interior. A lot of work was done to solve this problem, but it hasn't been integrated into this code drop yet.

When will these limitations be fixed?

It is hard to say. The current version is functional and I don't foresee having a lot of time to work on this any time soon. If a specific need arises I may get back to it sooner. I definitely want to add the acceleration structures to the raycast routine; which will speed things up. I also really want to know why the remove tjunctions code has a bug in it, since that was working fine before.

What is all of this source code, what is it for?

As I said before, you only need to include 'NvConvexDecomposition.h' and nothing else to use the library. I will, however, document what the other pieces of source code are and what purpose they serve.

• NvConcavityVolume.h / .cpp : Computes the 'volume of concavity' of a triangle mesh. It does this by first computing the convex hull for this triangle mesh. Next, it examines every single individual triangle in the original mesh and 'projects it' onto both the convex hull and on itself. If the projection hits the hull, then that extruded triangle volume is added as part of the 'total concavity volume'. It the projection hits the mesh itself, it first determines if it hit an interior or exterior face. If it hits an interior face, the volume is rejected. Otherwise, it adds to the volume of concavity the projection up to the point of self-intersection. This would be easier to explain with some drawings and pictures but I don't have time to make those up right now.
  
• NvConvexDecomposition.h / .cpp : This is the main public interface to the convex decomposition library. This is the only header your application should need to include directly.
• NvFloatMath.h / .cpp / .inl : This contains a collection of common and useful math library routines which work of of either const float or const double pointers.
• NvHashMap.h : This single header file contains support for both vector and hashmap container template classes. The reason this header file is used is because some of the game engine integrations that I work on do not allow the use of the STL at all.
• NvMeshIslandGeneration.h / .cpp : This is a code snippet which walks the topology of a triangle mesh, effectively flood filling it along the edges, to compute all of the independent mesh islands. Let's take the simple case. You pass in a single triangle mesh which actually contains two separate boxes. By walking the topology of the mesh the NvMeshIslandGeneration code snippet would immediately identify these as two distinctly unique triangle meshes.
• NvRayCast.h / .cpp : This code snippet provides based support to cast a ray against an arbitrary triangle mesh. Ideally it would use acceleration structures (such as an axis-aligned bounding volume tree). The current version does not yet have this optimization built in.
• NvRemoveTjunctions.h / .cpp : This code snippet is designed to identify and remove T-junctions in the triangle mesh. After a triangle mesh has been split by a plane it is common for t-junctions to be introduced. However, if you wish to continue to walk the topology of the mesh, either to identify mesh islands or to generate capped ends, there can be no t-junctions allowed in the mesh. This routine was not working properly when I put the library together so is currently disabled.
• NvSimpleTypes.h : This is a tiny header file that creates a set of platform and compiler independent standard defines for integer and floating point data types.
• NvStanHull.h / .cpp : Contains the convex hull generation code written originally by Stan Melax.
• NvThreadConfig.h / .cpp : This is a small code snippet that provides a platform independent abstraction for creating threads and mutexes.
• NvUserMemAlloc.h : This is a simple header file that controls how memory allocation is performed by this library. The default behavior is to use malloc/free and global new/delete. However, you can modify this header file to redirect memory allocations performed by this library to vector off to your application specific memory allocator if needed.
• wavefront.h / cpp : This is a tiny code snippet to read a Wavefront OBJ triangle mesh file. It is not considered part of the convex decomposition library and is only included for the sample application.
• main.cpp : This is a basic sample application that shows how to use the convex decomposition library by loading a triangle mesh from a Wavefront OBJ and uses command line switches to experiment with different parameters.

How does the convex decomposition algorithm work?

The convex decomposition algorithm works as follows.

1. The input mesh has any possible t-junctions removed to make sure that it has a clean topology. (Currently disabled)
2. The input mesh is broken up into any unique mesh islands. This is collection of triangles which all share edges. (Currently only enabled on the initial triangle mesh)
3. For each mesh island we do the following steps.
4. We compute the overall volume of the triangle mesh.
   
5. Make sure we have not exceeded our maximum decomposition depth, if we have, we are done.
6. We compute the volume of the current part of the mes we are working on. We then calculate what percentage the volume of this piece is, relative to the volume of the entire object. It the volume is too small (based on the input parameter 'volumeSplitThresholdPercent' then we are done with this piece.
7. Next we compute the 'volume of concavity'. This is done by building a convex hull around this piece of the mesh and then projecting the volume of each triangle on the original mesh onto either the mesh itself or the surrounding convex hull. The sum total is represented as the 'volume of concavity'.
8. We compute what percentage the volume of concavity is relative ot the volume of the surrounding convex hull. This percentage is then compared against the input parameter 'concavityThresholdPercent'. If the volume percentage of concavity is below this threshold we consider it 'good enough' and accept this piece as is.
9. If we have determined that the mesh piece is too concave we split it in half. First we compute the best fit OBB (object oriented box) around the convex hull of this piece. We create a split plane exactly half way along the long axis. (Other techniques for performing approximate convex decomposition have focused a lot of work finding just the absolutely perfect split plane to use. As you will see later, this algorithm doesn't require that.)
10. Once we have split the mesh by the plan we need to cap the ends so that the two pieces do not have holes in them. If we do not cap the ends then, as we recurse more deeply we will end up producing a hollow interior. It is important to note that this feature is not yet implemented! A lot of work has been done on this process and quite likely the library will be revised to support this feature at some time in the future.
    
11. Having split the mesh at the mid-point we just keep recursively calling the routine until we have exceeded our maximum recursion depth and/or other limits specified.
12. The final step is critical. Since we split each piece on the long axis of its orientation there is no guarantee that we split at exactly the correct location. We make up for this by actually splitting the source mesh many more times that is necessary. The final clean-up phase called 'merging' corrects for this.
13. For every hull we have generated we try combining it with every other hull in the decomposition. We compute the volume of the two hulls separately and compare that to the volume of the two hulls combined. If the difference in volume is below the parameter 'mergeThresholdPercent' than we combine the two hulls into one. We continue this process until we can no longer merge any hulls. In a brute force manner this technique causes the merged hulls to converge towards the optimal split boundaries.
    

ThreadFrac revised

Grrr...I went to run my copy of 'ThreadFrac' that was uploaded in a couple of places and it wouldn't run due to side-by-side assembly issues or some such nonsense.

I rebuilt it with an embedded manifest and it should run now.

Let me know if you have a problem; requires Windows with DX9 to run.

The reason I was looking for ThreadFrac is that I want to start messing with the new 3d equation called 'Mandelbulb'.

I'm going to write a real-time multi-threaded raytracer and add it to my ThreadFrac program when I get a chance to work on.

If you haven't seen the 'Mandelbulb' yet, check it out.

Here is the link to the revised executable for ThreadFrac.

A test application for the MeshImport library and showcasing EZMesh

I spent some time this morning and created a really nice sample program to demonstrate how to use the MeshImport plugins. (Here is a link to the formal documentation for the EZ-Mesh file format. It is a work in progress but should be finished up tomorrow)

The MeshImport plugin library provides an easy mechanism to both import and export fully skeletal deformed and animated mesh content.

It supports multiple graphics file formats but I am strongly recommending the EZMesh graphics file format.

I describe the reasons for this in the enclosed readme.

The readme can be found at this link: MeshImportReadme.txt

An example of an EZ-Mesh file which describes a skeleton, an animation, and a deformed mesh, can be found at the following link. In only 34 lines of XML it is able to describe all of the components necessary to a skeletal deformed (and animated) mesh in a highly human readable format. Let's see COLLADA (or any other graphics file format) try doing that.

EXPORT.EZM

To download the sample application, with all of the necessary DLL components, use this link:

MeshImportTest.zip

You can browse the sample demonstration source code here, so see how easy it is to actually use the MeshImport library.

main.cpp

Documentation for the Ez-Mesh file format.

Here are some more important links:

Here is the link to a Google Code project containing the Mesh Import test application.

If you are interested in building the plugins, or perhaps writing a new mesh importer. I have recently updated the source in the Google Code project.

The Google Code project for the Mesh Import libraries is located here.

Once you sync, to build the project load the solution file in:

\MeshImport\compiler\vc8\MeshConvert.sln

The FBX importer is not built by default, because it is dependent on the FBX SDK from Autodesk which you must obtain here. None of the other importers contain any external dependencies.

The solution file for the FBX importer is located in:

\MeshImport\compiler\vc8\MeshImportFBX.sln

You will need to change the include paths to point to wherever you have the FBX SDK on your machine.