Medial Axis/Surface Transforms
Introduction
Definition: The
Medial Axis of a 2D
region is defined as the locus of the centre of all the maximal
inscribed circle of the object.
More Medial Axis Examples, CLICK
Here
In most commercial computer aided design systems, physical
objects are represented at a low level as a collection of
boundary topological elements; faces, edges, vertices, together
with the geometry associated with each elements. Often this
representation does not provide the shape information which is
required for subsequent modelling applications.
Medial
Axis can be used as a complimentary representation which
captures the geometric proximity of the boundary elements in a
simple forms. This led to an abstract shaped representation known
as
skeleton. it provides the unique description of shape
which is of lower dimension than the original object.
The term
Medial Axis Transform is use to describe a method
which reduces an objects to its medial axis and associated radius
function (distance from the medial axis to the closest point on
the object boundary) and provide a unique representation of the
object.
Medial Axis Computation
Given a set of points
S in
the plane, the
Delaunay
triangulation constructs a set of triangles whose vertices
are the points
S such that the circumcircle associated
with each triangle contains no other point in
S. This is
the geometric dual of the
Voronoi
diagram of
S. Each Delaunay triangle satisfies the
empty circumcircle property. Therefore, if the triangulation can
be constructed to conform to; the object boundary, then the
circumcircle approximate maximal circles and their circumcentres
approximate point on the medial axis (see figure below).
Since the density of the boundary point set required to give a
correct topological representation of the medial axis cannot be
established priori, and also to extract medial axis from a dense
triangulation will be too computationally expensive even with
today computing power; an adaptive refinement strategy is adopted
in research conducted by the QUB FE Group.
The algorithm has the following steps:
- Generation of an initial point set on the boundary of the
region
- Generate Delaunay triangulation of the point set
- Refined the triangulation by inserting tentative medial
axis exact tangent point.
- Retriangulate the new point set, and trace out the medial
axis
Medial Axis Tracing Algorithm
Since we are not using a
dense triangulation mesh to approximate a medial axis, it is
rather important to have a robust and accurate algorithm to trace
out the medial axis from the coarse triangulation.
The topological entities of the medial surface can be defined
quite simply on the basis of the number of degrees of the
translative freedom of the maximal sphere. In essence a medial
vertex, medial edge and medial face is associated with the centre
of a maximal sphere which has zero, one and two degrees of
freedom respectively. Therefore they are locally homeomorphic to
a point, line and plane respectively.
Tracing Algorithm
For each Medial Surface Vertex(MSV)
While neighbour not visited or NULL
Do Tracing
Tracing
if common entities >= 3
if neighbour is not a MSV
recursively do Tracing
else if neighbour is MSV
end Tracing
for this algorithm to work,
first we need to classify the tetrahedra inside the triangulation
to different type according to their vertices touching
entities.
I have created a little animated
gif(~121k) file to help
you visualize how the tracing can be done. Hope it can give you a
better idea of how tracing is used in this topic. If you still
have any doubts, please don't hesitate to contact
me.
Medial Surface Construction
As for the medial surface, we
can briefly approximate it by creating a faceted medial surface
from the Medial Surface type tetrahedra.
Input: model triangulation
Output: faceted medial surface
for each Medial Surface type tetrahedra
Do Rotate Around DelaunayEdge touching two and the
only two of the governor entities of the tetrahedra
till a polygon is formed
Facet the polygon
Again there are
gifs(~155k) file to
help you visualize this particular procedure.
Examples
You can simply browse to this
page where you can find more examples of
the medial objects in VRML format.
Just like the wed browser, in order to view VRML files, you would
need to have a VRML browser install, if you are not sure, check
it out over
here.
