Topraj Gurung
School of Interactive Computing
College of Computing
Georgia Institute of Technology
http://www.cc.gatech.edu/~topraj

Title: Compact Connectivity Representation for Triangle Meshes

Committee:
-------------

• Dr. Jarek Rossignac (Advisor, College of Computing)
• Dr. J. David Frost (Co-Advisor, School of Civil and Environmental Engineering)
• Dr. Greg Turk (College of Computing)
• Dr. C. Karen Liu (College of Computing)
• + Dr. Peter Lindstrom (Lawrence Livermore National Laboratory)

Abstract:
-------------
A fraction of digital models used in entertainment, medical visualization, architecture, GIS, and mechanical CAD are defined in terms of their boundaries. These boundaries are often approximated using triangle meshes. The complexity of models, which can be measured by triangle count, increases rapidly with the precision of scanning technologies and with the needs for higher resolution. An increase in mesh complexity results in an increase of storage requirement, which in turn increases the frequency of disk access or cache misses during mesh processing, and hence decreases performance. For example, in a test application involving a mesh with 55 million triangles in a machine with 4GB of memory versus a machine with 1GB of memory, performance slows down by a factor of about 6000 because of memory thrashing. To help reduce memory thrashing, we focus on decreasing the average storage requirement per triangle (rpt).

The proposed research covers compact connectivity representation for triangle meshes and discusses 4 data structures for triangle meshes:
1) Sorted Opposite Table (SOT), which uses about 3 rpt and is easily extensible to tetrahedral meshes
2) Sorted Quad (SQuad), which uses about 2 rpt and has interesting extensions to streaming
3) Laced Ring (LR), which uses about 1 rpt and supports an efficient implementation of the corner operators
4) Zipper, an extension of LR, which uses about 6 bits per triangle, but for which the operators are not as efficient as those for LR

The triangle mesh data structures proposed in this thesis support the standard set of mesh connectivity operators at average constant cost. If geometry is stored as 16-bit quantized coordinates, using Zipper instead of the Corner Table increases the size of the mesh that can be stored in-core by a factor of 8.