com.sun.j3d.utils.geometry.compression
Class HuffmanTable

java.lang.Object
  extended by com.sun.j3d.utils.geometry.compression.HuffmanTable

 class HuffmanTable
extends java.lang.Object

This class maintains a map from compression stream elements (tokens) onto HuffmanNode objects. A HuffmanNode contains a tag describing the associated token's data length, right shift value, and absolute/relative status.

The tags are computed using Huffman's algorithm to build a binary tree with a minimal total weighted path length. The frequency of each token is used as its node's weight when building the tree. The path length from the root to the token's node then indicates the bit length that should be used for that token's tag in order to minimize the total size of the compressed stream.


Field Summary
private  HuffmanNode[] colors
           
private static int MAX_TAG_LENGTH
           
private  HuffmanNode[] normals
           
private  HuffmanNode[] positions
           
 
Constructor Summary
HuffmanTable()
          Create a new HuffmanTable with entries for all possible position, normal, and color tokens.
 
Method Summary
(package private)  void addColorEntry(int length, int shift, boolean absolute)
          Add a color entry with the given length, shift, and absolute status.
private  void addEntry(HuffmanNode[] table, int index, int length, int shift, boolean absolute)
           
private  void addNodeInOrder(java.util.LinkedList l, HuffmanNode node, java.util.Comparator c)
           
(package private)  void addNormalEntry(int length, int shift, boolean absolute)
          Add a normal entry with the given length, shift, and absolute status.
(package private)  void addPositionEntry(int length, int shift, boolean absolute)
          Add a position entry with the given length, shift, and absolute status.
(package private)  void clear()
          Clear this HuffmanTable instance.
(package private)  void computeTags()
          Compute optimized tags for each position, color, and normal entry.
private  void computeTags(java.util.LinkedList nodes, int minComponentCount)
           
private  void expand(java.util.LinkedList nodes, int minComponentCount)
           
(package private)  HuffmanNode getColorEntry(int length, int shift, boolean absolute)
          Get the color entry associated with the specified length, shift, and absolute status.
private  int getColorIndex(int length, int shift, boolean absolute)
           
private  void getEntries(HuffmanNode[] table, java.util.Collection c)
           
private  HuffmanNode getEntry(HuffmanNode[] table, int index)
           
(package private)  HuffmanNode getNormalEntry(int length, int shift, boolean absolute)
          Get the normal entry associated with the specified length, shift, and absolute status.
private  int getNormalIndex(int length, int shift, boolean absolute)
           
(package private)  HuffmanNode getPositionEntry(int length, int shift, boolean absolute)
          Get the position entry associated with the specified length, shift, and absolute status.
private  int getPositionIndex(int len, int shift, boolean absolute)
           
private  void merge(java.util.LinkedList nodes)
           
private  void outputCommands(java.util.Collection nodes, CommandStream output, int tableId)
           
(package private)  void outputCommands(CommandStream output)
          Create compression stream commands for decompressors to use to set up their decompression tables.
(package private)  void print()
          Print the contents of this instance to standard out.
(package private)  void print(java.lang.String header, java.util.Collection nodes)
          Print a collection of HuffmanNode objects to standard out.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

MAX_TAG_LENGTH

private static final int MAX_TAG_LENGTH
See Also:
Constant Field Values

positions

private HuffmanNode[] positions

normals

private HuffmanNode[] normals

colors

private HuffmanNode[] colors
Constructor Detail

HuffmanTable

HuffmanTable()
Create a new HuffmanTable with entries for all possible position, normal, and color tokens.

Method Detail

getPositionIndex

private final int getPositionIndex(int len,
                                   int shift,
                                   boolean absolute)

getNormalIndex

private final int getNormalIndex(int length,
                                 int shift,
                                 boolean absolute)

getColorIndex

private final int getColorIndex(int length,
                                int shift,
                                boolean absolute)

addPositionEntry

