com.davisor.graphics
Class OctreeColorReducer.ColorTree

java.lang.Object
  com.davisor.graphics.OctreeColorReducer.ColorTree

Enclosing class:

OctreeColorReducer

protected class OctreeColorReducer.ColorTree

extends java.lang.Object

ColorTree implements a color octree that orginizes colors into a hierarchy of similar colors. The color tree is made of OctreeColorReducer.ColorNode nodes, each having up to 8 children nodes. Each node represents a RGB color value. If the node has children, the node color value represents also the weighed average of all the children color values.

All nodes at the same tree depth are also arranged into one-directional linked lists. The head nodes of these lists are always known to the color tree. These lists area allow very fast access to nodes at spesific depth.

This implementation uses a speed optimization strategy that keeps the color tree size down to given maximum size AT ALL TIMES. In particular, the color tree is reduced immediately back to the maximum size each time after a new color has been added to the tree. This produces less optimal but much faster results than a strategy that would first add all colors to the tree, and only then reduce it.

The 8 children represent all the combinations a 3 bit bit -patterns can take. These bit patterns are formed by taking the corresponding bits from the 3 RGB component values. RGB component values are expected to be 8 bit values, so the maximum color tree depth is also 8.

See Also:

addColor(int), reduce()

Field Summary

static int	ALPHA_THRESHOLD BITMAP trasparency threshold (0x80).
protected int	M_leafCount Current total number of color leafs.
protected int	M_maxColors Maximum allowed number of color leafs.
protected OctreeColorReducer.ColorNode[]	M_nodesAtDepth Color node list heads, indexed and sorted by node depth.
protected OctreeColorReducer.ColorNode	M_root The color tree root node.
protected boolean	M_transparent Indicates the presense or absense of a special transparent color.
static int	MAX_DEPTH Maximum color tree depth (8).

Constructor Summary

protected

OctreeColorReducer.ColorTree(int maxColors) Creates a new color tree, with potential to grow to contain up to given maximum number of different colors.

Method Summary

protected void	addColor(int argb) Adds a ARGB color into the tree.
protected int	getColor(int argb) Gets the replacement color value for the given color.
protected int[]	getColors() Traverses through the tree is depth-first order and stores the found color sRGB values into the returned array.
protected int	getIndex(int argb) Gets the replacement color index for the given color.
protected void	reduce() Reduces the tree size size by collapsing one of the less significant color nodes.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

ALPHA_THRESHOLD

public static final int ALPHA_THRESHOLD

BITMAP trasparency threshold (0x80).

See Also:

Constant Field Values

MAX_DEPTH

public static final int MAX_DEPTH

Maximum color tree depth (8).

See Also:

Constant Field Values

M_leafCount

protected int M_leafCount

Current total number of color leafs.

M_maxColors

protected int M_maxColors

Maximum allowed number of color leafs.

M_nodesAtDepth

protected OctreeColorReducer.ColorNode[] M_nodesAtDepth

Color node list heads, indexed and sorted by node depth.

M_root

protected OctreeColorReducer.ColorNode M_root

The color tree root node.

M_transparent

protected boolean M_transparent

Indicates the presense or absense of a special transparent color.

Constructor Detail

OctreeColorReducer.ColorTree

protected OctreeColorReducer.ColorTree(int maxColors)

Creates a new color tree, with potential to grow to contain up to given maximum number of different colors.

Parameters:

maxColors - maximum number of colors this tree may contain

Method Detail

addColor

protected void addColor(int argb)

Adds a ARGB color into the tree. Takes care of transparency by treating all colors with alpha smaller than 0x80 as fully transparent, and others as fully opaque.

Parameters:

argb - standard 32 bit ARGB color value to add to the tree

See Also:

getColor(int), getIndex(int), reduce()

getColors

protected int[] getColors()

Traverses through the tree is depth-first order and stores the found color sRGB values into the returned array.

getColor

protected int getColor(int argb)

Gets the replacement color value for the given color.

Color palettes provide typically only limited set of transparent colors, as typical color palette contains only fully opaque colors, and only one fully transparent color, if even that. The transparency component of the returned palette color may therefore be significantly different that of the source color.

Parameters:

argb - standard sRGB color value (with alpha)

Returns:

replacement sRGB color value (with alpha)

See Also:

addColor(int), getIndex(int), OctreeColorReducer.ColorNode.getColor()

getIndex

protected int getIndex(int argb)

Gets the replacement color index for the given color. The index values returned will refer to the latest color palette generated by the OctreeColorReducer.getPalette() method.

Color palettes provide typically only limited set of transparent colors, as typical color palette contains only fully opaque colors, and only one fully transparent color, if even that. The transparency component of the returned palette color may therefore be significantly different that of the source color.

Parameters:

argb - standard sRGB color value (with alpha)

Returns:

replacement color index

Throws:

java.lang.IllegalStateException - if the color tree has not been assosiated with any color palette

See Also:

addColor(int), getColor(int), OctreeColorReducer.ColorNode.getIndex(int, int, int, int)

reduce

protected void reduce()
               throws com.davisor.core.NotFoundException

Reduces the tree size size by collapsing one of the less significant color nodes. The children of the collapsed color node will be approximated with their mutual average color.

If the tree has been reduced down to just the root node, it will not be collapsed, as this would result a tree with just one color. Instead, the least referenced root child is removed, and the root color is changed to the average between the original root color, and the color of the removed child.

If the tree has been reduced so small that even the root node has no children, no node to be collapsed can be found, and an exception is thrown.

This implementation optimizes the less significant color node search by just taking the latest added node from the deepest possible tree hierarchy level. An optimal but much slower solution would search the whole tree for the least reference color.

Throws:

com.davisor.core.NotFoundException - if not even one reductable node was found