|
The multiresolution framework
The components of the Multiresolution package of NeMeSi are depicted in the figure below:
The components in the Models box can be applied to any non-manifold model loaded
into NeMeSi. The remaining component, D3b, can only be applied to height field
data that contain missing values, an interesting problem in the field of geoscience.
Multiresolution representation
The standard operator used to construct multiresolution representation of models is
the edge collapse. The operator introduced by Hoppe has been generalized to handle
non-manifold models correctly. In particular, the operator is guaranteed not to change
the topology of models. This is accomplished by defining a set of allowable collapses:
- A vertex in the interior of a 2-cell, i.e. not on a boundary or on an intersection
curve, can be collapsed with any of its neighbor vertices.
- A vertex on a boundary or on an intersection of a 2-cell can only be collapsed
with its two neighbors on the one-cell.
- A vertex on the intersection of two one-cells, i.e. a zero-cell, cannot be removed
from the model.
Using these simple rules, plus an error norm that consider topological inconsistencies,
allowed us to construct a robust simplification algorithm. The following figures show
how models are simplified:
Multiresolution editing
An important functionality of any modeling system is editing. Traditionally, non-manifold
models are edited in a manifold setting by extracting surfaces from it and handling them
separately. The NeMeSi framework attempts at constructing a basic editor that works in
the model, so that changes have a global effect.
Editing is performed in four steps:
- Initially, the user defines a handle that will be used in the edit operations.
- The smooth base domain of the model is computed, and the high frequency information
is stored in local frames. This is an important step, since edits should only affect the
structural information of the model, but not the details.
- The user then modifies the surface by displacing the handle.
- The changes in the surface are computed by calculating the new base domain that
interpolates the position of the handle, and by adding the high frequency information
to it.
This operation is illustrated in the following example:
D3b: continuous LOD of height field data
An interesting challenge in geoscience consists in computing continuous LOD approximation
of height field data that contains missing values. In particular, it must be guaranteed
that the topological type of any approximation is the same than the topological type of
the input surface, and that no self-intersection of the boundaries in parameter space
occours.
The D3b framework solves this problem using a standard vertex removal algorithm extended
to a set of constraints to guarantee the correctness of the approximations. The framework
is subdivided into two components:
- A pre-computation pipeline computes the importance of every vertex in the
height field. During this computation, the algorithm checks whether a vertex can be
safely removed from the surface without invalidating the assumptions stated above.
- A run-time pipeline constructs an approximation by collecting the n
most important vertices, triangulating them using an unconstrained Delaunay triangulation,
and by removing any extra vertices that cover the holes of the surface.
Some of the results obtained using D3b are shown below:
|