1 /*
2 * Copyright 2008-2010 Stephan Aßmus <superstippi@gmx.de>
3 * Distributed under the terms of the MIT license.
4 */
5 //----------------------------------------------------------------------------
6 // Anti-Grain Geometry - Version 2.4
7 // Copyright (C) 2002-2005 Maxim Shemanarev (http://www.antigrain.com)
8 //
9 // Permission to copy, use, modify, sell and distribute this software
10 // is granted provided this copyright notice appears in all copies.
11 // This software is provided "as is" without express or implied
12 // warranty, and with no claim as to its suitability for any purpose.
13 //
14 //----------------------------------------------------------------------------
15 // Contact: mcseem@antigrain.com
16 // mcseemagg@yahoo.com
17 // http://www.antigrain.com
18 //----------------------------------------------------------------------------
19 //
20 // The Stack Blur Algorithm was invented by Mario Klingemann,
21 // mario@quasimondo.com and described here:
22 // http://incubator.quasimondo.com/processing/fast_blur_deluxe.php
23 // (search phrase "Stackblur: Fast But Goodlooking").
24 // The major improvement is that there's no more division table
25 // that was very expensive to create for large blur radii. Insted,
26 // for 8-bit per channel and radius not exceeding 254 the division is
27 // replaced by multiplication and shift.
28 //
29 //----------------------------------------------------------------------------
30
31
32 #include "StackBlurFilter.h"
33
34 #include <stdio.h>
35
36 #include <Bitmap.h>
37
38 #include <agg_array.h>
39
40
41 template<class T> struct stack_blur_tables
42 {
43 static uint16 const g_stack_blur8_mul[255];
44 static uint8 const g_stack_blur8_shr[255];
45 };
46
47
48 template<class T>
49 uint16 const stack_blur_tables<T>::g_stack_blur8_mul[255] =
50 {
51 512,512,456,512,328,456,335,512,405,328,271,456,388,335,292,512,
52 454,405,364,328,298,271,496,456,420,388,360,335,312,292,273,512,
53 482,454,428,405,383,364,345,328,312,298,284,271,259,496,475,456,
54 437,420,404,388,374,360,347,335,323,312,302,292,282,273,265,512,
55 497,482,468,454,441,428,417,405,394,383,373,364,354,345,337,328,
56 320,312,305,298,291,284,278,271,265,259,507,496,485,475,465,456,
57 446,437,428,420,412,404,396,388,381,374,367,360,354,347,341,335,
58 329,323,318,312,307,302,297,292,287,282,278,273,269,265,261,512,
59 505,497,489,482,475,468,461,454,447,441,435,428,422,417,411,405,
60 399,394,389,383,378,373,368,364,359,354,350,345,341,337,332,328,
61 324,320,316,312,309,305,301,298,294,291,287,284,281,278,274,271,
62 268,265,262,259,257,507,501,496,491,485,480,475,470,465,460,456,
63 451,446,442,437,433,428,424,420,416,412,408,404,400,396,392,388,
64 385,381,377,374,370,367,363,360,357,354,350,347,344,341,338,335,
65 332,329,326,323,320,318,315,312,310,307,304,302,299,297,294,292,
66 289,287,285,282,280,278,275,273,271,269,267,265,263,261,259
67 };
68
69
70 template<class T>
71 uint8 const stack_blur_tables<T>::g_stack_blur8_shr[255] =
72 {
73 9, 11, 12, 13, 13, 14, 14, 15, 15, 15, 15, 16, 16, 16, 16, 17,
74 17, 17, 17, 17, 17, 17, 18, 18, 18, 18, 18, 18, 18, 18, 18, 19,
75 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 20, 20, 20,
76 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 21,
77 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
78 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 22, 22, 22, 22, 22, 22,
79 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
80 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 23,
81 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
82 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
83 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
84 23, 23, 23, 23, 23, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
85 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
86 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
87 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
88 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24
89 };
90
91
92 #if __GNUC__ < 4
93 static inline float
roundf(float v)94 roundf(float v)
95 {
96 return floorf(v + 0.5);
97 }
98 #endif
99
100
StackBlurFilter()101 StackBlurFilter::StackBlurFilter()
102 {
103 }
104
105
~StackBlurFilter()106 StackBlurFilter::~StackBlurFilter()
107 {
108 }
109
110
111 void
Filter(BBitmap * bitmap,double radius)112 StackBlurFilter::Filter(BBitmap* bitmap, double radius)
113 {
114 if (radius < 1.0)
115 return;
116
117 int32 width = bitmap->Bounds().IntegerWidth() + 1;
118 int32 height = bitmap->Bounds().IntegerHeight() + 1;
119 uint32 bpr = bitmap->BytesPerRow();
120 uint8* bits = (uint8*)bitmap->Bits();
121
122 unsigned r = (unsigned)roundf(radius);
123
124 if (bitmap->ColorSpace() == B_RGBA32
125 || bitmap->ColorSpace() == B_RGB32) {
126
127 _Filter32(bits, width, height, bpr, r, r);
128
129 } else if (bitmap->ColorSpace() == B_GRAY8) {
130
131 _Filter8(bits, width, height, bpr, r, r);
132
133 } else
134 printf("StackBlurFilter::Filter() - unsupported color space\n");
135 }
136
137
138 // #pragma mark -
139
140
141 struct rgba {
142 uint8 r;
143 uint8 g;
144 uint8 b;
145 uint8 a;
146 };
147
148
149 void
_Filter32(uint8 * buffer,unsigned width,unsigned height,int32 bpr,unsigned rx,unsigned ry) const150 StackBlurFilter::_Filter32(uint8* buffer, unsigned width, unsigned height,
151 int32 bpr, unsigned rx, unsigned ry) const
152 {
153 typedef rgba color_type;
154
155 unsigned x, y, xp, yp, i;
156 unsigned stack_ptr;
157 unsigned stack_start;
158
159 const uint8* src_pix_ptr;
160 uint8* dst_pix_ptr;
161 color_type* stack_pix_ptr;
162
163 unsigned sum_r;
164 unsigned sum_g;
165 unsigned sum_b;
166 unsigned sum_a;
167 unsigned sum_in_r;
168 unsigned sum_in_g;
169 unsigned sum_in_b;
170 unsigned sum_in_a;
171 unsigned sum_out_r;
172 unsigned sum_out_g;
173 unsigned sum_out_b;
174 unsigned sum_out_a;
175
176 unsigned w = width;
177 unsigned h = height;
178 unsigned wm = w - 1;
179 unsigned hm = h - 1;
180
181 unsigned div;
182 unsigned mul_sum;
183 unsigned shr_sum;
184
185 agg::pod_vector<color_type> stack;
186
187 if (rx > 0) {
188 if (rx > 254)
189 rx = 254;
190 div = rx * 2 + 1;
191 mul_sum = stack_blur_tables<int>::g_stack_blur8_mul[rx];
192 shr_sum = stack_blur_tables<int>::g_stack_blur8_shr[rx];
193 stack.allocate(div);
194
195 for (y = 0; y < h; y++) {
196 sum_r =
197 sum_g =
198 sum_b =
199 sum_a =
200 sum_in_r =
201 sum_in_g =
202 sum_in_b =
203 sum_in_a =
204 sum_out_r =
205 sum_out_g =
206 sum_out_b =
207 sum_out_a = 0;
208
209 src_pix_ptr = buffer + bpr * y;
210 for (i = 0; i <= rx; i++) {
211 stack_pix_ptr = &stack[i];
212 stack_pix_ptr->r = src_pix_ptr[2];
213 stack_pix_ptr->g = src_pix_ptr[1];
214 stack_pix_ptr->b = src_pix_ptr[0];
215 stack_pix_ptr->a = src_pix_ptr[3];
216 sum_r += src_pix_ptr[2] * (i + 1);
217 sum_g += src_pix_ptr[1] * (i + 1);
218 sum_b += src_pix_ptr[0] * (i + 1);
219 sum_a += src_pix_ptr[3] * (i + 1);
220 sum_out_r += src_pix_ptr[2];
221 sum_out_g += src_pix_ptr[1];
222 sum_out_b += src_pix_ptr[0];
223 sum_out_a += src_pix_ptr[3];
224 }
225 for (i = 1; i <= rx; i++) {
226 if (i <= wm)
227 src_pix_ptr += 4;
228 stack_pix_ptr = &stack[i + rx];
229 stack_pix_ptr->r = src_pix_ptr[2];
230 stack_pix_ptr->g = src_pix_ptr[1];
231 stack_pix_ptr->b = src_pix_ptr[0];
232 stack_pix_ptr->a = src_pix_ptr[3];
233 sum_r += src_pix_ptr[2] * (rx + 1 - i);
234 sum_g += src_pix_ptr[1] * (rx + 1 - i);
235 sum_b += src_pix_ptr[0] * (rx + 1 - i);
236 sum_a += src_pix_ptr[3] * (rx + 1 - i);
237 sum_in_r += src_pix_ptr[2];
238 sum_in_g += src_pix_ptr[1];
239 sum_in_b += src_pix_ptr[0];
240 sum_in_a += src_pix_ptr[3];
241 }
242
243 stack_ptr = rx;
244 xp = rx;
245 if (xp > wm)
246 xp = wm;
247 src_pix_ptr = buffer + xp * 4 + y * bpr;
248 dst_pix_ptr = buffer + y * bpr;
249 for (x = 0; x < w; x++) {
250 dst_pix_ptr[2] = (sum_r * mul_sum) >> shr_sum;
251 dst_pix_ptr[1] = (sum_g * mul_sum) >> shr_sum;
252 dst_pix_ptr[0] = (sum_b * mul_sum) >> shr_sum;
253 dst_pix_ptr[3] = (sum_a * mul_sum) >> shr_sum;
254 dst_pix_ptr += 4;
255
256 sum_r -= sum_out_r;
257 sum_g -= sum_out_g;
258 sum_b -= sum_out_b;
259 sum_a -= sum_out_a;
260
261 stack_start = stack_ptr + div - rx;
262 if(stack_start >= div) stack_start -= div;
263 stack_pix_ptr = &stack[stack_start];
264
265 sum_out_r -= stack_pix_ptr->r;
266 sum_out_g -= stack_pix_ptr->g;
267 sum_out_b -= stack_pix_ptr->b;
268 sum_out_a -= stack_pix_ptr->a;
269
270 if (xp < wm) {
271 src_pix_ptr += 4;
272 ++xp;
273 }
274
275 stack_pix_ptr->r = src_pix_ptr[2];
276 stack_pix_ptr->g = src_pix_ptr[1];
277 stack_pix_ptr->b = src_pix_ptr[0];
278 stack_pix_ptr->a = src_pix_ptr[3];
279
280 sum_in_r += src_pix_ptr[2];
281 sum_in_g += src_pix_ptr[1];
282 sum_in_b += src_pix_ptr[0];
283 sum_in_a += src_pix_ptr[3];
284 sum_r += sum_in_r;
285 sum_g += sum_in_g;
286 sum_b += sum_in_b;
287 sum_a += sum_in_a;
288
289 ++stack_ptr;
290 if (stack_ptr >= div)
291 stack_ptr = 0;
292 stack_pix_ptr = &stack[stack_ptr];
293
294 sum_out_r += stack_pix_ptr->r;
295 sum_out_g += stack_pix_ptr->g;
296 sum_out_b += stack_pix_ptr->b;
297 sum_out_a += stack_pix_ptr->a;
298 sum_in_r -= stack_pix_ptr->r;
299 sum_in_g -= stack_pix_ptr->g;
300 sum_in_b -= stack_pix_ptr->b;
301 sum_in_a -= stack_pix_ptr->a;
302 }
303 }
304 }
305
306 if (ry > 0) {
307 if (ry > 254)
308 ry = 254;
309 div = ry * 2 + 1;
310 mul_sum = stack_blur_tables<int>::g_stack_blur8_mul[ry];
311 shr_sum = stack_blur_tables<int>::g_stack_blur8_shr[ry];
312 stack.allocate(div);
313
314 int stride = bpr;
315 for(x = 0; x < w; x++) {
316 sum_r =
317 sum_g =
318 sum_b =
319 sum_a =
320 sum_in_r =
321 sum_in_g =
322 sum_in_b =
323 sum_in_a =
324 sum_out_r =
325 sum_out_g =
326 sum_out_b =
327 sum_out_a = 0;
328
329 src_pix_ptr = buffer + x * 4;
330 for (i = 0; i <= ry; i++) {
331 stack_pix_ptr = &stack[i];
332 stack_pix_ptr->r = src_pix_ptr[2];
333 stack_pix_ptr->g = src_pix_ptr[1];
334 stack_pix_ptr->b = src_pix_ptr[0];
335 stack_pix_ptr->a = src_pix_ptr[3];
336 sum_r += src_pix_ptr[2] * (i + 1);
337 sum_g += src_pix_ptr[1] * (i + 1);
338 sum_b += src_pix_ptr[0] * (i + 1);
339 sum_a += src_pix_ptr[3] * (i + 1);
340 sum_out_r += src_pix_ptr[2];
341 sum_out_g += src_pix_ptr[1];
342 sum_out_b += src_pix_ptr[0];
343 sum_out_a += src_pix_ptr[3];
344 }
345 for (i = 1; i <= ry; i++) {
346 if (i <= hm)
347 src_pix_ptr += stride;
348 stack_pix_ptr = &stack[i + ry];
349 stack_pix_ptr->r = src_pix_ptr[2];
350 stack_pix_ptr->g = src_pix_ptr[1];
351 stack_pix_ptr->b = src_pix_ptr[0];
352 stack_pix_ptr->a = src_pix_ptr[3];
353 sum_r += src_pix_ptr[2] * (ry + 1 - i);
354 sum_g += src_pix_ptr[1] * (ry + 1 - i);
355 sum_b += src_pix_ptr[0] * (ry + 1 - i);
356 sum_a += src_pix_ptr[3] * (ry + 1 - i);
357 sum_in_r += src_pix_ptr[2];
358 sum_in_g += src_pix_ptr[1];
359 sum_in_b += src_pix_ptr[0];
360 sum_in_a += src_pix_ptr[3];
361 }
362
363 stack_ptr = ry;
364 yp = ry;
365 if (yp > hm)
366 yp = hm;
367 src_pix_ptr = buffer + x * 4 + yp * bpr;
368 dst_pix_ptr = buffer + x * 4;
369 for (y = 0; y < h; y++) {
370 dst_pix_ptr[2] = (sum_r * mul_sum) >> shr_sum;
371 dst_pix_ptr[1] = (sum_g * mul_sum) >> shr_sum;
372 dst_pix_ptr[0] = (sum_b * mul_sum) >> shr_sum;
373 dst_pix_ptr[3] = (sum_a * mul_sum) >> shr_sum;
374 dst_pix_ptr += stride;
375
376 sum_r -= sum_out_r;
377 sum_g -= sum_out_g;
378 sum_b -= sum_out_b;
379 sum_a -= sum_out_a;
380
381 stack_start = stack_ptr + div - ry;
382 if (stack_start >= div)
383 stack_start -= div;
384
385 stack_pix_ptr = &stack[stack_start];
386 sum_out_r -= stack_pix_ptr->r;
387 sum_out_g -= stack_pix_ptr->g;
388 sum_out_b -= stack_pix_ptr->b;
389 sum_out_a -= stack_pix_ptr->a;
390
391 if (yp < hm) {
392 src_pix_ptr += stride;
393 ++yp;
394 }
395
396 stack_pix_ptr->r = src_pix_ptr[2];
397 stack_pix_ptr->g = src_pix_ptr[1];
398 stack_pix_ptr->b = src_pix_ptr[0];
399 stack_pix_ptr->a = src_pix_ptr[3];
400
401 sum_in_r += src_pix_ptr[2];
402 sum_in_g += src_pix_ptr[1];
403 sum_in_b += src_pix_ptr[0];
404 sum_in_a += src_pix_ptr[3];
405 sum_r += sum_in_r;
406 sum_g += sum_in_g;
407 sum_b += sum_in_b;
408 sum_a += sum_in_a;
409
410 ++stack_ptr;
411 if (stack_ptr >= div)
412 stack_ptr = 0;
413 stack_pix_ptr = &stack[stack_ptr];
414
415 sum_out_r += stack_pix_ptr->r;
416 sum_out_g += stack_pix_ptr->g;
417 sum_out_b += stack_pix_ptr->b;
418 sum_out_a += stack_pix_ptr->a;
419 sum_in_r -= stack_pix_ptr->r;
420 sum_in_g -= stack_pix_ptr->g;
421 sum_in_b -= stack_pix_ptr->b;
422 sum_in_a -= stack_pix_ptr->a;
423 }
424 }
425 }
426 }
427
428
429 void
_Filter8(uint8 * buffer,unsigned width,unsigned height,int32 bpr,unsigned rx,unsigned ry) const430 StackBlurFilter::_Filter8(uint8* buffer, unsigned width, unsigned height,
431 int32 bpr, unsigned rx, unsigned ry) const
432 {
433 unsigned x, y, xp, yp, i;
434 unsigned stack_ptr;
435 unsigned stack_start;
436
437 const uint8* src_pix_ptr;
438 uint8* dst_pix_ptr;
439 unsigned pix;
440 unsigned stack_pix;
441 unsigned sum;
442 unsigned sum_in;
443 unsigned sum_out;
444
445 unsigned w = width;
446 unsigned h = height;
447 unsigned wm = w - 1;
448 unsigned hm = h - 1;
449
450 unsigned div;
451 unsigned mul_sum;
452 unsigned shr_sum;
453
454 agg::pod_vector<uint8> stack;
455
456 if(rx > 0)
457 {
458 if(rx > 254) rx = 254;
459 div = rx * 2 + 1;
460 mul_sum = stack_blur_tables<int>::g_stack_blur8_mul[rx];
461 shr_sum = stack_blur_tables<int>::g_stack_blur8_shr[rx];
462 stack.allocate(div);
463
464 for(y = 0; y < h; y++)
465 {
466 sum = sum_in = sum_out = 0;
467
468 src_pix_ptr = buffer + y * bpr;
469 pix = *src_pix_ptr;
470 for(i = 0; i <= rx; i++)
471 {
472 stack[i] = pix;
473 sum += pix * (i + 1);
474 sum_out += pix;
475 }
476 for(i = 1; i <= rx; i++)
477 {
478 if(i <= wm) src_pix_ptr += 1;
479 pix = *src_pix_ptr;
480 stack[i + rx] = pix;
481 sum += pix * (rx + 1 - i);
482 sum_in += pix;
483 }
484
485 stack_ptr = rx;
486 xp = rx;
487 if(xp > wm) xp = wm;
488 src_pix_ptr = buffer + xp + y * bpr;
489 dst_pix_ptr = buffer + y * bpr;
490 for(x = 0; x < w; x++)
491 {
492 *dst_pix_ptr = (sum * mul_sum) >> shr_sum;
493 dst_pix_ptr += 1;
494
495 sum -= sum_out;
496
497 stack_start = stack_ptr + div - rx;
498 if(stack_start >= div) stack_start -= div;
499 sum_out -= stack[stack_start];
500
501 if(xp < wm)
502 {
503 src_pix_ptr += 1;
504 pix = *src_pix_ptr;
505 ++xp;
506 }
507
508 stack[stack_start] = pix;
509
510 sum_in += pix;
511 sum += sum_in;
512
513 ++stack_ptr;
514 if(stack_ptr >= div) stack_ptr = 0;
515 stack_pix = stack[stack_ptr];
516
517 sum_out += stack_pix;
518 sum_in -= stack_pix;
519 }
520 }
521 }
522
523 if(ry > 0)
524 {
525 if(ry > 254) ry = 254;
526 div = ry * 2 + 1;
527 mul_sum = stack_blur_tables<int>::g_stack_blur8_mul[ry];
528 shr_sum = stack_blur_tables<int>::g_stack_blur8_shr[ry];
529 stack.allocate(div);
530
531 int stride = bpr;
532 for(x = 0; x < w; x++)
533 {
534 sum = sum_in = sum_out = 0;
535
536 src_pix_ptr = buffer + x;
537 pix = *src_pix_ptr;
538 for(i = 0; i <= ry; i++)
539 {
540 stack[i] = pix;
541 sum += pix * (i + 1);
542 sum_out += pix;
543 }
544 for(i = 1; i <= ry; i++)
545 {
546 if(i <= hm) src_pix_ptr += stride;
547 pix = *src_pix_ptr;
548 stack[i + ry] = pix;
549 sum += pix * (ry + 1 - i);
550 sum_in += pix;
551 }
552
553 stack_ptr = ry;
554 yp = ry;
555 if(yp > hm) yp = hm;
556 src_pix_ptr = buffer + x + yp * bpr;
557 dst_pix_ptr = buffer + x;
558 for(y = 0; y < h; y++)
559 {
560 *dst_pix_ptr = (sum * mul_sum) >> shr_sum;
561 dst_pix_ptr += stride;
562
563 sum -= sum_out;
564
565 stack_start = stack_ptr + div - ry;
566 if(stack_start >= div) stack_start -= div;
567 sum_out -= stack[stack_start];
568
569 if(yp < hm)
570 {
571 src_pix_ptr += stride;
572 pix = *src_pix_ptr;
573 ++yp;
574 }
575
576 stack[stack_start] = pix;
577
578 sum_in += pix;
579 sum += sum_in;
580
581 ++stack_ptr;
582 if(stack_ptr >= div) stack_ptr = 0;
583 stack_pix = stack[stack_ptr];
584
585 sum_out += stack_pix;
586 sum_in -= stack_pix;
587 }
588 }
589 }
590 }
591
592