parry3d/transformation/vhacd/mod.rs
1//! Approximate Convex Decomposition using the V-HACD algorithm.
2//!
3//! # What is Convex Decomposition?
4//!
5//! Convex decomposition is the process of breaking down a complex, possibly concave shape into
6//! multiple simpler convex shapes. A **convex** shape is one where any line segment connecting
7//! two points inside the shape lies entirely within the shape (think of shapes without dents
8//! or holes). For example:
9//! - Convex: sphere, box, cone, tetrahedron
10//! - Concave: bowl, donut, 'L' shape, 'C' shape, star
11//!
12//! # Why Use Convex Decomposition?
13//!
14//! Convex shapes are much more efficient for collision detection than concave shapes because:
15//! 1. **Performance**: Collision algorithms like GJK work directly with convex shapes
16//! 2. **Physics Simulation**: Physics engines (like Rapier) can only handle convex shapes
17//! for dynamic objects
18//! 3. **Accuracy**: Better than using a single bounding volume or triangle mesh for complex shapes
19//!
20//! **Example use cases:**
21//! - Game character models with complex geometry (humanoids, creatures)
22//! - Architectural elements (stairs, furniture, buildings)
23//! - Vehicles (cars, planes, spaceships)
24//! - Complex terrain features
25//!
26//! # When to Use Each Approach
27//!
28//! | Shape Type | Best Approach | Example |
29//! |------------|---------------|---------|
30//! | Already convex | Use [`convex_hull`](crate::transformation::convex_hull) | Box, sphere, simple pyramid |
31//! | Simple concave | Use [`Compound`](crate::shape::Compound) of basic shapes | Two boxes in an 'L' shape |
32//! | Complex concave | Use convex decomposition | Character mesh, furniture |
33//! | Very detailed mesh | Use [`TriMesh`](crate::shape::TriMesh) for static objects | Detailed terrain, static level geometry |
34//!
35//! # The V-HACD Algorithm
36//!
37//! V-HACD (Volumetric Hierarchical Approximate Convex Decomposition) works by:
38//! 1. **Voxelization**: Converting the input mesh into a 3D grid of voxels (or 2D pixels)
39//! 2. **Decomposition**: Recursively splitting the voxelized shape along planes that minimize concavity
40//! 3. **Convex Hull**: Computing the convex hull of each resulting part
41//!
42//! The algorithm balances:
43//! - **Quality**: How closely the parts approximate the original shape (controlled by `concavity`)
44//! - **Count**: How many convex parts to generate (controlled by `max_convex_hulls`)
45//! - **Performance**: How long the decomposition takes (controlled by `resolution`)
46//!
47//! # Basic Usage
48//!
49//! ## Quick Start (Default Parameters)
50//!
51//! The simplest way to decompose a mesh is using default parameters:
52//!
53//! ```no_run
54//! # #[cfg(all(feature = "dim3", feature = "f32"))] {
55//! use parry3d::math::Point;
56//! use parry3d::transformation::vhacd::VHACD;
57//! use parry3d::transformation::vhacd::VHACDParameters;
58//!
59//! // Define a simple concave mesh (an 'L' shape made of triangles)
60//! let vertices = vec![
61//! Point::new(0.0, 0.0, 0.0), Point::new(2.0, 0.0, 0.0),
62//! Point::new(2.0, 1.0, 0.0), Point::new(1.0, 1.0, 0.0),
63//! Point::new(1.0, 2.0, 0.0), Point::new(0.0, 2.0, 0.0),
64//! // Add corresponding back face vertices
65//! Point::new(0.0, 0.0, 1.0), Point::new(2.0, 0.0, 1.0),
66//! Point::new(2.0, 1.0, 1.0), Point::new(1.0, 1.0, 1.0),
67//! Point::new(1.0, 2.0, 1.0), Point::new(0.0, 2.0, 1.0),
68//! ];
69//! let indices = vec![
70//! // Front face triangles
71//! [0, 1, 2], [0, 2, 3], [0, 3, 4], [0, 4, 5],
72//! // Back face triangles
73//! [6, 8, 7], [6, 9, 8], [6, 10, 9], [6, 11, 10],
74//! // Connect front and back
75//! [0, 6, 7], [0, 7, 1], [1, 7, 8], [1, 8, 2],
76//! [2, 8, 9], [2, 9, 3], [3, 9, 10], [3, 10, 4],
77//! [4, 10, 11], [4, 11, 5], [5, 11, 6], [5, 6, 0],
78//! ];
79//!
80//! // Decompose with default parameters
81//! let decomposition = VHACD::decompose(
82//! &VHACDParameters::default(),
83//! &vertices,
84//! &indices,
85//! false, // don't keep voxel-to-primitive mapping
86//! );
87//!
88//! // Get the voxelized convex parts
89//! let parts = decomposition.voxel_parts();
90//! println!("Generated {} convex parts", parts.len());
91//!
92//! // Compute the convex hulls (for collision detection)
93//! let convex_hulls = decomposition.compute_convex_hulls(4);
94//! for (i, (vertices, indices)) in convex_hulls.iter().enumerate() {
95//! println!("Part {}: {} vertices, {} triangles", i, vertices.len(), indices.len());
96//! }
97//! # }
98//! ```
99//!
100//! ## Customizing Parameters
101//!
102//! For more control over the decomposition quality and performance:
103//!
104//! ```no_run
105//! # #[cfg(all(feature = "dim3", feature = "f32"))] {
106//! use parry3d::math::Point;
107//! use parry3d::transformation::vhacd::{VHACD, VHACDParameters};
108//! use parry3d::transformation::voxelization::FillMode;
109//!
110//! # let vertices = vec![
111//! # Point::new(0.0, 0.0, 0.0), Point::new(1.0, 0.0, 0.0),
112//! # Point::new(0.5, 1.0, 0.0), Point::new(0.5, 0.0, 1.0),
113//! # ];
114//! # let indices = vec![[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]];
115//! #
116//! // Configure parameters for higher quality decomposition
117//! let params = VHACDParameters {
118//! resolution: 128, // Higher = more detail (but slower)
119//! concavity: 0.001, // Lower = more parts but better fit
120//! max_convex_hulls: 32, // Maximum number of convex parts
121//! plane_downsampling: 4, // Precision of plane search
122//! convex_hull_downsampling: 4, // Precision of convex hull generation
123//! alpha: 0.05, // Bias toward symmetrical splits
124//! beta: 0.05, // Bias toward revolution axis splits
125//! convex_hull_approximation: true, // Approximate for speed
126//! fill_mode: FillMode::FloodFill {
127//! detect_cavities: false,
128//! },
129//! };
130//!
131//! let decomposition = VHACD::decompose(¶ms, &vertices, &indices, false);
132//! # }
133//! ```
134//!
135//! ## Working with Original Mesh Geometry
136//!
137//! By default, the convex hulls are computed from the voxelized representation. To get more
138//! accurate hulls based on the original mesh:
139//!
140//! ```no_run
141//! # #[cfg(all(feature = "dim3", feature = "f32"))] {
142//! use parry3d::math::Point;
143//! use parry3d::transformation::vhacd::{VHACD, VHACDParameters};
144//!
145//! # let vertices = vec![
146//! # Point::new(0.0, 0.0, 0.0), Point::new(1.0, 0.0, 0.0),
147//! # Point::new(0.5, 1.0, 0.0), Point::new(0.5, 0.0, 1.0),
148//! # ];
149//! # let indices = vec![[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]];
150//! #
151//! // Enable voxel-to-primitive mapping
152//! let decomposition = VHACD::decompose(
153//! &VHACDParameters::default(),
154//! &vertices,
155//! &indices,
156//! true, // <-- Keep mapping to original mesh primitives
157//! );
158//!
159//! // Compute exact convex hulls using original mesh geometry
160//! let exact_hulls = decomposition.compute_exact_convex_hulls(&vertices, &indices);
161//! println!("Generated {} exact convex hulls", exact_hulls.len());
162//! # }
163//! ```
164//!
165//! ## 2D Convex Decomposition
166//!
167//! The same API works in 2D for decomposing polylines:
168//!
169//! ```no_run
170//! # #[cfg(all(feature = "dim2", feature = "f32"))] {
171//! use parry2d::math::Point;
172//! use parry2d::transformation::vhacd::{VHACD, VHACDParameters};
173//!
174//! // Define a concave polyline (e.g., an 'L' shape)
175//! let vertices = vec![
176//! Point::new(0.0, 0.0), Point::new(2.0, 0.0),
177//! Point::new(2.0, 1.0), Point::new(1.0, 1.0),
178//! Point::new(1.0, 2.0), Point::new(0.0, 2.0),
179//! ];
180//! let indices = vec![
181//! [0, 1], [1, 2], [2, 3], [3, 4], [4, 5], [5, 0],
182//! ];
183//!
184//! let decomposition = VHACD::decompose(
185//! &VHACDParameters::default(),
186//! &vertices,
187//! &indices,
188//! false,
189//! );
190//!
191//! // Get convex polygons
192//! let convex_polygons = decomposition.compute_convex_hulls(4);
193//! for (i, polygon) in convex_polygons.iter().enumerate() {
194//! println!("Polygon {}: {} vertices", i, polygon.len());
195//! }
196//! # }
197//! ```
198//!
199//! # Integration with Physics Engines
200//!
201//! The decomposed convex parts can be used directly with physics engines:
202//!
203//! ```no_run
204//! # #[cfg(all(feature = "dim3", feature = "f32"))] {
205//! use parry3d::math::Point;
206//! use parry3d::shape::{SharedShape, Compound};
207//! use parry3d::transformation::vhacd::VHACDParameters;
208//! use parry3d::na::Isometry3;
209//!
210//! # let vertices = vec![
211//! # Point::new(0.0, 0.0, 0.0), Point::new(1.0, 0.0, 0.0),
212//! # Point::new(0.5, 1.0, 0.0), Point::new(0.5, 0.0, 1.0),
213//! # ];
214//! # let indices = vec![[0, 1, 2], [0, 2, 3], [0, 3, 1], [1, 3, 2]];
215//! #
216//! // Use the high-level API for direct integration
217//! let compound_shape = SharedShape::convex_decomposition(&vertices, &indices);
218//!
219//! // Or with custom parameters
220//! let params = VHACDParameters {
221//! concavity: 0.001,
222//! max_convex_hulls: 32,
223//! ..Default::default()
224//! };
225//! let compound_shape = SharedShape::convex_decomposition_with_params(
226//! &vertices,
227//! &indices,
228//! ¶ms,
229//! );
230//!
231//! // The resulting compound can be used as a collider shape
232//! println!("Created compound shape with convex parts");
233//! # }
234//! ```
235//!
236//! # Performance Tips
237//!
238//! 1. **Resolution**: Start with lower values (32-64) for fast iteration, increase for final quality
239//! 2. **Concavity**: Higher values (0.01-0.1) = fewer parts = faster but less accurate
240//! 3. **Max Convex Hulls**: Limit to reasonable values (8-32) for game objects
241//! 4. **Approximation**: Keep `convex_hull_approximation: true` for better performance
242//! 5. **Preprocessing**: Simplify your mesh before decomposition if it has excessive detail
243//!
244//! # Debugging Tips
245//!
246//! If the decomposition doesn't look right:
247//! - Visualize the voxelized parts using `voxel_parts()` to understand the algorithm's view
248//! - Try adjusting `resolution` if details are lost or voxelization is too coarse
249//! - Increase `max_convex_hulls` if the shape is still too concave
250//! - Decrease `concavity` for tighter fitting convex parts
251//! - Check that your mesh is manifold and has consistent winding order
252//!
253//! # Algorithm Details
254//!
255//! The V-HACD algorithm was developed by Khaled Mamou and is described in:
256//! > "Volumetric Hierarchical Approximate Convex Decomposition"
257//! > Khaled Mamou and Faouzi Ghorbel
258//!
259//! Implementation based on: <https://github.com/kmammou/v-hacd>
260//!
261//! # See Also
262//!
263//! - [`VHACDParameters`](crate::transformation::vhacd::VHACDParameters): Configuration parameters for the algorithm
264//! - [`VHACD`](crate::transformation::vhacd::VHACD): The main decomposition structure
265//! - [`SharedShape::convex_decomposition`](crate::shape::SharedShape::convex_decomposition): High-level API
266//! - [`convex_hull`](crate::transformation::convex_hull): For computing convex hulls directly
267//! - [`Compound`](crate::shape::Compound): For manually combining convex shapes
268
269pub use self::parameters::VHACDParameters;
270pub use self::vhacd::VHACD;
271
272pub(crate) use self::vhacd::CutPlane;
273
274mod parameters;
275mod vhacd;