1 #include "palette_creater.h"
2
3 #ifdef _DEBUG
4 #define new DEBUG_NEW
5 #else
6 #define STUDIOX_EVAL_BUILD
7 #endif
8
palette_creater()9 palette_creater::palette_creater()
10 {
11 histogram = NULL;
12 boxlist = NULL;
13 }
14
15
~palette_creater()16 palette_creater::~palette_creater()
17 {
18 }
19
20 ///////////////////////////////////////////////////////////////////////////////
21 // Note:
22 // The color quantization code is implemented based on Heckbert's Median Cut
23 // Algorithm that described in the following paper:
24 //
25 // Heckbert, Paul. "Color Image Quantization for Frame Buffer Display",
26 // *Proc.SIGGRAPH '82, Computer Graphics v.16 #3 (July 1982), pp 297-304.
27 //
28 // The concept behind the median cut algorithm is to partition the color space
29 // into a three-dimensional rectangle box. Next separated the selected box into
30 // two halves recursively untill we get a desired number of boxes.
31 ///////////////////////////////////////////////////////////////////////////////
CreatePaletteForOnePixelmap(res_info * resource,palette_info * info,int requested_size)32 void palette_creater::CreatePaletteForOnePixelmap(res_info *resource, palette_info *info, int requested_size)
33 {
34 CreatePaletteForPixelmaps(resource, info, FALSE, requested_size);
35 }
36
37
CreatePaletteForPixelmaps(res_info * resource,palette_info * info,BOOL recursive,int requested_size)38 void palette_creater::CreatePaletteForPixelmaps(res_info *resource, palette_info *info, BOOL recursive, int requested_size)
39 {
40 int boxes_num;
41
42 ULONG hist_size = (1 << (HIST_RED_BITS + HIST_GREEN_BITS + HIST_BLUE_BITS));
43
44 histogram = new ULONG[hist_size];
45 memset(histogram, 0, hist_size * sizeof(UINT));
46
47 if (requested_size == -1)
48 {
49 requested_size = 255;
50 }
51
52 boxlist = new BOX[requested_size];
53 memset(boxlist, 0, requested_size * sizeof(BOX));
54
55 // Accumulate the color histogram of all images under
56 // the specified pixelmap folder, which showing the
57 // usage count of each possible color
58 if (!recursive)
59 {
60 AccumulateOneMapHistogram(resource);
61 }
62 else
63 {
64 AccumulateSharedHistogram(resource);
65 }
66
67 // Initiate one box that containing whole space.
68 // Here we properly decrease the precision of the input color by
69 // Remaining 5 bits for red, 6 bits for green and 5 bits for blue.
70 // By doing this, we get a smaller histogram size that contains
71 // 65536 colors.
72 boxlist[0].rmin = 0;
73 boxlist[0].rmax = (1 << HIST_RED_BITS) - 1;
74 boxlist[0].gmin = 0;
75 boxlist[0].gmax = (1 << HIST_GREEN_BITS) - 1;
76 boxlist[0].bmin = 0;
77 boxlist[0].bmax = (1 << HIST_BLUE_BITS) - 1;
78
79 // Update some parametersi of the first box that containing whole space
80 UpdateBox(&boxlist[0]);
81
82 // Process median cut algorithm to produce the desired number of boxes
83 boxes_num = median_cut(requested_size);
84
85 info->palette = new GX_COLOR[requested_size];
86 memset(info->palette, 0, requested_size * sizeof(GX_COLOR));
87 info->total_size = requested_size;
88 info->used_size = boxes_num;
89
90 // Calculate the average color of each box which comes to one entry of
91 // the optimized palette
92 for (int index = 0; index < boxes_num; index++)
93 {
94 ComputeColor(info, &boxlist[index], index);
95 }
96
97 if (histogram)
98 {
99 delete histogram;
100 histogram = NULL;
101 }
102
103 if (boxlist)
104 {
105 delete boxlist;
106 boxlist = NULL;
107 }
108 }
109
110 // Find the splittable BOX with the largest color population.
FindLargestColorPop(int numboxes)111 BOX *palette_creater::FindLargestColorPop(int numboxes)
112 {
113 BOX *which = NULL;
114 long maxc = 0;
115 BOX *boxp = boxlist;
116
117 for (int i = 0; i < numboxes; i++)
118 {
119 if ((boxp->color_count > maxc) && (boxp->volume > 0))
120 {
121 which = boxp;
122 maxc = boxp->color_count;
123 }
124
125 boxp++;
126 }
127
128 return which;
129 }
130
131 // Find the splittable BOX with the largest color volume.
FindLargestColorVolume(int numboxes)132 BOX *palette_creater::FindLargestColorVolume(int numboxes)
133 {
134 BOX *which = NULL;
135 long maxc = 0;
136 BOX *boxp = boxlist;
137
138 for (int i = 0; i < numboxes; i++)
139 {
140 if ((boxp->volume > maxc) && (boxp->color_count > 0))
141 {
142 which = boxp;
143 maxc = boxp->volume;
144 }
145
146 boxp++;
147 }
148
149 return which;
150 }
151
UpdateBox(BOX * boxp)152 void palette_creater::UpdateBox(BOX *boxp)
153 {
154 // Shrink the min and max bounds of a BOX to include only nonzero pixels
155 int rmin, rmax;
156 int gmin, gmax;
157 int bmin, bmax;
158
159 rmin = (1 << HIST_RED_BITS) - 1;
160 rmax = 0;
161 gmin = (1 << HIST_GREEN_BITS) - 1;
162 gmax = 0;
163 bmin = (1 << HIST_BLUE_BITS) - 1;
164 bmax = 0;
165
166 int r, g, b;
167 int color_count = 0;
168 ULONG *histp;
169 int pos;
170
171 for (r = boxp->rmin; r <= boxp->rmax; r++)
172 {
173 for (g = boxp->gmin; g <= boxp->gmax; g++)
174 {
175 for (b = boxp->bmin; b <= boxp->bmax; b++)
176 {
177 pos = ASSEMBLECOLOR_16BPP(r, g, b);
178 histp = &histogram[pos];
179
180 if (*histp != 0)
181 {
182 color_count++;
183
184 if (r < rmin)
185 {
186 rmin = r;
187 }
188
189 if (r > rmax)
190 {
191 rmax = r;
192 }
193
194 if (g < gmin)
195 {
196 gmin = g;
197 }
198
199 if (g > gmax)
200 {
201 gmax = g;
202 }
203
204 if (b < bmin)
205 {
206 bmin = b;
207 }
208
209 if (b > bmax)
210 {
211 bmax = b;
212 }
213 }
214 }
215 }
216 }
217
218 boxp->color_count = color_count;
219 boxp->rmin = rmin;
220 boxp->rmax = rmax;
221 boxp->gmin = gmin;
222 boxp->gmax = gmax;
223 boxp->bmin = bmin;
224 boxp->bmax = bmax;
225
226 int rdist = ((rmax - rmin) << HIST_RED_SHIFT) * RED_SCALE;
227 int gdist = ((gmax - gmin) << HIST_GREEN_SHIFT) * GREEN_SCALE;
228 int bdist = ((bmax - bmin) << HIST_BLUE_SHIFT) * BLUE_SCALE;
229
230 boxp->volume = rdist * rdist + gdist * gdist + bdist * bdist;
231 }
232
233 // Accumulate color histogram of all pixelmaps under info that are
234 // using shared palette
AccumulateSharedHistogram(res_info * info)235 void palette_creater::AccumulateSharedHistogram(res_info *info)
236 {
237 while (info)
238 {
239 if (info->type == RES_TYPE_PIXELMAP)
240 {
241 if (info->palette_type == PALETTE_TYPE_SHARED)
242 {
243 AccumulateOneMapHistogram(info);
244 }
245 }
246 if (info->child)
247 {
248 AccumulateSharedHistogram(info->child);
249 }
250 info = info->next;
251 }
252 }
253
254 // Accumulate one map color histogram
AccumulateOneMapHistogram(res_info * info)255 void palette_creater::AccumulateOneMapHistogram(res_info *info)
256 {
257 if (info->type != RES_TYPE_PIXELMAP)
258 {
259 return;
260 }
261
262 GX_COLOR *getdata;
263 int width;
264 int height;
265 int red, green, blue;
266 ULONG *histp;
267 USHORT pos;
268 res_info *pixinfo;
269
270 pixinfo = new res_info(NULL, *info, FALSE);
271 pixinfo->output_color_format = GX_COLOR_FORMAT_24XRGB;
272 pixinfo->keep_alpha = FALSE;
273 pixinfo->compress = FALSE;
274 GetOpenProject()->InitializeOnePixelmap(pixinfo, NULL, GX_COLOR_FORMAT_24XRGB);
275
276 GX_PIXELMAP *map;
277
278 for (int index = 0; index < pixinfo->GetPixelmapFrameCount(); index++)
279 {
280 map = pixinfo->GetPixelmap(index);
281
282 if (map && map->gx_pixelmap_data)
283 {
284 getdata = (GX_COLOR*)map->gx_pixelmap_data;
285 width = map->gx_pixelmap_width;
286 height = map->gx_pixelmap_height;
287
288 for (int index = 0; index < width * height; index++)
289 {
290 red = (*getdata) >> 16;
291 green = ((*getdata) & 0xff00) >> 8;
292 blue = ((*getdata) & 0xff);
293
294 red >>= HIST_RED_SHIFT;
295 green >>= HIST_GREEN_SHIFT;
296 blue >>= HIST_BLUE_SHIFT;
297
298 pos = ASSEMBLECOLOR_16BPP(red, green, blue);
299 histp = &histogram[pos];
300
301 if (++(*histp) <= 0)
302 {
303 (*histp)--;
304 }
305
306 getdata++;
307 }
308 }
309 }
310
311 delete pixinfo;
312 }
313
314 // Median cut color quantization algorithm that split one box that containing
315 // the whole color space into desired number of boxes.
median_cut(int desired_colors_num)316 int palette_creater::median_cut(int desired_colors_num)
317 {
318 int boxes_num = 1;
319 BOX *b1, *b2;
320
321 while (boxes_num < desired_colors_num)
322 {
323 if (boxes_num * 2 <= desired_colors_num)
324 {
325 // select the box with the largest color population
326 b1 = FindLargestColorPop(boxes_num);
327 }
328 else
329 {
330 // select the box with the largets color volumn
331 b1 = FindLargestColorVolume(boxes_num);
332 }
333
334 if (b1 == NULL)
335 {
336 break;
337 }
338
339 b2 = &boxlist[boxes_num];
340
341 /* initiate new BOX. */
342 (*b2) = (*b1);
343
344 int rdist = ((b1->rmax - b1->rmin) << HIST_RED_SHIFT) * RED_SCALE;
345 int gdist = ((b1->gmax - b1->gmin) << HIST_GREEN_SHIFT) * GREEN_SCALE;
346 int bdist = ((b1->bmax - b1->bmin) << HIST_BLUE_SHIFT) * BLUE_SCALE;
347
348 // split the selected box along the longges axis
349 if ((rdist >= gdist) && (rdist >= bdist))
350 {
351 //split BOX along red axis
352 b1->rmax = (b1->rmax + b1->rmin) / 2;
353 b2->rmin = (b1->rmax + 1);
354 }
355 else if ((gdist >= rdist) && (gdist >= bdist))
356 {
357 //split BOX along green axis
358 b1->gmax = (b1->gmax + b1->gmin) / 2;
359 b2->gmin = (b1->gmax + 1);
360 }
361 else
362 {
363 //split BOX along blue axis
364 b1->bmax = (b1->bmax + b1->bmin) / 2;
365 b2->bmin = (b1->bmax + 1);
366 }
367
368 UpdateBox(b1);
369 UpdateBox(b2);
370
371 boxes_num++;
372 }
373
374 return boxes_num;
375 }
376
377 // Calcualte the average color value of one box
ComputeColor(palette_info * control,BOX * boxp,int index)378 void palette_creater::ComputeColor(palette_info *control, BOX *boxp, int index)
379 {
380 int r, g, b;
381 int count;
382 ULONG *histp;
383 ULONG total = 0;
384 ULONG totalred = 0;
385 ULONG totalgreen = 0;
386 ULONG totalblue = 0;
387
388 for (r = boxp->rmin; r <= boxp->rmax; r++)
389 {
390 for (g = boxp->gmin; g <= boxp->gmax; g++)
391 {
392 for (b = boxp->bmin; b <= boxp->bmax; b++)
393 {
394 histp = &histogram[ASSEMBLECOLOR_16BPP(r, g, b)];
395 count = *histp;
396
397 if (count)
398 {
399 total += count;
400
401 totalred += (r << HIST_RED_SHIFT) * count;
402 totalgreen += (g << HIST_GREEN_SHIFT) * count;
403 totalblue += (b << HIST_BLUE_SHIFT) * count;
404 }
405 }
406 }
407 }
408
409 if (total)
410 {
411 r = totalred / total;
412 g = totalgreen / total;
413 b = totalblue / total;
414
415 control->palette[index] = 0xff000000 | ASSEMBLECOLOR_24BPP(r, g, b);
416 }
417 }
