Back to index

radiance  4R0+20100331
rhd_ctab.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char    RCSid[] = "$Id: rhd_ctab.c,v 3.5 2004/01/01 11:21:55 schorsch Exp $";
00003 #endif
00004 /*
00005  * Allocate and control dynamic color table.
00006  *
00007  *     We start off with a uniform partition of color space.
00008  *     As pixels are sent to the frame buffer, a histogram is built.
00009  *     When a new color table is requested, the histogram is used
00010  *     to make a pseudo-optimal partition, after which the
00011  *     histogram is cleared.  This algorithm
00012  *     performs only as well as the next drawing's color
00013  *     distribution is correlated to the last.
00014  *
00015  *     This module is essentially identical to src/rt/colortab.c,
00016  *     except there is no color mapping, since the tm library is used.
00017  */
00018 
00019 #include <string.h>
00020 
00021 #include "standard.h"
00022 #include "rhdisp.h"
00023 #include "color.h"
00024                             /* histogram resolution */
00025 #define NRED         24
00026 #define NGRN         32
00027 #define NBLU         16
00028 #define HMAX         NGRN
00029                             /* minimum box count for adaptive partition */
00030 #define MINSAMP             7
00031                             /* maximum distance^2 before color reassign */
00032 #define MAXDST2             12
00033                             /* color partition tree */
00034 #define CNODE        short
00035 #define set_branch(p,c) ((c)<<2|(p))
00036 #define set_pval(pv) ((pv)<<2|3)
00037 #define is_branch(cn)       (((cn)&3)!=3)
00038 #define is_pval(cn)  (((cn)&3)==3)
00039 #define part(cn)     ((cn)>>2)
00040 #define prim(cn)     ((cn)&3)
00041 #define pval(cn)     ((cn)>>2)
00042                             /* our color table */
00043 static struct tabent {
00044        long   sum[3];              /* sum of colors using this entry */
00045        int    n;            /* number of colors */
00046        BYTE   ent[3];              /* current table value */
00047 }      *clrtab = NULL;
00048                             /* color cube partition */
00049 static CNODE  *ctree = NULL;
00050                             /* histogram of colors used */
00051 static unsigned short       histo[NRED][NGRN][NBLU];
00052                             /* initial color cube boundary */
00053 static int    CLRCUBE[3][2] = {{0,NRED},{0,NGRN},{0,NBLU}};
00054 
00055 static void cut(CNODE *tree, int level, int box[3][2], int c0, int c1);
00056 static int split(int box[3][2]);
00057 
00058 
00059 
00060 extern int
00061 new_ctab(            /* start new color table with max ncolors */
00062        int    ncolors
00063 )
00064 {
00065        int    treesize;
00066 
00067        if (ncolors < 1)
00068               return(0);
00069                             /* free old tables */
00070        if (clrtab != NULL)
00071               free((void *)clrtab);
00072        if (ctree != NULL)
00073               free((void *)ctree);
00074                             /* get new tables */
00075        for (treesize = 1; treesize < ncolors; treesize <<= 1)
00076               ;
00077        treesize <<= 1;
00078        clrtab = (struct tabent *)calloc(ncolors, sizeof(struct tabent));
00079        ctree = (CNODE *)malloc(treesize*sizeof(CNODE));
00080        if (clrtab == NULL || ctree == NULL)
00081               return(0);
00082                             /* partition color space */
00083        cut(ctree, 0, CLRCUBE, 0, ncolors);
00084                             /* clear histogram */
00085        memset((void *)histo, '\0', sizeof(histo));
00086                             /* return number of colors used */
00087        return(ncolors);
00088 }
00089 
00090 
00091 extern int
00092 get_pixel(    /* get pixel for color */
00093        BYTE   rgb[3],
00094        void   (*set_pixel)(int h, int r, int g, int b)
00095 )
00096 {
00097        int    r, g, b;
00098        int    cv[3];
00099        register CNODE       *tp;
00100        register int  h;
00101                                           /* get desired color */
00102        r = rgb[RED];
00103        g = rgb[GRN];
00104        b = rgb[BLU];
00105                                           /* reduce resolution */
00106        cv[RED] = (r*NRED)>>8;
00107        cv[GRN] = (g*NGRN)>>8;
00108        cv[BLU] = (b*NBLU)>>8;
00109                                           /* add to histogram */
00110        histo[cv[RED]][cv[GRN]][cv[BLU]]++;
00111                                           /* find pixel in tree */
00112        for (tp = ctree, h = 0; is_branch(*tp); h++)
00113               if (cv[prim(*tp)] < part(*tp))
00114                      tp += 1<<h;          /* left branch */
00115               else
00116                      tp += 1<<(h+1);             /* right branch */
00117        h = pval(*tp);
00118                                           /* add to color table */
00119        clrtab[h].sum[RED] += r;
00120        clrtab[h].sum[GRN] += g;
00121        clrtab[h].sum[BLU] += b;
00122        clrtab[h].n++;
00123                                    /* recompute average */
00124        r = clrtab[h].sum[RED] / clrtab[h].n;
00125        g = clrtab[h].sum[GRN] / clrtab[h].n;
00126        b = clrtab[h].sum[BLU] / clrtab[h].n;
00127                                    /* check for movement */
00128        if (clrtab[h].n == 1 ||
00129                      (r-clrtab[h].ent[RED])*(r-clrtab[h].ent[RED]) +
00130                      (g-clrtab[h].ent[GRN])*(g-clrtab[h].ent[GRN]) +
00131                      (b-clrtab[h].ent[BLU])*(b-clrtab[h].ent[BLU]) > MAXDST2) {
00132               clrtab[h].ent[RED] = r;
00133               clrtab[h].ent[GRN] = g; /* reassign pixel */
00134               clrtab[h].ent[BLU] = b;
00135 #ifdef DEBUG
00136               {
00137                      extern char   errmsg[];
00138                      sprintf(errmsg, "pixel %d = (%d,%d,%d) (%d refs)\n",
00139                                    h, r, g, b, clrtab[h].n);
00140                      eputs(errmsg);
00141               }
00142 #endif
00143               (*set_pixel)(h, r, g, b);
00144        }
00145        return(h);                         /* return pixel value */
00146 }
00147 
00148 
00149 static void
00150 cut(          /* partition color space */
00151        register CNODE       *tree,
00152        int    level,
00153        register int  box[3][2],
00154        int    c0,
00155        int    c1
00156 )
00157 {
00158        int    kb[3][2];
00159        
00160        if (c1-c0 <= 1) {           /* assign pixel */
00161               *tree = set_pval(c0);
00162               return;
00163        }
00164                                    /* split box */
00165        *tree = split(box);
00166        memcpy((void *)kb, (void *)box, sizeof(kb));
00167                                           /* do left (lesser) branch */
00168        kb[prim(*tree)][1] = part(*tree);
00169        cut(tree+(1<<level), level+1, kb, c0, (c0+c1)>>1);
00170                                           /* do right branch */
00171        kb[prim(*tree)][0] = part(*tree);
00172        kb[prim(*tree)][1] = box[prim(*tree)][1];
00173        cut(tree+(1<<(level+1)), level+1, kb, (c0+c1)>>1, c1);
00174 }
00175 
00176 
00177 static int
00178 split(                      /* find median cut for box */
00179        register int  box[3][2]
00180 )
00181 {
00182 #define c0    r
00183        register int  r, g, b;
00184        int    pri;
00185        long   t[HMAX], med;
00186                                    /* find dominant axis */
00187        pri = RED;
00188        if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
00189               pri = GRN;
00190        if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
00191               pri = BLU;
00192                                    /* sum histogram over box */
00193        med = 0;
00194        switch (pri) {
00195        case RED:
00196               for (r = box[RED][0]; r < box[RED][1]; r++) {
00197                      t[r] = 0;
00198                      for (g = box[GRN][0]; g < box[GRN][1]; g++)
00199                             for (b = box[BLU][0]; b < box[BLU][1]; b++)
00200                                    t[r] += histo[r][g][b];
00201                      med += t[r];
00202               }
00203               break;
00204        case GRN:
00205               for (g = box[GRN][0]; g < box[GRN][1]; g++) {
00206                      t[g] = 0;
00207                      for (b = box[BLU][0]; b < box[BLU][1]; b++)
00208                             for (r = box[RED][0]; r < box[RED][1]; r++)
00209                                    t[g] += histo[r][g][b];
00210                      med += t[g];
00211               }
00212               break;
00213        case BLU:
00214               for (b = box[BLU][0]; b < box[BLU][1]; b++) {
00215                      t[b] = 0;
00216                      for (r = box[RED][0]; r < box[RED][1]; r++)
00217                             for (g = box[GRN][0]; g < box[GRN][1]; g++)
00218                                    t[b] += histo[r][g][b];
00219                      med += t[b];
00220               }
00221               break;
00222        }
00223        if (med < MINSAMP)          /* if too sparse, split at midpoint */
00224               return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
00225                                    /* find median position */
00226        med >>= 1;
00227        for (c0 = box[pri][0]; med > 0; c0++)
00228               med -= t[c0];
00229        if (c0 > (box[pri][0]+box[pri][1])>>1)    /* if past the midpoint */
00230               c0--;                       /* part left of median */
00231        return(set_branch(pri,c0));
00232 #undef c0
00233 }