Multiresolution Ordered Meshes

Contents

Multiresolution modeling

Modeling objects by means of polygonal surfaces currently predominates in the field of interactive computer graphics. Visualization of these models is generally slow for distant objects, where the level of detail is excessive, or low in quality for close objects, where the level of detail is insufficient. Multiresolution modeling has been presented as an efficient solution to this problem. It consists in representing an object through multiple approximations or levels of detail (LoDs) each of which is made up of a different number of polygons. In this way the application can perform a selection of the LoD in running time in order to establish a balance between the LoD with which the object will be represented and the amount of time needed to visualize it. A multiresolution scheme must define the data structures and access algorithms that allow the different approximations to be stored and retrieved. The way it is designed has a direct effect on its performance and determines its applicability. There is absolutely no point in developing a scheme in which the overload produced by the data handling process is so large that all attempts to accelerate the visualization are in vain.


Three approximations of the Cow data set simulating the level of detail to be used depending on the distance from the observer

Multiresolution Ordered Meshes, MOM

The MOM scheme provides a solution to the problem of the interactive visualization of polygonal surfaces made up of hundreds of thousands of polygons. MOM keeps a low storage costs and allows, on demand, the extraction of approximations with both a uniform and variable level of detail in an efficient way. It is based on an ordered arrangement of data that is established by the simplification method used in the construction process. This order will allow most of the dependencies that exist between the different stored triangulations to be encoded implicitly, thus lowering storage costs and increasing performance of the access algorithms. The main advantages of this scheme are as follows:

  • Simplicity. The basic data structure of the model corresponds to a structure based on lists, which makes it simple and easy to put into operation. At the same time, this characteristic also helps to simplify both the construction process and the access algorithms.
  • Generality. Any simplification method may be used to construct the multiresolution representation. Manifold and Non-manifold polygonal surfaces can be represented. Both these characteristics favour the use of this scheme in a wider range of applications.
  • Efficiency. The experiments carried out show that storage costs, the extraction time of uniform level of detail approximations and the visualization times of variable level of detail approximations are all greatly improved compared with other multiresolution schemes with characteristics similar to those of MOM.


The eight approximations of the Cow data set shown, from left to right and from top to bottom, correspond to the following levels of detail: 0 (the lowest), 0.03, 0.07, 0.14, 0.21, 0.38, 0.64 and 1.0 (the highest)

Characterization

The criteria used in this characterization are classified into three groups:

  • Input data: they refer to the input data of the multiresolution scheme, such as the type of polygonal surface that it can manage.
  • Application: they refer to the suitability of the multiresolution scheme for application to interactive visualization, progressive transmission or geometry compression.
  • Operation: they refer to the internal operation of the multiresolution scheme, such as the way data is stored or retrieved, and they inform on special functionalities, if any.

Input data

  • The MOM scheme can represent Manifold and Non-manifold polygonal surfaces.
  • The MOM scheme does not provide a specific solution for efficient encoding of appearance attributes.
  • In order to build a MOM representation, The MOM scheme does not impose any condition on how the simplification should be done.

Application

  • The MOM scheme has not been specially designed for the progressive transmission of 3D data through a comunication line. However, It can do it without optimizing the amount of information to be transmitted.
  • The MOM scheme is not suitable for geometry compression.
  • The MOM scheme was designed focused on interactive visualization using uniform LoDs. Data structures were designed so that the retrieving algorithms recover an approximation in the least possible time.
  • The MOM scheme is suitable for interactive visualization using variable LoDs allowing the regions of the object near the observer to be visualized in more detail while the rest of the object is visualized in less detail.


Example of variable resolution level of detail.

Operation

  • The MOM scheme stores the 3D data explicitily, that is, storage of information in the way it is required for the application.
  • The MOM scheme can exploit the frame to frame coherence property in order to  increase the performance of the application.
  • The MOM scheme do not support geomorphing, that is, the soft transition  between approximations by means of the geometric interpolation of the vertices.
  • The MOM scheme requires  the data set to fit entirely into main memory. It cannot interactively visualize data sets when they exceed the main memory size.

Papers

The MOM scheme is the core of my Phd. Thesis defended on December 2000. Results from this research have been presented on several conferences from 1998 to 2001.

Papers in English

