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