src/hd/rhd_ctab.c

#ifndef lint
static const char       RCSid[] = "$Id: rhd_ctab.c,v 3.4 2003/06/30 14:59:11 schorsch Exp $";
#endif
/*
 * 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.
 *
 *      This module is essentially identical to src/rt/colortab.c,
 *      except there is no color mapping, since the tm library is used.
 */

#include <string.h>

#include "standard.h"
#include "rhdisp.h"
#include "color.h"
                                /* 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
                                /* color partition tree */
#define CNODE           short
#define set_branch(p,c) ((c)<<2|(p))
#define set_pval(pv)    ((pv)<<2|3)
#define is_branch(cn)   (((cn)&3)!=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 */
static struct tabent {
        long    sum[3];         /* sum of colors using this entry */
        int     n;              /* number of colors */
        BYTE    ent[3];         /* current table value */
}       *clrtab = NULL;
                                /* color cube partition */
static CNODE    *ctree = NULL;
                                /* histogram of colors used */
static unsigned short   histo[NRED][NGRN][NBLU];
                                /* initial color cube boundary */
static int      CLRCUBE[3][2] = {{0,NRED},{0,NGRN},{0,NBLU}};

static void cut(CNODE *tree, int level, int box[3][2], int c0, int c1);
static int split(int box[3][2]);


extern int
new_ctab(               /* start new color table with max ncolors */
        int     ncolors
)
{
        int     treesize;

        if (ncolors < 1)
                return(0);
                                /* free old tables */
        if (clrtab != NULL)
                free((void *)clrtab);
        if (ctree != NULL)
                free((void *)ctree);
                                /* get new tables */
        for (treesize = 1; treesize < ncolors; treesize <<= 1)
                ;
        treesize <<= 1;
        clrtab = (struct tabent *)calloc(ncolors, sizeof(struct tabent));
        ctree = (CNODE *)malloc(treesize*sizeof(CNODE));
        if (clrtab == NULL || ctree == NULL)
                return(0);
                                /* partition color space */
        cut(ctree, 0, CLRCUBE, 0, ncolors);
                                /* clear histogram */
        memset((void *)histo, '\0', sizeof(histo));
                                /* return number of colors used */
        return(ncolors);
}


extern int
get_pixel(      /* get pixel for color */
        BYTE    rgb[3],
        void    (*set_pixel)(int h, int r, int g, int b)
)
{
        int     r, g, b;
        int     cv[3];
        register CNODE  *tp;
        register int    h;
                                                /* get desired color */
        r = rgb[RED];
        g = rgb[GRN];
        b = rgb[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 */
        for (tp = ctree, h = 0; is_branch(*tp); h++)
                if (cv[prim(*tp)] < part(*tp))
                        tp += 1<<h;             /* left branch */
                else
                        tp += 1<<(h+1);         /* right branch */
        h = pval(*tp);
                                                /* add to color table */
        clrtab[h].sum[RED] += r;
        clrtab[h].sum[GRN] += g;
        clrtab[h].sum[BLU] += b;
        clrtab[h].n++;
                                        /* recompute average */
        r = clrtab[h].sum[RED] / clrtab[h].n;
        g = clrtab[h].sum[GRN] / clrtab[h].n;
        b = clrtab[h].sum[BLU] / clrtab[h].n;
                                        /* check for movement */
        if (clrtab[h].n == 1 ||
                        (r-clrtab[h].ent[RED])*(r-clrtab[h].ent[RED]) +
                        (g-clrtab[h].ent[GRN])*(g-clrtab[h].ent[GRN]) +
                        (b-clrtab[h].ent[BLU])*(b-clrtab[h].ent[BLU]) > MAXDST2) {
                clrtab[h].ent[RED] = r;
                clrtab[h].ent[GRN] = g; /* reassign pixel */
                clrtab[h].ent[BLU] = b;
#ifdef DEBUG
                {
                        extern char     errmsg[];
                        sprintf(errmsg, "pixel %d = (%d,%d,%d) (%d refs)\n",
                                        h, r, g, b, clrtab[h].n);
                        eputs(errmsg);
                }
#endif
                (*set_pixel)(h, r, g, b);
        }
        return(h);                              /* return pixel value */
}


static void
cut(            /* partition color space */
        register CNODE  *tree,
        int     level,
        register int    box[3][2],
        int     c0,
        int     c1
)
{
        int     kb[3][2];
        
        if (c1-c0 <= 1) {               /* assign pixel */
                *tree = set_pval(c0);
                return;
        }
                                        /* split box */
        *tree = split(box);
        memcpy((void *)kb, (void *)box, sizeof(kb));
                                                /* do left (lesser) branch */
        kb[prim(*tree)][1] = part(*tree);
        cut(tree+(1<<level), level+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<<(level+1)), level+1, kb, (c0+c1)>>1, c1);
}


