LibreOffice Module vcl (master)  1
Octree.cxx
Go to the documentation of this file.
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  {
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 
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 
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 
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 
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 
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 
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 
271 
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 
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: */
const BitmapReadAccess * mpAccess
Definition: Octree.hxx:55
Octree(const BitmapReadAccess &rReadAcc, sal_uLong nColors)
Definition: Octree.cxx:33
sal_uInt8 GetRed() const
Scanline GetScanline(long nY) const
void SetEntryCount(sal_uInt16 nCount)
sal_uIntPtr sal_uLong
bool bLeaf
Definition: Octree.hxx:35
void GetPalIndex(const OctreeNode *pNode)
Definition: Octree.cxx:187
long Width() const
float x
std::unique_ptr< OctreeNode > pTree
Definition: Octree.hxx:52
std::unique_ptr< OctreeNode > pChild[8]
Definition: Octree.hxx:32
void ImplCreateBuffers()
Definition: Octree.cxx:272
~Octree()
Definition: Octree.cxx:87
sal_uInt16 mnPalIndex
Definition: Octree.hxx:56
sal_uLong mnLeafCount
Definition: Octree.hxx:50
sal_uInt8 GetBlue() const
sal_uLong nCount
Definition: Octree.hxx:28
sal_uInt16 GetEntryCount() const
void CreatePalette(OctreeNode *pNode)
Definition: Octree.cxx:166
sal_uInt8 * Scanline
Definition: Scanline.hxx:25
OctreeNode * pNext
Definition: Octree.hxx:33
sal_uLong nBlue
Definition: Octree.hxx:31
bool HasPalette() const
std::vector< sal_uInt8 > mpBuffer
Definition: Octree.hxx:69
int i
BitmapPalette maPalette
Definition: Octree.hxx:49
sal_uInt16 nPalIndex
Definition: Octree.hxx:34
std::vector< sal_uInt8 > mpMap
Definition: Octree.hxx:70
sal_uLong mnLevel
Definition: Octree.hxx:51
std::vector< OctreeNode * > mpReduce
Definition: Octree.hxx:53
BitmapColor const * mpColor
Definition: Octree.hxx:54
SAL_DLLPRIVATE void add(std::unique_ptr< OctreeNode > &rpNode)
Definition: Octree.cxx:89
sal_uInt8 GetGreen() const
sal_uLong nGreen
Definition: Octree.hxx:30
long Height() const
unsigned char sal_uInt8
sal_uLong nRed
Definition: Octree.hxx:29
BitmapColor GetPixelFromData(const sal_uInt8 *pData, long nX) const
constexpr int nColorMax
Definition: Octree.cxx:221
const BitmapColor & GetPaletteColor(sal_uInt16 nColor) const
SAL_DLLPRIVATE void reduce()
Definition: Octree.cxx:126
sal_uInt16 GetBestPaletteIndex(const BitmapColor &rColor)
Definition: Octree.cxx:281
sal_uInt16 GetBestPaletteIndex(const BitmapColor &rColor)
Definition: Octree.cxx:212
InverseColorMap(const BitmapPalette &rPal)
Definition: Octree.cxx:223
const BitmapPalette & GetPalette()
Definition: Octree.cxx:204
sal_uInt8 GetIndexFromData(const sal_uInt8 *pData, long nX) const