Geometry prediction for high degree polygons

ABSTRACT

The parallelogram rule is a simple, yet effective scheme to predict the position of a vertex from a neighboring triangle. It was introduced by Touma and Gotsman [1998] to compress the vertex positions of triangular meshes. Later, Isenburg and Alliez [2002] showed that this rule is especially efficient for quad-dominant polygon meshes when applied "within" rather than across polygons. However, for hexagon-dominant meshes the parallelogram rule systematically performs miss-predictions.In this paper we present a generalization of the parallelogram rule to higher degree polygons. We compute a Fourier decomposition for polygons of different degrees and assume the highest frequencies to be zero for predicting missing points around the polygon. In retrospect, this theory also validates the parallelogram rule for quadrilateral surface mesh elements, as well as the Lorenzo predictor [Ibarria et al. 2003] for hexahedral volume mesh elements.

References

1. Berlekamp, E., Gilbert, E., and Sinden, F. 1965. A polygon problem. Amer. Math. Monthly 72, 233--241.]]
2. Chazelle, B. 2000. The Discrepancy Method --- Randomness and Complexity. Cambridge University Press.]]
3. Cohen-Or, D., Cohen, R., and Irony, R. 2002. Multi-way geometry encoding. Tech. rep., Computer Science, Tel Aviv University.]]
4. Coors, V., and Rossignac, J. 2004. Delphi: Geometry-based connectivity prediction in triangle mesh compression. The Visual Computer 20, 8-9, 507--520.]]
5. Davis, P. 1979. Circulant matrices. Wiley-Interscience.]]
6. Devillers, O., and Gandoin, P.-M. 2002. Progressive and lossless compression of arbitrary simplicial complexes. In SIGGRAPH'02 Conference Proceedings, 372--379.]]
7. Ibarria, L., Lindstrom, P., Rossignac, J., and Szymczak, A. 2003. Out-of-core compression and decompression of large n-dimensional scalar fields. In Eurographics'03 Proceedings, 343--348.]]
8. Isenburg, M., and Alliez, P. 2002. Compressing polygon mesh geometry with parallelogram prediction. In Visualization'02 Conference Proceedings, 141--146.]]
9. Isenburg, M., and Gumhold, S. 2003. Out-of-core compression for gigantic polygon meshes. In SIGGRAPH'03 Proceedings, 935--942.]]
10. Isenburg, M., and Snoeyink, J. 2000. Face Fixer: Compressing polygon meshes with properties. In SIGGRAPH'00 Proceedings, 263--270.]]
11. Isenburg, M., and Snoeyink, J. 2005. Early-split coding of triangle mesh connectivity. manuscript.]]
12. Isenburg, M. 2002. Compressing polygon mesh connectivity with degree duality prediction. In Graphics Interface'02 Proceedings, 161--170.]]
13. Kälberer, F., Polthier, K., Reitebuch, U., and Wardetzky, M. 2005. Freelence: Compressing triangle meshes using geometric information. to appear in Eurographics'05 Proceedings, September 2005.]]
14. Karni, Z., and Gotsman, C. 2000. Spectral compression of mesh geometry. In SIGGRAPH'00 Conference Proceedings, 279--286.]]
15. Khodakovsky, A., Schroeder, P., and Sweldens, W. 2000. Progressive geometry compression. In SIGGRAPH'00 Proceedings, 271--278.]]
16. Khodakovsky, A., Alliez, P., Desbrun, M., and Schroeder, P. 2002. Near-optimal connectivity encoding of 2-manifold polygon meshes. Graphical Models 64, 3-4, 147--168.]]
17. Kronrod, B., and Gotsman, C. 2002. Optimized compression of triangle mesh geometry using prediction trees. In International Symposium on 3D Data Processing Visualization and Transmission, 602--608.]]
18. Lee, H., Alliez, P., and Desbrun, M. 2002. Angle-analyzer: A triangle-quad mesh codec. In Eurographics'02 Proceedings, 198--205.]]
19. Shikhare, D., Bhakar, S., and Mudur, S. 2001. Compression of 3D engineering models using automatic discovery of repeating geometric features. In Proc. of Vision Modeling and Visualization'01, 233--240.]]
20. Sorkine, O., Cohen-Or, D., and Toledo, S. 2003. High-pass quantization for mesh encoding. In Proceedings of Symposium on Geometry Processing'03, 42--51.]]
21. Surazhsky, V., Alliez, P., and Gotsman, C. 2003. Isotropic remeshing of surfaces: a local parameterization approach. In Proceedings of 12th International Meshing Roundtable, 215--224.]]
22. Touma, C., and Gotsman, C. 1998. Triangle mesh compression. In Graphics Interface'98 Conference Proceedings, 26--34.]]
23. Witten, I. H., Neal, R. M., and Cleary, J. G. 1987. Arithmetic coding for data compression. Communications of the ACM 30, 6, 520--540.]]