DocumentCode :
782336
Title :
An algorithm for the medial axis transform of 3D polyhedral solids
Author :
Sherbrooke, Evan C. ; Patrikalakis, Nicholas M. ; Brisson, Erik
Author_Institution :
New Technols. Inc., Bedford, MA, USA
Volume :
2
Issue :
1
fYear :
1996
fDate :
3/1/1996 12:00:00 AM
Firstpage :
44
Lastpage :
61
Abstract :
The medial axis transform (MAT) is a representation of an object which has been shown to be useful in design, interrogation, animation, finite element mesh generation, performance analysis, manufacturing simulation, path planning and tolerance specification. In this paper, an algorithm for determining the MAT is developed for general 3D polyhedral solids of arbitrary genus without cavities, with nonconvex vertices and edges. The algorithm is based on a classification scheme which relates different pieces of the medial axis (MA) to one another, even in the presence of degenerate MA points. Vertices of the MA are connected to one another by tracing along adjacent edges, and finally the faces of the axis are found by traversing closed loops of vertices and edges. Representation of the MA and its associated radius function is addressed, and pseudocode for the algorithm is given along with recommended optimizations. A connectivity theorem is proven to show the completeness of the algorithm. Complexity estimates and stability analysis for the algorithms are presented. Finally, examples illustrate the computational properties of the algorithm for convex and nonconvex 3D polyhedral solids with polyhedral holes
Keywords :
CAD; computational complexity; computational geometry; optimisation; solid modelling; 3D polyhedral solids; CAD; Voronoi diagram; adjacent edge tracing; algorithm completeness; algorithm computational properties; animation; axis faces; classification scheme; closed loop traversal; complexity estimates; computer-aided geometric design; connectivity theorem; convex solids; degenerate medial axis points; finite element mesh generation; geometric modelling; manufacturing simulation; medial axis transform; nonconvex solids; nonconvex vertices; object representation; optimization; path planning; performance analysis; polyhedral holes; pseudocode; radius function; skeleton; solid modelling; stability analysis; tolerance specification; Analytical models; Animation; Finite element methods; Marine technology; Mesh generation; Path planning; Shape; Skeleton; Solid modeling; Virtual manufacturing;
fLanguage :
English
Journal_Title :
Visualization and Computer Graphics, IEEE Transactions on
Publisher :
ieee
ISSN :
1077-2626
Type :
jour
DOI :
10.1109/2945.489386
Filename :
489386
Link To Document :
بازگشت