byte level;

bool isLeaf;

uint32 numPixels;

uint32 sumRed;

uint32 sumGreen;

uint32 sumBlue;

OctreeNode *child[8];

OctreeNode *nextNode;

uint _leafLevel = kOctreeDepth - 1;

OctreeNode *_root = nullptr;

uint _numLeaves = 0;

uint _maxLeaves = 0;

OctreeNode *_reduceList[kOctreeDepth - 1];

Common::Stack<OctreeNode *> _nodePool;

OctreeNode *allocateNode(byte level) {

OctreeNode *node;

if (!_nodePool.empty())

node = _nodePool.pop();

else

node = new OctreeNode();

if (level == _leafLevel) {

node->isLeaf = true;

_numLeaves++;

} else

node->isLeaf = false;

node->level = level;

node->numPixels = 0;

node->sumRed = 0;

node->sumGreen = 0;

node->sumBlue = 0;

node->nextNode = nullptr;

for (int i = 0; i < 8; i++)

node->child[i] = nullptr;

return node;

}

void releaseNode(OctreeNode *node) {

_nodePool.push(node);

}

void deleteNodeRecursively(OctreeNode *node) {

if (!node)

return;

for (int i = 0; i < 8; i++)

deleteNodeRecursively(node->child[i]);

delete node;

}

void insert(OctreeNode **node, byte r, byte g, byte b, uint level) {

if (*node == nullptr) {

*node = allocateNode(level);

if (level != _leafLevel) {

assert(level < kOctreeDepth - 1);

(*node)->nextNode = _reduceList[level];

_reduceList[level] = *node;

}

}

// Once we encounter a leaf, add the color there. This is not

// necessarily at the bottom of the tree, so I guess it would

// not be out of the question to transform the leaf into a

// regular node. But I saw no mention of this in the article.

if ((*node)->isLeaf) {

(*node)->numPixels++;

(*node)->sumRed += r;

(*node)->sumGreen += g;

(*node)->sumBlue += b;

} else {

byte bit = (0x80 >> level);

byte rbit = (r & bit) >> (5 - level);

byte gbit = (g & bit) >> (6 - level);

byte bbit = (b & bit) >> (7 - level);

int idx = rbit | gbit | bbit;

insert(&((*node)->child[idx]), r, g, b, level + 1);

}

// Usually one reduction would be enough, but it's possible

// that the reduction will not actually remove any leaves.

while (_numLeaves > _maxLeaves)

reduceTree();

}

void reduceTree() {

// In the original article, once a reduce list has been emptied

// the leaf level was decreased, meaning that the tree could

// never again grow beyond that height. I don't understand why,

// so I have made this a local variable instead.

int level = _leafLevel - 1;

while (!_reduceList[level])

level--;

// There are several possible approaches to picking the node to

// reduce. Picking the one with the largest number of pixels

// may leave more color for fine details. Picking the one with

// the smallest number may sacrifice detail, but preserve subtle

// gradations in large areas. This just picks the first one,

// i.e. the most recently inserted one, so it's pretty random

// which may be good on average.

//

// Once a subtree has been pruned, it will no longer grow back.

// It seems to me it should be possible to allow it to, but the

// article doesn't mention it. On the contrary, it states that

// "any new colors whose path through the tree take them

// through [a node that was turned into a leaf] now stop here".

OctreeNode *node = _reduceList[level];

_reduceList[level] = _reduceList[level]->nextNode;

// Combine all the leaves into their parent, and make the

// parent a leaf.

uint32 sumRed = 0;

uint32 sumGreen = 0;

uint32 sumBlue = 0;

byte numChildren = 0;

for (int i = 0; i < 8; i++) {

OctreeNode *child = node->child[i];

if (child) {

numChildren++;

sumRed += child->sumRed;

sumGreen += child->sumGreen;

sumBlue += child->sumBlue;

node->numPixels += child->numPixels;

releaseNode(child);

node->child[i] = nullptr;

}

}

node->isLeaf = true;

node->sumRed = sumRed;

node->sumGreen = sumGreen;

node->sumBlue = sumBlue;

_numLeaves -= (numChildren - 1);

}

Palette *_palette;

uint _colorIndex;

void getPalette(OctreeNode *node) {

if (node->isLeaf) {

byte r = node->sumRed / node->numPixels;

byte g = node->sumGreen / node->numPixels;

byte b = node->sumBlue / node->numPixels;

_palette->set(_colorIndex, r, g, b);

_colorIndex++;

} else {

for (uint i = 0; i < 8; i++) {

if (node->child[i])

getPalette(node->child[i]);

}

}

}

Octree(int maxLeaves) : _maxLeaves(maxLeaves) {

for (uint i = 0; i < kOctreeDepth - 1; i++)

_reduceList[i] = nullptr;

}

~Octree() {

while (!_nodePool.empty())

delete _nodePool.pop();

deleteNodeRecursively(_root);

}

void insert(byte r, byte g, byte b) {

insert(&_root, r, g, b, 0);

}

Palette *getPalette() {

_palette = new Graphics::Palette(_maxLeaves);

_colorIndex = 0;

getPalette(_root);

return _palette;

}