Ph.D. Defense of Dissertation Announcement
Title: Compact Connectivity Representation for Triangle Meshes

Topraj Gurung
Computer Science Ph.D. Student
School of Interactive Computing
College of Computing
Georgia Institute of Technology

Thursday, January 10, 2013
2:00 pm - 4:30 pm EDT
Location: TSRB 223

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 measured in references per triangle (rpt).

This thesis covers compact connectivity representation for triangle meshes and discusses four data structures:
1. Sorted Opposite Table (SOT), which uses 3 rpt and has been extended to support tetrahedral meshes 2. Sorted Quad (SQuad), which uses about 2 rpt and has been extended to support streaming 3. Laced Ring (LR), which uses about 1 rpt and offers an excellent compromise between storage compactness and performance of mesh traversal operators 4. Zipper, an extension of LR, which uses about 6 bits per triangle (equivalently 0.19 rpt), therefore is the most compact representation

The triangle mesh data structures proposed in this thesis support the standard set of mesh connectivity operators at expected constant time complexity. They can be constructed in linear cost from the previous proposed Corner Table or any equivalent representation. If geometry is stored as 16-bit coordinates, using Zipper instead of the Corner Table increases the size of the mesh that can be stored in core memory by a factor of 8.