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

  • ©Martin Isenburg and Stefan Gumhold




    Out-of-core compression for gigantic polygon meshes



    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

ACM Digital Library Publication: