HACD optimization

Today, I have updated the HACD library in order to reduce both memory usage and computation complexity (cf. http://sourceforge.net/projects/hacd/). 

The new version:

• uses John's Micro Allocator to avoid intensive dynamic memory allocation (thanks John for the great work),
• exploits a simplified version of  an axis-aligned-bounding-volume AABB tree to accelerate dual graph generation (the code is inspired by John's post on this subject, thanks again John :) )
• has an integrated mesh simplification pre-processing step, which makes it possible to handle dense meshes.

In this post, I'll give more details about this last feature.

To enable mesh decimation, the user specifies the target number of triangles that should be produced before running the convex decomposition. HACD will handle automatically the simplification and the decomposition processes. For the details of the mesh decimation algorithm, have a look at Michael Garland's  webpage http://mgarland.org/research/thesis.html. To turn this feature off just set the parameter targetNTrianglesDecimatedMesh=0.

I have tested the updated HACD algorithm on the 3D model "Bunny", which has 70K triangles. The HACD's parameters were set as follows:

• minNClusters = 12
• maxConcavity = 1000
• addExtraDistPoints = 1
• addFacesPoints = 1
• ConnectedComponentsDist = 30
• targetNTrianglesDecimatedMesh = 500, 1000, 2000, 4000, 8000 and 16000.

The snapshots of the produced convex decompositions are reported below. The computation times on my machine (Mac Intel Core 2 Duo, 4 GB RAM DDR3) ranged between 3 sec. for 500 triangles and 200 sec. for 16000 triangles (cf. Table 1 for the details).

----------------------------------------

# triangles  Time (sec.)

----------------------------------------

500 2.8

1000 4.6

2000 10

4000 21

8000 70

16000 192

----------------------------------------

Table 1. Computation times for targetNTrianglesDecimatedMesh= 500, 1000, 2000, 4000, 8000 and 16000 

# triangles after simplification - 500

# triangles after simplification - 1000

# triangles after simplification - 2000

# triangles after simplification - 4000

# triangles after simplification - 8000

# triangles after simplification - 16000