xref: /aoo42x/main/vcl/source/gdi/octree.cxx (revision 87bc88d3)
19f62ea84SAndrew Rist /**************************************************************
2cdf0e10cSrcweir  *
39f62ea84SAndrew Rist  * Licensed to the Apache Software Foundation (ASF) under one
49f62ea84SAndrew Rist  * or more contributor license agreements.  See the NOTICE file
59f62ea84SAndrew Rist  * distributed with this work for additional information
69f62ea84SAndrew Rist  * regarding copyright ownership.  The ASF licenses this file
79f62ea84SAndrew Rist  * to you under the Apache License, Version 2.0 (the
89f62ea84SAndrew Rist  * "License"); you may not use this file except in compliance
99f62ea84SAndrew Rist  * with the License.  You may obtain a copy of the License at
109f62ea84SAndrew Rist  *
119f62ea84SAndrew Rist  *   http://www.apache.org/licenses/LICENSE-2.0
129f62ea84SAndrew Rist  *
139f62ea84SAndrew Rist  * Unless required by applicable law or agreed to in writing,
149f62ea84SAndrew Rist  * software distributed under the License is distributed on an
159f62ea84SAndrew Rist  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
169f62ea84SAndrew Rist  * KIND, either express or implied.  See the License for the
179f62ea84SAndrew Rist  * specific language governing permissions and limitations
189f62ea84SAndrew Rist  * under the License.
199f62ea84SAndrew Rist  *
209f62ea84SAndrew Rist  *************************************************************/
219f62ea84SAndrew Rist 
229f62ea84SAndrew Rist 
23cdf0e10cSrcweir 
24cdf0e10cSrcweir // MARKER(update_precomp.py): autogen include statement, do not remove
25cdf0e10cSrcweir #include "precompiled_vcl.hxx"
26cdf0e10cSrcweir 
27cdf0e10cSrcweir #include <limits.h>
28cdf0e10cSrcweir 
29cdf0e10cSrcweir #include <vcl/bmpacc.hxx>
30cdf0e10cSrcweir #include <vcl/octree.hxx>
31cdf0e10cSrcweir 
32cdf0e10cSrcweir #include <impoct.hxx>
33cdf0e10cSrcweir 
34cdf0e10cSrcweir // ---------
35cdf0e10cSrcweir // - pMask -
36cdf0e10cSrcweir // ---------
37cdf0e10cSrcweir 
38cdf0e10cSrcweir static sal_uInt8 pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
39cdf0e10cSrcweir 
40cdf0e10cSrcweir // -------------
41cdf0e10cSrcweir // - NodeCache -
42cdf0e10cSrcweir // -------------
43cdf0e10cSrcweir 
ImpNodeCache(const sal_uLong nInitSize)44cdf0e10cSrcweir ImpNodeCache::ImpNodeCache( const sal_uLong nInitSize ) :
45cdf0e10cSrcweir             pActNode( NULL )
46cdf0e10cSrcweir {
47cdf0e10cSrcweir     const sal_uLong nSize = nInitSize + 4;
48cdf0e10cSrcweir 
49cdf0e10cSrcweir     for( sal_uLong i = 0; i < nSize; i++ )
50cdf0e10cSrcweir     {
51cdf0e10cSrcweir         OctreeNode* pNewNode = new NODE;
52cdf0e10cSrcweir 
53cdf0e10cSrcweir         pNewNode->pNextInCache = pActNode;
54cdf0e10cSrcweir         pActNode = pNewNode;
55cdf0e10cSrcweir     }
56cdf0e10cSrcweir }
57cdf0e10cSrcweir 
58cdf0e10cSrcweir // ------------------------------------------------------------------------
59cdf0e10cSrcweir 
~ImpNodeCache()60cdf0e10cSrcweir ImpNodeCache::~ImpNodeCache()
61cdf0e10cSrcweir {
62cdf0e10cSrcweir     while( pActNode )
63cdf0e10cSrcweir     {
64cdf0e10cSrcweir         OctreeNode* pNode = pActNode;
65cdf0e10cSrcweir 
66cdf0e10cSrcweir         pActNode = pNode->pNextInCache;
67cdf0e10cSrcweir         delete pNode;
68cdf0e10cSrcweir     }
69cdf0e10cSrcweir }
70cdf0e10cSrcweir 
71cdf0e10cSrcweir // ----------
72cdf0e10cSrcweir // - Octree -
73cdf0e10cSrcweir // ----------
74cdf0e10cSrcweir 
Octree(sal_uLong nColors)75cdf0e10cSrcweir Octree::Octree( sal_uLong nColors ) :
76cdf0e10cSrcweir             nMax        ( nColors ),
77cdf0e10cSrcweir             nLeafCount  ( 0L ),
78cdf0e10cSrcweir             pTree       ( NULL ),
79cdf0e10cSrcweir             pAcc        ( NULL )
80cdf0e10cSrcweir {
81cdf0e10cSrcweir     pNodeCache = new ImpNodeCache( nColors );
82cdf0e10cSrcweir     memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) );
83cdf0e10cSrcweir }
84cdf0e10cSrcweir 
85cdf0e10cSrcweir // ------------------------------------------------------------------------
86cdf0e10cSrcweir 
Octree(const BitmapReadAccess & rReadAcc,sal_uLong nColors)87cdf0e10cSrcweir Octree::Octree( const BitmapReadAccess& rReadAcc, sal_uLong nColors ) :
88cdf0e10cSrcweir             nMax        ( nColors ),
89cdf0e10cSrcweir             nLeafCount  ( 0L ),
90cdf0e10cSrcweir             pTree       ( NULL ),
91cdf0e10cSrcweir             pAcc        ( &rReadAcc )
92cdf0e10cSrcweir {
93cdf0e10cSrcweir     pNodeCache = new ImpNodeCache( nColors );
94cdf0e10cSrcweir     memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) );
95cdf0e10cSrcweir     ImplCreateOctree();
96cdf0e10cSrcweir }
97cdf0e10cSrcweir 
98cdf0e10cSrcweir // ------------------------------------------------------------------------
99cdf0e10cSrcweir 
~Octree()100cdf0e10cSrcweir Octree::~Octree()
101cdf0e10cSrcweir {
102cdf0e10cSrcweir     ImplDeleteOctree( &pTree );
103cdf0e10cSrcweir     delete pNodeCache;
104cdf0e10cSrcweir }
105cdf0e10cSrcweir 
106cdf0e10cSrcweir // ------------------------------------------------------------------------
107cdf0e10cSrcweir 
AddColor(const BitmapColor & rColor)108cdf0e10cSrcweir void Octree::AddColor( const BitmapColor& rColor )
109cdf0e10cSrcweir {
110cdf0e10cSrcweir     pColor = &(BitmapColor&) rColor;
111cdf0e10cSrcweir     nLevel = 0L;
112cdf0e10cSrcweir     ImplAdd( &pTree );
113cdf0e10cSrcweir 
114cdf0e10cSrcweir     while( nLeafCount > nMax )
115cdf0e10cSrcweir         ImplReduce();
116cdf0e10cSrcweir }
117cdf0e10cSrcweir 
118cdf0e10cSrcweir // ------------------------------------------------------------------------
119cdf0e10cSrcweir 
ImplCreateOctree()120cdf0e10cSrcweir void Octree::ImplCreateOctree()
121cdf0e10cSrcweir {
122cdf0e10cSrcweir     if( !!*pAcc )
123cdf0e10cSrcweir     {
124cdf0e10cSrcweir         const long      nWidth = pAcc->Width();
125cdf0e10cSrcweir         const long      nHeight = pAcc->Height();
126cdf0e10cSrcweir 
127cdf0e10cSrcweir         if( pAcc->HasPalette() )
128cdf0e10cSrcweir         {
129cdf0e10cSrcweir             for( long nY = 0; nY < nHeight; nY++ )
130cdf0e10cSrcweir             {
131cdf0e10cSrcweir                 for( long nX = 0; nX < nWidth; nX++ )
132cdf0e10cSrcweir                 {
133*87bc88d3SHerbert Dürr                     pColor = &(BitmapColor&) pAcc->GetPaletteColor( pAcc->GetPixelIndex( nY, nX ) );
134cdf0e10cSrcweir                     nLevel = 0L;
135cdf0e10cSrcweir                     ImplAdd( &pTree );
136cdf0e10cSrcweir 
137cdf0e10cSrcweir                     while( nLeafCount > nMax )
138cdf0e10cSrcweir                         ImplReduce();
139cdf0e10cSrcweir                 }
140cdf0e10cSrcweir             }
141cdf0e10cSrcweir         }
142cdf0e10cSrcweir         else
143cdf0e10cSrcweir         {
144cdf0e10cSrcweir             BitmapColor aColor;
145cdf0e10cSrcweir 
146cdf0e10cSrcweir             pColor = &aColor;
147cdf0e10cSrcweir 
148cdf0e10cSrcweir             for( long nY = 0; nY < nHeight; nY++ )
149cdf0e10cSrcweir             {
150cdf0e10cSrcweir                 for( long nX = 0; nX < nWidth; nX++ )
151cdf0e10cSrcweir                 {
152cdf0e10cSrcweir                     aColor = pAcc->GetPixel( nY, nX );
153cdf0e10cSrcweir                     nLevel = 0L;
154cdf0e10cSrcweir                     ImplAdd( &pTree );
155cdf0e10cSrcweir 
156cdf0e10cSrcweir                     while( nLeafCount > nMax )
157cdf0e10cSrcweir                         ImplReduce();
158cdf0e10cSrcweir                 }
159cdf0e10cSrcweir             }
160cdf0e10cSrcweir         }
161cdf0e10cSrcweir     }
162cdf0e10cSrcweir }
163cdf0e10cSrcweir 
164cdf0e10cSrcweir // ------------------------------------------------------------------------
165cdf0e10cSrcweir 
ImplDeleteOctree(PPNODE ppNode)166cdf0e10cSrcweir void Octree::ImplDeleteOctree( PPNODE ppNode )
167cdf0e10cSrcweir {
168cdf0e10cSrcweir     for ( sal_uLong i = 0UL; i < 8UL; i++ )
169cdf0e10cSrcweir     {
170cdf0e10cSrcweir         if ( (*ppNode)->pChild[ i ] )
171cdf0e10cSrcweir             ImplDeleteOctree( &(*ppNode)->pChild[ i ] );
172cdf0e10cSrcweir     }
173cdf0e10cSrcweir 
174cdf0e10cSrcweir     pNodeCache->ImplReleaseNode( *ppNode );
175cdf0e10cSrcweir     *ppNode = NULL;
176cdf0e10cSrcweir }
177cdf0e10cSrcweir 
178cdf0e10cSrcweir // ------------------------------------------------------------------------
179cdf0e10cSrcweir 
ImplAdd(PPNODE ppNode)180cdf0e10cSrcweir void Octree::ImplAdd( PPNODE ppNode )
181cdf0e10cSrcweir {
182cdf0e10cSrcweir     // ggf. neuen Knoten erzeugen
183cdf0e10cSrcweir     if( !*ppNode )
184cdf0e10cSrcweir     {
185cdf0e10cSrcweir         *ppNode = pNodeCache->ImplGetFreeNode();
186cdf0e10cSrcweir         (*ppNode)->bLeaf = ( OCTREE_BITS == nLevel );
187cdf0e10cSrcweir 
188cdf0e10cSrcweir         if( (*ppNode)->bLeaf )
189cdf0e10cSrcweir             nLeafCount++;
190cdf0e10cSrcweir         else
191cdf0e10cSrcweir         {
192cdf0e10cSrcweir             (*ppNode)->pNext = pReduce[ nLevel ];
193cdf0e10cSrcweir             pReduce[ nLevel ] = *ppNode;
194cdf0e10cSrcweir         }
195cdf0e10cSrcweir     }
196cdf0e10cSrcweir 
197cdf0e10cSrcweir     if( (*ppNode)->bLeaf )
198cdf0e10cSrcweir     {
199cdf0e10cSrcweir         (*ppNode)->nCount++;
200cdf0e10cSrcweir         (*ppNode)->nRed += pColor->GetRed();
201cdf0e10cSrcweir         (*ppNode)->nGreen += pColor->GetGreen();
202cdf0e10cSrcweir         (*ppNode)->nBlue += pColor->GetBlue();
203cdf0e10cSrcweir     }
204cdf0e10cSrcweir     else
205cdf0e10cSrcweir     {
206cdf0e10cSrcweir         const sal_uLong nShift = 7 - nLevel;
207cdf0e10cSrcweir         const sal_uInt8  cMask = pImplMask[ nLevel ];
208cdf0e10cSrcweir         const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
209cdf0e10cSrcweir                              ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
210cdf0e10cSrcweir                              ( ( pColor->GetBlue() & cMask ) >> nShift );
211cdf0e10cSrcweir 
212cdf0e10cSrcweir         nLevel++;
213cdf0e10cSrcweir         ImplAdd( &(*ppNode)->pChild[ nIndex ] );
214cdf0e10cSrcweir     }
215cdf0e10cSrcweir }
216cdf0e10cSrcweir 
217cdf0e10cSrcweir // ------------------------------------------------------------------------
218cdf0e10cSrcweir 
ImplReduce()219cdf0e10cSrcweir void Octree::ImplReduce()
220cdf0e10cSrcweir {
221cdf0e10cSrcweir     sal_uLong   i;
222cdf0e10cSrcweir     PNODE   pNode;
223cdf0e10cSrcweir     sal_uLong   nRedSum = 0L;
224cdf0e10cSrcweir     sal_uLong   nGreenSum = 0L;
225cdf0e10cSrcweir     sal_uLong   nBlueSum = 0L;
226cdf0e10cSrcweir     sal_uLong   nChilds = 0L;
227cdf0e10cSrcweir 
228cdf0e10cSrcweir     for ( i = OCTREE_BITS - 1; i && !pReduce[i]; i-- ) {}
229cdf0e10cSrcweir 
230cdf0e10cSrcweir     pNode = pReduce[ i ];
231cdf0e10cSrcweir     pReduce[ i ] = pNode->pNext;
232cdf0e10cSrcweir 
233cdf0e10cSrcweir     for ( i = 0; i < 8; i++ )
234cdf0e10cSrcweir     {
235cdf0e10cSrcweir         if ( pNode->pChild[ i ] )
236cdf0e10cSrcweir         {
237cdf0e10cSrcweir             PNODE pChild = pNode->pChild[ i ];
238cdf0e10cSrcweir 
239cdf0e10cSrcweir             nRedSum += pChild->nRed;
240cdf0e10cSrcweir             nGreenSum += pChild->nGreen;
241cdf0e10cSrcweir             nBlueSum += pChild->nBlue;
242cdf0e10cSrcweir             pNode->nCount += pChild->nCount;
243cdf0e10cSrcweir 
244cdf0e10cSrcweir             pNodeCache->ImplReleaseNode( pNode->pChild[ i ] );
245cdf0e10cSrcweir             pNode->pChild[ i ] = NULL;
246cdf0e10cSrcweir             nChilds++;
247cdf0e10cSrcweir         }
248cdf0e10cSrcweir     }
249cdf0e10cSrcweir 
250cdf0e10cSrcweir     pNode->bLeaf = sal_True;
251cdf0e10cSrcweir     pNode->nRed = nRedSum;
252cdf0e10cSrcweir     pNode->nGreen = nGreenSum;
253cdf0e10cSrcweir     pNode->nBlue = nBlueSum;
254cdf0e10cSrcweir     nLeafCount -= --nChilds;
255cdf0e10cSrcweir }
256cdf0e10cSrcweir 
257cdf0e10cSrcweir // ------------------------------------------------------------------------
258cdf0e10cSrcweir 
CreatePalette(PNODE pNode)259cdf0e10cSrcweir void Octree::CreatePalette( PNODE pNode )
260cdf0e10cSrcweir {
261cdf0e10cSrcweir     if( pNode->bLeaf )
262cdf0e10cSrcweir     {
263cdf0e10cSrcweir         pNode->nPalIndex = nPalIndex;
264cdf0e10cSrcweir         aPal[ nPalIndex++ ] = BitmapColor( (sal_uInt8) ( (double) pNode->nRed / pNode->nCount ),
265cdf0e10cSrcweir                                            (sal_uInt8) ( (double) pNode->nGreen / pNode->nCount ),
266cdf0e10cSrcweir                                            (sal_uInt8) ( (double) pNode->nBlue / pNode->nCount ) );
267cdf0e10cSrcweir     }
268cdf0e10cSrcweir     else for( sal_uLong i = 0UL; i < 8UL; i++ )
269cdf0e10cSrcweir         if( pNode->pChild[ i ] )
270cdf0e10cSrcweir             CreatePalette( pNode->pChild[ i ] );
271cdf0e10cSrcweir 
272cdf0e10cSrcweir }
273cdf0e10cSrcweir 
274cdf0e10cSrcweir // ------------------------------------------------------------------------
275cdf0e10cSrcweir 
GetPalIndex(PNODE pNode)276cdf0e10cSrcweir void Octree::GetPalIndex( PNODE pNode )
277cdf0e10cSrcweir {
278cdf0e10cSrcweir     if ( pNode->bLeaf )
279cdf0e10cSrcweir         nPalIndex = pNode->nPalIndex;
280cdf0e10cSrcweir     else
281cdf0e10cSrcweir     {
282cdf0e10cSrcweir         const sal_uLong nShift = 7 - nLevel;
283cdf0e10cSrcweir         const sal_uInt8  cMask = pImplMask[ nLevel++ ];
284cdf0e10cSrcweir         const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
285cdf0e10cSrcweir                              ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
286cdf0e10cSrcweir                              ( ( pColor->GetBlue() & cMask ) >> nShift );
287cdf0e10cSrcweir 
288cdf0e10cSrcweir         GetPalIndex( pNode->pChild[ nIndex ] );
289cdf0e10cSrcweir     }
290cdf0e10cSrcweir }
291cdf0e10cSrcweir 
292cdf0e10cSrcweir // -------------------
293cdf0e10cSrcweir // - InverseColorMap -
294cdf0e10cSrcweir // -------------------
295cdf0e10cSrcweir 
InverseColorMap(const BitmapPalette & rPal)296cdf0e10cSrcweir InverseColorMap::InverseColorMap( const BitmapPalette& rPal ) :
297cdf0e10cSrcweir             nBits( 8 - OCTREE_BITS )
298cdf0e10cSrcweir {
299cdf0e10cSrcweir     sal_uLong*			cdp;
300cdf0e10cSrcweir     sal_uInt8*           crgbp;
301cdf0e10cSrcweir     const sal_uLong     nColorMax = 1 << OCTREE_BITS;
302cdf0e10cSrcweir     const sal_uLong     xsqr = 1 << ( nBits << 1 );
303cdf0e10cSrcweir     const sal_uLong     xsqr2 = xsqr << 1;
304cdf0e10cSrcweir     const sal_uLong     nColors = rPal.GetEntryCount();
305cdf0e10cSrcweir     const long      x = 1L << nBits;
306cdf0e10cSrcweir     const long      x2 = x >> 1L;
307cdf0e10cSrcweir     sal_uLong           r, g, b;
308cdf0e10cSrcweir     long            rxx, gxx, bxx;
309cdf0e10cSrcweir     long            rdist, gdist, bdist;
310cdf0e10cSrcweir     long            crinc, cginc, cbinc;
311cdf0e10cSrcweir 
312cdf0e10cSrcweir     ImplCreateBuffers( nColorMax );
313cdf0e10cSrcweir 
314cdf0e10cSrcweir     for( sal_uLong nIndex = 0; nIndex < nColors; nIndex++ )
315cdf0e10cSrcweir     {
316cdf0e10cSrcweir         const BitmapColor&  rColor = rPal[ (sal_uInt16) nIndex ];
317cdf0e10cSrcweir         const sal_uInt8			cRed = rColor.GetRed();
318cdf0e10cSrcweir         const sal_uInt8			cGreen = rColor.GetGreen();
319cdf0e10cSrcweir         const sal_uInt8			cBlue = rColor.GetBlue();
320cdf0e10cSrcweir 
321cdf0e10cSrcweir         rdist = cRed - x2;
322cdf0e10cSrcweir         gdist = cGreen - x2;
323cdf0e10cSrcweir         bdist = cBlue - x2;
324cdf0e10cSrcweir         rdist = rdist*rdist + gdist*gdist + bdist*bdist;
325cdf0e10cSrcweir 
326cdf0e10cSrcweir         crinc = ( xsqr - ( cRed << nBits ) ) << 1L;
327cdf0e10cSrcweir         cginc = ( xsqr - ( cGreen << nBits ) ) << 1L;
328cdf0e10cSrcweir         cbinc = ( xsqr - ( cBlue << nBits ) ) << 1L;
329cdf0e10cSrcweir 
330cdf0e10cSrcweir         cdp = (sal_uLong*) pBuffer;
331cdf0e10cSrcweir         crgbp = pMap;
332cdf0e10cSrcweir 
333cdf0e10cSrcweir         for( r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2 )
334cdf0e10cSrcweir         {
335cdf0e10cSrcweir             for( g = 0, gdist = rdist, gxx = cginc; g < nColorMax;  gdist += gxx, g++, gxx += xsqr2 )
336cdf0e10cSrcweir             {
337cdf0e10cSrcweir                 for( b = 0, bdist = gdist, bxx = cbinc; b < nColorMax; bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2 )
338cdf0e10cSrcweir                     if ( !nIndex || ( (long) *cdp ) > bdist )
339cdf0e10cSrcweir                     {
340cdf0e10cSrcweir                         *cdp = bdist;
341cdf0e10cSrcweir                         *crgbp = (sal_uInt8) nIndex;
342cdf0e10cSrcweir                     }
343cdf0e10cSrcweir             }
344cdf0e10cSrcweir         }
345cdf0e10cSrcweir     }
346cdf0e10cSrcweir }
347cdf0e10cSrcweir 
348cdf0e10cSrcweir // ------------------------------------------------------------------------
349cdf0e10cSrcweir 
~InverseColorMap()350cdf0e10cSrcweir InverseColorMap::~InverseColorMap()
351cdf0e10cSrcweir {
352cdf0e10cSrcweir     rtl_freeMemory( pBuffer );
353cdf0e10cSrcweir     rtl_freeMemory( pMap );
354cdf0e10cSrcweir }
355cdf0e10cSrcweir 
356cdf0e10cSrcweir // ------------------------------------------------------------------------
357cdf0e10cSrcweir 
ImplCreateBuffers(const sal_uLong nMax)358cdf0e10cSrcweir void InverseColorMap::ImplCreateBuffers( const sal_uLong nMax )
359cdf0e10cSrcweir {
360cdf0e10cSrcweir     const sal_uLong nCount = nMax * nMax * nMax;
361cdf0e10cSrcweir     const sal_uLong nSize = nCount * sizeof( sal_uLong );
362cdf0e10cSrcweir 
363cdf0e10cSrcweir     pMap = (sal_uInt8*) rtl_allocateMemory( nCount );
364cdf0e10cSrcweir     memset( pMap, 0x00, nCount );
365cdf0e10cSrcweir 
366cdf0e10cSrcweir     pBuffer = (sal_uInt8*) rtl_allocateMemory( nSize );
367cdf0e10cSrcweir     memset( pBuffer, 0xff, nSize );
368cdf0e10cSrcweir }
369