Skip to main content
SpringerLink
Log in

Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering

  • Chapter
  • First Online:
Advances in 3D Geo-Information Sciences

Part of the book series: Lecture Notes in Geoinformation and Cartography ((LNGC))

Abstract

A technique to create a Delaunay triangulation for terrain visualization on a virtual globe is presented. This method can be used to process large scale elevation datasets with billions of points by using little RAM during data processing. All data is being transformed to a global spatial reference system. If grid based elevation data is used as input, a reduced TIN can be calculated. Furthermore, a level of detail approach for large scale out-of-core spherical terrain rendering for virtual globes is presented using the previously created TIN.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
USD 169.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  • Devillers, O., Devillers, Pion, S., Pion, S., Prisme, P.: Efficient exact geometric predicates for Delaunay triangulations. In: Proceedings of the 5th Workshop Algorithm Engineering and Experiments. pp. 37–44. Baltimore (2003)

    Google Scholar 

  • Dick, C., Schneider, J., Westermann, R.: Efficient geometry compression for GPU- based decoding in realtime terrain rendering. Comp. Graph. Forum 28(1), 67–83 (2009)

    Article  Google Scholar 

  • Fowler, R.E., Samberg, A., Flood, M., Greaves, T.J.: Modeling mobile terrestrial LiDAR to vector based models. In: Maune, D. F. (ed.) Digital Elevation Model Technologies and Applications: The DEM Users Manual, chap. Topographic and Terrestrial Lidar. pp. 199–252. American Society of Photogrammetry and Remote Sensing, Bethesda (1997)

    Google Scholar 

  • Gerstner, T.: Multiresolution visualization and compression of global topographic data. Tech. rep., GeoInformatica (1999)

    Google Scholar 

  • Google: Earth, http://earth.google.com

  • Google: Google Earth API Developer’s Guide, http://code.google.com/apis/earth/documentation/

  • Guibas, L.J., Stolfi, J.: Primitives for the manipulation of general subdivisions and the computation of voronoi diagrams. In: STOC’ 83: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing. pp. 221–234. ACM, New York (1983)

    Google Scholar 

  • Guibas, L.J., Stolfi, J.: Primitives for the manipulation of general subdivisions and the computation of Voronoi diagrams. ACM Trans. Graph. 4, 74–123 (1985)

    Article  Google Scholar 

  • Heller, M.: Triangulation algorithms for adaptive terrain modeling. In: Proceedings of the 4th International Symposium on Spatial Data Handling. pp. 163–174. Zurich, Switzerland (1990)

    Google Scholar 

  • Hjelle, O., Daehlen, M.: Triangulations and Applications (Mathematics and Visualization). Springer-Verlag New York, Secaucus, NJ (2006)

    Google Scholar 

  • Hoppe, H.: Smooth view-dependent level-of-detail control and its application to terrain rendering. In: VIS ’98: Proceedings of the Conference on Visualization ’98. pp. 35–42. IEEE Computer Society Press, Los Alamitos (1998)

    Google Scholar 

  • Isenburg, M., Liu, Y., Shewchuk, J., Snoeyink, J.: Streaming computation of Delaunay triangulations. ACM Trans. Graph. 25(3), 1049–1056 (2006)

    Article  Google Scholar 

  • Isenburg, M., Shewchuk, J.: Visualizing LIDAR in Google Earth. In: Proceedings of the 17th International Conference on Geoinformatics. Fairfax (2009)

    Google Scholar 

  • Lee, J.: A drop heuristic conversion method for extracting irregular networks for digital elevation models. In: Proceedings of the GIS/LIS ’89. pp. 30–39. Orlando (1989)

    Google Scholar 

  • Lindstrom, P., Cohen, J.D.: On-the-fly decompression and rendering of multiresolution terrain. In: I3D ’10: Proceedings of the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games. pp. 65–73. ACM, New York (2010)

    Google Scholar 

  • Livny, Y., Kogan, Z., El-Sana, J.: Seamless patches for GPU-based terrain rendering. Vis. Comput. 25(3), 197–208 (2009)

    Article  Google Scholar 

  • Microsoft: Bing Maps 3d, http://www.bing.com/maps

  • Microsoft: Bing Maps Tile System, http://msdn.microsoft.com/en-us/library/bb259689.aspx

  • Morton, G.: A computer oriented geodetic data base and a new technique in file sequencing. Tech. Rep. IBM Ltd., Ottawa, Ontario, Canada (1966)

    Google Scholar 

  • Mostafavi, M.A., Gold, C., Dakowicz, M.: Delete and insert operations in Voronoi/Delaunay methods and applications. Comput. Geosci. 29(4), 523–530 (2003)

    Article  Google Scholar 

  • Nebiker, S., Christen, M., Eugster, H., Flückiger, K., Stierli, C.: Integrating mobile geo sensors into collaborative virtual globes – design and implementation issues. Paper presented at the Mobile Mapping Technologies Symposium MMT 2007, Padua (2007)

    Google Scholar 

  • Nebiker, S., Bleisch, S., Christen, M.: Rich point clouds in virtual globes a new paradigm in city modeling? Computers, Environment and Urban Systems (June 2010), http://dx.doi.org/10.1016/j.compenvurbsys.2010.05.002

  • Open Geospatial Consortium, Inc: OpenGIS® city geography markup language (CityGML) – encoding standard (ogc 08-007r1). (p. 218): Open Geospatial Consortium Inc. (2010)

    Google Scholar 

  • Pajarola, R., Gobbetti, E.: Survey of semi-regular multiresolution models for interactive terrain rendering. Vis. Comput. 23(8), 583–605 (2007)

    Article  Google Scholar 

  • Pajarola, R., Antonijuan, M., Lario, R.: Quadtin: quadtree based triangulated irregular networks. In: VIS ’02: Proceedings of the Conference on Visualization ’02. pp. 395–402. IEEE Computer Society, Washington, DC (2002)

    Google Scholar 

  • Shan, J., Toth, C.: Topographic laser ranging and scanning. CRC Press, Boca Raton (2009)

    Google Scholar 

  • Shewchuk, J.R.: Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete Comput. Geometry 18, 305–363 (1996)

    Article  Google Scholar 

  • Snyder, J.P.: Map Projections: A Working Manual. U.S. Geological Survey Professional Paper 1395, U.S. Geological Survey, http://pubs.er.usgs.gov/usgspubs/pp/pp1395 (1987)

  • Szalay, A.S., Gray, J., Fekete, G., Kunszt, P.Z., Kukol, P., Thakar, A.: Indexing the sphere with the hierarchical triangular mesh. CoRR abs/cs/0701164 (2007)

    Google Scholar 

  • Weiler, K.: Edge-based data structures for solid modeling in curved-surface environments. IEEE Comput. Graph. Appl. 5(1), 21–40 (1985)

    Article  Google Scholar 

  • Zhou, Q., Lees, B., Tang, G.A.: Lecture Notes in Geoinformation and Cartography, chap. A Seamless and Adaptive LOD Model of the Global Terrain Based on the QTM. pp. 85–103. Springer Berlin Heidelberg, New York (2008)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Geomatics Engineering, University of Applied Sciences Northwestern Switzerland, Gründenstr. 40, 4132, Muttenz, Switzerland

    M. Christen & S. Nebiker

Authors
  1. M. Christen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. S. Nebiker
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to M. Christen .

Editor information

Editors and Affiliations

  1. FG Methodik der Geoinformationstechnik, Sekr. H12, TU Berlin, Straße des 17. Juni 135, Berlin, 10623, Germany

    Thomas H. Kolbe

  2. FG Methodik der Geoinformationstechnik, Sekr. H12, TU Berlin, Straße des 17. Juni 135, Berlin, 10623, Germany

    Gerhard König

  3. FG Methodik der Geoinformationstechnik, Sekr. H12, TU Berlin, Straße des 17. Juni 135, Berlin, 10623, Germany

    Claus Nagel

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Christen, M., Nebiker, S. (2011). Large Scale Constraint Delaunay Triangulation for Virtual Globe Rendering. In: Kolbe, T., König, G., Nagel, C. (eds) Advances in 3D Geo-Information Sciences. Lecture Notes in Geoinformation and Cartography(). Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-12670-3_4

Download citation

Publish with us

Policies and ethics

Search

Navigation