Efficient terrain data representation for 3D rendering using the generalized BFOS algorithm

Digital terrain data has widespread applications in areas such as the military, geographic information systems (GIS), and flight simulator video games. The combination of the abundance of terrain data with the limited rendering capabilities of computer graphics machines creates the necessity for algorithms which generate efficient representations of the data for rendering. This paper presents such an algorithm. Terrain data is tessellated using a regular triangular grid, and the regular grid is represented using a binary tree. The generalized BFOS algorithm, a well-known optimal tree-pruning method for regression and quantization trees, is used to prune the tree optimally, resulting in a far more efficient representation of this data than known in the literature. In addition to its optimal properties, the representation is also embedded, making it suitable for displays at multiple resolutions.