Mesh transformation

Meshes can be computed from other meshes as well. This may be useful to make them usable by some geometric queries that have specific requirements. For example most queries on Parry require the objects to be convex or to be the union of several convex objects. A convex hull or a convex decomposition may thus help to pre-process complex concave meshes.

Convex Hull

Besides the ToTriMesh and ToLinestrip traits, the procedural and transformation modules export free functions that generate various meshes and line strips, including those accessible by the two former traits.

It also exposes functions to compute the convex hull of a set of point using the QuickHull algorithm which has an average $O(n \log{n})$ time complexity:

Function	Description
convex_hull(...)	Computes the convex hull of a set of points.

If you are not interested in the Polyline representation of the 2D convex hull but only on the original indices of the vertices it contains, use the _idx variant of the function − namely convex_hull2d_idx(...). The following example creates 100,000 random points and compute their convex hull.

Example 2D

let mut points = Vec::new();

for _ in 0usize..100000 {

points.push(rand::random() * 2.0);

}

let _ = transformation::convex_hull(&points[..]);

Example 3D

let mut points = Vec::new();

for _ in range(0u, 100000) {

points.push(rand::random() * 2.0f32);

}

let convex_hull = transformation::convex_hull(&points[..]);

Approximate convex decomposition

While convex objects have nice properties that help designing efficient algorithms, studies show that using only convex objects leads to very boring applications! That is why Parry allows the description of concave objects from its convex parts using the Compound shape. For example, one could describe the following object as the union of two convex parts:

But decomposing manually a concave polyhedra into its convex parts is a very tedious task and computing an exact convex decomposition is often not necessary. That is why Parry implements the 3D HACD algorithm that computes an approximate convex decomposition. It is not yet implemented in 2D.

HACD

The HACD is simply a clustering algorithm based on a concavity criterion to separate the different groups. It will group triangles together until the directional distances between their vertices and their convex hull do not exceed an user-defined limit.

To compute the decomposition of a triangle mesh, use the procedural::hacd function. It takes three arguments:

Argument	Description
mesh	The TriMesh to decompose. It must have normals. Disconnected components of the mesh will not be merged together.
error	The maximum normalized concavity per cluster. It must not be close to a limit value like Bounded::max_value(). Values around 0.03 seems to give fine results for most objects.
min_components	Force the algorithm not to generate more than min_components convex parts.

Let us define what normalized concavity means. Because there is no official definition of the concavity of a 3D object, we are using the maximal distance between the triangle mesh vertices and its convex hull. This distance is computed along the direction of the vertex normal (hence, it is usually different from the intuitive distance obtained by orthogonal projection of the point on the closest convex hull face):

Then, to make this concavity measure kind of independent from the whole shape dimensions, it is divided by the object AABB diagonal $D$:

We call the ratio $\frac{d}{D}$ the normalized concavity. In this example, it is equal to $\frac{6.0}{10.0} = 0.6$.

The procedural::hacd function returns a tuple. Its first member is the set of convex objects that approximate the input mesh and the second one is the set of indices of the triangles used to compute each convex object.

The following figure shows a tube (left), the result of the clustering done by the HACD algorithm (middle), and the resulting approximate convex decomposition (right):

The following example creates a concave object using a path-based mesh generation and approximates it using the HACD algorithm. Together with kiss3d, this code was used to generate the figure above.

let control_points = [

Point3::new(0.0f32, 1.0, 0.0),

Point3::new(2.0, 4.0, 2.0),

Point3::new(2.0, 1.0, 4.0),

Point3::new(4.0, 4.0, 6.0),

Point3::new(2.0, 1.0, 8.0),

Point3::new(2.0, 4.0, 10.0),

Point3::new(0.0, 1.0, 12.0),

Point3::new(-2.0, 4.0, 10.0),

Point3::new(-2.0, 1.0, 8.0),

Point3::new(-4.0, 4.0, 6.0),

Point3::new(-2.0, 1.0, 4.0),

Point3::new(-2.0, 4.0, 2.0),

];

let bezier = procedural::bezier_curve(&control_points, 100);

let mut path = PolylinePath::new(&bezier);

let pattern = parry2d::procedural::unit_circle(100);

let mut pattern = PolylinePattern::new(pattern.coords(), true, NoCap::new(), NoCap::new());

let mut trimesh = pattern.stroke(&mut path);

// The path stroke does not generate normals =(

// Compute them as they are needed by the HACD.

trimesh.recompute_normals();

/*

* Decomposition of the mesh.

*/

let (decomp, partitioning) = transformation::hacd(trimesh.clone(), 0.03, 0);

// We end up with 7 convex parts.

assert!(decomp.len() == 7);

assert!(partitioning.len() == 7);