More Web Proxy on the site http://driver.im/

Article

A multi-resolution topological representation for non-manifold meshes

Authors:

Leila De Floriani,

Davide SobreroAuthors Info & Claims

SMA '02: Proceedings of the seventh ACM symposium on Solid modeling and applications

Pages 159 - 170

https://doi.org/10.1145/566282.566307

Published: 17 June 2002 Publication History

Abstract

We address the problem of representing and processing non-regular, non-manifold two-dimensional simplicial meshes, that we call triangle-segment meshes, at different levels of detail. Such meshes are used to describe spatial objects consisting of parts of mixed dimensions, and with a non-manifold topology. First, we describe a multi-resolution model for non-regular, non-manifold meshes, that we call a Non-manifold Multi-Tessellation (NMT). We consider the selective refinement query, which is at the heart of several analysis operations on multiresolution meshes. Next, we focus on a specific instance of a NMT, generated by a simplification process based on vertex-pair contraction, and we describe a compact data structure for encoding it. We also propose a new data structure for triangle-segment meshes, capable of representing both connectivity and adjacency information with a small memory overhead, that we use to describe the mesh extracted with selective refinement. To this aim, we define algorithms to efficiently perform mesh updates on such a data structure.

References

[1]

S. Campagna, L. Kobbelt, and H.-P. Seidel. Directed edges - a scalable representation for triangle meshes. Journal of Graphics Tools, 4(3):1--12, 1999

Digital Library

[2]

W. Charlesworth and D. Anderson. Applications of non-manifold topology. In Proceesings Computers in Engineering Conference and Engineering Database Symposium, pages 103--112. ASME, 1995

[3]

P. Cignoni, C. Montani, and R. Scopigno. A comparison of mesh simplification algorithms. Computers and Graphics, 22(1):37--54, 1998

[4]

L. De Floriani and P. Magillo. Multiresolution mesh representation: Models and data structures. In PRIMUS 2001 -- Course Notes, Munich, Germany, August 2001

[5]

L. De Floriani, P. Magillo, F. Morando, and E. Puppo. Dynamic view-dependent multiresolution on a client-server architecture. CAD Journal, 32(13):805--823, 2000

[6]

L. De Floriani, M. Mesmoudi, F. Morando, and E. Puppo. Non-manifold decomposition in arbitrary dimensions. In Discrete Geometry for Computer Imagery. April 2002. To appear

Digital Library

[7]

H. Desaulnier and N. Stewart. An extension of manifold boundary representation to r-sets. ACM Transactions on Graphics, 11(1):40--60, 1992

Digital Library

[8]

M. Duchaineau, M. Wolinsky, D. Sigeti, M. Miller, C. Aldrich, and M. Mineed-Weinstein. ROAMing terrain: Real-time optimally adapting meshes. In Proceedings IEEE Visualization'97, pages 81--88, 1997

Digital Library

[9]

H. Edelsbrunner. Algorithms in Combinatorial Geometry. Springer-Verlag, Berlin, 1987

Digital Library

[10]

J. El-Sana and A. Varshney. Generalized view-dependent simplification. Computer Graphics Forum, 18(3):C83--C94, 1999

[11]

W. Evans, D. Kirkpatrick, and G. Townsend. Right triangular irregular networks. Algorithmica, 30(2):264--286, 2001. Special Issue on Algorithms for Geographical Information

Digital Library

[12]

B. Falcidieno and O. Ratto. Two-manifold cell-decomposition of r-sets. Computer Graphics Forum (EUROGRAPHICS '92 Proceedings), 11(3):391--404, Sept. 1992

[13]

M. Garland. Multiresolution modeling: Survey & future opportunities. In Eurographics '99 -- State of the Art Reports, pages 111--131, 1999

[14]

M. Garland and P. Heckbert. Surface simplification using quadric error metrics. In Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH '97), ACM Press, pages 209--216, 1997

Digital Library

[15]

A. Gueziec, F. Bossen, G. Taubin, and C. Silva. Efficient compression of non-manifold polygonal meshes. Computational Geometry: Theory and Applications, 14:137--166, 1999

Digital Library

[16]

A. Gueziec, G. Taubin, F. Lazarus, and W. Horn. Simplicial maps for progressive transmission of polygonal surfaces. In Proceedings ACM VRML98, pages 25--31, 1998

Digital Library

[17]

E. Gursoz, Y. Choi, and F. Prinz. Vertex-based representation of non-manifold boundaries. In Geometric Modeling for Product Engineering, pages 107--130, North Holland, 1990. Elsevier Science Publishers

[18]

T. He, L. Hong, A. Varshney, and S. Wang. Controlled topology simplification. IEEE Transactions on Visualization and Computer Graphics, 2(2):171--183, 1996

Digital Library

[19]

H. Hoppe. View-dependent refinement of progressive meshes. In ACM Computer Graphics Proceedings, Annual Conference Series, (SIGGRAPH '97), pages 189--198, 1997

Digital Library

[20]

(MATH) L. Kobbelt. $sqrt3$ subdivision. In Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH 2000), ACM Press, 2000

Digital Library

[21]

S. Lee and K. Lee. Partial entity structure: a fast and compact non-manifold boundary representation based on partial topological entities. In Proceedings Sixth ACM Symposium on Solid Modeling and Applications, Ann Arbor, Michigan, June 4--8 2001

Digital Library

[22]

P. Lindstrom, D. Koller, W. Ribarsky, L. Hodges, N. Faust, and G. Turner. Real-time, continuous level of detail rendering of height fields. In ACM Computer Graphics (SIGGRAPH '96 Proceedings), pages 109--118, New Orleans, LA, USA, Aug. 6-8 1996. ACM Press

Digital Library

[23]

D. Luebke. A developer's survey of polygonal simlification algorithms. IEEE Computer Graphics & Applications, 21(3):24--35, May-June 2001

Digital Library

[24]

D. Luebke and C. Erikson. View-dependent simplification of arbitrary polygonal environments. In ACM Computer Graphics Proceedings, Annual Conference Series, (SIGGRAPH '97), pages 199--207, 1997

Digital Library

[25]

P. Magillo. The MT (Multi-Tesselation) package. Dept. of Computer and Informations Sciences, University of Genova, Italy, http://www.disi.unige.it/person/MagilloP/MT/index.html, January 2000

[26]

S. McMains and C. S. J. Hellerstein. Out-of-core build of a topological data structure from polygon soup. In Proccedings Sixth ACM Symposium on Solid Modeling and Applications, pages 171--182, Ann Arbor, Michigan (USA), June 6-8 2001

Digital Library

[27]

P.Lindstrom. Out-of-core simplification of large polygonal models. In ACM Computer Graphics (SIGGRAPH 2000 Proceedings), pages 259--270, New Orleans, LA, USA, July 2000. ACM Press

Digital Library

[28]

J. Popovic and H. Hoppe. Progressive simplicial complexes. In ACM Computer Graphics Proceedings, Annual Conference Series, (SIGGRAPH '97), pages 217--224, 1997

Digital Library

[29]

E. Puppo. Variable resolution terrain surfaces. In Proceedings Eight Canadian Conference on Computational Geometry, pages 202--210, Ottawa, Canada, August 12--15 1996. Extended version appeared with title Variable Resolution Triangulations, Computational Geometry, 1998, 11(3-4):219--238

Digital Library

[30]

J. Rossignac and P. Borrel. Multi-resolution 3D approximation for rendering complex scenes. In B. Falcidieno and T. Kunii, editors, Geometric Modeling in Computer Graphics, pages 455--465. Springer Verlag, October 17--18 1993

[31]

J. Rossignac and M. O'Connor. SGC: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In J. Turner, M. Wozny, and K. Preiss, editors, Geometric Modeling for Product Engineering, pages 145--180, North Holland, Amsterdam, 1990. Elsevier Science Publishers

[32]

R. Sriram, A. Wong, and L. He. GNOMES: an object-oriented non-manifold geometric engine. Computer Aided Design, 27(11):853--868, 1995

[33]

L. Velho, L. H. de~Figueredo, and J. Gomes. A unified approach for hierarchical adaptive tesselation of surfaces. ACM Transactions on Graphics, 4(18):329--360, 1999

Digital Library

[34]

K. Weiler. The radial edge data structure: A topological representation for non-manifold geometric boundary modeling. In J. E. M.J. Wozny, H.W. McLaughlin, editor, Geometric Modeling for CAD Applications, pages 3--36, North-Holland, 1988. Elsevier Science

[35]

J. Xia, J. El-Sana, and A. Varshney. Adaptive real-time level-of-detail-based rendering for polygonal models. IEEE Transactions on Visualization and Computer Graphics, 3(2):171--183, 1997

Digital Library

[36]

Y. Yamaguchi and F. Kimura. Nonmanifold topology based on coupling entities. IEEE Computer Graphics and Applications, 15(1):42--50, January 1995

Digital Library

[37]

D. Zorin, P. Schroder, and W. Sweldens. Interactive multiresolution mesh editing. In Computer Graphics Proceedings, Annual Conference Series (SIGGRAPH '97), ACM Press, pages 259--268, 1997

Digital Library

Cited By

Khan FRoy LZhang EQu BHung SYeh HLaramee RZhang Y(2019)Multi-Scale Topological Analysis of Asymmetric Tensor Fields on SurfacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.2934314(1-1)Online publication date: 2019
https://doi.org/10.1109/TVCG.2019.2934314
Rodrigues RMorgado JSilva FGomes A(2007)A ghost cell-based data structure for multiresolution meshesProceedings of the 2007 international conference on Computational science and Its applications - Volume Part II10.5555/1802954.1803022(666-679)Online publication date: 26-Aug-2007
https://dl.acm.org/doi/10.5555/1802954.1803022
Rodrigues RMorgado JSilva FGomes A(2007)A Ghost Cell-Based Data Structure for Multiresolution MeshesComputational Science and Its Applications – ICCSA 200710.1007/978-3-540-74477-1_61(666-679)Online publication date: 2007
https://doi.org/10.1007/978-3-540-74477-1_61
Show More Cited By

Index Terms

A multi-resolution topological representation for non-manifold meshes
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

n-Dimensional multiresolution representation of subdivision meshes with arbitrary topology

We present a new model for the representation of n-dimensional multiresolution meshes. It provides a robust topological representation of arbitrary meshes that are combined in closely interlinked levels of resolution. The proposed combinatorial model is ...
Normal meshes
SIGGRAPH '00: Proceedings of the 27th annual conference on Computer graphics and interactive techniques

Normal meshes are new fundamental surface descriptions inspired by differential geometry. A normal mesh is a multiresolution mesh where each level can be written as a normal offset from a coarser version. Hence the mesh can be stored with a single float ...
New quadric metric for simplifiying meshes with appearance attributes
VIS '99: Proceedings of the conference on Visualization '99: celebrating ten years

Complex triangle meshes arise naturally in many areas of computer graphics and visualization. Previous work has shown that a quadric error metric allows fast and accurate geometric simplification of meshes. This quadric approach was recently generalized ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SMA '02: Proceedings of the seventh ACM symposium on Solid modeling and applications

June 2002

424 pages

ISBN:1581135068

DOI:10.1145/566282

Conference Chairs:
Hans-Peter Seidel
Max-Planck-Institut für Informatik, Saarbrücken, Germany
,
Vadim Shapiro
University of Wisconsin, Madison, U.S.A.
,
Program Chairs:
Kunwoo Lee
Seoul National University, Seoul, Korea
,
Nick Patrikalakis
Massachsetts Institute of Technology, Cambridge, U.S.A.

Copyright © 2002 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: 17 June 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

SM02

Sponsor:

SIGGRAPH

SM02: ACM Symposium on Solid Modeling and Applications 2002

June 17 - 21, 2002

Saarbrücken, Germany

Acceptance Rates

SMA '02 Paper Acceptance Rate 43 of 93 submissions, 46%;

Overall Acceptance Rate 86 of 173 submissions, 50%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
583
Total Downloads

Downloads (Last 12 months)15
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khan FRoy LZhang EQu BHung SYeh HLaramee RZhang Y(2019)Multi-Scale Topological Analysis of Asymmetric Tensor Fields on SurfacesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2019.2934314(1-1)Online publication date: 2019
https://doi.org/10.1109/TVCG.2019.2934314
Rodrigues RMorgado JSilva FGomes A(2007)A ghost cell-based data structure for multiresolution meshesProceedings of the 2007 international conference on Computational science and Its applications - Volume Part II10.5555/1802954.1803022(666-679)Online publication date: 26-Aug-2007
https://dl.acm.org/doi/10.5555/1802954.1803022
Rodrigues RMorgado JSilva FGomes A(2007)A Ghost Cell-Based Data Structure for Multiresolution MeshesComputational Science and Its Applications – ICCSA 200710.1007/978-3-540-74477-1_61(666-679)Online publication date: 2007
https://doi.org/10.1007/978-3-540-74477-1_61
Celes WPaulino GEspinha R(2005)Efficient Handling of Implicit Entities in Reduced Mesh RepresentationsJournal of Computing and Information Science in Engineering10.1115/1.20528305:4(348)Online publication date: 2005
https://doi.org/10.1115/1.2052830
Guthe MBalázs ÁKlein R(2004)Interactive high quality trimmed NURBS visualization using appearance preserving tessellationProceedings of the Sixth Joint Eurographics - IEEE TCVG conference on Visualization10.5555/2384225.2384257(211-220)Online publication date: 19-May-2004
https://dl.acm.org/doi/10.5555/2384225.2384257
Chang YQin HElber GPatrikalakis NBrunet P(2004)A framework for multi-dimensional adaptive subdivision objectsProceedings of the ninth ACM symposium on Solid modeling and applications10.5555/1217875.1217894(123-134)Online publication date: 9-Jun-2004
https://dl.acm.org/doi/10.5555/1217875.1217894
De Floriani LHui AKobbelt LSchröder PHoppe H(2003)A scalable data structure for three-dimensional non-manifold objectsProceedings of the 2003 Eurographics/ACM SIGGRAPH symposium on Geometry processing10.5555/882370.882380(72-82)Online publication date: 23-Jun-2003
https://dl.acm.org/doi/10.5555/882370.882380
De Floriani LMesmoudi MMorando FPuppo E(2003)Decomposing non-manifold objects in arbitrary dimensionsGraphical Models10.1016/S1524-0703(03)00006-765:1-3(2-22)Online publication date: 1-Jan-2003
https://dl.acm.org/doi/10.1016/S1524-0703%2803%2900006-7
De Floriani LMorando FPuppo E(2003)A Representation for Abstract Simplicial Complexes: An Analysis and a ComparisonDiscrete Geometry for Computer Imagery10.1007/978-3-540-39966-7_43(454-464)Online publication date: 2003
https://doi.org/10.1007/978-3-540-39966-7_43
Guthe MMeseth JKlein R(2002)Fast and memory efficient view-dependent trimmed NURBS rendering10th Pacific Conference on Computer Graphics and Applications, 2002. Proceedings.10.1109/PCCGA.2002.1167860(204-213)Online publication date: 2002
https://doi.org/10.1109/PCCGA.2002.1167860

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.

Media

Figures

Other

Tables

View Table of Contents