> Date: Tue, 10 Jun 2003 13:02:23 +0200 > From: Karsten Wutzke <[EMAIL PROTECTED]> > > I'm delving into geometry compression for a university seminar. But I > still have some problems understanding the variation a the Huffman > coding used.
The source code for the GeometryCompressor utility class is available with the Java 3D SDK -- you'll probably find the answers to most of your questions there. > 1. Huffman coding takes a set of symbols as input to build up the tree. > What are these symbols in geometry compression? Are these just the > deltas between successive vertices/colors/normals that are compared? No, these symbols just describe the format of the immediately following data, in terms of data length, right shift, and absolute/relative status from the preceding data. The Huffman algorithm is used to assign the shortest symbol lengths to those symbols that occur most frequently. So, for example, if the data contains 1000's of entities 5 bits long and only a couple that are 16 bits long, then the Huffman tag to describe the former may be as short as 1 bit, while the latter tag might be 10 bits long. The Java 3D geometry compression process is designed to be decompressed by hardware however, so the Huffman table is limited to 64 entries, for a maximum tag length of 6 bits; if the tag length is longer, then the symbols must be merged until there are no more than 64. > If so, are these XY(Z) or RGB(A) deltas histogrammed independently? Positions, colors, and normals are histogrammed independently and use three separate Huffman tables for a total of 192 Huffman table entries. This was found to be more efficient than a single Huffman table due to the differences in how positions, colors, and normals are encoded. See HuffmanNode.java and HuffmanTable.java in the compressor package. > 2. If I understand it correctly, the final bit stream is a combination > of fixed-length geometry instruction opcodes plus variable length > Huffman codes "inside" the setVertex, setColor and setNormal > instructions??? <- THE question! Yes. The opcode is in a fixed-length header 8 bits long. The first 2 bits determine whether it's a vertex, color, or normal. The next 6 bits contain the Huffman tag and possibly part of the data. You don't know how many bits of those 6 are the tag and how much are the data until you use those 6 bits to index into the Huffman table. For example, if those 6 bits are 110101, you look up entry 53 in the appropriate table, and you might find that the tag is 3 bits long (110) and the data is 10 bits long, the first 3 of which (101) are actually at the end of 6 bits you used to index the table. Then you would read 7 more bits from the stream to complete the data. So setting up those self-describing tables is the tricky part. A 1-bit tag is a short descriptor but takes up 32 entries in the table, so the other descriptors have to be less efficient in describing the data. That's where the Huffman algorithm for minimal weighted trees comes in: a 1-bit tag is only created if it's worth it based on the statistical distribution of data lengths. > 3. What is the variation in contrast to classic Huffman made up of? > The header forwarding? The fact, that the Huffman codes represent > Deltas inside instructions and not the whole instruction? Not sure what you mean by "classic Huffman". His algorithm basically computes trees with minimal weighted path lengths. There are lots of applications, such as arranging the order of conditional tests in code, in addition to compression. I would say the most novel feature of the Java 3D geometry compression is the compression of normals from 3 32-bit quantities (96 bits total) to 3 6-bit quanties (sextant/octant plus U and V for 18 bits total) without apparent loss of visual quality. The rest is just quantization, delta encoding, and clever self-describing data structures. > 4. How is the final bit stream composed? Just as a concatenation? It's basically a concatenation of the commands, with the 8-bit headers forwarded ahead of the command bodies by one command in an interleaved fashion. The header forwarding is there to make an efficient hardware implementation possible. There is also some fairly complicated no-op padding at the end of the stream to align it to 64-bit word boundaries. > I'm referring to this article, chapter B.9: > http://java.sun.com/products/java-media/3D/1_2_api/j3dguide/AppendixCompress.doc.html See also Michael Deering's original paper in the 1994 SIGGRAPH Proceedings. -- Mark Hood =========================================================================== To unsubscribe, send email to [EMAIL PROTECTED] and include in the body of the message "signoff JAVA3D-INTEREST". For general help, send email to [EMAIL PROTECTED] and include in the body of the message "help".
