Graphics Reference
In-Depth Information
Definition.
The
medial axis representation
or
medial axis transform
(
MAT
) of an
object consists of its medial axis together with the associated radius function in the
continuous case and the distance function in the discrete case.
One can show that an object is completely specified by its medial axis represen-
tation. See [Verm94] and [RosK76]. Furthermore, in the continuous case the enve-
lope of the maximal disks is just the boundary of the object. One nice thing about the
medial axis representation is that it depends on the geometry of the object and not
on the choice of coordinate axes like the quadtree or octree representation for dis-
crete objects defined by pixels or voxels.
Algorithms that compute medial axes divide into two types based on whether they
apply to discrete or continuous objects. The basic thinning algorithm for computing
the discrete medial axis is often referred to as the “
grassfire
”
algorithm
. If a fire
started at the boundary of the object were to burn into the object at a constant rate,
then it would meet in the medial axis. One starts on the boundary of the object and
strips away one layer of pixels or voxels after another until one reaches points that
the fire reaches from two directions. See [RosK76] and [WatP98] for thinning of two-
dimensional discrete sets. Similar arguments work in three dimensions.
In describing algorithms for finding the medial axis of continuous objects we shall
concentrate on three-dimensional objects. Such algorithms can be classified by the
specific approach that is used: volume thinning, tracing of seams and sheets, Voronoi
diagrams, or Delaunay triangulation. See [BBGS99] for advantages and disadvantages
for various schemes. [CuKM99] also describes previous work.
Volume Thinning.
One voxelizes the object and then computes the discrete medial
axis that is then polygonized. An additional extra pass is required at the end to deter-
mine the radius function. Of course, this will only determine an approximation to the
medial axis and one must be careful that it is accurate.
Tracing Approaches.
One tracing approach is described in [ShPB95]. One starts at
a known junction like a vertex of the polyhedron and then traces along an adjacent
seam, defined as the zero set of some functions, until one gets to another junction. At
that point one repeats this process for each seam that ends at that new junction. Polyg-
onal approximations to the seams are computed. The main difficulty is determining
the next junction. A similar approach is used in [CuKM99] but is claimed to be more
accurate because it uses exact arithmetic.
Voronoi Diagrams.
A number of algorithms use Voronoi diagrams because of their
close connection to the medial axis problem since they also deal with equidistant sets
of points. See Section 17.7 for a definition of Voronoi diagrams and some of their
properties. The idea is to use a suitable sample of points in the boundary and compute
their Voronoi diagram. See [Bran92], [ShPB95], or [ShPB96]. [CuKM99] describes an
algorithm for polyhedra via Voronoi diagram and exact arithmetic.
Delaunay Triangulations.
See Section 17.8 for a definition of a Delaunay triangu-
lation of a set of points. A Delaunay triangulation is the geometric dual to the Voronoi
diagram. [ShAR95] and [ShAR96] generate a domain Delaunay triangulation con-
sisting of a set of tetrahedra based on an adaptive collection of boundary points. The
medial axis is obtained from this triangulation.
