Zoë Wood
Hugues Hoppe
Skip Abstract Section
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.
- Aleksandrov, P. 1956. Combinatorial Topology. Vol. 1. Graylock Press.Google Scholar
- 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. Google Scholar
- Axen, U. 1999. Computing morse functions on triangulated manifolds. In Proceedings of the SIAM Symposium on Discrete Algorithms (SODA). 850--851. Google Scholar
- 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.Google Scholar
- Bischoff, S. and Kobbelt, L. 2002. Isosurface reconstruction with topology control. In Proceedings of Pacific Graphics. 246--255. Google Scholar
- Carr, H., Snoeyink, J., and Axen, U. 2003. Computing contour trees in all dimensions. Comput. Geom. 24, 2, 75--94. Google Scholar
- 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. Google Scholar
- Cormen, T., Leiserson, C., and Rivest, R. 1990. Introduction to Algorithms. MIT Press, Cambridge, Mass. Google Scholar
- 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. Google Scholar
- 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.Google Scholar
- 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. Google Scholar
- Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Disc. Comput. Geom. 28, 511--533.Google Scholar
- 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. Google Scholar
- Erickson, J. and Har-Peled, S. 2002. Optimally cutting a surface into a disk. In Proceedings of SOCG. ACM, New York, 244--253. Google Scholar
- Francis, G. and Weeks, J. 1999. Conway's ZIP proof. Amer. Math. Monthly 106, 393--399.Google Scholar
- Garland, M. and Heckbert, P. S. 1997. Surface simplification using quadric error metrics. Proceedings of SIGGRAPH. ACM, New York, 209--216. Google Scholar
- Gu, X., Gortler, S. J., and Hoppe, H. 2002. Geometry images. Proceedings of SIGGRAPH. ACM, New York, 355--361. Google Scholar
- 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. Google Scholar
- Guskov, I. and Wood, Z. 2001. Topological noise removal. Graph. Interf., 19--26. Google Scholar
- 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.Google Scholar
- He, T., Hong, L., Varshney, A., and Wang, S. W. 1996. Controlled Topology Simplification. IEEE Trans. Visual. Comput. Graph. 2, 2, 171--184. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- Hoppe, H. 1996. Progressive meshes. In Proceedings of SIGGRAPH. ACM, New York, 99--108. Google Scholar
- 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. Google Scholar
- Jaume, S., Macq, B., and Warfield, S. K. 2002. Labeling the brain surface using a deformable multiresolution mesh. In MICCAI. 451--457. Google Scholar
- 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. Google Scholar
- Kaufman, A. 1987. Scan-conversion of polygons. In Proceedings of Eurographics. 197--208.Google Scholar
- Khodakovsky, A., Schröder, P., and Sweldens, W. 2000. Progressive geometry compression. In Proceedings of SIGGRAPH. ACM, New York, 271--278. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- 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. Google Scholar
- Massey, W. 1967. Algebraic Topology: An Introduction. Harcourt, Brace & World, Inc., New York.Google Scholar
- Milnor, J. 1963. Morse Theory. Princeton University Press, Princeton, N.J.Google Scholar
- Nooruddin, F. and Turk, G. 2003. Simplification and repair of polygonal models using volumetric techniques. IEEE Trans. Visual. Comput. Graph. 9, 2, 191--205. Google Scholar
- Popovic, J. and Hoppe, H. 1997. Progressive simplicial complexes. In Proceedings of SIGGRAPH. ACM, New York, 217--224. Google Scholar
- 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.Google Scholar
- Sander, P., Snyder, J., Gortler, S., and Hoppe, H. 2001. Texture mapping progressive meshes. In Proceedings of SIGGRAPH. ACM, New York, 409--416. Google Scholar
- Schröder, P. and Sweldens, W., Eds. 2001. Digital Geometry Processing. Course Notes. In ACM SIGGRAPH. ACM, New York.Google Scholar
- Shattuck, D. W. and Leahy, R. M. 2001. Automated graph based analysis and correction of cortical volume topology. IEEE Trans. Med. Imag. 1167--1177.Google Scholar
- Shinagawa, Y. and Kunii, T. L. 1991. Constructing a reeb graph automatically from cross sections. IEEE Comput. Graph. Appl. 11, 6, 44--51. Google Scholar
- 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. Google Scholar
- Vegter, G. and Yapp, C. K. 1990. Computational complexity of combinatorial surfaces. In Proceedings of the 6th Annual Symposium on Computational Geometry. 93--111. Google Scholar
- Wood, Z. 2003. Computational topology algorithms for discrete 2-manifolds. Ph.D. dissertation. California Institute of Technology. Google Scholar
- Wood, Z., Desbrun, M., Schröder, P., and Breen, D. 2000. Semi-regular mesh extraction from volumes. In Proceedings of Visualization. 275--282. Google Scholar
- Wyvill, B., McPheeters, C., and Wyvill, G. 1986. Data structure for soft objects. Vis. Comput. 2, 4, 227--234.Google Scholar
- Zomorodian, A. 2001. Computing and comprehending topology: Persistence and hierarchical morse complexes. Ph.D. dissertation. University of Illinois at Urbana-Champaign. Google Scholar
Index Terms
- Removing excess topology from isosurfaces
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 '02We 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