We present Grouper: an all-in-one compact file format, random-access data structure, and streamable representation for large triangle meshes. Similarly to the recently published SQuad representation, Grouper represents the geometry and connectivity of a mesh by grouping vertices and triangles into fixed-size records, most of which store two adjacent triangles and a shared vertex. Unlike SQuad, however, Grouper interleaves geometry with connectivity and uses a new connectivity representation to ensure that vertices and triangles can be stored in a coherent order that enables memory-efficient sequential stream processing. We present a linear-time construction algorithm that allows streaming out Grouper meshes using a small memory footprint while preserving the initial ordering of vertices. As a part of this construction, we show how the problem of assigning vertices and triangles to groups reduces to a well-known NP-hard optimization problem, and present a simple yet effective heuristic solution that performs well in practice. Our array-based Grouper representation also doubles as a triangle mesh data structure that allows direct access to vertices and triangles. Storing only about two integer references per triangle--i.e., less than the three vertex references stored with each triangle in a conventional indexed mesh format--Grouper answers both incidence and adjacency queries in amortized constant time. Our compact representation enables data-parallel processing on multicore computers, instant partitioning and fast transmission for distributed processing, as well as efficient out-of-core access. We demonstrate the versatility and performance benefits of Grouper using a suite of example meshes and processing kernels.

Abstract 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.

We propose LR ( Laced Ring )---a simple data structure for representing the connectivity of manifold triangle meshes. LR provides the option to store on average either 1.08 references per triangle or 26.2 bits per triangle. Its construction, from an input mesh that supports constant-time adjacency queries, has linear space and time complexity, and involves ordering most vertices along a nearly-Hamiltonian cycle. LR is best suited for applications that process meshes with fixed connectivity, as any changes to the connectivity require the data structure to be rebuilt. We provide an implementation of the set of standard random-access, constant-time operators for traversing a mesh, and show that LR often saves both space and traversal time over competing representations.

The Corner Table (CT) promoted by Rossignac et al. provides a simple and efficient representation of triangle meshes, storing 6 integer references per triangle (3 vertex references in the V table and 3 references to opposite corners in the O table that accelerate access to adjacent triangles). The Compact Half Face (CHF) proposed by Lage et al. extends CT to tetrahedral meshes, storing 8 references per tetrahedron (4 in the V table and 4 in the O table). We call it the Vertex Opposite Table (VOT) and propose a sorted variation, SVOT, which does not require any additional storage and yet provides, for each vertex, a reference to an incident corner from which an incident tetrahedron may be recovered and the star of the vertex may be traversed at a constant cost per visited element. We use a set of powerful wedge-based operators for querying and traversing the mesh. Finally, inspired by tetrahedral mesh encoding techniques used by Weiler et al. and by Szymczak and Rossignac, we propose our Sorted O Table (SOT) variation, which eliminates the V table completely and hence reduces storage requirements by 50% to only 4 references and 9 bits per tetrahedron, while preserving the vertex-to-incident-corner references and supporting our wedge operators with a linear average cost.