vcl/source/gdi/octree.cxx

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