Random-Accessible Compressed Triangle Meshes
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.
Abstract
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.
Contents
Paper:
Random-Accessible Compressed Triangle Meshes
IEEE TVCG and Visualization, 2007
Source codes: OpenRACM
Talk slides: ppt slides
Acknowledgements
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
KAIST SGLab.
Department of Computer Science
KAIST
DaeJeon, 305-701
South Korea
Note: This homepage is not sanctioned or supported by DoE, UC, LLNL or CASC.
