Premium
SQuad: Compact Representation for Triangle Meshes
Author(s) -
Gurung Topraj,
Laney Daniel,
Lindstrom Peter,
Rossignac Jarek
Publication year - 2011
Publication title -
computer graphics forum
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.578
H-Index - 120
eISSN - 1467-8659
pISSN - 0167-7055
DOI - 10.1111/j.1467-8659.2011.01866.x
Subject(s) - traverse , computer science , polygon mesh , tree traversal , vertex (graph theory) , triangle mesh , table (database) , data structure , simple (philosophy) , isosceles triangle , triangle inequality , computer graphics (images) , algorithm , parallel computing , theoretical computer science , mathematics , discrete mathematics , graph , geometry , programming language , database , philosophy , geodesy , epistemology , geography
The SQuad data structure represents the connectivity of a triangle mesh by its “S table” of about 2 rpt (integer references per triangle). Yet it allows for a simple implementation of expected constant‐time, random‐access operators for traversing the mesh, including in‐order traversal of the triangles incident upon a vertex. SQuad is more compact than the Corner Table (CT), which stores 6 rpt, and than the recently proposed SOT, which stores 3 rpt. However, in‐core access is generally faster in CT than in SQuad, and SQuad requires rebuilding the S table if the connectivity is altered. The storage reduction and memory coherence opportunities it offers may help to reduce the frequency of page faults and cache misses when accessing elements of a mesh that does not fit in memory. We provide the details of a simple algorithm that builds the S table and of an optimized implementation of the SQuad operators.