vcl/source/gdi/octree.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: octree.cxx,v $
  10  * $Revision: 1.8 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_vcl.hxx"
  33 #include <limits.h>
  34 #include <vcl/bmpacc.hxx>
  35 #include <vcl/impoct.hxx>
  36 #include <vcl/octree.hxx>
  37
  38 // ---------
  39 // - pMask -
  40 // ---------
  41
  42 static BYTE pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  43
  44 // -------------
  45 // - NodeCache -
  46 // -------------
  47
  48 ImpNodeCache::ImpNodeCache( const ULONG nInitSize ) :
  49             pActNode( NULL )
  50 {
  51     const ULONG nSize = nInitSize + 4;
  52
  53     for( 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( 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, 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 ( 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 ULONG nShift = 7 - nLevel;
 211         const BYTE  cMask = pImplMask[ nLevel ];
 212         const 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     ULONG   i;
 226     PNODE   pNode;
 227     ULONG   nRedSum = 0L;
 228     ULONG   nGreenSum = 0L;
 229     ULONG   nBlueSum = 0L;
 230     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 = 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( (BYTE) ( (double) pNode->nRed / pNode->nCount ),
 269                                            (BYTE) ( (double) pNode->nGreen / pNode->nCount ),
 270                                            (BYTE) ( (double) pNode->nBlue / pNode->nCount ) );
 271     }
 272     else for( 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 ULONG nShift = 7 - nLevel;
 287         const BYTE  cMask = pImplMask[ nLevel++ ];
 288         const 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     ULONG*                      cdp;
 304     BYTE*           crgbp;
 305     const ULONG     nColorMax = 1 << OCTREE_BITS;
 306     const ULONG     xsqr = 1 << ( nBits << 1 );
 307     const ULONG     xsqr2 = xsqr << 1;
 308     const ULONG     nColors = rPal.GetEntryCount();
 309     const long      x = 1L << nBits;
 310     const long      x2 = x >> 1L;
 311     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( ULONG nIndex = 0; nIndex < nColors; nIndex++ )
 319     {
 320         const BitmapColor&  rColor = rPal[ (USHORT) nIndex ];
 321         const BYTE                      cRed = rColor.GetRed();
 322         const BYTE                      cGreen = rColor.GetGreen();
 323         const BYTE                      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 = (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 = (BYTE) 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 ULONG nMax )
 363 {
 364     const ULONG nCount = nMax * nMax * nMax;
 365     const ULONG nSize = nCount * sizeof( ULONG );
 366
 367     pMap = (BYTE*) rtl_allocateMemory( nCount );
 368     memset( pMap, 0x00, nCount );
 369
 370     pBuffer = (BYTE*) rtl_allocateMemory( nSize );
 371     memset( pBuffer, 0xff, nSize );
 372 }