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/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 
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 
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 
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 
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 
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 
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 
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 
263 
265 {
267  const sal_uLong nSize = nCount * sizeof(sal_uLong);
268 
269  mpMap.resize(nCount, 0x00);
270  mpBuffer.resize(nSize, 0xff);
271 }
272 
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: */
sal_uInt8 GetIndexFromData(const sal_uInt8 *pData, tools::Long nX) const
tools::Long Height() const
sal_Int32 nIndex
Octree(const BitmapReadAccess &rReadAcc, sal_uLong nColors)
Definition: Octree.cxx:33
sal_uInt8 GetRed() const
void SetEntryCount(sal_uInt16 nCount)
sal_Int16 mnLevel
sal_uIntPtr sal_uLong
long Long
bool bLeaf
Definition: Octree.hxx:36
SAL_DLLPRIVATE void add(std::unique_ptr< OctreeNode > &rpNode, BitmapColor const &color)
Definition: Octree.cxx:82
float x
std::unique_ptr< OctreeNode > pTree
Definition: Octree.hxx:53
std::unique_ptr< OctreeNode > pChild[8]
Definition: Octree.hxx:33
void ImplCreateBuffers()
Definition: Octree.cxx:264
~Octree()
Definition: Octree.cxx:80
Scanline GetScanline(tools::Long nY) const
int nCount
sal_uInt16 mnPalIndex
Definition: Octree.hxx:55
sal_uLong mnLeafCount
Definition: Octree.hxx:51
sal_uInt8 GetBlue() const
Color color
Definition: ipict.cxx:83
sal_uLong nCount
Definition: Octree.hxx:29
sal_uInt16 GetEntryCount() const
void CreatePalette(OctreeNode *pNode)
Definition: Octree.cxx:159
sal_uInt8 * Scanline
Definition: Scanline.hxx:26
OctreeNode * pNext
Definition: Octree.hxx:34
sal_uLong nBlue
Definition: Octree.hxx:32
int i
bool HasPalette() const
std::vector< sal_uInt8 > mpBuffer
Definition: Octree.hxx:68
void GetPalIndex(const OctreeNode *pNode, BitmapColor const &color)
Definition: Octree.cxx:180
BitmapPalette maPalette
Definition: Octree.hxx:50
sal_uInt16 nPalIndex
Definition: Octree.hxx:35
tools::Long Width() const
std::vector< sal_uInt8 > mpMap
Definition: Octree.hxx:69
sal_uLong mnLevel
Definition: Octree.hxx:52
std::vector< OctreeNode * > mpReduce
Definition: Octree.hxx:54
sal_uInt8 GetGreen() const
sal_uLong nGreen
Definition: Octree.hxx:31
unsigned char sal_uInt8
sal_uLong nRed
Definition: Octree.hxx:30
BitmapColor GetPixelFromData(const sal_uInt8 *pData, tools::Long nX) const
constexpr int nColorMax
Definition: Octree.cxx:213
const BitmapColor & GetPaletteColor(sal_uInt16 nColor) const
SAL_DLLPRIVATE void reduce()
Definition: Octree.cxx:119
sal_uInt16 GetBestPaletteIndex(const BitmapColor &rColor)
Definition: Octree.cxx:273
sal_uInt16 GetBestPaletteIndex(const BitmapColor &rColor)
Definition: Octree.cxx:205
InverseColorMap(const BitmapPalette &rPal)
Definition: Octree.cxx:215
const BitmapPalette & GetPalette()
Definition: Octree.cxx:197