Manifold Approximation of 3D Medial Axis

Tyler Casella - CSC 572 Spring 2012

The medial axis of an object is the union of all points within the object that are the closest point for two or more points on the object's surface. The medial axis holds important information on the object's geometric properties. However, obtaining the exact medial axis for a given object is non-trivial. The goal of this project is to implement the ideas presented by Shin Yoshizawa for generating a manifold approximation of the 3D medial axis of a polyhedral mesh for use in mesh fracturing. This project was built off of source code provided by Yoshizawa and aims to extend the functionality to provide an approximation of the inner surfaces of a mesh after fracturing off a portion of the surface.

Algorithm Steps

1. Generate point cloud from mesh
2. Use Qhull to generate the Delaunay triangulation of the points
3. Voronoi diagram derived from Delaunay triangulation (dual graph)
4. Each vertex of the surface now has a voronoi cell associated with it.
5. For each vertex, remove any voronoi vertices which are outside the bounding box of the mesh or lay on the positive side of the plane defined by the vertex and its normal.
6. Average the remaining voronoi vertices to obtain a single vertex approximating the point on the medial axis.
7. Connectivity between points on the approximate medial axis remain to the same as the surface vertices they are associated with

Accuracy

The current medial axis approximation is a decent estimation, however requires additional fine-tuning to achieve a more consistent and accurate medial axis. Voronoi diagrams tend to produce an erratic medial axis when noise is present in the mesh. This can be seen in the bunny10k mesh above.

Additionally, the medial axis approximation becomes less accurate as the density of the point cloud decreases. To combat this, faces can be subdivided a number of times prior to being sent to Qhull.

References

Yoshizawa, Shin. Manifold Approximation of 3D Medial Axis
Qhull
C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. 1996. The quickhull algorithm for convex hulls. ACM Trans. Math. Softw. 22, 4 (December 1996), 469-483.