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