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