Article

Approximate medial axis as a voronoi subcomplex

Authors:

Wulue ZhaoAuthors Info & Claims

SMA '02: Proceedings of the seventh ACM symposium on Solid modeling and applications

Pages 356 - 366

https://doi.org/10.1145/566282.566333

Published: 17 June 2002 Publication History

Abstract

Medial axis as a compact representation of shapes has evolved as an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial axis is difficult in general, efforts continue to approximate them. One line of research considers the point cloud representation of the boundary surface of a solid and then attempts to compute an approximate medial axis from this point sample. It is known that the Voronoi vertices converge to the medial axis for a curve in 2D as the sample density approaches infinity. Unfortunately, the same is not true in 3D. Recently, it is discovered that a subset of Voronoi vertices called poles converge to the medial axis in 3D. However, in practice, a continuous approximation as opposed to a discrete one is sought. Recently few algorithms have been proposed which use the Voronoi diagram and its derivatives to compute this continuous approximation. These algorithms are scale or density dependent. Most of them do not have convergence guarantees, and one of them computes it indirectly from the power diagram of the poles. In this paper we present a new algorithm that approximates the medial axis straight from the Voronoi diagram in a scale and density independent manner with convergence guarantees. The advantage is that, unlike for others, one does not need to fine tune any parameter for this algorithm. We present extensive experimental evidences in support of our claims.

References

[1]

N. Amenta, S. Choi and R. K. Kolluri. The power crust. Proc. Solid Modeling '01, (2001), 249--260]]

Digital Library

[2]

D. Attali and J.-O. Lachaud. Delaunay conforming iso-surface, skeleton extraction and noise removal. Comput. Geom.: Theory Appl., 2001, to appear]]

Digital Library

[3]

D. Attali and A. Montanvert. Computing and simplifying 2D and 3D continuous skeletons. Computer Vision and Image Understanding bf 67(1997), 261--273]]

Digital Library

[4]

C. Bajaj, F. Bernardini and G. Xu. Automatic reconstruction of surfaces and scalar fields from 3D scans. SIGGRAPH 95, (1995), 109--118]]

Digital Library

[5]

F. Bernardini and C. L. Bajaj. Sampling and reconstructing manifolds using $alpha$-shapes. it Proc. 9th Canadian Conf. Comput. Geom.,(1997), 193--198]]

[6]

C. Bajaj, K. Lin, and E. Coyle. Arbitrary topology shape reconstruction from planar cross sections. Graphical Models and Image Processing bf 58 (1996), 524--543]]

Digital Library

[7]

G. Barequet and M. Sharir. Piecewise-linear interpolation between polygonal slices. Computer Vision and Image Understanding bf 63 (1996), 251--272]]

Digital Library

[8]

S. Bouix and K. Siddiqi. Divergence-based medial surfaces. Proc. European Conference on Computer Vision, 2000]]

Digital Library

[9]

J. D. Boissonnat. Geometric structures for three dimensional shape representation, ACM Transact. on Graphics 3(4), (1984) 266--286]]

Digital Library

[10]

J. D. Boissonnat and F. Cazals. Smooth surface reconstruction via natural neighbor interpolation of distance functions. Proc. 16th. ACM Sympos. Comput. Geom., (2000), 223--232]]

Digital Library

[11]

J. W. Brandt. Convergence and continuity criteria for discrete approximation of the continuous planar skeletons. CVGIP: Image Understanding bf 59 (1994), 116--124]]

Digital Library

[12]

J. W. Brandt and V. R. Algazi. Continuous skeleton computation by Voronoi diagram. Comput. Vision, Graphics, Image Process. bf 55 (1992), 329--338]]

Digital Library

[13]

B. Curless and M. Levoy. A volumetric method for building complex models from range images. SIGGRAPH 96, (1996), 303-312]]

Digital Library

[14]

T. Culver, J. Keyser and D. Manocha. Accurate computation of the medial axis of a polyhedron. Solid Modeling '99, (1999), 179--190]]

Digital Library

[15]

T. K. Dey and J. Giesen. Detecting undersampling in surface reconstruction. Proc. 17th Ann. Sympos. Comput. Geom. (2001), 257--263]]

Digital Library

[16]

T. K. Dey, J. Giesen and J. Hudson. Decimating samples for mesh simplification. Proc. 13th Canadian Conf. Comput. Geom. (2001), 85--88]]

[17]

T. K. Dey and W. Zhao. Approximating medial axis from the Voronoi diagram with convergence guarantee. Manuscript, 2001. http://www.cis.ohio-state.edu/$sim$tamaldey/paper/medial.pdf]]

[18]

H. Edelsbrunner. Shape reconstruction with Delaunay complex. it LNCS 1380, LATIN'98: Theoretical Informatics, (1998), 119--132]]

Digital Library

[19]

