ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/hd/rhd_ctab.c
Revision: 3.1
Committed: Wed Nov 19 18:01:03 1997 UTC (26 years, 4 months ago) by gregl
Content type: text/plain
Branch: MAIN
Log Message:
Initial revision

File Contents

# Content
1 /* Copyright (c) 1997 Silicon Graphics, Inc. */
2
3 #ifndef lint
4 static char SCCSid[] = "$SunId$ SGI";
5 #endif
6
7 /*
8 * Allocate and control dynamic color table.
9 *
10 * We start off with a uniform partition of color space.
11 * As pixels are sent to the frame buffer, a histogram is built.
12 * When a new color table is requested, the histogram is used
13 * to make a pseudo-optimal partition, after which the
14 * histogram is cleared. This algorithm
15 * performs only as well as the next drawing's color
16 * distribution is correlated to the last.
17 *
18 * This module is essentially identical to src/rt/colortab.c,
19 * except there is no color mapping, since the tm library is used.
20 */
21
22 #include "standard.h"
23 #include "color.h"
24 /* histogram resolution */
25 #define NRED 24
26 #define NGRN 32
27 #define NBLU 16
28 #define HMAX NGRN
29 /* minimum box count for adaptive partition */
30 #define MINSAMP 7
31 /* maximum distance^2 before color reassign */
32 #define MAXDST2 12
33 /* color partition tree */
34 #define CNODE short
35 #define set_branch(p,c) ((c)<<2|(p))
36 #define set_pval(pv) ((pv)<<2|3)
37 #define is_branch(cn) (((cn)&3)!=3)
38 #define is_pval(cn) (((cn)&3)==3)
39 #define part(cn) ((cn)>>2)
40 #define prim(cn) ((cn)&3)
41 #define pval(cn) ((cn)>>2)
42 /* our color table */
43 static struct tabent {
44 long sum[3]; /* sum of colors using this entry */
45 int n; /* number of colors */
46 BYTE ent[3]; /* current table value */
47 } *clrtab = NULL;
48 /* color cube partition */
49 static CNODE *ctree = NULL;
50 /* histogram of colors used */
51 static unsigned short histo[NRED][NGRN][NBLU];
52 /* initial color cube boundary */
53 static int CLRCUBE[3][2] = {{0,NRED},{0,NGRN},{0,NBLU}};
54
55 static int split(), cut();
56
57
58 int
59 new_ctab(ncolors) /* start new color table with max ncolors */
60 int ncolors;
61 {
62 int treesize;
63
64 if (ncolors < 1)
65 return(0);
66 /* free old tables */
67 if (clrtab != NULL)
68 free((char *)clrtab);
69 if (ctree != NULL)
70 free((char *)ctree);
71 /* get new tables */
72 for (treesize = 1; treesize < ncolors; treesize <<= 1)
73 ;
74 treesize <<= 1;
75 clrtab = (struct tabent *)calloc(ncolors, sizeof(struct tabent));
76 ctree = (CNODE *)malloc(treesize*sizeof(CNODE));
77 if (clrtab == NULL || ctree == NULL)
78 return(0);
79 /* partition color space */
80 cut(ctree, 0, CLRCUBE, 0, ncolors);
81 /* clear histogram */
82 bzero((char *)histo, sizeof(histo));
83 /* return number of colors used */
84 return(ncolors);
85 }
86
87
88 int
89 get_pixel(rgb, set_pixel) /* get pixel for color */
90 BYTE rgb[3];
91 int (*set_pixel)();
92 {
93 extern char errmsg[];
94 int r, g, b;
95 int cv[3];
96 register CNODE *tp;
97 register int h;
98 /* get desired color */
99 r = rgb[RED];
100 g = rgb[GRN];
101 b = rgb[BLU];
102 /* reduce resolution */
103 cv[RED] = (r*NRED)>>8;
104 cv[GRN] = (g*NGRN)>>8;
105 cv[BLU] = (b*NBLU)>>8;
106 /* add to histogram */
107 histo[cv[RED]][cv[GRN]][cv[BLU]]++;
108 /* find pixel in tree */
109 for (tp = ctree, h = 0; is_branch(*tp); h++)
110 if (cv[prim(*tp)] < part(*tp))
111 tp += 1<<h; /* left branch */
112 else
113 tp += 1<<(h+1); /* right branch */
114 h = pval(*tp);
115 /* add to color table */
116 clrtab[h].sum[RED] += r;
117 clrtab[h].sum[GRN] += g;
118 clrtab[h].sum[BLU] += b;
119 clrtab[h].n++;
120 /* recompute average */
121 r = clrtab[h].sum[RED] / clrtab[h].n;
122 g = clrtab[h].sum[GRN] / clrtab[h].n;
123 b = clrtab[h].sum[BLU] / clrtab[h].n;
124 /* check for movement */
125 if (clrtab[h].n == 1 ||
126 (r-clrtab[h].ent[RED])*(r-clrtab[h].ent[RED]) +
127 (g-clrtab[h].ent[GRN])*(g-clrtab[h].ent[GRN]) +
128 (b-clrtab[h].ent[BLU])*(b-clrtab[h].ent[BLU]) > MAXDST2) {
129 clrtab[h].ent[RED] = r;
130 clrtab[h].ent[GRN] = g; /* reassign pixel */
131 clrtab[h].ent[BLU] = b;
132 #ifdef DEBUG
133 sprintf(errmsg, "pixel %d = (%d,%d,%d) (%d refs)\n",
134 h, r, g, b, clrtab[h].n);
135 eputs(errmsg);
136 #endif
137 (*set_pixel)(h, r, g, b);
138 }
139 return(h); /* return pixel value */
140 }
141
142
143 static
144 cut(tree, level, box, c0, c1) /* partition color space */
145 register CNODE *tree;
146 int level;
147 register int box[3][2];
148 int c0, c1;
149 {
150 int kb[3][2];
151
152 if (c1-c0 <= 1) { /* assign pixel */
153 *tree = set_pval(c0);
154 return;
155 }
156 /* split box */
157 *tree = split(box);
158 bcopy((char *)box, (char *)kb, sizeof(kb));
159 /* do left (lesser) branch */
160 kb[prim(*tree)][1] = part(*tree);
161 cut(tree+(1<<level), level+1, kb, c0, (c0+c1)>>1);
162 /* do right branch */
163 kb[prim(*tree)][0] = part(*tree);
164 kb[prim(*tree)][1] = box[prim(*tree)][1];
165 cut(tree+(1<<(level+1)), level+1, kb, (c0+c1)>>1, c1);
166 }
167
168
169 static int
170 split(box) /* find median cut for box */
171 register int box[3][2];
172 {
173 #define c0 r
174 register int r, g, b;
175 int pri;
176 long t[HMAX], med;
177 /* find dominant axis */
178 pri = RED;
179 if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
180 pri = GRN;
181 if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
182 pri = BLU;
183 /* sum histogram over box */
184 med = 0;
185 switch (pri) {
186 case RED:
187 for (r = box[RED][0]; r < box[RED][1]; r++) {
188 t[r] = 0;
189 for (g = box[GRN][0]; g < box[GRN][1]; g++)
190 for (b = box[BLU][0]; b < box[BLU][1]; b++)
191 t[r] += histo[r][g][b];
192 med += t[r];
193 }
194 break;
195 case GRN:
196 for (g = box[GRN][0]; g < box[GRN][1]; g++) {
197 t[g] = 0;
198 for (b = box[BLU][0]; b < box[BLU][1]; b++)
199 for (r = box[RED][0]; r < box[RED][1]; r++)
200 t[g] += histo[r][g][b];
201 med += t[g];
202 }
203 break;
204 case BLU:
205 for (b = box[BLU][0]; b < box[BLU][1]; b++) {
206 t[b] = 0;
207 for (r = box[RED][0]; r < box[RED][1]; r++)
208 for (g = box[GRN][0]; g < box[GRN][1]; g++)
209 t[b] += histo[r][g][b];
210 med += t[b];
211 }
212 break;
213 }
214 if (med < MINSAMP) /* if too sparse, split at midpoint */
215 return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
216 /* find median position */
217 med >>= 1;
218 for (c0 = box[pri][0]; med > 0; c0++)
219 med -= t[c0];
220 if (c0 > (box[pri][0]+box[pri][1])>>1) /* if past the midpoint */
221 c0--; /* part left of median */
222 return(set_branch(pri,c0));
223 #undef c0
224 }