src/rt/colortab.c

/* Copyright (c) 1989 Regents of the University of California */

#ifndef lint
static char SCCSid[] = "$SunId$ LBL";
#endif

/*
 * colortab.c - allocate and control dynamic color table.
 *
 *      We start off with a uniform partition of color space.
 *      As pixels are sent to the frame buffer, a histogram is built.
 *      When a new color table is requested, the histogram is used
 *      to make a pseudo-optimal partition, after which the
 *      histogram is cleared.  This algorithm
 *      performs only as well as the next drawing's color
 *      distribution is correlated to the last.
 */

#include "color.h"

#define NULL            0
                                /* histogram resolution */
#define NRED            24
#define NGRN            32
#define NBLU            16
#define HMAX            NGRN
                                /* minimum box count for adaptive partition */
#define MINSAMP         7
                                /* maximum distance^2 before color reassign */
#define MAXDST2         12
                                /* maximum frame buffer depth */
#define FBDEPTH         8
                                /* map a color */
#define map_col(c,p)    clrmap[p][ colval(c,p)<1. ? \
                                (int)(colval(c,p)*256.) : 255 ]
                                /* color partition tree */
#define CNODE           short
#define set_branch(p,c) ((c)<<2|(p))
#define set_pval(pv)    ((pv)<<2|3)
#define is_pval(cn)     (((cn)&3)==3)
#define part(cn)        ((cn)>>2)
#define prim(cn)        ((cn)&3)
#define pval(cn)        ((cn)>>2)
                                /* our color table */
struct tabent {
        long    sum[3];         /* sum of colors using this entry */
        long    n;              /* number of colors */
        short   ent[3];         /* current table value */
}       clrtab[1<<FBDEPTH];
                                /* our color correction map */
static BYTE     clrmap[3][256];
                                /* histogram of colors used */
static unsigned histo[NRED][NGRN][NBLU];
                                /* initial color cube boundaries */
static int      CLRCUBE[3][2] = {0,NRED,0,NGRN,0,NBLU};
                                /* color cube partition */
static CNODE    ctree[1<<(FBDEPTH+1)];


int
new_ctab(ncolors)               /* start new color table with max ncolors */
int     ncolors;
{
        if (ncolors < 1 || ncolors > 1<<FBDEPTH)
                return(0);
                                /* clear color table */
        bzero(clrtab, sizeof(clrtab));
                                /* partition color space */
        cut(ctree, FBDEPTH, CLRCUBE, 0, ncolors);
                                /* clear histogram */
        bzero(histo, sizeof(histo));
                                /* return number of colors used */
        return(ncolors);
}


int
get_pixel(col, set_pixel)       /* get pixel for color */
COLOR   col;
int     (*set_pixel)();
{
        int     r, g, b;
        int     cv[3];
        register union { CNODE *t; struct tabent *e; }  p;
        register int    h;
                                                /* map color */
        r = map_col(col,RED);
        g = map_col(col,GRN);
        b = map_col(col,BLU);
                                                /* reduce resolution */
        cv[RED] = (r*NRED)>>8;
        cv[GRN] = (g*NGRN)>>8;
        cv[BLU] = (b*NBLU)>>8;
                                                /* add to histogram */
        histo[cv[RED]][cv[GRN]][cv[BLU]]++;
                                                /* find pixel in tree */
        p.t = ctree;
        for (h = FBDEPTH; h > 0; h--) {
                if (is_pval(*p.t))
                        break;
                if (cv[prim(*p.t)] < part(*p.t))
                        p.t++;          /* left branch */
                else
                        p.t += 1<<h;    /* right branch */
        }
        h = pval(*p.t);
                                                /* add to color table */
        p.e = clrtab + h;
                                        /* add to sum */
        p.e->sum[RED] += r;
        p.e->sum[GRN] += g;
        p.e->sum[BLU] += b;
        p.e->n++;
                                        /* recompute average */
        r = p.e->sum[RED] / p.e->n;
        g = p.e->sum[GRN] / p.e->n;
        b = p.e->sum[BLU] / p.e->n;
                                        /* check for movement */
        if (p.e->n == 1 ||
                        (r-p.e->ent[RED])*(r-p.e->ent[RED]) +
                        (g-p.e->ent[GRN])*(g-p.e->ent[GRN]) +
                        (b-p.e->ent[BLU])*(b-p.e->ent[BLU]) > MAXDST2) {
                p.e->ent[RED] = r;
                p.e->ent[GRN] = g;      /* reassign pixel */
                p.e->ent[BLU] = b;
#ifdef notdef
                printf("pixel %d = (%d,%d,%d) (%d refs)\n",
                                h, r, g, b, p.e->n);
#endif
                (*set_pixel)(h, r, g, b);
        }
        return(h);                              /* return pixel value */
}


make_gmap(gam)                  /* make gamma correction map */
double  gam;
{
        extern double   pow();
        register int    i;
        
        for (i = 0; i < 256; i++)
                clrmap[RED][i] =
                clrmap[GRN][i] =
                clrmap[BLU][i] = 256.0 * pow(i/256.0, 1.0/gam);
}


set_cmap(rmap, gmap, bmap)      /* set custom color correction map */
BYTE    *rmap, *gmap, *bmap;
{
        bcopy(rmap, clrmap[RED], 256);
        bcopy(gmap, clrmap[GRN], 256);
        bcopy(bmap, clrmap[BLU], 256);
}


static
cut(tree, height, box, c0, c1)          /* partition color space */
register CNODE  *tree;
int     height;
register int    box[3][2];
int     c0, c1;
{
        int     kb[3][2];
        
        if (c1-c0 <= 1) {               /* assign pixel */
                *tree = set_pval(c0);
                return;
        }
                                        /* split box */
        *tree = split(box);
        bcopy(box, kb, sizeof(kb));
                                                /* do left (lesser) branch */
        kb[prim(*tree)][1] = part(*tree);
        cut(tree+1, height-1, kb, c0, (c0+c1)>>1);
                                                /* do right branch */
        kb[prim(*tree)][0] = part(*tree);
        kb[prim(*tree)][1] = box[prim(*tree)][1];
        cut(tree+(1<<height), height-1, kb, (c0+c1)>>1, c1);
}


static int
split(box)                              /* find median cut for box */
register int    box[3][2];
{
#define c0      r
        register int    r, g, b;
        int     pri;
        int     t[HMAX], med;
                                        /* find dominant axis */
        pri = RED;
        if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
                pri = GRN;
        if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
                pri = BLU;
                                        /* sum histogram over box */
        med = 0;
        switch (pri) {
        case RED:
                for (r = box[RED][0]; r < box[RED][1]; r++) {
                        t[r] = 0;
                        for (g = box[GRN][0]; g < box[GRN][1]; g++)
                                for (b = box[BLU][0]; b < box[BLU][1]; b++)
                                        t[r] += histo[r][g][b];
                        med += t[r];
                }
                break;
        case GRN:
                for (g = box[GRN][0]; g < box[GRN][1]; g++) {
                        t[g] = 0;
                        for (b = box[BLU][0]; b < box[BLU][1]; b++)
                                for (r = box[RED][0]; r < box[RED][1]; r++)
                                        t[g] += histo[r][g][b];
                        med += t[g];
                }
                break;
        case BLU:
                for (b = box[BLU][0]; b < box[BLU][1]; b++) {
                        t[b] = 0;
                        for (r = box[RED][0]; r < box[RED][1]; r++)
                                for (g = box[GRN][0]; g < box[GRN][1]; g++)
                                        t[b] += histo[r][g][b];
                        med += t[b];
                }
                break;
        }
        if (med < MINSAMP)              /* if too sparse, split at midpoint */
                return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
                                        /* find median position */
        med >>= 1;
        for (c0 = box[pri][0]; med > 0; c0++)
                med -= t[c0];
        if (c0 > (box[pri][0]+box[pri][1])>>1)  /* if past the midpoint */
                c0--;                           /* part left of median */
        return(set_branch(pri,c0));
#undef c0
}
Revision:	1.5
Committed:	Tue Oct 3 16:15:52 1989 UTC (36 years, 3 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.4:	+1 -1 lines
Log Message:	Increased allowed color error before table update.
#	User	Rev	Content
1	greg	1.1	/* Copyright (c) 1989 Regents of the University of California */
2
3			#ifndef lint
4			static char SCCSid[] = "$SunId$ LBL";
5			#endif
6
7			/*
8			* colortab.c - 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
19			#include "color.h"
20
21			#define NULL 0
22			/* histogram resolution */
23	greg	1.3	#define NRED 24
24	greg	1.1	#define NGRN 32
25	greg	1.3	#define NBLU 16
26	greg	1.1	#define HMAX NGRN
27			/* minimum box count for adaptive partition */
28			#define MINSAMP 7
29	greg	1.3	/* maximum distance^2 before color reassign */
30	greg	1.5	#define MAXDST2 12
31	greg	1.1	/* maximum frame buffer depth */
32			#define FBDEPTH 8
33			/* map a color */
34	greg	1.4	#define map_col(c,p) clrmap[p][ colval(c,p)<1. ? \
35			(int)(colval(c,p)*256.) : 255 ]
36	greg	1.1	/* color partition tree */
37			#define CNODE short
38			#define set_branch(p,c) ((c)<<2\|(p))
39			#define set_pval(pv) ((pv)<<2\|3)
40			#define is_pval(cn) (((cn)&3)==3)
41			#define part(cn) ((cn)>>2)
42			#define prim(cn) ((cn)&3)
43			#define pval(cn) ((cn)>>2)
44			/* our color table */
45	greg	1.3	struct tabent {
46			long sum[3]; /* sum of colors using this entry */
47			long n; /* number of colors */
48			short ent[3]; /* current table value */
49			} clrtab[1<<FBDEPTH];
50	greg	1.1	/* our color correction map */
51	greg	1.4	static BYTE clrmap[3][256];
52	greg	1.1	/* histogram of colors used */
53			static unsigned histo[NRED][NGRN][NBLU];
54			/* initial color cube boundaries */
55			static int CLRCUBE[3][2] = {0,NRED,0,NGRN,0,NBLU};
56			/* color cube partition */
57			static CNODE ctree[1<<(FBDEPTH+1)];
58
59
60	greg	1.3	int
61	greg	1.4	new_ctab(ncolors) /* start new color table with max ncolors */
62	greg	1.1	int ncolors;
63			{
64	greg	1.4	if (ncolors < 1 \|\| ncolors > 1<<FBDEPTH)
65	greg	1.3	return(0);
66			/* clear color table */
67			bzero(clrtab, sizeof(clrtab));
68			/* partition color space */
69	greg	1.1	cut(ctree, FBDEPTH, CLRCUBE, 0, ncolors);
70			/* clear histogram */
71			bzero(histo, sizeof(histo));
72	greg	1.3	/* return number of colors used */
73			return(ncolors);
74	greg	1.1	}
75
76
77			int
78	greg	1.4	get_pixel(col, set_pixel) /* get pixel for color */
79	greg	1.1	COLOR col;
80	greg	1.4	int (*set_pixel)();
81	greg	1.1	{
82	greg	1.3	int r, g, b;
83	greg	1.1	int cv[3];
84	greg	1.3	register union { CNODE t; struct tabent e; } p;
85	greg	1.1	register int h;
86	greg	1.3	/* map color */
87			r = map_col(col,RED);
88			g = map_col(col,GRN);
89			b = map_col(col,BLU);
90			/* reduce resolution */
91			cv[RED] = (r*NRED)>>8;
92			cv[GRN] = (g*NGRN)>>8;
93			cv[BLU] = (b*NBLU)>>8;
94			/* add to histogram */
95	greg	1.1	histo[cv[RED]][cv[GRN]][cv[BLU]]++;
96	greg	1.3	/* find pixel in tree */
97			p.t = ctree;
98	greg	1.1	for (h = FBDEPTH; h > 0; h--) {
99	greg	1.3	if (is_pval(*p.t))
100	greg	1.1	break;
101	greg	1.3	if (cv[prim(p.t)] < part(p.t))
102			p.t++; /* left branch */
103	greg	1.1	else
104	greg	1.3	p.t += 1<<h; /* right branch */
105	greg	1.1	}
106	greg	1.3	h = pval(*p.t);
107			/* add to color table */
108			p.e = clrtab + h;
109			/* add to sum */
110			p.e->sum[RED] += r;
111			p.e->sum[GRN] += g;
112			p.e->sum[BLU] += b;
113			p.e->n++;
114			/* recompute average */
115			r = p.e->sum[RED] / p.e->n;
116			g = p.e->sum[GRN] / p.e->n;
117			b = p.e->sum[BLU] / p.e->n;
118			/* check for movement */
119			if (p.e->n == 1 \|\|
120			(r-p.e->ent[RED])*(r-p.e->ent[RED]) +
121			(g-p.e->ent[GRN])*(g-p.e->ent[GRN]) +
122			(b-p.e->ent[BLU])*(b-p.e->ent[BLU]) > MAXDST2) {
123			p.e->ent[RED] = r;
124			p.e->ent[GRN] = g; /* reassign pixel */
125			p.e->ent[BLU] = b;
126	greg	1.1	#ifdef notdef
127	greg	1.3	printf("pixel %d = (%d,%d,%d) (%d refs)\n",
128			h, r, g, b, p.e->n);
129	greg	1.1	#endif
130	greg	1.3	(*set_pixel)(h, r, g, b);
131			}
132			return(h); /* return pixel value */
133	greg	1.1	}
134
135
136	greg	1.4	make_gmap(gam) /* make gamma correction map */
137	greg	1.1	double gam;
138			{
139			extern double pow();
140			register int i;
141
142	greg	1.4	for (i = 0; i < 256; i++)
143			clrmap[RED][i] =
144			clrmap[GRN][i] =
145			clrmap[BLU][i] = 256.0 * pow(i/256.0, 1.0/gam);
146			}
147
148
149			set_cmap(rmap, gmap, bmap) /* set custom color correction map */
150			BYTE rmap, gmap, *bmap;
151			{
152			bcopy(rmap, clrmap[RED], 256);
153			bcopy(gmap, clrmap[GRN], 256);
154			bcopy(bmap, clrmap[BLU], 256);
155	greg	1.1	}
156
157
158			static
159			cut(tree, height, box, c0, c1) /* partition color space */
160			register CNODE *tree;
161			int height;
162			register int box[3][2];
163			int c0, c1;
164			{
165			int kb[3][2];
166
167	greg	1.3	if (c1-c0 <= 1) { /* assign pixel */
168	greg	1.1	*tree = set_pval(c0);
169			return;
170			}
171			/* split box */
172			*tree = split(box);
173			bcopy(box, kb, sizeof(kb));
174	greg	1.3	/* do left (lesser) branch */
175	greg	1.1	kb[prim(tree)][1] = part(tree);
176	greg	1.3	cut(tree+1, height-1, kb, c0, (c0+c1)>>1);
177			/* do right branch */
178	greg	1.1	kb[prim(tree)][0] = part(tree);
179			kb[prim(tree)][1] = box[prim(tree)][1];
180	greg	1.3	cut(tree+(1<<height), height-1, kb, (c0+c1)>>1, c1);
181	greg	1.1	}
182
183
184			static int
185			split(box) /* find median cut for box */
186			register int box[3][2];
187			{
188			#define c0 r
189			register int r, g, b;
190			int pri;
191			int t[HMAX], med;
192			/* find dominant axis */
193			pri = RED;
194			if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
195			pri = GRN;
196			if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
197			pri = BLU;
198			/* sum histogram over box */
199			med = 0;
200			switch (pri) {
201			case RED:
202			for (r = box[RED][0]; r < box[RED][1]; r++) {
203			t[r] = 0;
204			for (g = box[GRN][0]; g < box[GRN][1]; g++)
205			for (b = box[BLU][0]; b < box[BLU][1]; b++)
206			t[r] += histo[r][g][b];
207			med += t[r];
208			}
209			break;
210			case GRN:
211			for (g = box[GRN][0]; g < box[GRN][1]; g++) {
212			t[g] = 0;
213			for (b = box[BLU][0]; b < box[BLU][1]; b++)
214			for (r = box[RED][0]; r < box[RED][1]; r++)
215			t[g] += histo[r][g][b];
216			med += t[g];
217			}
218			break;
219			case BLU:
220			for (b = box[BLU][0]; b < box[BLU][1]; b++) {
221			t[b] = 0;
222			for (r = box[RED][0]; r < box[RED][1]; r++)
223			for (g = box[GRN][0]; g < box[GRN][1]; g++)
224			t[b] += histo[r][g][b];
225			med += t[b];
226			}
227			break;
228			}
229			if (med < MINSAMP) /* if too sparse, split at midpoint */
230			return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
231			/* find median position */
232			med >>= 1;
233			for (c0 = box[pri][0]; med > 0; c0++)
234			med -= t[c0];
235			if (c0 > (box[pri][0]+box[pri][1])>>1) /* if past the midpoint */
236			c0--; /* part left of median */
237			return(set_branch(pri,c0));
238			#undef c0
239			}