Module vhacd

Approximate convex decomposition using the VHACD algorithm. Approximate Convex Decomposition using the V-HACD algorithm.

What is Convex Decomposition?

Convex decomposition is the process of breaking down a complex, possibly concave shape into multiple simpler convex shapes. A convex shape is one where any line segment connecting two points inside the shape lies entirely within the shape (think of shapes without dents or holes). For example:

• Convex: sphere, box, cone, tetrahedron
• Concave: bowl, donut, ‘L’ shape, ‘C’ shape, star

Why Use Convex Decomposition?

Convex shapes are much more efficient for collision detection than concave shapes because:

1. Performance: Collision algorithms like GJK work directly with convex shapes
2. Physics Simulation: Physics engines (like Rapier) can only handle convex shapes for dynamic objects
3. Accuracy: Better than using a single bounding volume or triangle mesh for complex shapes

Example use cases:

• Game character models with complex geometry (humanoids, creatures)
• Architectural elements (stairs, furniture, buildings)
• Vehicles (cars, planes, spaceships)
• Complex terrain features

When to Use Each Approach

Shape Type	Best Approach	Example
Already convex	Use convex_hull	Box, sphere, simple pyramid
Simple concave	Use Compound of basic shapes	Two boxes in an ‘L’ shape
Complex concave	Use convex decomposition	Character mesh, furniture
Very detailed mesh	Use TriMesh for static objects	Detailed terrain, static level geometry

The V-HACD Algorithm

V-HACD (Volumetric Hierarchical Approximate Convex Decomposition) works by:

1. Voxelization: Converting the input mesh into a 3D grid of voxels (or 2D pixels)
2. Decomposition: Recursively splitting the voxelized shape along planes that minimize concavity
3. Convex Hull: Computing the convex hull of each resulting part

The algorithm balances:

• Quality: How closely the parts approximate the original shape (controlled by concavity)
• Count: How many convex parts to generate (controlled by max_convex_hulls)
• Performance: How long the decomposition takes (controlled by resolution)

Basic Usage

Quick Start (Default Parameters)

The simplest way to decompose a mesh is using default parameters:

use parry3d::math::Point;
use parry3d::transformation::vhacd::VHACD;
use parry3d::transformation::vhacd::VHACDParameters;

// Define a simple concave mesh (an 'L' shape made of triangles)
let vertices = vec![
    Point::new(0.0, 0.0, 0.0), Point::new(2.0, 0.0, 0.0),
    Point::new(2.0, 1.0, 0.0), Point::new(1.0, 1.0, 0.0),
    Point::new(1.0, 2.0, 0.0), Point::new(0.0, 2.0, 0.0),
    // Add corresponding back face vertices
    Point::new(0.0, 0.0, 1.0), Point::new(2.0, 0.0, 1.0),
    Point::new(2.0, 1.0, 1.0), Point::new(1.0, 1.0, 1.0),
    Point::new(1.0, 2.0, 1.0), Point::new(0.0, 2.0, 1.0),
];
let indices = vec![
    // Front face triangles
    [0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5],
    // Back face triangles
    [6, 8, 7], [6, 9, 8], [6, 10, 9], [6, 11, 10],
    // Connect front and back
    [0, 6, 7], [0, 7, 1], [1, 7, 8], [1, 8, 2],
    [2, 8, 9], [2, 9, 3], [3, 9, 10], [3, 10, 4],
    [4, 10, 11], [4, 11, 5], [5, 11, 6], [5, 6, 0],
];

// Decompose with default parameters
let decomposition = VHACD::decompose(
    &VHACDParameters::default(),
    &vertices,
    &indices,
    false, // don't keep voxel-to-primitive mapping
);

// Get the voxelized convex parts
let parts = decomposition.voxel_parts();
println!("Generated {} convex parts", parts.len());

// Compute the convex hulls (for collision detection)
let convex_hulls = decomposition.compute_convex_hulls(4);
for (i, (vertices, indices)) in convex_hulls.iter().enumerate() {
    println!("Part {}: {} vertices, {} triangles", i, vertices.len(), indices.len());
}

Customizing Parameters

For more control over the decomposition quality and performance:

use parry3d::math::Point;
use parry3d::transformation::vhacd::{VHACD, VHACDParameters};
use parry3d::transformation::voxelization::FillMode;

