MINGLE
Multiresolution in Geometric Modelling

Research Topic

`Multiresolution' is becoming the term used, in several scientific disciplines, to describe the concept of several levels of detail or accuracy in a single model. In the last five to ten years, numerous applications of multiresolution have begun to emerge in 3D computer graphics and 3D geometric modelling. Among these applications are

fast rendering (e.g. in real-time flight simulation),
editing and compression of both geometric models and images,
surface illumination,
computer animation, and
scientific visualization (such as weather simulations over the earth).

A simple example of the use of multiresolution is in fast rendering of terrain models, represented in the form of triangulations. If the terrain or part of terrain is relatively far from the viewer, it is inefficient to display the whole triangulation. The solution is to create a multiresolution model by breaking down the original model into a hierarchical sequence of coarser and coarser versions, the coarsest one providing merely a rough impression of the original. Since the coarser levels contain much less data, and in particular fewer triangles, they can be displayed much faster than the higher levels. At the same time the coarser levels contain sufficient information for an accurate image, provided the approximation is good. Generally, one wants to balance the two conflicting requirements of low data size and high fidelity (accuracy).

It is applications such as these that motivate the focus of the network project:

Investigation and development of efficient and robust methods for generating, storing, and manipulating multiresolution models based on triangulated data sets.

The goal will be to strive for both fast algorithms and high orders of approximation. The project will embrace both terrain models, in the form of data over planar and spherical triangulations, and free-form surfaces, in the form of triangle meshes in 3D. Although the focus of the project is not on the `B-spline' aspect of geometric modelling, some interaction with B-spline theory (NURBS curves and surfaces) is expected.

The current mathematical theory concerning multiresolution analysis for 3D geometric models is much less developed than that for (2D) image processing. Usually, 2D computer images are represented as rectangular grids of values which are relatively simple mathematical objects and can be analyzed and decomposed using techniques from signal processing, such as wavelets, for example tensor-product Haar wavelets. On the other hand, terrain models and 3D models in computer graphics are typically irregular triangle meshes which are either represented as functions over planar (and frequently spherical) triangulations or as manifold (and possibly non-manifold) triangulations. It is this inherent irregularity that renders standard wavelet techniques non-applicable. Fourier Analysis, which underpins the classical wavelet constructions, is no longer relevant and more general mathematical methods are necessary in order to generalize multiresolution techniques.

Currently diverse research groups are tackling multiresolution in 3D modelling from various angles. One approach is to ignore wavelet theory altogether and apply very pragmatic algorithms, such as thinning and edge-collapsing in order to generate hierarchical sequences of triangle meshes. However, though these kinds of algorithms have already been applied by commercial software companies, the techniques are still in an early phase of development and more (collaborative) effort is needed in order to find optimal algorithms, both from the point of view of approximation error and algorithmic complexity.

Another approach being studied by more mathematically-oriented groups is that of demanding that the model is organized in nested triangulations, giving rise to nested linear spaces. Under this assumption, appropriate wavelet spaces can be defined and various multiresolution decompositions have been carried out and implemented. In order to apply these results to arbitrary meshes however, it is necessary to approximate an arbitrary mesh by a nested one. Here the question is one of finding the best approximation with respect to a given mesh size. An alternative recent approach is the concept of wavelets over non-nested spaces. Another important issue concerning triangulations, whether hierarchical or not, is efficient storage.

Areas of Research Focus

hierarchical decomposition over nested triangulations
generation of smooth surfaces from irregular triangle meshes
thinning of triangle meshes
compression of hierarchical triangle meshes
remeshing
wavelet-like decomposition
application of multiresolution representations to computer graphics
data structures and algorithms for storage and manipulation of hierarchical and nested triangulations

Training Content

All aspects of multiresolution in geometric modelling, namely the mathematical theory, algorithms, and applications in industry and commerce, are under extremely rapid development. Building up the necessary knowledge base and reaching a sufficient level of competence in these areas has therefore become a daunting task for a young researcher. University courses often tend to be too rigidly organized to provide training in the newest research ideas and latest developments in industry. The network group, however, can offer a timely exposure to state-of-the-art techniques in this research area. Young researchers will thus acquire expertise that will make them sought-after specialists in a highly attractive area of information technology.

The joint activities of the training program will include lecture series, workshops, short-term exchange visits, and software management.

Prepared by: SINTEF Applied Mathematics & TECHNION, Computer Science Dept.

Last update: June 15, 2000 | Vitaly Surazhsky