source/gdi/octree.cxx

/**************************************************************
 *
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 *
 *************************************************************/


// MARKER(update_precomp.py): autogen include statement, do not remove
#include "precompiled_vcl.hxx"

#include <limits.h>

#include <vcl/bmpacc.hxx>
#include <vcl/octree.hxx>

#include <impoct.hxx>

// ---------
// - pMask -
// ---------

static sal_uInt8 pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };

// -------------
// - NodeCache -
// -------------

ImpNodeCache::ImpNodeCache( const sal_uLong nInitSize ) :
            pActNode( NULL )
{
    const sal_uLong nSize = nInitSize + 4;

    for( sal_uLong i = 0; i < nSize; i++ )
    {
        OctreeNode* pNewNode = new NODE;

        pNewNode->pNextInCache = pActNode;
        pActNode = pNewNode;
    }
}

// ------------------------------------------------------------------------

ImpNodeCache::~ImpNodeCache()
{
    while( pActNode )
    {
        OctreeNode* pNode = pActNode;

        pActNode = pNode->pNextInCache;
        delete pNode;
    }
}

// ----------
// - Octree -
// ----------

Octree::Octree( sal_uLong nColors ) :
            nMax        ( nColors ),
            nLeafCount  ( 0L ),
            pTree       ( NULL ),
            pAcc        ( NULL )
{
    pNodeCache = new ImpNodeCache( nColors );
    memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) );
}

// ------------------------------------------------------------------------

Octree::Octree( const BitmapReadAccess& rReadAcc, sal_uLong nColors ) :
            nMax        ( nColors ),
            nLeafCount  ( 0L ),
            pTree       ( NULL ),
            pAcc        ( &rReadAcc )
{
    pNodeCache = new ImpNodeCache( nColors );
    memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) );
    ImplCreateOctree();
}

// ------------------------------------------------------------------------

Octree::~Octree()
{
    ImplDeleteOctree( &pTree );
    delete pNodeCache;
}

// ------------------------------------------------------------------------

void Octree::AddColor( const BitmapColor& rColor )
{
    pColor = &(BitmapColor&) rColor;
    nLevel = 0L;
    ImplAdd( &pTree );

    while( nLeafCount > nMax )
        ImplReduce();
}

// ------------------------------------------------------------------------

void Octree::ImplCreateOctree()
{
    if( !!*pAcc )
    {
        const long      nWidth = pAcc->Width();
        const long      nHeight = pAcc->Height();

        if( pAcc->HasPalette() )
        {
            for( long nY = 0; nY < nHeight; nY++ )
            {
                for( long nX = 0; nX < nWidth; nX++ )
                {
                    pColor = &(BitmapColor&) pAcc->GetPaletteColor( pAcc->GetPixel( nY, nX ) );
                    nLevel = 0L;
                    ImplAdd( &pTree );

                    while( nLeafCount > nMax )
                        ImplReduce();
                }
            }
        }
        else
        {
            BitmapColor aColor;

            pColor = &aColor;

            for( long nY = 0; nY < nHeight; nY++ )
            {
                for( long nX = 0; nX < nWidth; nX++ )
                {
                    aColor = pAcc->GetPixel( nY, nX );
                    nLevel = 0L;
                    ImplAdd( &pTree );

                    while( nLeafCount > nMax )
                        ImplReduce();
                }
            }
        }
    }
}

// ------------------------------------------------------------------------

void Octree::ImplDeleteOctree( PPNODE ppNode )
{
    for ( sal_uLong i = 0UL; i < 8UL; i++ )
    {
        if ( (*ppNode)->pChild[ i ] )
            ImplDeleteOctree( &(*ppNode)->pChild[ i ] );
    }

    pNodeCache->ImplReleaseNode( *ppNode );
    *ppNode = NULL;
}

// ------------------------------------------------------------------------

void Octree::ImplAdd( PPNODE ppNode )
{
    // ggf. neuen Knoten erzeugen
    if( !*ppNode )
    {
        *ppNode = pNodeCache->ImplGetFreeNode();
        (*ppNode)->bLeaf = ( OCTREE_BITS == nLevel );

        if( (*ppNode)->bLeaf )
            nLeafCount++;
        else
        {
            (*ppNode)->pNext = pReduce[ nLevel ];
            pReduce[ nLevel ] = *ppNode;
        }
    }

    if( (*ppNode)->bLeaf )
    {
        (*ppNode)->nCount++;
        (*ppNode)->nRed += pColor->GetRed();
        (*ppNode)->nGreen += pColor->GetGreen();
        (*ppNode)->nBlue += pColor->GetBlue();
    }
    else
    {
        const sal_uLong nShift = 7 - nLevel;
        const sal_uInt8  cMask = pImplMask[ nLevel ];
        const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
                             ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
                             ( ( pColor->GetBlue() & cMask ) >> nShift );

        nLevel++;
        ImplAdd( &(*ppNode)->pChild[ nIndex ] );
    }
}

// ------------------------------------------------------------------------

void Octree::ImplReduce()
{
    sal_uLong   i;
    PNODE   pNode;
    sal_uLong   nRedSum = 0L;
    sal_uLong   nGreenSum = 0L;
    sal_uLong   nBlueSum = 0L;
    sal_uLong   nChilds = 0L;

    for ( i = OCTREE_BITS - 1; i && !pReduce[i]; i-- ) {}

    pNode = pReduce[ i ];
    pReduce[ i ] = pNode->pNext;

    for ( i = 0; i < 8; i++ )
    {
        if ( pNode->pChild[ i ] )
        {
            PNODE pChild = pNode->pChild[ i ];

            nRedSum += pChild->nRed;
            nGreenSum += pChild->nGreen;
            nBlueSum += pChild->nBlue;
            pNode->nCount += pChild->nCount;

            pNodeCache->ImplReleaseNode( pNode->pChild[ i ] );
            pNode->pChild[ i ] = NULL;
            nChilds++;
        }
    }

    pNode->bLeaf = sal_True;
    pNode->nRed = nRedSum;
    pNode->nGreen = nGreenSum;
    pNode->nBlue = nBlueSum;
    nLeafCount -= --nChilds;
}

// ------------------------------------------------------------------------

void Octree::CreatePalette( PNODE pNode )
{
    if( pNode->bLeaf )
    {
        pNode->nPalIndex = nPalIndex;
        aPal[ nPalIndex++ ] = BitmapColor( (sal_uInt8) ( (double) pNode->nRed / pNode->nCount ),
                                           (sal_uInt8) ( (double) pNode->nGreen / pNode->nCount ),
                                           (sal_uInt8) ( (double) pNode->nBlue / pNode->nCount ) );
    }
    else for( sal_uLong i = 0UL; i < 8UL; i++ )
        if( pNode->pChild[ i ] )
            CreatePalette( pNode->pChild[ i ] );

}

// ------------------------------------------------------------------------

void Octree::GetPalIndex( PNODE pNode )
{
    if ( pNode->bLeaf )
        nPalIndex = pNode->nPalIndex;
    else
    {
        const sal_uLong nShift = 7 - nLevel;
        const sal_uInt8  cMask = pImplMask[ nLevel++ ];
        const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
                             ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
                             ( ( pColor->GetBlue() & cMask ) >> nShift );

        GetPalIndex( pNode->pChild[ nIndex ] );
    }
}

// -------------------
// - InverseColorMap -
// -------------------

InverseColorMap::InverseColorMap( const BitmapPalette& rPal ) :
            nBits( 8 - OCTREE_BITS )
{
    sal_uLong*			cdp;
    sal_uInt8*           crgbp;
    const sal_uLong     nColorMax = 1 << OCTREE_BITS;
    const sal_uLong     xsqr = 1 << ( nBits << 1 );
    const sal_uLong     xsqr2 = xsqr << 1;
    const sal_uLong     nColors = rPal.GetEntryCount();
    const long      x = 1L << nBits;
    const long      x2 = x >> 1L;
    sal_uLong           r, g, b;
    long            rxx, gxx, bxx;
    long            rdist, gdist, bdist;
    long            crinc, cginc, cbinc;

    ImplCreateBuffers( nColorMax );

    for( sal_uLong nIndex = 0; nIndex < nColors; nIndex++ )
    {
        const BitmapColor&  rColor = rPal[ (sal_uInt16) nIndex ];
        const sal_uInt8			cRed = rColor.GetRed();
        const sal_uInt8			cGreen = rColor.GetGreen();
        const sal_uInt8			cBlue = rColor.GetBlue();

        rdist = cRed - x2;
        gdist = cGreen - x2;
        bdist = cBlue - x2;
        rdist = rdist*rdist + gdist*gdist + bdist*bdist;

        crinc = ( xsqr - ( cRed << nBits ) ) << 1L;
        cginc = ( xsqr - ( cGreen << nBits ) ) << 1L;
        cbinc = ( xsqr - ( cBlue << nBits ) ) << 1L;

        cdp = (sal_uLong*) pBuffer;
        crgbp = pMap;

        for( r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2 )
        {
            for( g = 0, gdist = rdist, gxx = cginc; g < nColorMax;  gdist += gxx, g++, gxx += xsqr2 )
            {
                for( b = 0, bdist = gdist, bxx = cbinc; b < nColorMax; bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2 )
                    if ( !nIndex || ( (long) *cdp ) > bdist )
                    {
                        *cdp = bdist;
                        *crgbp = (sal_uInt8) nIndex;
                    }
            }
        }
    }
}

// ------------------------------------------------------------------------

InverseColorMap::~InverseColorMap()
{
    rtl_freeMemory( pBuffer );
    rtl_freeMemory( pMap );
}

// ------------------------------------------------------------------------

void InverseColorMap::ImplCreateBuffers( const sal_uLong nMax )
{
    const sal_uLong nCount = nMax * nMax * nMax;
    const sal_uLong nSize = nCount * sizeof( sal_uLong );

    pMap = (sal_uInt8*) rtl_allocateMemory( nCount );
    memset( pMap, 0x00, nCount );

    pBuffer = (sal_uInt8*) rtl_allocateMemory( nSize );
    memset( pBuffer, 0xff, nSize );
}