mirror of
https://github.com/thug1src/thug.git
synced 2025-01-21 21:33:46 +00:00
980 lines
27 KiB
C++
980 lines
27 KiB
C++
|
|
#ifndef __CORE_DEFINES_H
|
|
#include <core/defines.h>
|
|
#endif
|
|
|
|
#include <gfx/ngps/PaletteGen.h>
|
|
|
|
|
|
namespace Nx
|
|
{
|
|
|
|
#define RED 1
|
|
#define GREEN 2
|
|
#define BLUE 3
|
|
#define ALPHA 4
|
|
|
|
#define MAXDEPTH 5
|
|
#define MAXCOLOR 256
|
|
|
|
#define ColorRealLengthSq(a) ((a)->red*(a)->red + (a)->green*(a)->green + (a)->blue*(a)->blue + (a)->alpha*(a)->alpha)
|
|
#define ColorRealFromColorInt(o,i) \
|
|
{ \
|
|
(o)->red = \
|
|
(((float)(((i)->r))) * ( (float)((1.0/255.0)))); \
|
|
(o)->green = \
|
|
(((float)(((i)->g))) * ( (float)((1.0/255.0)))); \
|
|
(o)->blue = \
|
|
(((float)(((i)->b))) * ( (float)((1.0/255.0)))); \
|
|
(o)->alpha = \
|
|
(((float)(((i)->a))) * ( (float)((1.0/255.0)))); \
|
|
} \
|
|
|
|
#define ColorRealScale(o,a,scale) \
|
|
{ \
|
|
(o)->red = (((a)->red) * ( scale)); \
|
|
(o)->green = (((a)->green) * ( scale)); \
|
|
(o)->blue = (((a)->blue) * ( scale)); \
|
|
(o)->alpha = (((a)->alpha) * ( scale)); \
|
|
} \
|
|
|
|
#define ColorRealAdd(o,a,b) \
|
|
{ \
|
|
(o)->red = (((a)->red) + ( (b)->red)); \
|
|
(o)->green = (((a)->green) + ( (b)->green)); \
|
|
(o)->blue = (((a)->blue) + ( (b)->blue)); \
|
|
(o)->alpha = (((a)->alpha) + ( (b)->alpha)); \
|
|
} \
|
|
|
|
#define ColorRealSub(o,a,b) \
|
|
{ \
|
|
(o)->red = (((a)->red) - ( (b)->red)); \
|
|
(o)->green = (((a)->green) - ( (b)->green)); \
|
|
(o)->blue = (((a)->blue) - ( (b)->blue)); \
|
|
(o)->alpha = (((a)->alpha) - ( (b)->alpha)); \
|
|
} \
|
|
|
|
typedef uint32 OctantMap;
|
|
|
|
/* local */
|
|
static OctantMap *p_splice = NULL;
|
|
|
|
/*************************************************************************/
|
|
static LeafNode *
|
|
InitLeaf(LeafNode * Leaf)
|
|
{
|
|
Dbg_Assert( Leaf );
|
|
|
|
Leaf->palIndex = 0;
|
|
Leaf->weight = 0.0f;
|
|
Leaf->ac.red = 0.0f;
|
|
Leaf->ac.green = 0.0f;
|
|
Leaf->ac.blue = 0.0f;
|
|
Leaf->ac.alpha = 0.0f;
|
|
Leaf->m2 = 0.0f;
|
|
|
|
return Leaf;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
static BranchNode *
|
|
InitBranch(BranchNode * Branch)
|
|
{
|
|
int i;
|
|
|
|
Dbg_Assert( Branch );
|
|
|
|
for (i = 0; i < 16; i++)
|
|
{
|
|
Branch->dir[i] = (OctNode *)NULL;
|
|
}
|
|
|
|
return Branch;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
static OctNode *
|
|
CreateCube( void )
|
|
{
|
|
OctNode *cube;
|
|
|
|
cube = (OctNode*) Mem::Calloc( 1, sizeof( OctNode ));
|
|
return(cube);
|
|
}
|
|
|
|
/*************************************************************************/
|
|
static OctantMap
|
|
GetOctAdr(Image::RGBA * c)
|
|
{
|
|
int cs = 8 - MAXDEPTH;
|
|
|
|
Dbg_Assert(c);
|
|
|
|
return((p_splice[c->r >> cs] << 3) | (p_splice[c->g >> cs] << 2) |
|
|
(p_splice[c->b >> cs] << 1) | (p_splice[c->a >> cs] << 0));
|
|
}
|
|
|
|
/*************************************************************************/
|
|
static OctNode *
|
|
AllocateToLeaf(PalQuant * pq, OctNode * root, OctantMap Octs, int depth)
|
|
{
|
|
|
|
Dbg_Assert(pq);
|
|
Dbg_Assert(root);
|
|
|
|
/* return leaf */
|
|
if (depth == 0)
|
|
{
|
|
return(root);
|
|
}
|
|
|
|
/* populate branch */
|
|
if (!root->Branch.dir[Octs & 15])
|
|
{
|
|
OctNode *node;
|
|
|
|
node = CreateCube();//(pq->cubefreelist);
|
|
root->Branch.dir[Octs & 15] = node;
|
|
if (depth == 1)
|
|
{
|
|
InitLeaf(&node->Leaf);
|
|
}
|
|
else
|
|
{
|
|
InitBranch(&node->Branch);
|
|
}
|
|
}
|
|
|
|
return(AllocateToLeaf
|
|
(pq, root->Branch.dir[Octs & 15], Octs >> 4, depth - 1));
|
|
}
|
|
|
|
/*************************************************************************/
|
|
void
|
|
PalQuantAddImage(PalQuant *pq, uint8 *img, int width, int height, int image_bpp, float weight)
|
|
{
|
|
int i, size;//, stride;
|
|
//unsigned char *pixels;
|
|
|
|
Dbg_Assert(pq);
|
|
Dbg_Assert(img);
|
|
|
|
//pixels = (unsigned char*) texture->buf;//GetTexelData( 0 );
|
|
size = width * height;
|
|
|
|
switch (image_bpp / 8)
|
|
{
|
|
case 3:
|
|
{
|
|
#if 0
|
|
Image::RGBA color;
|
|
ColorReal rColor;
|
|
OctNode *leaf;
|
|
OctantMap Octs;
|
|
|
|
color24* colors= (color24*)img;
|
|
for( i = 0; i < size; i++ )
|
|
{
|
|
color.red = colors[i].r;
|
|
color.green = colors[i].g;
|
|
color.blue = colors[i].b;
|
|
color.alpha = 255;
|
|
|
|
/* build down to leaf */
|
|
Octs = GetOctAdr(&color);
|
|
leaf = AllocateToLeaf(pq, pq->root, Octs, MAXDEPTH);
|
|
|
|
ColorRealFromColorInt(&rColor, &color);
|
|
leaf->Leaf.weight += weight;
|
|
ColorRealScale(&rColor, &rColor, weight);
|
|
ColorRealAdd(&leaf->Leaf.ac, &leaf->Leaf.ac,
|
|
&rColor);
|
|
leaf->Leaf.m2 += weight*ColorRealLengthSq(&rColor);
|
|
}
|
|
#endif
|
|
Dbg_Assert(0);
|
|
break;
|
|
}
|
|
case 4:
|
|
{
|
|
Image::RGBA color;
|
|
ColorReal rColor;
|
|
OctNode *leaf;
|
|
OctantMap Octs;
|
|
|
|
uint32* p_colors= (uint32*)img;
|
|
for( i = 0; i < size; i++ )
|
|
{
|
|
color = *((Image::RGBA *) &p_colors[i]);
|
|
|
|
/* build down to leaf */
|
|
Octs = GetOctAdr(&color);
|
|
leaf = AllocateToLeaf(pq, pq->root, Octs, MAXDEPTH);
|
|
|
|
ColorRealFromColorInt(&rColor, &color);
|
|
leaf->Leaf.weight += weight;
|
|
ColorRealScale(&rColor, &rColor, weight);
|
|
ColorRealAdd(&leaf->Leaf.ac, &leaf->Leaf.ac,
|
|
&rColor);
|
|
leaf->Leaf.m2 += weight*ColorRealLengthSq(&rColor);
|
|
}
|
|
break;
|
|
}
|
|
|
|
default:
|
|
break;
|
|
}
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
/*************************************************************************/
|
|
static void
|
|
assignindex(OctNode * root, Image::RGBA * origin, int depth, box * region,
|
|
int palIndex)
|
|
{
|
|
int width, dr, dg, db, da, dR, dG, dB, dA;
|
|
int i;
|
|
|
|
Dbg_Assert(origin);
|
|
Dbg_Assert(region);
|
|
|
|
if (!root)
|
|
return;
|
|
|
|
width = 1 << depth;
|
|
|
|
dr = origin->r - region->col1.r;
|
|
dg = origin->g - region->col1.g;
|
|
db = origin->b - region->col1.b;
|
|
da = origin->a - region->col1.a;
|
|
if (dr >= 0 || dg >= 0 || db >= 0 || da >= 0)
|
|
{
|
|
return;
|
|
}
|
|
|
|
dR = region->col0.r - origin->r;
|
|
dG = region->col0.g - origin->g;
|
|
dB = region->col0.b - origin->b;
|
|
dA = region->col0.a - origin->a;
|
|
if (dR >= width || dG >= width || dB >= width || dA >= width)
|
|
{
|
|
return;
|
|
}
|
|
|
|
/* wholly inside region and a leaf? */
|
|
if (dr <= -width && dg <= -width && db <= -width && da <= -width)
|
|
if (dR <= 0 && dG <= 0 && dB <= 0 && dA <= 0)
|
|
if (depth == 0)
|
|
{
|
|
root->Leaf.palIndex = (unsigned char) palIndex;
|
|
return;
|
|
}
|
|
|
|
/* try children */
|
|
depth--;
|
|
for (i = 0; i < 16; i++)
|
|
{
|
|
Image::RGBA suborigin;
|
|
|
|
suborigin.r = origin->r + (((i >> 3) & 1) << depth);
|
|
suborigin.g = origin->g + (((i >> 2) & 1) << depth);
|
|
suborigin.b = origin->b + (((i >> 1) & 1) << depth);
|
|
suborigin.a = origin->a + (((i >> 0) & 1) << depth);
|
|
|
|
assignindex(root->Branch.dir[i], &suborigin, depth, region, palIndex);
|
|
}
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
/* Assign palIndex to leaves */
|
|
static void
|
|
nAssign(int palIndex, OctNode * root, box * cube)
|
|
{
|
|
Image::RGBA origin;
|
|
|
|
Dbg_Assert(root);
|
|
Dbg_Assert(cube);
|
|
|
|
origin.r = 0;
|
|
origin.g = 0;
|
|
origin.b = 0;
|
|
origin.a = 0;
|
|
assignindex(root, &origin, MAXDEPTH, cube, palIndex);
|
|
}
|
|
|
|
/*************************************************************************/
|
|
static void
|
|
addvolume(OctNode * root, Image::RGBA * origin, int depth, box * region,
|
|
LeafNode * volume)
|
|
{
|
|
int width, dr, dg, db, da, dR, dG, dB, dA;
|
|
int i;
|
|
|
|
Dbg_Assert(origin);
|
|
Dbg_Assert(region);
|
|
|
|
if (!root)
|
|
return;
|
|
|
|
width = 1 << depth;
|
|
|
|
dr = origin->r - region->col1.r;
|
|
dg = origin->g - region->col1.g;
|
|
db = origin->b - region->col1.b;
|
|
da = origin->a - region->col1.a;
|
|
if (dr >= 0 || dg >= 0 || db >= 0 || da >= 0)
|
|
{
|
|
return;
|
|
}
|
|
|
|
dR = region->col0.r - origin->r;
|
|
dG = region->col0.g - origin->g;
|
|
dB = region->col0.b - origin->b;
|
|
dA = region->col0.a - origin->a;
|
|
if (dR >= width || dG >= width || dB >= width || dA >= width)
|
|
{
|
|
return;
|
|
}
|
|
|
|
/* wholly inside region? */
|
|
if (dr <= -width && dg <= -width && db <= -width && da <= -width)
|
|
if (dR <= 0 && dG <= 0 && dB <= 0 && dA <= 0)
|
|
#ifndef CACHEWEIGHTS
|
|
if (depth == 0) /* we need to visit each leaf */
|
|
#endif
|
|
{
|
|
volume->weight += root->Leaf.weight;
|
|
ColorRealAdd(&volume->ac, &volume->ac, &root->Leaf.ac);
|
|
volume->m2 += root->Leaf.m2;
|
|
return;
|
|
}
|
|
|
|
/* try children */
|
|
depth--;
|
|
for (i = 0; i < 16; i++)
|
|
{
|
|
Image::RGBA suborigin;
|
|
|
|
suborigin.r = origin->r + (((i >> 3) & 1) << depth);
|
|
suborigin.g = origin->g + (((i >> 2) & 1) << depth);
|
|
suborigin.b = origin->b + (((i >> 1) & 1) << depth);
|
|
suborigin.a = origin->a + (((i >> 0) & 1) << depth);
|
|
|
|
addvolume(root->Branch.dir[i], &suborigin, depth, region, volume);
|
|
}
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
/* Compute sum over a box of any given statistic */
|
|
static LeafNode *
|
|
nVol(LeafNode * Vol, OctNode * root, box * cube)
|
|
{
|
|
Image::RGBA origin;
|
|
|
|
Dbg_Assert(root);
|
|
Dbg_Assert(cube);
|
|
|
|
origin.r = 0;
|
|
origin.g = 0;
|
|
origin.b = 0;
|
|
origin.a = 0;
|
|
InitLeaf(Vol);
|
|
addvolume(root, &origin, MAXDEPTH, cube, Vol);
|
|
|
|
return(Vol);
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
/* Compute the weighted variance of a box */
|
|
|
|
/* NB: as with the raw statistics, this is really the variance * size */
|
|
static float
|
|
nVar(OctNode * root, box * cube)
|
|
{
|
|
LeafNode Node;
|
|
|
|
Dbg_Assert(root);
|
|
Dbg_Assert(cube);
|
|
|
|
nVol(&Node, root, cube);
|
|
|
|
return(Node.m2 - (ColorRealLengthSq(&Node.ac) / Node.weight));
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
/* We want to minimize the sum of the variances of two subboxes.
|
|
* The sum(c^2) terms can be ignored since their sum over both subboxes
|
|
* is the same (the sum for the whole box) no matter where we split.
|
|
* The remaining terms have a minus sign in the variance formula,
|
|
* so we drop the minus sign and MAXIMIZE the sum of the two terms.
|
|
*/
|
|
static float
|
|
nMaximize(OctNode * root, box * cube, int dir, int * cut,
|
|
LeafNode * whole)
|
|
{
|
|
box infcube;
|
|
LeafNode left, right;
|
|
float maxsum, val, lastval;
|
|
int i;
|
|
|
|
Dbg_Assert(root);
|
|
Dbg_Assert(cube);
|
|
Dbg_Assert(cut);
|
|
Dbg_Assert(whole);
|
|
|
|
lastval = maxsum = 0.0f;
|
|
*cut = -1;
|
|
infcube = *cube;
|
|
switch (dir)
|
|
{
|
|
case RED:
|
|
for (i = cube->col0.r; i < cube->col1.r; i++)
|
|
{
|
|
infcube.col1.r = (unsigned char) i;
|
|
|
|
nVol(&left, root, &infcube);
|
|
ColorRealSub(&right.ac, &whole->ac, &left.ac);
|
|
right.weight = whole->weight - left.weight;
|
|
if ((left.weight > 0.0f) && (right.weight > 0.0f))
|
|
{
|
|
val = ColorRealLengthSq(&left.ac) / left.weight;
|
|
val += ColorRealLengthSq(&right.ac) / right.weight;
|
|
|
|
if (val > maxsum)
|
|
{
|
|
maxsum = val;
|
|
*cut = i;
|
|
}
|
|
else if (val < lastval)
|
|
{
|
|
/* we've past the peak */
|
|
break;
|
|
}
|
|
|
|
lastval = val;
|
|
}
|
|
}
|
|
break;
|
|
|
|
case GREEN:
|
|
for (i = cube->col0.g; i < cube->col1.g; i++)
|
|
{
|
|
infcube.col1.g = (unsigned char) i;
|
|
|
|
nVol(&left, root, &infcube);
|
|
ColorRealSub(&right.ac, &whole->ac, &left.ac);
|
|
right.weight = whole->weight - left.weight;
|
|
if ((left.weight > 0.0f) && (right.weight > 0.0f))
|
|
{
|
|
val = ColorRealLengthSq(&left.ac) / left.weight;
|
|
val += ColorRealLengthSq(&right.ac) / right.weight;
|
|
|
|
if (val > maxsum)
|
|
{
|
|
maxsum = val;
|
|
*cut = i;
|
|
}
|
|
else if (val < lastval)
|
|
{
|
|
/* we've past the peak */
|
|
break;
|
|
}
|
|
|
|
lastval = val;
|
|
}
|
|
}
|
|
break;
|
|
|
|
case BLUE:
|
|
for (i = cube->col0.b; i < cube->col1.b; i++)
|
|
{
|
|
infcube.col1.b = (unsigned char) i;
|
|
|
|
nVol(&left, root, &infcube);
|
|
ColorRealSub(&right.ac, &whole->ac, &left.ac);
|
|
right.weight = whole->weight - left.weight;
|
|
if ((left.weight > 0.0f) && (right.weight > 0.0f))
|
|
{
|
|
val = ColorRealLengthSq(&left.ac) / left.weight;
|
|
val += ColorRealLengthSq(&right.ac) / right.weight;
|
|
|
|
if (val > maxsum)
|
|
{
|
|
maxsum = val;
|
|
*cut = i;
|
|
}
|
|
else if (val < lastval)
|
|
{
|
|
/* we've past the peak */
|
|
break;
|
|
}
|
|
|
|
lastval = val;
|
|
}
|
|
}
|
|
break;
|
|
|
|
case ALPHA:
|
|
for (i = cube->col0.a; i < cube->col1.a; i++)
|
|
{
|
|
infcube.col1.a = (unsigned char) i;
|
|
|
|
nVol(&left, root, &infcube);
|
|
ColorRealSub(&right.ac, &whole->ac, &left.ac);
|
|
right.weight = whole->weight - left.weight;
|
|
if ((left.weight > 0.0f) && (right.weight > 0.0f))
|
|
{
|
|
val = ColorRealLengthSq(&left.ac) / left.weight;
|
|
val += ColorRealLengthSq(&right.ac) / right.weight;
|
|
|
|
if (val > maxsum)
|
|
{
|
|
maxsum = val;
|
|
*cut = i;
|
|
}
|
|
else if (val < lastval)
|
|
{
|
|
/* we've past the peak */
|
|
break;
|
|
}
|
|
|
|
lastval = val;
|
|
}
|
|
}
|
|
break;
|
|
}
|
|
|
|
return(maxsum);
|
|
}
|
|
|
|
/*************************************************************************/
|
|
static bool
|
|
nCut(OctNode * root, box * set1, box * set2)
|
|
{
|
|
int cutr, cutg, cutb, cuta;
|
|
float maxr, maxg, maxb, maxa;
|
|
LeafNode whole;
|
|
|
|
Dbg_Assert(root);
|
|
Dbg_Assert(set1);
|
|
Dbg_Assert(set2);
|
|
|
|
nVol(&whole, root, set1);
|
|
maxr = nMaximize(root, set1, RED, &cutr, &whole);
|
|
maxg = nMaximize(root, set1, GREEN, &cutg, &whole);
|
|
maxb = nMaximize(root, set1, BLUE, &cutb, &whole);
|
|
maxa = nMaximize(root, set1, ALPHA, &cuta, &whole);
|
|
|
|
/* did we find any splits? */
|
|
if ( (maxr == 0.0f) &&
|
|
(maxg == 0.0f) &&
|
|
(maxb == 0.0f) &&
|
|
(maxa == 0.0f) )
|
|
{
|
|
return false;
|
|
}
|
|
|
|
*set2 = *set1;
|
|
|
|
/* NEED TO CHECK FOR ALPHA TOO */
|
|
|
|
if (maxr >= maxg)
|
|
{
|
|
if (maxr >= maxb)
|
|
{
|
|
if (maxr >= maxa)
|
|
{
|
|
set1->col1.r = set2->col0.r = (unsigned char) cutr;
|
|
}
|
|
else
|
|
{
|
|
set1->col1.a = set2->col0.a = (unsigned char) cuta;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (maxb >= maxa)
|
|
{
|
|
set1->col1.b = set2->col0.b = (unsigned char) cutb;
|
|
}
|
|
else
|
|
{
|
|
set1->col1.a = set2->col0.a = (unsigned char) cuta;
|
|
}
|
|
}
|
|
}
|
|
else if (maxg >= maxb)
|
|
{
|
|
if (maxg >= maxa)
|
|
{
|
|
set1->col1.g = set2->col0.g = (unsigned char) cutg;
|
|
}
|
|
else
|
|
{
|
|
set1->col1.a = set2->col0.a = (unsigned char) cuta;
|
|
}
|
|
}
|
|
else if (maxb >= maxa)
|
|
{
|
|
set1->col1.b = set2->col0.b = (unsigned char) cutb;
|
|
}
|
|
else
|
|
{
|
|
set1->col1.a = set2->col0.a = (unsigned char) cuta;
|
|
}
|
|
|
|
|
|
return true;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
#ifdef CACHEWEIGHTS
|
|
static LeafNode *
|
|
CalcNodeWeights(OctNode * root, int depth)
|
|
{
|
|
LeafNode *Leaf;
|
|
int i;
|
|
|
|
Leaf = NULL;
|
|
if (root)
|
|
{
|
|
Leaf = &root->Leaf;
|
|
|
|
/* is it a branch? */
|
|
if (depth > 0)
|
|
{
|
|
InitLeaf(Leaf);
|
|
for (i = 0; i < 16; i++)
|
|
{
|
|
LeafNode *SubNode =
|
|
CalcNodeWeights(root->Branch.dir[i], depth - 1);
|
|
|
|
if (SubNode)
|
|
{
|
|
Leaf->weight += SubNode->weight;
|
|
ColorRealAdd(&Leaf->ac, &Leaf->ac, &SubNode->ac);
|
|
Leaf->m2 += SubNode->m2;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return(Leaf);
|
|
}
|
|
#endif
|
|
|
|
/*************************************************************************/
|
|
static int
|
|
CountLeafs(OctNode * root, int depth)
|
|
{
|
|
int i, n;
|
|
|
|
n = 0;
|
|
if (root)
|
|
{
|
|
/* is it a branch? */
|
|
if (depth > 0)
|
|
{
|
|
for (i = 0; i < 16; i++)
|
|
{
|
|
n += CountLeafs(root->Branch.dir[i], depth - 1);
|
|
}
|
|
}
|
|
else
|
|
{
|
|
n = 1;
|
|
}
|
|
}
|
|
|
|
return(n);
|
|
}
|
|
|
|
/*************************************************************************/
|
|
static int
|
|
CountNodes(OctNode * root, int depth)
|
|
{
|
|
int i, n;
|
|
|
|
n = 0;
|
|
if (root)
|
|
{
|
|
n = 1;
|
|
|
|
/* is it a branch? */
|
|
if (depth > 0)
|
|
{
|
|
for (i = 0; i < 16; i++)
|
|
{
|
|
n += CountNodes(root->Branch.dir[i], depth - 1);
|
|
}
|
|
}
|
|
}
|
|
|
|
return(n);
|
|
}
|
|
|
|
/*************************************************************************/
|
|
|
|
/*
|
|
* Note the use of 255.9999f value when generating the scale variable.
|
|
* This is used instead of 255.0f to prevent rounding errors.
|
|
*/
|
|
|
|
#define node2pal(rgb, node) \
|
|
{ \
|
|
int quantize; \
|
|
float scale = ( ((node)->weight > 0) ? \
|
|
(255.9999f / (node)->weight) : \
|
|
(float) 0 ); \
|
|
\
|
|
quantize = (int) ((node)->ac.red * scale); \
|
|
(rgb)->r = (unsigned char) quantize; \
|
|
quantize = (int) ((node)->ac.green * scale); \
|
|
(rgb)->g = (unsigned char) quantize; \
|
|
quantize = (int) ((node)->ac.blue * scale); \
|
|
(rgb)->b = (unsigned char) quantize; \
|
|
quantize = (int) ((node)->ac.alpha * scale); \
|
|
(rgb)->a = (unsigned char) quantize; \
|
|
} \
|
|
|
|
/*************************************************************************/
|
|
int
|
|
PalQuantResolvePalette(Image::RGBA * palette, int maxcols, PalQuant * pq)
|
|
{
|
|
int numcols, uniquecols, i, k, next;
|
|
|
|
#if (defined(RWDEBUG))
|
|
if (256 < maxcols)
|
|
{
|
|
RWMESSAGE(("256 < %d == maxcols", (int) maxcols));
|
|
}
|
|
#endif /* (defined(RWDEBUG)) */
|
|
|
|
|
|
Dbg_Assert(palette);
|
|
Dbg_Assert(maxcols <= 256);
|
|
Dbg_Assert(pq);
|
|
|
|
numcols = maxcols;
|
|
uniquecols = CountLeafs(pq->root, MAXDEPTH);
|
|
if (numcols > uniquecols)
|
|
{
|
|
numcols = uniquecols;
|
|
}
|
|
|
|
#ifdef CACHEWEIGHTS
|
|
/* cache weightings at every node */
|
|
CalcNodeWeights(pq->root, MAXDEPTH);
|
|
#endif
|
|
|
|
/* divide and conquer */
|
|
pq->Mcube[0].col0.r = 0;
|
|
pq->Mcube[0].col0.g = 0;
|
|
pq->Mcube[0].col0.b = 0;
|
|
pq->Mcube[0].col0.a = 0;
|
|
pq->Mcube[0].col1.r = 1 << MAXDEPTH;
|
|
pq->Mcube[0].col1.g = 1 << MAXDEPTH;
|
|
pq->Mcube[0].col1.b = 1 << MAXDEPTH;
|
|
pq->Mcube[0].col1.a = 1 << MAXDEPTH;
|
|
pq->Mvv[0] = nVar(pq->root, &pq->Mcube[0]);
|
|
for (i = 1; i < numcols; i++)
|
|
{
|
|
float maxvar;
|
|
|
|
/* find best box to split */
|
|
next = -1;
|
|
maxvar = 0.0f;
|
|
for (k = 0; k < i; k++)
|
|
{
|
|
if (pq->Mvv[k] > maxvar)
|
|
{
|
|
maxvar = pq->Mvv[k];
|
|
next = k;
|
|
}
|
|
}
|
|
|
|
/* stop if we couldn't find a box to split */
|
|
if (next == -1)
|
|
{
|
|
break;
|
|
}
|
|
|
|
/* split box */
|
|
if (nCut(pq->root, &pq->Mcube[next], &pq->Mcube[i]))
|
|
{
|
|
/* volume test ensures we won't try to cut one-cell box */
|
|
pq->Mvv[next] = nVar(pq->root, &pq->Mcube[next]);
|
|
pq->Mvv[i] = nVar(pq->root, &pq->Mcube[i]);
|
|
}
|
|
else
|
|
{
|
|
/* don't try to split this box again */
|
|
pq->Mvv[next] = 0.0f;
|
|
i--;
|
|
}
|
|
}
|
|
|
|
/* extract the new palette */
|
|
for (k = 0; k < maxcols; k++)
|
|
{
|
|
if (k < numcols)
|
|
{
|
|
LeafNode Node;
|
|
|
|
nAssign(k, pq->root, &pq->Mcube[k]);
|
|
nVol(&Node, pq->root, &pq->Mcube[k]);
|
|
node2pal(&palette[k], &Node);
|
|
}
|
|
else
|
|
{
|
|
palette[k].r = 0;
|
|
palette[k].g = 0;
|
|
palette[k].b = 0;
|
|
palette[k].a = 0;
|
|
}
|
|
}
|
|
|
|
return(numcols);
|
|
}
|
|
|
|
#if 0
|
|
/*************************************************************************/
|
|
static unsigned char
|
|
GetIndex(OctNode * root, OctantMap Octs, int depth)
|
|
{
|
|
unsigned char result;
|
|
|
|
Dbg_Assert(root);
|
|
|
|
if (depth == 0)
|
|
{
|
|
result = root->Leaf.palIndex;
|
|
}
|
|
else
|
|
{
|
|
result = GetIndex(root->Branch.dir[Octs & 15], Octs >> 4, depth - 1);
|
|
}
|
|
|
|
return(result);
|
|
}
|
|
#endif
|
|
|
|
/*************************************************************************/
|
|
bool
|
|
PalQuantInit(PalQuant * pq)
|
|
{
|
|
int i, j, maxval;
|
|
|
|
Dbg_Assert(pq);
|
|
Dbg_Assert(!p_splice);
|
|
|
|
p_splice = (OctantMap *) Mem::Malloc(sizeof(OctantMap) * MAXCOLOR);
|
|
|
|
/* lookup mapping (8) bit-patterns to every 4th bit b31->b00 (least to most) */
|
|
maxval = 1 << MAXDEPTH;
|
|
for (i = 0; i < maxval; i++)
|
|
{
|
|
OctantMap mask = 0;
|
|
|
|
for (j = 0; j < MAXDEPTH; j++)
|
|
{
|
|
mask |= (i & (1 << j)) ? (1 << ((MAXDEPTH - 1 - j) * 4)) : 0;
|
|
}
|
|
p_splice[i] = mask;
|
|
}
|
|
|
|
pq->Mcube = (box *) Mem::Calloc(sizeof(box), MAXCOLOR);
|
|
pq->Mvv = (float *) Mem::Calloc(sizeof(float), MAXCOLOR);
|
|
|
|
pq->root = CreateCube();
|
|
InitBranch(&pq->root->Branch);
|
|
|
|
return true;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
static void
|
|
DeleteOctTree(PalQuant * pq, OctNode * root, int depth)
|
|
{
|
|
int i;
|
|
|
|
Dbg_Assert(pq);
|
|
|
|
if (root)
|
|
{
|
|
/* is it a branch? */
|
|
if (depth > 0)
|
|
{
|
|
for (i = 0; i < 16; i++)
|
|
{
|
|
DeleteOctTree(pq, root->Branch.dir[i], depth - 1);
|
|
}
|
|
}
|
|
|
|
Mem::Free(root);
|
|
}
|
|
}
|
|
|
|
/*************************************************************************/
|
|
void
|
|
PalQuantTerm(PalQuant * pq)
|
|
{
|
|
|
|
Dbg_Assert(pq);
|
|
Dbg_Assert(p_splice);
|
|
|
|
|
|
DeleteOctTree(pq, pq->root, MAXDEPTH);
|
|
pq->root = (OctNode *)NULL;
|
|
|
|
Mem::Free( pq->Mvv );
|
|
Mem::Free( pq->Mcube );
|
|
Mem::Free( p_splice );
|
|
p_splice = NULL;
|
|
}
|
|
|
|
/*************************************************************************/
|
|
void GeneratePalette( Image::RGBA *p_palette, uint8* src_image, int width, int height, int image_bpp, int max_colors )
|
|
{
|
|
int num_colors;
|
|
PalQuant pal_quant;
|
|
|
|
Mem::Manager::sHandle().PushContext(Mem::Manager::sHandle().TopDownHeap());
|
|
|
|
if( !PalQuantInit( &pal_quant ))
|
|
{
|
|
return;
|
|
}
|
|
|
|
PalQuantAddImage( &pal_quant, src_image, width, height, image_bpp, 1 );
|
|
|
|
// Create a palette for all of the mips
|
|
num_colors = PalQuantResolvePalette( p_palette, max_colors, &pal_quant );
|
|
|
|
// And swizzle for the PS2
|
|
Image::RGBA temp_rgba;
|
|
for (int j=0; j<256; j+=32)
|
|
{
|
|
for (int k=0; k<8; k++)
|
|
{
|
|
temp_rgba = p_palette[j+k+8];
|
|
p_palette[j+k+8] = p_palette[j+k+16];
|
|
p_palette[j+k+16] = temp_rgba;
|
|
}
|
|
}
|
|
|
|
|
|
PalQuantTerm( &pal_quant );
|
|
|
|
Mem::Manager::sHandle().PopContext();
|
|
}
|
|
|
|
|
|
} // Namespace Nx
|
|
|