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 
34 {
35 private:
37 
38 public:
39  ImpNodeCache(const sal_uLong nInitSize)
40  : mpActNode(nullptr)
41  {
42  const sal_uLong nSize = nInitSize + 4;
43 
44  for (sal_uLong i = 0; i < nSize; i++)
45  {
46  OctreeNode* pNewNode = new OctreeNode;
47 
48  pNewNode->pNextInCache = mpActNode;
49  mpActNode = pNewNode;
50  }
51  }
52 
54  {
55  while (mpActNode)
56  {
57  OctreeNode* pNode = mpActNode;
58 
59  mpActNode = pNode->pNextInCache;
60  delete pNode;
61  }
62  }
63 
65  {
66  OctreeNode* pNode;
67 
68  if (!mpActNode)
69  {
70  mpActNode = new OctreeNode;
71  mpActNode->pNextInCache = nullptr;
72  }
73 
74  pNode = mpActNode;
75  mpActNode = pNode->pNextInCache;
76  memset(pNode, 0, sizeof(OctreeNode));
77 
78  return pNode;
79  }
81  {
82  pNode->pNextInCache = mpActNode;
83  mpActNode = pNode;
84  }
85 };
86 
87 Octree::Octree(const BitmapReadAccess& rReadAcc, sal_uLong nColors)
88  : mnLeafCount(0)
89  , mnLevel(0)
90  , pTree(nullptr)
91  , mpReduce(OCTREE_BITS + 1, nullptr)
92  , mpColor(nullptr)
93  , mpNodeCache(std::make_unique<ImpNodeCache>(nColors))
94  , mpAccess(&rReadAcc)
95  , mnPalIndex(0)
96 {
97  sal_uLong nMax(nColors);
98 
99  if (!!*mpAccess)
100  {
101  const long nWidth = mpAccess->Width();
102  const long nHeight = mpAccess->Height();
103 
104  if (mpAccess->HasPalette())
105  {
106  for (long nY = 0; nY < nHeight; nY++)
107  {
108  Scanline pScanline = mpAccess->GetScanline(nY);
109  for (long nX = 0; nX < nWidth; nX++)
110  {
112  mnLevel = 0;
113  add(&pTree);
114 
115  while (mnLeafCount > nMax)
116  reduce();
117  }
118  }
119  }
120  else
121  {
122  BitmapColor aColor;
123 
124  mpColor = &aColor;
125 
126  for (long nY = 0; nY < nHeight; nY++)
127  {
128  Scanline pScanline = mpAccess->GetScanline(nY);
129  for (long nX = 0; nX < nWidth; nX++)
130  {
131  aColor = mpAccess->GetPixelFromData(pScanline, nX);
132  mnLevel = 0;
133  add(&pTree);
134 
135  while (mnLeafCount > nMax)
136  reduce();
137  }
138  }
139  }
140  }
141 }
142 
144 
146 {
147  for (OctreeNode* i : (*ppNode)->pChild)
148  {
149  if (i)
150  deleteOctree(&i);
151  }
152 
153  mpNodeCache->ImplReleaseNode(*ppNode);
154  *ppNode = nullptr;
155 }
156 
157 void Octree::add(OctreeNode** ppNode)
158 {
159  // possibly generate new nodes
160  if (!*ppNode)
161  {
162  *ppNode = mpNodeCache->ImplGetFreeNode();
163  (*ppNode)->bLeaf = (OCTREE_BITS == mnLevel);
164 
165  if ((*ppNode)->bLeaf)
166  mnLeafCount++;
167  else
168  {
169  (*ppNode)->pNext = mpReduce[mnLevel];
170  mpReduce[mnLevel] = *ppNode;
171  }
172  }
173 
174  if ((*ppNode)->bLeaf)
175  {
176  (*ppNode)->nCount++;
177  (*ppNode)->nRed += mpColor->GetRed();
178  (*ppNode)->nGreen += mpColor->GetGreen();
179  (*ppNode)->nBlue += mpColor->GetBlue();
180  }
181  else
182  {
183  const sal_uLong nShift = 7 - mnLevel;
184  const sal_uInt8 cMask = 0x80 >> mnLevel;
185  const sal_uLong nIndex = (((mpColor->GetRed() & cMask) >> nShift) << 2)
186  | (((mpColor->GetGreen() & cMask) >> nShift) << 1)
187  | ((mpColor->GetBlue() & cMask) >> nShift);
188 
189  mnLevel++;
190  add(&(*ppNode)->pChild[nIndex]);
191  }
192 }
193 
195 {
196  OctreeNode* pNode;
197  sal_uLong nRedSum = 0;
198  sal_uLong nGreenSum = 0;
199  sal_uLong nBlueSum = 0;
200  sal_uLong nChildren = 0;
201 
202  sal_uLong nIndex = OCTREE_BITS - 1;
203  while (nIndex > 0 && !mpReduce[nIndex])
204  {
205  nIndex--;
206  }
207 
208  pNode = mpReduce[nIndex];
209  mpReduce[nIndex] = pNode->pNext;
210 
211  for (sal_uLong i = 0; i < 8; i++)
212  {
213  if (pNode->pChild[i])
214  {
215  OctreeNode* pChild = pNode->pChild[i];
216 
217  nRedSum += pChild->nRed;
218  nGreenSum += pChild->nGreen;
219  nBlueSum += pChild->nBlue;
220  pNode->nCount += pChild->nCount;
221 
222  mpNodeCache->ImplReleaseNode(pNode->pChild[i]);
223  pNode->pChild[i] = nullptr;
224  nChildren++;
225  }
226  }
227 
228  pNode->bLeaf = true;
229  pNode->nRed = nRedSum;
230  pNode->nGreen = nGreenSum;
231  pNode->nBlue = nBlueSum;
232  mnLeafCount -= --nChildren;
233 }
234 
236 {
237  if (pNode->bLeaf)
238  {
239  pNode->nPalIndex = mnPalIndex;
240  maPalette[mnPalIndex++] = BitmapColor(sal_uInt8(double(pNode->nRed) / pNode->nCount),
241  sal_uInt8(double(pNode->nGreen) / pNode->nCount),
242  sal_uInt8(double(pNode->nBlue) / pNode->nCount));
243  }
244  else
245  {
246  for (OctreeNode* i : pNode->pChild)
247  {
248  if (i)
249  {
250  CreatePalette(i);
251  }
252  }
253  }
254 }
255 
257 {
258  if (pNode->bLeaf)
259  mnPalIndex = pNode->nPalIndex;
260  else
261  {
262  const sal_uLong nShift = 7 - mnLevel;
263  const sal_uInt8 cMask = 0x80 >> mnLevel;
264  mnLevel++;
265  const sal_uLong nIndex = (((mpColor->GetRed() & cMask) >> nShift) << 2)
266  | (((mpColor->GetGreen() & cMask) >> nShift) << 1)
267  | ((mpColor->GetBlue() & cMask) >> nShift);
268 
269  GetPalIndex(pNode->pChild[nIndex]);
270  }
271 }
272 
274 {
275  maPalette.SetEntryCount(sal_uInt16(mnLeafCount));
276  mnPalIndex = 0;
278  return maPalette;
279 }
280 
281 sal_uInt16 Octree::GetBestPaletteIndex(const BitmapColor& rColor)
282 {
283  mpColor = &rColor;
284  mnPalIndex = 65535;
285  mnLevel = 0;
287  return mnPalIndex;
288 }
289 
290 constexpr int nColorMax = 1 << OCTREE_BITS;
291 
293 {
294  const unsigned long xsqr = 1 << (gnBits << 1);
295  const unsigned long xsqr2 = xsqr << 1;
296  const int nColors = rPal.GetEntryCount();
297  const long x = 1 << gnBits;
298  const long x2 = x >> 1;
299  sal_uLong r, g, b;
300  long rxx, gxx, bxx;
301 
303 
304  for (int nIndex = 0; nIndex < nColors; nIndex++)
305  {
306  const BitmapColor& rColor = rPal[static_cast<sal_uInt16>(nIndex)];
307  const long cRed = rColor.GetRed();
308  const long cGreen = rColor.GetGreen();
309  const long cBlue = rColor.GetBlue();
310 
311  long rdist = cRed - x2;
312  long gdist = cGreen - x2;
313  long bdist = cBlue - x2;
314  rdist = rdist * rdist + gdist * gdist + bdist * bdist;
315 
316  const long crinc = (xsqr - (cRed << gnBits)) << 1;
317  const long cginc = (xsqr - (cGreen << gnBits)) << 1;
318  const long cbinc = (xsqr - (cBlue << gnBits)) << 1;
319 
320  sal_uLong* cdp = reinterpret_cast<sal_uLong*>(mpBuffer.data());
321  sal_uInt8* crgbp = mpMap.data();
322 
323  for (r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2)
324  {
325  for (g = 0, gdist = rdist, gxx = cginc; g < nColorMax; gdist += gxx, g++, gxx += xsqr2)
326  {
327  for (b = 0, bdist = gdist, bxx = cbinc; b < nColorMax;
328  bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2)
329  if (!nIndex || static_cast<long>(*cdp) > bdist)
330  {
331  *cdp = bdist;
332  *crgbp = static_cast<sal_uInt8>(nIndex);
333  }
334  }
335  }
336  }
337 }
338 
340 
342 {
343  const sal_uLong nCount = nColorMax * nColorMax * nColorMax;
344  const sal_uLong nSize = nCount * sizeof(sal_uLong);
345 
346  mpMap.resize(nCount, 0x00);
347  mpBuffer.resize(nSize, 0xff);
348 }
349 
351 {
352  return mpMap[((static_cast<sal_uLong>(rColor.GetRed()) >> gnBits) << OCTREE_BITS_1)
353  | ((static_cast<sal_uLong>(rColor.GetGreen()) >> gnBits) << OCTREE_BITS)
354  | (static_cast<sal_uLong>(rColor.GetBlue()) >> gnBits)];
355 }
356 
357 /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
const BitmapReadAccess * mpAccess
Definition: Octree.hxx:59
Octree(const BitmapReadAccess &rReadAcc, sal_uLong nColors)
Definition: Octree.cxx:87
sal_uInt8 GetRed() const
Scanline GetScanline(long nY) const
void SetEntryCount(sal_uInt16 nCount)
sal_uIntPtr sal_uLong
bool bLeaf
Definition: Octree.hxx:36
OctreeNode * mpActNode
Definition: Octree.cxx:36
long Width() const
float x
SAL_DLLPRIVATE void ImplCreateBuffers()
Definition: Octree.cxx:341
std::unique_ptr< ImpNodeCache > mpNodeCache
Definition: Octree.hxx:58
~Octree()
Definition: Octree.cxx:143
sal_uInt16 mnPalIndex
Definition: Octree.hxx:60
sal_uLong mnLeafCount
Definition: Octree.hxx:53
sal_uInt8 GetBlue() const
OctreeNode * ImplGetFreeNode()
Definition: Octree.cxx:64
sal_uLong nCount
Definition: Octree.hxx:28
sal_uInt16 GetEntryCount() const
void CreatePalette(OctreeNode *pNode)
Definition: Octree.cxx:235
sal_uInt8 * Scanline
Definition: Scanline.hxx:25
OctreeNode * pNext
Definition: Octree.hxx:33
sal_uLong nBlue
Definition: Octree.hxx:31
bool HasPalette() const
~ImpNodeCache()
Definition: Octree.cxx:53
std::vector< sal_uInt8 > mpBuffer
Definition: Octree.hxx:73
ImpNodeCache(const sal_uLong nInitSize)
Definition: Octree.cxx:39
int i
BitmapPalette maPalette
Definition: Octree.hxx:52
sal_uInt16 nPalIndex
Definition: Octree.hxx:35
std::vector< sal_uInt8 > mpMap
Definition: Octree.hxx:74
sal_uLong mnLevel
Definition: Octree.hxx:54
OctreeNode * pTree
Definition: Octree.hxx:55
std::vector< OctreeNode * > mpReduce
Definition: Octree.hxx:56
void GetPalIndex(OctreeNode *pNode)
Definition: Octree.cxx:256
BitmapColor const * mpColor
Definition: Octree.hxx:57
SAL_DLLPRIVATE void deleteOctree(OctreeNode **ppNode)
Definition: Octree.cxx:145
sal_uInt8 GetGreen() const
void ImplReleaseNode(OctreeNode *pNode)
Definition: Octree.cxx:80
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:290
const BitmapColor & GetPaletteColor(sal_uInt16 nColor) const
OctreeNode * pNextInCache
Definition: Octree.hxx:34
SAL_DLLPRIVATE void reduce()
Definition: Octree.cxx:194
sal_uInt16 GetBestPaletteIndex(const BitmapColor &rColor)
Definition: Octree.cxx:350
sal_uInt16 GetBestPaletteIndex(const BitmapColor &rColor)
Definition: Octree.cxx:281
InverseColorMap(const BitmapPalette &rPal)
Definition: Octree.cxx:292
OctreeNode * pChild[8]
Definition: Octree.hxx:32
SAL_DLLPRIVATE void add(OctreeNode **ppNode)
Definition: Octree.cxx:157
const BitmapPalette & GetPalette()
Definition: Octree.cxx:273
sal_uInt8 GetIndexFromData(const sal_uInt8 *pData, long nX) const