The NeMeSi Project

Arrow Overview
Arrow Data structure
Arrow Fairing
Arrow Multiresolution
Arrow Subdivision
Arrow Feature Extraction
Arrow Publications

The multiresolution framework

The components of the Multiresolution package of NeMeSi are depicted in the figure below:
Components of the multiresolution package
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:
Input model Coarse model
Input model Coarse model

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:
  1. Initially, the user defines a handle that will be used in the edit operations.
  2. 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.
  3. The user then modifies the surface by displacing the handle.
  4. 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:
Input model Smooth base domain Edited base domain Edited model

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:
Input model Coarse approximation Wireframe of the approximation
Input model Coarse approximation Wireframe of the approximation

Valid HTML 4.0!