research-article

Topology Repair of Solid Models Using Skeletons

Authors:

Shi-Min HuAuthors Info & Claims

IEEE Transactions on Visualization and Computer Graphics, Volume 13, Issue 4

Pages 675 - 685

https://doi.org/10.1109/TVCG.2007.1015

Published: 01 July 2007 Publication History

Abstract

We present a method for repairing topological errors on solid models in the form of small surface handles, which often arise from surface reconstruction algorithms. We utilize a skeleton representation that offers a new mechanism for identifying and measuring handles. Our method presents two unique advantages over previous approaches. First, handle removal is guaranteed not to introduce invalid geometry or additional handles. Second, by using an adaptive grid structure, our method is capable of processing huge models efficiently at high resolutions.

References

[1]

H. Blum, “A Transformation for Extracting New Descriptors of Shape,” Models for the Perception of Speech and Visual Forms, W.Wathen-Dunn, ed., pp. 362-380, MIT Press, 1967.

[2]

N. Amenta, S. Choi, and R.K. Kolluri, “The Power Crust,” Proc. Sixth ACM Symp. Solid Modeling and Applications (SMA '01), pp.249-266, 2001.

Digital Library

[3]

T.K. Dey and W. Zhao, “Approximate Medial Axis as a Voronoi Subcomplex,” Proc. Seventh ACM Symp. Solid Modeling and Applications (SMA '02), pp. 356-366, 2002.

Digital Library

[4]

I. Ragnemalm, “The Euclidean Distance Transformation in Arbitrary Dimensions,” Pattern Recognition, vol. 14, pp. 883-888, 1993.

Digital Library

[5]

K. Siddiqi, S. Bouix, A. Tannenbaum, and S. Zucker, “The Hamilton-Jacobi Skeleton,” Proc. Int'l Conf. Computer Vision (ICCV '99), pp. 828-834, 1999, citeseer.ist.psu.edu/article/siddiqi99hamiltonjacobi.html.

Digital Library

[6]

L. Lam, S.-W. Lee, and C.Y. Suen, “Thinning Methodologies—A Comprehensive Survey,” IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 14, no. 9, pp. 869-885, 1992.

Digital Library

[7]

K. Palágyi and A. Kuba, “A Parallel 3D 12-Subiteration Thinning Algorithm,” Graphical Models Image Processing, vol. 61, no. 4, pp.199-221, 1999.

Digital Library

[8]

G. Bertrand, “Simple Points, Topological Numbers and Geodesic Neighborhoods in Cubic Grids,” Pattern Recognition Letters, vol. 15, no. 10, pp. 1003-1011, 1994.

Digital Library

[9]

J.-F. Mangin, V. Frouin, I. Bloch, J. Regis, and J. Lopez-Krahe, “From 3D Magnetic Resonance Images to Structural Representations of the Cortex Topography Using Topology Preserving Deformations,” J. Math. Imaging and Vision, vol. 5, pp. 297-318, 1995.

Digital Library

[10]

Z. Aktouf, G. Bertrand, and L. Perroton, “A 3D-Hole Closing Algorithm,” Proc. Sixth Int'l Workshop Discrete Geometry for Computer Imagery, pp. 36-47, 1996.

Digital Library

[11]

N. Kriegeskorte and R. Goebel, “An Efficient Algorithm for Topologically Correct Segmentation of the Cortical Sheet in Anatomical MR Volumes,” Neuroimage, vol. 14, no. 2, pp. 329-346, Aug. 2001.

[12]

S. Bischoff and L. Kobbelt, “Isosurface Reconstruction with Topology Control,” Proc. Pacific Conf. Computer Graphics and Applications, pp. 246-255, 2002.

Digital Library

[13]

B. Fischl, A.K. Liu, and A.M. Dale, “Automated Manifold Surgery: Constructing Geometrically Accurate and Topologically Correct Models of the Human Cerebral Cortex,” IEEE Trans. Medical Imaging, vol. 20, no. 1, pp. 70-80, 2001.

[14]

J. El-Sana and A. Varshney, “Controlled Simplification of Genus for Polygonal Models,” IEEE Visualization, pp. 403-412, 1997.

Digital Library

[15]

I. Guskov and Z.J. Wood, “Topological Noise Removal,” Graphics Interface, pp. 19-26, 2001.

Digital Library

[16]

M. Attene and B. Falcidieno, “Remesh: An Interactive Environment to Edit and Repair Triangle Meshes,” Proc. IEEE Int'l Conf. Shape Modeling and Applications (SMI '06), p. 41, 2006.

