What are perimeter and aspect ratio, in the context of 3D mesh approximate convex decomposition?

Question

I'm trying to understand the logic behind Mamou and Ghorbel's algorithm in their paper A Simple And Efficient Approach For 3D Mesh Approximate Convex Decomposition.

I cannot understand what is the aspect ratio of a surface as defined by the author. It includes the perimeter of two vertices v and w. These two vertices represent two triangles in the original mesh as they come from the dual graph as the authors define it. So I'm guessing they are talking about the perimeter of the two triangles these vertices correspond to. What is the perimeter of two triangles? Do they mean the sum?

The algorithm proceeds like this:

1. Create a dual graph of the mesh, where each vertex corresponds to a triangle of the original mesh, and two vertices are connected by an edge iff their corresponding triangles share an edge.

2. Iteratively choose and collapse an edge, so that two vertices are merged into one. We keep track of the "ancestors" of each vertex, A(v) that have been merged into it in this way.

Here's where I get confused:

The decimation process described in the previous section is guided by a cost function describing the concavity and the aspect ratio [5] of the surface \$S(v, w)\$ resulting from the unification of the vertices \$v\$ and \$w\$ and their ancestors:

$$S(v, w) = A(v) ∪ A(w) ∪ {w, v}. (2)$$

As in [5], we define the aspect ratio \$E_{shape}(v, w)\$ of the surface S(v, w) as follows:

$$E_{shape}(v, w) = \frac{ρ2(S(v, w))}{4π × σ(S(v, w))}, (3)$$

where \$ρ(S(v, w))\$ and \$σ(S(v, w))\$ are respectively the perimeter and the area of \$S(v, w)\$.

Answer 1

I wasn't able to find a free version of AK Jain's book "Fundamentals of digital image processing" referenced as [5], so this is a little bit of speculation on my part.

Since \$S(v, w)\$ is a subset of dual graph, formed from vertices v, w, and all of their ancestors from previous edge collapse operations, it corresponds to a contiguous subset of triangles in the original mesh.

• We can sum the area of each triangle that has been merged with v or w (including v & w's own corresponding triangles) to form the area of this 2D surface

• We can take all uncollapsed edges incident to v or w (but not both), and sum the lengths of their corresponding triangle edges in the original mesh to find the perimeter of this surface.

  (Note that after several edge collapse operations, you may have multiple edges joining a pair of vertices - representing multiple triangle edges forming the border between two clusters. If your collapse method simplifies these to a single edge, then you'll want to sum their lengths as you go or keep track of edge ancestors so you can find the total length along the border)

This construction will allow the aspect ratio to drop below 1 if the surface is curved (eg, if it's shaped like a fishbowl, with a large surface bounded by a narrow hoop). It could even drop to zero if v & w are the last two clusters in an island of the graph, so their union corresponds to a closed surface with no loose edges.