home *** CD-ROM | disk | FTP | other *** search
/ Nebula 1 / Nebula One.iso / Graphics / Viewers / aa_m68k_Intel_Only / ToyViewer1.2 / Source / getmap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1995-11-12  |  10.4 KB  |  450 lines
  1. /*
  2.     getmap.c
  3.         1995-07-02
  4.         by T.Ogihara (ogihara@seg.kobe-u.ac.jp)
  5.  
  6.         Checks number of color used in the image.
  7.         Reduces color by median cut algorithm (MCA) of Paul Heckbert.
  8.         This code refers to "ppmquant" of Jef Poskanzer, but, in
  9.         many cases, this program could generate more beautiful image.
  10. */
  11.  
  12.  
  13. #include <stdlib.h>
  14. #include <string.h>
  15. #include <appkit/color.h>
  16. #include "common.h"
  17. #include "save.h"
  18.  
  19. #define  EnoughMemory    1
  20.  
  21. #if EnoughMemory
  22. # define  COLORSTEPS        65536    /* = 0x10000 */
  23. # define  MAXColors        62000    /* < COLORSTEPS */
  24. # define  ColorHash(r,g,b)    ( ((r)<<8) | (g) )    /* Hash KEY */
  25. # define  ColorHnew(x)        (((x) + 5987) & 0xffff)
  26.   typedef int indexint;
  27. #else
  28. # define  COLORSTEPS        32768    /* = 32 ^ 3 = 0x8000 */
  29. # define  MAXColors        30000    /* < COLORSTEPS */
  30. # define  ColorHash(r,g,b)    ( ((r)<<7) | ((g) & 0x7f) )    /* Hash KEY */
  31. # define  ColorHnew(x)        (((x) + 5987) & 0x7fff)
  32.   typedef short indexint;
  33. #endif
  34.  
  35. typedef struct {
  36.     int     count;
  37.     unsigned char red, green, blue;
  38.     unsigned char palidx;    /* index for palette */
  39. } tabcell;
  40.  
  41. typedef struct {
  42.     int index, colors;
  43.     int sum;
  44. } element;
  45.  
  46. /* quick sort */
  47. static int q_red(int);
  48. static int q_green(int);
  49. static int q_blue(int);
  50. static int q_colors(int);
  51. static int q_count(int);
  52. static int q_palette(int);
  53. static void inssort(int, indexint *, int (*)(int));
  54. static void quicksort(int, indexint *, int (*)(int));
  55.  
  56. static tabcell *hashtab = NULL;
  57. static indexint *pindex = NULL;
  58. static paltype *pal = NULL;
  59. static int colornum, totalnum;
  60. static float darkfactor = 0.0;
  61. static int darken = 0;
  62.  
  63.  
  64. static int hashIndex(int r, int g, int b)
  65. {
  66.     tabcell *tp;
  67.     int x = ColorHash(r,g,b);
  68.  
  69.     tp = &hashtab[x];
  70.     while (tp->count > 0
  71.         && (tp->red != r || tp->green != g || tp->blue != b))
  72.         tp = &hashtab[x = ColorHnew(x)];
  73.     if (tp->count == 0) {
  74.         tp->red = r;
  75.         tp->green = g;
  76.         tp->blue = b;
  77.         colornum++;
  78.     }
  79.     tp->count++;
  80.     return x;
  81. }
  82.  
  83. void free256map(void)
  84. {
  85.     if (hashtab) free((void *)hashtab);
  86.     hashtab = NULL;
  87.     if (pindex) free((void *)pindex);
  88.     pindex = NULL;
  89.     if (pal) free((void *)pal);
  90.     pal = NULL;
  91. }
  92.  
  93. int getAllColor(int *cnum, unsigned char **map)
  94.     /* »¨⁄õ⁄ò⁄˘⁄⁄⁄º¿§¿û⁄ù cnum⁄¸˘⁄ò⁄º¡£
  95.        ¿§¿û⁄‹´¿⁄„⁄fi⁄˘¿û⁄¤⁄Ø⁄ò⁄˚⁄⁄»⁄ˇ COLORSTEPS ⁄‹ cnum ⁄¸˘⁄Œ¡¢
  96.        ˚±¿û colornum ⁄ˇ£®⁄¸¥»¥ˆ¥¨⁄¦⁄ò⁄º¡£
  97.        ˚á⁄Œˆ˝⁄ˇ¥¤¥Ø¡…⁄ù²‰⁄„¡£ */
  98. {
  99.     int r, g, b, i;
  100.  
  101.     if (hashtab == NULL) {
  102.         if ((hashtab = (tabcell *)calloc(COLORSTEPS, sizeof(tabcell))) == NULL
  103.         || (pindex = (indexint *)calloc(COLORSTEPS, sizeof(indexint))) == NULL
  104.         || (pal = (paltype *)calloc(FIXcount, sizeof(paltype))) == NULL) {
  105.         free256map();
  106.         *cnum = 0;
  107.         return Err_MEMORY;
  108.         }
  109.     }
  110.     for (i = 0; i < COLORSTEPS; i++)
  111.         pindex[i] = i;
  112.  
  113.     resetPixel(map, 0);
  114.     colornum = 0;
  115.     while (getPixel(&r, &g, &b) >= 0) {
  116.         (void) hashIndex(r,g,b);
  117.         if (colornum >= MAXColors) { /* Too many color */
  118.             *cnum = COLORSTEPS;
  119.             colornum = 0;
  120.             return 0;
  121.         }
  122.     }
  123.     *cnum = colornum;
  124.     return 0;
  125. }
  126.  
  127. int getAllPalColor(void)
  128.     /* ¥±¥ò¥ˆ¥¨⁄˛ˆð⁄˛¿§⁄ù˜·⁄ä¡¢¥ˇ¥ˆ¥•¥ï²‰⁄¸¯—ˇ¿⁄•⁄˘⁄“⁄fl¡£ */
  129. {
  130.     int r, g, b, i;
  131.  
  132.     pal = NULL;
  133.     pindex = NULL;
  134.     if (hashtab == NULL) {
  135.         hashtab = (tabcell *)calloc(COLORSTEPS, sizeof(tabcell));
  136.         if (hashtab == NULL) {
  137.         free256map();
  138.         return Err_MEMORY;
  139.         }
  140.     }
  141.     colornum = 0;
  142.     darken = 0;
  143.     for (i = 0; getPalPixel(&r, &g, &b) >= 0; i++)
  144.         hashtab[hashIndex(r,g,b)].palidx = i;
  145.     return 0;
  146. }
  147.  
  148.  
  149. paltype *getNormalmap(int *cnum)
  150.     /* getAllColor() ⁄˛‚ï⁄˙»¨⁄⁄¡¢¥±¥ò¥ˆ¥¨⁄ù˚á⁄„¡£
  151.        »¨⁄õ⁄ò⁄˘⁄⁄⁄º¿§⁄‹ 256¿§®˚˘í⁄˙⁄¢⁄º⁄‡⁄¨¡£ */
  152. {
  153.     unsigned char *p;
  154.     tabcell *t;
  155.     int i, x, num;
  156.  
  157.     quicksort(COLORSTEPS, pindex, q_colors);
  158.     for (i = 0, num = 0; i < COLORSTEPS && num < FIXcount; i++) {
  159.         if (hashtab[x = pindex[i]].count == 0) continue;
  160.         t = &hashtab[x];
  161.         p = pal[num];
  162.         p[RED]   = t->red;
  163.         p[GREEN] = t->green;
  164.         p[BLUE]  = t->blue;
  165.         t->palidx = num++;
  166.     }
  167.     darken = 0;
  168.     *cnum = num;
  169.     return pal;
  170. }
  171.  
  172. int reduce_bright(int *cnum, float *bright, unsigned char **map)
  173.     /* getAllColor() ⁄˛‚ï⁄˙»¨⁄ƒ¡£³¹⁄º⁄¦⁄ù‚”⁄Ø⁄•⁄˘¿§⁄ù˘²⁄ë„⁄똬⁄„¡£
  174.        *bright ⁄‹ 0.0 ⁄˚⁄Ø”˙‰Ø⁄˛»ô„¾⁄¹⁄‹¡¢⁄‰⁄ò®˚‡®⁄˚⁄Ø⁄—‚”¿§⁄˛•«⁄Œ˚á⁄•
  175.        ⁄˛¯½ˆð⁄˙⁄¢⁄º¡£⁄‡⁄ò⁄ˇ¡¢¯½ˆð⁄˙•—†Æ˚ú„ö⁄ù„¾⁄ƒ⁄¿⁄Æ⁄˙⁄¢⁄º¡£
  176.        …”˙¾⁄•⁄¿⁄Ø¡¢*bright⁄¸…¡†ú⁄˛¥±¥Ø¥Æ¡…¥¿⁄ù˘⁄ò¡¢£®⁄ù˚á⁄„¡£*/
  177. {
  178.     int r, g, b;
  179.     static float fact[] = {
  180.         0.0, 1.0, 0.96, 0.875, 0.75, 0.625, 0.5,
  181.         0.4, 0.3, 0.25, 0.2, 0.16667, 0.13333, 0.1, 0.0 };
  182.  
  183.     if (*bright < 0.01) { /* == 0.0 */
  184.         *bright = fact[darken = 1];
  185.         return 0;
  186.     }
  187.     darkfactor = fact[darken];
  188.     bzero((void *)hashtab, sizeof(tabcell)*COLORSTEPS);
  189.     resetPixel(map, 0);
  190.     colornum = 0;
  191.     totalnum = 0;
  192.     while (getPixel(&r, &g, &b) >= 0) {
  193.         r = (int)(r * darkfactor + 0.9) & 0xfe;
  194.         g = (int)(g * darkfactor + 0.9) & 0xfe;
  195.         b = (int)(b * darkfactor + 0.9) & 0xfe;
  196.         (void) hashIndex(r,g,b);
  197.         totalnum++;
  198.         if (colornum >= MAXColors) { /* Too many color */
  199.             colornum = 0;
  200.             *bright = fact[++darken];
  201.             return 0;
  202.         }
  203.     }
  204.     *bright = 0.0;
  205.     return 1;
  206. }
  207.  
  208. int mapping(int r, int g, int b)
  209. {
  210.     if (darken) {
  211.         r = (int)(r * darkfactor + 0.9) & 0xfe;
  212.         g = (int)(g * darkfactor + 0.9) & 0xfe;
  213.         b = (int)(b * darkfactor + 0.9) & 0xfe;
  214.     }
  215.     return hashtab[hashIndex(r,g,b)].palidx;
  216. }
  217.  
  218.  
  219. static void SortMaxElement(int indx, int clrs)
  220. {
  221.     int i, j, end;
  222.     unsigned short min[3], max[3], val[3];
  223.     float bright[3];
  224.     tabcell *t;
  225.  
  226.     /* Find the minimum and maximum of each component */
  227.     for (i = 0; i < 3; i++)
  228.         min[i] = 255, max[i] = 0;
  229.     end = indx + clrs;
  230.     for (i = indx; i < end; i++) {
  231.         t = &hashtab[pindex[i]];
  232.         if (t->count == 0)
  233.             continue;
  234.         val[RED]   = t->red;
  235.         val[GREEN] = t->green;
  236.         val[BLUE]  = t->blue;
  237.         for (j = 0; j < 3; j++) {
  238.             if (min[j] > val[j]) min[j] = val[j];
  239.             if (max[j] < val[j]) max[j] = val[j];
  240.         }
  241.     }
  242.     /* calculate brightness */
  243.     bright[RED] = (max[RED] - min[RED]) * 0.299;
  244.     bright[GREEN] = (max[GREEN] - min[GREEN]) * 0.587;
  245.     bright[BLUE] = (max[BLUE] - min[BLUE]) * 0.114;
  246.     if ( bright[RED] >= bright[GREEN] && bright[RED] >= bright[BLUE] )
  247.         quicksort(clrs, &pindex[indx], q_red);
  248.     else if ( bright[GREEN] >= bright[BLUE] )
  249.         quicksort(clrs, &pindex[indx], q_green);
  250.     else
  251.         quicksort(clrs, &pindex[indx], q_blue);
  252. }
  253.  
  254. static void makepalette(element *elm, int cellnum)
  255. {
  256.     int indx, clrs, i, ex, best;
  257.     long r, g, b, w, sum;
  258.     unsigned char *p;
  259.     tabcell *t;
  260.  
  261.     for (ex = 0; ex < cellnum; ex++) {
  262.         indx = elm[ex].index;
  263.         clrs = elm[ex].colors;
  264.         r = g = b = 0, sum = 0;
  265.         p = pal[ex];
  266.     
  267.         w = indx + clrs;
  268.         for (i = indx; i < w; i++) {
  269.         int c = (t = &hashtab[pindex[i]])->count;
  270.         r += t->red * c;
  271.         g += t->green * c;
  272.         b += t->blue * c;
  273.         sum += c;
  274.         }
  275.         p[RED]   = ((r /= sum) < 256) ? r : 255;
  276.         p[GREEN] = ((g /= sum) < 256) ? g : 255;
  277.         p[BLUE]  = ((b /= sum) < 256) ? b : 255;
  278.     }
  279.     /* Values of pindex[] are not used any more.
  280.        Sort the palette. */
  281.     for (i = 0; i < cellnum; i++)
  282.         pindex[i] = i;
  283.     quicksort(cellnum, pindex, q_palette);
  284.     for (ex = 0; ex < cellnum; ex++) {
  285.         unsigned char *q;
  286.         int x, y;
  287.         x = pindex[ex];
  288.         if (ex == x) continue;
  289.         for (y = ex+1; y < cellnum; y++)
  290.             if (pindex[y] == ex) break;
  291.         p = pal[x];
  292.         q = pal[ex];
  293.         for (i = 0; i < 3; i++)
  294.             r = p[i], p[i] = q[i], q[i] = r;
  295.         pindex[ex] = ex;
  296.         pindex[y] = x;
  297.     }
  298.     
  299.     for (i = 0; i < COLORSTEPS; i++) {
  300.         if (hashtab[i].count == 0) continue;
  301.         t = &hashtab[i];
  302.         r = t->red;
  303.         g = t->green;
  304.         b = t->blue;
  305.         w = 4 * 256 * 256;
  306.         best = 0;
  307.         for (ex = 0; ex < cellnum; ex++) {
  308.             long rr, gg, bb;
  309.             p = pal[ex];
  310.             rr = r - p[RED];
  311.             gg = g - p[GREEN];
  312.             bb = b - p[BLUE];
  313.             if ((sum = rr*rr + gg*gg + bb*bb) < w)
  314.                 w = sum, best = ex;
  315.         }
  316.         t->palidx = best;
  317.     }
  318. }
  319.  
  320. paltype *get256map(int *cnum)
  321. {
  322.     int i, w;
  323.     element elm[FIXcount];
  324.     int elmptr, curelm;
  325.     int indx, clrs, sm;
  326.     int halfsum, lowersum;
  327.  
  328.     quicksort(COLORSTEPS, pindex, q_count);
  329.     for (i = 0; i < COLORSTEPS; i++)
  330.         if (hashtab[pindex[i]].count) break;
  331.     elm[0].index = i;
  332.     elm[0].colors = COLORSTEPS - i;
  333.     elm[0].sum = totalnum;
  334.     elmptr = 1;
  335.     
  336.     while (elmptr < FIXcount) {
  337.         /* Find largest element */
  338.         curelm = -1;
  339.         w = 2;    /* should be divided */
  340.         for (i = 0; i < elmptr; i++) {
  341.         if (elm[i].colors >= w)
  342.             w = elm[curelm = i].colors;
  343.         }
  344.         if (curelm < 0)
  345.         break;    /* all color was found */
  346.         indx = elm[curelm].index;
  347.         clrs = elm[curelm].colors;
  348.         sm = elm[curelm].sum;
  349.         SortMaxElement(indx, clrs);
  350.  
  351.         /* Find the median */
  352.         w = clrs - 1;
  353.         lowersum = 0;
  354.         halfsum = sm / 2;
  355.         for (i = 0; i < w && lowersum < halfsum; i++)
  356.         lowersum += hashtab[pindex[indx + i]].count;
  357.     
  358.         /* Divide the box */
  359.         elm[curelm].colors = i;
  360.         elm[curelm].sum = lowersum;
  361.         elm[elmptr].index = indx + i;
  362.         elm[elmptr].colors = clrs - i;
  363.         elm[elmptr].sum = sm - lowersum;
  364.         ++elmptr;
  365.     }
  366.  
  367.     makepalette(elm, elmptr);
  368.     *cnum = elmptr;
  369.     return pal;
  370. }
  371.  
  372. /* ----------------------------------------------------------------
  373.     QUICK SORT by Haruhiko Okumura
  374.     –þ´…¹†²§¡á£ˆ‚¹‚ò⁄¸⁄Ł⁄º”˙¿•¥¢¥º¥·¥Œ¥”¥ì»ü¯¦¡â¡˚¦»‰±²¬ˇ¹…¼¡¸
  375.     modified by T. Ogihara
  376. ----------------------------------------------------------------- */
  377.  
  378. static int q_red(int x) { return hashtab[x].red; }
  379. static int q_green(int x) { return hashtab[x].green; }
  380. static int q_blue(int x) { return hashtab[x].blue; }
  381. static int q_count(int x) { return hashtab[x].count; }
  382. static int q_colors(int x) {
  383.     tabcell *t = &hashtab[x];
  384.     return (t->count)
  385.         ? ((t->red << 16) | (t->green << 8) | t->blue) : 0;
  386. }
  387. static int q_palette(int x) {
  388.     unsigned char *p = pal[x];
  389.     return ((p[RED] << 16) | (p[GREEN] << 8) | p[BLUE]);
  390. }
  391.  
  392. static void inssort(int n, indexint *a, int (*qval)(int))
  393. {
  394.     int i, j, val;
  395.     indexint x;
  396.  
  397.     for (i = 1; i < n; i++) {
  398.         val = qval(x = a[i]);
  399.         for (j = i - 1; j >= 0 && qval(a[j]) > val; j--)
  400.             a[j + 1] = a[j];
  401.         a[j + 1] = x;
  402.     }
  403. }
  404.  
  405. #define THRESHOLD 10
  406. #define STACKSIZE 32  /* ⁄¿⁄«⁄¹⁄« int ⁄˛¥½¥ˆ¥¨¿û˜ł¯ä */
  407.  
  408. static void quicksort(int n, indexint *ar, int (*qval)(int))
  409. {
  410.     int i, j, left, right, p;
  411.     int leftstack[STACKSIZE], rightstack[STACKSIZE];
  412.     indexint t;
  413.     int x;
  414.  
  415.     left = 0;  right = n - 1;  p = 0;
  416.     for ( ; ; ) {
  417.         if (right - left <= THRESHOLD) {
  418.             if (p == 0) break;
  419.             p--;
  420.             left = leftstack[p];
  421.             right = rightstack[p];
  422.         }
  423.         x = qval(ar[(left + right) / 2]);
  424.         i = left;  j = right;
  425.         for ( ; ; ) {
  426.             while (qval(ar[i]) < x) i++;
  427.             while (x < qval(ar[j])) j--;
  428.             if (i >= j) break;
  429.             t = ar[i];  ar[i] = ar[j];  ar[j] = t;
  430.             i++;  j--;
  431.         }
  432.         if (i - left > right - j) {
  433.             if (i - left > THRESHOLD) {
  434.                 leftstack[p] = left;
  435.                 rightstack[p] = i - 1;
  436.                 p++;
  437.             }
  438.             left = j + 1;
  439.         } else {
  440.             if (right - j > THRESHOLD) {
  441.                 leftstack[p] = j + 1;
  442.                 rightstack[p] = right;
  443.                 p++;
  444.             }
  445.             right = i - 1;
  446.         }
  447.     }
  448.     inssort(n, ar, qval);
  449. }
  450.