VHACD (Volumetric Hierarchical Approximate Convex Decomposition)

Approximate Convex Decomposition (ACD) is used to solve the problem of collision detection for concave 3D surfaces.

Standard collision detection often uses simple convex shapes (ellipsoids, capsules, or convex hulls), but these provide poor approximations for concave surfaces and cause false collisions. While an exact convex decomposition is possible, it is NP-hard and produces too many clusters for real-time use.

ACD relaxes the exact convexity constraint. It partitions a mesh into a minimal number of clusters while ensuring each cluster's concavity remains below a user-defined threshold. This allows for realistic physical interactions in real-time environments like video games and robotics simulations.

To install the VHACD package in Unity 2020.2 or later, use the Package Manager to add the package via its Git URL.

1. Open the Package Manager from Window -> Package Manager.
2. Click the + button in the upper left corner.
3. Select Add package from git URL....
4. Enter the Git URL. You can append a version tag (e.g., #v0.4.0) to target a specific version, or omit it to use the latest from the main branch.

Git URL: https://github.com/Unity-Technologies/VHACD.git?path=/com.unity.robotics.vhacd

The VHACD::Parameters class controls the behavior and quality of the convex decomposition. You can initialize a default set of parameters using the constructor and then modify specific fields.

Key parameters include:

• m_resolution: Voxel resolution.
• m_concavity: Maximum allowed concavity.
• m_maxConvexHulls: The maximum number of convex hulls to produce (replaces the old m_gamma metric).
• m_mode: 0 for voxel-based (recommended), 1 for tetrahedron-based.
• m_projectHullVertices: If true, projects output vertices onto the original mesh to increase floating-point accuracy.
• m_oclAcceleration: Enables OpenCL acceleration.
• m_callback and m_logger: Pointers to user-implemented IUserCallback and IUserLogger interfaces.

VHACD::Parameters params;
params.m_maxConvexHulls = 128;
params.m_concavity = 0.001;
params.m_projectHullVertices = true;

After a successful Compute call, you can retrieve the resulting convex hulls and their properties:

1. Get count: Use GetNConvexHulls() to find how many hulls were produced.
2. Get individual hull: Use GetConvexHull(index, ch) to populate a VHACD::ConvexHull object with the points, triangles, volume, and center of a specific hull.
3. Center of Mass: Use ComputeCenterOfMass(double centerOfMass[3]) to calculate the center of mass for the entire decomposition. Returns false if it fails.

uint32_t numHulls = vhacd->GetNConvexHulls();
for (uint32_t i = 0; i < numHulls; ++i) {
    VHACD::ConvexHull ch;
    vhacd->GetConvexHull(i, ch);
    // Access ch.m_points, ch.m_triangles, ch.m_volume, etc.
}

To use the V-HACD library, you must first instantiate an IVHACD object using one of two factory functions:

1. CreateVHACD(): Creates a synchronous instance. The Compute call will block the calling thread until the decomposition is complete.
2. CreateVHACD_ASYNC(): Creates an asynchronous instance. The Compute call returns immediately, and the decomposition runs in a background thread.

When using the asynchronous version, you should poll IsReady() to check if the operation is complete. All callback messages and logs are dispatched in the caller's thread, so no manual mutex locking is required for handling callbacks.

IVHACD* vhacd = VHACD::CreateVHACD_ASYNC();
// ... configure and call Compute ...
if (vhacd->IsReady()) {
    // Process results
}

Use the Compute method on an IVHACD instance to perform the decomposition. The method is overloaded to support both float and double point arrays.

Arguments:

• points: Pointer to the array of vertex coordinates.
• countPoints: Number of vertices.
• triangles: Pointer to the array of triangle indices.
• countTriangles: Number of triangles.
• params: A VHACD::Parameters object defining the decomposition settings.

If you call Compute while a previous operation is still running, the library will automatically cancel the previous request and start the new one.

bool success = vhacd->Compute(points, numPoints, triangles, numTriangles, params);

Once decomposition is complete, use GetConvexHull(index, ch) to extract the geometric data for a specific hull. The ConvexHull object (passed by reference) will be populated with the following fields:

• m_nPoints: Number of vertices in the hull.
• m_nTriangles: Number of triangles in the hull.
• m_points: Pointer to the vertex array.
• m_triangles: Pointer to the triangle index array.
• m_volume: The computed volume of the hull.
• m_center: An array of 3 doubles representing the center of mass (X, Y, Z).

VHACD::ConvexHull ch;
vhacd.GetConvexHull(index, ch);
// Access data:
// ch.m_points
// ch.m_triangles
// ch.m_center[0] // X

Properly manage resources to avoid memory leaks:

• Cancel(): Stops a currently running approximation.
• Clean(): Releases internally allocated memory.
• Release(): Releases the IVHACD instance.

OpenCL Acceleration: If m_oclAcceleration is enabled in Parameters, you must initialize the OpenCL device using OCLInit(void* const oclDevice, IUserLogger* const logger = 0). Use OCLRelease() to shut down OpenCL support.

To enable OpenCL acceleration for the decomposition process, call OCLInit(). This requires an OpenCL-compatible device.

• OCLInit(void* const oclDevice, IUserLogger* const logger = 0): Initializes the OpenCL context and kernels. Returns true on success.

// oclDevice would be a pointer to a cl_device_id
bool success = vhacd.OCLInit(myOclDevice, myLogger);

The VHACD class provides methods for manual memory and state management:

• Clean(): Resets the internal state, releases allocated resources (like the raycast mesh and volume data), and re-initializes the object. Use this to clear previous computation results without destroying the object.
• Release(): Deletes the VHACD instance itself. Use this if you allocated the object via new.

vhacd.Clean(); // Reset state
// OR
vhacd.Release(); // Delete instance