// Configure parameters for higher quality decomposition
let params = VHACDParameters {
    resolution: 128,          // Higher = more detail (but slower)
    concavity: 0.001,         // Lower = more parts but better fit
    max_convex_hulls: 32,     // Maximum number of convex parts
    plane_downsampling: 4,    // Precision of plane search
    convex_hull_downsampling: 4, // Precision of convex hull generation
    alpha: 0.05,              // Bias toward symmetrical splits
    beta: 0.05,               // Bias toward revolution axis splits
    convex_hull_approximation: true, // Approximate for speed
    fill_mode: FillMode::FloodFill {
        detect_cavities: false,
    },
};

let decomposition = VHACD::decompose(&params, &vertices, &indices, false);

Working with Original Mesh Geometry

By default, the convex hulls are computed from the voxelized representation. To get more accurate hulls based on the original mesh:

use parry3d::math::Point;
use parry3d::transformation::vhacd::{VHACD, VHACDParameters};

// Enable voxel-to-primitive mapping
let decomposition = VHACD::decompose(
    &VHACDParameters::default(),
    &vertices,
    &indices,
    true, // <-- Keep mapping to original mesh primitives
);

// Compute exact convex hulls using original mesh geometry
let exact_hulls = decomposition.compute_exact_convex_hulls(&vertices, &indices);
println!("Generated {} exact convex hulls", exact_hulls.len());

2D Convex Decomposition

The same API works in 2D for decomposing polylines:

use parry2d::math::Point;
use parry2d::transformation::vhacd::{VHACD, VHACDParameters};

// Define a concave polyline (e.g., an 'L' shape)
let vertices = vec![
    Point::new(0.0, 0.0), Point::new(2.0, 0.0),
    Point::new(2.0, 1.0), Point::new(1.0, 1.0),
    Point::new(1.0, 2.0), Point::new(0.0, 2.0),
];
let indices = vec![
    [0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 0],
];

let decomposition = VHACD::decompose(
    &VHACDParameters::default(),
    &vertices,
    &indices,
    false,
);

// Get convex polygons
let convex_polygons = decomposition.compute_convex_hulls(4);
for (i, polygon) in convex_polygons.iter().enumerate() {
    println!("Polygon {}: {} vertices", i, polygon.len());
}

Integration with Physics Engines

The decomposed convex parts can be used directly with physics engines:

use parry3d::math::Point;
use parry3d::shape::{SharedShape, Compound};
use parry3d::transformation::vhacd::VHACDParameters;
use parry3d::na::Isometry3;

// Use the high-level API for direct integration
let compound_shape = SharedShape::convex_decomposition(&vertices, &indices);

// Or with custom parameters
let params = VHACDParameters {
    concavity: 0.001,
    max_convex_hulls: 32,
    ..Default::default()
};
let compound_shape = SharedShape::convex_decomposition_with_params(
    &vertices,
    &indices,
    &params,
);

// The resulting compound can be used as a collider shape
println!("Created compound shape with convex parts");

Performance Tips

1. Resolution: Start with lower values (32-64) for fast iteration, increase for final quality
2. Concavity: Higher values (0.01-0.1) = fewer parts = faster but less accurate
3. Max Convex Hulls: Limit to reasonable values (8-32) for game objects
4. Approximation: Keep convex_hull_approximation: true for better performance
5. Preprocessing: Simplify your mesh before decomposition if it has excessive detail

Debugging Tips

If the decomposition doesn’t look right:

• Visualize the voxelized parts using voxel_parts() to understand the algorithm’s view
• Try adjusting resolution if details are lost or voxelization is too coarse
• Increase max_convex_hulls if the shape is still too concave
• Decrease concavity for tighter fitting convex parts
• Check that your mesh is manifold and has consistent winding order

Algorithm Details

The V-HACD algorithm was developed by Khaled Mamou and is described in:

“Volumetric Hierarchical Approximate Convex Decomposition” Khaled Mamou and Faouzi Ghorbel

Implementation based on: https://github.com/kmammou/v-hacd

See Also

• VHACDParameters: Configuration parameters for the algorithm
• VHACD: The main decomposition structure
• SharedShape::convex_decomposition: High-level API
• convex_hull: For computing convex hulls directly
• Compound: For manually combining convex shapes

Structs

VHACD

Approximate convex decomposition using the VHACD algorithm.

VHACDParameters

Parameters controlling the VHACD convex decomposition algorithm.