Optimized triangle mesh compression using prediction trees

B. Kronrod, C. Gotsman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


Recently, a wealth of algorithms for the efficient coding of 3D triangle meshes have been published. All these focus on achieving the most compact code for the connectivity data. The geometric data, i.e. the vertex coordinates, are then coded in an order induced by the connectivity code, which is probably not optimal. This is a pity, as the geometric portion of the data set dominates the code. We propose a way to optimize the geometry code without sacrificing too much in the connectivity code. In our approach, we achieve approximately two bits/triangle for the connectivity before entropy coding, which is not as good as other published algorithms but certainly not significantly worse. Our approach is based on the parallelogram prediction method for mesh geometry. This method is based on the observation that two adjacent triangles in a typical mesh tend to form a shape similar to a parallelogram. If an algorithm uses a parallelogram prediction method then it should build a traversal structure of triangles covering all vertices. The vertex coordinates are then predicted as the structure is traversed. The cost of this code is then the entropy of the distribution of the vertex prediction errors. Since this entropy is hard to manipulate, the accepted practice is to measure the code's effectiveness in the approximation sense, i.e. as the sum of the lengths of the vertex prediction error vectors. The full version of this paper is available at 'http://www.cs.technion.ac.il/~gotsman/pubs/kronrod1.zip'.

Original languageEnglish (US)
Title of host publicationProceedings - 8th Pacific Conference on Computer Graphics and Applications, PG 2000
EditorsBrian A. Barsky, Yoshihisa Shinagawa, Wenping Wang
PublisherIEEE Computer Society
Number of pages2
ISBN (Electronic)0769508685
StatePublished - 2000
Externally publishedYes
Event8th Pacific Conference on Computer Graphics and Applications, PG 2000 - Hong Kong, China
Duration: Oct 3 2000Oct 5 2000

Publication series

NameProceedings - Pacific Conference on Computer Graphics and Applications
ISSN (Print)1550-4085


Other8th Pacific Conference on Computer Graphics and Applications, PG 2000
CityHong Kong

All Science Journal Classification (ASJC) codes

  • Software
  • Computer Graphics and Computer-Aided Design
  • Modeling and Simulation


  • Computer science
  • Costs
  • Decoding
  • Design optimization
  • Entropy coding
  • Geometry
  • Length measurement
  • Prediction methods
  • Shape
  • Tree graphs


Dive into the research topics of 'Optimized triangle mesh compression using prediction trees'. Together they form a unique fingerprint.

Cite this