Accurate computation of the medial axis of a polyhedron

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Accurate computation of the medial axis of a polyhedron

Full text

Pdf (1.59 MB)

Source

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

Ann Arbor, Michigan, United States

Pages: 179 - 190

Year of Publication: 1999

ISBN:1-58113-080-5

Authors

Tim Culver	Department of Computer Science, University of North Carolina, Chapel Hill, NC
John Keyser	Department of Computer Science, University of North Carolina, Chapel Hill, NC
Dinesh Manocha	Department of Computer Science, University of North Carolina, Chapel Hill, NC

Sponsor

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 42, Citation Count: 23

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/304012.304030 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.

	1	S. S. Abhyankar , C. L. Bajaj, Automatic parameterization of rational curves and surfaces III: algebraic plane curves, Computer Aided Geometric Design, v.5 n.4, p.309-321, Nov. 1988 [doi>10.1016/0167-8396(88)90011-8]
	2	Pankaj K. Agarwal , Boris Aronov , Micha Sharir, Computing Envelopes in Four Dimensions with Applications, SIAM Journal on Computing, v.26 n.6, p.1714-1732, Dec. 1997 [doi>10.1137/S0097539794265724]
	3	Stefan Arnborg , Huichun Feng, Algebraic decomposition of regular curves, Journal of Symbolic Computation, v.5 n.1-2, p.131-140, February/April 1988 [doi>10.1016/S0747-7171(88)80009-9]
	4	M. O. Benouamer, D. Michelucci, and B. Peroche. Error-free boundary evaluation based on a lazy rational arithmetic: A detailed implementation. Computer Aided Design, 26(6):403- 416, June 1994.
	5	H. Blum. A transformation for extracting new descriptors of shape. In W. Wathen-Durm, editor, Models for the Perception of Speech and Visual Form, pages 362-380. MIT Press, 1'967.
	6	J. W. Brandt. Describing a solid with the three-dimensional 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, 1992.
	7	Hervé Brönnimann , Ioannis Z. Emiris , Victor Y. Pan , Sylvain Pion, Computing exact geometric predicates using modular arithmetic with single precision, Proceedings of the thirteenth annual symposium on Computational geometry, p.174-182, June 04-06, 1997, Nice, France [doi>10.1145/262839.262948]
	8	Hervé Brönnimann , Mariette Yvinec, Efficient exact evaluation of signs of determinants, Proceedings of the thirteenth annual symposium on Computational geometry, p.166-173, June 04-06, 1997, Nice, France [doi>10.1145/262839.262944]
	9	W. S. Brown , J. F. Traub, On Euclid's Algorithm and the Theory of Subresultants, Journal of the ACM (JACM), v.18 n.4, p.505-514, Oct. 1971 [doi>10.1145/321662.321665]
	10	John F. Canny, The complexity of robot motion planning, MIT Press, Cambridge, MA, 1988
	11	Ching-Shoei Chiang, The Euclidean distance transform, Purdue University, West Lafayette, IN, 1992
	12	K.L. Clarkson. Safe and effective determinant evaluation. In Proc. 33rd Annu. IEEE Sympos. Found. Comput. Sci., pages 387-395, 1992.
	13	culver , keyser , dm, Accurate Computation of the Medial Axis of a Polyhedron, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1998
	14	J. H. Davenport , Y. Siret , E. Tournier, Computer algebra (2nd ed.): systems and algorithms for algebraic computation, Academic Press Professional, Inc., San Diego, CA, 1993
	15	J. Demmel. LAPACK: A portable linear algebra library for supercomputers. In Proceedings of the 1989 IEEE Control Systems Society Workshop on Computer-Aided Control System Design, Tampa, FL, Dec 1989. IEEE.
	16	A. L. Dixon. The eliminant of the equations of four quadric surfaces. Proc. London Math. Soc., pages 340-352, 1910.
	17	D. Dutta and C. M. Hoffmann. A geometric investigation of the skeleton of CSG objects. In Proc. ASME Conf. Design Automation, 1990.
	18	D. Dutta and C. M. Hoffmann. On the skeleton of simple CSG objects. Journal of Mechanical Design, ASME Transactions, 115(I):87-94, 1993.
	19	G. Elber and M-S. Kim. The bisector surface of freeform rational space curves. Technical Report CIS Report #9619, Technion-Israel institute of Technology, September 1996.
	20	Steven Fortune, Polyhedral modelling with exact arithmetic, Proceedings of the third ACM symposium on Solid modeling and applications, p.225-234, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218065]
	21	S. J. Fortune. A sweepline algorithm for Voronoi diagrams. Algorithmica, 2:153-174, 1987.
	22	LiDIA Group. A library for computational number theory. Technical report, TH Darmstadt, Fachbereich Informatik, Institut fur Theoretische Informatik, 1997.
	23	M. Held. On computing Voronoi diagrams of convex polyhedra by means of wavefront propagation. In Proc. 6th Canad. Conf. Comput. Geom., pages 128-133, 1994.
	24	Martin Held. Voronoi diagrams and offset curves of curvilinear polygons. Computer-Aided Design, 30(4):287-300, 1998.
	25	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, University of Bath, UK, September 1990. Oxford University Press, New York, ~994.
	26	Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
	27	Kenneth E Hoff, III , Tim Culver , John Keyser , Ming Lin , Dinesh Manocha, Fast Computation of Generalized Voronoi Diagrams Using Graphics Hardware, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1999
	28	Toshiyuki Imai, A Topology Oriented Algorithm for the Voronoi Diagram of Polygons, Proceedings of the 8th Canadian Conference on Computational Geometry, p.107-112, August 12-15, 1996
	29	John K. Johnstone , Chanderjit L. Bajaj, Sorting points along an algebraic curve, SIAM Journal on Computing, v.19 n.5, p.925-967, Oct. 1990 [doi>10.1137/0219065]
	30	John Keyser , Shankar Krishnan , Dinesh Manocha, Efficient and accurate B-rep generation of low degree sculptured solids using exact arithmetic, Proceedings of the fourth ACM symposium on Solid modeling and applications, p.42-55, May 14-16, 1997, Atlanta, Georgia, United States [doi>10.1145/267734.267753]
	31	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 [doi>10.1145/304893.304990]
	32	Shankar Krishnan , Dinesh Manocha, Efficient and accurate boundary evaluation algorithms for boolean combinations of sculptured solids, 1997
	33	D.T. Lee. Medial axis transformation of a planar shape. IEEE Trans. Pattern Anal. Mach. Intell., PAMI-&363-369, 1982.
	34	ES. Macaulay. On ..some formula in elimination. Proceedings of London Mathematical Society, 1 (33):3-27, May tt902.
	35	V. Milenkovic. Robust construction of the Voronoi diagram of a polyhedron. In Proc. 5th Canad. Conf. Comput. Geom., pages 473-478, 1993.
	36	P. S. Milne. On the solutions of a set of polynomial equations. In Symbolic and Numerical Computation for Artificial Intelligence, pages 89-102, 1992.
	37	Paul Pedersen, Multivariate Sturm Theory, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.318-332, October 07-11, 1991
	38	Jayachandra Reddy and George Turkiyyah. Comp~tation of 3D skeletons using a generalized Delaunay triangulation technique. Computer-Aided Design, 27(9):677-694, 1995.
	39	Raimund Seidel, Linear programming and convex hulls made easy, Proceedings of the sixth annual symposium on Computational geometry, p.211-215, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98570]
	40	D. J. Sheehy , C. G. Armstrong , D. J. Robinson, Computing the medial surface of a solid from a domain Delaunay triangulation, Proceedings of the third ACM symposium on Solid modeling and applications, p.201-212, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218062]
	41	Evan C. Sherbrooke , Nicholas M. Patrikalakis , Erik Brisson, Computation of the Medial Axis Transform of 3-D polyhedra, Proceedings of the third ACM symposium on Solid modeling and applications, p.187-200, May 17-19, 1995, Salt Lake City, Utah, United States [doi>10.1145/218013.218059]
	42	V. Srinivasan, L. R. Nackman, J.-M. Tang, and S. N. Meshkat. Automatic mesh generation using the symmetric axis transform of polygonal domains. Proc. IEEE, 80(9):1485-1501, September 1992.
	43	K. Sugihara , M. Iri, A solid modelling system free from topological inconsistency, Journal of Information Processing, v.12 n.4, p.380-393, 1989
	44	Pamela Jean Vermeer, Medial axis transform to boundary representation conversion, Purdue University, West Lafayette, IN, 1994
	45	Jules Vleugels and Mark Overmars. Approximating general-. ized Voronoi diagrams in any dimension. Technical R epol~: UU-CS- 1995-14, Department of Computer Science, Utrecht University, 1995.
	46	E E. Wolter. Cut locus and medial axis in global shape interrogation and representation. Computer Aided Geometric" Design, 1992.
	47	Jiaxun Yu, Exact arithmetic solid modeling, Purdue University, West Lafayette, IN, 1992

