Topology preserving surface extraction using adaptive subdivision

ABSTRACT

We address the problem of computing a topology preserving isosurface from a volumetric grid using Marching Cubes for geometry processing applications. We present a novel topology preserving subdivision algorithm to generate an adaptive volumetric grid. Our algorithm ensures that every grid cell satisfies two local geometric criteria: a complex cell criterion and a star-shaped criterion. We show that these two criteria are sufficient to ensure that the surface extracted from the grid using Marching Cubes has the same genus and connectedness as that of the exact isosurface. We use our subdivision algorithm for accurate boundary evaluation of CSG combinations of polyhedra and low degree algebraic primitives, translational motion planning, model simplification and remeshing. The running time of our algorithm varies between a few seconds for simple models composed of a few thousand triangles to tens of seconds for complex polyhedral models represented using hundreds of thousands of triangles.

REFERENCES

• 1: Jean-Daniel Boissonnat , David Cohen-Steiner , Gert Vegter, Isotopic implicit surface meshing, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA [doi>10.1145/1007352.1007401]
• 2: 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
• 3: {BMW00} Breen D., Mauch S., Whitaker R.: 3d scan conversion of csg models into distance, closest-point and color volumes. Proc. of Volume Graphics (2000), 135--158.
• 4: {CGMS00} Cignoni P., Ganovelli F., Montani C., Scopigno R.: Reconstruction of topologically correct and adaptive trilinear isosurfaces. Computers & Graphics 24, 3 (2000), 399--418.
• 5: Jonathan Cohen , Amitabh Varshney , Dinesh Manocha , Greg Turk , Hans Weber , Pankaj Agarwal , Frederick Brooks , William Wright, Simplification envelopes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.119-128, August 1996 [doi>10.1145/237170.237220]
• 6: 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
• 7: Sarah F. Frisken , Ronald N. Perry , Alyn P. Rockwood , Thouis R. Jones, Adaptively sampled distance fields: a general representation of shape for computer graphics, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.249-254, July 2000 [doi>10.1145/344779.344899]
• 8: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 9: Tao Ju , Frank Losasso , Scott Schaefer , Joe Warren, Dual contouring of hermite data, Proceedings of the 29th annual conference on Computer graphics and interactive techniques, July 23-26, 2002, San Antonio, Texas
• 10: Leif P. Kobbelt , Mario Botsch , Ulrich Schwanecke , Hans-Peter Seidel, Feature sensitive surface extraction from volume data, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.57-66, August 2001 [doi>10.1145/383259.383265]
• 11: 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
• 12: 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]
• 13: Raj Shekhar , Elias Fayyad , Roni Yagel , J. Fredrick Cornhill, Octree-based decimation of marching cubes surfaces, Proceedings of the 7th conference on Visualization '96, p.335-ff., October 28-29, 1996, San Francisco, California, United States
• 14: Barton T. Stander , John C. Hart, Guaranteeing the topology of an implicit surface polygonization for interactive modeling, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.279-286, August 1997 [doi>10.1145/258734.258868]
• 15: Gokul Varadhan , Shankar Krishnan , Young J. Kim , Suhas Diggavi , Dinesh Manocha, Efficient max-norm distance computation and reliable voxelization, Proceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing, June 23-25, 2003, Aachen, Germany
• 16: {VKSM04a} Varadhan G., Krishnan S., Sriram T., Manocha D.: A simple algorithm for complete motion planning of translating polyhedral robots. Workshop on the Algorithmic Foundations of Robotics (2004).
• 17: {VKSM04b} Varadhan G., Krishnan S., Sriram T., Manocha D.: Topology Preserving Isosurface Extraction Using Adaptive Subdivision. UNC Technical Report, 2004.
• 18: Jane Wilhelms , Allen Van Gelder, Topological considerations in isosurface generation extended abstract, ACM SIGGRAPH Computer Graphics, v.24 n.5, p.79-86, Nov. 1990
• 19: {WHDS02} Wood Z., Hoppe H., Desbrun M., Schroder P.: Iso-surface Topology Simplication. Tech. rep., Microsoft Research, MSR-TR-2002-28, 2002.
• 20: Steve Zelinka , Michael Garland, Permission grids: practical, error-bounded simplification, ACM Transactions on Graphics (TOG), v.21 n.2, p.207-229, April 2002 [doi>10.1145/508357.508363]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling