Compressing Polygon Mesh Geometry with Parallelogram Prediction

Martin Isenburg            Pierre Alliez

abstract:
In this paper we present a prediction scheme for efficient compression of the vertex positions of a polygonal mesh. We provide a prototype implementation of the decoder in pure Java that proves the reported bit-rates. The tommygun model shown below has just been decompressed on the fly in your browser. The geometry was decoded from (a) an array of 51936 zeros and ones, (b) six floating point values, and (c) one 5-bit integer value. This data can be represented with 51936 + 6*32 + 5 = 52133 bits or 6517 bytes. This is an improvement of 36 percent in geometry compression over the Touma-Gotsman scheme at the same quantization level (12 bits). Our prediction scheme is not more complex than that of Touma and Gotsman ... but we do not triangulate the polygons, instead we use this additional information for better predictions.

Note that for purely triangular models (e.g. the cow) we get roughly the same bit-rates as the Touma and Gotsman coder. This validates that our improvement really comes from using the polygonal information.


press SHIFT to translate and CTRL to zoom

publication:
[ia-cpmgpp-02.pdf] Martin Isenburg, Pierre Alliez, Compressing Polygon Mesh Geometry with Parallelogram Prediction, in Proceedings of Visualization 2002, pages 141-146, October 2002.

related publications:

  • [iigs-gphdp-05.pdf slides] Martin Isenburg, Ioannis Ivrissimtzis, Stefan Gumhold, Hans-Peter Seidel, Geometry Prediction for High Degree Polygons, Proceedings of SCCG'05, pages 147-152, May 2005.
  • [i-cpmcddp-02.pdf slides] Martin Isenburg, Compressing Polygon Mesh Connectivity with Degree Duality Prediction, Proceedings of Graphics Interface 2002, pages 161-170, May 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 # polygons PMC (bytes) TMC (bytes) gain (%) link
    conn geom conn geom conn geom total
    triceratops 2832 2835 422 5226 767 7095 45.0 26.3 28.2 link
    cessna 3745 2372 1190 5856 1145 8943 -3.9 34.5 30.2 link
    sandal 2636 2953 697 5253 699 6709 0.3 21.7 19.7 link
    shark 2560 2562 242 3384 484 5703 50.0 40.7 41.4 link
    al 3618 4175 1099 8997 952 10344 -15.4 13.0 10.6 link
    tommygun 4171 3980 1178 6517 1077 10197 -9.4 36.4 31.7 link
    cow 2904 5804 647 7487 682 7397 5.1 -1.1 -0.7 link
    teapot 1189 1290 168 2387 151 3090 -11.3 22.8 21.2 link

    The above table lists the compression rates of our Polygon Mesh Compressor (PMC) in bytes and compares them to those of the Triangle Mesh Compressor (TMC) by Touma & Gotsman. The improvement in compression is reported in percent. The exact bit counts can be verified by following the demo links to an interactive online implementation of the decoder.

    The demo links bring you to a java implementation of the decoder, that will decode the corresponding mesh on the fly from the compressed representation. You can actually "look" at the bits produced by our Polygon Mesh Compressor: 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 mymodel directory. You may also open the java console to read the decoding control output of decoder.

    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 PolygonMeshCompressedIndexedFaceSet {
            code_conn [ 0 0 0 0 1 0 0 0 1 ...... 1 0 1 0 1 1 1 0 0 1 ]
            code_geom [ 1 1 1 1 1 0 1 1 0 0 0 0 ...... 0 1 1 1 0 1 0 1 0 1 1 1 ]
            bounding_box [ -10.29977798 -3.69169402 -2.91280293 7.41632795 4.06365108 2.94422793 ]
            precision_bits 12
            }
        }
    }

    This is actually the polygon-mesh-compressed triceratops model. The code_conn field contains the bits that are the compressed connectivity of the triceratops model. The connectivity is compressed using degree duality coding. The code_geom field contains the bits that are the compressed geometry of the triceratops model. The geometry is compressed using the proposed geometry compression scheme for polygon meshes. In addition to these bits the decoder uses the six floats of the bounding_box field (that specify the [xmin,ymin,zmin,xmax,ymax,zmax] of the bounding box) and the small integer of the precision_bits field (that specifies the number of bits used for quantization of vertex coordinates). A java implementation of the decoder decompresses the mesh 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 PolygonMeshCompressedIndexedFaceSet {
            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 ]
        }
    }

    download:

  • slides: cpmgpp.ppt
  • demos
  • models
  • this algorithm is implemented in the benchmark coder
  • funding:

  • This work was partly supported by the ARC-TeleGeo grant at INRIA, Sophia-Antipolis.