Colloquy Cycle on Thursday, June 19, 1997 - 16:15

Multilevel representations and mesh reduction techniques have been used for accelerating the processing and the rendering of large datasets representing scalar or vector valued functions defined on complex 2 or 3 dimensional meshes. We present a method based on finite elements and hierarchical bases which combines these two approaches in a new and unique way that is conceptually simple and theoretically sound. Starting with a very coarse triangulation of the functional domain a hierarchy of highly non-uniform tetrahedral (or triangular in 2D) meshes is generated adaptively by local refinement. This process is driven by controlling the local error of the piecewise linear finite element approximation of the function (in the least-squares sense) on each mesh element. Flexibility in choosing the underlying error norm allows for gradient information to be included. A reliable and efficient a posteriori estimate of the global approximation error combined with a preconditioned conjugate gradient solver are the key components of the implementation. Many areas where the proposed method can by applied successfully are envisioned, such as mesh reduction of parameterized grids, visualization of scalar and vector volume data, physically based computer animation of extended bodies and global illumination algorithms. The example application we implemented in order to analyze the properties and advantages of the generated tetrahedral mesh is an iso-surface algorithm which combines the so far separated tasks of extraction acceleration and polygonal decimation in one single processing step. The quality of the iso-surface is measured based on a special geometric norm which does not require the full resolution surface.