static int
split(                          /* find median cut for box */
        register int    box[3][2]
)
{
#define c0      r
        register int    r, g, b;
        int     pri;
        long    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:	3.5
Committed:	Thu Jan 1 11:21:55 2004 UTC (21 years, 9 months ago) by schorsch
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R7P2, rad3R7P1, rad4R0, rad3R6, rad3R6P1, rad3R8, rad3R9
Changes since 3.4:	+31 -21 lines
Log Message:	Ansification and prototypes.
#	User	Rev	Content
1	gregl	3.1	#ifndef lint
2	schorsch	3.5	static const char RCSid[] = "$Id: rhd_ctab.c,v 3.4 2003/06/30 14:59:11 schorsch Exp $";
3	gregl	3.1	#endif
4			/*
5			* 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			* This module is essentially identical to src/rt/colortab.c,
16			* except there is no color mapping, since the tm library is used.
17			*/
18
19	schorsch	3.4	#include <string.h>
20
21	gregl	3.1	#include "standard.h"
22	schorsch	3.5	#include "rhdisp.h"
23	gregl	3.1	#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	schorsch	3.5	static void cut(CNODE *tree, int level, int box[3][2], int c0, int c1);
56			static int split(int box[3][2]);
57	gregl	3.1
58
59	schorsch	3.5
60			extern int
61			new_ctab( /* start new color table with max ncolors */
62			int ncolors
63			)
64	gregl	3.1	{
65			int treesize;
66
67			if (ncolors < 1)
68			return(0);
69			/* free old tables */
70			if (clrtab != NULL)
71	greg	3.2	free((void *)clrtab);
72	gregl	3.1	if (ctree != NULL)
73	greg	3.2	free((void *)ctree);
74	gregl	3.1	/* get new tables */
75			for (treesize = 1; treesize < ncolors; treesize <<= 1)
76			;
77			treesize <<= 1;
78			clrtab = (struct tabent *)calloc(ncolors, sizeof(struct tabent));
79			ctree = (CNODE )malloc(treesizesizeof(CNODE));
80			if (clrtab == NULL \|\| ctree == NULL)
81			return(0);
82			/* partition color space */
83			cut(ctree, 0, CLRCUBE, 0, ncolors);
84			/* clear histogram */
85	schorsch	3.4	memset((void *)histo, '\0', sizeof(histo));
86	gregl	3.1	/* return number of colors used */
87			return(ncolors);
88			}
89
90
91	schorsch	3.5	extern int
92			get_pixel( /* get pixel for color */
93			BYTE rgb[3],
94			void (*set_pixel)(int h, int r, int g, int b)
95			)
96	gregl	3.1	{
97			int r, g, b;
98			int cv[3];
99			register CNODE *tp;
100			register int h;
101			/* get desired color */
102			r = rgb[RED];
103			g = rgb[GRN];
104			b = rgb[BLU];
105			/* reduce resolution */
106			cv[RED] = (r*NRED)>>8;
107			cv[GRN] = (g*NGRN)>>8;
108			cv[BLU] = (b*NBLU)>>8;
109			/* add to histogram */
110			histo[cv[RED]][cv[GRN]][cv[BLU]]++;
111			/* find pixel in tree */
112			for (tp = ctree, h = 0; is_branch(*tp); h++)
113			if (cv[prim(tp)] < part(tp))
114			tp += 1<<h; /* left branch */
115			else
116			tp += 1<<(h+1); /* right branch */
117			h = pval(*tp);
118			/* add to color table */
119			clrtab[h].sum[RED] += r;
120			clrtab[h].sum[GRN] += g;
121			clrtab[h].sum[BLU] += b;
122			clrtab[h].n++;
123			/* recompute average */
124			r = clrtab[h].sum[RED] / clrtab[h].n;
125			g = clrtab[h].sum[GRN] / clrtab[h].n;
126			b = clrtab[h].sum[BLU] / clrtab[h].n;
127			/* check for movement */
128			if (clrtab[h].n == 1 \|\|
129			(r-clrtab[h].ent[RED])*(r-clrtab[h].ent[RED]) +
130			(g-clrtab[h].ent[GRN])*(g-clrtab[h].ent[GRN]) +
131			(b-clrtab[h].ent[BLU])*(b-clrtab[h].ent[BLU]) > MAXDST2) {
132			clrtab[h].ent[RED] = r;
133			clrtab[h].ent[GRN] = g; /* reassign pixel */
134			clrtab[h].ent[BLU] = b;
135			#ifdef DEBUG
136	schorsch	3.5	{
137			extern char errmsg[];
138			sprintf(errmsg, "pixel %d = (%d,%d,%d) (%d refs)\n",
139			h, r, g, b, clrtab[h].n);
140			eputs(errmsg);
141			}
142	gregl	3.1	#endif
143			(*set_pixel)(h, r, g, b);
144			}
145			return(h); /* return pixel value */
146			}
147
148
149	schorsch	3.5	static void
150			cut( /* partition color space */
151			register CNODE *tree,
152			int level,
153			register int box[3][2],
154			int c0,
155			int c1
156			)
157	gregl	3.1	{
158			int kb[3][2];
159
160			if (c1-c0 <= 1) { /* assign pixel */
161			*tree = set_pval(c0);
162			return;
163			}
164			/* split box */
165			*tree = split(box);
166	schorsch	3.4	memcpy((void )kb, (void )box, sizeof(kb));
167	gregl	3.1	/* do left (lesser) branch */
168			kb[prim(tree)][1] = part(tree);
169			cut(tree+(1<<level), level+1, kb, c0, (c0+c1)>>1);
170			/* do right branch */
171			kb[prim(tree)][0] = part(tree);
172			kb[prim(tree)][1] = box[prim(tree)][1];
173			cut(tree+(1<<(level+1)), level+1, kb, (c0+c1)>>1, c1);
174			}
175
176
177			static int
178	schorsch	3.5	split( /* find median cut for box */
179			register int box[3][2]
180			)
181	gregl	3.1	{
182			#define c0 r
183			register int r, g, b;
184			int pri;
185			long t[HMAX], med;
186			/* find dominant axis */
187			pri = RED;
188			if (box[GRN][1]-box[GRN][0] > box[pri][1]-box[pri][0])
189			pri = GRN;
190			if (box[BLU][1]-box[BLU][0] > box[pri][1]-box[pri][0])
191			pri = BLU;
192			/* sum histogram over box */
193			med = 0;
194			switch (pri) {
195			case RED:
196			for (r = box[RED][0]; r < box[RED][1]; r++) {
197			t[r] = 0;
198			for (g = box[GRN][0]; g < box[GRN][1]; g++)
199			for (b = box[BLU][0]; b < box[BLU][1]; b++)
200			t[r] += histo[r][g][b];
201			med += t[r];
202			}
203			break;
204			case GRN:
205			for (g = box[GRN][0]; g < box[GRN][1]; g++) {
206			t[g] = 0;
207			for (b = box[BLU][0]; b < box[BLU][1]; b++)
208			for (r = box[RED][0]; r < box[RED][1]; r++)
209			t[g] += histo[r][g][b];
210			med += t[g];
211			}
212			break;
213			case BLU:
214			for (b = box[BLU][0]; b < box[BLU][1]; b++) {
215			t[b] = 0;
216			for (r = box[RED][0]; r < box[RED][1]; r++)
217			for (g = box[GRN][0]; g < box[GRN][1]; g++)
218			t[b] += histo[r][g][b];
219			med += t[b];
220			}
221			break;
222			}
223			if (med < MINSAMP) /* if too sparse, split at midpoint */
224			return(set_branch(pri,(box[pri][0]+box[pri][1])>>1));
225			/* find median position */
226			med >>= 1;
227			for (c0 = box[pri][0]; med > 0; c0++)
228			med -= t[c0];
229			if (c0 > (box[pri][0]+box[pri][1])>>1) /* if past the midpoint */
230			c0--; /* part left of median */
231			return(set_branch(pri,c0));
232			#undef c0
233			}