External Memory Management and Simplification of Huge Meshes

Very large triangle meshes, i.e. meshes composed of millions of faces, are becoming common in many applications. Obviously, processing, rendering, transmission and archival of these meshes are not simple tasks. Mesh simplification and LOD management are a rather mature technology that in many cases can efficiently manage complex data. But only few available systems can manage meshes characterized by a huge size: RAM size is often a severe bottleneck. In this paper we present a data structure called Octree-based External Memory Mesh (OEMM ). It supports external memory management of complex meshes, loading dynamically in main memory only the selected sections and preserving data consistency during local updates. The functionalities implemented on this data structure (simplification, detail preservation, mesh editing, visualization and inspection) can be applied to huge triangles meshes on low cost PC platforms. Simplification is performed by adopting the approach based on edge collapse and quadric error. The time overhead due to the external memory management is affordable. Results of the test of our system on complex meshes are presented.

We would like to thank Marc Levoy and the Stanford Computer Graphics Group for providing scanned data, and for choosing our simplified meshes as the official simplified models distributed from the Digital Michelangelo Project's Archive of 3D Models.

Papers

Images

A comparison of the different visual quality provided by: two simplified David meshes, 1,683K and 10K faces, and the latter enhanced by mapping a re-sampled bump texture (please note that the image with bump-mapping has been created with a different viewer):

A comparison of the different quality of the models obtained from the simplification of the 2mm David mesh (8M faces) using the OutOfCore Clustering solution (top) and our OEMM simplifier based on edge collapse and quadric error (bottom):

A comparison of the different quality of some simplified David models (from the original 1mm David mesh, 53.6 M faces) using the OEMM simplification.


Original data Size of rendered section ~161k triangles		quad-err=1e-2 Size of rendered section ~39k triangles

quad-err=1e-1 Size of rendered section ~21k triangles	quad-err=1 Size of rendered section ~10k triangles	quad-err=10 Size of rendered section ~6k triangles


Simplifed mesh 1.6M tri quad-err=10		Original data rendered section of ~532k triangles

quad-err=1e-5 rendered section of ~100k triangles	quad-err=1e-3 rendered section of ~30k triangles	quad-err=1e-1 rendered section of ~7k triangles

A simplified model of the S. Matthew statue is shown on the left; a small section of the mesh (S. Matthew's eye and part of the nose) is shown on the right at different accuracies.

Qslim
18838 tri

RAM QEM
18838 tri

OOCC
19071 tri

OEMM QEM
18838 tri

Results obtained in the simplification of the Happy Buddha mesh, using four different simplification codes (as explained in the paper).
These meshes are available here for free downloading. The meshes are in ply format.

full depth octree

first 6 levels of octree

first 5 levels of the octree

The images show the structure of the octree of the St Matthew statue; the bounding box of the contained mesh portion is shown for each node of the octree.
The figure on the left shows the full octree, center and right images show the first 6 and 5 levels of the octree (leaves are shown in green, and intermediate nodes in blue)

Some snapshots of the mesh editing system based on the OEMM

Given an OEMM encoding the result of the decimation at quadric error equal to 1e-1 (i.e. a mesh of 6M faces), a small portion of the back of the St. Matthew statue is loaded and all the holes smaller than a user selected size (<100 edges) are automatically filled; hole boundaries are enhanced in green.

... a paper on simplification cannot be successful without a bunny!


1683k face shaded	10k faces, shaded	10k faces, bump mapped