I'm currently in the process of implementing Approximate Convex Decomposition for Maya. This allows one type of skeletonization approach which using the decomposed shapes.
I have all of the work done to project the convex hull edges (i.e. the bridge edges) onto the mesh itself. The purpose of the project edges is to help determine the appropriate convex hull face (bridge) from which to calculate SL-concavity (the straight-line distance from a point on the mesh to the plane represented by the bridge). An example can be seen below:
I implemented Dijkstra's algorithm using the shortest distance between the points. For low-poly meshes like this dog, the resulting projection can deviate from an actual projection quite a bit. It would be better to have a more accurate projection than a shorter path. I was mistaken in my implementation! I changed the distance calculation to use perpendicular point-line distance instead. The green path is the new projected edge using point-line distance. The white path represents the original shortest distance projection.
Much better! Since we know the corresponding bridge faces for each projected edge, we can reduce the number of bridge faces to search through as we try to find the minimum SL-concavity. The problem lies with finding the corresponding faces for vertices that lie outside of the projected edges.
The approach I took was to iterate through each vertex with undetermined bridges and flood the area until projected edges were found. Usually, all of the projected edges share a common bridge face, which we use. Occasionally, in deeply concave areas, such as the underside of a dog, no common bridge face can be found. In such scenarios with multiple possible bridge faces, the closest bridge face by point-plane distance is used. The resulting concavity visualization:
And herein lies a potential fault of ACD (or SL-concavity). There aren't always intuitive decompositions based on concavity. For this dog model, we would expect at least one well-defined concave ring between the head and the body to separate the two body parts. Or a ring around the base of the limbs or a ring around the feet. However, they're not particularly easy to see in the visualization.
Of course, the visualization has limits and there may actually be significant points that aren't visible to the eye. There is a slight gradient around the neck that is overpowered by the range of concavities. For that purpose, ACD dedicates some time to find significant points on the body, also known as knots.