void addPositionEntry(int length,
                      int shift,
                      boolean absolute)
Add a position entry with the given length, shift, and absolute status.

Parameters:
length - number of bits in each X, Y, and Z component
shift - number of trailing zeros in each component
absolute - if false, value represented is a delta from the previous vertex in the compression stream

getPositionEntry

HuffmanNode getPositionEntry(int length,
                             int shift,
                             boolean absolute)
Get the position entry associated with the specified length, shift, and absolute status. This will contain a tag indicating the actual encoding to be used in the compression command stream, not necessarily the same as the original length and shift with which the the entry was created.

Parameters:
length - number of bits in each X, Y, and Z component
shift - number of trailing zeros in each component
absolute - if false, value represented is a delta from the previous vertex in the compression stream
Returns:
HuffmanNode mapped to the specified parameters

addColorEntry

void addColorEntry(int length,
                   int shift,
                   boolean absolute)
Add a color entry with the given length, shift, and absolute status.

Parameters:
length - number of bits in each R, G, B, and A component
shift - number of trailing zeros in each component
absolute - if false, value represented is a delta from the previous color in the compression stream

getColorEntry

HuffmanNode getColorEntry(int length,
                          int shift,
                          boolean absolute)
Get the color entry associated with the specified length, shift, and absolute status. This will contain a tag indicating the actual encoding to be used in the compression command stream, not necessarily the same as the original length and shift with which the the entry was created.

Parameters:
length - number of bits in each R, G, B, and A component
shift - number of trailing zeros in each component
absolute - if false, value represented is a delta from the previous color in the compression stream
Returns:
HuffmanNode mapped to the specified parameters

addNormalEntry

void addNormalEntry(int length,
                    int shift,
                    boolean absolute)
Add a normal entry with the given length, shift, and absolute status.

Parameters:
length - number of bits in each U and V component
shift - number of trailing zeros in each component
absolute - if false, value represented is a delta from the previous normal in the compression stream

getNormalEntry

HuffmanNode getNormalEntry(int length,
                           int shift,
                           boolean absolute)
Get the normal entry associated with the specified length, shift, and absolute status. This will contain a tag indicating the actual encoding to be used in the compression command stream, not necessarily the same as the original length and shift with which the the entry was created.

Parameters:
length - number of bits in each U and V component
shift - number of trailing zeros in each component
absolute - if false, value represented is a delta from the previous normal in the compression stream
Returns:
HuffmanNode mapped to the specified parameters

addEntry

private void addEntry(HuffmanNode[] table,
                      int index,
                      int length,
                      int shift,
                      boolean absolute)

getEntry

private HuffmanNode getEntry(HuffmanNode[] table,
                             int index)

getEntries

private void getEntries(HuffmanNode[] table,
                        java.util.Collection c)

clear

void clear()
Clear this HuffmanTable instance.


computeTags

void computeTags()
Compute optimized tags for each position, color, and normal entry.


computeTags

private void computeTags(java.util.LinkedList nodes,
                         int minComponentCount)

merge

private void merge(java.util.LinkedList nodes)

expand

private void expand(java.util.LinkedList nodes,
                    int minComponentCount)

addNodeInOrder

private void addNodeInOrder(java.util.LinkedList l,
                            HuffmanNode node,
                            java.util.Comparator c)

outputCommands

void outputCommands(CommandStream output)
Create compression stream commands for decompressors to use to set up their decompression tables.

Parameters:
output - CommandStream which receives the compression commands

outputCommands

private void outputCommands(java.util.Collection nodes,
                            CommandStream output,
                            int tableId)

print

void print(java.lang.String header,
           java.util.Collection nodes)
Print a collection of HuffmanNode objects to standard out.

Parameters:
header - descriptive string
nodes - Collection of HuffmanNode objects to print

print

void print()
Print the contents of this instance to standard out.



Copyright 1996-2008 Sun Microsystems, Inc. All Rights Reserved. Use is subject to license terms.