Branch data Line data Source code
1 : : /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*- */
2 : : /*************************************************************************
3 : : *
4 : : * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 : : *
6 : : * Copyright 2000, 2010 Oracle and/or its affiliates.
7 : : *
8 : : * OpenOffice.org - a multi-platform office productivity suite
9 : : *
10 : : * This file is part of OpenOffice.org.
11 : : *
12 : : * OpenOffice.org is free software: you can redistribute it and/or modify
13 : : * it under the terms of the GNU Lesser General Public License version 3
14 : : * only, as published by the Free Software Foundation.
15 : : *
16 : : * OpenOffice.org is distributed in the hope that it will be useful,
17 : : * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 : : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 : : * GNU Lesser General Public License version 3 for more details
20 : : * (a copy is included in the LICENSE file that accompanied this code).
21 : : *
22 : : * You should have received a copy of the GNU Lesser General Public License
23 : : * version 3 along with OpenOffice.org. If not, see
24 : : * <http://www.openoffice.org/license.html>
25 : : * for a copy of the LGPLv3 License.
26 : : *
27 : : ************************************************************************/
28 : :
29 : :
30 : : #include <limits.h>
31 : :
32 : : #include <vcl/bmpacc.hxx>
33 : : #include <vcl/octree.hxx>
34 : :
35 : : #include <impoct.hxx>
36 : :
37 : : // ---------
38 : : // - pMask -
39 : : // ---------
40 : :
41 : : static sal_uInt8 pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
42 : :
43 : : // -------------
44 : : // - NodeCache -
45 : : // -------------
46 : :
47 : 0 : ImpNodeCache::ImpNodeCache( const sal_uLong nInitSize ) :
48 : 0 : pActNode( NULL )
49 : : {
50 : 0 : const sal_uLong nSize = nInitSize + 4;
51 : :
52 [ # # ]: 0 : for( sal_uLong i = 0; i < nSize; i++ )
53 : : {
54 : 0 : OctreeNode* pNewNode = new NODE;
55 : :
56 : 0 : pNewNode->pNextInCache = pActNode;
57 : 0 : pActNode = pNewNode;
58 : : }
59 : 0 : }
60 : :
61 : : // ------------------------------------------------------------------------
62 : :
63 : 0 : ImpNodeCache::~ImpNodeCache()
64 : : {
65 [ # # ]: 0 : while( pActNode )
66 : : {
67 : 0 : OctreeNode* pNode = pActNode;
68 : :
69 : 0 : pActNode = pNode->pNextInCache;
70 : 0 : delete pNode;
71 : : }
72 : 0 : }
73 : :
74 : : // ----------
75 : : // - Octree -
76 : : // ----------
77 : :
78 : 0 : Octree::Octree( const BitmapReadAccess& rReadAcc, sal_uLong nColors ) :
79 : : nMax ( nColors ),
80 : : nLeafCount ( 0L ),
81 : : pTree ( NULL ),
82 : 0 : pAcc ( &rReadAcc )
83 : : {
84 [ # # ][ # # ]: 0 : pNodeCache = new ImpNodeCache( nColors );
85 : 0 : memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) );
86 [ # # ]: 0 : ImplCreateOctree();
87 : 0 : }
88 : :
89 : : // ------------------------------------------------------------------------
90 : :
91 : 0 : Octree::~Octree()
92 : : {
93 [ # # ]: 0 : ImplDeleteOctree( &pTree );
94 [ # # ]: 0 : delete pNodeCache;
95 : 0 : }
96 : :
97 : : // ------------------------------------------------------------------------
98 : :
99 : 0 : void Octree::ImplCreateOctree()
100 : : {
101 [ # # ]: 0 : if( !!*pAcc )
102 : : {
103 : 0 : const long nWidth = pAcc->Width();
104 : 0 : const long nHeight = pAcc->Height();
105 : :
106 [ # # ]: 0 : if( pAcc->HasPalette() )
107 : : {
108 [ # # ]: 0 : for( long nY = 0; nY < nHeight; nY++ )
109 : : {
110 [ # # ]: 0 : for( long nX = 0; nX < nWidth; nX++ )
111 : : {
112 : 0 : pColor = &(BitmapColor&) pAcc->GetPaletteColor( pAcc->GetPixel( nY, nX ) );
113 : 0 : nLevel = 0L;
114 : 0 : ImplAdd( &pTree );
115 : :
116 [ # # ]: 0 : while( nLeafCount > nMax )
117 : 0 : ImplReduce();
118 : : }
119 : : }
120 : : }
121 : : else
122 : : {
123 : 0 : BitmapColor aColor;
124 : :
125 : 0 : pColor = &aColor;
126 : :
127 [ # # ]: 0 : for( long nY = 0; nY < nHeight; nY++ )
128 : : {
129 [ # # ]: 0 : for( long nX = 0; nX < nWidth; nX++ )
130 : : {
131 [ # # ]: 0 : aColor = pAcc->GetPixel( nY, nX );
132 : 0 : nLevel = 0L;
133 [ # # ]: 0 : ImplAdd( &pTree );
134 : :
135 [ # # ]: 0 : while( nLeafCount > nMax )
136 : 0 : ImplReduce();
137 : : }
138 : 0 : }
139 : : }
140 : : }
141 : 0 : }
142 : :
143 : : // ------------------------------------------------------------------------
144 : :
145 : 0 : void Octree::ImplDeleteOctree( PPNODE ppNode )
146 : : {
147 [ # # ]: 0 : for ( sal_uLong i = 0UL; i < 8UL; i++ )
148 : : {
149 [ # # ]: 0 : if ( (*ppNode)->pChild[ i ] )
150 : 0 : ImplDeleteOctree( &(*ppNode)->pChild[ i ] );
151 : : }
152 : :
153 : 0 : pNodeCache->ImplReleaseNode( *ppNode );
154 : 0 : *ppNode = NULL;
155 : 0 : }
156 : :
157 : : // ------------------------------------------------------------------------
158 : :
159 : 0 : void Octree::ImplAdd( PPNODE ppNode )
160 : : {
161 : : // ggf. neuen Knoten erzeugen
162 [ # # ]: 0 : if( !*ppNode )
163 : : {
164 : 0 : *ppNode = pNodeCache->ImplGetFreeNode();
165 : 0 : (*ppNode)->bLeaf = ( OCTREE_BITS == nLevel );
166 : :
167 [ # # ]: 0 : if( (*ppNode)->bLeaf )
168 : 0 : nLeafCount++;
169 : : else
170 : : {
171 : 0 : (*ppNode)->pNext = pReduce[ nLevel ];
172 : 0 : pReduce[ nLevel ] = *ppNode;
173 : : }
174 : : }
175 : :
176 [ # # ]: 0 : if( (*ppNode)->bLeaf )
177 : : {
178 : 0 : (*ppNode)->nCount++;
179 : 0 : (*ppNode)->nRed += pColor->GetRed();
180 : 0 : (*ppNode)->nGreen += pColor->GetGreen();
181 : 0 : (*ppNode)->nBlue += pColor->GetBlue();
182 : : }
183 : : else
184 : : {
185 : 0 : const sal_uLong nShift = 7 - nLevel;
186 : 0 : const sal_uInt8 cMask = pImplMask[ nLevel ];
187 : 0 : const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
188 : 0 : ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
189 : 0 : ( ( pColor->GetBlue() & cMask ) >> nShift );
190 : :
191 : 0 : nLevel++;
192 : 0 : ImplAdd( &(*ppNode)->pChild[ nIndex ] );
193 : : }
194 : 0 : }
195 : :
196 : : // ------------------------------------------------------------------------
197 : :
198 : 0 : void Octree::ImplReduce()
199 : : {
200 : : sal_uLong i;
201 : : PNODE pNode;
202 : 0 : sal_uLong nRedSum = 0L;
203 : 0 : sal_uLong nGreenSum = 0L;
204 : 0 : sal_uLong nBlueSum = 0L;
205 : 0 : sal_uLong nChildren = 0L;
206 : :
207 [ # # ][ # # ]: 0 : for ( i = OCTREE_BITS - 1; i && !pReduce[i]; i-- ) {}
[ # # ]
208 : :
209 : 0 : pNode = pReduce[ i ];
210 : 0 : pReduce[ i ] = pNode->pNext;
211 : :
212 [ # # ]: 0 : for ( i = 0; i < 8; i++ )
213 : : {
214 [ # # ]: 0 : if ( pNode->pChild[ i ] )
215 : : {
216 : 0 : PNODE pChild = pNode->pChild[ i ];
217 : :
218 : 0 : nRedSum += pChild->nRed;
219 : 0 : nGreenSum += pChild->nGreen;
220 : 0 : nBlueSum += pChild->nBlue;
221 : 0 : pNode->nCount += pChild->nCount;
222 : :
223 : 0 : pNodeCache->ImplReleaseNode( pNode->pChild[ i ] );
224 : 0 : pNode->pChild[ i ] = NULL;
225 : 0 : nChildren++;
226 : : }
227 : : }
228 : :
229 : 0 : pNode->bLeaf = sal_True;
230 : 0 : pNode->nRed = nRedSum;
231 : 0 : pNode->nGreen = nGreenSum;
232 : 0 : pNode->nBlue = nBlueSum;
233 : 0 : nLeafCount -= --nChildren;
234 : 0 : }
235 : :
236 : : // ------------------------------------------------------------------------
237 : :
238 : 0 : void Octree::CreatePalette( PNODE pNode )
239 : : {
240 [ # # ]: 0 : if( pNode->bLeaf )
241 : : {
242 : 0 : pNode->nPalIndex = nPalIndex;
243 : 0 : aPal[ nPalIndex++ ] = BitmapColor( (sal_uInt8) ( (double) pNode->nRed / pNode->nCount ),
244 : : (sal_uInt8) ( (double) pNode->nGreen / pNode->nCount ),
245 : 0 : (sal_uInt8) ( (double) pNode->nBlue / pNode->nCount ) );
246 : : }
247 [ # # ]: 0 : else for( sal_uLong i = 0UL; i < 8UL; i++ )
248 [ # # ]: 0 : if( pNode->pChild[ i ] )
249 : 0 : CreatePalette( pNode->pChild[ i ] );
250 : :
251 : 0 : }
252 : :
253 : : // ------------------------------------------------------------------------
254 : :
255 : 0 : void Octree::GetPalIndex( PNODE pNode )
256 : : {
257 [ # # ]: 0 : if ( pNode->bLeaf )
258 : 0 : nPalIndex = pNode->nPalIndex;
259 : : else
260 : : {
261 : 0 : const sal_uLong nShift = 7 - nLevel;
262 : 0 : const sal_uInt8 cMask = pImplMask[ nLevel++ ];
263 : 0 : const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
264 : 0 : ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
265 : 0 : ( ( pColor->GetBlue() & cMask ) >> nShift );
266 : :
267 : 0 : GetPalIndex( pNode->pChild[ nIndex ] );
268 : : }
269 : 0 : }
270 : :
271 : : // -------------------
272 : : // - InverseColorMap -
273 : : // -------------------
274 : :
275 : 0 : InverseColorMap::InverseColorMap( const BitmapPalette& rPal ) :
276 : 0 : nBits( 8 - OCTREE_BITS )
277 : : {
278 : : sal_uLong* cdp;
279 : : sal_uInt8* crgbp;
280 : 0 : const sal_uLong nColorMax = 1 << OCTREE_BITS;
281 : 0 : const sal_uLong xsqr = 1 << ( nBits << 1 );
282 : 0 : const sal_uLong xsqr2 = xsqr << 1;
283 : 0 : const sal_uLong nColors = rPal.GetEntryCount();
284 : 0 : const long x = 1L << nBits;
285 : 0 : const long x2 = x >> 1L;
286 : : sal_uLong r, g, b;
287 : : long rxx, gxx, bxx;
288 : : long rdist, gdist, bdist;
289 : : long crinc, cginc, cbinc;
290 : :
291 : 0 : ImplCreateBuffers( nColorMax );
292 : :
293 [ # # ]: 0 : for( sal_uLong nIndex = 0; nIndex < nColors; nIndex++ )
294 : : {
295 : 0 : const BitmapColor& rColor = rPal[ (sal_uInt16) nIndex ];
296 : 0 : const sal_uInt8 cRed = rColor.GetRed();
297 : 0 : const sal_uInt8 cGreen = rColor.GetGreen();
298 : 0 : const sal_uInt8 cBlue = rColor.GetBlue();
299 : :
300 : 0 : rdist = cRed - x2;
301 : 0 : gdist = cGreen - x2;
302 : 0 : bdist = cBlue - x2;
303 : 0 : rdist = rdist*rdist + gdist*gdist + bdist*bdist;
304 : :
305 : 0 : crinc = ( xsqr - ( cRed << nBits ) ) << 1L;
306 : 0 : cginc = ( xsqr - ( cGreen << nBits ) ) << 1L;
307 : 0 : cbinc = ( xsqr - ( cBlue << nBits ) ) << 1L;
308 : :
309 : 0 : cdp = (sal_uLong*) pBuffer;
310 : 0 : crgbp = pMap;
311 : :
312 [ # # ]: 0 : for( r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2 )
313 : : {
314 [ # # ]: 0 : for( g = 0, gdist = rdist, gxx = cginc; g < nColorMax; gdist += gxx, g++, gxx += xsqr2 )
315 : : {
316 [ # # ]: 0 : for( b = 0, bdist = gdist, bxx = cbinc; b < nColorMax; bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2 )
317 [ # # ][ # # ]: 0 : if ( !nIndex || ( (long) *cdp ) > bdist )
318 : : {
319 : 0 : *cdp = bdist;
320 : 0 : *crgbp = (sal_uInt8) nIndex;
321 : : }
322 : : }
323 : : }
324 : : }
325 : 0 : }
326 : :
327 : : // ------------------------------------------------------------------------
328 : :
329 : 0 : InverseColorMap::~InverseColorMap()
330 : : {
331 : 0 : rtl_freeMemory( pBuffer );
332 : 0 : rtl_freeMemory( pMap );
333 : 0 : }
334 : :
335 : : // ------------------------------------------------------------------------
336 : :
337 : 0 : void InverseColorMap::ImplCreateBuffers( const sal_uLong nMax )
338 : : {
339 : 0 : const sal_uLong nCount = nMax * nMax * nMax;
340 : 0 : const sal_uLong nSize = nCount * sizeof( sal_uLong );
341 : :
342 : 0 : pMap = (sal_uInt8*) rtl_allocateMemory( nCount );
343 : 0 : memset( pMap, 0x00, nCount );
344 : :
345 : 0 : pBuffer = (sal_uInt8*) rtl_allocateMemory( nSize );
346 : 0 : memset( pBuffer, 0xff, nSize );
347 : 0 : }
348 : :
349 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
