`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
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).
- 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).
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
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
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
- wavelet-like decomposition
- application of multiresolution representations to
- data structures and algorithms for storage and manipulation
of hierarchical and nested triangulations
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.