UCT CS Research Document Archive

Distance ranked connectivity compression of triangle meshes

Marais, Patrick and James Gain (2005) Distance ranked connectivity compression of triangle meshes. Technical Report CS05-01-00, Department of Computer Science, University of Cape Town.

Full text available as:
PDF - Requires Adobe Acrobat Reader or other PDF viewer.


We present a new, single-rate method for compressing the connectivity information of a 2-manifold triangle mesh with or without boundary. Traditional compression schemes interleave geometry and connectivity coding, and are thus unable to utilise information from vertices (mesh regions) they have not yet processed. With the advent of competitive point cloud compression schemes, it has become feasible to develop separate connectivity encoding schemes which can exploit complete, global vertex position information to improve performance.

Our scheme demonstrates the utility of this separation of vertex and connectivity coding. By traversing the mesh edges in a consistent breadth-first fashion, and using global vertex information, we can predict the position of the vertex which completes the unprocessed triangle attached to a given edge. We then rank the vertices in the neighbourhood of this predicted position by their Euclidean distance. The distance rank of the correct closing vertex is stored. Typically, these rank values are small, and the sequence of rank values thus possesses low entropy and compresses very well. The paper details the algorithm as well as the predictors we have tested. Results indicate improvement on the current best valence-based schemes for many common mesh classes.

EPrint Type:Departmental Technical Report
Keywords:triangle mesh, connectivity compression, geometry driven coding
Subjects:I Computing Methodologies: I.3 COMPUTER GRAPHICS
I Computing Methodologies: I.m MISCELLANEOUS
ID Code:200
Deposited By:Marais, Patrick
Deposited On:22 March 2005