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