ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/rt/colortab.c
Revision: 2.9
Committed: Tue Mar 30 16:13:01 2004 UTC (20 years ago) by schorsch
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R7P2, rad3R7P1, rad4R0, rad3R6, rad3R6P1, rad3R8, rad3R9
Changes since 2.8: +8 -6 lines
Log Message:
Continued ANSIfication. There are only bits and pieces left now.

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: colortab.c,v 2.8 2003/06/30 14:59:12 schorsch Exp $";
3 #endif
4 /*
5 * colortab.c - allocate and control dynamic color table.
6 *
7 * We start off with a uniform partition of color space.
8 * As pixels are sent to the frame buffer, a histogram is built.
9 * When a new color table is requested, the histogram is used
10 * to make a pseudo-optimal partition, after which the
11 * histogram is cleared. This algorithm
12 * performs only as well as the next drawing's color
13 * distribution is correlated to the last.
14 *
15 * External symbols declared in drvier.h
16 */
17
18 #include "copyright.h"
19
20 #include <string.h>
21
22 #include "standard.h"
23 #include "color.h"
24 #include "driver.h"
25
26 /* histogram resolution */
27 #define NRED 24
28 #define NGRN 32
29 #define NBLU 16
30 #define HMAX NGRN
31 /* minimum box count for adaptive partition */
32 #define MINSAMP 7
33 /* maximum distance^2 before color reassign */
34 #define MAXDST2 12
35 /* map a color */
36 #define map_col(c,p) clrmap[p][ colval(c,p)<1. ? \
37 (int)(colval(c,p)*256.) : 255 ]
38 /* color partition tree */
39 #define CNODE short
40 #define set_branch(p,c) ((c)<<2|(p))
41 #define set_pval(pv) ((pv)<<2|3)
42 #define is_branch(cn) (((cn)&3)!=3)
43 #define is_pval(cn) (((cn)&3)==3)
44 #define part(cn) ((cn)>>2)
45 #define prim(cn) ((cn)&3)
46 #define pval(cn) ((cn)>>2)
47 /* our color table */
48 static struct tabent {
49 long sum[3]; /* sum of colors using this entry */
50 int n; /* number of colors */
51 BYTE ent[3]; /* current table value */
52 } *clrtab = NULL;
53 /* color cube partition */
54 static CNODE *ctree = NULL;
55 /* our color correction map */
56 static BYTE clrmap[3][256];
57 /* histogram of colors used */
58 static unsigned short histo[NRED][NGRN][NBLU];
59 /* initial color cube boundary */
60 static int CLRCUBE[3][2] = {{0,NRED},{0,NGRN},{0,NBLU}};
61
62 static int split();
63 static void cut();
64
65
66 int
67 new_ctab(ncolors) /* start new color table with max ncolors */
68 int ncolors;
69 {
70 int treesize;
71
72 if (ncolors < 1)
73 return(0);
74 /* free old tables */
75 if (clrtab != NULL)
76 free((void *)clrtab);
77 if (ctree != NULL)
78 free((void *)ctree);
79 /* get new tables */
80 for (treesize = 1; treesize < ncolors; treesize <<= 1)
81 ;
82 treesize <<= 1;
83 clrtab = (struct tabent *)calloc(ncolors, sizeof(struct tabent));
84 ctree = (CNODE *)malloc(treesize*sizeof(CNODE));
85 if (clrtab == NULL || ctree == NULL)
86 return(0);
87 /* partition color space */
88 cut(ctree, 0, CLRCUBE, 0, ncolors);
89 /* clear histogram */
90 memset((void *)histo, '\0', sizeof(histo));
91 /* return number of colors used */
92 return(ncolors);
93 }
94
95
96 extern int
97 get_pixel( /* get pixel for color */
98 COLOR col,
99 dr_newcolrf_t *newcolr
100 )
101 {
102 int r, g, b;
103 int cv[3];
104 register CNODE *tp;
105 register int h;
106 /* map color */
107 r = map_col(col,RED);
108 g = map_col(col,GRN);
109 b = map_col(col,BLU);
110 /* reduce resolution */
111 cv[RED] = (r*NRED)>>8;
112 cv[GRN] = (g*NGRN)>>8;
113 cv[BLU] = (b*NBLU)>>8;
114 /* add to histogram */
115 histo[cv[RED]][cv[GRN]][cv[BLU]]++;
116 /* find pixel in tree */
117 for (tp = ctree, h = 0; is_branch(*tp); h++)
118 if (cv[prim(*tp)] < part(*tp))
119 tp += 1<<h; /* left branch */
120 else
121 tp += 1<<(h+1); /* right branch */
122 h = pval(*tp);
123 /* add to color table */
124 clrtab[h].sum[RED] += r;
125 clrtab[h].sum[GRN] += g;
126 clrtab[h].sum[BLU] += b;
127 clrtab[h].n++;
128 /* recompute average */
129 r = clrtab[h].sum[RED] / clrtab[h].n;
130 g = clrtab[h].sum[GRN] / clrtab[h].n;
131 b = clrtab[h].sum[BLU] / clrtab[h].n;
132 /* check for movement */
133 if (clrtab[h].n == 1 ||
134 (r-clrtab[h].ent[RED])*(r-clrtab[h].ent[RED]) +
135 (g-clrtab[h].ent[GRN])*(g-clrtab[h].ent[GRN]) +
136 (b-clrtab[h].ent[BLU])*(b-clrtab[h].ent[BLU]) > MAXDST2) {
137 clrtab[h].ent[RED] = r;
138 clrtab[h].ent[GRN] = g; /* reassign pixel */
139 clrtab[h].ent[BLU] = b;
140 #ifdef DEBUG
141 sprintf(errmsg, "pixel %d = (%d,%d,%d) (%d refs)\n",
142 h, r, g, b, clrtab[h].n);
143 eputs(errmsg);
144 #endif
145 (*newcolr)(h, r, g, b);
146 }
147 return(h); /* return pixel value */
148 }
149
150
151 void
152 make_gmap(gam) /* make gamma correction map */
153 double gam;
154 {
155 register int i;
156
157 for (i = 0; i < 256; i++)
158 clrmap[RED][i] =
159 clrmap[GRN][i] =
160 clrmap[BLU][i] = 256.0 * pow((i+0.5)/256.0, 1.0/gam);
161 }
162
163
164 void
165 set_cmap(rmap, gmap, bmap) /* set custom color correction map */
166 BYTE *rmap, *gmap, *bmap;
167 {
168 memcpy((void *)clrmap[RED], (void *)rmap, 256);
169 memcpy((void *)clrmap[GRN], (void *)gmap, 256);
170 memcpy((void *)clrmap[BLU], (void *)bmap, 256);
171 }
172
173
174 void
175 map_color(rgb, col) /* map a color to a byte triplet */
176 BYTE rgb[3];
177 COLOR col;
178 {
179 rgb[RED] = map_col(col,RED);
180 rgb[GRN] = map_col(col,GRN);
181 rgb[BLU] = map_col(col,BLU);
182 }
183
184
185 static void
186 cut(tree, level, box, c0, c1) /* partition color space */
187 register CNODE *tree;
188 int level;
189 register int box[3][2];
190 int c0, c1;
191 {
192 int kb[3][2];
193
194 if (c1-c0 <= 1) { /* assign pixel */
195 *tree = set_pval(c0);
196 return;
197 }
198 /* split box */
199 *tree = split(box);
200 memcpy((void *)kb, (void *)box, sizeof(kb));
201 /* do left (lesser) branch */
202 kb[prim(*tree)][1] = part(*tree);
203 cut(tree+(1<<level), level+1, kb, c0, (c0+c1)>>1);
204 /* do right branch */
205 kb[prim(*tree)][0] = part(*tree);
206 kb[prim(*tree)][1] = box[prim(*tree)][1];
207 cut(tree+(1<<(level+1)), level+1, kb, (c0+c1)>>1, c1);
208 }
209
210
211 static int
212 split(box) /* find median cut for box */
213 register int box[3][2];
214 {
215 #define c0 r
216 register int r, g, b;
217 int pri;
218 long t[HMAX], med;
219 /* find dominant axis */
220 pri = RED;
221 if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
222 pri = GRN;
223 if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
224 pri = BLU;
225 /* sum histogram over box */
226 med = 0;
227 switch (pri) {
228 case RED:
229 for (r = box[RED][0]; r < box[RED][1]; r++) {
230 t[r] = 0;
231 for (g = box[GRN][0]; g < box[GRN][1]; g++)
232 for (b = box[BLU][0]; b < box[BLU][1]; b++)
233 t[r] += histo[r][g][b];
234 med += t[r];
235 }
236 break;
237 case GRN:
238 for (g = box[GRN][0]; g < box[GRN][1]; g++) {
239 t[g] = 0;
240 for (b = box[BLU][0]; b < box[BLU][1]; b++)
241 for (r = box[RED][0]; r < box[RED][1]; r++)
242 t[g] += histo[r][g][b];
243 med += t[g];
244 }
245 break;
246 case BLU:
247 for (b = box[BLU][0]; b < box[BLU][1]; b++) {
248 t[b] = 0;
249 for (r = box[RED][0]; r < box[RED][1]; r++)
250 for (g = box[GRN][0]; g < box[GRN][1]; g++)
251 t[b] += histo[r][g][b];
252 med += t[b];
253 }
254 break;
255 }
256 if (med < MINSAMP) /* if too sparse, split at midpoint */
257 return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
258 /* find median position */
259 med >>= 1;
260 for (c0 = box[pri][0]; med > 0; c0++)
261 med -= t[c0];
262 if (c0 > (box[pri][0]+box[pri][1])>>1) /* if past the midpoint */
263 c0--; /* part left of median */
264 return(set_branch(pri,c0));
265 #undef c0
266 }