//16bit（565）轉成256色圖像。
//作者：吳夢華 csdn上叫神曲（serenade)
//wondertop@263.net
//2003-3-13
//用法：
//OctreeQuantize quantize;
//quantize( pwImgBuf, width, height, pitch );// 要求pitch是偶數，pitch不用我解釋了吧
//quantize中的m_pPal和m_pbyIndexedImg就分別指向256色調色板（565格式）和8位的索引圖像。
//釋放這兩個內存是你自己的工作。
//
//效果還可以，也夠快，300×200的圖像需要60ms。



#include "stdafx.h"
#include "Quantize.h"

OctreeQuantize::OctreeQuantize()
{
	m_pOctantRoot	= new SOctant;
	m_pPal			= NULL;
	m_pbyIndexedImg = NULL;
	m_iPalIndex		= 0;
	m_iNumColors	= 0;
}
OctreeQuantize::~OctreeQuantize()
{
	delete m_pOctantRoot;
}

// the pitch is presupposed to be even.
void OctreeQuantize::BuildOctree(WORD *pwImgBuf, int width, int height, int pitch)
{
	int index = 0;
	for( int row=0; row<height; row++ )
	{
		for( int col=0; col<width; col++ )
		{
			int red = pwImgBuf[index] >> 11;
			int green = (pwImgBuf[index] & 0x7e0 )>>6;
			int blue = pwImgBuf[index] & 0x1f;
			index ++;

			SOctant *pOctant = m_pOctantRoot;
			for( int i=0; i<5; i++ ) 
			{
				int indexChildren = ( ((red>>(4-i))&1) <<2 ) | 
									( ((green>>(4-i))&1) <<1 ) | 
									((blue>>(4-i))&1);
				
				if( !pOctant->m_pChildren[indexChildren] )
				{
					SOctant *pChild = new SOctant;
					pOctant->m_pChildren[indexChildren] = pChild;
					pChild->m_pParent = pOctant;
				}
				
				pOctant = pOctant->m_pChildren[indexChildren];

			}

			if( !pOctant->m_iRefCount ) m_iNumColors++;
			
			pOctant->m_iRefCount++;
			pOctant->m_iRed += red;
			pOctant->m_iGreen += green;
			pOctant->m_iBlue += blue;
		}
		index += (pitch>>1)-width;
	}
}

int cmp( const void *pEle1, const void *pEle2 )
{
	if( (*(SOctant**)pEle1)->m_iRefCount < (*(SOctant**)pEle2)->m_iRefCount )
		return 1;
	if( (*(SOctant**)pEle1)->m_iRefCount == (*(SOctant**)pEle2)->m_iRefCount )
		return 0;
	else return -1;
}

void OctreeQuantize::ReduceTo256()
{
	if( m_iNumColors < 256 ) return;

	BuildRev2ndLevelVector(m_pOctantRoot);
	// make it in descending order.
	qsort( &m_vRev2ndLevelOctants[0], m_vRev2ndLevelOctants.size(),
			sizeof( SOctant*), cmp );
	
	while( true )
	{
		SOctant *pOctant = m_vRev2ndLevelOctants.back();
		for( int i=0; i<8; i++ )
		{
			if( pOctant->m_pChildren[i] )
			{
				m_iNumColors --;
				SAFE_DELETE( pOctant->m_pChildren[i] );			
			}
		}
		
		m_iNumColors ++;
		if( m_iNumColors < 256 ) break;

		m_vRev2ndLevelOctants.pop_back();

		if( pOctant->m_pParent->IsRev2ndLevel() ) 
		{
			SOctant *pParent = pOctant->m_pParent;
			for( int i=m_vRev2ndLevelOctants.size()-1; i>=0; i--)
				if( m_vRev2ndLevelOctants[i]->m_iRefCount >= pParent->m_iRefCount )
				{
					pParent->SumChildren();
					m_vRev2ndLevelOctants.insert( 
						m_vRev2ndLevelOctants.begin()+i+1, pParent );
					break;
				}
		}
	}
}

// build the internal vector( recording reverse 2nd-level octant )
void OctreeQuantize::BuildRev2ndLevelVector(SOctant *pOctant)
{
	if( pOctant->IsRev2ndLevel() )
	{
		pOctant->SumChildren();
		m_vRev2ndLevelOctants.push_back( pOctant );
	}
	else
		for( int i=0; i<8; i++ )
			if( pOctant->m_pChildren[i] )
				BuildRev2ndLevelVector( pOctant->m_pChildren[i] );
}

void OctreeQuantize::BuildPal()
{
	m_pPal = new WORD[256];
	memset( m_pPal, 0, 512 );
	m_iPalIndex = 0;
	BuildPalIt( m_pOctantRoot );
}

void OctreeQuantize::BuildPalIt( SOctant *pOctant )
{
	if( pOctant->IsLeaf() ) 
	{
		pOctant->m_iRed /= pOctant->m_iRefCount;
		pOctant->m_iGreen /= pOctant->m_iRefCount;
		pOctant->m_iBlue /= pOctant->m_iRefCount;
		m_pPal[m_iPalIndex] = ( pOctant->m_iRed << 11 ) |
							  ( pOctant->m_iGreen << 6 ) |
							  ( pOctant->m_iBlue );
		
		pOctant->m_iPalIndex = m_iPalIndex;

		m_iPalIndex ++;
	}
	else
	{		
		for( int i=0; i<8; i++ )
		{
			if( pOctant->m_pChildren[i] )
				BuildPalIt( pOctant->m_pChildren[i] );
		}
	}
}

void OctreeQuantize::MapImgTo256(WORD *pwImgBuf, int width, int height, int pitch)
{
	m_pbyIndexedImg = new BYTE[ width*height ];
	int indexSrc=0;
	int indexDst=0;
	for( int row=0; row<height; row++ )
	{
		for( int col=0; col<width; col++ )
		{
			int red = pwImgBuf[indexSrc] >> 11;
			int green = (pwImgBuf[indexSrc] & 0x7e0 )>>6;
			int blue = pwImgBuf[indexSrc] & 0x1f;
			indexSrc ++;

			SOctant *pOctant = m_pOctantRoot;
			for( int i=0; i<5; i++ ) 
			{
				int indexChild = ( ((red>>(4-i))&1) <<2 ) | 
								 ( ((green>>(4-i))&1) <<1 ) | 
								 ( (blue>>(4-i))&1);

				pOctant = pOctant->m_pChildren[indexChild];

				if( pOctant->IsLeaf() )
				{
					m_pbyIndexedImg[indexDst++] = pOctant->m_iPalIndex;
					break;
				}
			}			
		}
		indexSrc += (pitch>>1)-width;
	}
}

BOOL SOctant::IsRev2ndLevel()
{
	BOOL bHasChild = false;
	for( int i=0; i<8; i++ )
	{
		if( m_pChildren[i] )
		{
			bHasChild = true;
			if( !m_pChildren[i]->IsLeaf() ) return false;
		}
	}

	if( bHasChild ) return true;
	else return false;
}

void OctreeQuantize::Chg16bitTo256(WORD *pwImgBuf, int width, int height, int pitch)
{
	BuildOctree( pwImgBuf, width, height, pitch );
	ReduceTo256();
	BuildPal();
	MapImgTo256( pwImgBuf, width, height, pitch );
}