|
|
|
In this section we will explain the V-HACD algorithm and we will show where each of the parameters described in the former section is involved. A good explanation can be found in chapter 11 of the book Game Engine Gems 3.
|
|
|
|
|
|
|
|
The V-HACD consists on four steps:
|
|
|
|
1. Voxelization or tetrahedralization
|
|
|
|
In this initial step the model is voxelized or tetrahedralized (depending on value of
|
|
|
|
parameter mode).
|
|
|
|
The parameter resolution is used to set up the number of voxels (or size of the grid applied) generated during this step.
|
|
|
|
2. Hierarchical segmentation
|
|
|
|
This is the core of the algorithm. The set of voxels obtained in the former step are split in different subsets recursively until the concavity of each subset is smaller than the concavity parameter. In order to avoid infinite decompositions when the concavity criteria is not reached, the splitting process is stopped after a maximum number of iterations, this number of iteration is defined by the parameter depth. The depth parameter cannot longer be set by the user but it is obtained from the maxConvexHulls parameter.
|
|
|
|
Two important concepts are used in this phase: the calculation of the best splitting plane (clipping plane) and the calculation of the concavity of a subset of voxels.
|
|
|
|
|
|
|
|
##### Best clipping plane
|
|
|
|
The criteria applied to obtain the best clipping (or splitting) plane is that the best plane is the one with minimum energy function.
|
|
|
|
The energy function is the combination of three components:
|
|
|
|
- Connectivity
|
|
|
|
It is a normalized sum of the concavities of both voxel subsets (left and right) obtained after the clipping.
|
|
|
|
- Balance
|
|
|
|
Controls the difference in volume between the left and the right subset.The parameter alpha is used as a weight coefficient of this component.
|
|
|
|
- Symmetry
|
|
|
|
Controls the fact of obtaining clipping planes orthogonal (or almost orthogonal) to a revolution axis. The parameter beta is used as a weight coefficient of this component.
|
|
|
|
|
|
|
|
##### Concavity calculation
|
|
|
|
One of the main characteristics of this algorithm is that it uses volumetric information in its calculus. Specifically, it calculates the concavity of a subset of voxels as a difference of the volume of the subset and the volume of its convex hull.
|
|
|
|
|
|
|
|
3. Convex hull merging
|
|
|
|
After the segmentation a phase of merge is done to reduce the number of segmentations (sometimes oversegmentation happen).
|
|
|
|
The parameter maxConvexHulls is used to define the limit of this merging phase.
|
|
|
|
4. Convex hull adaptive sampling
|
|
|
|
This step is done to reduce the number of triangles and vertices of each convex hull obtained after the merge. The sampling does not change the shape though.
|
|
|
|
A recursive algorithm is used (see chapter 11 of the book Game Engine Gems 3) until the volume of the convex hull is smaller than the user defined parameter MinVolumePerCH or the number of vertices is higher than the parameter MaxNumVertices. |
|
|
\ No newline at end of file |
