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