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 vertexbased 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 lowdegree vertices are likely to be surrounded by highdegree 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 bitrates. 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 bitrate 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 "nearoptimal 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 (contextsensitive) 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:
[icpmcddp02.pdf] Martin Isenburg, Compressing Polygon Mesh Connectivity with Degree Duality Prediction, in Proceedings of Graphics Interface 2002, pages 161170, May 2002.
downloads:
slides: cpmcddp.ppt (11 MB)
demos: demos
models: models
this algorithm is implemented in the benchmark coder
related publications:
[iacpmgpp02.pdf slides] Martin Isenburg, Pierre Alliez, Compressing Polygon Mesh Geometry with Parallelogram Prediction, in Proceedings of Visualization 2002, pages 141146, October 2002.
[iachvm02.pdf slides], Martin Isenburg, Pierre Alliez, Compressing Hexahedral Volume Meshes, Proceedings of Pacific Graphics 2002, pages 284293, October 2002.
results and proofofconcept implementation:
models

# vertices

# codebits

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 nonmanifold vertex which is correctly reconstructed by our decoder. The bitrate 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 ]
}
}