“Computing geometry-aware handle and tunnel loops in 3D models” by Dey, Li, Sun and Cohen-Steiner

  • ©Tamal K. Dey, Kuiyu Li, Jian Sun, and David Cohen-Steiner




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



    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.


    1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. In Proc. SIGGRAPH 2005, 617–625. Google ScholarDigital Library
    2. Ben-Chen, M., Gotsman, C., and Bunin, G. 2008. Conformal flattening by curvature prescription and metric scaling. Computer Graphics Forum (Proc. Eurographics) 27.Google Scholar
    3. Biasotti, S., Giorgi, D., Spagnuolo, M., and Falcidieno, B. 2008. Reeb graphs for shape analysis and applications. Theoretical Comput. Sci. 392, 5–22. Google ScholarDigital Library
    4. Bischoff, S., and Kobbelt, L. 2005. Structure preserving CAD model repair. Comput. Graphics Forum 24, 527–536.Google ScholarCross Ref
    5. Chen, C., and Freedman, D. 2008. Quantifying homology classes. In Sympos. Theoretical Aspects Comput. Sci., 169–180.Google Scholar
    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.Google Scholar
    7. Cohen-Steiner, D., Edelsbrunner, H., and Morozov, D. 2006. Vines and vineyards by updating persistence in linear time. In Proc. 22nd Ann. Sympos. Comput. Geom., 119–126. Google ScholarDigital Library
    8. Dey, T. K., and Sun, J. 2006. Defining and computing curve-skeletons with medial geodesic function. In Proc. Sympos. Geom. Processing, 143–152. Google ScholarDigital Library
    9. Dey, T. K., Li, K., and Sun, J. 2007. On computing handle and tunnel loops. In IEEE Proc. Internat. Conf. Cyberworlds, 357–366. Google ScholarCross Ref
    10. Dey, T. K. 2007. Curve and surface reconstruction: algorithms with mathematical analysis. Cambridge University Press. Google ScholarDigital Library
    11. Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Discrete Comput. Geom. 28, 511–533.Google ScholarDigital Library
    12. El-Sana, J., and Varshney, A. 1997. Controlled simplification of genus for polygonal models. In Proc. IEEE Visualization, 403–412. Google ScholarDigital Library
    13. Éric Colin de Verdière, and Erickson, J. 2006. Tightening non-simple paths and cycles on surfaces. In Proc. ACM-SIAM Sympos. Discrete Algorithms, 192–201. Google ScholarDigital Library
    14. Éric Colin de Verdière, and Lazarus, F. 2005. Optimal system of loops on an orientable surface. Discrete Comput. Geom. 33, 507–534.Google ScholarDigital Library
    15. Erickson, J., and Whittlesey, K. 2005. Greedy optimal homotopy and homology generators. In Proc. ACM-SIAM Sympos. Discrete Algorithms, 1038–1046. Google ScholarDigital Library
    16. Gu, X., Gortler, S., and Hoppe, H. 2002. Geometry images. In Proc. SIGGRAPH 2002, 355–361. Google ScholarDigital Library
    17. Guskov, I., and Wood, Z. 2001. Topological noise removal. In Proc. Graphics Interface 2001, 19–26. Google ScholarDigital Library
    18. Hatcher, A. 2002. Algebraic Topology. Cambridge University Press.Google Scholar
    19. 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 Proc. SIGGRAPH 2000, 131–144. Google ScholarDigital Library
    20. Ni, X., Garland, M., and Hart, J. C. 2004. Fair morse functions for extracting the topological structure of a surface mesh. In Proc. SIGGRAPH 2004, 613–622. Google ScholarDigital Library
    21. Nooruddin, F. S., and Turk, G. 2003. Simplification and repair of polygonal models using volumetric techniques. IEEE Trans. Vis. Comput. Graph. 9, 191–205. Google ScholarDigital Library
    22. Oudot, S., Rineau, L., and Yvinec, M. 2005. Meshing volumes bounded by smooth surfaces. In Proc. 14th Internat. Meshing Roundtable, 203–219.Google Scholar
    23. Pascucci, V., Scorzelli, G., Bremer, P.-T., and Mascarenhas, A. 2007. Robust on-line computation of Reeb graphs: simplicity and speed. ACM Trans. Graphics. 58, 1–9. Google ScholarDigital Library
    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.Google ScholarCross Ref
    25. Sheffer, A., and Hart, J. 2002. Seamster: inconspicuous low-distortion texture seam layout. In Proc. IEEE Visualization, 291–298. Google ScholarDigital Library
    26. Wood, Z., Hoppe, H., Desbrun, M., and Schröder, P. 2004. Removing excess topology from isosurfaces. ACM Trans. Graphics 23, 511–533. Google ScholarDigital Library
    27. Yin, X., Jin, M., and Gu, X. 2007. Computing shortest cycles using universal covering space. Visual Computer 23, 999–1004. Google ScholarDigital Library
    28. Zhou, Q.-Y., Ju, T., and Hu, S.-M. 2007. Topology repair of solid models using skeletons. IEEE Trans. Vis. Comput. Graph. 13, 675–685. Google ScholarDigital Library
    29. Zomorodian, A., and Carlsson, G. 2005. Computing persistent homology. Discrete Comput. Geom. 33, 249–274. Google ScholarDigital Library
    30. Zomorodian, A., and Carlsson, G. 2007. Localized homology. In Proc. Shape Modeling Internat., 189–198. Google ScholarDigital Library

ACM Digital Library Publication:

Overview Page: