ERCIM News No.44 - January 2001 [contents]

A System for Out-of-Core Simplification of Huge Meshes

by Paolo Cignoni and Roberto Scopigno

Recent evolution in graphics technology has been impressive, and the management of very complex models is now possible on inexpensive platforms. We present the results of a project aimed at the design and implementation of a library for the out-of-core management of huge 3D meshes. One of the main goals is to support high quality simplification of huge meshes.

The performance of graphics subsystems has improved enormously in the last couple of years, but unfortunately the complexity of 3D scenes and graphics applications has also increased greatly. A very critical aspect in interactive 3D graphics is the complexity, in terms of number of triangles, of the meshes to be managed. Huge meshes can be easily produced in many applications: by fitting isosurfaces on large volume datasets, by converting surfaces into triangulated meshes, by 3D scanning real objects. All 3D scanners perform a regular sampling on the surface of an object, returning triangle meshes of complexity directly proportional to the scanner’s sampling resolution and the object surface area. For example, the size of the S. Matthew 3D model, recently produced by the Digital Michelangelo Project, is around 370M triangles. Obviously, these complex meshes introduce severe overheads in transmission, rendering, processing and storage. Mesh simplification and level-of-detail (LOD) management can in many cases efficiently reduce these overheads but only very large and costly systems can manage meshes characterized by such a huge size: RAM size is often a severe bottleneck.

The management of complex geometric datasets is a very active research area. A number of sophisticated technologies have been developed to simplify the geometry while maintaining accuracy and preserving any attributes contained (eg colour or pictorial data), and to use LOD techniques to speedup rendering.

We have recently studied a problem which arises while 3D scanning large artefacts: how can simplification technology be extended to manage datasets that do not fit the main memory of most computers? Our aim is to design an Out Of Core (OOC) mesh simplifier. Here below we describe the architecture of a new OOC simplifier, which adopts a simplification approach based on edge collapse.

Management and Simplification of Huge Meshes
We briefly introduce a system which supports huge mesh management (including mesh editing, visualization, simplification and detail preservation) on PC-based platforms. The system uses a innovative hierarchical data structure, called Octree-based External Memory Mesh (OEMM), to maintain the data on external memory, to load only selected sections dynamically in main memory, and to preserve data consistency during local updates.

Our goal has been the management of really huge meshes on a PC-based platform with limited memory. No existing systems support this functionality. The hierarchical OEMM data structure is at the base of our mesh management and simplification system. The OEMM structure supports dynamic ‘on request’ loading of portions of the current dataset from secondary memory, for the browsing or updating of geometrical and topological information. This data structure can be constructed starting from a generic raw triangle-based mesh representation. The following modules can be built on the top of this data structure:

Our system supports management and simplification of up to O (109) triangles meshes. The time overhead due to the external memory management is affordable.

The only other approach which supports out-of-core simplification of huge meshes is the out-of-core clustering solution recently proposed by Lindstrom at Siggraph 2000. This solution is very easy to implement but, unfortunately, it has the drawbacks of the clustering approach: the simplified mesh quality is much lower than the quality of simplified meshes produced with the edge collapse approach, simplification is not adaptive to surface shape and many topological degenerated situations are introduced. We have compared the results produced by OOC Clustering and our OEMM edge collapse simplifier on the same dataset (the David mesh of the Digital Michelangelo Project) and the improvement of shape accuracy supported by our solution was significant.

This project has been developed with the financial support of the Progetto Finalizzato ‘Beni Culturali’ of the Italian National Research Council and the Project ‘RIS+’ of the Tuscany Regional Government. Scanned data are courtesy of the Digital Michelangelo Project, Stanford University (USA).

Visual Computing Group CNR-PISA:

Please Contact:
Paolo Cignoni - IEI-CNR
Tel: +39 050 315 2927