CS 101.3 Spring 2002

Homework 2

Due: April 29^th 11:59pm

Implement the T&G valence encoder/decoder pair.

You program should work for a closed 2-manifold mesh of a single connected component, which is orientable. We will provide sample inputs and will test your program only on meshes that satisfy these criteria.

Your encoder should write out two files, one with the connectivity information, the other with the geometry information (needless to say your decoder should be able to read these files and successfully reconstruct the original mesh). The encoder should take as an argument the quantization level to be applied to vertices prior to coding. The decoder will of course only reconstruct the quantized version. The connectivity of the decoded mesh will be isomorphic to the connectivity of the original mesh, though in general not have identical enumeration (why?). Your coder should however be idempotent. That is, if you encode and decoded mesh again and decode once more that firstly and secondly decoded meshes should now be identical. Test this...

For the former the format should be a stream of integers in ASCII format separated by whitespace. All numbers 3 and higher are valences, while the number 1 is reserved for the SPLIT symbol. The split symbol is followed by two additional integers which indicate the position of the split vertex in your active vertex data structure (hint: this will likely be an index counting from the top of a stack or some such [there are many different ways of doing this, but giving an index for a linked list is not such a terrific idea...]) as well as the index of the triangle which was just conquered IN THE RING OF TRIANGLE NEIGHBORS OF THE SPLIT VERTEX. Note that T&G maintain explicit edge lists and have to worry about explicit management of splits of such lists and merges of such lists (with a stack of such lists). Yuck. Think about this. There is no need for this. In fact, there is no need to distinguish between

SPLIT and MERGE (which explains why we only define a SPLIT code).

Furthermore, while they follow the split symbol with an index in the active vertex data structure they do not mention the second index, namely where the just conquered triangle sits within the triangle neighbor ring of the split vertex. This is not necessary, but will make your coding life much easier. It will also avoid additional split messages later (why? think about this! if you can't answer this question for yourself you do not understand the algorithm well enough yet...).

We will provide a program which will take such a white space delimited ascii stream and turn it into an arithmetically coded bit representation (only for the connectivity part) and vice versa.

Compression of the geometry should be performed as follows: for a given bit budget, renormalize the geometry into a bounding box of that size (i.e. for 10 bits, use a bounding box 1024x1024x1024). Then truncate all float values to the closest integer in this bounding box. Your program should be able to handle various bit budgets (either taken on the command line or as an input text box). Write out the compressed geometry (as integers) to its own file with every vertex comma separated.

Extra points will be given for programs which can take as input meshes with boundaries and reconstruct on the decoding side the same boundaries (hint: insert a dummy vertex to close all boundaries and send an extra message to the decoder to tell it which vertices are dummy).

The coder which achieves the smallest bit budget for the connectivity on some sample meshes wins additional points.