A novel terrain rendering algorithm based on quasi Delaunay triangulation

被引:5
作者
Liu, Xin [1 ]
Rokne, Jon G. [1 ]
Gavrilova, Marina L. [1 ]
机构
[1] Univ Calgary, Dept Comp Sci, Calgary, AB T2N 1N4, Canada
关键词
Terrain rendering; Quasi Delaunay triangulation; Smooth morphing; DYNAMIC ADAPTIVE MESHES; BDAM;
D O I
10.1007/s00371-010-0440-3
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:697 / 706
页数:10
相关论文
共 24 条
[1]  
[Anonymous], 2003, P 14 IEEE VIS 2003 V
[2]  
Apu RA, 2004, LECT NOTES COMPUT SC, V3044, P592
[3]  
BERG MD, 1998, GRAPH MODEL IM PROC, V60, P1
[4]   Real-time Rendering and Manipulation of Large Terrains [J].
Bhattacharjee, Shiben ;
Patidar, Suryakant ;
Narayanan, P. J. .
SIXTH INDIAN CONFERENCE ON COMPUTER VISION, GRAPHICS & IMAGE PROCESSING ICVGIP 2008, 2008, :551-559
[5]   BDAM - Batched dynamic adaptive meshes for high performance terrain visualization [J].
Cignoni, P ;
Ganovelli, F ;
Gobbetti, E ;
Marton, E ;
Ponchio, F ;
Scopigno, R .
COMPUTER GRAPHICS FORUM, 2003, 22 (03) :505-514
[6]   Temporal continuity of levels of detail in Delaunay triangulated terrain [J].
CohenOr, D ;
Levanoni, Y .
VISUALIZATION '96, PROCEEDINGS, 1996, :37-42
[7]  
De Berg M., 2008, Computational Geometry: Algorithms and Applications, V17
[8]  
DEB S, 2006, ACM SIGGRAPH 2006 SK, P181
[9]   Dynamic delaunay tetrahedralisation of a deforming surface [J].
Debard, Jean-Baptiste ;
Balp, Romain ;
Chaine, Raphaelle .
VISUAL COMPUTER, 2007, 23 (12) :975-986
[10]  
DECASTRP M, 2009, COMPUT GRAPH FORUM, V28