/************************************************************** * * 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 #include #include #include // --------- // - 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->GetPixelIndex( 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 ); }