Digital Library

[17]

F.S. Nooruddin and G. Turk, “Simplification and Repair of Polygonal Models Using Volumetric Techniques,” IEEE Trans. Visual Computer Graphics, vol. 9, no. 2, pp. 191-205, 2003.

Digital Library

[18]

Z.J. Wood, H. Hoppe, M. Desbrun, and P. Schröder, “Removing Excess Topology from Isosurfaces,” ACM Trans. Graphics, vol. 23, no. 2, pp. 190-208, 2004.

Digital Library

[19]

W.E. Lorensen and H.E. Cline, “Marching Cubes: A High Resolution 3D Surface Construction Algorithm,” Proc. 14th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH '87), pp. 163-169, 1987.

Digital Library

[20]

D.W. Shattuck and R.M. Leahy, “Automated Graph Based Analysis and Correction of Cortical Volume Topology,” IEEE Trans. Medical Imaging, vol. 20, no. 11, pp. 1167-1177, 2001.

[21]

X. Han, C. Xu, U. Braga-Neto, and J.L. Prince, “Topology Correction in Brain Cortex Segmentation Using a Multi-Scale, Graph-Based Algorithm,” IEEE Trans. Medical Imaging, vol. 21, no. 2, pp. 109-121, 2002.

[22]

A. Szymczak and J. Vanderhyde, “Extraction of Topologically Simple Isosurfaces from Volume Datasets,” IEEE Visualization, pp.67-74, 2003.

Digital Library

[23]

S. Bischoff and L. Kobbelt, “Sub-Voxel Topology Control for Level-Set Surfaces,” Computer Graphics Forum, vol. 22, no. 3, pp.273-280, 2003.

[24]

T. Ju, “Robust Repair of Polygonal Models,” ACM Trans. Graphics, vol. 23, no. 3, pp. 888-895, 2004.

Digital Library

[25]

T. Ju, F. Losasso, S. Schaefer, and J. Warren, “Dual Contouring of Hermite Data,” Proc. 29th Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH '02), pp. 339-346, 2002.

Digital Library

[26]

