Random-Accessible Compressed Triangle Meshes

by Sung-Eui Yoon and Peter Lindstrom

Puget Sound Iso-Contour: The contour line (in black) at 720m elevation was extracted from an unstructured terrain model consisting of 134M triangles. The contour passes through 286K triangles. Our compression method achieves a compression ratio of up to 21 to 1 compared to uncompressed original mesh. Moreover, we are able to achieve runtime performance of the iso-contouring 2.5 times on average compared to using uncompressed meshes.


With the exponential growth in size of geometric data, it is becoming increasingly important to make effective use of multilevel caches, limited disk storage, and bandwidth. As a result, recent work in the visualization community has focused either on designing sequential access compression schemes or on producing cache-coherent layouts of (uncompressed) meshes for random access. Unfortunately combining these two strategies is challenging as they fundamentally assume conflicting modes of data access. In this paper, we propose a novel order-preserving compression method that supports transparent random access to compressed triangle meshes. Our decompression method selectively fetches from disk, decodes, and caches in memory requested parts of a mesh. We also provide a general mesh access API for seamless mesh traversal and incidence queries. While the method imposes no particular mesh layout, it is especially suitable for cache-oblivious layouts, which minimize the number of decompression I/O requests and provide high cache utilization during access to decompressed, in-memory portions of the mesh. Moreover, the transparency of our scheme enables improved performance without the need for application code changes. We achieve compression rates on the order of 20:1 and significantly improved I/O performance due to reduced data transfer. To demonstrate the benefits of our method, we implement two common applications as benchmarks. By using cache-oblivious layouts for the input models, we observe 2--6 times overall speedup compared to using uncompressed meshes.


Paper: Random-Accessible Compressed Triangle Meshes
IEEE TVCG and Visualization, 2007

Source codes: OpenRACM
Talk slides: ppt slides


We would like to thank Martin Isenburg for sharing his streaming mesh compression code with us. This work was performed under the auspices of the U.S. DOE by LLNL under contract no.W-7405-Eng-48, and was supported in part by a KAIST seed grant

Related Links

Cache-oblivious layouts

Department of Computer Science
DaeJeon, 305-701
South Korea

Note: This homepage is not sanctioned or supported by DoE, UC, LLNL or CASC.