home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / radsrc22 / src / px / closest.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-12  |  3.7 KB  |  136 lines
  1. /* Copyright 1988 Regents of the University of California */
  2.  
  3. #ifndef lint
  4. static char SCCSid[] = "@(#)closest.c 2.1 11/12/91 LBL";
  5. #endif
  6.  
  7. /*
  8. CLOSEST - nearest-color lookup by locally ordered search
  9. we use distance in rgb space as color metric
  10.  
  11. fillbucket subroutine makes trimmed, sorted lists of
  12. possible closest colors to speed the closest searching.
  13. About 6 times faster than exhaustive.
  14.  
  15. Paul Heckbert
  16. */
  17.  
  18. #include "ciq.h"
  19.  
  20. #define inf 3*256*256
  21. #define key(r,g,b) (((r)&0xe0)<<1|((g)&0xe0)>>2|((b)&0xe0)>>5)   
  22.     /* 9-bit hash key: rrrgggbbb */
  23.  
  24. static struct thing {int mindist,pv;} space[512*257],*next,*bucket[512];
  25.                     /* sorted lists of colors */
  26.  
  27. static int nfill,tests,calls;
  28. static char filled[512];        /* has bucket[key] been filled yet? */
  29. static int sq[511];
  30.  
  31. initializeclosest() {            /* reset the buckets */
  32.     int k;
  33.     nfill = tests = calls = 0;
  34.     for (k=0; k<512; k++) filled[k] = 0;
  35.     next = space;
  36. }
  37.  
  38. closest(r,g,b)        /* find pv of colormap color closest to (r,g,b) */
  39. int r,g,b;
  40. {
  41.     register struct thing *p;
  42.     register int *rsq,*gsq,*bsq,dist,min;
  43.     int best,k;
  44.     struct thing *p0;
  45.  
  46.     k = key(r,g,b);
  47.     if (!filled[k]) fillbucket(k);
  48.     min = inf;
  49.     rsq = sq+255-r;
  50.     gsq = sq+255-g;
  51.     bsq = sq+255-b;
  52.  
  53.     /* stop looking when best is closer than next could be */
  54.     for (p0=p=bucket[k]; min>p->mindist; p++) {
  55.     dist = rsq[color[0][p->pv]] + gsq[color[1][p->pv]] +
  56.         bsq[color[2][p->pv]];
  57.     if (dist<min) {
  58.         best = p->pv;
  59.         min = dist;
  60.     }
  61.     }
  62.     tests += p-p0;
  63.     calls++;
  64.     return best;
  65. }
  66.  
  67. #define H 16    /* half-width of a bucket */
  68.  
  69. compare(a,b)
  70. register struct thing *a,*b;
  71. {
  72.     return a->mindist-b->mindist;
  73. }
  74.  
  75. fillbucket(k)    /* make list of colormap colors which could be closest */
  76. int k;        /* matches for colors in bucket #k */
  77. {
  78.     register int r,g,b,j,dist,*rsq,*gsq,*bsq,min,best;
  79.     struct thing *p,*q;
  80.  
  81.     if (!sq[0]) for (j= -255; j<256; j++) sq[j+255] = j*j;
  82.  
  83.     r = k>>1&0xe0|H;            /* center of 32x32x32 cubical bucket */
  84.     g = k<<2&0xe0|H;
  85.     b = k<<5&0xe0|H;
  86.     rsq = sq+255-r;
  87.     gsq = sq+255-g;
  88.     bsq = sq+255-b;
  89.     bucket[k] = p = next;
  90.     min = inf;
  91.  
  92.     for (j=0; j<n; j++, p++) {
  93.     p->pv = j;
  94.     dist = 0;            /* compute distance from cube surface */
  95.          if (color[0][j]< r-H) dist += rsq[color[0][j]+H];
  96.     else if (color[0][j]>=r+H) dist += rsq[color[0][j]-H+1];
  97.          if (color[1][j]< g-H) dist += gsq[color[1][j]+H];
  98.     else if (color[1][j]>=g+H) dist += gsq[color[1][j]-H+1];
  99.          if (color[2][j]< b-H) dist += bsq[color[2][j]+H];
  100.     else if (color[2][j]>=b+H) dist += bsq[color[2][j]-H+1];
  101.     p->mindist = dist;        /* for termination test in closest */
  102.     dist = rsq[color[0][j]]+gsq[color[1][j]]+bsq[color[2][j]];
  103.     if (dist<min) {            /* find color closest to cube center */
  104.         best = j;
  105.         min = dist;
  106.     }
  107.     }
  108.  
  109.     dist = rsq[color[0][best]+(color[0][best]<r?1-H:H)] +
  110.        gsq[color[1][best]+(color[1][best]<g?1-H:H)] +
  111.        bsq[color[2][best]+(color[2][best]<b?1-H:H)];
  112.     /* dist is an upper bound on mindist: maximum possible distance */
  113.     /* between a color in the bucket and its nearest neighbor */
  114.  
  115.     /* eliminate colors which couldn't be closest */
  116.     for (p=q=next, j=0; j<n; j++, p++)
  117.     if (p->mindist<dist) {
  118.         q->mindist = p->mindist;
  119.         q->pv = p->pv;
  120.         q++;
  121.     }
  122.     if (q<=next) fprintf(stderr,"ERROR: empty bucket!\n");
  123.  
  124.     /* and sort the list by mindist */
  125.     qsort(next,q-next,sizeof(struct thing),compare);
  126.     q->mindist = inf;                /* list terminator */
  127.     next = q+1;
  128.     filled[k] = 1;
  129.     nfill++;
  130. }
  131.  
  132. /*endclosest() {
  133.     printf("filled %d buckets, averaging %d colors per list, %d of which were tested\n",
  134.     nfill,(next-space-nfill)/nfill,tests/calls);
  135. }*/
  136.