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 }