#flipcode

Image by <a href=mailto:"bored_and_dangerous2003@yahoo.com">Conor Stokes aka DirtyPunk</a><br/>Posted 2005-10-15<br/><br/><img src="galleria/fullsize/conor_stokes_meshc_untextured.PNG"/><h1>Description</h1><br/><p>This is a screenshot directly from one of my last semester projects from uni

(way back in 2003). It was a full mesh compression system. While the system

supports textured models, I think these high resolution untextured models have a

bit more character (In other words, the textured models were programmer

art).</p>

<p> The abbreviations "VL" and "VA" refer to being visually the same to casual

viewing or visually

acceptable to casual viewing.

The method used to compress combines a simple vertex compression system with a

much more complex

connectivity (triangle) compression system.</p>

<p>The mesh compression is based on Gumhold's Cut Border Machine, but modified to

use different operators (mainly so I don't need to keep track of border rings).

I use no union operator, but the connect forwards/back operator has a least bit

representation to choose from multiple options (least bits is 0 when only a

single choice can be made). Also, least bits is used for stack indexing with the

connect general operator. Fixed huffman codes are used to represent operators.

My variant out performs cut-border by about 2x speedwise due to the changes,

while being slightly better for compression.

</p>

<p>I also implement a "feature edge" prefix operator code for texturing, which

picks up where there is a break between surface coordinates (texture/normal) but

not position coordinates.</p>

<p>With constant Huffman codes, I get around 1.4 bits a triangle in terms of

connectivity information (better than the 96 used for 3 indices :).</p>

<p>Because the algorithm produces a vertex order (vertices in the stream are

instanced with a "new vertex" operator) and the triangle across from the vertex

is guaranteed to exist, this can be used to make a delta predictor (I use a

parallelogram extension of the triangle as a predictor). I then use <br>

a "least bits" over a run of delta encoded vertices (which have first been

quantitised with a saved transform) for entropy encoding - it's not as size<br>

efficient as Huffman, but it's a lot faster for vertices.</p>

<p>Texture coordinates are encoded in a similar way (as are normals, with a

different predictor - although, in many of the display models, I just flag to

calculate normals).</p>

<p>The algorithm is very fast for both compression and decompression - it takes

under a second to compress or decompress the Happy Buddha model, even though it

is over a million polygons.</p>