research-article

Sparse terrain pyramids

Authors:

Leila De FlorianiAuthors Info & Claims

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

Article No.: 15, Pages 1 - 10

https://doi.org/10.1145/1463434.1463454

Published: 05 November 2008 Publication History

Abstract

Bintrees based on longest edge bisection and hierarchies of diamonds are popular multiresolution techniques on regularly sampled terrain datasets. In this work, we consider Sparse Terrain Pyramids as a compact multiresolution representation for terrain datasets whose samples are a subset of those lying on a regular grid. While previous diamond-based approaches can efficiently represent meshes built on a complete grid of resolution (2^k +1)², this is not suitable when the field values are uniform in large areas or simply non-existent. We explore properties of diamonds to simplify an encoding of the implicit dependency relationship between diamonds. Additionally, we introduce a diamond clustering technique to further reduce the geometric and topological overhead of such representations. We demonstrate the coherence of our clustering technique as well as the compactness of our representation.

References

[1]

J. Blow. Terrain Rendering at High Levels of Detail. Proc. of the 2000 Game Developers Conference, 2000.

[2]

P. Cignoni, F. Ganovelli, E. Gobbetti, F. Marton, F. Ponchio, and R. Scopigno. BDAM- Batched Dynamic Adaptive Meshes for High Performance Terrain Visualization. Computer Graphics Forum, 22(3):505--514, 2003.

[3]

