source: trunk/src/opengl/glide/cvg/texus/pal256.c

Last change on this file was 6653, checked in by bird, 24 years ago

Added $Id:$ keyword.
File size: 18.3 KB
Line 
1/* $Id: pal256.c,v 1.2 2001-09-05 14:30:45 bird Exp $ */
2/*
3 * This software is copyrighted as noted below. It may be freely copied,
4 * modified, and redistributed, provided that the copyright notice is
5 * preserved on all copies.
6 *
7 * There is no warranty or other guarantee of fitness for this software,
8 * it is provided solely "as is". Bug reports or fixes may be sent
9 * to the author, who may or may not act on them as he desires.
10 *
11 * You may not include this software in a program or other software product
12 * without supplying the source, or without informing the end-user that the
13 * source is available for no extra charge.
14 *
15 * If you modify this software, you should include a notice giving the
16 * name of the person performing the modification, the date of modification,
17 * and the reason for such modification.
18 */
19
20
21/*
22 * Well, I hacked it anyway.... Murali.
23 *
24 * colorquant.c
25 *
26 * Perform variance-based color quantization on a "full color" image.
27 * Author: Craig Kolb
28 * Department of Mathematics
29 * Yale University
30 * kolb@yale.edu
31 * Date: Tue Aug 22 1989
32 * Copyright (C) 1989 Craig E. Kolb
33 */
34
35#include <stdio.h>
36#include <stdlib.h>
37#include <string.h>
38#include <memory.h>
39#include <math.h>
40
41#include "texusint.h"
42
43
44#define USE_INVERSE_PAL
45#define INVERSE_PAL_R_BITS 5
46#define INVERSE_PAL_G_BITS 5
47#define INVERSE_PAL_B_BITS 5
48#define INVERSE_PAL_TOTAL_BITS ( INVERSE_PAL_R_BITS + \
49 INVERSE_PAL_G_BITS + \
50 INVERSE_PAL_B_BITS )
51
52#ifdef USE_INVERSE_PAL
53unsigned char inverse_pal[1<<INVERSE_PAL_TOTAL_BITS];
54#endif
55
56typedef unsigned long ulong;
57typedef unsigned char uchar;
58typedef unsigned short ushort;
59
60#ifdef HUGE
61#undef HUGE
62#endif
63
64#define HUGE 1.0e38
65
66#define NBITS 5
67
68#define MAXCOLORS 256
69#define FULLINTENSITY 255
70#define MAX(x,y) ((x) > (y) ? (x) : (y))
71
72/*
73 * Readability constants.
74 */
75#define REDI 0
76#define GREENI 1
77#define BLUEI 2
78#define TRUE 1
79#define FALSE 0
80#define bzero(ptr, sz) memset(ptr, 0, sz)
81
82typedef struct {
83 float weightedvar; /* weighted variance */
84 ulong mean[3]; /* centroid */
85 ulong weight; /* # of pixels in box */
86 ulong freq[3][MAXCOLORS]; /* Projected frequencies */
87 int low[3], high[3]; /* Box extent */
88} Box;
89
90#define COLORMAXI ( 1 << NBITS )
91#if 0
92static ulong *Histogram; /* image histogram */
93#else
94static ulong Histogram[COLORMAXI*COLORMAXI*COLORMAXI * sizeof(long)];
95#endif
96static ulong SumPixels; /* total # of pixels */
97static ulong ColormaxI; /* # of colors, 2^Bits */
98static Box _Boxes[MAXCOLORS];
99static Box *Boxes; /* Array of color boxes. */
100
101static void SetRGBmap(int boxnum, Box *box, uchar *rgbmap);
102static void ComputeRGBMap(Box *boxes, int colors, uchar *rgbmap);
103static void UpdateFrequencies(Box *box1, Box *box2);
104static int FindCutpoint(Box *box, int color, Box *newbox1, Box *newbox2);
105static int CutBox(Box *box, Box *newbox);
106static void BoxStats(Box *box);
107static int GreatestVariance(Box *boxes, int n);
108static int CutBoxes(Box *boxes, int colors);
109static void QuantHistogram(ulong *pixels, int npixels, Box *box);
110
111/*
112 * Perform variance-based color quantization on a 24-bit image.
113 */
114int
115txMipPal256(TxMip *pxMip, TxMip *txMip, int format, FxU32 dither, FxU32 compression)
116{
117 int w, h;
118 int i; /* Counter */
119 int OutColors; /* # of entries computed */
120 int Colormax; /* quantized full-intensity */
121 float Cfactor; /* Conversion factor */
122#if 0
123 uchar *rgbmap; /* how to map colors to palette indices */
124#else
125 static uchar rgbmap[(1<<NBITS)*(1<<NBITS)*(1<<NBITS)]; /* how to map colors to palette indices */
126#endif
127 int pixsize;
128
129
130 ColormaxI = 1 << NBITS; /* 2 ^ NBITS */
131 Colormax = ColormaxI - 1;
132 Cfactor = (float)FULLINTENSITY / Colormax;
133
134 Boxes = _Boxes;
135#if 0
136 Histogram = (ulong *) txMalloc(ColormaxI*ColormaxI*ColormaxI * sizeof(long));
137 rgbmap = txMalloc((1<<NBITS)*(1<<NBITS)*(1<<NBITS));
138#endif
139
140 /*
141 * Zero-out the projected frequency arrays of the largest box.
142 */
143 bzero(Boxes->freq[0], ColormaxI * sizeof(ulong));
144 bzero(Boxes->freq[1], ColormaxI * sizeof(ulong));
145 bzero(Boxes->freq[2], ColormaxI * sizeof(ulong));
146 bzero(Histogram, ColormaxI * ColormaxI * ColormaxI * sizeof(long));
147
148 /* Feed all bitmaps & generate histogram */
149 SumPixels = 0;
150 w = txMip->width;
151 h = txMip->height;
152 for (i=0; i< txMip->depth; i++) {
153 SumPixels += w * h;
154 QuantHistogram((ulong *)txMip->data[i], w * h, &Boxes[0]);
155 if (w > 1) w >>= 1;
156 if (h > 1) h >>= 1;
157 }
158
159 OutColors = CutBoxes(Boxes, MAXCOLORS);
160
161 /*
162 * We now know the set of representative colors. We now
163 * must fill in the colormap and convert the representatives
164 * from their 'prequantized' range to 0-FULLINTENSITY.
165 */
166 for (i = 0; i < OutColors; i++) {
167 ulong r, g, b;
168 r = (ulong)(Boxes[i].mean[REDI] * Cfactor + 0.5);
169 g = (ulong)(Boxes[i].mean[GREENI] * Cfactor + 0.5);
170 b = (ulong)(Boxes[i].mean[BLUEI] * Cfactor + 0.5);
171
172 /*
173 r &= 0xff;
174 g &= 0xff;
175 b &= 0xff;
176 */
177 if (r > 255) r = 255;
178 if (g > 255) g = 255;
179 if (b > 255) b = 255;
180
181 pxMip->pal[i] = (r<<16) | (g << 8) | b;
182 }
183 ComputeRGBMap(Boxes, OutColors, rgbmap);
184
185 /*
186 * Now translate the colors to palette indices.
187 */
188 pixsize = (format == GR_TEXFMT_P_8) ? 1 : 2;
189
190 if ((dither&TX_DITHER_MASK) != TX_DITHER_NONE) {
191 /* support only error diffusion, no 4x4 dithering */
192 txDiffuseIndex(pxMip, txMip, pixsize, pxMip->pal, OutColors);
193 } else {
194
195 w = txMip->width;
196 h = txMip->height;
197
198 for (i=0; i< txMip->depth; i++) {
199 ulong *src;
200 uchar *dst;
201 int n;
202
203 src = (ulong *) txMip->data[i];
204 dst = (uchar *) pxMip->data[i];
205 n = w * h;
206 while (n--) {
207 int r, g, b, argb, index;
208
209 argb = *src++;
210 r = (argb & 0x00FF0000) >> (16 + 8 - NBITS);
211 g = (argb & 0x0000FF00) >> ( 8 + 8 - NBITS);
212 b = (argb & 0x000000FF) >> ( 0 + 8 - NBITS);
213
214 index = (r << (NBITS+NBITS)) | (g << NBITS) | b;
215 if ((index < 0) || (index >= 32768)) {
216 printf("Bad index: %d (%d %d %d)\n", index, r, g, b);
217 }
218 if (pixsize == 1) {
219 *dst++ = rgbmap[index];
220 } else {
221 *(FxU16 *)dst = (rgbmap[index]) |
222 ((argb >> 16) & 0xFF00);
223 dst+= 2;
224 }
225 }
226 if (w > 1) w >>= 1;
227 if (h > 1) h >>= 1;
228 }
229 }
230
231#if 0
232 txFree((char *)Histogram);
233 txFree((char *)rgbmap);
234#endif
235 return OutColors;
236}
237
238/*
239 * Compute the histogram of the image as well as the projected frequency
240 * arrays for the first world-encompassing box.
241 */
242static void
243QuantHistogram(ulong *pixels, int npixels, Box *box)
244{
245 ulong *rf, *gf, *bf;
246 uchar rr, gg, bb;
247 int i;
248
249 rf = box->freq[0];
250 gf = box->freq[1];
251 bf = box->freq[2];
252
253 /*
254 * We compute both the histogram and the proj. frequencies of
255 * the first box at the same time to save a pass through the
256 * entire image.
257 */
258
259 for (i = 0; i < npixels; i++) {
260 rr = (uchar) (((*pixels >> 16) & 0xff) >> (8-NBITS));
261 gg = (uchar) (((*pixels >> 8) & 0xff) >> (8-NBITS));
262 bb = (uchar) (((*pixels ) & 0xff) >> (8-NBITS));
263 pixels++;
264 rf[rr]++;
265 gf[gg]++;
266 bf[bb]++;
267 Histogram[(((rr<<NBITS)|gg)<<NBITS)|bb]++;
268 }
269
270}
271
272/*
273 * Interatively cut the boxes.
274 */
275static int
276CutBoxes(Box *boxes, int colors)
277{
278 int curbox;
279
280 boxes[0].low[REDI] = boxes[0].low[GREENI] = boxes[0].low[BLUEI] = 0;
281 boxes[0].high[REDI] = boxes[0].high[GREENI] =
282 boxes[0].high[BLUEI] = ColormaxI;
283 boxes[0].weight = SumPixels;
284
285 BoxStats(&boxes[0]);
286
287 for (curbox = 1; curbox < colors; curbox++) {
288 if (CutBox(&boxes[GreatestVariance(boxes, curbox)],
289 &boxes[curbox]) == FALSE)
290 break;
291 }
292
293 return curbox;
294}
295
296/*
297 * Return the number of the box in 'boxes' with the greatest variance.
298 * Restrict the search to those boxes with indices between 0 and n-1.
299 */
300static int
301GreatestVariance(Box *boxes, int n)
302{
303 int i, whichbox = 0;
304 float max;
305
306 max = -1.0f;
307 for (i = 0; i < n; i++) {
308 if (boxes[i].weightedvar > max) {
309 max = (float) boxes[i].weightedvar;
310 whichbox = i;
311 }
312 }
313 return whichbox;
314}
315
316/*
317 * Compute mean and weighted variance of the given box.
318 */
319static void
320BoxStats(Box *box)
321{
322 int i, color;
323 ulong *freq;
324 float mean, var;
325
326 if(box->weight == 0) {
327 box->weightedvar = (float) 0.0;
328 return;
329 }
330
331 box->weightedvar = (float) 0.0;
332 for (color = 0; color < 3; color++) {
333 var = mean = (float) 0.0;
334 i = box->low[color];
335 freq = &box->freq[color][i];
336 for (; i < box->high[color]; i++, freq++) {
337 mean += (float) i * *freq;
338 var += (float) i*i* *freq;
339 }
340 box->mean[color] = (unsigned long) (mean / (float)box->weight);
341 box->weightedvar += var - box->mean[color]*box->mean[color]*
342 (float)box->weight;
343 }
344 box->weightedvar /= SumPixels;
345}
346
347/*
348 * Cut the given box. Returns TRUE if the box could be cut, FALSE otherwise.
349 */
350static int
351CutBox(Box *box, Box *newbox)
352{
353 int i;
354 float totalvar[3];
355 Box newboxes[3][2];
356
357 if (box->weightedvar == 0. || box->weight == 0)
358 /*
359 * Can't cut this box.
360 */
361 return FALSE;
362
363 /*
364 * Find 'optimal' cutpoint along each of the red, green and blue
365 * axes. Sum the variances of the two boxes which would result
366 * by making each cut and store the resultant boxes for
367 * (possible) later use.
368 */
369 for (i = 0; i < 3; i++) {
370 if (FindCutpoint(box, i, &newboxes[i][0], &newboxes[i][1]))
371 totalvar[i] = newboxes[i][0].weightedvar +
372 newboxes[i][1].weightedvar;
373 else
374 totalvar[i] = (float) HUGE;
375 }
376
377 /*
378 * Find which of the three cuts minimized the total variance
379 * and make that the 'real' cut.
380 */
381 if (totalvar[REDI] <= totalvar[GREENI] &&
382 totalvar[REDI] <= totalvar[BLUEI]) {
383 *box = newboxes[REDI][0];
384 *newbox = newboxes[REDI][1];
385 } else if (totalvar[GREENI] <= totalvar[REDI] &&
386 totalvar[GREENI] <= totalvar[BLUEI]) {
387 *box = newboxes[GREENI][0];
388 *newbox = newboxes[GREENI][1];
389 } else {
390 *box = newboxes[BLUEI][0];
391 *newbox = newboxes[BLUEI][1];
392
393 }
394
395 return TRUE;
396}
397
398/*
399 * Compute the 'optimal' cutpoint for the given box along the axis
400 * indcated by 'color'. Store the boxes which result from the cut
401 * in newbox1 and newbox2.
402 */
403static int
404FindCutpoint(Box *box, int color, Box *newbox1, Box *newbox2)
405{
406 float u, v, max;
407 int i, maxindex, minindex, cutpoint;
408 ulong optweight, curweight;
409
410 if (box->low[color] + 1 == box->high[color])
411 return FALSE; /* Cannot be cut. */
412 minindex = (int)((box->low[color] + box->mean[color]) * 0.5);
413 maxindex = (int)((box->mean[color] + box->high[color]) * 0.5);
414
415 cutpoint = minindex;
416 optweight = box->weight;
417
418 curweight = 0;
419 for (i = box->low[color] ; i < minindex ; i++)
420 curweight += box->freq[color][i];
421 u = 0.0f;
422 max = -1.0f;
423 for (i = minindex; i <= maxindex ; i++) {
424 curweight += box->freq[color][i];
425 if (curweight == box->weight)
426 break;
427 u += (float)(i * box->freq[color][i]) /
428 (float)box->weight;
429 v = ((float)curweight / (float)(box->weight-curweight)) *
430 (box->mean[color]-u)*(box->mean[color]-u);
431 if (v > max) {
432 max = v;
433 cutpoint = i;
434 optweight = curweight;
435 }
436 }
437 cutpoint++;
438 *newbox1 = *newbox2 = *box;
439 newbox1->weight = optweight;
440 newbox2->weight -= optweight;
441 newbox1->high[color] = cutpoint;
442 newbox2->low[color] = cutpoint;
443 UpdateFrequencies(newbox1, newbox2);
444 BoxStats(newbox1);
445 BoxStats(newbox2);
446
447 return TRUE; /* Found cutpoint. */
448}
449
450/*
451 * Update projected frequency arrays for two boxes which used to be
452 * a single box.
453 */
454
455static void
456UpdateFrequencies(Box *box1, Box *box2)
457{
458 ulong myfreq, *h;
459 int b, g, r;
460 int roff;
461
462 bzero(box1->freq[0], ColormaxI * sizeof(ulong));
463 bzero(box1->freq[1], ColormaxI * sizeof(ulong));
464 bzero(box1->freq[2], ColormaxI * sizeof(ulong));
465
466 for (r = box1->low[0]; r < box1->high[0]; r++) {
467 roff = r << NBITS;
468 for (g = box1->low[1];g < box1->high[1]; g++) {
469 b = box1->low[2];
470 h = Histogram + (((roff | g) << NBITS) | b);
471 for (; b < box1->high[2]; b++) {
472 if ((myfreq = *h++) == 0)
473 continue;
474 box1->freq[0][r] += myfreq;
475 box1->freq[1][g] += myfreq;
476 box1->freq[2][b] += myfreq;
477 box2->freq[0][r] -= myfreq;
478 box2->freq[1][g] -= myfreq;
479 box2->freq[2][b] -= myfreq;
480 }
481 }
482 }
483}
484
485/*
486 * Compute RGB to colormap index map.
487 */
488
489static void
490ComputeRGBMap(Box *boxes, int colors, uchar *rgbmap)
491{
492 int i;
493
494 /*
495 * The centroid of each box serves as the representative
496 * for each color in the box.
497 */
498 for (i = 0; i < colors; i++)
499 SetRGBmap(i, &boxes[i], rgbmap);
500}
501
502/*
503 * Make the centroid of "boxnum" serve as the representative for
504 * each color in the box.
505 */
506static void
507SetRGBmap(int boxnum, Box *box, uchar *rgbmap)
508{
509 int r, g, b;
510
511 for (r = box->low[REDI]; r < box->high[REDI]; r++) {
512 for (g = box->low[GREENI]; g < box->high[GREENI]; g++) {
513 for (b = box->low[BLUEI]; b < box->high[BLUEI]; b++) {
514 int index;
515
516 index = (((r<<NBITS)|g)<<NBITS)|b;
517 rgbmap[index]=(char)boxnum;
518 }
519 }
520 }
521}
522
523/* ---------------------------------------------------------------------- */
524
525unsigned char _txPixTrueToFixedPal( void *pix, const FxU32 *pal )
526{
527 int i;
528 long min_dist;
529 int min_index;
530 long r, g, b;
531
532 min_dist = 256 * 256 + 256 * 256 + 256 * 256;
533 min_index = -1;
534 /* 0 1 2 */
535 r = ( long )( ( unsigned char * )pix )[2];
536 g = ( long )( ( unsigned char * )pix )[1];
537 b = ( long )( ( unsigned char * )pix )[0];
538
539 for( i = 0; i < 256; i++ )
540 {
541 long palr, palg, palb, dist;
542 long dr, dg, db;
543
544 palr = ( long )( ( pal[i] & 0x00ff0000 ) >> 16 );
545 palg = ( long )( ( pal[i] & 0x0000ff00 ) >> 8 );
546 palb = ( long )( pal[i] & 0x000000ff );
547 dr = palr - r;
548 dg = palg - g;
549 db = palb - b;
550 dist = dr * dr + dg * dg + db * db;
551 if( dist < min_dist )
552 {
553 min_dist = dist;
554 min_index = i;
555 }
556 }
557
558 if( min_index < 0 )
559 txPanic( "_txPixTrueToFixedPal: this shouldn't happen\n" );
560
561 // printf( "%d\n", ( max_index ) );
562 return ( unsigned char )min_index;
563}
564
565void _txImgTrueToFixedPal( unsigned char *dst, unsigned char *src, const FxU32 *pal,
566 int w, int h, FxU32 flags )
567{
568 long i;
569
570 for( i = 0; i < w * h; i++ )
571 {
572 if( flags == TX_FIXED_PAL_QUANT_TABLE )
573 {
574 unsigned long index;
575 unsigned long r_index, g_index, b_index;
576
577 r_index = ( ( ( unsigned long )src[i*4+2] ) >> ( 8 - INVERSE_PAL_R_BITS ) );
578 g_index = ( ( ( unsigned long )src[i*4+1] ) >> ( 8 - INVERSE_PAL_G_BITS ) );
579 b_index = ( ( ( unsigned long )src[i*4+0] ) >> ( 8 - INVERSE_PAL_B_BITS ) );
580 index =
581 ( r_index << ( INVERSE_PAL_G_BITS + INVERSE_PAL_B_BITS ) ) |
582 ( g_index << INVERSE_PAL_B_BITS ) |
583 b_index;
584 dst[i] = inverse_pal[index];
585 }
586 else
587 {
588 dst[i] = _txPixTrueToFixedPal( &src[i*4], pal );
589 }
590 }
591}
592
593void _CreateInversePal( const FxU32 *pal )
594{
595 long r, g, b;
596 long index = 0;
597 unsigned char true_color[4];
598
599 true_color[3] = 0;
600 for( r = 0; r < ( 1 << INVERSE_PAL_R_BITS ); r++ )
601 for( g = 0; g < ( 1 << INVERSE_PAL_G_BITS ); g++ )
602 for( b = 0; b < ( 1 << INVERSE_PAL_B_BITS ); b++ )
603 {
604 true_color[2] = ( unsigned char )( r << ( 8 - INVERSE_PAL_R_BITS ) );
605 true_color[1] = ( unsigned char )( g << ( 8 - INVERSE_PAL_G_BITS ) );
606 true_color[0] = ( unsigned char )( b << ( 8 - INVERSE_PAL_B_BITS ) );
607 inverse_pal[index] = _txPixTrueToFixedPal( ( void * )true_color, pal );
608 index++;
609 }
610}
611
612/*
613 * Convert an image from true color to a predefined palette.
614 */
615void txMipTrueToFixedPal( TxMip *outputMip, TxMip *trueColorMip, const FxU32 *pal,
616 FxU32 flags )
617{
618 int i, w, h;
619 static FxU32 last_pal[256];
620 static FxBool been_here = FXFALSE;
621
622 w = outputMip->width;
623 h = outputMip->height;
624
625 if( flags == TX_FIXED_PAL_QUANT_TABLE )
626 {
627 if( !been_here || ( memcmp( last_pal, pal, sizeof( FxU32 ) * 256 ) != 0 ) )
628 {
629 memcpy( last_pal, pal, sizeof( FxU32 ) * 256 );
630 _CreateInversePal( pal );
631 been_here = FXTRUE;
632 }
633 }
634
635 for( i = 0; i < trueColorMip->depth; i++ )
636 {
637 _txImgTrueToFixedPal( outputMip->data[i], trueColorMip->data[i], pal,
638 w, h, flags );
639 if (w > 1) w >>= 1;
640 if (h > 1) h >>= 1;
641 }
642}
Note: See TracBrowser for help on using the repository browser.