article

Removing excess topology from isosurfaces

Authors:

Mathieu Desbrun,

Peter SchröderAuthors Info & Claims

ACM Transactions on Graphics (TOG), Volume 23, Issue 2

Pages 190 - 208

https://doi.org/10.1145/990002.990007

Published: 01 April 2004 Publication History

Abstract

Many high-resolution surfaces are created through isosurface extraction from volumetric representations, obtained by 3D photography, CT, or MRI. Noise inherent in the acquisition process can lead to geometrical and topological errors. Reducing geometrical errors during reconstruction is well studied. However, isosurfaces often contain many topological errors in the form of tiny handles. These nearly invisible artifacts hinder subsequent operations like mesh simplification, remeshing, and parametrization. In this article we present a practical method for removing handles in an isosurface. Our algorithm makes an axis-aligned sweep through the volume to locate handles, compute their sizes, and selectively remove them. The algorithm is designed to facilitate out-of-core execution. It finds the handles by incrementally constructing and analyzing a Reeb graph. The size of a handle is measured by a short nonseparating cycle. Handles are removed robustly by modifying the volume rather than attempting "mesh surgery." Finally, the volumetric modifications are spatially localized to preserve geometrical detail. We demonstrate topology simplification on several complex models, and show its benefits for subsequent surface processing.

References

[1]

Aleksandrov, P. 1956. Combinatorial Topology. Vol. 1. Graylock Press.

[2]

Attene, M., Biasotti, S., and Spagnuolo, M. 2001. Re-meshing techniques for topological analysis. In International Conference of Shape Modeling and Applications (Genova, Italy). IEEE Computer Society Press, Los Alamitos, Calif., 142--151.

[3]

Axen, U. 1999. Computing morse functions on triangulated manifolds. In Proceedings of the SIAM Symposium on Discrete Algorithms (SODA). 850--851.

[4]

Axen, U. and Edelsbrunner, H. 1998. Auditory morse analysis of triangulated manifolds. In Mathematical Visualization, H.-C. Hege and K. Polthier, Eds. Springer-Verlag, Berlin, Germany, 223--236.

[5]

Bischoff, S. and Kobbelt, L. 2002. Isosurface reconstruction with topology control. In Proceedings of Pacific Graphics. 246--255.

[6]

Carr, H., Snoeyink, J., and Axen, U. 2003. Computing contour trees in all dimensions. Comput. Geom. 24, 2, 75--94.

[7]

Colin de Verdière, É. and Lazarus, F. 2002. Optimal system of loops on an orientable surface. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science (Vancouver, B.C., Canada). IEEE Computer Society Press, Los Alamitos, Calif., 627--636.

[8]

Cormen, T., Leiserson, C., and Rivest, R. 1990. Introduction to Algorithms. MIT Press, Cambridge, Mass.

[9]

Curless, B. and Levoy, M. 1996. A volumetric method for building complex models from range images. In Proceedings of SIGGRAPH. ACM, New York, 303--312.

[10]

Dey, T. K. and Schipper, H. 1995. A new technique to compute polygonal schema for 2-manifolds with applications to null-homotopy detection. Disc. Comput. Geom. 14, 93--110.

[11]

Edelsbrunner, H., Harer, J., Natarajan, V., and Pascucci, V. 2003. Morse complexes for piecewise linear 3-manifolds. In Proceedings of the 19th Annual ACM Symposium on Computer Geometry. ACM, New York, 98--101.

[12]

Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Disc. Comput. Geom. 28, 511--533.

[13]

El-Sana, J. and Varshney, A. 1997. Controlled simplification of genus for polygonal models. In Proceedings of IEEE Visualization. IEEE Computer Society Press, Los Alamitos, Calif., 403--412.

[14]

Erickson, J. and Har-Peled, S. 2002. Optimally cutting a surface into a disk. In Proceedings of SOCG. ACM, New York, 244--253.

[15]

Francis, G. and Weeks, J. 1999. Conway's ZIP proof. Amer. Math. Monthly 106, 393--399.

[16]

Garland, M. and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. Proceedings of SIGGRAPH. ACM, New York, 209--216.

[17]

Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry images. Proceedings of SIGGRAPH. ACM, New York, 355--361.

[18]

Guskov, I., Khodakovsky, A., SchrAder, P., and Sweldens, W. 2002. Hybrid meshes: multiresolution using regular and irregular refinement. In Proceedings of the 18th Annual Symposium on Computational Geometry. ACM, New York, 264--272.

[19]

Guskov, I. and Wood, Z. 2001. Topological noise removal. Graph. Interf., 19--26.

[20]

Han, X., Xu, C., and Prince, J. L. 2001. A topology preserving deformable model using level sets. In Proceedings of the IEEE Computer Vision and Pattern Recognition. IEEE Computer Society Press, Los Alamitos, Calif., 765--770.

[21]

He, T., Hong, L., Varshney, A., and Wang, S. W. 1996. Controlled Topology Simplification. IEEE Trans. Visual. Comput. Graph. 2, 2, 171--184.

[22]

Hilaga, M., Shinagawa, Y., Kohmura, T., and Kunii, T. L. 2001. Topology matching for fully automatic similarity estimation of 3d shapes. In Proceedings of SIGGRAPH. ACM, New York, 203--212.

[23]

Hilton, A., Toddart, A. J., Illingworth, J., and Windeatt, T. 1996. Reliable surface reconstruction from multiple range images. Fourth European Conference on Computer Vision I, 117--126.

[24]

Hoppe, H. 1996. Progressive meshes. In Proceedings of SIGGRAPH. ACM, New York, 99--108.

[25]

Hoppe, H., DeRose, T., Duchamp, T., McDonald, J., and Stuetzle, W. 1992. Surface reconstruction from unorganized points. In Computer Graphics (Proceedings of SIGGRAPH 92). ACM, New York, 71--78.

[26]

Jaume, S., Macq, B., and Warfield, S. K. 2002. Labeling the brain surface using a deformable multiresolution mesh. In MICCAI. 451--457.

[27]

Kartasheva, E. 1999. The algorithm for automatic cutting of three-dimensional polyhedron of h-genus. In International Conference of Shape Modeling and Applications (Aizu, Japan). IEEE Computer Society Press, Los Alamitos, Calif., 26--33.

[28]

Kaufman, A. 1987. Scan-conversion of polygons. In Proceedings of Eurographics. 197--208.

[29]

Khodakovsky, A., Schröder, P., and Sweldens, W. 2000. Progressive geometry compression. In Proceedings of SIGGRAPH. ACM, New York, 271--278.

[30]

Kikinis, R., Shenton, M. E., Iosifescu, D. V., McCarley, R. W., Saiviroonporn, P., Hokama, H. H., Robatino, A., Metcalf, D., Wible, C. G., Portas, C. M., Donnino, R., and Jolesz, F. A. 1996. A digital brain atlas for surgical planning, model driven segmentation and teaching. IEEE Trans. Visual. Comput. Graph., 232--241.

[31]

Kreveld, M. V., van Oostrum, R., Bajaj, C., Pascucci, V., and Schikore, D. 1997. Contour trees and small seed sets for isosurface traversal. In Proceedings of the 13th ACM Symposium on Computational Geometry. ACM, New York, 212--219.

[32]

Lachaud, J.-O. 1996. Topologically Defined Iso-surfaces. In Proceedings of the 6th Discrete Geometry for Computer Imagery (DGCI). Lecture Notes in Computer Science, Vol. 1176. Springer-Verlag, New York, 245--256.

[33]

Lazarus, F., Pocchiola, M., Vegter, G., and Verroust, A. 2001. Computing a canonical polygonal schema of an orientable triangulated surface. In Proceedings of the ACM SOCG. ACM, New York, 80--89.

[34]

Lazarus, F. and Verroust, A. 1999. Level set diagrams of polyhedral objects. In Proceedings of the ACM Solid Modeling'99 (Ann Arbor, Mich.). ACM, New York, 130--140.

