research-article

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

Authors:

David Cohen-SteinerAuthors Info & Claims

SIGGRAPH '08: ACM SIGGRAPH 2008 papers

Article No.: 45, Pages 1 - 9

https://doi.org/10.1145/1399504.1360644

Published: 01 August 2008 Publication History

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.

Supplementary Material

MOV File (a45-dey.mov)

Download
20.08 MB

References

[1]

Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. In Proc. SIGGRAPH 2005, 617--625.

Digital 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.

[3]

Biasotti, S., Giorgi, D., Spagnuolo, M., and Falcidieno, B. 2008. Reeb graphs for shape analysis and applications. Theoretical Comput. Sci. 392, 5--22.

Digital Library

[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]

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.

Digital 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.

Digital 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.

[10]

Dey, T. K. 2007. Curve and surface reconstruction: algorithms with mathematical analysis. Cambridge University Press.

Digital Library

[11]

Edelsbrunner, H., Letscher, D., and Zomorodian, A. 2002. Topological persistence and simplification. Discrete Comput. Geom. 28, 511--533.

Digital Library

[12]

El-Sana, J., and Varshney, A. 1997. Controlled simplification of genus for polygonal models. In Proc. IEEE Visualization, 403--412.

Digital 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.

Digital 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.

Digital Library

[15]

Erickson, J., and Whittlesey, K. 2005. Greedy optimal homotopy and homology generators. In Proc. ACM-SIAM Sympos. Discrete Algorithms, 1038--1046.

Digital Library

[16]

Gu, X., Gortler, S., and Hoppe, H. 2002. Geometry images. In Proc. SIGGRAPH 2002, 355--361.

Digital Library

[17]

Guskov, I., and Wood, Z. 2001. Topological noise removal. In Proc. Graphics Interface 2001, 19--26.

Digital Library

[18]

Hatcher, A. 2002. Algebraic Topology. Cambridge University Press.

