Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1109/TVCG.2013.81 | IEEE Trans. Vis. Comput. Graph. |
Keywords | Field | DocType |
squad representation,adjacent triangle,compact representation,memory-efficient sequential stream processing,streamable representation,array-based grouper representation,data-parallel processing,grouper interleaves geometry,large triangle mesh,new connectivity representation,streamable triangle mesh data,computational complexity,data structures,mesh generation,random access | Adjacency list,Data structure,Polygon mesh,Vertex (geometry),Computer science,Amortized analysis,Theoretical computer science,T-vertices,Triangle mesh,Random access | Journal |
Volume | Issue | ISSN |
20 | 1 | 1941-0506 |
Citations | PageRank | References |
1 | 0.34 | 16 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mark Luffel | 1 | 26 | 2.14 |
| Topraj Gurung | 2 | 57 | 2.80 |
| Peter Lindstrom | 3 | 1838 | 103.19 |
| Jarek Rossignac | 4 | 3101 | 330.15 |