G. Taubin, “A Signal Processing Approach to Fair Surface Design,” Proc. 22nd Ann. Conf. Computer Graphics and Interactive Techniques (SIGGRAPH '95), pp. 351-358, 1995.

Digital Library

[27]

J. Giesen and M. John, “The Flow Complex: A Data Structure for Geometric Modeling,” Proc. ACM-SIAM Symp. Discrete Algorithms (SODA '03), pp. 285-294, 2003.

Digital Library

[28]

A. Hatcher, Algebraic Topology. Cambridge Univ. Press, 2002.

[29]

S. Matveev, Algorithmic Topology and Classification of 3-Manifolds. Springer, 2003.

Digital Library

[30]

S. Bischoff and L. Kobbelt, “Structure Preserving CAD Model Repair,” Computer Graphics Forum, vol. 24, no. 3, pp. 527-536, 2005.

[31]

S. Bischoff and L. Kobbelt, “Topologically Correct Extraction of the Cortical Surface of a Brain Using Level-Set Methods,” Bildverarbeitung für die Medizin, pp. 50-54, 2004.

Cited By

Chen JJester JGopi M(2018)Fast Computation of Tunnels in Corneal Collagen StructureProceedings of Computer Graphics International 201810.1145/3208159.3208175(57-65)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3208159.3208175
Tagliasacchi ADelame TSpagnuolo MAmenta NTelea AMadeira JPatow G(2016)3D skeletonsProceedings of the 37th Annual Conference of the European Association for Computer Graphics: State of the Art Reports10.5555/3059330.3059333(573-597)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3059330.3059333
Zou MHolloway MCarr NJu T(2015)Topology-constrained surface reconstruction from cross-sectionsACM Transactions on Graphics10.1145/276697634:4(1-10)Online publication date: 27-Jul-2015
https://dl.acm.org/doi/10.1145/2766976
Show More Cited By

Index Terms

Topology Repair of Solid Models Using Skeletons

Recommendations

Skeleton based solid representation with topology preservation
Special issue on SPM 05

The medial axis (MA) of an object is homotopy equivalent to the solid model. This makes the medial axis a natural candidate for a skeleton representation of a general solid object. In addition, the medial axis transform is useful for many applications ...
Computing a family of skeletons of volumetric models for shape description

Skeletons are important shape descriptors in object representation and recognition. Typically, skeletons of volumetric models are computed using iterative thinning. However, traditional thinning methods often generate skeletons with complex structures ...
SMI 2012: Full Skeleton pruning by contour approximation and the integer medial axis transform

We present a new shape skeleton pruning algorithm based on contour approximation and the integer medial axis. The algorithm effectively removes unwanted branches, conserves the connectivity of the skeleton and respects the topological properties of the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Visualization and Computer Graphics

IEEE Transactions on Visualization and Computer Graphics Volume 13, Issue 4

July 2007

208 pages

ISSN:1077-2626

Issue’s Table of Contents

Copyright © 2007.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 July 2007

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chen JJester JGopi M(2018)Fast Computation of Tunnels in Corneal Collagen StructureProceedings of Computer Graphics International 201810.1145/3208159.3208175(57-65)Online publication date: 11-Jun-2018
https://dl.acm.org/doi/10.1145/3208159.3208175
Tagliasacchi ADelame TSpagnuolo MAmenta NTelea AMadeira JPatow G(2016)3D skeletonsProceedings of the 37th Annual Conference of the European Association for Computer Graphics: State of the Art Reports10.5555/3059330.3059333(573-597)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/3059330.3059333
Zou MHolloway MCarr NJu T(2015)Topology-constrained surface reconstruction from cross-sectionsACM Transactions on Graphics10.1145/276697634:4(1-10)Online publication date: 27-Jul-2015
https://dl.acm.org/doi/10.1145/2766976
Yin KHuang HZhang HGong MCohen-Or DChen B(2014)MorfitACM Transactions on Graphics10.1145/2661229.266124133:6(1-12)Online publication date: 19-Nov-2014
https://dl.acm.org/doi/10.1145/2661229.2661241
Ebke HCampen MBommes DKobbelt L(2014)Level-of-detail quad meshingACM Transactions on Graphics10.1145/2661229.266124033:6(1-11)Online publication date: 19-Nov-2014
https://dl.acm.org/doi/10.1145/2661229.2661240
Alhashim ILi HXu KCao JMa RZhang H(2014)Topology-varying 3D shape creation via structural blendingACM Transactions on Graphics10.1145/2601097.260110233:4(1-10)Online publication date: 27-Jul-2014
https://dl.acm.org/doi/10.1145/2601097.2601102
Dey TFan FWang Y(2013)An efficient computation of handle and tunnel loops via Reeb graphsACM Transactions on Graphics10.1145/2461912.246201732:4(1-10)Online publication date: 21-Jul-2013
https://dl.acm.org/doi/10.1145/2461912.2462017
Attene MCampen MKobbelt L(2013)Polygon mesh repairingACM Computing Surveys10.1145/2431211.243121445:2(1-33)Online publication date: 12-Mar-2013
https://dl.acm.org/doi/10.1145/2431211.2431214
Shen CZhang GLai YHu SMartin R(2010)Harmonic field based volume model construction from triangle soupJournal of Computer Science and Technology10.1007/s11390-010-9345-x25:3(562-571)Online publication date: 1-May-2010
https://dl.acm.org/doi/10.1007/s11390-010-9345-x
Hagbi NEl-Sana J(2008)A carving framework for topology simplification of polygonal meshesProceedings of the 5th international conference on Advances in geometric modeling and processing10.5555/1792279.1792284(47-61)Online publication date: 23-Apr-2008
https://dl.acm.org/doi/10.5555/1792279.1792284
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents