Efficient algorithms for embedded rendering of terrain models
Laurent Balmelli, Steven K. Ayer, Martin Vetterli · 2002
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.