P. Cignoni, F. Ganovelli, E. Gobbetti, F. Marton, F. Ponchio, and R. Scopigno. Planet-Sized Batched Dynamic Adaptive Meshes (P-BDAM). Proceedings of the 14th IEEE Visualization 2003 (VIS'03), 2003.

Digital Library

[4]

L. De Floriani and P. Magillo. Multi-resolution mesh representation: models and data structures. In M. Floater, A. Iske, and E. Quak, editors, Principles of Multi-resolution Geometric Modeling, Lecture Notes in Mathematics, pages 364--418, Berlin, 2002. Springer Verlag.

[5]

L. De Floriani, P. Magillo, and E. Puppo. VARIANT: a system for terrain modeling at variable resolution. Geoinformatica, 4(3):287--315, 2000.

Digital Library

[6]

L. De Floriani, E. Puppo, and P. Magillo. Applications of computational geometry to Geographic Information Systems. In J. R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, chapter 7, pages 333--388. Elsevier Science, 1999.

[7]

M. Duchaineau, M. Wolinsky, D. E. Sigeti, M. C. Miller, C. Aldrich, and M. B. Mineev-Weinstein. ROAMing terrain: real-time optimally adapting meshes. In R. Yagel and H. Hagen, editors, Proceedings IEEE Visualization'97, pages 81--88, Phoenix, AZ, October 1997. IEEE Computer Society.

Digital Library

[8]

W. Evans, D. Kirkpatrick, and G. Townsend. Right-triangulated irregular networks. Algorithmica, 30(2):264--286, 2001.

Digital Library

[9]

T. Gerstner. Multi-resolution visualization and compression of global topographic data. GeoInformatica, 7(1):7--32, 2003.

Digital Library

[10]

T. Gerstner. Top-down view-dependent terrain triangulation using the octagon metric. Technical report, Institut für Angewandte Mathematik, University of Bonn, 2003.

[11]

B. Gregorski, M. Duchaineau, P. Lindstrom, V. Pascucci, and K. Joy. Interactive view-dependent rendering of large isosurfaces. In Proceedings IEEE Visualization 2002, San Diego, CA, October 2002. IEEE Computer Society.

Digital Library

[12]

L. Hwa, M. Duchaineau, and K. Joy. Real-Time Optimal Adaptation for Planetary Geometry and Texture: 4--8 Tile Hierarchies. IEEE Transactions on Visualization and Computer Graphics, pages 355--368, 2005.

Digital Library

[13]

S. Lefebvre and H. Hoppe. Perfect spatial hashing. ACM Transactions on Graphics (TOG), 25(3):579--588, 2006.

Digital Library

[14]

P. Lindstrom, D. Koller, W. Ribarsky, L. F. Hodges, N. Faust, and G. A. Turner. Real-time continuous level of detail rendering of height fields. In Proceedings SIGGRAPH'96, pages 109--118, August 1996.

Digital Library

[15]

P. Lindstrom and V. Pascucci. Terrain simplification simplified: a general framework for view-dependent out-of-core visualization. IEEE Transactions on Visualization and Computer Graphics, 8(3):239--254, 2002.

Digital Library

[16]

D. Luebke, M. Reddy, J. Cohen, A. Varshney, B. Watson, and R. Huebner. Level of Detail for 3D Graphics. Morgan-Kaufmann, San Francisco, 2002.

Digital Library

[17]

J. M. Maubach. Local bisection refinement for n-simplicial grids generated by reflection. SIAM Journal on Scientific Computing, 16(1):210--227, January 1995.

Digital Library

[18]

R. Pajarola. Large scale terrain visualization using the restricted quadtree triangulation. In D. Ebert, H. Hagen, and H. Rushmeier, editors, Proceedings IEEE Visualization'98, pages 19--26, Research Triangle Park, NC, October 1998. IEEE Computer Society.

Digital Library

[19]

R. Pajarola and E. Gobbetti. Survey of semi-regular multiresolution models for interactive terrain rendering. The Visual Computer, 23(8):583--605, 2007.

Digital Library

[20]

H. Samet. Foundations of Multidimensional and Metric Data Structures. Elsevier, 2006.

Digital Library

[21]

R. Sivan and H. Samet. Algorithms for constructing quadtree surface maps. Proc. 5th Int. Symposium on Spatial Data Handling, pages 361--370, 1992.

[22]

U.S. Geological Survey. Global 30 arc second elevation data. http://edc.usgs.gov/products/elevation/gtopo30/gtopo30.html.

Cited By

Yalçin MWeiss KDe Floriani L(2011)GPU algorithms for diamond-based multiresolution terrain processingProceedings of the 11th Eurographics conference on Parallel Graphics and Visualization10.5555/2386230.2386247(121-130)Online publication date: 10-Apr-2011
https://dl.acm.org/doi/10.5555/2386230.2386247
Vitali MDe Floriani LMagillo P(2011)Computing morse decompositions for triangulated terrainsProceedings of the 16th international conference on Image analysis and processing: Part I10.5555/2042620.2042689(565-574)Online publication date: 14-Sep-2011
https://dl.acm.org/doi/10.5555/2042620.2042689
Weiss KDe Floriani L(2009)SupercubesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2009.18615:6(1603-1610)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1109/TVCG.2009.186

Index Terms

Sparse terrain pyramids
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision representations
        Hierarchical representations
  2. Computer graphics
    1. Graphics systems and interfaces
      1. Graphics file formats
    2. Shape modeling

Recommendations

Isodiamond Hierarchies: An Efficient Multiresolution Representation for Isosurfaces and Interval Volumes

Efficient multiresolution representations for isosurfaces and interval volumes are becoming increasingly important as the gap between volume data sizes and processing speed continues to widen. Our multiresolution scalar field model is a hierarchy of ...
Supercubes: A High-Level Primitive for Diamond Hierarchies

Volumetric datasets are often modeled using a multiresolution approach based on a nested decomposition of the domain into a polyhedral mesh.Nested tetrahedral meshes generated through the longest edge bisection rule are commonly used to decompose ...
Lepp-bisection algorithms, applications and mathematical properties

Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods for PDEs. In ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GIS '08: Proceedings of the 16th ACM SIGSPATIAL international conference on Advances in geographic information systems

November 2008

559 pages

ISBN:9781605583235

DOI:10.1145/1463434

Program Chairs:
Walid G. Aref
Purdue University
,
Mohamed F. Mokbel
University of Minnesota
,
Markus Schneider
University of Florida

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

ESRI
Google Inc.
Oak Ridge National Laboratory
Microsoft: Microsoft
SIGSPATIAL: ACM Special Interest Group on Spatial Information

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

GIS '08

Sponsor:

Microsoft
SIGSPATIAL

GIS '08: 16th International Symposium on Advances in Geographic Information Systems

November 5 - 7, 2008

California, Irvine

Acceptance Rates

Overall Acceptance Rate 257 of 1,238 submissions, 21%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
291
Total Downloads

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

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Yalçin MWeiss KDe Floriani L(2011)GPU algorithms for diamond-based multiresolution terrain processingProceedings of the 11th Eurographics conference on Parallel Graphics and Visualization10.5555/2386230.2386247(121-130)Online publication date: 10-Apr-2011
https://dl.acm.org/doi/10.5555/2386230.2386247
Vitali MDe Floriani LMagillo P(2011)Computing morse decompositions for triangulated terrainsProceedings of the 16th international conference on Image analysis and processing: Part I10.5555/2042620.2042689(565-574)Online publication date: 14-Sep-2011
https://dl.acm.org/doi/10.5555/2042620.2042689
Weiss KDe Floriani L(2009)SupercubesIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2009.18615:6(1603-1610)Online publication date: 1-Nov-2009
https://dl.acm.org/doi/10.1109/TVCG.2009.186

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