[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

A novel terrain rendering algorithm based on quasi Delaunay triangulation

  • Original Article
  • Published:
The Visual Computer Aims and scope Submit manuscript

Abstract

Terrain rendering has long been an interesting research topic, and Delaunay triangulation has been one of the methods frequently employed. The problem of smooth morphing between successive Delaunay meshes in a dynamic setting does not have a satisfactory solution however. In this paper, we address this issue by temporarily relieving the mesh from the strict constraints of Delaunay triangulation (DT). The proposed algorithm uses an off-line process to compute a relative importance for each sampling point in a Digital Elevation Model (DEM). It then constructs a mesh model in real-time from a set of points selected according to their viewpoint distances and relative importances. The mesh model is initialized to be a genuine DT. As the viewpoint moves, some points are added, and some are removed. We use simple methods for point insertion and removal that allow smooth morphing between successive frames. While the simple methods do not ensure Delaunay properties, we eliminate the slivery triangles gradually by collecting and flipping illegal edges incident to them. Point insertions, removals, edge flips, and their animations are organized by queueing and carried out over time. In this way, we amortize the burst computations to successive frames, so that a balanced workload and a high frame rate are achieved. The proposed algorithm produces a concise and well-composed mesh adaptive to both viewpoint and the terrain’s local geometry, and, most importantly, it supports smooth morphing.

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

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

References

  1. Apu, R., Gavrilova, M.: Gtvis: fast and efficient rendering system for real-time terrain visualization. In: Computational Science and Its Applications, pp. 592–602 (2004)

  2. Bhattacharjee, S., Patidar, S., Narayanan, P.J.: Real-time rendering and manipulation of large terrains. In: Sixth Indian Conference on Computer Vision, Graphics & Image Processing, pp. 551–559 (2008)

  3. CGAL: Computational geometry algorithms library. http://www.cgal.org (2010)

  4. Cignoni, P., Ganovelli, F., Gobbetti, E., Marton, F., Ponchio, F., Scopigno, R.: BDAM-batched dynamic adaptive meshes for high performance terrain visualization. Comput. Graph. Forum 22(3), 505–514 (2003)

    Article  Google Scholar 

  5. Cignoni, P., Ganovelli, F., Gobbetti, E., Marton, F., Ponchio, F., Scopigno, R.: Planet-sized batched dynamic adaptive meshes (P-BDAM). In: Proceedings of the 14th IEEE Visualization 2003 (VIS’03), p. 20 (2003)

  6. Cohen-Or, D., Levanoni, Y.: Temporal continuity of levels of detail in Delaunay triangulated terrain. In: IEEE Visualization, pp. 37–42. IEEE Computer Society Press, Los Alamitos (1996)

    Google Scholar 

  7. De Berg, M., Dobrindt, K.: On levels of detail in terrains. Graph. Models Image Process. 60(1), 1–12 (1998)

    Article  Google Scholar 

  8. De Berg, M., Cheong, O., Van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications. Springer, New York (2008)

    MATH  Google Scholar 

  9. De Castro, M., Tournois, J., Alliez, P., Devillers, O.: Filtering relocations on a Delaunay triangulation. Comput. Graph. Forum 28(5) (2009)

  10. Deb, S., Narayanan, P., Bhattacharjee, S.: Streaming terrain rendering. In: ACM SIGGRAPH 2006 Sketches, p. 181. ACM Press, New York (2006)

    Chapter  Google Scholar 

  11. Debard, J., Balp, R., Chaine, R.: Dynamic Delaunay tetrahedralisation of a deforming surface. Vis. Comput. 23(12), 975–986 (2007)

    Article  Google Scholar 

  12. Devillers, O., De Castro, M., et al.: State of the art: updating Delaunay triangulations for moving points. Tech. Rep. 00325816, INRIA (2008)

  13. Duchaineau, M., Wolinsky, M., Sigeti, D., Miller, M., Aldrich, C., Mineev-Weinstein, M.: Roaming terrain: real-time optimally adapting meshes. In: IEEE Visualization, pp. 81–88. IEEE Computer Society Press, Los Alamitos (1997)

    Google Scholar 

  14. Dyer, R., Zhang, H., Möller, T.: Delaunay mesh construction. In: Proceedings of the Fifth Eurographics Symposium on Geometry Processing, p. 282. Eurographics Association, Geneva (2007)

    Google Scholar 

  15. Fowler, R., Little, J.: Automatic extraction of irregular network digital terrain models. In: SIGGRAPH, p. 207. ACM Press, New York (1979)

    Google Scholar 

  16. Garland, M., Heckbert, P.: Fast polygonal approximation of terrains and height fields. Tech. Rep. CMU-CS-95-181, Carnegie Mellon University (1995)

  17. Gobbetti, E., Marton, F., Cignoni, P., Di Benedetto, M., Ganovelli, F.: C-BDAM-compressed batched dynamic adaptive meshes for terrain rendering. Comput. Graph. Forum 25(3), 333–342 (2006)

    Article  Google Scholar 

  18. Hoppe, H.: Smooth view-dependent level-of-detail control and its application to terrain rendering. In: IEEE Visualization, pp. 35–42. IEEE Computer Society Press, Los Alamitos (1998)

    Google Scholar 

  19. Losasso, F., Hoppe, H.: Geometry clipmaps: terrain rendering using nested regular grids. In: IEEE Visualization, pp. 769–776. ACM Press, New York (2004)

    Google Scholar 

  20. Rabinovich, B., Gotsman, C.: Visualization of large terrains in resource-limited computing environments. In: IEEE Visualization, pp. 95–102. IEEE Computer Society Press, Los Alamitos (1997)

    Google Scholar 

  21. Rippa, S.: Minimal roughness property of the Delaunay triangulation. Comput. Aided Geom. Design 7, 489–497 (1990)

    Article  MATH  MathSciNet  Google Scholar 

  22. Valette, S., Chaine, R., Prost, R.: Progressive lossless mesh compression via incremental parametric refinement. Comput. Graph. Forum 28(5), 1301–1310 (2009)

    Article  Google Scholar 

  23. Yang, S., Choi, Y., Lee, H.: CAD data visualization on mobile devices using sequential constrained Delaunay triangulation. Comput. Aided Design 41(5), 375–384 (2009)

    Article  Google Scholar 

  24. Zhang, W.: Ringlike level of detail in real-time terrain rendering. In: International Conference on Environmental Science and Information Application Technology, pp. 716–719 (2009)

  25. Zhang, H., Sun, J., Liu, J., Nan, L.: A new simplification method for terrain model using discrete particle swarm optimization. In: The 15th International Symposium on Advances in Geographic Information Systems (ACM GIS), pp. 1–4 (2007)

Download references

Author information

Authors and Affiliations

  1. Department of Computer Science, University of Calgary, 2500 University Drive NW, Calgary, AB, Canada, T2N 1N4

    Xin Liu, Jon G. Rokne & Marina L. Gavrilova

Authors
  1. Xin Liu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jon G. Rokne
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marina L. Gavrilova
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xin Liu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liu, X., Rokne, J.G. & Gavrilova, M.L. A novel terrain rendering algorithm based on quasi Delaunay triangulation. Vis Comput 26, 697–706 (2010). https://doi.org/10.1007/s00371-010-0440-3

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00371-010-0440-3

Keywords

Search

Navigation