summaryrefslogtreecommitdiffstats
path: root/vcl/source/bitmap/Octree.cxx
diff options
context:
space:
mode:
Diffstat (limited to 'vcl/source/bitmap/Octree.cxx')
-rw-r--r--vcl/source/bitmap/Octree.cxx280
1 files changed, 280 insertions, 0 deletions
diff --git a/vcl/source/bitmap/Octree.cxx b/vcl/source/bitmap/Octree.cxx
new file mode 100644
index 000000000..98ad8c9fc
--- /dev/null
+++ b/vcl/source/bitmap/Octree.cxx
@@ -0,0 +1,280 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
+/*
+ * This file is part of the LibreOffice project.
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/.
+ *
+ * This file incorporates work covered by the following license notice:
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed
+ * with this work for additional information regarding copyright
+ * ownership. The ASF licenses this file to you under the Apache
+ * License, Version 2.0 (the "License"); you may not use this file
+ * except in compliance with the License. You may obtain a copy of
+ * the License at http://www.apache.org/licenses/LICENSE-2.0 .
+ */
+
+#include <vcl/BitmapReadAccess.hxx>
+
+#include <bitmap/Octree.hxx>
+
+namespace
+{
+constexpr size_t OCTREE_BITS = 5;
+constexpr size_t OCTREE_BITS_1 = 10;
+
+constexpr sal_uLong gnBits = 8 - OCTREE_BITS;
+
+} // end anonymous namespace
+
+Octree::Octree(const BitmapReadAccess& rReadAcc, sal_uLong nColors)
+ : mnLeafCount(0)
+ , mnLevel(0)
+ , mpReduce(OCTREE_BITS + 1, nullptr)
+ , mnPalIndex(0)
+{
+ const BitmapReadAccess* pAccess = &rReadAcc;
+ sal_uLong nMax(nColors);
+
+ if (!*pAccess)
+ return;
+
+ const tools::Long nWidth = pAccess->Width();
+ const tools::Long nHeight = pAccess->Height();
+
+ if (pAccess->HasPalette())
+ {
+ for (tools::Long nY = 0; nY < nHeight; nY++)
+ {
+ Scanline pScanline = pAccess->GetScanline(nY);
+ for (tools::Long nX = 0; nX < nWidth; nX++)
+ {
+ mnLevel = 0;
+ add(pTree, pAccess->GetPaletteColor(pAccess->GetIndexFromData(pScanline, nX)));
+
+ while (mnLeafCount > nMax)
+ reduce();
+ }
+ }
+ }
+ else
+ {
+ for (tools::Long nY = 0; nY < nHeight; nY++)
+ {
+ Scanline pScanline = pAccess->GetScanline(nY);
+ for (tools::Long nX = 0; nX < nWidth; nX++)
+ {
+ mnLevel = 0;
+ add(pTree, pAccess->GetPixelFromData(pScanline, nX));
+
+ while (mnLeafCount > nMax)
+ reduce();
+ }
+ }
+ }
+}
+
+Octree::~Octree() {}
+
+void Octree::add(std::unique_ptr<OctreeNode>& rpNode, BitmapColor const& color)
+{
+ // possibly generate new nodes
+ if (!rpNode)
+ {
+ rpNode.reset(new OctreeNode);
+ rpNode->bLeaf = (OCTREE_BITS == mnLevel);
+
+ if (rpNode->bLeaf)
+ mnLeafCount++;
+ else
+ {
+ rpNode->pNext = mpReduce[mnLevel];
+ mpReduce[mnLevel] = rpNode.get();
+ }
+ }
+
+ if (rpNode->bLeaf)
+ {
+ rpNode->nCount++;
+ rpNode->nRed += color.GetRed();
+ rpNode->nGreen += color.GetGreen();
+ rpNode->nBlue += color.GetBlue();
+ }
+ else
+ {
+ const sal_uLong nShift = 7 - mnLevel;
+ const sal_uInt8 cMask = 0x80 >> mnLevel;
+ const sal_uLong nIndex = (((color.GetRed() & cMask) >> nShift) << 2)
+ | (((color.GetGreen() & cMask) >> nShift) << 1)
+ | ((color.GetBlue() & cMask) >> nShift);
+
+ mnLevel++;
+ add(rpNode->pChild[nIndex], color);
+ }
+}
+
+void Octree::reduce()
+{
+ OctreeNode* pNode;
+ sal_uLong nRedSum = 0;
+ sal_uLong nGreenSum = 0;
+ sal_uLong nBlueSum = 0;
+ sal_uLong nChildren = 0;
+
+ sal_uLong nIndex = OCTREE_BITS - 1;
+ while (nIndex > 0 && !mpReduce[nIndex])
+ {
+ nIndex--;
+ }
+
+ pNode = mpReduce[nIndex];
+ mpReduce[nIndex] = pNode->pNext;
+
+ for (unsigned int i = 0; i < 8; i++)
+ {
+ if (pNode->pChild[i])
+ {
+ OctreeNode* pChild = pNode->pChild[i].get();
+
+ nRedSum += pChild->nRed;
+ nGreenSum += pChild->nGreen;
+ nBlueSum += pChild->nBlue;
+ pNode->nCount += pChild->nCount;
+
+ pNode->pChild[i].reset();
+ nChildren++;
+ }
+ }
+
+ pNode->bLeaf = true;
+ pNode->nRed = nRedSum;
+ pNode->nGreen = nGreenSum;
+ pNode->nBlue = nBlueSum;
+ mnLeafCount -= --nChildren;
+}
+
+void Octree::CreatePalette(OctreeNode* pNode)
+{
+ if (pNode->bLeaf)
+ {
+ pNode->nPalIndex = mnPalIndex;
+ maPalette[mnPalIndex++] = BitmapColor(sal_uInt8(double(pNode->nRed) / pNode->nCount),
+ sal_uInt8(double(pNode->nGreen) / pNode->nCount),
+ sal_uInt8(double(pNode->nBlue) / pNode->nCount));
+ }
+ else
+ {
+ for (auto const& i : pNode->pChild)
+ {
+ if (i)
+ {
+ CreatePalette(i.get());
+ }
+ }
+ }
+}
+
+void Octree::GetPalIndex(const OctreeNode* pNode, BitmapColor const& color)
+{
+ if (pNode->bLeaf)
+ mnPalIndex = pNode->nPalIndex;
+ else
+ {
+ const sal_uLong nShift = 7 - mnLevel;
+ const sal_uInt8 cMask = 0x80 >> mnLevel;
+ mnLevel++;
+ const sal_uLong nIndex = (((color.GetRed() & cMask) >> nShift) << 2)
+ | (((color.GetGreen() & cMask) >> nShift) << 1)
+ | ((color.GetBlue() & cMask) >> nShift);
+
+ GetPalIndex(pNode->pChild[nIndex].get(), color);
+ }
+}
+
+const BitmapPalette& Octree::GetPalette()
+{
+ maPalette.SetEntryCount(sal_uInt16(mnLeafCount));
+ mnPalIndex = 0;
+ CreatePalette(pTree.get());
+ return maPalette;
+}
+
+sal_uInt16 Octree::GetBestPaletteIndex(const BitmapColor& rColor)
+{
+ mnPalIndex = 65535;
+ mnLevel = 0;
+ GetPalIndex(pTree.get(), rColor);
+ return mnPalIndex;
+}
+
+constexpr int nColorMax = 1 << OCTREE_BITS;
+
+InverseColorMap::InverseColorMap(const BitmapPalette& rPal)
+{
+ const unsigned long xsqr = 1 << (gnBits << 1);
+ const unsigned long xsqr2 = xsqr << 1;
+ const int nColors = rPal.GetEntryCount();
+ const tools::Long x = 1 << gnBits;
+ const tools::Long x2 = x >> 1;
+ sal_uLong r, g, b;
+ tools::Long rxx, gxx, bxx;
+
+ ImplCreateBuffers();
+
+ for (int nIndex = 0; nIndex < nColors; nIndex++)
+ {
+ const BitmapColor& rColor = rPal[static_cast<sal_uInt16>(nIndex)];
+ const tools::Long cRed = rColor.GetRed();
+ const tools::Long cGreen = rColor.GetGreen();
+ const tools::Long cBlue = rColor.GetBlue();
+
+ tools::Long rdist = cRed - x2;
+ tools::Long gdist = cGreen - x2;
+ tools::Long bdist = cBlue - x2;
+ rdist = rdist * rdist + gdist * gdist + bdist * bdist;
+
+ const tools::Long crinc = (xsqr - (cRed << gnBits)) << 1;
+ const tools::Long cginc = (xsqr - (cGreen << gnBits)) << 1;
+ const tools::Long cbinc = (xsqr - (cBlue << gnBits)) << 1;
+
+ sal_uLong* cdp = reinterpret_cast<sal_uLong*>(mpBuffer.data());
+ sal_uInt8* crgbp = mpMap.data();
+
+ for (r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2)
+ {
+ for (g = 0, gdist = rdist, gxx = cginc; g < nColorMax; gdist += gxx, g++, gxx += xsqr2)
+ {
+ for (b = 0, bdist = gdist, bxx = cbinc; b < nColorMax;
+ bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2)
+ if (!nIndex || static_cast<tools::Long>(*cdp) > bdist)
+ {
+ *cdp = bdist;
+ *crgbp = static_cast<sal_uInt8>(nIndex);
+ }
+ }
+ }
+ }
+}
+
+InverseColorMap::~InverseColorMap() {}
+
+void InverseColorMap::ImplCreateBuffers()
+{
+ const sal_uLong nCount = nColorMax * nColorMax * nColorMax;
+ const sal_uLong nSize = nCount * sizeof(sal_uLong);
+
+ mpMap.resize(nCount, 0x00);
+ mpBuffer.resize(nSize, 0xff);
+}
+
+sal_uInt16 InverseColorMap::GetBestPaletteIndex(const BitmapColor& rColor)
+{
+ return mpMap[((static_cast<sal_uLong>(rColor.GetRed()) >> gnBits) << OCTREE_BITS_1)
+ | ((static_cast<sal_uLong>(rColor.GetGreen()) >> gnBits) << OCTREE_BITS)
+ | (static_cast<sal_uLong>(rColor.GetBlue()) >> gnBits)];
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-29 00:37:04 +0000