[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.

Digital 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.

Digital 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.

Digital Library

[22]

Oudot, S., Rineau, L., and Yvinec, M. 2005. Meshing volumes bounded by smooth surfaces. In Proc. 14th Internat. Meshing Roundtable, 203--219.

[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.

Digital 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.

[25]

Sheffer, A., and Hart, J. 2002. Seamster: inconspicuous low-distortion texture seam layout. In Proc. IEEE Visualization, 291--298.

Digital Library

[26]

Wood, Z., Hoppe, H., Desbrun, M., and Schröder, P. 2004. Removing excess topology from isosurfaces. ACM Trans. Graphics 23, 511--533.

Digital Library

[27]

Yin, X., Jin, M., and Gu, X. 2007. Computing shortest cycles using universal covering space. Visual Computer 23, 999--1004.

Digital 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.

Digital Library

[29]

Zomorodian, A., and Carlsson, G. 2005. Computing persistent homology. Discrete Comput. Geom. 33, 249--274.

Digital Library

[30]

Zomorodian, A., and Carlsson, G. 2007. Localized homology. In Proc. Shape Modeling Internat., 189--198.

Digital Library

Cited By

Abdelrahman HTong Y(2025)Computing skeleton-based handle/tunnel loopsComputers & Graphics10.1016/j.cag.2025.104177127(104177)Online publication date: Apr-2025
https://doi.org/10.1016/j.cag.2025.104177
Chen WRen YLei NLuo ZGu X(2024)Texture Space Optimization via Harmonic MapNumerical Geometry, Grid Generation and Scientific Computing10.1007/978-3-031-59652-0_3(41-56)Online publication date: 18-Dec-2024
https://doi.org/10.1007/978-3-031-59652-0_3
Yuan NWang PMeng WChen SXu JXin SHe YWang W(2023)A Variational Framework for Curve Shortening in Various Geometric DomainsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.313502129:4(1951-1963)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TVCG.2021.3135021
Show More Cited By

Index Terms

Computing geometry-aware handle and tunnel loops in 3D models
1. Computing methodologies
  1. Computer graphics
    1. Graphics systems and interfaces
    2. Shape modeling
      1. Parametric curve and surface models
      2. Volumetric models

Recommendations

An efficient computation of handle and tunnel loops via Reeb graphs

A special family of non-trivial loops on a surface called handle and tunnel loops associates closely to geometric features of "handles" and "tunnels" respectively in a 3D model. The identification of these handle and tunnel loops can benefit a broad ...
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 ...
Least squares conformal maps for automatic texture atlas generation

A Texture Atlas is an efficient color representation for 3D Paint Systems. The model to be textured is decomposed into charts homeomorphic to discs, each chart is parameterized, and the unfolded charts are packed in texture space. Existing texture atlas ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SIGGRAPH '08: ACM SIGGRAPH 2008 papers

August 2008

887 pages

ISBN:9781450301121

DOI:10.1145/1399504

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

SIGGRAPH '08

Sponsor:

SIGGRAPH

SIGGRAPH '08: Special Interest Group on Computer Graphics and Interactive Techniques Conference

August 11 - 15, 2008

California, Los Angeles

Acceptance Rates

SIGGRAPH '08 Paper Acceptance Rate 90 of 518 submissions, 17%;

Overall Acceptance Rate 1,822 of 8,601 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
1,025
Total Downloads

Downloads (Last 12 months)7
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Abdelrahman HTong Y(2025)Computing skeleton-based handle/tunnel loopsComputers & Graphics10.1016/j.cag.2025.104177127(104177)Online publication date: Apr-2025
https://doi.org/10.1016/j.cag.2025.104177
Chen WRen YLei NLuo ZGu X(2024)Texture Space Optimization via Harmonic MapNumerical Geometry, Grid Generation and Scientific Computing10.1007/978-3-031-59652-0_3(41-56)Online publication date: 18-Dec-2024
https://doi.org/10.1007/978-3-031-59652-0_3
Yuan NWang PMeng WChen SXu JXin SHe YWang W(2023)A Variational Framework for Curve Shortening in Various Geometric DomainsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.313502129:4(1951-1963)Online publication date: 1-Apr-2023
https://doi.org/10.1109/TVCG.2021.3135021
Rehal ASen D(2023)Generation of Homotopy Classes for Unconstrained 3D Wire Routing from Characteristic LoopsComputer-Aided Design10.1016/j.cad.2023.103607164(103607)Online publication date: Nov-2023
https://doi.org/10.1016/j.cad.2023.103607
Huo WLiu CDu ZJiang XLiu ZGuo X(2022)Topology Optimization on Complex Surfaces Based on the Moving Morphable Component Method and Computational Conformal MappingJournal of Applied Mechanics10.1115/1.405372789:5Online publication date: 4-Mar-2022
https://doi.org/10.1115/1.4053727
Wang FDeng CYuan BChen C(2019)Hardware Acceleration of Persistent Homology ComputationLarge-Scale Annotation of Biomedical Data and Expert Label Synthesis and Hardware Aware Learning for Medical Imaging and Computer Assisted Intervention10.1007/978-3-030-33642-4_9(81-88)Online publication date: 24-Oct-2019
https://doi.org/10.1007/978-3-030-33642-4_9
Roy LKumar PGolbabaei SZhang YZhang E(2018)Interactive Design and Visualization of Branched Covering SpacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2017.274403824:1(843-852)Online publication date: Jan-2018
https://doi.org/10.1109/TVCG.2017.2744038
Dey TFan FWang Y(2013)An efficient computation of handle and tunnel loops via Reeb graphsACM Transactions on Graphics10.1145/2461912.246201732:4(1-10)Online publication date: 21-Jul-2013
https://dl.acm.org/doi/10.1145/2461912.2462017
Jin MDing NYang Y(2013)Computing shortest homotopic cycles on polyhedral surfaces with hyperbolic uniformization metricComputer-Aided Design10.1016/j.cad.2012.07.01545:2(113-123)Online publication date: 1-Feb-2013
https://dl.acm.org/doi/10.1016/j.cad.2012.07.015
Favreau JBarra V(2010)Tiling Surfaces with Cylinders Using n-loopsProceedings of the 2010 Shape Modeling International Conference10.1109/SMI.2010.24(266-270)Online publication date: 21-Jun-2010
https://dl.acm.org/doi/10.1109/SMI.2010.24
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten