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 : #include <limits.h>
21 :
22 : #include <vcl/bmpacc.hxx>
23 :
24 : #include <impoct.hxx>
25 :
26 : #include "octree.hxx"
27 :
28 : // - pMask -
29 :
30 : static const sal_uInt8 pImplMask[8] = { 0x80, 0x40, 0x20, 0x10, 0x08, 0x04, 0x02, 0x01 };
31 :
32 : // - NodeCache -
33 :
34 473 : ImpNodeCache::ImpNodeCache( const sal_uLong nInitSize ) :
35 473 : pActNode( NULL )
36 : {
37 473 : const sal_uLong nSize = nInitSize + 4;
38 :
39 122973 : for( sal_uLong i = 0; i < nSize; i++ )
40 : {
41 122500 : OctreeNode* pNewNode = new NODE;
42 :
43 122500 : pNewNode->pNextInCache = pActNode;
44 122500 : pActNode = pNewNode;
45 : }
46 473 : }
47 :
48 473 : ImpNodeCache::~ImpNodeCache()
49 : {
50 166444 : while( pActNode )
51 : {
52 165498 : OctreeNode* pNode = pActNode;
53 :
54 165498 : pActNode = pNode->pNextInCache;
55 165498 : delete pNode;
56 : }
57 473 : }
58 :
59 : // - Octree -
60 :
61 473 : Octree::Octree( const BitmapReadAccess& rReadAcc, sal_uLong nColors ) :
62 : nMax ( nColors ),
63 : nLeafCount ( 0L ),
64 : pTree ( NULL ),
65 473 : pAcc ( &rReadAcc )
66 : {
67 473 : pNodeCache = new ImpNodeCache( nColors );
68 473 : memset( pReduce, 0, ( OCTREE_BITS + 1 ) * sizeof( PNODE ) );
69 473 : ImplCreateOctree();
70 473 : }
71 :
72 946 : Octree::~Octree()
73 : {
74 473 : ImplDeleteOctree( &pTree );
75 473 : delete pNodeCache;
76 473 : }
77 :
78 473 : void Octree::ImplCreateOctree()
79 : {
80 473 : if( !!*pAcc )
81 : {
82 473 : const long nWidth = pAcc->Width();
83 473 : const long nHeight = pAcc->Height();
84 :
85 473 : if( pAcc->HasPalette() )
86 : {
87 0 : for( long nY = 0; nY < nHeight; nY++ )
88 : {
89 0 : for( long nX = 0; nX < nWidth; nX++ )
90 : {
91 0 : pColor = &(BitmapColor&) pAcc->GetPaletteColor( pAcc->GetPixelIndex( nY, nX ) );
92 0 : nLevel = 0L;
93 0 : ImplAdd( &pTree );
94 :
95 0 : while( nLeafCount > nMax )
96 0 : ImplReduce();
97 : }
98 : }
99 : }
100 : else
101 : {
102 473 : BitmapColor aColor;
103 :
104 473 : pColor = &aColor;
105 :
106 34813 : for( long nY = 0; nY < nHeight; nY++ )
107 : {
108 3650166 : for( long nX = 0; nX < nWidth; nX++ )
109 : {
110 3615826 : aColor = pAcc->GetPixel( nY, nX );
111 3615826 : nLevel = 0L;
112 3615826 : ImplAdd( &pTree );
113 :
114 7248290 : while( nLeafCount > nMax )
115 16638 : ImplReduce();
116 : }
117 473 : }
118 : }
119 : }
120 473 : }
121 :
122 138588 : void Octree::ImplDeleteOctree( PPNODE ppNode )
123 : {
124 1247292 : for ( sal_uLong i = 0UL; i < 8UL; i++ )
125 : {
126 1108704 : if ( (*ppNode)->pChild[ i ] )
127 138115 : ImplDeleteOctree( &(*ppNode)->pChild[ i ] );
128 : }
129 :
130 138588 : pNodeCache->ImplReleaseNode( *ppNode );
131 138588 : *ppNode = NULL;
132 138588 : }
133 :
134 20724506 : void Octree::ImplAdd( PPNODE ppNode )
135 : {
136 : // ggf. neuen Knoten erzeugen
137 20724506 : if( !*ppNode )
138 : {
139 164889 : *ppNode = pNodeCache->ImplGetFreeNode();
140 164889 : (*ppNode)->bLeaf = ( OCTREE_BITS == nLevel );
141 :
142 164889 : if( (*ppNode)->bLeaf )
143 93391 : nLeafCount++;
144 : else
145 : {
146 71498 : (*ppNode)->pNext = pReduce[ nLevel ];
147 71498 : pReduce[ nLevel ] = *ppNode;
148 : }
149 : }
150 :
151 20724506 : if( (*ppNode)->bLeaf )
152 : {
153 3615826 : (*ppNode)->nCount++;
154 3615826 : (*ppNode)->nRed += pColor->GetRed();
155 3615826 : (*ppNode)->nGreen += pColor->GetGreen();
156 3615826 : (*ppNode)->nBlue += pColor->GetBlue();
157 : }
158 : else
159 : {
160 17108680 : const sal_uLong nShift = 7 - nLevel;
161 17108680 : const sal_uInt8 cMask = pImplMask[ nLevel ];
162 34217360 : const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
163 34217360 : ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
164 34217360 : ( ( pColor->GetBlue() & cMask ) >> nShift );
165 :
166 17108680 : nLevel++;
167 17108680 : ImplAdd( &(*ppNode)->pChild[ nIndex ] );
168 : }
169 20724506 : }
170 :
171 16638 : void Octree::ImplReduce()
172 : {
173 : sal_uLong i;
174 : PNODE pNode;
175 16638 : sal_uLong nRedSum = 0L;
176 16638 : sal_uLong nGreenSum = 0L;
177 16638 : sal_uLong nBlueSum = 0L;
178 16638 : sal_uLong nChildren = 0L;
179 :
180 16638 : for ( i = OCTREE_BITS - 1; i && !pReduce[i]; i-- ) {}
181 :
182 16638 : pNode = pReduce[ i ];
183 16638 : pReduce[ i ] = pNode->pNext;
184 :
185 149742 : for ( i = 0; i < 8; i++ )
186 : {
187 133104 : if ( pNode->pChild[ i ] )
188 : {
189 26301 : PNODE pChild = pNode->pChild[ i ];
190 :
191 26301 : nRedSum += pChild->nRed;
192 26301 : nGreenSum += pChild->nGreen;
193 26301 : nBlueSum += pChild->nBlue;
194 26301 : pNode->nCount += pChild->nCount;
195 :
196 26301 : pNodeCache->ImplReleaseNode( pNode->pChild[ i ] );
197 26301 : pNode->pChild[ i ] = NULL;
198 26301 : nChildren++;
199 : }
200 : }
201 :
202 16638 : pNode->bLeaf = true;
203 16638 : pNode->nRed = nRedSum;
204 16638 : pNode->nGreen = nGreenSum;
205 16638 : pNode->nBlue = nBlueSum;
206 16638 : nLeafCount -= --nChildren;
207 16638 : }
208 :
209 138588 : void Octree::CreatePalette( PNODE pNode )
210 : {
211 138588 : if( pNode->bLeaf )
212 : {
213 83728 : pNode->nPalIndex = nPalIndex;
214 251184 : aPal[ nPalIndex++ ] = BitmapColor( (sal_uInt8) ( (double) pNode->nRed / pNode->nCount ),
215 83728 : (sal_uInt8) ( (double) pNode->nGreen / pNode->nCount ),
216 167456 : (sal_uInt8) ( (double) pNode->nBlue / pNode->nCount ) );
217 : }
218 493740 : else for( sal_uLong i = 0UL; i < 8UL; i++ )
219 438880 : if( pNode->pChild[ i ] )
220 138115 : CreatePalette( pNode->pChild[ i ] );
221 :
222 138588 : }
223 :
224 0 : void Octree::GetPalIndex( PNODE pNode )
225 : {
226 0 : if ( pNode->bLeaf )
227 0 : nPalIndex = pNode->nPalIndex;
228 : else
229 : {
230 0 : const sal_uLong nShift = 7 - nLevel;
231 0 : const sal_uInt8 cMask = pImplMask[ nLevel++ ];
232 0 : const sal_uLong nIndex = ( ( ( pColor->GetRed() & cMask ) >> nShift ) << 2 ) |
233 0 : ( ( ( pColor->GetGreen() & cMask ) >> nShift ) << 1 ) |
234 0 : ( ( pColor->GetBlue() & cMask ) >> nShift );
235 :
236 0 : GetPalIndex( pNode->pChild[ nIndex ] );
237 : }
238 0 : }
239 :
240 : // - InverseColorMap -
241 :
242 473 : InverseColorMap::InverseColorMap( const BitmapPalette& rPal ) :
243 473 : nBits( 8 - OCTREE_BITS )
244 : {
245 : sal_uLong* cdp;
246 : sal_uInt8* crgbp;
247 473 : const sal_uLong nColorMax = 1 << OCTREE_BITS;
248 473 : const sal_uLong xsqr = 1 << ( nBits << 1 );
249 473 : const sal_uLong xsqr2 = xsqr << 1;
250 473 : const sal_uLong nColors = rPal.GetEntryCount();
251 473 : const long x = 1L << nBits;
252 473 : const long x2 = x >> 1L;
253 : sal_uLong r, g, b;
254 : long rxx, gxx, bxx;
255 : long rdist, gdist, bdist;
256 : long crinc, cginc, cbinc;
257 :
258 473 : ImplCreateBuffers( nColorMax );
259 :
260 84201 : for( sal_uLong nIndex = 0; nIndex < nColors; nIndex++ )
261 : {
262 83728 : const BitmapColor& rColor = rPal[ (sal_uInt16) nIndex ];
263 83728 : const sal_uInt8 cRed = rColor.GetRed();
264 83728 : const sal_uInt8 cGreen = rColor.GetGreen();
265 83728 : const sal_uInt8 cBlue = rColor.GetBlue();
266 :
267 83728 : rdist = cRed - x2;
268 83728 : gdist = cGreen - x2;
269 83728 : bdist = cBlue - x2;
270 83728 : rdist = rdist*rdist + gdist*gdist + bdist*bdist;
271 :
272 83728 : crinc = ( xsqr - ( cRed << nBits ) ) << 1L;
273 83728 : cginc = ( xsqr - ( cGreen << nBits ) ) << 1L;
274 83728 : cbinc = ( xsqr - ( cBlue << nBits ) ) << 1L;
275 :
276 83728 : cdp = (sal_uLong*) pBuffer;
277 83728 : crgbp = pMap;
278 :
279 2763024 : for( r = 0, rxx = crinc; r < nColorMax; rdist += rxx, r++, rxx += xsqr2 )
280 : {
281 88416768 : for( g = 0, gdist = rdist, gxx = cginc; g < nColorMax; gdist += gxx, g++, gxx += xsqr2 )
282 : {
283 2829336576 : for( b = 0, bdist = gdist, bxx = cbinc; b < nColorMax; bdist += bxx, b++, cdp++, crgbp++, bxx += xsqr2 )
284 2743599104 : if ( !nIndex || ( (long) *cdp ) > bdist )
285 : {
286 371634681 : *cdp = bdist;
287 371634681 : *crgbp = (sal_uInt8) nIndex;
288 : }
289 : }
290 : }
291 : }
292 473 : }
293 :
294 473 : InverseColorMap::~InverseColorMap()
295 : {
296 473 : rtl_freeMemory( pBuffer );
297 473 : rtl_freeMemory( pMap );
298 473 : }
299 :
300 473 : void InverseColorMap::ImplCreateBuffers( const sal_uLong nMax )
301 : {
302 473 : const sal_uLong nCount = nMax * nMax * nMax;
303 473 : const sal_uLong nSize = nCount * sizeof( sal_uLong );
304 :
305 473 : pMap = (sal_uInt8*) rtl_allocateMemory( nCount );
306 473 : memset( pMap, 0x00, nCount );
307 :
308 473 : pBuffer = (sal_uInt8*) rtl_allocateMemory( nSize );
309 473 : memset( pBuffer, 0xff, nSize );
310 473 : }
311 :
312 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
