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 bitrates. 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 5bit 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 ToumaGotsman 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 bitrates 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:
[iacpmgpp02.pdf] Martin Isenburg, Pierre Alliez, Compressing Polygon Mesh Geometry with Parallelogram Prediction, in Proceedings of Visualization 2002, pages 141146, October 2002.
related publications:
[iigsgphdp05.pdf slides] Martin Isenburg, Ioannis Ivrissimtzis, Stefan Gumhold, HansPeter Seidel, Geometry Prediction for High Degree Polygons, Proceedings of SCCG'05, pages 147152, May 2005.
[icpmcddp02.pdf slides] Martin Isenburg, Compressing Polygon Mesh Connectivity with Degree Duality Prediction, Proceedings of Graphics Interface 2002, pages 161170, May 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

# 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 polygonmeshcompressed 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 ARCTeleGeo grant at INRIA, SophiaAntipolis.