Computation of the Medial Axis Transform of 3-D polyhedra

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Computation of the Medial Axis Transform of 3-D polyhedra

Full text

Pdf (1.36 MB)

Source

ACM Symposium on Solid and Physical Modeling archive
Proceedings of the third ACM symposium on Solid modeling and applications table of contents

Salt Lake City, Utah, United States

Pages: 187 - 200

Year of Publication: 1995

ISBN:0-89791-672-7

Authors

Evan C. Sherbrooke	Massachusetts Institute of Technology, Department of Ocean Engineering, Design Laboratory, Cambridge, MA
Nicholas M. Patrikalakis	Massachusetts Institute of Technology, Department of Ocean Engineering, Design Laboratory, Cambridge, MA
Erik Brisson	Boston University, Office of Information Technology, Scientific Computing and Visualization Group, Boston, MA

Sponsor

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 9, Downloads (12 Months): 76, Citation Count: 13

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/218013.218059 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	ATR+91	C. G. Armstrong, T. K. H. Tam, D. J. Robinson, R. M. McKeag, and M. A. Price. Automatic generation of well structured meshes using medial axis and surface subdivision. In G. A. Gabriele, editor, Proceedings of the 17th ASME Design Automation Conference: Advances in Design Automation, Vol. 2, pages 139-146, Miami, FL, September 199 i. New York" ASME.
	Aur91	Franz Aurenhammer, Voronoi diagrams—a survey of a fundamental geometric data structure, ACM Computing Surveys (CSUR), v.23 n.3, p.345-405, Sept. 1991 [doi>10.1145/116873.116880]
	Blu67	H. Blum. A transformation for extracting new descriptors of shape. Models for the Perception of Speech and Visual Form, pages 362-381, ed: Weinant Wathen- Dunn MIT Press, 1967.
	Blu73	H. Blum. Biological shape and visual science (part I). Journal of Theoretical Biology, 38:205-287, 1973.
	BN78	H. Blum and R. N. Nagel. Shape description using weighted symmetric axis features. Pattern Recognition, 10(3)" 167-180, 1978.
	Boo79	F.L. Bookstein. The line skeleton. Computer Graphics and Image Processing, I 1" 123-137, 1979.
	Bra91	Jonathan Worthen Brandt, Theory and application of the skeleton representation of continuous shapes, University of California at Davis, Davis, CA, 1992
	Bra92	J.W. Brandt. Describing a solid with the threedimensional skeleton. In J. D. Warren, editor, Proceedings of The International Society for Optical Engineering Volume 1830, Curves and Surfaces in Computer Vision and Graphics 111, pages 258-269. SPIE, Boston, Massachusetts, 1992.
	Chi92	Ching-Shoei Chiang, The Euclidean distance transform, Purdue University, West Lafayette, IN, 1992
	CLR90	Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
	Dan80	P.-E. Danielsson. Euclidean distance mapping. Computer Graphics and Image Processing, 14:227-248, 1980.
	DH90	D. Dutta and C. M. Hoffmann. A geometric investigation of the skeleton of CSG objects. In B. Ravani, editor, of the 16th ASME Design Automation Conference: Advances in Design Automation, Computer Aided and Computational Design, volume I, pages 67- 75, Chicago, IL, September 1990. New York: ASME, 1990.
	DH93	D. Dutta and C. M. Hoffmann. On the skeleton of simple CSG objects. Journal of Mechanical Design, ASME Transactions, 115(1):87-94, March 1993.
	For92	S. Fortune. Voronoi diagrams and Delaunay triangulations, in D.-Z. Du and E K. Hwang, editors, Computing in Euclidean Geometry, pages 193-233. World Scientific, 1992.
	FP79	I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
	GD95	Sean M. Gelston , Debashish Dutta, Boundary surface recovery from skeleton curves and surfaces, Computer Aided Geometric Design, v.12 n.1, p.27-51, Feb. 1995 [doi>10.1016/0167-8396(94)E0055-V]
	GP91	H.N. Gursoy and N. M. Patrikalakis. Automated interrogation and adaptive subdivision of shape using medial axis transform. Advances in Engineering Software and Workstations, 13(5/6):287-302, September/November 1991.
	GP92a	H.N. Gursoy and N. M. Patrikalakis. An automated coarse and fine surface mesh generation scheme based on medial axis transform, part I: Algorithms. Engineering with Computers, 8(3):121-137, 1992.
	GP92b	H.N. Gursoy and N. M. Patrikalakis. An automated coarse and fine surface mesh generation scheme based on medial axis transform, part Ii: Implementation. Engineering with Computers, 8(4):179-196, 1992.
	GS85	Leonidas Guibas , Jorge Stolfi, Primitives for the manipulation of general subdivisions and the computation of Voronoi, ACM Transactions on Graphics (TOG), v.4 n.2, p.74-123, April 1985 [doi>10.1145/282918.282923]
	Gur89	H.N. Gursoy. Shape Interrogation by Medial Axis Transform for Automated Analysis. PhD thesis, Massachusetts institute of Technology, Cambridge, MA, November 1989.
	GVL89	G.H. Golub and C. E Van Loan. Matrix Computations. Johns Hopkins University Press, Baltimore, MD, 1989.
	Hel91	Martin Held, On the computational geometry of pocket machining, Springer-Verlag New York, Inc., New York, NY, 1991
	Hof91	C.M. Hoffmann. Computer vision, descriptive geometry, and classical mechanics. Technical Report CSD-TR-91-073, Computer Sciences Department, Purdue University, October 1991. Also in Proceedings of the Eurographics Workshop, Computer Graphics and Mathematics, October 1991, Genoa, Italy.
	Hof94	C.M. Hoffmann. How to construct the skeleton of CSG objects. In A. Bowyer and J. Davenport, editors, Proceedings of the Fourth IMA Conference, The Mathematics of Surfaces, UniversilT of Bath, UK, September 1990, New York, 1994. Oxford University Press.
	LBD+92	David Lavender , Adrian Bowyer , James Davenport , Andrew Wallis , John Woodwark, Voronoi Diagrams of Set-Theoretic solid Models, IEEE Computer Graphics and Applications, v.12 n.5, p.69-77, September 1992 [doi>10.1109/38.156016]
	Lee82	D.T. Lee. Medial axis transformation of a planar shape. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-4(4):363-369, July 1982.
	Mon69	Ugo Montanari, Continuous Skeletons from Digitized Images, Journal of the ACM (JACM), v.16 n.4, p.534-549, Oct. 1969 [doi>10.1145/321541.321543]
	MP93	Takashi Maekawa , Nicholas M. Patrikalakis, Computation of singularities and intersections of offsets of planar curves, Computer Aided Geometric Design, v.10 n.5, p.407-429, Oct. 1993 [doi>10.1016/0167-8396(93)90020-4]
	Nac82	L. R. Nackman. Curvature relations in threedimensional symmetric axes. Computer Graphics and Image Processing, 20:43-57, 1982.
	NP85	L.R. Nackman and S. M. Pizer. Three-dimensional shape description using the symmetric axis transform I" Theory. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-7(2): 187-202, March 1985.
	PG90	N.M. Patrikalakis and H. N. Gursoy. Shape interrogation by medial axis transform. In B. Ravani, editor, Proceedings of the 16th ASME Design Automation Conference: Advances in Design Automation, Computer Aided and Computational Design, Vol. 1, pages 77-88, Chicago, IL, September 1990. New York: ASME.
	Pre77	E P. Preparata. The medial axis of a simple polygon. In G. Goos and J. Hartmanis, editors, Lecture Notes in Computer Science: Mathematical Foundations of Computer Science, pages 443-450. Springer..Verlag, 1977.
	RT94	J.M. Reddy and G. Turkiyyah. Computation of 3d skeletons by a generalized Delaunay triangulation technique. Computer Aided Design, October 1994. To appear.
	SGP93	Atul Sudhalkar , Levent Gürsöz , Fritz Prinz, Continuous skeletons of discrete objects, Proceedings on the second ACM symposium on Solid modeling and applications, p.85-94, May 19-21, 1993, Montreal, Quebec, Canada [doi>10.1145/164360.164393]
	She95	Evan Conway Sherbrooke, 3-D shape interrogation by medial axis transform, Massachusetts Institute of Technology, Cambridge, MA, 1996
	SN87	Vijay Srinivasan , Lee R. Nackman, Voronoi diagram for multiply-connected polygonal domains 1: algorithm, IBM Journal of Research and Development, v.31 n.3, p.361-372, May 1, 1987
	SNTM92	V. Srinivasan, L. R. Nackman, J.-M. Tang, and S. N. Meshkat. Automatic mesh generation using the symmetric axis transformation of polygonal domains. Proceedings of the IEEE, Special Issue on Computational Geometry, 80(9): 1485-1501, 1992.
	SP93	Evan C. Sherbrooke , Nicholas M. Patrikalakis, Computation of the solutions of nonlinear polynomial systems, Computer Aided Geometric Design, v.10 n.5, p.379-405, Oct. 1993 [doi>10.1016/0167-8396(93)90019-Y]
	STZ89	G. L. Scott , S. C. Turner , A. Zisserman, Using a mixed wave/diffusion process to elicit the symmetry set, Image and Vision Computing, v.7 n.1, p.63-70, February 1989 [doi>10.1016/0262-8856(89)90022-X]
	Sug93	Kokichi Sugihara, Approximation of generalized Voronoi diagrams by ordinary Voronoi diagrams, CVGIP: Graphical Models and Image Processing, v.55 n.6, p.522-531, Nov. 1993 [doi>10.1006/cgip.1993.1039]
	TA91	T.K.H. Tam and C. G. Armstrong. 2d finite element mesh generation by medial axis subdivision. Advances in Engineering Sofm,are and Workstations, 13(5/6):313-324, September/November 1991.
	Ver94	Pamela Jean Vermeer, Medial axis transform to boundary representation conversion, Purdue University, West Lafayette, IN, 1994
	Wol85	E-E. Woiter. Cut Loci in Bordered and Unbordered Riemamlian Manifolds. PhD thesis, Technical University of Berlin, Department of Mathematics, December 1985.
	Wol92	F.-E. Wolter. Cut locus and medial axis in global shape interrogation and representation. Computer Aided Geometric Design, 1992. To appear. Also available as MIT Ocean Engineering Design Laboratory Memorandum 92-2, January 1992.
	ZSP93	J. Zhou, E. C. Sherbrooke, and N. M. Patrikalakis. Computation of stationary points of distance functions. Engineering with Computers, 9(4):231-246, Winter 1993.

CITED BY 13

	Kenneth E. Hoff, III , John Keyser , Ming Lin , Dinesh Manocha , Tim Culver, Fast computation of generalized Voronoi diagrams using graphics hardware, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.277-286, July 1999
	Robert Blanding , Cole Brooking , Mark Ganter , Duane Storti, A skeletal-based solid editor, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.141-150, June 08-11, 1999, Ann Arbor, Michigan, United States
	Tim Culver , John Keyser , Dinesh Manocha, Accurate computation of the medial axis of a polyhedron, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.179-190, June 08-11, 1999, Ann Arbor, Michigan, United States
	Mark Foskey , Ming C. Lin , Dinesh Manocha, Efficient computation of a simplified medial axis, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Duane W. Storti , George M. Turkiyyah , Mark A. Ganter , Chek T. Lim , Derek M. Stal, Skeleton-based modeling operations on solids, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.141-154, May 14-16, 1997, Atlanta, Georgia, United States
	John Keyser , Tim Culver , Dinesh Manocha , Shankar Krishnan, MAPC: a library for efficient and exact manipulation of algebraic points and curves, Proceedings of the fifteenth annual symposium on Computational geometry, p.360-369, June 13-16, 1999, Miami Beach, Florida, United States
	Evan C. Sherbrooke , Nicholas M. Patrikalakis , Erik Brisson, An Algorithm for the Medial Axis Transform of 3D Polyhedral Solids, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.44-61, March 1996
	Damian J. Sheehy , Cecil G. Armstrong , Desmond J. Robinson, Shape Description By Medial Surface Construction, IEEE Transactions on Visualization and Computer Graphics, v.2 n.1, p.62-72, March 1996
	Yuandong Yang , Oliver Brock , Robert N. Moll, Efficient and robust computation of an approximated medial axis, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Haixia Du , Hong Qin, Medial axis extraction and shape manipulation of solid objects using parabolic PDEs, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Ian Stroud , Gábor Renner , Paul Xirouchakis, A divide and conquer algorithm for medial surface calculation of planar polyhedra, Computer-Aided Design, v.39 n.9, p.794-817, September, 2007
	Nicu D. Cornea , Deborah Silver , Patrick Min, Curve-Skeleton Properties, Applications, and Algorithms, IEEE Transactions on Visualization and Computer Graphics, v.13 n.3, p.530-548, May 2007
	Brian Whited , Jarek Rossignac, Relative blending, Computer-Aided Design, v.41 n.6, p.456-462, June, 2009