Overview: We construct an approximate simplified medial axis of a polyhedral model using a volumetric approach, accelerated by graphics hardware. For each voxel, the distance and direction to the nearest feature on the surface of a model is computed, by a method based on the approach of Hoff et al. If two neighboring voxels have direction vectors to their respective nearest neighbors that differ by a sufficiently large angle, we assume that the medial axis passes between the two voxels. A surface representation of the medial axis is then generated by a simple surface reconstruction technique.
PREPRINT Efficient Computation of a Simplified Medial Axis
Mark Foskey, Ming Lin, Dinesh Manocha
Proc. ACM Symposium on Solid Modeling and Applications, 2003. pdf(1.2M)
Three images of the medial axis of a head model. First, the head and medial axis together. Then, just the medial axis. Finally, just the seam and boundary curves. In this and other images, the appearance of bumpiness in the medial axis results from the voxel-based surface reconstruction.
A mounting plate and its medial axis. Each sheet of the medial axis has been extracted and rendered in a different color. The pink curves are seams between medial axis sheets, and the purple curves make up the boundary of the extracted medial axis.
An elbow-shaped piece of piping (that fits through the above mounting plate). In this image, the medial axis is color coded by distance to the model surface, with blue indicating regions that are close, and yellow indicating greater distance.
A small portion of a shotgun shell, again color coded by sheets and seams.
primer_anvil.tri: A component of a shotgun shell.
torus_plain.tri: A wireframe torus, with medial axis in blue.
cup.tri: A teacup, with medial axis.
bunny.tri: Bunny. The first image shows the bunny with the medial axis in the interior, and the second shows just the medial axis. The third image shows the seam and boundary curves in pink and purple, respectively. Resolution is 128x126x100.
Timing data for selected cases. Tris: Number of triangles in model. Res: number of voxels along longest dimension. For more recent data, all three dimensions are reported. Gradients: time to compute direction vectors (negated normalized gradients of the distance field). Medial Axis: Time to extract the medial axis from the gradient information. The above images for these cases were computed with a resolution of 128.
Input Filename Tris Res Gradients Medial Axis torus_plain.tri 2000 128 8.813 1.156 torus_plain.tri 2000 64 3.344 0.532 cup.tri 8452 64 10.516 7.5 cup.tri 8452 128 27.672 25.453 shell_primer_anvil.tri 4340 256 86.188 37.578 shell_primer_anvil.tri 4340 64 17.969 8.266 shell_primer_anvil.tri 4340 128 24.734 13.657 bunny.tri 69451 128x126x100 455.349 13.376 bunny.tri 69451 64x63x50 150.564 2.766 bunny.tri 69451 32x31x25 54.407 0.297
last updated: 6/4/02