Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1007/s00371-010-0440-3 | The Visual Computer |
Keywords | Field | DocType |
delaunay triangulation,simple method,mesh model,point insertion,quasi delaunay triangulation,terrain rendering · quasi delaunay triangulation · smooth morphing,smooth morphing,successive delaunay mesh,novel terrain rendering algorithm,proposed algorithm,delaunay property,successive frame,relative importance,digital elevation model,terrain rendering,real time | Computer vision,Chew's second algorithm,Bowyer–Watson algorithm,Minimum-weight triangulation,Computer science,Surface triangulation,Algorithm,Artificial intelligence,Constrained Delaunay triangulation,Ruppert's algorithm,Pitteway triangulation,Delaunay triangulation | Journal |
Volume | Issue | ISSN |
26 | 6-8 | 1432-2315 |
Citations | PageRank | References |
4 | 0.42 | 19 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Xin Liu | 1 | 4 | 0.42 |
| Jon G. Rokne | 2 | 263 | 45.63 |
| Marina L. Gavrilova | 3 | 2012 | 211.17 |