SMA: An Approximate, Simplified Medial Axis

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.

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.

Resolution: 64x63x50.

Resolution: 32x31x25.
Timing Data
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

Mark Foskey
last updated: 6/4/02