CITED BY 23

	Nina Amenta , Sunghee Choi , Ravi Krishna Kolluri, The power crust, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.249-266, May 2001, Ann Arbor, Michigan, United States
	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
	Xuetao Li , Tong Wing Toon , Zhiyong Huang, Decomposing polygon meshes for interactive applications, Proceedings of the 2001 symposium on Interactive 3D graphics, p.35-42, March 2001
	Nina Amenta , Ravi Krishna Kolluri, Accurate and efficient unions of balls, Proceedings of the sixteenth annual symposium on Computational geometry, p.119-128, June 12-14, 2000, Clear Water Bay, Kowloon, Hong Kong
	Masaki Hilaga , Yoshihisa Shinagawa , Taku Kohmura , Tosiyasu L. Kunii, Topology matching for fully automatic similarity estimation of 3D shapes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.203-212, August 2001
	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
	Tamal K. Dey , Wulue Zhao, Approximate medial axis as a voronoi subcomplex, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Sung Woo Choi , Hans-Peter Seidel, Linear onesided stability of MAT for weakly injective 3D domain, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Tamal K. Dey , Hyuckje Woo , Wulue Zhao, Approximate medial axis for CAD models, Proceedings of the eighth ACM symposium on Solid modeling and applications, June 16-20, 2003, Seattle, Washington, USA
	Tim Culver , John Keyser , Dinesh Manocha, Exact computation of the medial axis of a polyhedron, Computer Aided Geometric Design, v.21 n.1, p.65-98, January 2004
	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
	Herbert Edelsbrunner , John Harer , Vijay Natarajan , Valerio Pascucci, Morse-smale complexes for piecewise linear 3-manifolds, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Shankar Krishnan , Mark Foskey , Tim Culver , John Keyser , Dinesh Manocha, PRECISE: efficient multiprecision evaluation of algebraic roots and predicates for reliable geometric computation, Proceedings of the seventeenth annual symposium on Computational geometry, p.274-283, June 2001, Medford, Massachusetts, United States
	F. Chazal , R. Soufflet, Stability and Finiteness Properties of Medial Axis and Skeleton, Journal of Dynamical and Control Systems, v.10 n.2, p.149-170, April 2004
	Frédéric Chazal , André Lieutier, The "λ-medial axis", Graphical Models, v.67 n.4, p.304-331, July 2005
	Avneesh Sud , Mark Foskey , Dinesh Manocha, Homotopy-preserving medial axis simplification, Proceedings of the 2005 ACM symposium on Solid and physical modeling, p.39-50, June 13-15, 2005, Cambridge, Massachusetts
	John Keyser , Tim Culver , Mark Foskey , Shankar Krishnan , Dinesh Manocha, ESOLID---A System for Exact Boundary Evaluation, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Ariel Shamir , Amir Shaham, Skeleton based solid representation with topology preservation, Graphical Models, v.68 n.3, p.307-321, May 2006
	Stephen M. Pizer , Kaleem Siddiqi , Gabor Székely , James N. Damon , Steven W. Zucker, Multiscale Medial Loci and Their Properties, International Journal of Computer Vision, v.55 n.2-3, p.155-179, November-December 2003
	Amir Shaham , Ariel Shamir , Daniel Cohen-Or, Medial axis based solid representation, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	F. Chazal , A. Lieutier, Stability and homotopy of a subset of the medial axis, Proceedings of the ninth ACM symposium on Solid modeling and applications, June 09-11, 2004, Genoa, Italy
	Hoon Hong , Erich Kaltofen , Michael Singer, East Coast Computer Algebra Day '99 (April 24, 1999): abstracts of invited talks and presented posters, ACM SIGSAM Bulletin, v.33 n.2, p.43-52, June 1999
	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