The basic details of the MOM scheme were first published in the paper:

  • J. Ribelles, M. Chover, J. Huerta, R. Quirós. "Multiresolution Ordered Meshes" (abstract) (postscript.gz), Proc.of 1998 IEEE Conference on Information Visualization (IV'98), 198-204, London (UK), July 1998. ISBN 0-8186-8509-3.

This basic scheme was later improved, extended and generalized in different ways. In order to exploit the frame-to-frame coherence property:

  • J.Ribelles, M. Chover, A. López, J. Huerta. "Frame-to-frame Coherence of Multiresolution Ordered Meshes" (abstract) (postscript.gz), Actas del IX Congreso Español de Informática Gráfica (CEIG'99), 91-104, Jaen (Spain), June, 1999. ISBN 84-89869-81-2.

In order to use the triangle fan as its basic representation primitive:

  • J.Ribelles, A. López, I. Remolar, O. Belmonte, M. Chover. "Multiresolution Modelling of Polygonal Surface Meshes Using Triangle Fans" (abstract) (paper), Lecture Notes in Computer Science 1953. Proc.of 9th Discrete Geometry for ComputerImagery Conference (DGCI 2000), 431-442, Uppsala (Sweden), December, 2000. ISBN 3-540-41396-0.

In order to retrieve variable resolution levels-of-detail:

  • J.Ribelles, A. López, O. Belmonte, I. Remolar, M. Chover. "Variable Resolution Level-of-detail of Multiresolution Ordered Meshes" (abstract) (postscript.gz), Proc.of 9-th International Conference in Central Europe on Computer Graphics,Visualization and Computer Vision (WSCG 2001), Vol. 2, 299-306, Plzen(Czech Republic), February, 2001. ISBN 80-7082-712-4.

A comparison with the Progressive Meshes scheme is presented in these papers:

  • J.Ribelles, M. Chover, A. López, J. Huerta. "A First Step to Evaluate and Compare Multiresolution Models" (abstract) (postscript.gz), Short Papers and Demos of EUROGRAPHICS'99, 230-232, Milano (Italy), September,1999. ISSN 1017-4656,  (postscript.gz), Departamento de Informática, Universitat Jaume I, Technical Report DI 01-07/99, Castellón (Spain), July, 1999.

Papers in Spanish

My Ph.D. thesis contains the most authoritative description of the multiresolution scheme. It also contains the most extensive analysis of the MOM's behavior:

  • J. Ribelles. "Mallas Ordenadas Multirresolución" (abstract) (postscript.gz), Ph.D.Thesis, Departamento de Informática, Universitat Jaume I, Castellón(Spain), December, 2000

A shorter revision of the MOM scheme is presented in this technical report:

  • J. Ribelles, A. López, O. Belmonte, I. Remolar, M. Chover. "Un Esquema Multirresolución General, Simple y Eficiente para Visualización Interactiva de Superficies Poligonales" (abstract) (postscript.gz), Departamento de Lenguajes y Sistemas Informáticos, Universitat Jaume I, Technical Report DLSI 01/11/2001, Castellón (Spain), November, 2001

The basic details of the MOM scheme were first published in the paper:

  • J. Ribelles, M. Chover, J. Huerta, R. Quirós. " Un Modelo Multirresolución para Visualización Interactiva" (abstract) (postscript.gz), Actas del VIII Congreso Español de Informática Gráfica (CEIG'98), 267-280, Ourense (Spain), June 1998. ISBN 84-8408-017-X
This basic representation was improved in order to use the triangle fanas its basic representation primitive:
  • J. Ribelles, A. López, I. Remolar, O. Belmonte, M. Chover. "Representación de Modelos Multirresolución con Abanicos de Triángulos" (abstract) (postscript.gz), Actas del X Congreso Español de Informática Gráfica (CEIG2000) , 37-50, Castellón (Spain), June, 2000. ISBN 84-8021-314-0
The issue of the progressive transmission was studied in this paper:
  • R. Vidal, J. Ribelles. "Un Servidor de Geometria 3D" (abstract) (postscript.gz), Actas del IX Congreso Español de Informática Gráfica (CEIG'99) , 355-356, Jaen (Spain), June, 1999. ISBN 84-89869-81-2

Software

This software package is a very simple implementation of the MOM scheme. This first version only contains the algorithm to visualize approximations with uniform level of detail. It is not an optimized version. The goal is to provide an easy code to understand. The simplicity of the multiresolution scheme is made evident. Any comments you'd like to make are welcome. You can make free use of the software under the terms of the GNU General Public License.

Instructions

This software requires OpenGL and the GLUT library. It shoulds compile on any Linux system (a makefile is provided), as well as Windows 9x/NT.

  • Run ' visMom cow.mom '. You will see the cow, the current level of detail (0 the lowest detail, 1 the highest detail), the number of faces painted and the frames per second.
  • Use the left button to rotate the object
  • Use Ctrl + left button for zooming
  • Use the right button for options:
    • Polygon mode: choose between fill or line
    • Change the Lod:
      • with Mouse: the LoD changes when you move the mouse and the Shift + left button is holded
      • with Fovy: tle LoD changes with the zoom (default)
      • the highest detail: the highest detail is visualized
      • the lowest detail: the lowest detail is visualized

Downloads

The main distribution contains the source code and a MOM representation of the cow model (this model is based on data distributed with SGI's Powerflip demo). I've also built binary versions on a few different platforms. These are packaged without the MOM model, so please download it as well.