ViewVC Help
View File | Revision Log | Show Annotations | Download File | Root Listing
root/radiance/ray/src/px/clrtab.c
(Generate patch)

Comparing ray/src/px/clrtab.c (file contents):
Revision 2.1 by greg, Mon Oct 12 12:58:39 1992 UTC vs.
Revision 2.19 by greg, Fri May 20 02:06:39 2011 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 uby8     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(uby8 *nl[], int r, int g, int b);
45 > static void addneigh(uby8 *nl[], int i, int j);
46 > static unsigned int dist(uby8 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 uby8   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((uby8 *)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 uby8   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 uby8   *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 uby8   *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 +        uby8    *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] = (uby8 *)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 uby8   *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] = (uby8 *)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 uby8   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 +        uby8    *nl[],
404 +        int     r,
405 +        int     g,
406 +        int     b
407 + )
408 + {
409 +        int     ident;
410 +        unsigned        min;
411 +        register unsigned       d;
412 +        register uby8   *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
> Changed lines