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)

IMAGES

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