15 struct octnode *redlist[NUM_LEVELS];
26 struct octnode *sub[8];
31 static void init_octree(struct octree *tree, int maxcol);
32 static void destroy_octree(struct octree *tree);
34 static struct octnode *alloc_node(struct octree *tree, int lvl);
35 static void free_node(struct octnode *n);
36 static void free_tree(struct octnode *n);
38 static void add_color(struct octree *tree, int r, int g, int b, int nref);
39 static void reduce_colors(struct octree *tree);
40 static int assign_colors(struct octnode *n, int next, struct cmapent *cmap);
41 static int lookup_color(struct octree *tree, int r, int g, int b);
42 static int subidx(int bit, int r, int g, int b);
43 static void print_tree(struct octnode *n, int lvl);
45 int quantize_image(struct image *img, int maxcol)
50 struct image newimg = *img;
52 if(maxcol < 2 || maxcol > 256) {
57 newimg.bpp = maxcol > 16 ? 8 : 4;
59 newimg.scansz = newimg.width * newimg.bpp / 8;
60 newimg.pitch = newimg.scansz;
63 init_octree(&tree, maxcol);
65 for(i=0; i<img->height; i++) {
66 for(j=0; j<img->width; j++) {
67 get_pixel_rgb(img, j, i, rgb);
68 add_color(&tree, rgb[0], rgb[1], rgb[2], 1);
70 while(tree.nleaves > maxcol) {
76 /* use created octree to generate the palette */
77 newimg.cmap_ncolors = assign_colors(tree.root, 0, newimg.cmap);
79 /* replace image pixels */
80 for(i=0; i<img->height; i++) {
81 for(j=0; j<img->width; j++) {
82 get_pixel_rgb(img, j, i, rgb);
83 cidx = lookup_color(&tree, rgb[0], rgb[1], rgb[2]);
84 assert(cidx >= 0 && cidx < maxcol);
85 put_pixel(&newimg, j, i, cidx);
91 destroy_octree(&tree);
95 int gen_shades(struct image *img, int levels, int maxcol, int *shade_lut)
97 int i, j, cidx, r, g, b;
98 unsigned int color[3];
100 struct image newimg = *img;
102 if(maxcol < 2 || maxcol > 256) {
106 init_octree(&tree, maxcol);
108 for(i=0; i<img->cmap_ncolors; i++) {
109 add_color(&tree, img->cmap[i].r, img->cmap[i].g, img->cmap[i].b, 1024);
112 for(i=0; i<img->cmap_ncolors; i++) {
113 for(j=0; j<levels - 1; j++) {
114 r = img->cmap[i].r * j / (levels - 1);
115 g = img->cmap[i].g * j / (levels - 1);
116 b = img->cmap[i].b * j / (levels - 1);
117 add_color(&tree, r, g, b, 1);
119 while(tree.nleaves > maxcol) {
120 reduce_colors(&tree);
125 newimg.cmap_ncolors = assign_colors(tree.root, 0, newimg.cmap);
127 /* replace image pixels */
128 for(i=0; i<img->height; i++) {
129 for(j=0; j<img->width; j++) {
130 get_pixel_rgb(img, j, i, color);
131 cidx = lookup_color(&tree, color[0], color[1], color[2]);
132 put_pixel(&newimg, j, i, cidx);
136 /* populate shade_lut based on the new palette, can't generate levels only
137 * for the original colors, because the palette entries will have changed
140 for(i=0; i<newimg.cmap_ncolors; i++) {
141 for(j=0; j<levels; j++) {
142 r = newimg.cmap[i].r * j / (levels - 1);
143 g = newimg.cmap[i].g * j / (levels - 1);
144 b = newimg.cmap[i].b * j / (levels - 1);
145 *shade_lut++ = lookup_color(&tree, r, g, b);
148 for(i=0; i<(maxcol - newimg.cmap_ncolors) * levels; i++) {
149 *shade_lut++ = maxcol - 1;
154 destroy_octree(&tree);
158 static void init_octree(struct octree *tree, int maxcol)
160 memset(tree, 0, sizeof *tree);
162 tree->redlev = NUM_LEVELS - 1;
163 tree->maxcol = maxcol;
165 tree->root = alloc_node(tree, 0);
168 static void destroy_octree(struct octree *tree)
170 free_tree(tree->root);
173 static struct octnode *alloc_node(struct octree *tree, int lvl)
177 if(!(n = calloc(1, sizeof *n))) {
178 perror("failed to allocate octree node");
186 if(lvl < tree->redlev) {
187 n->next = tree->redlist[lvl];
188 tree->redlist[lvl] = n;
196 static void free_node(struct octnode *n)
198 struct octnode *prev, dummy;
200 dummy.next = n->tree->redlist[n->lvl];
203 if(prev->next == n) {
204 prev->next = n->next;
209 n->tree->redlist[n->lvl] = dummy.next;
213 assert(n->tree->nleaves >= 0);
218 static void free_tree(struct octnode *n)
225 free_tree(n->sub[i]);
230 static void add_color(struct octree *tree, int r, int g, int b, int nref)
232 int i, idx, rr, gg, bb;
245 for(i=0; i<NUM_LEVELS; i++) {
248 idx = subidx(i, r, g, b);
251 n->sub[idx] = alloc_node(tree, i + 1);
263 static struct octnode *get_reducible(struct octree *tree)
266 struct octnode dummy, *n, *prev, *best_prev, *best = 0;
268 while(tree->redlev >= 0) {
271 dummy.next = tree->redlist[tree->redlev];
275 if(n->nref < best_nref) {
283 best_prev->next = best->next;
284 tree->redlist[tree->redlev] = dummy.next;
293 static void reduce_colors(struct octree *tree)
298 if(!(n = get_reducible(tree))) {
299 fprintf(stderr, "warning: no reducible nodes!\n");
304 free_node(n->sub[i]);
312 static int assign_colors(struct octnode *n, int next, struct cmapent *cmap)
319 assert(next < n->tree->maxcol);
321 cmap[next].r = n->r / n->nref;
322 cmap[next].g = n->g / n->nref;
323 cmap[next].b = n->b / n->nref;
329 next = assign_colors(n->sub[i], next, cmap);
334 static int lookup_color(struct octree *tree, int r, int g, int b)
340 for(i=0; i<NUM_LEVELS; i++) {
342 assert(n->palidx >= 0);
346 idx = subidx(i, r, g, b);
348 if(n->sub[idx]) break;
356 fprintf(stderr, "lookup_color(%d, %d, %d) failed!\n", r, g, b);
361 static int subidx(int bit, int r, int g, int b)
363 assert(bit >= 0 && bit < NUM_LEVELS);
364 bit = NUM_LEVELS - 1 - bit;
365 return ((r >> bit) & 1) | ((g >> (bit - 1)) & 2) | ((b >> (bit - 2)) & 4);
368 static void print_tree(struct octnode *n, int lvl)
375 for(i=0; i<lvl; i++) {
379 sprintf(ptrbuf, "%p", (void*)n);
380 p = ptrbuf + strlen(ptrbuf) - 4;
383 printf("+-(%d) %s: <%d %d %d> #%d", n->lvl, p, n->r / n->nref, n->g / n->nref,
384 n->b / n->nref, n->nref);
386 printf("+-(%d) %s: <- - -> #0", n->lvl, p);
388 if(n->palidx >= 0) printf(" [%d]", n->palidx);
389 if(n->leaf) printf(" LEAF");
393 print_tree(n->sub[i], lvl + 1);