“Out-of-core compression for gigantic polygon meshes” by Isenburg and Gumhold

Polygonal models acquired with emerging 3D scanning technology or from large scale CAD applications easily reach sizes of several gigabytes and do not fit in the address space of common 32-bit desktop PCs. In this paper we propose an out-of-core mesh compression technique that converts such gigantic meshes into a streamable, highly compressed representation. During decompression only a small portion of the mesh needs to be kept in memory at any time. As full connectivity information is available along the decompression boundaries, this provides seamless mesh access for incremental in-core processing on gigantic meshes. Decompression speeds are CPU-limited and exceed one million vertices and two million triangles per second on a 1.8 GHz Athlon processor.A novel external memory data structure provides our compression engine with transparent access to arbitrary large meshes. This out-of-core mesh was designed to accommodate the access pattern of our region-growing based compressor, which – in return – performs mesh queries as seldom and as local as possible by remembering previous queries as long as needed and by adapting its traversal slightly. The achieved compression rates are state-of-the-art.

1. ALLIEZ, P., AND DESBRUN, M. 2001. Progressive encoding for lossless transmission of 3D meshes. In SIGGRAPH’01 Conference Proceedings, 198–205. Google Scholar
2. ALLIEZ, P., AND DESBRUN, M. 2001. Valence-driven connectivity encoding for 3D meshes. In Eurographics’01 Conference Proceedings, 480–489.Google Scholar
3. ANN. Version 0.2. A library for approximate nearest neighbor searching by D. Mount and S. Arya. University of Maryland.Google Scholar
4. BAJAJ, C., PASCUCCI, V., AND ZHUANG, G. 1999. Single resolution compression of arbitrary triangular meshes with properties. In Data Compression’99, 247–256. Google Scholar
5. BAR-YEHUDA, R., AND GOTSMAN, C. 1996. Time/space tradeoffs for polygon mesh rendering. ACM Transactions on Graphics 15, 2, 141–152. Google ScholarDigital Library
6. BERNARDINI, F., MARTIN, I., MITTLEMAN, J., RUSHMEIER, H., AND TAUBIN, G. 2002. Building a digital model of michelangelo’s florentine pieta. IEEE Computer Graphics and Applications 22, 1, 59–67. Google ScholarDigital Library
7. CIGNONI, P., MONTANI, C., ROCCHINI, C., AND SCOPIGNO, R. 2003. External memory management and simplification of huge meshes. To appear In IEEE Transactions on Visualization and Computer Graphics. Google Scholar
8. COHEN-OR, D., LEVIN, D., AND REMEZ, O. 1999. Progressive compression of arbitrary triangular meshes. In Visualization’99 Conference Proceedings, 67–72. Google Scholar
9. DEERING, M. 1995. Geometry compression. In SIGGRAPH’95 Conf. Proc., 13–20. Google Scholar
10. GU, X., GORTLER, S., AND HOPPE, H. 2002. Geometry images. In SIGGRAPH’02 Conference Proceedings, 355–361. Google Scholar
11. GUÉZIEC, A., TAUBIN, G., LAZARUS, F., AND HORN, W. 1998. Converting sets of polygons to manifolds by cutting and stitching. In Visualization’98, 383–390. Google Scholar
12. GUÉZIEC, A., BOSSEN, F., TAUBIN, G., AND SILVA, C. 1999. Efficient compression of non-manifold polygonal meshes. In Visualization’99 Conf. Proceedings, 73–80. Google Scholar
13. GUMHOLD, S., AND STRASSER, W. 1998. Real time compression of triangle mesh connectivity. In SIGGRAPH’98 Conference Proceedings, 133–140. Google Scholar
14. HO, J., LEE, K., AND KRIEGMAN, D. 2001. Compressing large polygonal models. In Visualization’01 Conference Proceedings, 357–362. Google Scholar
15. HOPPE, H. 1998. Smooth view-dependent level-of-detail control and its application to terrain rendering. In Visualization’98 Conference Proceedings, 35–42. Google Scholar
16. HOPPE, H. 1999. Optimization of mesh locality for transparent vertex caching. In SIGGRAPH’99 Conference Proceedings, 269–276. Google Scholar
17. ISENBURG, M., AND ALLIEZ, P. 2002. Compressing polygon mesh geometry with parallelogram prediction. In Visualization’02 Conference Proceedings, 141–146. Google Scholar
18. ISENBURG, M., AND SNOEYINK, J. 2000. Face Fixer: Compressing polygon meshes with properties. In SIGGRAPH’00 Conference Proceedings, 263–270. Google Scholar
19. ISENBURG, M. 2002. Compressing polygon mesh connectivity with degree duality prediction. In Graphics Interface’02 Conference Proceedings, 161–170.Google Scholar
20. KARNI, Z., AND GOTSMAN, C. 2000. Spectral compression of mesh geometry. In SIGGRAPH’00 Conference Proceedings, 279–286. Google ScholarDigital Library
21. KHODAKOVSKY, A., SCHROEDER, P., AND SWELDENS, W. 2000. Progressive geometry compression. In SIGGRAPH’00 Conference Proceedings, 271–278. Google ScholarDigital Library
22. KHODAKOVSKY, A., ALLIEZ, P., DESBRUN, M., AND SCHROEDER, P. 2002. Near-optimal connectivity encoding of 2-manifold polygon meshes. Graphical Models 64, 3-4, 147–168. Google ScholarDigital Library
23. KRONROD, B., AND GOTSMAN, C. 2002. Optimized compression of triangle mesh geometry using prediction trees. In Proceedings of International Symposium on 3D Data Processing Visualization and Transmission, 602–608.Google Scholar
24. LEE, E., AND KO, H. 2000. Vertex data compression for triangular meshes. In Proceedings of Pacific Graphics, 225–234. Google Scholar
25. LEE, H., ALLIEZ, P., AND DESBRUN, M. 2002. Angle-analyzer: A triangle-quad mesh codec. In Eurographics’02 Conference Proceedings, 198–205.Google Scholar
26. LEVOY, M., PULLI, K., CURLESS, B., RUSINKIEWICZ, S., KOLLER, D., PEREIRA, L., GINZTON, M., ANDERSON, S., DAVIS, J., GINSBERG, J., SHADE, J., AND FULK, D. 2000. The digital michelangelo project. In SIGGRAPH’00, 131–144. Google ScholarDigital Library
27. LI, J., AND KUO, C. C. 1998. A dual graph approach to 3D triangular mesh compression. In Proceedings of Intern. Conf. on Image Processing ’98, 891–894.Google Scholar
28. LINDSTROM, P., AND SILVA, C. 2001. A memory insensitive technique for large model simplification. In Visualization’01 Conference Proceedings, 121–126. Google Scholar
29. LINDSTROM, P. 2000. Out-of-core simplification of large polygonal models. In SIGGRAPH’00 Conference Proceedings, 259–262. Google ScholarDigital Library
30. MANTYLA, M. 1988. An Introduction to Solid Modeling. Computer Science Press. Google Scholar
31. MCMAINS, S., HELLERSTEIN, J., AND SEQUIN, C. 2001. Out-of-core build of a topological data structure from polygon soup. In Proceedings of the 6th ACM Symposium on Solid Modeling and Applications, 171–182. Google Scholar
32. METI S. Version 4. A software package for partitioning unstructured graphs by G. Karypis and V. Kumar. University of Minnesota.Google Scholar
33. PAJAROLA, R., AND ROSSIGNAC, J. 2000. Compressed progressive meshes. IEEE Transactions on Visualization and Computer Graphics 6, 1, 79–93. Google ScholarDigital Library
34. ROSSIGNAC, J., AND BORREL, P. 1993. Multi-resolution 3d approximation for rendering complex scenes. In Modeling in Computer Graphics, 455–465.Google Scholar
35. ROSSIGNAC, J. 1999. Edgebreaker: Connectivity compression for triangle meshes. IEEE Transactions on Visualization and Computer Graphics 5, 1, 47–61. Google ScholarDigital Library
36. SILVA, C., CHIANG, Y., EL-SANA, J., AND LINDSTROM, P. 2002. Out-of-core algorithms for scientific visualization and computer graphics. In Visualization’02, Course Notes, Tutorial 4.Google Scholar
37. SZYMCZAK, A., ROSSIGNAC, J., AND KING, D. 2002. Piecewise regular meshes: Construction and compression. Graphical Models 64, 3-4, 183–198. Google ScholarDigital Library
38. TAUBIN, G., AND ROSSIGNAC, J. 1998. Geometric compression through topological surgery. ACM Transactions on Graphics 17, 2, 84–115. Google ScholarDigital Library
39. TAUBIN, G., GUÉZIEC, A., HORN, W., AND LAZARUS, F. 1998. Progressive forest split compression. In SIGGRAPH’98 Conference Proceedings, 123–132. Google Scholar
40. TOUMA, C., AND GOTSMAN, C. 1998. Triangle mesh compression. In Graphics Interface’98 Conference Proceedings, 26–34.Google Scholar