Efficient algorithms for embedded rendering of terrain models

Author

Balmelli, Laurent ; Ayer, Serge ; Vetterli, Martin

Author_Institution

Lab. for Audio-Visual Commun., Fed. Inst. of Technol., Lausanne, Switzerland

Volume

2

fYear

1998

fDate

4-7 Oct 1998

Firstpage

914

Abstract

Digital terrains are generally large files and need to be simplified to be rendered efficiently. We propose to build an adaptive embedded triangulation based on a binary tree structure to generate multiple levels of details. We present a O(nlogn) decimation algorithm and a O(nlogn) refinement algorithm, where n is the number of elevation points. We compare them in a rate-distortion (RD) framework. The algorithms are based on an improved version of the optimal tree pruning algorithm G-BFOS allowing one to deal with constrained tree structures and non-monotonic tree functionals

Keywords

computational complexity; optimisation; rate distortion theory; rendering (computer graphics); tree data structures; G-BFOS; adaptive embedded triangulation; binary tree structure; constrained tree structures; decimation algorithm; digital terrains; efficient algorithms; elevation points; embedded rendering; large files; nonmonotonic tree functionals; optimal tree pruning algorithm; rate-distortion framework; refinement algorithm; terrain models; Binary trees; Digital elevation models; Laboratories; Rain; Rate-distortion; Rendering (computer graphics); Surface cracks; Tail; Tin; Tree data structures;

fLanguage

English

Publisher

ieee

Conference_Titel

Image Processing, 1998. ICIP 98. Proceedings. 1998 International Conference on

Conference_Location

Chicago, IL

Print_ISBN

0-8186-8821-1

Type

conf

DOI

10.1109/ICIP.1998.723704

Filename

723704