vcl/source/bitmap/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 <vcl/BitmapReadAccess.hxx>
  21
  22 #include <bitmap/Octree.hxx>
  23
  24 namespace
  25 {
  26 constexpr size_t OCTREE_BITS = 5;
  27 constexpr size_t OCTREE_BITS_1 = 10;
  28
  29 constexpr sal_uLong gnBits = 8 - OCTREE_BITS;
  30
  31 } // end anonymous namespace
  32
  33 Octree::Octree(const BitmapReadAccess& rReadAcc, sal_uLong nColors)
  34     : mnLeafCount(0)
  35     , mnLevel(0)
  36     , mpReduce(OCTREE_BITS + 1, nullptr)
  37     , mnPalIndex(0)
  38 {
  39     const BitmapReadAccess* pAccess = &rReadAcc;
  40     sal_uLong nMax(nColors);
  41
  42     if (!*pAccess)
  43         return;
  44
  45     const tools::Long nWidth = pAccess->Width();
  46     const tools::Long nHeight = pAccess->Height();
  47
  48     if (pAccess->HasPalette())
  49     {
  50         for (tools::Long nY = 0; nY < nHeight; nY++)
  51         {
  52             Scanline pScanline = pAccess->GetScanline(nY);
  53             for (tools::Long nX = 0; nX < nWidth; nX++)
  54             {
  55                 mnLevel = 0;
  56                 add(pTree, pAccess->GetPaletteColor(pAccess->GetIndexFromData(pScanline, nX)));
  57
  58                 while (mnLeafCount > nMax)
  59                     reduce();
  60             }
  61         }
  62     }
  63     else
  64     {
  65         for (tools::Long nY = 0; nY < nHeight; nY++)
  66         {
  67             Scanline pScanline = pAccess->GetScanline(nY);
  68             for (tools::Long nX = 0; nX < nWidth; nX++)
  69             {
  70                 mnLevel = 0;
  71                 add(pTree, pAccess->GetPixelFromData(pScanline, nX));
  72
  73                 while (mnLeafCount > nMax)
  74                     reduce();
  75             }
  76         }
  77     }
  78 }
  79
  80 Octree::~Octree() {}
  81
  82 void Octree::add(std::unique_ptr<OctreeNode>& rpNode, BitmapColor const& color)
  83 {
  84     // possibly generate new nodes
  85     if (!rpNode)
  86     {
  87         rpNode.reset(new OctreeNode);
  88         rpNode->bLeaf = (OCTREE_BITS == mnLevel);
  89
  90         if (rpNode->bLeaf)
  91             mnLeafCount++;
  92         else
  93         {
  94             rpNode->pNext = mpReduce[mnLevel];
  95             mpReduce[mnLevel] = rpNode.get();
  96         }
  97     }
  98
  99     if (rpNode->bLeaf)
 100     {
 101         rpNode->nCount++;
 102         rpNode->nRed += color.GetRed();
 103         rpNode->nGreen += color.GetGreen();
 104         rpNode->nBlue += color.GetBlue();
 105     }
 106     else
 107     {
 108         const sal_uLong nShift = 7 - mnLevel;
 109         const sal_uInt8 cMask = 0x80 >> mnLevel;
 110         const sal_uLong nIndex = (((color.GetRed() & cMask) >> nShift) << 2)
 111                                  | (((color.GetGreen() & cMask) >> nShift) << 1)
 112                                  | ((color.GetBlue() & cMask) >> nShift);
 113
 114         mnLevel++;
 115         add(rpNode->pChild[nIndex], color);
 116     }
 117 }
 118
 119 void Octree::reduce()
 120 {
 121     OctreeNode* pNode;
 122     sal_uLong nRedSum = 0;
 123     sal_uLong nGreenSum = 0;
 124     sal_uLong nBlueSum = 0;
 125     sal_uLong nChildren = 0;
 126
 127     sal_uLong nIndex = OCTREE_BITS - 1;
 128     while (nIndex > 0 && !mpReduce[nIndex])
 129     {
 130         nIndex--;
 131     }
 132
 133     pNode = mpReduce[nIndex];
 134     mpReduce[nIndex] = pNode->pNext;
 135
 136     for (unsigned int i = 0; i < 8; i++)
 137     {
 138         if (pNode->pChild[i])
 139         {
 140             OctreeNode* pChild = pNode->pChild[i].get();
 141
 142             nRedSum += pChild->nRed;
 143             nGreenSum += pChild->nGreen;
 144             nBlueSum += pChild->nBlue;
 145             pNode->nCount += pChild->nCount;
 146
 147             pNode->pChild[i].reset();
 148             nChildren++;
 149         }
 150     }
 151
 152     pNode->bLeaf = true;
 153     pNode->nRed = nRedSum;
 154     pNode->nGreen = nGreenSum;
 155     pNode->nBlue = nBlueSum;
 156     mnLeafCount -= --nChildren;
 157 }
 158
 159 void Octree::CreatePalette(OctreeNode* pNode)
 160 {
 161     if (pNode->bLeaf)
 162     {
 163         pNode->nPalIndex = mnPalIndex;
 164         maPalette[mnPalIndex++] = BitmapColor(sal_uInt8(double(pNode->nRed) / pNode->nCount),
 165                                               sal_uInt8(double(pNode->nGreen) / pNode->nCount),
 166                                               sal_uInt8(double(pNode->nBlue) / pNode->nCount));
 167     }
 168     else
 169     {
 170         for (auto const& i : pNode->pChild)
 171         {
 172             if (i)
 173             {
 174                 CreatePalette(i.get());
 175             }
 176         }
 177     }
 178 }
 179
 180 void Octree::GetPalIndex(const OctreeNode* pNode, BitmapColor const& color)
 181 {
 182     if (pNode->bLeaf)
 183         mnPalIndex = pNode->nPalIndex;
 184     else
 185     {
 186         const sal_uLong nShift = 7 - mnLevel;
 187         const sal_uInt8 cMask = 0x80 >> mnLevel;
 188         mnLevel++;
 189         const sal_uLong nIndex = (((color.GetRed() & cMask) >> nShift) << 2)
 190                                  | (((color.GetGreen() & cMask) >> nShift) << 1)
 191                                  | ((color.GetBlue() & cMask) >> nShift);
 192
 193         GetPalIndex(pNode->pChild[nIndex].get(), color);
 194     }
 195 }
 196
 197 const BitmapPalette& Octree::GetPalette()
 198 {
 199     maPalette.SetEntryCount(sal_uInt16(mnLeafCount));
 200     mnPalIndex = 0;
 201     CreatePalette(pTree.get());
 202     return maPalette;
 203 }
 204
 205 sal_uInt16 Octree::GetBestPaletteIndex(const BitmapColor& rColor)
 206 {
 207     mnPalIndex = 65535;
 208     mnLevel = 0;
 209     GetPalIndex(pTree.get(), rColor);
 210     return mnPalIndex;
 211 }
 212
 213 constexpr int nColorMax = 1 << OCTREE_BITS;
 214
 215 InverseColorMap::InverseColorMap(const BitmapPalette& rPal)
 216 {
 217     const unsigned long xsqr = 1 << (gnBits << 1);
 218     const unsigned long xsqr2 = xsqr << 1;
 219     const int nColors = rPal.GetEntryCount();
 220     const tools::Long x = 1 << gnBits;
 221     const tools::Long x2 = x >> 1;
 222     sal_uLong r, g, b;
 223     tools::Long rxx, gxx, bxx;
 224
 225     ImplCreateBuffers();
 226
 227     for (int nIndex = 0; nIndex < nColors; nIndex++)
 228     {
 229         const BitmapColor& rColor = rPal[static_cast<sal_uInt16>(nIndex)];
 230         const tools::Long cRed = rColor.GetRed();
 231         const tools::Long cGreen = rColor.GetGreen();
 232         const tools::Long cBlue = rColor.GetBlue();
 233
 234         tools::Long rdist = cRed - x2;
 235         tools::Long gdist = cGreen - x2;
 236         tools::Long bdist = cBlue - x2;
 237         rdist = rdist * rdist + gdist * gdist + bdist * bdist;
 238
 239         const tools::Long crinc = (xsqr - (cRed << gnBits)) << 1;
 240         const tools::Long cginc = (xsqr - (cGreen << gnBits)) << 1;
 241         const tools::Long cbinc = (xsqr - (cBlue << gnBits)) << 1;
 242
 243         sal_uLong* cdp = reinterpret_cast<sal_uLong*>(mpBuffer.data());
 244         sal_uInt8* crgbp = mpMap.data();
 245
 246         for (r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2)
 247         {
 248             for (g = 0, gdist = rdist, gxx = cginc; g < nColorMax; gdist += gxx, g++, gxx += xsqr2)
 249             {
 250                 for (b = 0, bdist = gdist, bxx = cbinc; b < nColorMax;
 251                      bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2)
 252                     if (!nIndex || static_cast<tools::Long>(*cdp) > bdist)
 253                     {
 254                         *cdp = bdist;
 255                         *crgbp = static_cast<sal_uInt8>(nIndex);
 256                     }
 257             }
 258         }
 259     }
 260 }
 261
 262 InverseColorMap::~InverseColorMap() {}
 263
 264 void InverseColorMap::ImplCreateBuffers()
 265 {
 266     const sal_uLong nCount = nColorMax * nColorMax * nColorMax;
 267     const sal_uLong nSize = nCount * sizeof(sal_uLong);
 268
 269     mpMap.resize(nCount, 0x00);
 270     mpBuffer.resize(nSize, 0xff);
 271 }
 272
 273 sal_uInt16 InverseColorMap::GetBestPaletteIndex(const BitmapColor& rColor)
 274 {
 275     return mpMap[((static_cast<sal_uLong>(rColor.GetRed()) >> gnBits) << OCTREE_BITS_1)
 276                  | ((static_cast<sal_uLong>(rColor.GetGreen()) >> gnBits) << OCTREE_BITS)
 277                  | (static_cast<sal_uLong>(rColor.GetBlue()) >> gnBits)];
 278 }
 279
 280 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */