1*cdf0e10cSrcweir /************************************************************************* 2*cdf0e10cSrcweir * 3*cdf0e10cSrcweir * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4*cdf0e10cSrcweir * 5*cdf0e10cSrcweir * Copyright 2000, 2010 Oracle and/or its affiliates. 6*cdf0e10cSrcweir * 7*cdf0e10cSrcweir * OpenOffice.org - a multi-platform office productivity suite 8*cdf0e10cSrcweir * 9*cdf0e10cSrcweir * This file is part of OpenOffice.org. 10*cdf0e10cSrcweir * 11*cdf0e10cSrcweir * OpenOffice.org is free software: you can redistribute it and/or modify 12*cdf0e10cSrcweir * it under the terms of the GNU Lesser General Public License version 3 13*cdf0e10cSrcweir * only, as published by the Free Software Foundation. 14*cdf0e10cSrcweir * 15*cdf0e10cSrcweir * OpenOffice.org is distributed in the hope that it will be useful, 16*cdf0e10cSrcweir * but WITHOUT ANY WARRANTY; without even the implied warranty of 17*cdf0e10cSrcweir * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18*cdf0e10cSrcweir * GNU Lesser General Public License version 3 for more details 19*cdf0e10cSrcweir * (a copy is included in the LICENSE file that accompanied this code). 20*cdf0e10cSrcweir * 21*cdf0e10cSrcweir * You should have received a copy of the GNU Lesser General Public License 22*cdf0e10cSrcweir * version 3 along with OpenOffice.org. If not, see 23*cdf0e10cSrcweir * <http://www.openoffice.org/license.html> 24*cdf0e10cSrcweir * for a copy of the LGPLv3 License. 25*cdf0e10cSrcweir * 26*cdf0e10cSrcweir ************************************************************************/ 27*cdf0e10cSrcweir 28*cdf0e10cSrcweir // MARKER(update_precomp.py): autogen include statement, do not remove 29*cdf0e10cSrcweir #include "precompiled_vcl.hxx" 30*cdf0e10cSrcweir 31*cdf0e10cSrcweir #include <limits.h> 32*cdf0e10cSrcweir 33*cdf0e10cSrcweir #include <vcl/bmpacc.hxx> 34*cdf0e10cSrcweir #include <vcl/octree.hxx> 35*cdf0e10cSrcweir 36*cdf0e10cSrcweir #include <impoct.hxx> 37*cdf0e10cSrcweir 38*cdf0e10cSrcweir // --------- 39*cdf0e10cSrcweir // - pMask - 40*cdf0e10cSrcweir // --------- 41*cdf0e10cSrcweir 42*cdf0e10cSrcweir static sal_uInt8 pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 }; 43*cdf0e10cSrcweir 44*cdf0e10cSrcweir // ------------- 45*cdf0e10cSrcweir // - NodeCache - 46*cdf0e10cSrcweir // ------------- 47*cdf0e10cSrcweir 48*cdf0e10cSrcweir ImpNodeCache::ImpNodeCache( const sal_uLong nInitSize ) : 49*cdf0e10cSrcweir pActNode( NULL ) 50*cdf0e10cSrcweir { 51*cdf0e10cSrcweir const sal_uLong nSize = nInitSize + 4; 52*cdf0e10cSrcweir 53*cdf0e10cSrcweir for( sal_uLong i = 0; i < nSize; i++ ) 54*cdf0e10cSrcweir { 55*cdf0e10cSrcweir OctreeNode* pNewNode = new NODE; 56*cdf0e10cSrcweir 57*cdf0e10cSrcweir pNewNode->pNextInCache = pActNode; 58*cdf0e10cSrcweir pActNode = pNewNode; 59*cdf0e10cSrcweir } 60*cdf0e10cSrcweir } 61*cdf0e10cSrcweir 62*cdf0e10cSrcweir // ------------------------------------------------------------------------ 63*cdf0e10cSrcweir 64*cdf0e10cSrcweir ImpNodeCache::~ImpNodeCache() 65*cdf0e10cSrcweir { 66*cdf0e10cSrcweir while( pActNode ) 67*cdf0e10cSrcweir { 68*cdf0e10cSrcweir OctreeNode* pNode = pActNode; 69*cdf0e10cSrcweir 70*cdf0e10cSrcweir pActNode = pNode->pNextInCache; 71*cdf0e10cSrcweir delete pNode; 72*cdf0e10cSrcweir } 73*cdf0e10cSrcweir } 74*cdf0e10cSrcweir 75*cdf0e10cSrcweir // ---------- 76*cdf0e10cSrcweir // - Octree - 77*cdf0e10cSrcweir // ---------- 78*cdf0e10cSrcweir 79*cdf0e10cSrcweir Octree::Octree( sal_uLong nColors ) : 80*cdf0e10cSrcweir nMax ( nColors ), 81*cdf0e10cSrcweir nLeafCount ( 0L ), 82*cdf0e10cSrcweir pTree ( NULL ), 83*cdf0e10cSrcweir pAcc ( NULL ) 84*cdf0e10cSrcweir { 85*cdf0e10cSrcweir pNodeCache = new ImpNodeCache( nColors ); 86*cdf0e10cSrcweir memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) ); 87*cdf0e10cSrcweir } 88*cdf0e10cSrcweir 89*cdf0e10cSrcweir // ------------------------------------------------------------------------ 90*cdf0e10cSrcweir 91*cdf0e10cSrcweir Octree::Octree( const BitmapReadAccess& rReadAcc, sal_uLong nColors ) : 92*cdf0e10cSrcweir nMax ( nColors ), 93*cdf0e10cSrcweir nLeafCount ( 0L ), 94*cdf0e10cSrcweir pTree ( NULL ), 95*cdf0e10cSrcweir pAcc ( &rReadAcc ) 96*cdf0e10cSrcweir { 97*cdf0e10cSrcweir pNodeCache = new ImpNodeCache( nColors ); 98*cdf0e10cSrcweir memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) ); 99*cdf0e10cSrcweir ImplCreateOctree(); 100*cdf0e10cSrcweir } 101*cdf0e10cSrcweir 102*cdf0e10cSrcweir // ------------------------------------------------------------------------ 103*cdf0e10cSrcweir 104*cdf0e10cSrcweir Octree::~Octree() 105*cdf0e10cSrcweir { 106*cdf0e10cSrcweir ImplDeleteOctree( &pTree ); 107*cdf0e10cSrcweir delete pNodeCache; 108*cdf0e10cSrcweir } 109*cdf0e10cSrcweir 110*cdf0e10cSrcweir // ------------------------------------------------------------------------ 111*cdf0e10cSrcweir 112*cdf0e10cSrcweir void Octree::AddColor( const BitmapColor& rColor ) 113*cdf0e10cSrcweir { 114*cdf0e10cSrcweir pColor = &(BitmapColor&) rColor; 115*cdf0e10cSrcweir nLevel = 0L; 116*cdf0e10cSrcweir ImplAdd( &pTree ); 117*cdf0e10cSrcweir 118*cdf0e10cSrcweir while( nLeafCount > nMax ) 119*cdf0e10cSrcweir ImplReduce(); 120*cdf0e10cSrcweir } 121*cdf0e10cSrcweir 122*cdf0e10cSrcweir // ------------------------------------------------------------------------ 123*cdf0e10cSrcweir 124*cdf0e10cSrcweir void Octree::ImplCreateOctree() 125*cdf0e10cSrcweir { 126*cdf0e10cSrcweir if( !!*pAcc ) 127*cdf0e10cSrcweir { 128*cdf0e10cSrcweir const long nWidth = pAcc->Width(); 129*cdf0e10cSrcweir const long nHeight = pAcc->Height(); 130*cdf0e10cSrcweir 131*cdf0e10cSrcweir if( pAcc->HasPalette() ) 132*cdf0e10cSrcweir { 133*cdf0e10cSrcweir for( long nY = 0; nY < nHeight; nY++ ) 134*cdf0e10cSrcweir { 135*cdf0e10cSrcweir for( long nX = 0; nX < nWidth; nX++ ) 136*cdf0e10cSrcweir { 137*cdf0e10cSrcweir pColor = &(BitmapColor&) pAcc->GetPaletteColor( pAcc->GetPixel( nY, nX ) ); 138*cdf0e10cSrcweir nLevel = 0L; 139*cdf0e10cSrcweir ImplAdd( &pTree ); 140*cdf0e10cSrcweir 141*cdf0e10cSrcweir while( nLeafCount > nMax ) 142*cdf0e10cSrcweir ImplReduce(); 143*cdf0e10cSrcweir } 144*cdf0e10cSrcweir } 145*cdf0e10cSrcweir } 146*cdf0e10cSrcweir else 147*cdf0e10cSrcweir { 148*cdf0e10cSrcweir BitmapColor aColor; 149*cdf0e10cSrcweir 150*cdf0e10cSrcweir pColor = &aColor; 151*cdf0e10cSrcweir 152*cdf0e10cSrcweir for( long nY = 0; nY < nHeight; nY++ ) 153*cdf0e10cSrcweir { 154*cdf0e10cSrcweir for( long nX = 0; nX < nWidth; nX++ ) 155*cdf0e10cSrcweir { 156*cdf0e10cSrcweir aColor = pAcc->GetPixel( nY, nX ); 157*cdf0e10cSrcweir nLevel = 0L; 158*cdf0e10cSrcweir ImplAdd( &pTree ); 159*cdf0e10cSrcweir 160*cdf0e10cSrcweir while( nLeafCount > nMax ) 161*cdf0e10cSrcweir ImplReduce(); 162*cdf0e10cSrcweir } 163*cdf0e10cSrcweir } 164*cdf0e10cSrcweir } 165*cdf0e10cSrcweir } 166*cdf0e10cSrcweir } 167*cdf0e10cSrcweir 168*cdf0e10cSrcweir // ------------------------------------------------------------------------ 169*cdf0e10cSrcweir 170*cdf0e10cSrcweir void Octree::ImplDeleteOctree( PPNODE ppNode ) 171*cdf0e10cSrcweir { 172*cdf0e10cSrcweir for ( sal_uLong i = 0UL; i < 8UL; i++ ) 173*cdf0e10cSrcweir { 174*cdf0e10cSrcweir if ( (*ppNode)->pChild[ i ] ) 175*cdf0e10cSrcweir ImplDeleteOctree( &(*ppNode)->pChild[ i ] ); 176*cdf0e10cSrcweir } 177*cdf0e10cSrcweir 178*cdf0e10cSrcweir pNodeCache->ImplReleaseNode( *ppNode ); 179*cdf0e10cSrcweir *ppNode = NULL; 180*cdf0e10cSrcweir } 181*cdf0e10cSrcweir 182*cdf0e10cSrcweir // ------------------------------------------------------------------------ 183*cdf0e10cSrcweir 184*cdf0e10cSrcweir void Octree::ImplAdd( PPNODE ppNode ) 185*cdf0e10cSrcweir { 186*cdf0e10cSrcweir // ggf. neuen Knoten erzeugen 187*cdf0e10cSrcweir if( !*ppNode ) 188*cdf0e10cSrcweir { 189*cdf0e10cSrcweir *ppNode = pNodeCache->ImplGetFreeNode(); 190*cdf0e10cSrcweir (*ppNode)->bLeaf = ( OCTREE_BITS == nLevel ); 191*cdf0e10cSrcweir 192*cdf0e10cSrcweir if( (*ppNode)->bLeaf ) 193*cdf0e10cSrcweir nLeafCount++; 194*cdf0e10cSrcweir else 195*cdf0e10cSrcweir { 196*cdf0e10cSrcweir (*ppNode)->pNext = pReduce[ nLevel ]; 197*cdf0e10cSrcweir pReduce[ nLevel ] = *ppNode; 198*cdf0e10cSrcweir } 199*cdf0e10cSrcweir } 200*cdf0e10cSrcweir 201*cdf0e10cSrcweir if( (*ppNode)->bLeaf ) 202*cdf0e10cSrcweir { 203*cdf0e10cSrcweir (*ppNode)->nCount++; 204*cdf0e10cSrcweir (*ppNode)->nRed += pColor->GetRed(); 205*cdf0e10cSrcweir (*ppNode)->nGreen += pColor->GetGreen(); 206*cdf0e10cSrcweir (*ppNode)->nBlue += pColor->GetBlue(); 207*cdf0e10cSrcweir } 208*cdf0e10cSrcweir else 209*cdf0e10cSrcweir { 210*cdf0e10cSrcweir const sal_uLong nShift = 7 - nLevel; 211*cdf0e10cSrcweir const sal_uInt8 cMask = pImplMask[ nLevel ]; 212*cdf0e10cSrcweir const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) | 213*cdf0e10cSrcweir ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) | 214*cdf0e10cSrcweir ( ( pColor->GetBlue() & cMask ) >> nShift ); 215*cdf0e10cSrcweir 216*cdf0e10cSrcweir nLevel++; 217*cdf0e10cSrcweir ImplAdd( &(*ppNode)->pChild[ nIndex ] ); 218*cdf0e10cSrcweir } 219*cdf0e10cSrcweir } 220*cdf0e10cSrcweir 221*cdf0e10cSrcweir // ------------------------------------------------------------------------ 222*cdf0e10cSrcweir 223*cdf0e10cSrcweir void Octree::ImplReduce() 224*cdf0e10cSrcweir { 225*cdf0e10cSrcweir sal_uLong i; 226*cdf0e10cSrcweir PNODE pNode; 227*cdf0e10cSrcweir sal_uLong nRedSum = 0L; 228*cdf0e10cSrcweir sal_uLong nGreenSum = 0L; 229*cdf0e10cSrcweir sal_uLong nBlueSum = 0L; 230*cdf0e10cSrcweir sal_uLong nChilds = 0L; 231*cdf0e10cSrcweir 232*cdf0e10cSrcweir for ( i = OCTREE_BITS - 1; i && !pReduce[i]; i-- ) {} 233*cdf0e10cSrcweir 234*cdf0e10cSrcweir pNode = pReduce[ i ]; 235*cdf0e10cSrcweir pReduce[ i ] = pNode->pNext; 236*cdf0e10cSrcweir 237*cdf0e10cSrcweir for ( i = 0; i < 8; i++ ) 238*cdf0e10cSrcweir { 239*cdf0e10cSrcweir if ( pNode->pChild[ i ] ) 240*cdf0e10cSrcweir { 241*cdf0e10cSrcweir PNODE pChild = pNode->pChild[ i ]; 242*cdf0e10cSrcweir 243*cdf0e10cSrcweir nRedSum += pChild->nRed; 244*cdf0e10cSrcweir nGreenSum += pChild->nGreen; 245*cdf0e10cSrcweir nBlueSum += pChild->nBlue; 246*cdf0e10cSrcweir pNode->nCount += pChild->nCount; 247*cdf0e10cSrcweir 248*cdf0e10cSrcweir pNodeCache->ImplReleaseNode( pNode->pChild[ i ] ); 249*cdf0e10cSrcweir pNode->pChild[ i ] = NULL; 250*cdf0e10cSrcweir nChilds++; 251*cdf0e10cSrcweir } 252*cdf0e10cSrcweir } 253*cdf0e10cSrcweir 254*cdf0e10cSrcweir pNode->bLeaf = sal_True; 255*cdf0e10cSrcweir pNode->nRed = nRedSum; 256*cdf0e10cSrcweir pNode->nGreen = nGreenSum; 257*cdf0e10cSrcweir pNode->nBlue = nBlueSum; 258*cdf0e10cSrcweir nLeafCount -= --nChilds; 259*cdf0e10cSrcweir } 260*cdf0e10cSrcweir 261*cdf0e10cSrcweir // ------------------------------------------------------------------------ 262*cdf0e10cSrcweir 263*cdf0e10cSrcweir void Octree::CreatePalette( PNODE pNode ) 264*cdf0e10cSrcweir { 265*cdf0e10cSrcweir if( pNode->bLeaf ) 266*cdf0e10cSrcweir { 267*cdf0e10cSrcweir pNode->nPalIndex = nPalIndex; 268*cdf0e10cSrcweir aPal[ nPalIndex++ ] = BitmapColor( (sal_uInt8) ( (double) pNode->nRed / pNode->nCount ), 269*cdf0e10cSrcweir (sal_uInt8) ( (double) pNode->nGreen / pNode->nCount ), 270*cdf0e10cSrcweir (sal_uInt8) ( (double) pNode->nBlue / pNode->nCount ) ); 271*cdf0e10cSrcweir } 272*cdf0e10cSrcweir else for( sal_uLong i = 0UL; i < 8UL; i++ ) 273*cdf0e10cSrcweir if( pNode->pChild[ i ] ) 274*cdf0e10cSrcweir CreatePalette( pNode->pChild[ i ] ); 275*cdf0e10cSrcweir 276*cdf0e10cSrcweir } 277*cdf0e10cSrcweir 278*cdf0e10cSrcweir // ------------------------------------------------------------------------ 279*cdf0e10cSrcweir 280*cdf0e10cSrcweir void Octree::GetPalIndex( PNODE pNode ) 281*cdf0e10cSrcweir { 282*cdf0e10cSrcweir if ( pNode->bLeaf ) 283*cdf0e10cSrcweir nPalIndex = pNode->nPalIndex; 284*cdf0e10cSrcweir else 285*cdf0e10cSrcweir { 286*cdf0e10cSrcweir const sal_uLong nShift = 7 - nLevel; 287*cdf0e10cSrcweir const sal_uInt8 cMask = pImplMask[ nLevel++ ]; 288*cdf0e10cSrcweir const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) | 289*cdf0e10cSrcweir ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) | 290*cdf0e10cSrcweir ( ( pColor->GetBlue() & cMask ) >> nShift ); 291*cdf0e10cSrcweir 292*cdf0e10cSrcweir GetPalIndex( pNode->pChild[ nIndex ] ); 293*cdf0e10cSrcweir } 294*cdf0e10cSrcweir } 295*cdf0e10cSrcweir 296*cdf0e10cSrcweir // ------------------- 297*cdf0e10cSrcweir // - InverseColorMap - 298*cdf0e10cSrcweir // ------------------- 299*cdf0e10cSrcweir 300*cdf0e10cSrcweir InverseColorMap::InverseColorMap( const BitmapPalette& rPal ) : 301*cdf0e10cSrcweir nBits( 8 - OCTREE_BITS ) 302*cdf0e10cSrcweir { 303*cdf0e10cSrcweir sal_uLong* cdp; 304*cdf0e10cSrcweir sal_uInt8* crgbp; 305*cdf0e10cSrcweir const sal_uLong nColorMax = 1 << OCTREE_BITS; 306*cdf0e10cSrcweir const sal_uLong xsqr = 1 << ( nBits << 1 ); 307*cdf0e10cSrcweir const sal_uLong xsqr2 = xsqr << 1; 308*cdf0e10cSrcweir const sal_uLong nColors = rPal.GetEntryCount(); 309*cdf0e10cSrcweir const long x = 1L << nBits; 310*cdf0e10cSrcweir const long x2 = x >> 1L; 311*cdf0e10cSrcweir sal_uLong r, g, b; 312*cdf0e10cSrcweir long rxx, gxx, bxx; 313*cdf0e10cSrcweir long rdist, gdist, bdist; 314*cdf0e10cSrcweir long crinc, cginc, cbinc; 315*cdf0e10cSrcweir 316*cdf0e10cSrcweir ImplCreateBuffers( nColorMax ); 317*cdf0e10cSrcweir 318*cdf0e10cSrcweir for( sal_uLong nIndex = 0; nIndex < nColors; nIndex++ ) 319*cdf0e10cSrcweir { 320*cdf0e10cSrcweir const BitmapColor& rColor = rPal[ (sal_uInt16) nIndex ]; 321*cdf0e10cSrcweir const sal_uInt8 cRed = rColor.GetRed(); 322*cdf0e10cSrcweir const sal_uInt8 cGreen = rColor.GetGreen(); 323*cdf0e10cSrcweir const sal_uInt8 cBlue = rColor.GetBlue(); 324*cdf0e10cSrcweir 325*cdf0e10cSrcweir rdist = cRed - x2; 326*cdf0e10cSrcweir gdist = cGreen - x2; 327*cdf0e10cSrcweir bdist = cBlue - x2; 328*cdf0e10cSrcweir rdist = rdist*rdist + gdist*gdist + bdist*bdist; 329*cdf0e10cSrcweir 330*cdf0e10cSrcweir crinc = ( xsqr - ( cRed << nBits ) ) << 1L; 331*cdf0e10cSrcweir cginc = ( xsqr - ( cGreen << nBits ) ) << 1L; 332*cdf0e10cSrcweir cbinc = ( xsqr - ( cBlue << nBits ) ) << 1L; 333*cdf0e10cSrcweir 334*cdf0e10cSrcweir cdp = (sal_uLong*) pBuffer; 335*cdf0e10cSrcweir crgbp = pMap; 336*cdf0e10cSrcweir 337*cdf0e10cSrcweir for( r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2 ) 338*cdf0e10cSrcweir { 339*cdf0e10cSrcweir for( g = 0, gdist = rdist, gxx = cginc; g < nColorMax; gdist += gxx, g++, gxx += xsqr2 ) 340*cdf0e10cSrcweir { 341*cdf0e10cSrcweir for( b = 0, bdist = gdist, bxx = cbinc; b < nColorMax; bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2 ) 342*cdf0e10cSrcweir if ( !nIndex || ( (long) *cdp ) > bdist ) 343*cdf0e10cSrcweir { 344*cdf0e10cSrcweir *cdp = bdist; 345*cdf0e10cSrcweir *crgbp = (sal_uInt8) nIndex; 346*cdf0e10cSrcweir } 347*cdf0e10cSrcweir } 348*cdf0e10cSrcweir } 349*cdf0e10cSrcweir } 350*cdf0e10cSrcweir } 351*cdf0e10cSrcweir 352*cdf0e10cSrcweir // ------------------------------------------------------------------------ 353*cdf0e10cSrcweir 354*cdf0e10cSrcweir InverseColorMap::~InverseColorMap() 355*cdf0e10cSrcweir { 356*cdf0e10cSrcweir rtl_freeMemory( pBuffer ); 357*cdf0e10cSrcweir rtl_freeMemory( pMap ); 358*cdf0e10cSrcweir } 359*cdf0e10cSrcweir 360*cdf0e10cSrcweir // ------------------------------------------------------------------------ 361*cdf0e10cSrcweir 362*cdf0e10cSrcweir void InverseColorMap::ImplCreateBuffers( const sal_uLong nMax ) 363*cdf0e10cSrcweir { 364*cdf0e10cSrcweir const sal_uLong nCount = nMax * nMax * nMax; 365*cdf0e10cSrcweir const sal_uLong nSize = nCount * sizeof( sal_uLong ); 366*cdf0e10cSrcweir 367*cdf0e10cSrcweir pMap = (sal_uInt8*) rtl_allocateMemory( nCount ); 368*cdf0e10cSrcweir memset( pMap, 0x00, nCount ); 369*cdf0e10cSrcweir 370*cdf0e10cSrcweir pBuffer = (sal_uInt8*) rtl_allocateMemory( nSize ); 371*cdf0e10cSrcweir memset( pBuffer, 0xff, nSize ); 372*cdf0e10cSrcweir } 373