“Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition” by Peng and Kuo

  • ©Jingliang Peng and C.-C. Jay Kuo




    Geometry-guided progressive lossless 3D mesh coding with octree (OT) decomposition



    A new progressive lossless 3D triangular mesh encoder is proposed in this work, which can encode any 3D triangular mesh with an arbitrary topological structure. Given a mesh, the quantized 3D vertices are first partitioned into an octree (OT) structure, which is then traversed from the root and gradually to the leaves. During the traversal, each 3D cell in the tree front is subdivided into eight childcells. For each cell subdivision, both local geometry and connectivity changes are encoded, where the connectivity coding is guided by the geometry coding. Furthermore, prioritized cell subdivision is performed in the tree front to provide better rate-distortion (RD) performance. Experiments show that the proposed mesh coder outperforms the kd-tree algorithm in both geometry and connectivity coding efficiency. For the geometry coding part, the range of improvement is typically around 10%~20%, but may go up to 50%~60% for meshes with highly regular geometry data and/or tight clustering of vertices.


    1. Alliez, P., and Desbrun, M. 2001. Progressive encoding for lossless transmission of triangle meshes. In ACM SIGGRAPH, 198–205.]] Google ScholarDigital Library
    2. Alliez, P., and Desbrun, M. 2001. Valence-driven connectivity encoding for 3D meshes. In EUROGRAPHICS, 480–489.]]Google Scholar
    3. Alliez, P., and Gotsman, C. 2003. Recent advance in compression of 3d meshes. In Proceedings of the Symposium on Multiresolution in Geometric Modeling.]]Google Scholar
    4. Attene, M., Falcidieno, B., Spagnuolo, M., and Rossignac, J. 2003. Swingwrapper: Retiling triangle meshes for better edgebreaker compression. ACM Transactions on Graphics 22, 4, 982–996.]] Google ScholarDigital Library
    5. Bajaj, C., Pascucci, V., and Zhuang, G. 1999. Progressive compression and transmission of arbitrary triangular meshes. In IEEE Visualization, 307–316.]] Google ScholarDigital Library
    6. Bajaj, C. L., Pascucci, V., and Zhuang, G. 1999. Single resolution compression of arbitrary triangular meshes with properties. Computational Geometry: Theory and Applications 14, 167–186.]]Google ScholarCross Ref
    7. Botsch, M., Wiratanaya, A., and Kobbelt, L. 2002. Efficient high quality rendering of point sampled geometry. In EGRW ’02: Proceedings of the 13th Eurographics workshop on Rendering, 53–64.]] Google ScholarDigital Library
    8. Cohen-Or, D., Levin, D., and Remez, O. 1999. Progressive compression of arbitrary triangular meshes. In IEEE Visualization, 67–72.]] Google ScholarDigital Library
    9. Coors, V., and Rossignac, J. 2004. Delphi: geometry-based connectivity prediction in triangle mesh compression. The Visual Computer 20, 8–9, 507–520.]] Google ScholarDigital Library
    10. Devillers, O., and Gandoin, P. 2000. Geometric compression for interactive transmission. In IEEE Visualization, 319–326.]] Google ScholarDigital Library
    11. Gandoin, P. M., and Devillers, O. 2002. Progressive lossless compression of arbitrary simplicial complexes. ACM Trans. Graphics 21, 3, 372–379.]] Google ScholarDigital Library
    12. Gotsman, C., Gumhold, S., and Kobbelt, L. 2002. Simplification and compression of 3D meshes. In Tutorials on Multiresolution in Geometric Modelling.]]Google Scholar
    13. Gumhold, S., and Strasser, W. 1998. Real time compression of triangle mesh connectivity. In ACM SIGGRAPH, 133–140.]] Google ScholarDigital Library
    14. Hoppe, H. 1996. Progressive meshes. In ACM SIGGRAPH, 99–108.]] Google ScholarDigital Library
    15. Karni, Z., and Gotsman, C. 2000. Spectral compression of mesh geometry. In ACM SIGGRAPH, 279–286.]] Google ScholarDigital Library
    16. Khodakovsky, A., and Guskov, I. 2000. Normal mesh compression. Preprint.]]Google Scholar
    17. Khodakovsky, A., Schröder, P., and Sweldens, W. 2000. Progressive geometry compression. In ACM SIGGRAPH, 271–278.]] Google ScholarDigital Library
    18. Laney, D., Bertram, M., Duchaineau, M., and Max, N. 2002. Multiresolution distance volumes for progressive surface compression. In Proceedings of the First International Symposium on 3D Data Processing, Visualization, and Transmission, 470–479.]]Google Scholar
    19. Lee, H., Desbrun, M., and Schröder, P. 2003. Progressive encoding of complex isosurfaces. In ACM SIGGRAPH.]] Google ScholarDigital Library
    20. Li, J., and Kuo, C.-C. J. 1998. Progressive coding of 3-D graphic models. Proceedings of the IEEE 86, 6 (Jun), 1052–1063.]] Google ScholarDigital Library
    21. Pajarola, R., and Rossignac, J. 2000. Compressed progressive meshes. IEEE Trans. Visualization and Computer Graphics 6, 1, 79–93.]] Google ScholarDigital Library
    22. Peng, J., Kim, C.-S., and Kuo, C.-C. J. Technologies For 3D mesh compression: A survey, to appear in Journal of Visual Communication and Image Representation.]] Google ScholarDigital Library
    23. Popovic, J., and Hoppe, H. 1997. Progressive simplicial complexes. In ACM SIGGRAPH, 217–224.]] Google ScholarDigital Library
    24. Rossignac, J., and Borrel, P. 1993. Geometric Modeling in Computer Graphics. Springer-Verlag, Jul.]]Google Scholar
    25. Rossignac, J. 1999. Edgebreaker: Connectivity compression for triangle meshes. IEEE Trans. Visualization and Computer Graphics 5, 1, 47–61.]] Google ScholarDigital Library
    26. Saupe, D., and Kuska, J.-P. 2001. Compression of isosurfaces for structured volumes. In Proceedings of Vision, Modeling and Visualization, 333–340.]] Google ScholarDigital Library
    27. Schmalstieg, D., and Schaufler, G. 1997. Smooth levels of detail. In IEEE Virtual Reality Annual International Symposium, 12–19.]] Google ScholarDigital Library
    28. Szymczak, A., Rossignac, J., and King, D. 2002. Piecewise regular meshes: construction and compression. Graphical Models 64, 3/4, 183–198.]] Google ScholarDigital Library
    29. Taubin, G., and Rossignac, J. 1998. Geometric compression through topological surgery, ACM Trans. Graphics 17, 2, 84–115.]] Google ScholarDigital Library
    30. Taubin, G., Gueziec, A., Horn, W., and Lazarus, F. 1998. Progressive forest split compression. In ACM SIGGRAPH, vol. 32, 123–132.]] Google ScholarDigital Library
    31. Touma, C., and Gotsman, C. 1998. Triangle mesh compression. In Proceedings of Graphics Interface, 26–34.]]Google Scholar

ACM Digital Library Publication:

Overview Page: