Back to search

Georgia Institute of Technology

Compact connectivity representation for triangle meshes

Abstract

dc:description.abstract

Many digital models used in entertainment, medical visualization, material science, architecture, Geographic Information Systems (GIS), and mechanical Computer Aided Design (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 need 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 decreases 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 32-bit integer 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 introduced by the previously proposed Corner Table at an amortized constant time complexity. They can be constructed in linear time and space from the 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 about 8.

Degree

thesis:*
Department dc:contributor.department
Computer Science
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2013

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gurung, Topraj
Advisors dc:contributor.advisor
  • Frost, J. David
  • Rossignac, Jarek
Committee members dc:contributor.committeemember
  • Lindstrom, Peter
  • Liu, C. Karen
  • Turk, Greg

Subjects

dc:subject × 7

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/47709

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gurung, Topraj. Compact connectivity representation for triangle meshes. Georgia Institute of Technology, 2013. http://hdl.handle.net/1853/47709