001    /*
002     * OctreeNode
003     * 
004     * Copyright (c) 2001, 2002, 2003 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.color.quantization;
009    
010    import net.sourceforge.jiu.data.RGBIndex;
011    import net.sourceforge.jiu.util.ComparatorInterface;
012    
013    /**
014     * A single node in an octree.
015     * @author Marco Schmidt
016     * @since 0.6.0
017     * @see OctreeColorQuantizer
018     */
019    public class OctreeNode implements ComparatorInterface, RGBIndex
020    {
021            private int paletteIndex;
022            private int pixelCount;
023            private int redSum;
024            private int greenSum;
025            private int blueSum;
026            private int red;
027            private int green;
028            private int blue;
029            private OctreeNode[] children;
030    
031            /**
032             * Add a color red-green-blue to the octree, given by its root node.
033             * This methods follows the octree down to the bitsPerSample'th level,
034             * creating nodes as necessary.
035             * Increases the pixelCount of a leaf node (if the node already exists)
036             * or initializes a newly-created leaf.
037             * @param root root node of the octree
038             * @param red the red intensity value of the color to be added
039             * @param green the green intensity value of the color to be added
040             * @param blue the blue intensity value of the color to be added
041             * @param bitsPerSample
042             */
043            public static boolean add(OctreeNode root, int red, int green, int blue, int bitsPerSample)
044            {
045                    OctreeNode node = root;
046                    boolean newColor = false;
047                    int shift = bitsPerSample - 1;
048                    do
049                    {
050                            if (shift >= 0)
051                            {
052                                    // not a leaf
053                                    OctreeNode[] children = node.children;
054                                    if (children == null)
055                                    {
056                                            children = new OctreeNode[8];
057                                            node.children = children;
058                                    }
059                                    int index = computeIndex(red, green, blue, shift);
060                                    node = children[index];
061                                    if (node == null)
062                                    {
063                                            node = new OctreeNode();
064                                            children[index] = node;
065                                            newColor = true;
066                                    }
067                                    shift--;
068                            }
069                            else
070                            {
071                                    // leaf; update its red/green/blue/pixel count and leave
072                                    node.update(red, green, blue);
073                                    return newColor;
074                            }
075                    }
076                    while (true);
077            }
078    
079            public int compare(Object o1, Object o2)
080            {
081                    OctreeNode n1 = (OctreeNode)o1;
082                    OctreeNode n2 = (OctreeNode)o2;
083                    int pc1 = n1.pixelCount;
084                    int pc2 = n2.pixelCount;
085                    if (pc1 < pc2)
086                    {
087                            return -1;
088                    }
089                    else
090                    if (pc1 == pc2)
091                    {
092                            return 0;
093                    }
094                    else
095                    {
096                            return 1;
097                    }
098            }
099    
100            private static int computeIndex(int red, int green, int blue, int shift)
101            {
102                    return (((red >> shift) & 1) << 2) |
103                            (((green >> shift) & 1) << 1) |
104                            ((blue >> shift) & 1);
105            }
106    
107            /**
108             * Adds the sums for red, green and blue values and
109             * the pixel count values of all child nodes and
110             * stores the results in this node.
111             * Does nothing if this is a leaf.
112             * Otherwise, recursively calls itself with all
113             * non-null child nodes and adds their sums for red,
114             * green and blue and the number of pixel values.
115             * Then stores these values in this node.
116             * They will be used when the octree is pruned to have
117             * a certain number of leaves.
118             */
119            public void copyChildSums()
120            {
121                    if (children == null)
122                    {
123                            return;
124                    }
125                    redSum = 0;
126                    greenSum = 0;
127                    blueSum = 0;
128                    pixelCount = 0;
129                    for (int i = 0; i < children.length; i++)
130                    {
131                            OctreeNode child = children[i];
132                            if (child != null)
133                            {
134                                    child.copyChildSums();
135                                    redSum += child.redSum;
136                                    greenSum += child.greenSum;
137                                    blueSum += child.blueSum;
138                                    pixelCount += child.pixelCount;
139                            }
140                    }
141            }
142    
143            public void determineRepresentativeColor()
144            {
145                    if (pixelCount > 0)
146                    {
147                            red = redSum / pixelCount;
148                            green = greenSum / pixelCount;
149                            blue = blueSum / pixelCount;
150                    }
151            }
152    
153            /*public static OctreeNode findMinimumNode(OctreeNode node, OctreeNode currentMinimumNode, int minimumNodePixelCount)
154            {
155                    OctreeNode[] children = node.getChildren();
156                    if (children == null)
157                    {
158                            return currentMinimumNode;
159                    }
160                    int sum = 0;
161                    boolean hasOnlyLeafChildren = true;
162                    for (int i = 0; i < children.length; i++)
163                    {
164                            OctreeNode child = children[i];
165                            if (child != null)
166                            {
167                                    if (child.isLeaf())
168                                    {
169                                            sum += child.pixelCount;
170                                    }
171                                    else
172                                    {
173                                            hasOnlyLeafChildren = false;
174                                            //findMinimumNode(child, currentMinimumNode, minimumNodePixelCount);
175                                    }
176                            }
177                    }
178                    return currentMinimumNode;
179            }*/
180    
181            public int getBlue()
182            {
183                    return blue;
184            }
185    
186            public OctreeNode[] getChildren()
187            {
188                    return children;
189            }
190    
191            public int getGreen()
192            {
193                    return green;
194            }
195    
196            public int getNumChildren()
197            {
198                    int result = 0;
199                    if (children != null)
200                    {
201                            for (int i = 0; i < children.length; i++)
202                            {
203                                    if (children[i] != null)
204                                    {
205                                            result++;
206                                    }
207                            }
208                    }
209                    return result;
210            }
211    
212            public int getPaletteIndex()
213            {
214                    return paletteIndex;
215            }
216    
217            public int getRed()
218            {
219                    return red;
220            }
221    
222            public boolean isLeaf()
223            {
224                    return children == null;
225            }
226    
227            /**
228             * Returns the index of the best match for origRgb in the palette or
229             * -1 if the best match could not be determined.
230             * If there was a best match, quantizedRgb is filled with the quantized color's
231             * RGB values.
232             */
233            public int map(int[] origRgb, int[] quantizedRgb)
234            {
235                    return map(origRgb[INDEX_RED], origRgb[INDEX_GREEN], origRgb[INDEX_BLUE], 7, quantizedRgb);
236            }
237    
238            private final int map(final int r, final int g, final int b, final int shift, final int[] quantizedRgb)
239            {
240                    if (children == null)
241                    {
242                            quantizedRgb[INDEX_RED] = red;
243                            quantizedRgb[INDEX_GREEN] = green;
244                            quantizedRgb[INDEX_BLUE] = blue;
245                            return paletteIndex;
246                    }
247                    int index = computeIndex(r, g, b, shift);
248                    OctreeNode node = children[index];
249                    if (node == null)
250                    {
251                            return -1;
252                    }
253                    return node.map(r, g, b, shift - 1, quantizedRgb);
254            }
255    
256            public void setChildren(OctreeNode[] newChildren)
257            {
258                    children = newChildren;
259            }
260    
261            public void setPaletteIndex(int index)
262            {
263                    paletteIndex = index;
264            }
265    
266            private void update(int red, int green, int blue)
267            {
268                    redSum += red;
269                    greenSum += green;
270                    blueSum += blue;
271                    pixelCount++;
272            }
273    }