Multiresolution Decimation
based on Global Error

Surface simplification is a very hot topic in visualization, for several application-driven motivations. In fact, huge surface meshes are produced in a number of fields, e.g. in volume visualization, virtual reality, automatic acquisition via range scanners, free form surface modeling.

Reducing the complexity of surface meshes is therefore a must to guarantee interactivity in rendering or, in some cases, to make the rendering itself possible. In fact, such large meshes often go over the sustainable storage/graphics performance of the current mid-level graphics subsystems. This interest in surface simplification is also proved by the large number of research groups which have started projects on this topic and the many papers published in recent years.

The goals of our activity on surface simplification are:

an accurate estimation of the approximation error introduced in the simplification process;
an high reduction factor;
the management of multiresolution: once the simplification process has been run, we want to make possible the interactive extraction of any LOD (Level Of Detail) representation.
short simplification times and low memory consumption, to allow the management of large meshes.

A new, general multiresolution data scheme together with an enhanced simplification approach are presented here. Jade, a new simplification solution based on the Mesh Decimation approach has been designed to provide both increased approximation precision, based on global error management, and multiresolution output.
Moreover, we show that with a small increase in memory, which is needed to store the multiresolution data representation, we are able to extract any level of detail representation from the simplification results in an extremely efficient way.

We have also developed a tool to measure the difference between a full resolution and a reduced mesh called Metro. Metro requires no knowledge of the simplification approach so it can be used to compare different simplification tecniques.

Jade: Multiresolution Decimation based on Global Error

Jade (Just Another Decimator) is our prototypal system for the simplification of triangular meshes. Given an input model and a user-specified error tolerance, the algorithm generates an output model that attempts to reduce considerably the number of polygons while staying within the specified error tolerance.

Jade's main features are :

approximation error : an accurate estimation of the approximation error introduced in the simplification process;
compression factor : a reduction factor comparable or better than other approaches, under the same level of approximation;
multiresolution management: once the simplification process has been run, it is possible to interactively extract any LOD (Level Of Detail) representation;
working domain: wide generality, the algorithm manages self intersecting, not manifold, not orientable mesh;
space/time efficency: short simplification time and low memory consumption, to allow the management of large meshes.

Jade is based on a "decimation approach" (mesh size is reduced by removing vertices, see Zarge et al. Siggraph '92).

Jade is described in a paper (also available in the web).

The Jade v.2 prototype is available in public domain. With respect to the previous version, the new Jade v.2 release supports enhanced error evaluation, provides a GUI (and, hopefully, should have less bugs).

The sw has been compiled for SGI and ALPHA workstations

Browse the Jade 2.0 HTML User Manual

Download the Jade 2.0 HTML User Manual (~650KB)

Download Jade 2.0

Download the paper describing Jade

Results

Note: these results should have been updated, because they were produced with the first version (Jade v.1) of our simplification system.

Modeled Surface, Lyria

Images below represents a mathematical modeled surface originally with about 60.000 triangles reduced by Jade.
On the left the original mesh, at center the reduced mesh and on the right a color image representing the approximation error.
The last image is generated by Metro.

Original Mesh	Reduced Mesh

Object	Vertex	Face	Area	F.E.L.^*
Original	29970	57884	348189	9.64
Reduced	1025	2075	348103	1.48

^*F.E.L. = Feature Edge Total Length (feature angle=90 deg.)

		Total	Positive	Negative
Mean Square Error	Absolute	1.3586	0.9764	1.4456
Mean Square Error	Relative^*	0.0559	0.0402	0.0595
Max Error	Absolute	3.5573	3.5441	3.5573
Max Error	Relative^*	0.1464	0.1458	0.1464

^*The relative error is measured as a percentage of the bounding box diagonal.

Papers

Multiresolution Decimation based on Global Error
A. Ciampalini, P. Cignoni, C. Montani, and R. Scopigno
The Visual Computer, Springer International, 13(5), 1997, pp.228-246.

Abstract
Due to the surface meshes produced at increasing complexity in many applications, interest in efficient simplification algorithms and multiresolution representation is very high. An enhanced simplification approach together with a general multiresolution data scheme are presented here. Jade, a new simplification solution based on the Mesh Decimation approach has been designed to provide both increased approximation precision, based on global error management, and multiresolution output. Moreover, we show that with a small increase in memory, which is needed to store the multiresolution data representation, we are able to extract any level of detail representation from the simplification results in an extremely efficient way.
Results are reported on empirical time complexity, approximation quality, and simplification power.

Images

Jade Images