Random-Accessible Compressed Triangle 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.
[1] 1536 P. Alliez and M. Desbrun, Valence-driven connectivity encoding for 3D meshes. Computer Graphics Forum, 20 (3): 480–489, 2001.
[2] P. Alliez and C. Gotsman, Recent advances in compression of 3D meshes. Advances in Multiresolution for Geometric Modelling, 3–26. 2005.
[3] L. Arge, G. Brodal, and R. Fagerberg, Cache oblivious data structures. Handbook on Data Structures and Applications, chapter 34. 2004.
[4] R. Bar-Yehuda and C. Gotsman, Time/space tradeoffs for polygon mesh rendering. ACM Transactions on Graphics, 15 (2): 141–152, 1996.
[5] A. Bogomjakov and C. Gotsman, Universal rendering sequences for transparent vertex caching of progressive meshes. Computer Graphics Forum, 21 (2): 137–149, 2002.
[6] M. Burtscher and P. Ratanawoabhan, High throughput compression of double-precision floating-point data. IEEE Data Compression Conference, 293–302. 2007.
[7] J. Chhugani and S. Kumar, Geometry engine optimization: Cache friendly compressed representation of geometry. ACM Symposium on Interactive 3D Graphics and Games, 9–16. 2007.
[8] S. Choe, J. Kim, H. Lee, S. Lee, and H.-P. Seidel, Mesh compression with random accessibility. Israel-Korea Bi-National Conf., 81–86. 2004.
[9] P. Cignoni, C. Montani, C. Rocchini, and R. Scopigno, External memory management and simplification of huge meshes. IEEE Transactions on Visualization and Computer Graphics, 9 (4): 525–537, 2003.
[10] C. DeCoro and R. Pajarola, XFastMesh: Fast view-dependent meshing from external memory. IEEE Visualization, 363–370. 2002.
[11] P. Diaz-Gutierrez, A. Bhushan, M. Gopi, and R. Pajarola, Single-strips for fast interactive rendering. The Visual Computer, 22 (6): 372–386, 2006.
[12] E. Gobbetti, F. Marton, P. Cignoni, M. Di Benedetto, and F. Ganovelli, CBDAM—Compressed batched dynamic adaptive meshes for terrain rendering. Computer Graphics Forum, 25 (3): 333–342, 2006.
[13] C. Gotsman, S. Gumhold, and L. Kobbelt, Simplification and compression of 3D meshes. Tutorials on Multiresolution in Geometric Modelling, 319–361. Springer, 2002.
[14] S. Gumhold and W. Strasser, Real time compression of triangle mesh connectivity. ACM SIGGRAPH, 133–140. 1998.
[15] J. Ho, K. Lee, and D. Kriegman, Compressing large polygonal models. IEEE Visualization, 357–362. 2001.
[16] H. Hoppe, Optimization of mesh locality for transparent vertex caching. ACM SIGGRAPH, 269–276. 1999.
[17] I. Ihm and S. Park, Wavelet-based 3D compression scheme for interactive visualization of very large volume data. Computer Graphics Forum, 18 (1): 3–15, 1999.
[18] M. Isenburg and S. Gumhold, Out-of-core compression for gigantic polygon meshes. ACM SIGGRAPH, 935–942. 2003.
[19] M. Isenburg and P. Lindstrom, Streaming meshes. IEEE Visualization, 231–238. 2005.
[20] M. Isenburg, P. Lindstrom, and J. Snoeyink, Streaming compression of triangle meshes. Symposium on Geometry Processing, 111–118. 2005.
[21] M. Isenburg and J. Snoeyink, Face Fixer: Compressing polygon meshes with properties. ACM SIGGRAPH, 263–270. 2000.
[22] K. I. Joy, J. Legakis, and R. MacCracken, Data structures for multiresolution representation of unstructured meshes. Hierarchical and Geometrical Methods in Scientific Visualization, 143–170. Springer, 2003.
[23] J. Kim, S. Choe, and S. Lee, Multiresolution random accessible mesh compression. Computer Graphics Forum, 25 (3): 323–332, 2006.
[24] J. Kim and S. Lee, Truly selective refinement of progressive meshes. Graphics Interface, 101–110. 2001.
[25] D. Le Gall, MPEG: A video compression standard for multimedia applications. Communications of the ACM, 34 (4): 46–58, 1991.
[26] J. Li and C. C. Kuo, A dual graph approach to 3D triangular mesh compression. IEEE ICIP, 891–894. 1998.
[27] G. Lin and T. P.-Y. Yu, An improved vertex caching scheme for 3D mesh rendering. IEEE Transactions on Visualization and Computer Graphics, 12 (4): 640–648, 2006.
[28] P. Lindstrom, Out-of-core construction and visualization of multiresolution surfaces. ACM Symp. on Interactive 3D Graphics, 93–102. 2003.
[29] P. Lindstrom and M. Isenburg, Fast and efficient compression of floating-point data. IEEE Transactions on Visualization and Computer Graphics, 12 (5): 1245–1250, 2006.
[30] F. Rodler, Wavelet based 3D compression with fast random access for very large volume data. Pacific Graphics, 108–117. 1999.
[31] J. Rossignac, Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics, 5 (1): 47–61, 1999.
[32] J. Rossignac, 3D compression made simple: Edgebreaker with zip & wrap on a corner-table. Shape Modelling & Applications, 278–283. 2001.
[33] H. Sagan, Space-Filling Curves. Springer-Verlag, 1994.
[34] P. V. Sander, D. Nehab, and J. Barczak, Fast triangle reordering for vertex locality and reduced overdraw. ACM SIGGRAPH, 2007. To appear.
[35] M. Schindler, Range encoder version 1.3, 2000. URL http://www.compressconsult.comrangecoder /.
[36] E. Shaffer and M. Garland, A multiresolution representation for massive meshes. IEEE Transaction on Visualization and Computer Graphics, 11 (2): 139–148, 2005.
[37] C. Silva, Y.-J. Chiang, W. Correa, J. El-Sana, and P. Lindstrom, Out-of-core algorithms for scientific visualization and computer graphics. IEEE Visualization Course Notes. 2002.
[38] C. Touma and C. Gotsman, Triangle mesh compression. Graphics Interface, 26–34. 1998.
[39] J. Vitter, External memory algorithms and data structures: Dealing with massive data. ACM Computing Surveys, 33 (2): 209–271, 2001.
[40] W. Wulf and S. McKee, Hitting the memory wall: implications of the obvious. ACM SIGARCH Computer Architecture News, 23 (1): 20–24, 1995.
[41] S.-E. Yoon and P. Lindstrom, Mesh layouts for block-based caches. IEEE Transactions on Visualization and Computer Graphics, 12 (5): 1213–1220, 2006.
[42] S.-E. Yoon, P. Lindstrom, V. Pascucci, and D. Manocha, Cache-oblivious mesh layouts. ACM SIGGRAPH, 886–893, 2005.
[43] S.-E. Yoon and D. Manocha, Cache-efficient layouts of bounding volume hierarchies. Computer Graphics Forum, 25 (3): 507–516 2006.
[44] S.-E. Yoon, D. Manocha, P. Lindstrom, and V. Pascucci OpenCCL, 2005. URL http://gamma.cs.unc.edu/COLOpenCCL/.
Index Terms:
Mesh compression, random access, cache-coherent layouts, mesh data structures, external memory algorithms
Citation:
Sung-eui Yoon, Peter Lindstrom, "Random-Accessible Compressed Triangle Meshes," IEEE Transactions on Visualization and Computer Graphics, vol. 13, no. 6, pp. 1536-1543, Nov./Dec. 2007, doi:10.1109/TVCG.2007.70585
PURCHASE ARTICLE: $19
IEEE Xplore Subscribers
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb