summaryrefslogtreecommitdiff
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.cxx298
1 files changed, 298 insertions, 0 deletions
diff --git a/vcl/source/bitmap/Octree.cxx b/vcl/source/bitmap/Octree.cxx
new file mode 100644
index 000000000000..64914f76385e
--- /dev/null
+++ b/vcl/source/bitmap/Octree.cxx
@@ -0,0 +1,298 @@
+/* -*- 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 <limits.h>
+
+#include <rtl/alloc.h>
+#include <vcl/bitmapaccess.hxx>
+
+#include <bitmap/Octree.hxx>
+#include <bitmap/impoctree.hxx>
+
+static const sal_uInt8 pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
+
+ImpNodeCache::ImpNodeCache( const sal_uLong nInitSize ) :
+ pActNode( nullptr )
+{
+ const sal_uLong nSize = nInitSize + 4;
+
+ for( sal_uLong i = 0; i < nSize; i++ )
+ {
+ OctreeNode* pNewNode = new OctreeNode;
+
+ pNewNode->pNextInCache = pActNode;
+ pActNode = pNewNode;
+ }
+}
+
+ImpNodeCache::~ImpNodeCache()
+{
+ while( pActNode )
+ {
+ OctreeNode* pNode = pActNode;
+
+ pActNode = pNode->pNextInCache;
+ delete pNode;
+ }
+}
+
+Octree::Octree(const BitmapReadAccess& rReadAcc, sal_uLong nColors)
+ : nLeafCount(0)
+ , nLevel(0)
+ , pTree(nullptr)
+ , pColor(nullptr)
+ , pAcc(&rReadAcc)
+ , nPalIndex(0)
+{
+ sal_uLong nMax(nColors);
+ pNodeCache.reset( new ImpNodeCache( nColors ) );
+ memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( OctreeNode* ) );
+
+ if( !!*pAcc )
+ {
+ const long nWidth = pAcc->Width();
+ const long nHeight = pAcc->Height();
+
+ if( pAcc->HasPalette() )
+ {
+ for( long nY = 0; nY < nHeight; nY++ )
+ {
+ Scanline pScanline = pAcc->GetScanline( nY );
+ for( long nX = 0; nX < nWidth; nX++ )
+ {
+ pColor = &pAcc->GetPaletteColor( pAcc->GetIndexFromData( pScanline, nX ) );
+ nLevel = 0;
+ ImplAdd( &pTree );
+
+ while( nLeafCount > nMax )
+ ImplReduce();
+ }
+ }
+ }
+ else
+ {
+ BitmapColor aColor;
+
+ pColor = &aColor;
+
+ for( long nY = 0; nY < nHeight; nY++ )
+ {
+ Scanline pScanline = pAcc->GetScanline( nY );
+ for( long nX = 0; nX < nWidth; nX++ )
+ {
+ aColor = pAcc->GetPixelFromData( pScanline, nX );
+ nLevel = 0;
+ ImplAdd( &pTree );
+
+ while( nLeafCount > nMax )
+ ImplReduce();
+ }
+ }
+ }
+ }
+}
+
+Octree::~Octree()
+{
+ ImplDeleteOctree( &pTree );
+ pNodeCache.reset();
+}
+
+void Octree::ImplDeleteOctree( OctreeNode** ppNode )
+{
+ for (OctreeNode* i : (*ppNode)->pChild)
+ {
+ if ( i )
+ ImplDeleteOctree( &i );
+ }
+
+ pNodeCache->ImplReleaseNode( *ppNode );
+ *ppNode = nullptr;
+}
+
+void Octree::ImplAdd( OctreeNode** ppNode )
+{
+ // possibly generate new nodes
+ if( !*ppNode )
+ {
+ *ppNode = pNodeCache->ImplGetFreeNode();
+ (*ppNode)->bLeaf = ( OCTREE_BITS == nLevel );
+
+ if( (*ppNode)->bLeaf )
+ nLeafCount++;
+ else
+ {
+ (*ppNode)->pNext = pReduce[ nLevel ];
+ pReduce[ nLevel ] = *ppNode;
+ }
+ }
+
+ if( (*ppNode)->bLeaf )
+ {
+ (*ppNode)->nCount++;
+ (*ppNode)->nRed += pColor->GetRed();
+ (*ppNode)->nGreen += pColor->GetGreen();
+ (*ppNode)->nBlue += pColor->GetBlue();
+ }
+ else
+ {
+ const sal_uLong nShift = 7 - nLevel;
+ const sal_uInt8 cMask = pImplMask[ nLevel ];
+ const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
+ ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
+ ( ( pColor->GetBlue() & cMask ) >> nShift );
+
+ nLevel++;
+ ImplAdd( &(*ppNode)->pChild[ nIndex ] );
+ }
+}
+
+void Octree::ImplReduce()
+{
+ sal_uLong i;
+ OctreeNode* pNode;
+ sal_uLong nRedSum = 0;
+ sal_uLong nGreenSum = 0;
+ sal_uLong nBlueSum = 0;
+ sal_uLong nChildren = 0;
+
+ for ( i = OCTREE_BITS - 1; i && !pReduce[i]; i-- ) {}
+
+ pNode = pReduce[ i ];
+ pReduce[ i ] = pNode->pNext;
+
+ for ( i = 0; i < 8; i++ )
+ {
+ if ( pNode->pChild[ i ] )
+ {
+ OctreeNode* pChild = pNode->pChild[ i ];
+
+ nRedSum += pChild->nRed;
+ nGreenSum += pChild->nGreen;
+ nBlueSum += pChild->nBlue;
+ pNode->nCount += pChild->nCount;
+
+ pNodeCache->ImplReleaseNode( pNode->pChild[ i ] );
+ pNode->pChild[ i ] = nullptr;
+ nChildren++;
+ }
+ }
+
+ pNode->bLeaf = true;
+ pNode->nRed = nRedSum;
+ pNode->nGreen = nGreenSum;
+ pNode->nBlue = nBlueSum;
+ nLeafCount -= --nChildren;
+}
+
+void Octree::CreatePalette( OctreeNode* pNode )
+{
+ if( pNode->bLeaf )
+ {
+ pNode->nPalIndex = nPalIndex;
+ aPal[ nPalIndex++ ] = BitmapColor( static_cast<sal_uInt8>( static_cast<double>(pNode->nRed) / pNode->nCount ),
+ static_cast<sal_uInt8>( static_cast<double>(pNode->nGreen) / pNode->nCount ),
+ static_cast<sal_uInt8>( static_cast<double>(pNode->nBlue) / pNode->nCount ) );
+ }
+ else for(OctreeNode* i : pNode->pChild)
+ if( i )
+ CreatePalette( i );
+
+}
+
+void Octree::GetPalIndex( OctreeNode* pNode )
+{
+ if ( pNode->bLeaf )
+ nPalIndex = pNode->nPalIndex;
+ else
+ {
+ const sal_uLong nShift = 7 - nLevel;
+ const sal_uInt8 cMask = pImplMask[ nLevel++ ];
+ const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
+ ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
+ ( ( pColor->GetBlue() & cMask ) >> nShift );
+
+ GetPalIndex( pNode->pChild[ nIndex ] );
+ }
+}
+
+InverseColorMap::InverseColorMap( const BitmapPalette& rPal )
+{
+ const int nColorMax = 1 << OCTREE_BITS;
+ const unsigned long xsqr = 1 << ( gnBits << 1 );
+ const unsigned long xsqr2 = xsqr << 1;
+ const int nColors = rPal.GetEntryCount();
+ const long x = 1 << gnBits;
+ const long x2 = x >> 1;
+ sal_uLong r, g, b;
+ long rxx, gxx, bxx;
+
+ ImplCreateBuffers( nColorMax );
+
+ for( int nIndex = 0; nIndex < nColors; nIndex++ )
+ {
+ const BitmapColor& rColor = rPal[ static_cast<sal_uInt16>(nIndex) ];
+ const long cRed = rColor.GetRed();
+ const long cGreen = rColor.GetGreen();
+ const long cBlue = rColor.GetBlue();
+
+ long rdist = cRed - x2;
+ long gdist = cGreen - x2;
+ long bdist = cBlue - x2;
+ rdist = rdist*rdist + gdist*gdist + bdist*bdist;
+
+ const long crinc = ( xsqr - ( cRed << gnBits ) ) << 1;
+ const long cginc = ( xsqr - ( cGreen << gnBits ) ) << 1;
+ const long cbinc = ( xsqr - ( cBlue << gnBits ) ) << 1;
+
+ sal_uLong* cdp = reinterpret_cast<sal_uLong*>(pBuffer.get());
+ sal_uInt8* crgbp = pMap.get();
+
+ 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<long>(*cdp) > bdist )
+ {
+ *cdp = bdist;
+ *crgbp = static_cast<sal_uInt8>(nIndex);
+ }
+ }
+ }
+ }
+}
+
+InverseColorMap::~InverseColorMap()
+{
+}
+
+void InverseColorMap::ImplCreateBuffers( const sal_uLong nMax )
+{
+ const sal_uLong nCount = nMax * nMax * nMax;
+ const sal_uLong nSize = nCount * sizeof( sal_uLong );
+
+ pMap.reset(new sal_uInt8[ nCount ]);
+ memset( pMap.get(), 0x00, nCount );
+
+ pBuffer.reset(new sal_uInt8[ nSize ]);
+ memset( pBuffer.get(), 0xff, nSize );
+}
+
+/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
generated by cgit (git 2.34.1) at 2024-07-14 17:41:48 +0000