ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/px/clrtab.c
Revision: 2.17
Committed: Sun Mar 28 20:33:13 2004 UTC (20 years ago) by schorsch
Content type: text/plain
Branch: MAIN
CVS Tags: rad3R7P2, rad3R7P1, rad3R6, rad3R6P1
Changes since 2.16: +84 -51 lines
Log Message:
Continued ANSIfication, and other fixes and clarifications.

File Contents

# Content
1 #ifndef lint
2 static const char RCSid[] = "$Id: clrtab.c,v 2.16 2003/07/27 22:12:03 schorsch Exp $";
3 #endif
4 /*
5 * Simple median-cut color quantization based on colortab.c
6 */
7
8 #include "copyright.h"
9
10 #include <string.h>
11
12 #include "standard.h"
13 #include "color.h"
14 #include "clrtab.h"
15
16 /* histogram resolution */
17 #define NRED 36
18 #define NGRN 48
19 #define NBLU 24
20 #define HMAX NGRN
21 /* minimum box count for adaptive partition */
22 #define MINSAMP 7
23 /* color partition */
24 #define set_branch(p,c) ((c)<<2|(p))
25 #define part(cn) ((cn)>>2)
26 #define prim(cn) ((cn)&3)
27 /* our color table (global) */
28 extern BYTE clrtab[256][3];
29 /* histogram of colors / color assignments */
30 static unsigned histo[NRED][NGRN][NBLU];
31 #define cndx(c) histo[((c)[RED]*NRED)>>8][((c)[GRN]*NGRN)>>8][((c)[BLU]*NBLU)>>8]
32 /* initial color cube boundary */
33 static int CLRCUBE[3][2] = {{0,NRED},{0,NGRN},{0,NBLU}};
34 /* maximum propagated error during dithering */
35 #define MAXERR 20
36 /* define CLOSEST to get closest colors */
37 #ifndef CLOSEST
38 #ifdef SPEED
39 #if SPEED > 8
40 #define CLOSEST 1 /* this step takes a little longer */
41 #endif
42 #endif
43 #endif
44
45
46 #ifdef CLOSEST
47 static void closest(int n);
48 static void setclosest(BYTE *nl[], int r, int g, int b);
49 static void addneigh(BYTE *nl[], int i, int j);
50 static unsigned int dist(BYTE col[3], int r, int g, int b);
51 #endif
52 static void cut(int box[3][2], int c0, int c1);
53 static int split(int box[3][2]);
54 static void mktabent(int p, int box[3][2]);
55
56
57 extern int
58 new_histo( /* clear our histogram */
59 int n
60 )
61 {
62 memset((void *)histo, '\0', sizeof(histo));
63 return(0);
64 }
65
66
67 extern void
68 cnt_pixel( /* add pixel to our histogram */
69 register BYTE col[]
70 )
71 {
72 cndx(col)++;
73 }
74
75
76 extern void
77 cnt_colrs( /* add a scanline to our histogram */
78 register COLR *cs,
79 register int n
80 )
81 {
82 while (n-- > 0) {
83 cndx(cs[0])++;
84 cs++;
85 }
86 }
87
88
89 extern int
90 new_clrtab( /* make new color table using ncolors */
91 int ncolors
92 )
93 {
94 if (ncolors < 1)
95 return(0);
96 if (ncolors > 256)
97 ncolors = 256;
98 /* partition color space */
99 cut(CLRCUBE, 0, ncolors);
100 #ifdef CLOSEST
101 closest(ncolors); /* ensure colors picked are closest */
102 #endif
103 /* reset dithering function */
104 dith_colrs((BYTE *)NULL, (COLR *)NULL, 0);
105 /* return new color table size */
106 return(ncolors);
107 }
108
109
110 extern int
111 map_pixel( /* get pixel for color */
112 register BYTE col[]
113 )
114 {
115 return(cndx(col));
116 }
117
118
119 extern void
120 map_colrs( /* convert a scanline to color index values */
121 register BYTE *bs,
122 register COLR *cs,
123 register int n
124 )
125 {
126 while (n-- > 0) {
127 *bs++ = cndx(cs[0]);
128 cs++;
129 }
130 }
131
132
133 extern void
134 dith_colrs( /* convert scanline to dithered index values */
135 register BYTE *bs,
136 register COLR *cs,
137 int n
138 )
139 {
140 static short (*cerr)[3] = NULL;
141 static int N = 0;
142 int err[3], errp[3];
143 register int x, i;
144
145 if (n != N) { /* get error propogation array */
146 if (N) {
147 free((void *)cerr);
148 cerr = NULL;
149 }
150 if (n)
151 cerr = (short (*)[3])malloc(3*n*sizeof(short));
152 if (cerr == NULL) {
153 N = 0;
154 map_colrs(bs, cs, n);
155 return;
156 }
157 N = n;
158 memset((void *)cerr, '\0', 3*N*sizeof(short));
159 }
160 err[0] = err[1] = err[2] = 0;
161 for (x = 0; x < n; x++) {
162 for (i = 0; i < 3; i++) { /* dither value */
163 errp[i] = err[i];
164 err[i] += cerr[x][i];
165 #ifdef MAXERR
166 if (err[i] > MAXERR) err[i] = MAXERR;
167 else if (err[i] < -MAXERR) err[i] = -MAXERR;
168 #endif
169 err[i] += cs[x][i];
170 if (err[i] < 0) err[i] = 0;
171 else if (err[i] > 255) err[i] = 255;
172 }
173 bs[x] = cndx(err);
174 for (i = 0; i < 3; i++) { /* propagate error */
175 err[i] -= clrtab[bs[x]][i];
176 err[i] /= 3;
177 cerr[x][i] = err[i] + errp[i];
178 }
179 }
180 }
181
182
183 static void
184 cut( /* partition color space */
185 register int box[3][2],
186 int c0,
187 int c1
188 )
189 {
190 register int branch;
191 int kb[3][2];
192
193 if (c1-c0 <= 1) { /* assign pixel */
194 mktabent(c0, box);
195 return;
196 }
197 /* split box */
198 branch = split(box);
199 memcpy((void *)kb, (void *)box, sizeof(kb));
200 /* do left (lesser) branch */
201 kb[prim(branch)][1] = part(branch);
202 cut(kb, c0, (c0+c1)>>1);
203 /* do right branch */
204 kb[prim(branch)][0] = part(branch);
205 kb[prim(branch)][1] = box[prim(branch)][1];
206 cut(kb, (c0+c1)>>1, c1);
207 }
208
209
210 static int
211 split( /* find median cut for box */
212 register int box[3][2]
213 )
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 }
267
268
269 static void
270 mktabent( /* compute average color for box and assign */
271 int p,
272 register int box[3][2]
273 )
274 {
275 unsigned long sum[3];
276 unsigned r, g;
277 unsigned long n;
278 register unsigned b, c;
279 /* sum pixels in box */
280 n = 0;
281 sum[RED] = sum[GRN] = sum[BLU] = 0;
282 for (r = box[RED][0]; r < box[RED][1]; r++)
283 for (g = box[GRN][0]; g < box[GRN][1]; g++)
284 for (b = box[BLU][0]; b < box[BLU][1]; b++) {
285 if ( (c = histo[r][g][b]) ) {
286 n += c;
287 sum[RED] += (long)c*r;
288 sum[GRN] += (long)c*g;
289 sum[BLU] += (long)c*b;
290 }
291 histo[r][g][b] = p; /* assign pixel */
292 }
293 if (n >= (1L<<23)/HMAX) { /* avoid overflow */
294 sum[RED] /= n;
295 sum[GRN] /= n;
296 sum[BLU] /= n;
297 n = 1;
298 }
299 if (n) { /* compute average */
300 clrtab[p][RED] = sum[RED]*256/NRED/n;
301 clrtab[p][GRN] = sum[GRN]*256/NGRN/n;
302 clrtab[p][BLU] = sum[BLU]*256/NBLU/n;
303 } else { /* empty box -- use midpoint */
304 clrtab[p][RED] = (box[RED][0]+box[RED][1])*256/NRED/2;
305 clrtab[p][GRN] = (box[GRN][0]+box[GRN][1])*256/NGRN/2;
306 clrtab[p][BLU] = (box[BLU][0]+box[BLU][1])*256/NBLU/2;
307 }
308 }
309
310
311 #ifdef CLOSEST
312 #define NBSIZ 32
313 static void
314 closest( /* make sure we have the closest colors */
315 int n
316 )
317 {
318 BYTE *neigh[256];
319 register int r, g, b;
320 #define i r
321 /* get space for neighbor lists */
322 for (i = 0; i < n; i++) {
323 if ((neigh[i] = (BYTE *)malloc(NBSIZ)) == NULL) {
324 while (i--)
325 free(neigh[i]);
326 return; /* ENOMEM -- abandon effort */
327 }
328 neigh[i][0] = i; /* identity is terminator */
329 }
330 /* make neighbor lists */
331 for (r = 0; r < NRED; r++)
332 for (g = 0; g < NGRN; g++)
333 for (b = 0; b < NBLU; b++) {
334 if (r < NRED-1 && histo[r][g][b] != histo[r+1][g][b])
335 addneigh(neigh, histo[r][g][b], histo[r+1][g][b]);
336 if (g < NGRN-1 && histo[r][g][b] != histo[r][g+1][b])
337 addneigh(neigh, histo[r][g][b], histo[r][g+1][b]);
338 if (b < NBLU-1 && histo[r][g][b] != histo[r][g][b+1])
339 addneigh(neigh, histo[r][g][b], histo[r][g][b+1]);
340 }
341 /* assign closest values */
342 for (r = 0; r < NRED; r++)
343 for (g = 0; g < NGRN; g++)
344 for (b = 0; b < NBLU; b++)
345 setclosest(neigh, r, g, b);
346 /* free neighbor lists */
347 for (i = 0; i < n; i++)
348 free(neigh[i]);
349 #undef i
350 }
351
352
353 static void
354 addneigh( /* i and j are neighbors; add them to list */
355 register BYTE *nl[],
356 register int i,
357 int j
358 )
359 {
360 int nc;
361 char *nnl;
362 register int t;
363
364 for (nc = 0; nc < 2; nc++) { /* do both neighbors */
365 for (t = 0; nl[i][t] != i; t++)
366 if (nl[i][t] == j)
367 break; /* in list already */
368 if (nl[i][t] == i) { /* add to list */
369 nl[i][t++] = j;
370 if (t % NBSIZ == 0) { /* enlarge list */
371 if ((nnl = realloc((void *)nl[i],
372 t+NBSIZ)) == NULL)
373 t--;
374 else
375 nl[i] = (BYTE *)nnl;
376 }
377 nl[i][t] = i; /* terminator */
378 }
379 t = i; i = j; j = t; /* swap and do it again */
380 }
381 }
382
383
384 static unsigned int
385 dist( /* find distance from clrtab entry to r,g,b */
386 register BYTE col[3],
387 int r,
388 int g,
389 int b
390 )
391 {
392 register int tmp;
393 register unsigned sum;
394
395 tmp = col[RED]*NRED/256 - r;
396 sum = tmp*tmp;
397 tmp = col[GRN]*NGRN/256 - g;
398 sum += tmp*tmp;
399 tmp = col[BLU]*NBLU/256 - b;
400 sum += tmp*tmp;
401 return(sum);
402 }
403
404
405 static void
406 setclosest( /* find index closest to color and assign */
407 BYTE *nl[],
408 int r,
409 int g,
410 int b
411 )
412 {
413 int ident;
414 unsigned min;
415 register unsigned d;
416 register BYTE *p;
417 /* get starting value */
418 min = dist(clrtab[ident=histo[r][g][b]], r, g, b);
419 /* find minimum */
420 for (p = nl[ident]; *p != ident; p++)
421 if ((d = dist(clrtab[*p], r, g, b)) < min) {
422 min = d;
423 histo[r][g][b] = *p;
424 }
425 }
426 #endif