[35]

Levoy, M., Pulli, K., Curless, B., Rusinkiewicz, S., Koller, D., Pereira, L., Ginzton, M., Anderson, S., Davis, J., Ginsberg, J., Shade, J., and Fulk, D. 2000. The digital Michelangelo project: 3D scanning of large statues. In Proceedings of SIGGRAPH. ACM, New York, 131--144.

[36]

Lorensen, W. E. and Cline, H. E. 1987. Marching cubes: A high resolution 3d surface construction algorithm. In Proceedings of SIGGRAPH. ACM, New York, 163--169.

[37]

Massey, W. 1967. Algebraic Topology: An Introduction. Harcourt, Brace & World, Inc., New York.

[38]

Milnor, J. 1963. Morse Theory. Princeton University Press, Princeton, N.J.

[39]

Nooruddin, F. and Turk, G. 2003. Simplification and repair of polygonal models using volumetric techniques. IEEE Trans. Visual. Comput. Graph. 9, 2, 191--205.

[40]

Popovic, J. and Hoppe, H. 1997. Progressive simplicial complexes. In Proceedings of SIGGRAPH. ACM, New York, 217--224.

[41]

Reeb, G. 1946. Sur les points singuliers d'une forme de Pfaff complètement intégrable ou d'une fonction numérique. Comptes Rendus Acad. Sci. de Paris. 847--849.

[42]

Sander, P., Snyder, J., Gortler, S., and Hoppe, H. 2001. Texture mapping progressive meshes. In Proceedings of SIGGRAPH. ACM, New York, 409--416.

[43]

Schröder, P. and Sweldens, W., Eds. 2001. Digital Geometry Processing. Course Notes. In ACM SIGGRAPH. ACM, New York.

[44]

Shattuck, D. W. and Leahy, R. M. 2001. Automated graph based analysis and correction of cortical volume topology. IEEE Trans. Med. Imag. 1167--1177.

[45]

Shinagawa, Y. and Kunii, T. L. 1991. Constructing a reeb graph automatically from cross sections. IEEE Comput. Graph. Appl. 11, 6, 44--51.

[46]

Szymczak, A. and Vanderhyde, J. 2003. Extraction of topologically simple isosurfaces from volume datasets. In Proceedings of Visualization 2003. IEEE Computer Society Press, Los Alamitos, Calif.

[47]

Vegter, G. and Yapp, C. K. 1990. Computational complexity of combinatorial surfaces. In Proceedings of the 6th Annual Symposium on Computational Geometry. 93--111.

[48]

Wood, Z. 2003. Computational topology algorithms for discrete 2-manifolds. Ph.D. dissertation. California Institute of Technology.

[49]

Wood, Z., Desbrun, M., Schröder, P., and Breen, D. 2000. Semi-regular mesh extraction from volumes. In Proceedings of Visualization. 275--282.

[50]

Wyvill, B., McPheeters, C., and Wyvill, G. 1986. Data structure for soft objects. Vis. Comput. 2, 4, 227--234.

[51]

Zomorodian, A. 2001. Computing and comprehending topology: Persistence and hierarchical morse complexes. Ph.D. dissertation. University of Illinois at Urbana-Champaign.

Cited By

Sorgente TBiasotti SManzini GSpagnuolo M(2023)A Survey of Indicators for Mesh Quality AssessmentComputer Graphics Forum10.1111/cgf.1477942:2(461-483)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14779
Weinrauch AMlakar DSeidel HSteinberger MZayer R(2023)A Variational Loop Shrinking Analogy for Handle and Tunnel Detection and Reeb Graph Construction on SurfacesComputer Graphics Forum10.1111/cgf.1476342:2(309-320)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14763
Zeng DChambers ELetscher DJu T(2022)Topological Simplification of Nested ShapesComputer Graphics Forum10.1111/cgf.1461141:5(161-173)Online publication date: 6-Oct-2022
https://doi.org/10.1111/cgf.14611
Show More Cited By

