More Web Proxy on the site http://driver.im/

Article

Efficient computation of a simplified medial axis

Authors:

Dinesh ManochaAuthors Info & Claims

SM '03: Proceedings of the eighth ACM symposium on Solid modeling and applications

Pages 96 - 107

https://doi.org/10.1145/781606.781623

Published: 16 June 2003 Publication History

Abstract

Applications of of the medial axis have been limited because of its instability and algebraic complexity. In this paper, we use a simplification of the medial axis, the θ-SMA, that is parameterized by a separation angle (θ) formed by the vectors connecting a point on the medial axis to the closest points on the boundary. We present a formal characterization of the degree of simplification of the θ-SMA as a function of θ, and we quantify the degree to which the simplified medial axis retains the features of the original polyhedron.We present a fast algorithm to compute an approximation of the θ-SMA. It is based on a spatial subdivision scheme, and uses fast computation of a distance field and its gradient using graphics hardware. The complexity of the algorithm varies based on the error threshold that is used, and is a linear function of the input size. We have applied this algorithm to approximate the SMA of models with tens or hundreds of thousands of triangles. Its running time varies from a few seconds, for a model consisting of hundreds of triangles, to minutes for highly complex models.

References

[1]

N. Amenta, S. Choi, and R. Kolluri. The power crust. In Proc. ACM Solid Modeling, pages 249--260, 2001.

Digital Library

[2]

D. Attali and J. Boissonnat. A linear bound on the complexity of the Delaunay triangulation of points on polyhedral surfaces. In Proc. ACM Solid Modeling, pages 139--146, 2002.

Digital Library

[3]

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

Digital Library

[4]

J. August, A. Tannenbaum, and S. Zucker. On the evolution of the skeleton. In Proc. Int. Conf. on Computer Vision, 1999.

[5]

H. Blum. A transformation for extracting new descriptors of shape. In W. Wathen-Dunn, editor, Models for the Perception of Speech and Visual Form, pages 362--380. MIT Press, 1967.

[6]

J.-D. Boissonnat. Geometric structures for three-dimensional shape representation. ACM Trans. Graph., 3(4):266--286, 1984.

Digital Library

[7]

J.-D. Boissonnat and F. Cazals. Smooth surface reconstruction via natural neighbour interpolation of distance functions. In ACM Symp. Computational Geometry, pages 223--232, 2000.

Digital Library

[8]

C.-S. Chiang. The Euclidean distance transform. Ph.D. thesis, Dept. Comput. Sci., Purdue Univ., West Lafayette, IN, Aug. 1992. Report CSD-TR 92-050.

Digital Library

[9]

H. I. Choi, S. W. Choi, and H. P. Moon. Mathematical theory of medial axis transform. Pacific J. Math., 181(1):56--88, 1997.

[10]

S. W. Choi and H.-P. Seidel. Linear onesided stability of MAT for weakly injective 3D domain. In Proc. ACM Solid Modeling, pages 344--355, 2002.

Digital Library

[11]

T. Culver, J. Keyser, and D. Manocha. Accurate computation of the medial axis of a polyhedron. In Proc. ACM Solid Modeling, pages 179--190, 1999.

Digital Library

[12]

P.-E. Danielsson. Euclidean distance mapping. Computer Graphics and Image Processing, 14:227--248, 1980.

[13]

T. K. Dey and W. Zhao. Approximate medial axis as a Voronoi subcomplex. In Proc. ACM Solid Modeling, pages 356--366, 2002.

Digital Library

[14]

T. K. Dey and W. Zhao. Approximating the medial axis from the Voronoi diagram with a convergence guarantee. In European Symp. Algorithms, pages 387--398, 2002.

Digital Library

[15]

D. Dutta and C. M. Hoffmann. A geometric investigation of the skeleton of CSG objects. In Proc. ASME Conf. Design Automation, 1990.

[16]

M. Etzion and A. Rappoport. Computing the Voronoi diagram of a 3-D polyhedron by separate computation of its symbolic and geometric parts. In Proc. ACM Solid Modeling, pages 167--178, 1999.

Digital Library

[17]

K. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha. Fast computation of generalized Voronoi diagrams using graphics hardware. Proc. ACM SIGGRAPH, pages 277--286, 1999.

