Geometry Prediction for High Degree Polygons

Martin Isenburg      Ioannis Ivrissimtzis      Stefan Gumhold      Hans-Peter Seidel

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 to compress the vertex positions of triangular meshes. Later, we 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 for hexahedral volume mesh elements.

main contributions:

  • extending the parallelogram rule to higher degree polygons
  • using polygonal Fourier decomposition for designing the predictor
  • giving existing prediction rules a retroactive theoretic blessing

  • 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.
  • 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.
  • [ils-lcpfpg-05.pdf slides] Martin Isenburg, Peter Lindstrom, Jack Snoeyink, Lossless Compression of Predicted Floating-Point Geometry, in Computer-Aided Design, Volume 37, Issue 8, pages 869-877, July 2005.


  • slides: gphdp.ppt (6 MB)
  • funding:

  • Max Planck Center for Visual Computing and Communication, Saarbruecken, Germany.