Index Terms

Removing excess topology from isosurfaces
1. Computing methodologies
  1. Computer graphics

Recommendations

Simplified patterns for extracting the isosurfaces of solid objects

By moving the positions of isosurface vertice from the cube edge interpolation points as in the standard marching cubes (MC), to the centers of the corresponding occupied cube vertices, this paper presents a set of much simpler triangulation patterns ...
Approximating normals for marching cubes applied to locally supported isosurfaces
VIS '02: Proceedings of the conference on Visualization '02

We present some new methods for computing estimates of normal vectors at the vertices of a triangular mesh surface approximation to an isosurface which has been computed by the marching cube algorithm. These estimates are required for the smooth ...
Optimizing the topological and combinatorial complexity of isosurfaces

Since the publication of the original Marching Cubes algorithm, numerous variations have been proposed for guaranteeing water-tight constructions of triangulated approximations of isosurfaces. Most approaches divide the 3D space into cubes that each ...

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Graphics

ACM Transactions on Graphics Volume 23, Issue 2

April 2004

112 pages

ISSN:0730-0301

EISSN:1557-7368

DOI:10.1145/990002

Issue’s Table of Contents

Copyright © 2004 ACM.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 2004

Published in TOG Volume 23, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

206
Total Citations
View Citations
1,463
Total Downloads

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

Reflects downloads up to 21 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Sorgente TBiasotti SManzini GSpagnuolo M(2023)A Survey of Indicators for Mesh Quality AssessmentComputer Graphics Forum10.1111/cgf.1477942:2(461-483)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14779
Weinrauch AMlakar DSeidel HSteinberger MZayer R(2023)A Variational Loop Shrinking Analogy for Handle and Tunnel Detection and Reeb Graph Construction on SurfacesComputer Graphics Forum10.1111/cgf.1476342:2(309-320)Online publication date: 23-May-2023
https://doi.org/10.1111/cgf.14763
Zeng DChambers ELetscher DJu T(2022)Topological Simplification of Nested ShapesComputer Graphics Forum10.1111/cgf.1461141:5(161-173)Online publication date: 6-Oct-2022
https://doi.org/10.1111/cgf.14611
Cohen-Addad Vde Verdière ÉMarx Dde Mesmay A(2021)Almost Tight Lower Bounds for Hard Cutting Problems in Embedded GraphsJournal of the ACM10.1145/345070468:4(1-26)Online publication date: 14-Jul-2021
https://dl.acm.org/doi/10.1145/3450704
Werner KGarth C(2021)Unordered Task-Parallel Augmented Merge Tree ConstructionIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.307687527:8(3585-3596)Online publication date: 1-Aug-2021
https://dl.acm.org/doi/10.1109/TVCG.2021.3076875
Vidal JGuillou PTierny J(2021)A Progressive Approach to Scalar Field TopologyIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.306050027:6(2833-2850)Online publication date: 1-Jun-2021
https://doi.org/10.1109/TVCG.2021.3060500
Bakke Bjerkevik H(2021)On the Stability of Interval Decomposable Persistence ModulesDiscrete & Computational Geometry10.1007/s00454-021-00298-066:1(92-121)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s00454-021-00298-0
Hajij MRosen P(2020)An Efficient Data Retrieval Parallel Reeb Graph AlgorithmAlgorithms10.3390/a1310025813:10(258)Online publication date: 12-Oct-2020
https://doi.org/10.3390/a13100258
Zeng DChambers ELetscher DJu T(2020)To cut or to fillACM Transactions on Graphics10.1145/3414685.341785439:6(1-18)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417854
Fang GZhang TZhong SChen XZhong ZWang C(2020)Reinforced FDMACM Transactions on Graphics10.1145/3414685.341783439:6(1-15)Online publication date: 27-Nov-2020
https://dl.acm.org/doi/10.1145/3414685.3417834
Show More Cited By

View Options

Get Access

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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents