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