Fast Real-Time blur for applet

[andre90boss]

hi guys!
i'm new here and i guess that i will learn a lot reading deep into this forum 

but now a question.. i'm trying to build a library to handle the animation and effects of my applets and i'm getting some problems with performance .. i'm using Java2D api to avoid problem of compatibility and i'm becoming crazy finding a fast way to implement a blur algorithm that i will use in animation.. the first try was with a ConvolveOp class but it's too much slow with a 8x8 kernel...

so any suggestion??
thanks

... forgive me for my inglish i'm italian

[Hansdampf]

this is really fast:
http://www.gamasutra.com/view/feature/3102/four_tricks_for_fast_blurring_in_.php

I think Pulpcore uses a similar approach, you can browse the source code.

[andre90boss]

thaks a lot for helping me

i will try to implement this trick, they seam good and fast

Games published by our own members! Check 'em out!

[pjt33]

thaks a lot for helping me

i will try to implement this trick, they seam good and fast

I've implemented the second one before, operating on an int[] raster. I think the fastest I managed to get it after a couple of days of optimisation was 20 blurs per second of 640x480 RGB on a 2006-era mid-range desktop.

[andre90boss]

I've implemented the second one before, operating on an int[] raster. I think the fastest I managed to get it after a couple of days of optimisation was 20 blurs per second of 640x480 RGB on a 2006-era mid-range desktop.

can you post some code?
i'm not very good in math 

[pjt33]

can you post some code?
i'm not very good in math 

I'd have to write it from scratch. When I did it before it was for a company (and I can't even violate my contract to post it because I no longer work there).

Do you want it done in place, or output to a different int[] to the input?

[Hansdampf]

There is C source code in that Gamasutra article, converting it to Java (and extending to ARGB) should not be difficult.


this could help you too (but I think converting the C code is easier):
http://code.google.com/p/pulpcore/source/browse/src/pulpcore/image/filter/Blur.java

[andre90boss]

EDIT: double post sorry 

[andre90boss]

I'd have to write it from scratch. When I did it before it was for a company (and I can't even violate my contract to post it because I no longer work there).

Do you want it done in place, or output to a different int[] to the input?

i work with BufferedImage 

i will take a look at the source code in C, i will try 

[Jono]

i work with BufferedImage 

i will take a look at the source code in C, i will try 

Depending on how the BufferedImage was constructed, you can get a significant speed up with:

1	DataBuffer imageData = myBufferedImage.getRaster().getDataBuffer();

and modify the DataBuffer directly with getElem() and setElem().

Edit: I just realised that doesn't really solve your problem. The WritableRaster you get from getRaster() has a method for setting all the image data from an array: setPixels(x,y,w,h,iArray)

Games published by our own members! Check 'em out!

[Abuse]

Even faster if you cast the DataBuffer to a DataBufferInt, and use DataBufferInt#getData() to obtain the underlying int[].
You are then manipulating the Image's data array directly - no copying necessary.

Obviously you need to ensure your BufferedImage is of a suitable type.

[andre90boss]

thaks for the reply !

but i still don't understand exactly the algorithm...
for example what means "each destination pixel is simply the average of a short horizontal line of pixels in the source image"?
means the average of all color component?

(i'm trying to implement the second trick because is more flexible i think..)

[pjt33]

but i still don't understand exactly the algorithm...
for example what means "each destination pixel is simply the average of a short horizontal line of pixels in the source image"?
means the average of all color component?

Yes, you do red, green, and blue separately.

[DzzD]

I'd have to write it from scratch. When I did it before it was for a company (and I can't even violate my contract to post it because I no longer work there).

Do you want it done in place, or output to a different int[] to the input?

really ? arf... as long as it is bunch or little piece of code I really really will never care...


@OP (andre90boss ):

you could use something like that :

1   2   3   4   5   6   7

int pixels[]; Image image; BufferedImage BIImage; BIImage = new BufferedImage(width, height,BufferedImage.TYPE_INT_RGB); pixels=((DataBufferInt)(BIImage.getRaster().getDataBuffer())).getData(); image=(Image)BIImage;

then later modify pixels array to access image pixels and use regular graphics.drawImage( .... ) when requiered to draw.

About pixels manipulation you can have a look here http://dzzd.net/SimpleParticle/ source code here http://dzzd.net/SimpleParticle/sources.zip there is similar pixels processing than bluring (as I remember it use MemoryImageSource but you can easily (with the above code) convert it to use BufferedImage)         

