Geometry Compression of Polygonal Models Using Topologically-Assisted Coding Methods



 
 

Computer Graphics is a growing field.  We see its effects in commercials, movies, and television shows.  However, with all the recent interest and advances in computer graphics, a need has developed for compression of 3-D objects. This is because these 3-D objects can be composed of millions of polygons, which take up inordinate amounts of storage space.  These files can also take a long time to transmit over the Internet due to limited bandwidth.  As a result, my research worked on addressing these issues.

My research consisted of using Gabriel Taubin and Jarek Rossignac et al's Topological Surgery method as a basis.  This method consists of incrementally layering a model, in an effort to create triangle strips - one of the most efficient methods to render a set of triangles.  Once layered, a vertex and triangle tree are created for a model, providing structures for geometric information for a mesh.  The vertex tree is a structure which includes each vertex of the model once.  Similarly, the triangle tree is a structure which includes each triangle of the mesh once.  Therefore, each model has its own set of fixed information (such as the number of triangles, number of vertices, etc.), geometry information (the makeup of the model) and position information (the positioning of the geometry in 3-space).  The fixed size information, stored in a binary format and concatenated together, can then be arithmetically encoded in an effort to reduce its size.  The geometry information is compressed using an entropy encoding technique - arithmetic encoding, while the position information can be compressed using two methods.

The first method for compression of the position information consists of using linear prediction based on vertex positions within the vertex tree.  In the original mesh, the actual vertex positions are stored to their full 32-bit floating point accuracy.  However, such precision is not necessarily a requirement.  8 to 16-bit accuracy of vertex positions has been shown to be adequate replacements for most models.  Fortunately, the vertex tree provides a nice structure for the use of linear prediction.  In other words, each vertex, except the root of the vertex tree, has ancestors associated with them.  Therefore, one can predict where a vertex position will be - based upon the position of its unique ancestors.  Furthermore, since error values (resultant from the difference in actual and predicted vertex positions) are usually of smaller magnitude than the actual positions, error values are stored instead of the predicted values (along with the linear prediction parameters).  These resultant errors, integer values, are concatenated to gether based upon a pre-order traversal of the vertex tree and then arithmetically encoded and placed at the end of the compressed file.  Since the root of the vertex tree is stored to its full accuracy, one can then reproduce the rest of the vertex positions by simply reversing the process.

The second method is an interesting one.  While linear prediction followed by arithmetic encoding is a proven method, we were searching for a more unique approach.  This method consists of treating the vertex positions as a 2-D image.  This was done because in recent years, much research and advances in image compression have arisen.  Therefore, we wondered if we could somehow use existing methods in a different manner, in an effort to achieve good compression ratios, without much loss of information.  The technique used is SLCCA, an algorithm designed and developed at the University of MO - Columbia.  While the results were not as good as we had hoped for, there is promise for this method, and further research into this method is ongoing.

The following links provide more information about their respective titles.  To view them, simply click on the desired underlined text.

    For more information on the Vertex Tree.

    For more information on the Triangle Tree.

    For more information on Linear Prediction.

    For more information on the SLCCA method.

    To view instructions on cmesh and how to compress/decompress a model using cmesh, click on Instructions.

    The results of this implementation can be found by clicking on RESULTS.

    To determine where cmesh and other downloaded compression routines can be found on the Multimedia Lab's meru server, click Here.

    For Links to other helpful sites, click Here.
 
 
 

If you have any questions or comments, email me at scottm@meru.cecs.missouri.edu