H. Edelsbrunner, D. G. Kirkpatrick and R. Seidel. On the shape of a set of points in the plane. IEEE Trans. Information Theory, bf 29, (1983), 551--559]]

Digital Library

[20]

H. Edelsbrunner and E. P. Mucke. Three-dimensional alpha shapes. ACM Trans. Graphics bf 13 (1994), 43--72]]

Digital Library

[21]

H. Edelsbrunner and N. Shah. Triangulating topological spaces. Proc. 10th ACM Sympos. Comput. Geom./, (1994), 285--292]]

Digital Library

[22]

M. Etzion and A. Rappoport. Computing Voronoi skeletons of a 3D polyhedron by space subdivision. Tech. Report, Hebrew University, 1999]]

[23]

P. J. Giblin and B. B. Kimia. A formal classification of 3D medial axis points and their local geometry. Proc. Computer Vision and Pattern Recognition (CVPR), 2000]]

[24]

Geomview tt http://www.geomview.org]]

[25]

L. Guibas, R. Holleman and L. E. Kavraki. A probabilistic roadmap planner for flexible objects with a workspace medial axis based sampling approach. Proc. IEEE/RSJ Intl. Conf. Intelligent Robots and Systems, 1999]]

[26]

H. N. Gursoy and N. M. Patrikalakis. Automated interrogation and adaptive subdivision of shape using medial axis transform. Advances in Engineering Software 13 (1991), 287--302]]

[27]

C. Hoffman. How to construct the skeleton of CSG objects. The Mathematics of Surfaces, IVA, Bowyer and J. Davenport Eds., Oxford Univ. Press, 1990]]

[28]

H. Hoppe, T. DeRose, T. Duchamp, J. McDonald and W. Stuetzle. Surface reconstruction from unorganized points. SIGGRAPH 92, (1992), 71--78]]

Digital Library

[29]

P. Hubbard. Approximating polyhedra with spheres for time critical collision detection. ACM Trans. Graphics bf 15 (1996), 179--210]]

Digital Library

[30]

C. Niblak, P. Gibbons and D. Capson. Generating skeletons and centerlines from the distance transform. CVGIP: Graphical Models and Image Processing bf 54 (1992), 420--437]]

Digital Library

[31]

R. L. Ogniewicz. Skeleton-space: A multiscale shape description combining region and boundary information. Proc. Computer Vision and Pattern Recognition, (1994), 746--751]]

[32]

D. Sheehy, C. Armstrong and D. Robinson. Shape description by medial axis construction. IEEE Trans. Visualization and Computer Graphics bf 2 (1996), 62--72]]

Digital Library

[33]

A. Sheffer, M. Etzion, A. Rappoport and M. Bercovier. Hexahedral mesh generation using the embedded Voronoi graph. Engineering Comput. 15 (1999), 248--262]]

[34]

E. C. Sherbrooke, N. M. Patrikalakis and E. Brisson. An algorithm for the medial axis transform of 3D polyhedral solids. IEEE Trans. Vis. Comput. Graphics 2 (1996), 44--61]]

Digital Library

[35]

D. Storti, G. Turkiyyah, M. Ganter, C. Lim and D. Stal. Skeleton-based modeling operations on solids. Solid Modeling '97 (1997), 141--154]]

Digital Library

[36]

G. M. Turkiyyah, D. W. Storti, M. Ganter, H. Chen and M. Vimawala. An accelerated triangulation method for computing the skeletons of free-form solid models. Computer Aided Design 29 (1997), 5--19]]

[37]

M. Teichman and S. Teller. Assisted articulation of closed polygonal models. Proc. 9th Eurographics Workshop on Animation and Simulation, 1998]]

Digital Library

[38]

F.-E. Wolter. Cut locus & medial axis in global shape interrogation & representation. MIT Design Laboratory Memorandum 92--2, 1992]]

[39]

www.cgal.org]]

[40]

www.cis.ohio-state.edu/~tamaldey/cocone.html]]

Cited By

Wang NHuang HSong SWang BWang WGuo X(2024)MATTopo: Topology-preserving Medial Axis Transform with Restricted Power DiagramACM Transactions on Graphics10.1145/368776343:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687763
Wang ZDou ZXu RLin CLiu YLong XXin SKomura TYuan XWang W(2024)Coverage Axis++: Efficient Inner Point Selection for 3D Shape SkeletonizationComputer Graphics Forum10.1111/cgf.1514343:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15143
YAO CSHI WLIU CCHEN HCHEN Q(2023)An overview of mobile robot navigation technologySCIENTIA SINICA Informationis10.1360/SSI-2022-042053:12(2303)Online publication date: 11-Dec-2023
https://doi.org/10.1360/SSI-2022-0420
Show More Cited By

Index Terms

