TOM: totally ordered mesh. A multiresolution data structure for time-critical graphics applications

摘要

Tridimensional interactive applications are confronted to situations where very large databases have to be animated, transmitted and displayed in very short bounded times. As it is generally impossible to handle the complete graphics description while meeting timing constraint, techniques enabling the extraction and manipulation of a significant part of the geometric database have been the focus of many research works in the field of computer graphics. Multiresolution representations of 3D models provide access to 3D objects at arbitrary resolutions while minimizing appearance degradation. Several kinds of data structures have been recently proposed for dealing with polygonal or parametric representations, but where not generally optimized for time-critical applications. We describe the TOM (Totally Ordered Mesh), a multiresolution triangle mesh structure tailored to the support of time-critical adaptive rendering. The structure grants high speed access to the continuous levels of detail of a mesh and allows very fast traversal of the list of triangles at arbitrary resolution so that bottlenecks in the graphic pipeline are avoided. Moreover, and without specific compression, the memory footprint of the TOM is small (about 108% of the single resolution object in face-vertex form) so that large scenes can be effectively handled. The TOM structure also supports storage of per vertex (or per corner of triangle) attributes such as colors, normals, texture coordinates or dynamic properties. Implementation details are presented along with the results of tests for memory needs, approximation quality, timing and efficacy.