Removing excess topology from isosurfaces

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: Marco Attene , Silvia Biasotti , Michela Spagnuolo, Re-Meshing Techniques for Topological Analysis, Proceedings of the International Conference on Shape Modeling & Applications, p.142, May 07-11, 2001
• 3: Ulrike Axen, Computing Morse functions on triangulated manifolds, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.850-851, January 17-19, 1999, Baltimore, Maryland, United States
• 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: Stephan Bischoff , Leif P. Kobbelt, Isosurface Reconstruction with Topology Control, Proceedings of the 10th Pacific Conference on Computer Graphics and Applications, p.246, October 09-11, 2002
• 6: Hamish Carr , Jack Snoeyink , Ulrike Axen, Computing contour trees in all dimensions, Computational Geometry: Theory and Applications, v.24 n.2, p.75-94, February 2003 [doi>10.1016/S0925-7721(02)00093-7]
• 7: Éric Colin de Verdière , Francis Lazarus, Optimal System of Loops on an Orientable Surface, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.627-636, November 16-19, 2002
• 8: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 9: Brian Curless , Marc Levoy, A volumetric method for building complex models from range images, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.303-312, August 1996 [doi>10.1145/237170.237269]
• 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: 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 [doi>10.1145/777792.777846]
• 12: Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Disc. Comput. Geom. 28, 511--533.
• 13: Jihad El-Sana , Amitabh Varshney, Controlled simplification of genus for polygonal models, Proceedings of the 8th conference on Visualization '97, p.403-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 14: Jeff Erickson , Sariel Har-Peled, Optimally cutting a surface into a disk, Proceedings of the eighteenth annual symposium on Computational geometry, p.244-253, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513430]
• 15: Francis, G. and Weeks, J. 1999. Conway's ZIP proof. Amer. Math. Monthly 106, 393--399.
• 16: Michael Garland , Paul S. Heckbert, Surface simplification using quadric error metrics, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.209-216, August 1997 [doi>10.1145/258734.258849]
• 17: Xianfeng Gu , Steven J. Gortler , Hugues Hoppe, Geometry images, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 18: Igor Guskov , Andrei Khodakovsky , Peter Schröder , Wim Sweldens, Hybrid meshes: multiresolution using regular and irregular refinement, Proceedings of the eighteenth annual symposium on Computational geometry, p.264-272, June 05-07, 2002, Barcelona, Spain [doi>10.1145/513400.513443]
• 19: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 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: Taosong He , Lichan Hong , Amitabh Varshney , Sidney W. Wang, Controlled Topology Simplification, IEEE Transactions on Visualization and Computer Graphics, v.2 n.2, p.171-184, June 1996 [doi>10.1109/2945.506228]
• 22: 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 [doi>10.1145/383259.383282]
• 23: Adrian Hilton , A. J. Stoddart , John Illingworth , T. Windeatt, Reliable Surface Reconstructiuon from Multiple Range Images, Proceedings of the 4th European Conference on Computer Vision-Volume I, p.117-126, April 15-18, 1996
• 24: Hugues Hoppe, Progressive meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.99-108, August 1996 [doi>10.1145/237170.237216]
• 25: Hugues Hoppe , Tony DeRose , Tom Duchamp , John McDonald , Werner Stuetzle, Surface reconstruction from unorganized points, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.71-78, July 1992
• 26: Sylvain Jaume , Benoit M. Macq , Simon K. Warfield, Labeling the Brain Surface Using a Deformable Multiresolution Mesh, Proceedings of the 5th International Conference on Medical Image Computing and Computer-Assisted Intervention-Part I, p.451-458, September 25-28, 2002
• 27: Elena Kartasheva, The Algorithm for Automatic Cutting of Three-Dimensional Polyhedrons of h-Genus., Proceedings of the International Conference on Shape Modeling and Applications, p.26, March 01-04, 1999
• 28: Kaufman, A. 1987. Scan-conversion of polygons. In Proceedings of Eurographics. 197--208.
• 29: Andrei Khodakovsky , Peter Schröder , Wim Sweldens, Progressive geometry compression, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.271-278, July 2000 [doi>10.1145/344779.344922]
• 30: Ron Kikinis , Martha E. Shenton , Dan V. Iosifescu , Robert W. McCarley , Pairash Saiviroonporn , Hiroto H. Hokama , Andre Robatino , David Metcalf , Cynthia G. Wible , Chiara M. Portas , Robert M. Donnino , Ferenc A. Jolesz, A Digital Brain Atlas for Surgical Planning, Model-Driven Segmentation, and Teaching, IEEE Transactions on Visualization and Computer Graphics, v.2 n.3, p.232-241, September 1996 [doi>10.1109/2945.537306]
• 31: Marc van Kreveld , René van Oostrum , Chandrajit Bajaj , Valerio Pascucci , Dan Schikore, Contour trees and small seed sets for isosurface traversal, Proceedings of the thirteenth annual symposium on Computational geometry, p.212-220, June 04-06, 1997, Nice, France [doi>10.1145/262839.269238]
• 32: Jacques-Olivier Lachaud, Topologically defined iso-surfaces, Proceedings of the 6th International Workshop on Discrete Geometry for Computer Imagery, p.245-256, November 13-15, 1996
• 33: Francis Lazarus , Michel Pocchiola , Gert Vegter , Anne Verroust, Computing a canonical polygonal schema of an orientable triangulated surface, Proceedings of the seventeenth annual symposium on Computational geometry, p.80-89, June 2001, Medford, Massachusetts, United States [doi>10.1145/378583.378630]
• 34: Francis Lazarus , Anne Verroust, Level set diagrams of polyhedral objects, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.130-140, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304025]
• 35: Marc Levoy , Kari Pulli , Brian Curless , Szymon Rusinkiewicz , David Koller , Lucas Pereira , Matt Ginzton , Sean Anderson , James Davis , Jeremy Ginsberg , Jonathan Shade , Duane Fulk, The digital Michelangelo project: 3D scanning of large statues, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.131-144, July 2000 [doi>10.1145/344779.344849]
• 36: William E. Lorensen , Harvey E. Cline, Marching cubes: A high resolution 3D surface construction algorithm, Proceedings of the 14th annual conference on Computer graphics and interactive techniques, p.163-169, August 1987
• 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: Fakir S. Nooruddin , Greg Turk, Simplification and Repair of Polygonal Models Using Volumetric Techniques, IEEE Transactions on Visualization and Computer Graphics, v.9 n.2, p.191-205, April 2003 [doi>10.1109/TVCG.2003.1196006]
• 40: Jovan Popović , Hugues Hoppe, Progressive simplicial complexes, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.217-224, August 1997 [doi>10.1145/258734.258852]
• 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: Pedro V. Sander , John Snyder , Steven J. Gortler , Hugues Hoppe, Texture mapping progressive meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.409-416, August 2001 [doi>10.1145/383259.383307]
• 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: Yoshihisa Shinagawa , Tosiyasu L. Kunii, Constructing a Reeb graph automatically from cross sections, IEEE Computer Graphics and Applications, v.11 n.6, p.44-51, November 1991 [doi>10.1109/38.103393]
• 46: Andrzej Szymczak , James Vanderhyde, Extraction of Topologically Simple Isosurfaces from Volume Datasets, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.10, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250356]
• 47: Gert Vegter , Chee K. Yap, Computational complexity of combinatorial surfaces, Proceedings of the sixth annual symposium on Computational geometry, p.102-111, June 07-09, 1990, Berkley, California, United States [doi>10.1145/98524.98546]
• 48: Zoe Justine Wood , Peter Schroder, Computational topology algorithms for discrete 2-manifolds, 2003
• 49: Zoë J. Wood , Peter Schröder , David Breen , Mathieu Desbrun, Semi-regular mesh extraction from volumes, Proceedings of the conference on Visualization '00, p.275-282, October 2000, Salt Lake City, Utah, United States
• 50: Wyvill, B., McPheeters, C., and Wyvill, G. 1986. Data structure for soft objects. Vis. Comput. 2, 4, 227--234.
• 51: Afra Joze Zomorodian , Herbert Edelsbrunner, Computing and comprehending topology: persistence and hierarchical morse complexes, 2001

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.0 General

General Terms:
Algorithms, Performance

Keywords:
Topological artifacts, genus reduction, marching cubes, surface reconstruction