home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / Assembler / dse-src3.dms / in.adf / Source / Vectors / Dithering / Quantize.lha / quantize.h < prev    next >
Encoding:
C/C++ Source or Header  |  1993-01-06  |  7.1 KB  |  252 lines
  1. /*----------------------------------------------------------------------
  2.  * split up color space for quantize program
  3.  *----------------------------------------------------------------------
  4.  */
  5.  
  6. #include <stdio.h>
  7. #include <std.h>
  8. #include "quantize.h"
  9.  
  10. /* Pick your choice of algorithm: */
  11. /* MIDPOINT_CUT or POPULARITY */
  12. /* (Choose in makefile) */
  13.  
  14. #ifdef MIDPOINT_CUT
  15.  
  16. typedef unsigned int color_index_t;
  17.  
  18. /* My method here is to allocate a clist array big enough for all the
  19.  * possible colors, and then recursively split it.  Since the recursion
  20.  * is depth-first and we're building a LIST, not a TREE of boxes, we can
  21.  * scramble the colors within a parent box because that parent won't be used
  22.  * any more.  We end up with a list of boxes into which all the existing
  23.  * colors are partitioned, as described in Heckbert's paper.
  24.  */
  25. struct Box {
  26.     struct Box *next;
  27.     int rmin, rmax, gmin, gmax, bmin, bmax;
  28.     color_index_t *clist;    /* an array of color indices */
  29.     int clist_len;        /* how many cindexes in the list */
  30. };
  31.  
  32. static int nboxes, maxboxes;    /* number of boxes so far and max needed */
  33.  
  34. MakeCmap(hist, cmap, cmaplen)
  35. unsigned int *hist;
  36. cmap_t *cmap;
  37. int cmaplen;
  38. {
  39.     register int i;
  40.     struct Box *box;
  41.     nboxes = 1;
  42.     maxboxes = cmaplen;
  43.     NEW(box, struct Box, 1);
  44.     dbug0("Making color boxes.\n");
  45.     MakeTopBox(box, hist);    /* Make the first (top-level) box */
  46.     while (nboxes < maxboxes)
  47.         SplitBoxes(box);
  48.     FindColors(box, cmap, cmaplen);
  49. }
  50.  
  51. MakeTopBox(box, hist)        /* Make the top box from the histogram */
  52. struct Box *box;
  53. color_index_t *hist;
  54. {
  55.     register int i;
  56.     ASSERT(box != NULL);
  57.     ASSERT(hist != NULL);
  58.     
  59.     /* Allocate enough color cells to hold all the colors */
  60.     NEW(box->clist, color_index_t, HIST_SIZE);
  61.     box->clist_len = 0;
  62.     box->next = NULL;
  63.     /* For each possible rgb color */
  64.     for (i = 0; i < HIST_SIZE; i++)
  65.     {
  66.     if (hist[i] > 0)    /* if any pixels are that color, */
  67.         box->clist[box->clist_len++] = i;
  68.     }
  69.     Compact(box);
  70.     fprintf(stderr,"Top box at 0x%x: %d colors, R (%d -> %d)  G (%d -> %d)  B (%d -> %d)\n",
  71.         box, box->clist_len,
  72.         box->rmin, box->rmax, box->gmin, box->gmax, box->bmin, box->bmax);
  73. }
  74.  
  75. /* Shrink the box limits until it just encloses the points within it. */
  76. Compact(box)
  77. struct Box *box;
  78. {
  79.     register int i;
  80.     ASSERT(box != NULL);
  81.     box->rmin = 256;
  82.     box->gmin = 256;
  83.     box->bmin = 256;    /* Greater than any value */
  84.     box->rmax = -1;
  85.     box->gmax = -1;
  86.     box->bmax = -1;    /* Less than any rgb value */
  87.     for (i = box->clist_len-1; i >= 0; i--)
  88.     {
  89.     int r = (box->clist[i] >> 10) & 0x1f; /* colors associated with 'i' */
  90.     int g = (box->clist[i] >> 5) & 0x1f;
  91.     int b = (box->clist[i]) & 0x1f;
  92.     /* Expand the box until it just fits the colors tightly */
  93.     if (r < box->rmin) box->rmin = r;
  94.     if (g < box->gmin) box->gmin = g;
  95.     if (b < box->bmin) box->bmin = b;
  96.     if (r > box->rmax) box->rmax = r;
  97.     if (g > box->gmax) box->gmax = g;
  98.     if (b > box->bmax) box->bmax = b;
  99.     }
  100. }
  101.  
  102. /* Split all the boxes once each, stop if we've got enough */
  103. SplitBoxes(box)
  104. struct Box *box;
  105. {
  106.     struct Box *nextbox;
  107.     dbug1("Splitting all the boxes with %d done so far.\n", nboxes);
  108.     while (box != NULL && nboxes < maxboxes)
  109.     {
  110.     nextbox = box->next;
  111.     SplitBox(box);        /* SplitBox changes box->next! */
  112.     box = nextbox;
  113.     }
  114. }
  115.  
  116. static char longdim;        /* char representing the longest dimension */
  117.  
  118. int
  119. CompareColors(c1, c2)
  120. color_index_t *c1, *c2;
  121. {
  122.     switch (longdim)
  123.     {
  124.       case 'r':
  125.     return ((*c1 >> 10 & 0x1f) - (*c2 >> 10 & 0x1f));
  126.       case 'g':
  127.     return ((*c1 >> 5 & 0x1f) - (*c2 >> 5 & 0x1f));
  128.       case 'b':
  129.     return ((*c1 & 0x1f) - (*c2 & 0x1f));
  130.       default:
  131.     fprintf(stderr,"Illegal longdim 0x%x in CompareColors.\n", longdim);
  132.     exit(1);
  133.     }
  134. }
  135.  
  136. /* Divide the box across its longest dimension at its median point
  137.  * This is NOT recursive - we split all the boxes once, then if there's
  138.  * more colors to be assigned we split all of them again, and so on. */
  139. SplitBox(box)
  140. struct Box *box;
  141. {
  142.     struct Box *newbox;        /* the 'other half' of the split box */
  143.     ASSERT(box != NULL);
  144.     if (nboxes > maxboxes) return;
  145.     if (box->clist_len <= 1) return;
  146.     nboxes++;
  147.     if (box->rmax - box->rmin >= box->gmax - box->gmin &&
  148.     box->rmax - box->rmin >= box->bmax - box->bmin)
  149.     longdim = 'r';
  150.     else
  151.     if (box->gmax - box->gmin >= box->rmax - box->rmin &&
  152.     box->gmax - box->gmin >= box->bmax - box->bmin)
  153.     longdim = 'g';
  154.     else
  155.     if (box->bmax - box->bmin >= box->gmax - box->gmin &&
  156.     box->bmax - box->bmin >= box->rmax - box->rmin)
  157.     longdim = 'b';
  158.     else
  159.     {
  160.     fprintf(stderr,"No longest dimension in SplitBox??!\n");
  161.         fprintf(stderr,"This box: R (%d -> %d)  G (%d -> %d)  B (%d -> %d)\n",
  162.         box->rmin, box->rmax, box->gmin, box->gmax, box->bmin, box->bmax);
  163.     exit(1);
  164.     }
  165.     qsort(box->clist, box->clist_len, sizeof(color_index_t), CompareColors);
  166.     /* Set up the new box and put it after the old box */
  167.     NEW(newbox, struct Box, 1);
  168.     newbox->next = box->next;
  169.     box->next = newbox;
  170.     /* If len is odd, put the extra one in the old box */
  171.     newbox->clist_len = box->clist_len / 2;
  172.     box->clist_len -= newbox->clist_len;
  173.     newbox->clist = box->clist + box->clist_len;
  174.     Compact(box);
  175.     Compact(newbox);
  176. }
  177.  
  178. /* Find the representative color in each box and put it into cmap. */
  179. FindColors(box, cmap, cmaplen)    /* here box is a list of boxes */
  180. struct Box *box;
  181. cmap_t *cmap;
  182. int cmaplen;
  183. {
  184.     register int r, g, b;
  185.     register int i;
  186.     int cml = 0;
  187.     while (box != NULL)
  188.     {
  189.     r = 0, g = 0, b = 0;
  190.     for (i=0; i < box->clist_len; i++)
  191.     {
  192.         r += (box->clist[i] >> 10 & 0x1f) << 3;
  193.         g += (box->clist[i] >> 5 & 0x1f) << 3;
  194.         b += (box->clist[i] & 0x1f) << 3;
  195.     }
  196.     ASSERT(r/box->clist_len < 256);
  197.     ASSERT(g/box->clist_len < 256);
  198.     ASSERT(b/box->clist_len < 256);
  199.     cmap[cml*3] = r / box->clist_len;
  200.     cmap[cml*3+1] = g / box->clist_len;
  201.     cmap[cml*3+2] = b / box->clist_len;
  202.     box = box->next;
  203.     cml++;
  204.     }
  205.     ASSERT(cmaplen == cml);    /* since there should be 'cmaplen' boxes */
  206.     for (i = 0; i < cmaplen*3; i+=3)
  207.     {
  208.     printf("Cmap[%4d] = %3d, %3d, %3d\n",
  209.        i/3, cmap[i], cmap[i+1], cmap[i+2]);
  210.     }
  211. }
  212.  
  213. #endif
  214.  
  215. #ifdef POPULARITY
  216. static unsigned int *HiSt;
  217.  
  218. CompareHist(v1, v2)
  219. int *v1, *v2;
  220. {
  221.     return (HiSt[*v2] - HiSt[*v1]);
  222. }
  223.  
  224. MakeCmap(hist, cmap, cmaplen)
  225. unsigned int *hist;
  226. cmap_t *cmap;
  227. int cmaplen;
  228. {
  229.     register int i;
  230.     unsigned int *hptrs;
  231.     /* This is the popularity algorithm (Boyle & Lippman, Archmac, 1978) */
  232.     /* First we sort the histogram: set up a bunch of pointers and sort them */
  233.     dbug1("Getting %d ints for hptrs...", HIST_SIZE);
  234. /*  NEW(hptrs, unsigned int, HIST_SIZE);*/
  235.     hptrs = (unsigned int *)quant_image;    /* use existing storage temporarily */
  236.     dbug0("initting it...");
  237.     for (i = 0; i < HIST_SIZE; i++) hptrs[i] = i;
  238.     HiSt = hist;
  239.     dbug0("Sorting...");
  240.     qsort (hptrs, HIST_SIZE, sizeof(unsigned int), CompareHist);
  241.     dbug0("making color map...");
  242.     for (i = 0; i < cmaplen; i++)
  243.     {
  244.     cmap[3*i] = hptrs[i] >> 10 << 3;
  245.     cmap[3*i+1] = (hptrs[i] >> 5 & 0x1f) << 3;
  246.     cmap[3*i+2] = (hptrs[i] & 0x1f) << 3;
  247.     }
  248.     dbug0("done.\n");
  249.     dbug1("Max pixels in one bucket: %d.\n", hist[hptrs[0]]);
  250. }
  251. #endif POPULARITY
  252.