Compressing Polygon Mesh Connectivity with Degree Duality Prediction

Martin Isenburg

abstract:
In this paper we present a coder for polygon mesh connectivity that delivers the best connectivity compression rates meshes reported so far. Our coder is an extension of the vertex-based coder for triangle mesh connectivity by Touma and Gotsman and borrows ideas from a paper by Alliez and Desbrun. We code polygonal connectivity as a sequence of face and vertex degrees and exploit the correlation between them for mutual predictive compression. Because low-degree vertices are likely to be surrounded by high-degree faces and vice versa, we predict vertex degrees based on neighboring face degrees and we predict face degrees based on neighboring vertex degrees. Furthermore, we provide a prototype implementation of the decoder in pure Java that proves the reported bit-rates. The connectivity of the cupie model shown below has just been decoded on the fly from exactly 4894 bits. This model has 2984 vertices which gives the reported bit-rate of 1.640 bpv (bits per vertex).


press SHIFT to translate and CTRL to zoom

A similar algorithm was developed independently and during the same time period by Khodakovsky (CalTech), Alliez (USC), Desbrun (USC), and Schroeder (CalTech). Their "near-optimal connectivity encoding" algorithm is based on the same basic idea as the one proposed here. However, there are several differences. One major difference is how the information generated by the encoder is put into a symbols stream and how this symbol stream is conditioned for subsequent (context-sensitive) entropy coding. While we propose a mutual prediction of vertex and face degrees, they predict face degrees from neighboring face degrees. Our compression rates are between 7 and 15 percent better than those reported in the preprint of their paper.

publication:

  • [i-cpmcddp-02.pdf] Martin Isenburg, Compressing Polygon Mesh Connectivity with Degree Duality Prediction, in Proceedings of Graphics Interface 2002, pages 161-170, May 2002.
  • downloads:

  • slides: cpmcddp.ppt (11 MB)
  • demos: demos
  • models: models
  • this algorithm is implemented in the benchmark coder
  • related publications:

  • [ia-cpmgpp-02.pdf slides] Martin Isenburg, Pierre Alliez, Compressing Polygon Mesh Geometry with Parallelogram Prediction, in Proceedings of Visualization 2002, pages 141-146, October 2002.
  • [ia-chvm-02.pdf slides], Martin Isenburg, Pierre Alliez, Compressing Hexahedral Volume Meshes, Proceedings of Pacific Graphics 2002, pages 284-293, October 2002.
  • results and proof-of-concept implementation:
    models # vertices # code-bits FF (bpv) DD (bpv) gain demo
    triceratops 2832 3368 2.115 1.189 43.8 % link
    galleon (*) 2372 4965 2.595 2.093 19.3 % link
    cessna 3745 9523 2.841 2.543 10.5 % link
    beethoven 2655 5582 2.890 2.102 27.3 % link
    sandal 2636 5576 2.602 2.115 18.7 % link
    shark 2560 1936 1.670 0.756 54.7 % link
    al 3618 8787 2.926 2.429 17.0 % link
    cupie 2984 5170 2.307 1.640 28.9 % link
    tommygun 4171 9418 2.611 2.258 13.5 % link
    cow 2904 5172 2.213 1.781 19.5 % link
    teapot 1189 1340 1.669 1.127 32.5 % link

    (*) The galleon model has one non-manifold vertex which is correctly reconstructed by our decoder. The bit-rate reported for the Face Fixer coder does not include this information.

    The above table list the compression rates of our Degree Duality coder (DD) in bits per vertex (bpv) and compares them to those of the Face Fixer coder (FF). The improvement in compression is reported in percent. We also list the vertex counts and the exact code bit count for each model. These exact bit counts can be verified by following the demo links to an interactive online implementation of our decoder.

    The demo links bring you to a java implementation of the decoder, that will decode the corresponding mesh on the fly from a the degree duality coded representation. You can actually "look" at the bits produced by our degree duality coder: We store the bits (only for this educational purpose) in textual representation in a Shout3D scene description file (*.s3d). You can download the source of each scene description file from the corresponding page or you find all of them in this model directory. You may also open the java console to read the decoding control output of degree duality coder.

    If you read the *.s3d scene desription files in a text editor you will see the following:

    Shape {
        appearance Appearance {
            material Material {
                diffuseColor 1 1 0
            }
        }
        geometry DegreeDualityCodedIndexedFaceSet {
            coord Coordinate {
                point [ -4.7117 -2.7333 -3.2484 ...... -9.0756 0.8488 0.0492 ]
            }
            code [ 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1 ...... 1 0 1 1 0 0 0 1 1 ]
        }
    }


    This is actually the degree duality coded galleon model. The coord field contains 3 floats for the three coordinates of each vertex position in the order implied by the connectivity decoder. This is the (uncompressed) geometry of the galleon mesh. The code field contains the bits produced by the arithmetic coder. Their number is reported in the table above. This is the (compressed) connectivity of the galleon mesh. A java implementation of the degree duality coder decompresses the mesh connectivity on the fly, thereby creating a proper instance of an IndexedFaceSet node that can be rendered by Shout3D's pure Java renderer which we use for visualization. After decoding it will contain the following information:

    Shape {
        appearance Appearance {
            material Material {
                diffuseColor 1 1 0
            }
        }
        geometry DegreeDualityCodedIndexedFaceSet {
            coord Coordinate {
                point [ -4.7117 -2.7333 -3.2484 ...... -9.0756 0.8488 0.0492 ]
            }
            coordIndex [ 0 1 2 3 -1 2 ...... 4577 -1 2367 2370 2371 -1 ]
        }
    }