[pjt33]

really ? arf... as long as it is bunch or little piece of code I really really will never care...

It wasn't particularly small. 200 or 300 lines of code because of unrolled loops, extracted special cases, etc.

[Riven]

Wouldn't it be fastest (least cache misses) to only work on scanlines (no columns)

1. blur on scanline
2. transpose pixels
3. blur on scanline
4. transpose pixels

[DzzD]

Wouldn't it be fastest (least cache misses) to only work on scanlines (no columns)

1. blur on scanline
2. transpose pixels
3. blur on scanline
4. transpose pixels

as working with scanline is always a lot faster I suppose you are right, sure it will.


like a common error when dealing with int buffer Image wich is : (EDIT: or any two dimensional array using "a single dimensional array."..)

1   2   3

for(x=0;x<w;x++)  for(y=0;y<h;y++)   pix[x+y*w]=something

;
 
instead of

 

1   2   3

for(y=0;y<h;y++)    for(x=0;x<w;x++)     pix[x+y*w]=something;

[andre90boss]

thanks for the replies!

i will try to follow yours suggestions
in the worst case i will post again 

[pjt33]

Wouldn't it be fastest (least cache misses) to only work on scanlines (no columns)

1. blur on scanline
2. transpose pixels
3. blur on scanline
4. transpose pixels

Why? You're going to get your cache misses in the transpose operations rather than the blurring, aren't you?

[Riven]

Why? You're going to get your cache misses in the transpose operations rather than the blurring, aren't you?

Lets say the image is 1024 pixels wide, so each scanline is exactly one page (4K).

If you blur 'radius' is 4 pixels, you need 4+1+4=9 pixel reads for each pixel write. When reading/writing columns, you have to continuously read from 9 different pages for each pixel write. Something tells me the CPU (or JVM) won't find the 'fast path' for such code.

Anyway, I'll benchmark it properly.

[Hansdampf]

If you blur 'radius' is 4 pixels, you need 4+1+4=9 pixel reads for each pixel write.

The speed of the algo is independant from the blur radius (Summed area tables)

[Hansdampf]

This is 8 years old code, so please don't shoot me.
I know there is a better way to do this (without using a buffer image of the same size), but this works.
At least for blurring integer data, easily extendable to ARGB.

the Screen class is basically

1   2   3   4

class Screen{ int[] m; //holds the pixel raster int w,h; //width and height }

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   38   39   40   41   42   43   44   45   46   47   48   49   50   51   52   53   54   55   56   57   58   59   60   61   62   63

public static void doPreComputation(Screen src, Screen dst) {       int[] s = src.m;       int[] d = dst.m;       int i = 0;       int w = src.w;       int h = src.h;       for (int y = 0; y < h; y++) {          for (int x = 0; x < w; x++) {             int tot = s[i];             if (x > 0)                tot += d[i - 1];             if (y > 0)                tot += d[i - w];             if (x > 0 && y > 0)                tot -= d[i - w - 1];             d[i] = tot;             i++;            }       }    }        public static void doBoxBlur(Screen src, Screen dst, int w, int h, float fak) {       int ww = src.w;       int hh = src.h;       int maxw = ww - 1;       int muli = (int) ((2 << 15) * 1.f / (w * h * 4) * fak);       int[] m = src.m;       int[] dstmem = dst.m;       int offset = 0;       for (int y = 0; y < hh; y++) {          int topy = y - h;          if (topy < 0)             topy = 0;          else if (topy >= hh - 1)             topy = hh - 1;          topy *= ww;          int bottomy = y + h;          if (bottomy < 0)             bottomy = 0;          else if (bottomy >= hh - 1)             bottomy = hh - 1;          bottomy *= ww;          for (int x = 0; x < ww; x++) {             int leftx = x - w;             if (leftx < 0)                leftx = 0;             else if (leftx >= maxw)                leftx = maxw;             int rightx = x + w;             if (rightx < 0)                rightx = 0;             else if (rightx >= maxw)                rightx = maxw;             int tot = m[rightx + bottomy] + m[leftx + topy] - m[leftx + bottomy] - m[rightx + topy];             tot *= muli;             tot >>= 16;             if (tot > 255)                tot = 255;             dstmem[offset++] = tot;          }       }    }