Digital Library

[18]

C. M. Hoffmann. How to construct the skeleton of CSG objects. In Proc. 4th IMA Conf. on The Mathematics of Surfaces, Bath, UK, 1990. Oxford University Press.

[19]

L. Lam, S.-W. Lee, and C. Y. Chen. Thinning methodologies---A comprehensive survey. IEEE Trans. PAMI, 14(9):869--885, 1992.

Digital Library

[20]

E. Larsen, S. Gottschalk, M. Lin, and D. Manocha. Fast proximity queries with swept sphere volumes. Technical Report TR99-018, Dept. Comput. Sci., University of North Carolina, 1999.

[21]

V. Milenkovic. Robust construction of the Voronoi diagram of a polyhedron. In Proc. 5th Canad. Conf. Comput. Geom., pages 473--478, 1993.

[22]

I. Ragnemalm. The euclidean distance transformation in arbitrary dimensions. Pattern Recognition Letters, 14:883--888, 1993.

Digital Library

[23]

J. Reddy and G. Turkiyyah. Computation of 3D skeletons using a generalized Delaunay triangulation technique. Computer-Aided Design, 27:677--694, 1995.

[24]

E. C. Sherbrooke, N. M. Patrikalakis, and E. Brisson. Computation of the medial axis transform of 3-D polyhedra. In Proc. ACM Solid Modeling, pages 187--199. ACM, 1995.

Digital Library

[25]

K. Siddiqi, S. Bouix, A. Tannenbaum, and S. W. Zucker. The Hamilton-Jacobi skeleton. In International Conf. Computer Vision, pages 828--834, 1999.

Digital Library

[26]

D. W. Storti, G. M. Turkiyyah, M. A. Ganter, C. T. Lim, and D. M. Stal. Skeleton-based modeling operations on solids. In Proc. ACM Solid Modeling, pages 141--154, 1997.

Digital Library

[27]

M. Styner, G. Gerig, S. Joshi, and S. Pizer. Automatic and robust computation of 3D medial models incorporating object variability. International Journal of Computer Vision, to appear.

Digital Library

[28]

G. Taubin. A signal processing approach to fair surface design. In Proc. ACM SIGGRAPH, pages 351--358, 1995.

Digital Library

[29]

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(1):5--19, Jan. 1997.

[30]

J. Vleugels and M. Overmars. Approximating generalized Voronoi diagrams in any dimension. Technical Report UU-CS-1995-14, Dept. Comput. Sci., Utrecht University, 1995.

[31]

S. A. Wilmarth, N. M. Amato, and P. F. Stiller. Motion planning for a rigid body using random networks on the medial axis of the free space. ACM Symp. Computational Geometry, pages 173--180, 1999.

Digital Library

[32]

Y. Y. Zhang and P. S. P. Wang. Analytical comparison of thinning algorithms. Int. J. Pattern Recognit. Artif. Intell., 7:1227--1246, 1993.

Cited By

Huang QKraemer PThery SBechmann D(2024)Dynamic Skeletonization via Variational Medial Axis SamplingSIGGRAPH Asia 2024 Conference Papers10.1145/3680528.3687678(1-11)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3680528.3687678
Li BYe YYao JYang YXie WGe M(2024)A detail-preserving method for medial mesh computation in triangular meshesGraphical Models10.1016/j.gmod.2024.101236136(101236)Online publication date: Dec-2024
https://doi.org/10.1016/j.gmod.2024.101236
Li HZhang ZLiao BHua C(2024)An improving integration-enhanced ZNN for solving time-varying polytope distance problems with inequality constraintNeural Computing and Applications10.1007/s00521-024-10100-w36:29(18237-18250)Online publication date: 24-Jul-2024
https://doi.org/10.1007/s00521-024-10100-w
Show More Cited By

Index Terms

Efficient computation of a simplified medial axis
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision problems
        Reconstruction
      2. Computer vision representations
        Image representations
  2. Computer graphics
    1. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models

Recommendations

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 ...
Approximate medial axis as a voronoi subcomplex
SMA '02: Proceedings of the seventh ACM symposium on Solid modeling and applications

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 ...
Progressive medial axis filtration
SA '13: SIGGRAPH Asia 2013 Technical Briefs

The Scale Axis Transform provides a parametric simplification of the Medial Axis of a 3D shape which can be seen as a hierarchical description. However, this powerful shape analysis method has a significant computational cost, requiring several minutes ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SM '03: Proceedings of the eighth ACM symposium on Solid modeling and applications

June 2003

362 pages

ISBN:1581137060

DOI:10.1145/781606

Conference Chairs:
George Turkiyyah
University of Washington, USA
,
Pere Brunet
Polytechnical University of Catalonia, Barcelona, Spain
,
Program Chairs:
Gershon Elber
Technion, Israel
,
Vadim Shapiro
University of Wisconsin, USA

Copyright © 2003 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 16 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SM03

Sponsor:

SM03: 8th ACM Symposium on Solid Modeling and Applications

June 16 - 20, 2003

Washington, Seattle, USA

Acceptance Rates

SM '03 Paper Acceptance Rate 43 of 80 submissions, 54%;

Overall Acceptance Rate 86 of 173 submissions, 50%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

82
Total Citations
View Citations
1,012
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)1

Reflects downloads up to 17 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Huang QKraemer PThery SBechmann D(2024)Dynamic Skeletonization via Variational Medial Axis SamplingSIGGRAPH Asia 2024 Conference Papers10.1145/3680528.3687678(1-11)Online publication date: 3-Dec-2024
https://dl.acm.org/doi/10.1145/3680528.3687678
Li BYe YYao JYang YXie WGe M(2024)A detail-preserving method for medial mesh computation in triangular meshesGraphical Models10.1016/j.gmod.2024.101236136(101236)Online publication date: Dec-2024
https://doi.org/10.1016/j.gmod.2024.101236
Li HZhang ZLiao BHua C(2024)An improving integration-enhanced ZNN for solving time-varying polytope distance problems with inequality constraintNeural Computing and Applications10.1007/s00521-024-10100-w36:29(18237-18250)Online publication date: 24-Jul-2024
https://doi.org/10.1007/s00521-024-10100-w
Lieutier AWintraecken MSaha BServedio R(2023)Hausdorff and Gromov-Hausdorff Stable Subsets of the Medial AxisProceedings of the 55th Annual ACM Symposium on Theory of Computing10.1145/3564246.3585113(1768-1776)Online publication date: 2-Jun-2023
https://dl.acm.org/doi/10.1145/3564246.3585113
Erber MRosnitschek THartmann CAlber-Laukant BTremmel SVolk W(2022)Geometry-based Assurance of Directional Solidification for Complex Topology-optimized Castings using the Medial Axis TransformComputer-Aided Design10.1016/j.cad.2022.103394152(103394)Online publication date: Nov-2022
https://doi.org/10.1016/j.cad.2022.103394
Zrour RAndres ESidibe SLenain RLargeteau-Skapin G(2021)A 2D and 3D discrete bisector function based on annulusPattern Analysis and Applications10.1007/s10044-021-00973-1Online publication date: 30-Mar-2021
https://doi.org/10.1007/s10044-021-00973-1
Rebain DAngles BValentin JVining NPeethambaran JIzadi STagliasacchi A(2019)LSMAT Least Squares Medial Axis TransformComputer Graphics Forum10.1111/cgf.1359938:6(5-18)Online publication date: 30-Jan-2019
https://doi.org/10.1111/cgf.13599
Bayardo Spadafora JGomez-Fernandez FTaubin G(2019)Fast Non-Convex Hull Computation2019 International Conference on 3D Vision (3DV)10.1109/3DV.2019.00087(747-755)Online publication date: Sep-2019
https://doi.org/10.1109/3DV.2019.00087
Tamayo‐Mas EFeliu‐Fabà JCasado‐Antolin MRodríguez‐Ferran A(2019)A continuous‐discontinuous model for crack branchingInternational Journal for Numerical Methods in Engineering10.1002/nme.6125120:1(86-104)Online publication date: 17-Jun-2019
https://doi.org/10.1002/nme.6125
Yan YLetscher DJu T(2018)Voxel coresACM Transactions on Graphics10.1145/3197517.320139637:4(1-13)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201396
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