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 #include <limits.h>
  21
  22 #include <rtl/alloc.h>
  23 #include <vcl/bitmapaccess.hxx>
  24
  25 #include "octree.hxx"
  26 #include "impoctree.hxx"
  27
  28 static const sal_uInt8 pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
  29
  30 ImpNodeCache::ImpNodeCache( const sal_uLong nInitSize ) :
  31             pActNode( nullptr )
  32 {
  33     const sal_uLong nSize = nInitSize + 4;
  34
  35     for( sal_uLong i = 0; i < nSize; i++ )
  36     {
  37         OctreeNode* pNewNode = new NODE;
  38
  39         pNewNode->pNextInCache = pActNode;
  40         pActNode = pNewNode;
  41     }
  42 }
  43
  44 ImpNodeCache::~ImpNodeCache()
  45 {
  46     while( pActNode )
  47     {
  48         OctreeNode* pNode = pActNode;
  49
  50         pActNode = pNode->pNextInCache;
  51         delete pNode;
  52     }
  53 }
  54
  55 Octree::Octree(const BitmapReadAccess& rReadAcc, sal_uLong nColors)
  56     : nMax(nColors)
  57     , nLeafCount(0)
  58     , nLevel(0)
  59     , pTree(nullptr)
  60     , pColor(nullptr)
  61     , pAcc(&rReadAcc)
  62     , nPalIndex(0)
  63 {
  64     pNodeCache = new ImpNodeCache( nColors );
  65     memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( NODE* ) );
  66
  67     if( !!*pAcc )
  68     {
  69         const long      nWidth = pAcc->Width();
  70         const long      nHeight = pAcc->Height();
  71
  72         if( pAcc->HasPalette() )
  73         {
  74             for( long nY = 0; nY < nHeight; nY++ )
  75             {
  76                 for( long nX = 0; nX < nWidth; nX++ )
  77                 {
  78                     pColor = &(BitmapColor&) pAcc->GetPaletteColor( pAcc->GetPixelIndex( nY, nX ) );
  79                     nLevel = 0;
  80                     ImplAdd( &pTree );
  81
  82                     while( nLeafCount > nMax )
  83                         ImplReduce();
  84                 }
  85             }
  86         }
  87         else
  88         {
  89             BitmapColor aColor;
  90
  91             pColor = &aColor;
  92
  93             for( long nY = 0; nY < nHeight; nY++ )
  94             {
  95                 for( long nX = 0; nX < nWidth; nX++ )
  96                 {
  97                     aColor = pAcc->GetPixel( nY, nX );
  98                     nLevel = 0;
  99                     ImplAdd( &pTree );
 100
 101                     while( nLeafCount > nMax )
 102                         ImplReduce();
 103                 }
 104             }
 105         }
 106     }
 107 }
 108
 109 Octree::~Octree()
 110 {
 111     ImplDeleteOctree( &pTree );
 112     delete pNodeCache;
 113 }
 114
 115 void Octree::ImplDeleteOctree( NODE** ppNode )
 116 {
 117     for (OctreeNode* i : (*ppNode)->pChild)
 118     {
 119         if ( i )
 120             ImplDeleteOctree( &i );
 121     }
 122
 123     pNodeCache->ImplReleaseNode( *ppNode );
 124     *ppNode = nullptr;
 125 }
 126
 127 void Octree::ImplAdd( NODE** ppNode )
 128 {
 129     // possibly generate new nodes
 130     if( !*ppNode )
 131     {
 132         *ppNode = pNodeCache->ImplGetFreeNode();
 133         (*ppNode)->bLeaf = ( OCTREE_BITS == nLevel );
 134
 135         if( (*ppNode)->bLeaf )
 136             nLeafCount++;
 137         else
 138         {
 139             (*ppNode)->pNext = pReduce[ nLevel ];
 140             pReduce[ nLevel ] = *ppNode;
 141         }
 142     }
 143
 144     if( (*ppNode)->bLeaf )
 145     {
 146         (*ppNode)->nCount++;
 147         (*ppNode)->nRed += pColor->GetRed();
 148         (*ppNode)->nGreen += pColor->GetGreen();
 149         (*ppNode)->nBlue += pColor->GetBlue();
 150     }
 151     else
 152     {
 153         const sal_uLong nShift = 7 - nLevel;
 154         const sal_uInt8  cMask = pImplMask[ nLevel ];
 155         const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
 156                              ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
 157                              ( ( pColor->GetBlue() & cMask ) >> nShift );
 158
 159         nLevel++;
 160         ImplAdd( &(*ppNode)->pChild[ nIndex ] );
 161     }
 162 }
 163
 164 void Octree::ImplReduce()
 165 {
 166     sal_uLong   i;
 167     NODE*       pNode;
 168     sal_uLong   nRedSum = 0;
 169     sal_uLong   nGreenSum = 0;
 170     sal_uLong   nBlueSum = 0;
 171     sal_uLong   nChildren = 0;
 172
 173     for ( i = OCTREE_BITS - 1; i && !pReduce[i]; i-- ) {}
 174
 175     pNode = pReduce[ i ];
 176     pReduce[ i ] = pNode->pNext;
 177
 178     for ( i = 0; i < 8; i++ )
 179     {
 180         if ( pNode->pChild[ i ] )
 181         {
 182             NODE* pChild = pNode->pChild[ i ];
 183
 184             nRedSum += pChild->nRed;
 185             nGreenSum += pChild->nGreen;
 186             nBlueSum += pChild->nBlue;
 187             pNode->nCount += pChild->nCount;
 188
 189             pNodeCache->ImplReleaseNode( pNode->pChild[ i ] );
 190             pNode->pChild[ i ] = nullptr;
 191             nChildren++;
 192         }
 193     }
 194
 195     pNode->bLeaf = true;
 196     pNode->nRed = nRedSum;
 197     pNode->nGreen = nGreenSum;
 198     pNode->nBlue = nBlueSum;
 199     nLeafCount -= --nChildren;
 200 }
 201
 202 void Octree::CreatePalette( NODE* pNode )
 203 {
 204     if( pNode->bLeaf )
 205     {
 206         pNode->nPalIndex = nPalIndex;
 207         aPal[ nPalIndex++ ] = BitmapColor( (sal_uInt8) ( (double) pNode->nRed / pNode->nCount ),
 208                                            (sal_uInt8) ( (double) pNode->nGreen / pNode->nCount ),
 209                                            (sal_uInt8) ( (double) pNode->nBlue / pNode->nCount ) );
 210     }
 211     else for(OctreeNode* i : pNode->pChild)
 212         if( i )
 213             CreatePalette( i );
 214
 215 }
 216
 217 void Octree::GetPalIndex( NODE* pNode )
 218 {
 219     if ( pNode->bLeaf )
 220         nPalIndex = pNode->nPalIndex;
 221     else
 222     {
 223         const sal_uLong nShift = 7 - nLevel;
 224         const sal_uInt8  cMask = pImplMask[ nLevel++ ];
 225         const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
 226                              ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
 227                              ( ( pColor->GetBlue() & cMask ) >> nShift );
 228
 229         GetPalIndex( pNode->pChild[ nIndex ] );
 230     }
 231 }
 232
 233 InverseColorMap::InverseColorMap( const BitmapPalette& rPal ) :
 234             nBits( 8 - OCTREE_BITS )
 235 {
 236     const int     nColorMax = 1 << OCTREE_BITS;
 237     const unsigned long xsqr = 1 << ( nBits << 1 );
 238     const unsigned long xsqr2 = xsqr << 1;
 239     const int     nColors = rPal.GetEntryCount();
 240     const long      x = 1 << nBits;
 241     const long      x2 = x >> 1;
 242     sal_uLong           r, g, b;
 243     long            rxx, gxx, bxx;
 244
 245     ImplCreateBuffers( nColorMax );
 246
 247     for( int nIndex = 0; nIndex < nColors; nIndex++ )
 248     {
 249         const BitmapColor&  rColor = rPal[ (sal_uInt16) nIndex ];
 250         const long          cRed = rColor.GetRed();
 251         const long          cGreen = rColor.GetGreen();
 252         const long          cBlue = rColor.GetBlue();
 253
 254         long rdist = cRed - x2;
 255         long gdist = cGreen - x2;
 256         long bdist = cBlue - x2;
 257         rdist = rdist*rdist + gdist*gdist + bdist*bdist;
 258
 259         const long crinc = ( xsqr - ( cRed << nBits ) ) << 1;
 260         const long cginc = ( xsqr - ( cGreen << nBits ) ) << 1;
 261         const long cbinc = ( xsqr - ( cBlue << nBits ) ) << 1;
 262
 263         sal_uLong* cdp = reinterpret_cast<sal_uLong*>(pBuffer);
 264         sal_uInt8* crgbp = pMap;
 265
 266         for( r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2 )
 267         {
 268             for( g = 0, gdist = rdist, gxx = cginc; g < nColorMax;  gdist += gxx, g++, gxx += xsqr2 )
 269             {
 270                 for( b = 0, bdist = gdist, bxx = cbinc; b < nColorMax; bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2 )
 271                     if ( !nIndex || ( (long) *cdp ) > bdist )
 272                     {
 273                         *cdp = bdist;
 274                         *crgbp = (sal_uInt8) nIndex;
 275                     }
 276             }
 277         }
 278     }
 279 }
 280
 281 InverseColorMap::~InverseColorMap()
 282 {
 283     rtl_freeMemory( pBuffer );
 284     rtl_freeMemory( pMap );
 285 }
 286
 287 void InverseColorMap::ImplCreateBuffers( const sal_uLong nMax )
 288 {
 289     const sal_uLong nCount = nMax * nMax * nMax;
 290     const sal_uLong nSize = nCount * sizeof( sal_uLong );
 291
 292     pMap = static_cast<sal_uInt8*>(rtl_allocateMemory( nCount ));
 293     memset( pMap, 0x00, nCount );
 294
 295     pBuffer = static_cast<sal_uInt8*>(rtl_allocateMemory( nSize ));
 296     memset( pBuffer, 0xff, nSize );
 297 }
 298
 299 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */