Line data Source code
1 : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : /*
3 : * This file is part of the LibreOffice project.
4 : *
5 : * This Source Code Form is subject to the terms of the Mozilla Public
6 : * License, v. 2.0. If a copy of the MPL was not distributed with this
7 : * file, You can obtain one at http://mozilla.org/MPL/2.0/.
8 : *
9 : * This file incorporates work covered by the following license notice:
10 : *
11 : * Licensed to the Apache Software Foundation (ASF) under one or more
12 : * contributor license agreements. See the NOTICE file distributed
13 : * with this work for additional information regarding copyright
14 : * ownership. The ASF licenses this file to you under the Apache
15 : * License, Version 2.0 (the "License"); you may not use this file
16 : * except in compliance with the License. You may obtain a copy of
17 : * the License at http://www.apache.org/licenses/LICENSE-2.0 .
18 : */
19 :
20 :
21 : #include <limits.h>
22 :
23 : #include <vcl/bmpacc.hxx>
24 : #include <vcl/octree.hxx>
25 :
26 : #include <impoct.hxx>
27 :
28 : // ---------
29 : // - pMask -
30 : // ---------
31 :
32 : static const sal_uInt8 pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
33 :
34 : // -------------
35 : // - NodeCache -
36 : // -------------
37 :
38 469 : ImpNodeCache::ImpNodeCache( const sal_uLong nInitSize ) :
39 469 : pActNode( NULL )
40 : {
41 469 : const sal_uLong nSize = nInitSize + 4;
42 :
43 122409 : for( sal_uLong i = 0; i < nSize; i++ )
44 : {
45 121940 : OctreeNode* pNewNode = new NODE;
46 :
47 121940 : pNewNode->pNextInCache = pActNode;
48 121940 : pActNode = pNewNode;
49 : }
50 469 : }
51 :
52 : // ------------------------------------------------------------------------
53 :
54 469 : ImpNodeCache::~ImpNodeCache()
55 : {
56 166452 : while( pActNode )
57 : {
58 165514 : OctreeNode* pNode = pActNode;
59 :
60 165514 : pActNode = pNode->pNextInCache;
61 165514 : delete pNode;
62 : }
63 469 : }
64 :
65 : // ----------
66 : // - Octree -
67 : // ----------
68 :
69 469 : Octree::Octree( const BitmapReadAccess& rReadAcc, sal_uLong nColors ) :
70 : nMax ( nColors ),
71 : nLeafCount ( 0L ),
72 : pTree ( NULL ),
73 469 : pAcc ( &rReadAcc )
74 : {
75 469 : pNodeCache = new ImpNodeCache( nColors );
76 469 : memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) );
77 469 : ImplCreateOctree();
78 469 : }
79 :
80 : // ------------------------------------------------------------------------
81 :
82 938 : Octree::~Octree()
83 : {
84 469 : ImplDeleteOctree( &pTree );
85 469 : delete pNodeCache;
86 469 : }
87 :
88 : // ------------------------------------------------------------------------
89 :
90 469 : void Octree::ImplCreateOctree()
91 : {
92 469 : if( !!*pAcc )
93 : {
94 469 : const long nWidth = pAcc->Width();
95 469 : const long nHeight = pAcc->Height();
96 :
97 469 : if( pAcc->HasPalette() )
98 : {
99 0 : for( long nY = 0; nY < nHeight; nY++ )
100 : {
101 0 : for( long nX = 0; nX < nWidth; nX++ )
102 : {
103 0 : pColor = &(BitmapColor&) pAcc->GetPaletteColor( pAcc->GetPixelIndex( nY, nX ) );
104 0 : nLevel = 0L;
105 0 : ImplAdd( &pTree );
106 :
107 0 : while( nLeafCount > nMax )
108 0 : ImplReduce();
109 : }
110 : }
111 : }
112 : else
113 : {
114 469 : BitmapColor aColor;
115 :
116 469 : pColor = &aColor;
117 :
118 32879 : for( long nY = 0; nY < nHeight; nY++ )
119 : {
120 2561999 : for( long nX = 0; nX < nWidth; nX++ )
121 : {
122 2529589 : aColor = pAcc->GetPixel( nY, nX );
123 2529589 : nLevel = 0L;
124 2529589 : ImplAdd( &pTree );
125 :
126 5076601 : while( nLeafCount > nMax )
127 17423 : ImplReduce();
128 : }
129 469 : }
130 : }
131 : }
132 469 : }
133 :
134 : // ------------------------------------------------------------------------
135 :
136 138708 : void Octree::ImplDeleteOctree( PPNODE ppNode )
137 : {
138 1248372 : for ( sal_uLong i = 0UL; i < 8UL; i++ )
139 : {
140 1109664 : if ( (*ppNode)->pChild[ i ] )
141 138239 : ImplDeleteOctree( &(*ppNode)->pChild[ i ] );
142 : }
143 :
144 138708 : pNodeCache->ImplReleaseNode( *ppNode );
145 138708 : *ppNode = NULL;
146 138708 : }
147 :
148 : // ------------------------------------------------------------------------
149 :
150 15073393 : void Octree::ImplAdd( PPNODE ppNode )
151 : {
152 : // ggf. neuen Knoten erzeugen
153 15073393 : if( !*ppNode )
154 : {
155 166486 : *ppNode = pNodeCache->ImplGetFreeNode();
156 166486 : (*ppNode)->bLeaf = ( OCTREE_BITS == nLevel );
157 :
158 166486 : if( (*ppNode)->bLeaf )
159 94680 : nLeafCount++;
160 : else
161 : {
162 71806 : (*ppNode)->pNext = pReduce[ nLevel ];
163 71806 : pReduce[ nLevel ] = *ppNode;
164 : }
165 : }
166 :
167 15073393 : if( (*ppNode)->bLeaf )
168 : {
169 2529589 : (*ppNode)->nCount++;
170 2529589 : (*ppNode)->nRed += pColor->GetRed();
171 2529589 : (*ppNode)->nGreen += pColor->GetGreen();
172 2529589 : (*ppNode)->nBlue += pColor->GetBlue();
173 : }
174 : else
175 : {
176 12543804 : const sal_uLong nShift = 7 - nLevel;
177 12543804 : const sal_uInt8 cMask = pImplMask[ nLevel ];
178 25087608 : const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
179 25087608 : ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
180 25087608 : ( ( pColor->GetBlue() & cMask ) >> nShift );
181 :
182 12543804 : nLevel++;
183 12543804 : ImplAdd( &(*ppNode)->pChild[ nIndex ] );
184 : }
185 15073393 : }
186 :
187 : // ------------------------------------------------------------------------
188 :
189 17423 : void Octree::ImplReduce()
190 : {
191 : sal_uLong i;
192 : PNODE pNode;
193 17423 : sal_uLong nRedSum = 0L;
194 17423 : sal_uLong nGreenSum = 0L;
195 17423 : sal_uLong nBlueSum = 0L;
196 17423 : sal_uLong nChildren = 0L;
197 :
198 17423 : for ( i = OCTREE_BITS - 1; i && !pReduce[i]; i-- ) {}
199 :
200 17423 : pNode = pReduce[ i ];
201 17423 : pReduce[ i ] = pNode->pNext;
202 :
203 156807 : for ( i = 0; i < 8; i++ )
204 : {
205 139384 : if ( pNode->pChild[ i ] )
206 : {
207 27778 : PNODE pChild = pNode->pChild[ i ];
208 :
209 27778 : nRedSum += pChild->nRed;
210 27778 : nGreenSum += pChild->nGreen;
211 27778 : nBlueSum += pChild->nBlue;
212 27778 : pNode->nCount += pChild->nCount;
213 :
214 27778 : pNodeCache->ImplReleaseNode( pNode->pChild[ i ] );
215 27778 : pNode->pChild[ i ] = NULL;
216 27778 : nChildren++;
217 : }
218 : }
219 :
220 17423 : pNode->bLeaf = sal_True;
221 17423 : pNode->nRed = nRedSum;
222 17423 : pNode->nGreen = nGreenSum;
223 17423 : pNode->nBlue = nBlueSum;
224 17423 : nLeafCount -= --nChildren;
225 17423 : }
226 :
227 : // ------------------------------------------------------------------------
228 :
229 138708 : void Octree::CreatePalette( PNODE pNode )
230 : {
231 138708 : if( pNode->bLeaf )
232 : {
233 84325 : pNode->nPalIndex = nPalIndex;
234 252975 : aPal[ nPalIndex++ ] = BitmapColor( (sal_uInt8) ( (double) pNode->nRed / pNode->nCount ),
235 84325 : (sal_uInt8) ( (double) pNode->nGreen / pNode->nCount ),
236 168650 : (sal_uInt8) ( (double) pNode->nBlue / pNode->nCount ) );
237 : }
238 489447 : else for( sal_uLong i = 0UL; i < 8UL; i++ )
239 435064 : if( pNode->pChild[ i ] )
240 138239 : CreatePalette( pNode->pChild[ i ] );
241 :
242 138708 : }
243 :
244 : // ------------------------------------------------------------------------
245 :
246 0 : void Octree::GetPalIndex( PNODE pNode )
247 : {
248 0 : if ( pNode->bLeaf )
249 0 : nPalIndex = pNode->nPalIndex;
250 : else
251 : {
252 0 : const sal_uLong nShift = 7 - nLevel;
253 0 : const sal_uInt8 cMask = pImplMask[ nLevel++ ];
254 0 : const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
255 0 : ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
256 0 : ( ( pColor->GetBlue() & cMask ) >> nShift );
257 :
258 0 : GetPalIndex( pNode->pChild[ nIndex ] );
259 : }
260 0 : }
261 :
262 : // -------------------
263 : // - InverseColorMap -
264 : // -------------------
265 :
266 469 : InverseColorMap::InverseColorMap( const BitmapPalette& rPal ) :
267 469 : nBits( 8 - OCTREE_BITS )
268 : {
269 : sal_uLong* cdp;
270 : sal_uInt8* crgbp;
271 469 : const sal_uLong nColorMax = 1 << OCTREE_BITS;
272 469 : const sal_uLong xsqr = 1 << ( nBits << 1 );
273 469 : const sal_uLong xsqr2 = xsqr << 1;
274 469 : const sal_uLong nColors = rPal.GetEntryCount();
275 469 : const long x = 1L << nBits;
276 469 : const long x2 = x >> 1L;
277 : sal_uLong r, g, b;
278 : long rxx, gxx, bxx;
279 : long rdist, gdist, bdist;
280 : long crinc, cginc, cbinc;
281 :
282 469 : ImplCreateBuffers( nColorMax );
283 :
284 84794 : for( sal_uLong nIndex = 0; nIndex < nColors; nIndex++ )
285 : {
286 84325 : const BitmapColor& rColor = rPal[ (sal_uInt16) nIndex ];
287 84325 : const sal_uInt8 cRed = rColor.GetRed();
288 84325 : const sal_uInt8 cGreen = rColor.GetGreen();
289 84325 : const sal_uInt8 cBlue = rColor.GetBlue();
290 :
291 84325 : rdist = cRed - x2;
292 84325 : gdist = cGreen - x2;
293 84325 : bdist = cBlue - x2;
294 84325 : rdist = rdist*rdist + gdist*gdist + bdist*bdist;
295 :
296 84325 : crinc = ( xsqr - ( cRed << nBits ) ) << 1L;
297 84325 : cginc = ( xsqr - ( cGreen << nBits ) ) << 1L;
298 84325 : cbinc = ( xsqr - ( cBlue << nBits ) ) << 1L;
299 :
300 84325 : cdp = (sal_uLong*) pBuffer;
301 84325 : crgbp = pMap;
302 :
303 2782725 : for( r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2 )
304 : {
305 89047200 : for( g = 0, gdist = rdist, gxx = cginc; g < nColorMax; gdist += gxx, g++, gxx += xsqr2 )
306 : {
307 2849510400 : for( b = 0, bdist = gdist, bxx = cbinc; b < nColorMax; bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2 )
308 2763161600 : if ( !nIndex || ( (long) *cdp ) > bdist )
309 : {
310 370683195 : *cdp = bdist;
311 370683195 : *crgbp = (sal_uInt8) nIndex;
312 : }
313 : }
314 : }
315 : }
316 469 : }
317 :
318 : // ------------------------------------------------------------------------
319 :
320 469 : InverseColorMap::~InverseColorMap()
321 : {
322 469 : rtl_freeMemory( pBuffer );
323 469 : rtl_freeMemory( pMap );
324 469 : }
325 :
326 : // ------------------------------------------------------------------------
327 :
328 469 : void InverseColorMap::ImplCreateBuffers( const sal_uLong nMax )
329 : {
330 469 : const sal_uLong nCount = nMax * nMax * nMax;
331 469 : const sal_uLong nSize = nCount * sizeof( sal_uLong );
332 :
333 469 : pMap = (sal_uInt8*) rtl_allocateMemory( nCount );
334 469 : memset( pMap, 0x00, nCount );
335 :
336 469 : pBuffer = (sal_uInt8*) rtl_allocateMemory( nSize );
337 469 : memset( pBuffer, 0xff, nSize );
338 934 : }
339 :
340 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
