ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/Development/ray/src/px/clrtab.c

Comparing ray/src/px/clrtab.c (file contents):
Revision 2.1 by greg, Mon Oct 12 12:58:39 1992 UTC vs.
Revision 2.18 by greg, Mon Sep 19 02:23:58 2005 UTC

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

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines (old)
>	Changed lines (new)