Multiscale compression of digital terrain data to meet real-time rendering rate constraints
Mark C. Miller · 1995
Image synthesis is the algorithmic computation involved in simulating, or rendering, an image of some three dimensional scene. We introduce a trade-off between rendering rate, in images, or frames, per second and the quality of the rendered images. This trade-off is governed by the number of graphics primitives in the input scene. The graphics primitives are elemental surface pieces used to represent the scene and are typically triangles. We present a method for lossy compression of a scene derived from a two dimensional raster of samples of terrain elevation, a digital terrain or height field. The problem is to represent the terrain scene input to a renderer with a number of triangles that can be rendered at a desired rate such that the resulting rendered images are as good as possible. In the approach we propose, a multiscale, power of two, decomposition of the terrain much like a pyramid of resolution is used. Each level in the hierarchy divides the terrain into a two dimensional array of square regions, called cells. For each cell, we store two triangles and related attributes representing the terrain in the cell and the error in this representation. During each frame in a simulated flight over the terrain, our compression algorithm selects cells, and triangles therein, such that the image of the terrain is rendered at the desired rate and with low error. Thus, we are concerned with the trade-off between compression of the set of triangles representing the terrain at the input and the corresponding quality in the image of the terrain at the output of the renderer. Our methods differ from related methods of terrain rendering and surface tiling in that we provide direct and very fine tuned control of the number of triangles used to represent the terrain rendered in each view and that computation of the triangles occurs in real time as the terrain is rendered. We show that we can compute compressed representations of almost arbitrarily large regions of terrain using several thousand triangles per frame in real time. We present results of our method from experiments performed using generic rendering hardware.