Computing geometry-aware handle and tunnel loops in 3D models

ABSTRACT

Many applications such as topology repair, model editing, surface parameterization, and feature recognition benefit from computing loops on surfaces that wrap around their 'handles' and 'tunnels'. Computing such loops while optimizing their geometric lengths is difficult. On the other hand, computing such loops without considering geometry is easy but may not be very useful. In this paper we strike a balance by computing topologically correct loops that are also geometrically relevant. Our algorithm is a novel application of the concepts from topological persistence introduced recently in computational topology. The usability of the computed loops is demonstrated with some examples in feature identification and topology simplification.

REFERENCES

• 1: Pierre Alliez , David Cohen-Steiner , Mariette Yvinec , Mathieu Desbrun, Variational tetrahedral meshing, ACM SIGGRAPH 2005 Papers, July 31-August 04, 2005, Los Angeles, California
• 2: Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum (Proc. Eurographics) 27.
• 3: S. Biasotti , D. Giorgi , M. Spagnuolo , B. Falcidieno, Reeb graphs for shape analysis and applications, Theoretical Computer Science, v.392 n.1-3, p.5-22, February, 2008 [doi>10.1016/j.tcs.2007.10.018]
• 4: Bischoff, S., and Kobbelt, L. 2005. Structure preserving CAD model repair. Comput. Graphics Forum 24, 527--536.
• 5: Chen, C., and Freedman, D. 2008. Quantifying homology classes. In Sympos. Theoretical Aspects Comput. Sci., 169--180.
• 6: Cheng, S.-W., Dey, T. K., and Levine, J. A. 2007. A practical Delaunay meshing algorithm for a large class of domains. In Proc. 16th Internat. Meshing Roundtable, 477--494.
• 7: David Cohen-Steiner , Herbert Edelsbrunner , Dmitriy Morozov, Vines and vineyards by updating persistence in linear time, Proceedings of the twenty-second annual symposium on Computational geometry, June 05-07, 2006, Sedona, Arizona, USA [doi>10.1145/1137856.1137877]
• 8: Tamal K. Dey , Jian Sun, Defining and computing curve-skeletons with medial geodesic function, Proceedings of the fourth Eurographics symposium on Geometry processing, June 26-28, 2006, Cagliari, Sardinia, Italy
• 9: Tamal K. Dey , Kuiyu Li , Jian Sun, On Computing Handle and Tunnel Loops, Proceedings of the 2007 International Conference on Cyberworlds, p.357-366, October 24-26, 2007 [doi>10.1109/CW.2007.49]
• 10: Tamal K. Dey, Curve and Surface Reconstruction: Algorithms with Mathematical Analysis (Cambridge Monographs on Applied and Computational Mathematics), Cambridge University Press, New York, NY, 2006
• 11: Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Discrete Comput. Geom. 28, 511--533.
• 12: 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
• 13: Éric Colin de Verdière , Jeff Erickson, Tightening non-simple paths and cycles on surfaces, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.192-201, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109580]
• 14: Éric Colin de Verdière, and Lazarus, F. 2005. Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33, 507--534.
• 15: Jeff Erickson , Kim Whittlesey, Greedy optimal homotopy and homology generators, Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms, January 23-25, 2005, Vancouver, British Columbia
• 16: 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
• 17: Igor Guskov , Zoë J. Wood, Topological noise removal, No description on Graphics interface 2001, p.19-26, June 07-09, 2001, Ottawa, Ontario, Canada
• 18: Hatcher, A. 2002. Algebraic Topology. Cambridge University Press.
• 19: 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]
• 20: Xinlai Ni , Michael Garland , John C. Hart, Fair morse functions for extracting the topological structure of a surface mesh, ACM SIGGRAPH 2004 Papers, August 08-12, 2004, Los Angeles, California
• 21: 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]
• 22: Oudot, S., Rineau, L., and Yvinec, M. 2005. Meshing volumes bounded by smooth surfaces. In Proc. 14th Internat. Meshing Roundtable, 203--219.
• 23: Valerio Pascucci , Giorgio Scorzelli , Peer-Timo Bremer , Ajith Mascarenhas, Robust on-line computation of Reeb graphs: simplicity and speed, ACM Transactions on Graphics (TOG), v.26 n.3, July 2007
• 24: Shattuck, D. W., and Leahy, R. M. 2001. Automated graph-based analysis and correction of cortical volume topology. IEEE Trans. Med. Imaging 20, 1167--1177.
• 25: Alla Sheffer , John C. Hart, Seamster: inconspicuous low-distortion texture seam layout, Proceedings of the conference on Visualization '02, October 27-November 01, 2002, Boston, Massachusetts
• 26: Zoë Wood , Hugues Hoppe , Mathieu Desbrun , Peter Schröder, Removing excess topology from isosurfaces, ACM Transactions on Graphics (TOG), v.23 n.2, p.190-208, April 2004 [doi>10.1145/990002.990007]
• 27: Xiaotian Yin , Miao Jin , Xianfeng Gu, Computing shortest cycles using universal covering space, The Visual Computer: International Journal of Computer Graphics, v.23 n.12, p.999-1004, November 2007 [doi>10.1007/s00371-007-0169-9]
• 28: Qian-Yi Zhou , Tao Ju , Shi-Min Hu, Topology Repair of Solid Models Using Skeletons, IEEE Transactions on Visualization and Computer Graphics, v.13 n.4, p.675-685, July 2007 [doi>10.1109/TVCG.2007.1015]
• 29: Afra Zomorodian , Gunnar Carlsson, Computing Persistent Homology, Discrete & Computational Geometry, v.33 n.2, p.249-274, February 2005 [doi>10.1007/s00454-004-1146-y]
• 30: Afra Zomorodian , Gunnar Carlsson, Localized Homology, Proceedings of the IEEE International Conference on Shape Modeling and Applications 2007, p.189-198, June 13-15, 2007 [doi>10.1109/SMI.2007.25]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.4 Graphics Utilities
          Subjects: Graphics editors

Keywords:
feature identification, persistent homology, shape analysis, surface loop, topology, topology repair