ProfitPress Mega CDROM2 …eeware (MSDOS)(1992)(Eng)/ProfitPress-MegaCDROM2.B6I/GRAPHICS/MISC/PVQUAN15.ZIP/QUANT.ZIP/OCTREE.C

C/C++ Source or Header | 1991-10-22 | 5.0 KB | 176 lines

/************************************************************************
 *                                                                      *
 *                  Copyright (c) 1991, Frank van der Hulst             *
 *                          All Rights Reserved                         *
 *                                                                      *
 * Authors:                                                             *
 *          FvdH - Frank van der Hulst (Wellington, NZ)                     *
 *                                                                      *
 * Versions:                                                            *
 *      V1.1 910626 FvdH - QUANT released for DBW_RENDER                *
 *      V1.2 911021 FvdH - QUANT released for PoV Ray                   *
 *                                                                      *
 ************************************************************************/
/* This code implements the alogrithm described in:
 * Graphic Gems edited by Andrew Glassner
 * Article: A Simple Method for Color Quantisation:
 *          Octree Quantisation, pg. 287 ff
 * by:      Michael Gervautz, Werner Purgathofer
 *          Technical University Vienna
 *          Vienna, Austria
 */

/* Written by wRZL (Wolfgang Stuerzlinger) */

/* This code is hereby placed in public domain */

#include <string.h>
#include "quant.h"
#include "octree.h"

#define RGB(r,g,b) ((((unsigned long)(b) << input_bits) | ((g) << input_bits)) | (r))
#define TESTBIT(a,i) ( ((a) >> (i)) & 1)
#define MAXDEPTH 7

static UINT size;
static UINT reducelevel;
static UINT leaflevel;
static OCTREE tree;
static OCTREE reducelist[MAXDEPTH + 1];

static unsigned char quant_r,    /* Originally a parameter for quant2(), */
                            quant_g,    /* moved here to reduce stack usage */
                            quant_b;

static char quant2(OCTREE tree)
{
    if (tree->leaf)   return(tree->colorindex);
    else                    return(quant2(tree->next[
                                TESTBIT(quant_r, MAXDEPTH - tree->level) * 4 +
                                TESTBIT(quant_g, MAXDEPTH - tree->level) * 2 +
                                TESTBIT(quant_b, MAXDEPTH - tree->level)]));
}

int pal_index(UCHAR *p)
{
    quant_r = p[RED];
    quant_g = p[GREEN];
    quant_b = p[BLUE];
    return quant2(tree);
}

static double init_Cfactor;
static UINT init_col_num;

static void initpalette(OCTREE tree)
{
    UINT j;

    if (tree == NULL) return;
    if (tree->leaf || tree->level == leaflevel) {
        palette[init_col_num][RED]   = (char) ((init_Cfactor * tree->rgbsum.r) / tree->colorcount + 0.5);
        palette[init_col_num][GREEN] = (char) ((init_Cfactor * tree->rgbsum.g) / tree->colorcount + 0.5);
        palette[init_col_num][BLUE]  = (char) ((init_Cfactor * tree->rgbsum.b) / tree->colorcount + 0.5);
        tree->colorindex = init_col_num;
        tree->leaf = TRUE;
        init_col_num++;
    } else {
        for (j = 0; j < 8; j++)
            initpalette(tree->next[j]);
    }
}

UINT calc_palette(UINT i, double Cfactor)
{
    init_Cfactor = Cfactor;
    init_col_num = i;
    initpalette(tree);
    return init_col_num;
}


static void newandinit(OCTREE *tree, UINT depth)
    {
    *tree = (OCTREE)calloc(1,sizeof(struct node));
    if (*tree == NULL) {
        printf("out of memory");
        exit(1);
        }
    (*tree)->level = depth;
    (*tree)->leaf = (depth >= leaflevel);
    if ((*tree)->leaf)
        size++;
    }

static void getreduceable(OCTREE *node)
    {
    UINT newreducelevel;

    newreducelevel = reducelevel;
    while (reducelist[newreducelevel] == NULL)
        newreducelevel--;
    *node = reducelist[newreducelevel];
    reducelist[newreducelevel] =
                reducelist[newreducelevel]->nextreduceable;
    }

static void makereduceable(UINT level,OCTREE node)
{
    node->nextreduceable = reducelist[level];
    reducelist[level] = node;
}

static void reducetree(void)
{
    OCTREE node;
    UINT depth;

    getreduceable(&node);
    node->leaf = 1;
    size = size - node->children + 1;
    depth = node->level;
    if (depth < reducelevel) {
        reducelevel = depth;
        leaflevel = reducelevel + 1;
    }
}

static UCHAR insert_rgb[3];   /* Originally a parameter for inserttree(), moved
                                        here to reduce stack usage */

static void inserttree(OCTREE *tree, UINT depth)
{
    UINT branch;

    if (*tree == NULL)
        newandinit(tree,depth);
    (*tree)->colorcount++;
    (*tree)->rgbsum.r += insert_rgb[RED];
    (*tree)->rgbsum.g += insert_rgb[GREEN];
    (*tree)->rgbsum.b += insert_rgb[BLUE];
    if ((*tree)->leaf == FALSE && depth < leaflevel) {
        branch = TESTBIT(insert_rgb[RED],MAXDEPTH - depth) * 4 +
                    TESTBIT(insert_rgb[GREEN],MAXDEPTH - depth) * 2 +
                    TESTBIT(insert_rgb[BLUE],MAXDEPTH - depth);
        if ((*tree)->next[branch] == NULL) {
            (*tree)->children++;
            if ((*tree)->children == 2)
                makereduceable(depth,*tree);
        }
        inserttree(&((*tree)->next[branch]), depth + 1);
    }
}

void generateoctree(void)
{
    reducelevel = MAXDEPTH;
    leaflevel = reducelevel + 1;

    while (get_pixel(insert_rgb)) {
        inserttree(&tree, 0);
        if (size > MAXCOLORS - 1)        /* max number of colors ! */
            reducetree();
    }
}