Hierarchical Methods for Computer Graphics

This paper presents a framework for multiresolution compression and geometric reconstruction of arbitrarily dimensioned data designed for distributed applications. Although being restricted to uniform sampled data, our versatile approach enables the handling of a large variety of real world elements. Examples include nonparametric, parametric and implicit lines, surfaces or volumes, all of which are common to large scale data sets. The framework is based on two fundamental steps: Compression is carried out by a remote server and generates a bitstream transmitted over the underlying network. Geometric reconstruction is performed by the local client and renders a piecewise linear approximation of the data. More precisely, our compression scheme consists of a newly developed pipeline starting from an initial B-spline wavelet precoding. The fundamental properties of wavelets allow progressive transmission and interactive control of the compression gain by means of global and local oracles. In particular we discuss the problem of oracles in semiorthogonal settings and propose sophisticated oracles to remove unimportant coefficients. In addition, geometric constraints such as boundary lines can be compressed in a lossless manner and are incorporated into the resulting bit-stream. The reconstruction pipeline performs a piecewise adaptive linear approximation of data using a fast and easy to use point removal strategy which works with any subsequent triangulation technique. As a result, the pipeline renders line segments, triangles or tetrahedra. Moreover, the underlying continuous approximation of the wavelet representation can be exploited to reconstruct implicit functions, such as isolines and isosurfaces more smoothly and precisely than commonplace methods. Although it scales straightforwardly to higher dimensions the performance of our framework is illustrated with results achieved on data very popular in practice: parametric curves and surfaces, digital terrain models, and volume data