Approximate medial axis as a voronoi subcomplex
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
  2. Computer graphics
    1. Image manipulation
      1. Image processing
    2. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Approximate medial axis for CAD models
SM '03: Proceedings of the eighth ACM symposium on Solid modeling and applications

Several research have pointed out the potential use of the medial axis in various geometric modeling applications. The computation of the medial axis for a three dimensional shape often becomes the major bottleneck in these applications. Towards this ...
Homotopy-preserving medial axis simplification
SPM '05: Proceedings of the 2005 ACM symposium on Solid and physical modeling

We present a novel algorithm to compute a simplified medial axis of a polyhedron. Our simplification algorithm tends to remove unstable features of Blum's medial axis. Moreover, our algorithm preserves the topological structure of the original medial ...
Approximating the Medial Axis from the Voronoi Diagram with a Convergence Guarantee

The medial axis of a surface in 3D is the closure of all points that have two or more closest points on the surface. It is an essential geometric structure in a number of applications involving 3D geometric shapes. Since exact computation of the medial ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SMA '02: Proceedings of the seventh ACM symposium on Solid modeling and applications

June 2002

424 pages

ISBN:1581135068

DOI:10.1145/566282

Conference Chairs:
Hans-Peter Seidel
Max-Planck-Institut für Informatik, Saarbrücken, Germany
,
Vadim Shapiro
University of Wisconsin, Madison, U.S.A.
,
Program Chairs:
Kunwoo Lee
Seoul National University, Seoul, Korea
,
Nick Patrikalakis
Massachsetts Institute of Technology, Cambridge, U.S.A.

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SM02

Sponsor:

SIGGRAPH

SM02: ACM Symposium on Solid Modeling and Applications 2002

June 17 - 21, 2002

Saarbrücken, Germany

Acceptance Rates

SMA '02 Paper Acceptance Rate 43 of 93 submissions, 46%;

Overall Acceptance Rate 86 of 173 submissions, 50%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

92
Total Citations
View Citations
874
Total Downloads

Downloads (Last 12 months)25
Downloads (Last 6 weeks)2

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang NHuang HSong SWang BWang WGuo X(2024)MATTopo: Topology-preserving Medial Axis Transform with Restricted Power DiagramACM Transactions on Graphics10.1145/368776343:6(1-16)Online publication date: 19-Dec-2024
https://dl.acm.org/doi/10.1145/3687763
Wang ZDou ZXu RLin CLiu YLong XXin SKomura TYuan XWang W(2024)Coverage Axis++: Efficient Inner Point Selection for 3D Shape SkeletonizationComputer Graphics Forum10.1111/cgf.1514343:5Online publication date: 31-Jul-2024
https://doi.org/10.1111/cgf.15143
YAO CSHI WLIU CCHEN HCHEN Q(2023)An overview of mobile robot navigation technologySCIENTIA SINICA Informationis10.1360/SSI-2022-042053:12(2303)Online publication date: 11-Dec-2023
https://doi.org/10.1360/SSI-2022-0420
Pan MZou RTong WGuo YChen F(2023) -smooth planar parameterization of complex domains for isogeometric analysis Computer Methods in Applied Mechanics and Engineering10.1016/j.cma.2023.116330417(116330)Online publication date: Dec-2023
https://doi.org/10.1016/j.cma.2023.116330
Wu YRytkin EBimrose MLi SChoi YLee GWang YTang LMadrid MWickerson GChang JGu JZhang YLiu JTawfick SHuang YKing WEfimov IRogers J(2023)A Sewing Approach to the Fabrication of Eco/bioresorbable ElectronicsSmall10.1002/smll.20230501719:49Online publication date: Aug-2023
https://doi.org/10.1002/smll.202305017
Nuvoli SPietroni NCignoni PScateni RTarini M(2022)SkinMixerACM Transactions on Graphics10.1145/3550454.355550341:6(1-15)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555503
Guo HLiu YPan HGuo B(2022)Implicit Conversion of Manifold B-Rep Solids by Neural Halfspace RepresentationACM Transactions on Graphics10.1145/3550454.355550241:6(1-15)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555502
Gao XZhong CXiang JHong YGuo YZhang J(2022)Reconstructing Personalized Semantic Facial NeRF Models from Monocular VideoACM Transactions on Graphics10.1145/3550454.355550141:6(1-12)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555501
Yu ZZhang CNowrouzezahrai DDong ZZhao S(2022)Efficient Differentiation of Pixel Reconstruction Filters for Path-Space Differentiable RenderingACM Transactions on Graphics10.1145/3550454.355550041:6(1-16)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555500
Zhang CElgharib MFox GGu MTheobalt CWang W(2022)An Implicit Parametric Morphable Dental ModelACM Transactions on Graphics10.1145/3550454.355546941:6(1-13)Online publication date: 30-Nov-2022
https://dl.acm.org/doi/10.1145/3550454.3555469
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents