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            28
#define NGRN            32
#define NBLU            22
#define HMAX            NGRN
                                /* minimum box count for adaptive partition */
#define MINSAMP         7
                                /* maximum frame buffer depth */
#define FBDEPTH         8
                                /* color map resolution */
#define MAPSIZ          128
                                /* map a color */
#define map_col(c,p)    clrmap[p][ colval(c,p)<1. ? \
                                (int)(colval(c,p)*MAPSIZ) : MAPSIZ-1 ]
                                /* 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 */
COLR    clrtab[1<<FBDEPTH];
                                /* our color correction map */
static BYTE     clrmap[3][MAPSIZ];
                                /* 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)];


COLR *
get_ctab(ncolors)       /* assign a color table with max ncolors */
int     ncolors;
{
        if (ncolors < 1 || ncolors > 1<<FBDEPTH)
                return(NULL);
                                /* partition color table */
        cut(ctree, FBDEPTH, CLRCUBE, 0, ncolors);
                                /* clear histogram */
        bzero(histo, sizeof(histo));
                                /* return color table */
        return(clrtab);
}


int
get_pixel(col)                  /* get pixel for color */
COLOR   col;
{
        int     cv[3];
        register CNODE  *tp;
        register int    h;
                                        /* map color */
        cv[RED] = map_col(col,RED);
        cv[GRN] = map_col(col,GRN);
        cv[BLU] = map_col(col,BLU);
                                        /* add to histogram */
        histo[cv[RED]][cv[GRN]][cv[BLU]]++;
                                        /* find pixel value in tree */
        tp = ctree;
        for (h = FBDEPTH; h > 0; h--) {
                if (is_pval(*tp))
                        break;
                if (cv[prim(*tp)] < part(*tp))
                        tp++;                   /* left branch */
                else
                        tp += 1<<h;             /* right branch */
        }
#ifdef notdef
        printf("distance (%d,%d,%d)\n",
                cv[RED] - clrtab[pval(*tp)][RED]*NRED/256, 
                cv[GRN] - clrtab[pval(*tp)][GRN]*NGRN/256,
                cv[BLU] - clrtab[pval(*tp)][BLU]*NBLU/256);
#endif
        return(pval(*tp));
}


make_cmap(gam)                  /* make gamma correction map */
double  gam;
{
        extern double   pow();
        double  d;
        register int    i;
        
        for (i = 0; i < MAPSIZ; i++) {
                d = pow(i/(double)MAPSIZ, 1.0/gam);
                clrmap[RED][i] = d * NRED;
                clrmap[GRN][i] = d * NGRN;
                clrmap[BLU][i] = d * NBLU;
        }
}


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 color */
                clrtab[c0][RED] = ((box[RED][0]+box[RED][1])<<7)/NRED;
                clrtab[c0][GRN] = ((box[GRN][0]+box[GRN][1])<<7)/NGRN;
                clrtab[c0][BLU] = ((box[BLU][0]+box[BLU][1])<<7)/NBLU;
                clrtab[c0][EXP] = COLXS;
                *tree = set_pval(c0);
#ifdef notdef
                printf("final box size = (%d,%d,%d)\n",
                        box[RED][1] - box[RED][0],
                        box[GRN][1] - box[GRN][0],
                        box[BLU][1] - box[BLU][0]);
#endif
                return;
        }
                                        /* split box */
        *tree = split(box);
        bcopy(box, kb, sizeof(kb));
        kb[prim(*tree)][1] = part(*tree);
        cut(tree+1, height-1, kb, c0, (c0+c1)>>1);              /* lesser */
        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);    /* greater */
}


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.2
Committed:	Mon Oct 2 17:12:42 1989 UTC (34 years, 7 months ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 1.1:	+2 -2 lines
Log Message:	New adaptive color allocation scheme for rview
#	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.2	#define NRED 28
24	greg	1.1	#define NGRN 32
25	greg	1.2	#define NBLU 22
26	greg	1.1	#define HMAX NGRN
27			/* minimum box count for adaptive partition */
28			#define MINSAMP 7
29			/* maximum frame buffer depth */
30			#define FBDEPTH 8
31			/* color map resolution */
32			#define MAPSIZ 128
33			/* map a color */
34			#define map_col(c,p) clrmap[p][ colval(c,p)<1. ? \
35			(int)(colval(c,p)*MAPSIZ) : MAPSIZ-1 ]
36			/* 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			COLR clrtab[1<<FBDEPTH];
46			/* our color correction map */
47			static BYTE clrmap[3][MAPSIZ];
48			/* histogram of colors used */
49			static unsigned histo[NRED][NGRN][NBLU];
50			/* initial color cube boundaries */
51			static int CLRCUBE[3][2] = {0,NRED,0,NGRN,0,NBLU};
52			/* color cube partition */
53			static CNODE ctree[1<<(FBDEPTH+1)];
54
55
56			COLR *
57			get_ctab(ncolors) /* assign a color table with max ncolors */
58			int ncolors;
59			{
60			if (ncolors < 1 \|\| ncolors > 1<<FBDEPTH)
61			return(NULL);
62			/* partition color table */
63			cut(ctree, FBDEPTH, CLRCUBE, 0, ncolors);
64			/* clear histogram */
65			bzero(histo, sizeof(histo));
66			/* return color table */
67			return(clrtab);
68			}
69
70
71			int
72			get_pixel(col) /* get pixel for color */
73			COLOR col;
74			{
75			int cv[3];
76			register CNODE *tp;
77			register int h;
78			/* map color */
79			cv[RED] = map_col(col,RED);
80			cv[GRN] = map_col(col,GRN);
81			cv[BLU] = map_col(col,BLU);
82			/* add to histogram */
83			histo[cv[RED]][cv[GRN]][cv[BLU]]++;
84			/* find pixel value in tree */
85			tp = ctree;
86			for (h = FBDEPTH; h > 0; h--) {
87			if (is_pval(*tp))
88			break;
89			if (cv[prim(tp)] < part(tp))
90			tp++; /* left branch */
91			else
92			tp += 1<<h; /* right branch */
93			}
94			#ifdef notdef
95			printf("distance (%d,%d,%d)\n",
96			cv[RED] - clrtab[pval(tp)][RED]NRED/256,
97			cv[GRN] - clrtab[pval(tp)][GRN]NGRN/256,
98			cv[BLU] - clrtab[pval(tp)][BLU]NBLU/256);
99			#endif
100			return(pval(*tp));
101			}
102
103
104			make_cmap(gam) /* make gamma correction map */
105			double gam;
106			{
107			extern double pow();
108			double d;
109			register int i;
110
111			for (i = 0; i < MAPSIZ; i++) {
112			d = pow(i/(double)MAPSIZ, 1.0/gam);
113			clrmap[RED][i] = d * NRED;
114			clrmap[GRN][i] = d * NGRN;
115			clrmap[BLU][i] = d * NBLU;
116			}
117			}
118
119
120			static
121			cut(tree, height, box, c0, c1) /* partition color space */
122			register CNODE *tree;
123			int height;
124			register int box[3][2];
125			int c0, c1;
126			{
127			int kb[3][2];
128
129			if (c1-c0 == 1) { /* assign color */
130			clrtab[c0][RED] = ((box[RED][0]+box[RED][1])<<7)/NRED;
131			clrtab[c0][GRN] = ((box[GRN][0]+box[GRN][1])<<7)/NGRN;
132			clrtab[c0][BLU] = ((box[BLU][0]+box[BLU][1])<<7)/NBLU;
133			clrtab[c0][EXP] = COLXS;
134			*tree = set_pval(c0);
135			#ifdef notdef
136			printf("final box size = (%d,%d,%d)\n",
137			box[RED][1] - box[RED][0],
138			box[GRN][1] - box[GRN][0],
139			box[BLU][1] - box[BLU][0]);
140			#endif
141			return;
142			}
143			/* split box */
144			*tree = split(box);
145			bcopy(box, kb, sizeof(kb));
146			kb[prim(tree)][1] = part(tree);
147			cut(tree+1, height-1, kb, c0, (c0+c1)>>1); /* lesser */
148			kb[prim(tree)][0] = part(tree);
149			kb[prim(tree)][1] = box[prim(tree)][1];
150			cut(tree+(1<<height), height-1, kb, (c0+c1)>>1, c1); /* greater */
151			}
152
153
154			static int
155			split(box) /* find median cut for box */
156			register int box[3][2];
157			{
158			#define c0 r
159			register int r, g, b;
160			int pri;
161			int t[HMAX], med;
162			/* find dominant axis */
163			pri = RED;
164			if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
165			pri = GRN;
166			if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
167			pri = BLU;
168			/* sum histogram over box */
169			med = 0;
170			switch (pri) {
171			case RED:
172			for (r = box[RED][0]; r < box[RED][1]; r++) {
173			t[r] = 0;
174			for (g = box[GRN][0]; g < box[GRN][1]; g++)
175			for (b = box[BLU][0]; b < box[BLU][1]; b++)
176			t[r] += histo[r][g][b];
177			med += t[r];
178			}
179			break;
180			case GRN:
181			for (g = box[GRN][0]; g < box[GRN][1]; g++) {
182			t[g] = 0;
183			for (b = box[BLU][0]; b < box[BLU][1]; b++)
184			for (r = box[RED][0]; r < box[RED][1]; r++)
185			t[g] += histo[r][g][b];
186			med += t[g];
187			}
188			break;
189			case BLU:
190			for (b = box[BLU][0]; b < box[BLU][1]; b++) {
191			t[b] = 0;
192			for (r = box[RED][0]; r < box[RED][1]; r++)
193			for (g = box[GRN][0]; g < box[GRN][1]; g++)
194			t[b] += histo[r][g][b];
195			med += t[b];
196			}
197			break;
198			}
199			if (med < MINSAMP) /* if too sparse, split at midpoint */
200			return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
201			/* find median position */
202			med >>= 1;
203			for (c0 = box[pri][0]; med > 0; c0++)
204			med -= t[c0];
205			if (c0 > (box[pri][0]+box[pri][1])>>1) /* if past the midpoint */
206			c0--; /* part left of median */
207			return(set_branch(pri,c0));
208			#undef c0
209			}