On Thu, 1 Oct 2009, IOhannes m zmoelnig wrote:
Mathieu Bouchard wrote:
Well, if you want to apply any amount of blur, of any shape of blur, in always the same amount of time, there's only one way that I know about, and it's using Fourier transforms.
or convolution which is just the same.
wow, I can't believe you just wrote that.
Well, anyway: there are two main ways to perform a convolution, and the usual way is by making each resulting pixel using a formula long like the size of the convolution-kernel, or else you can use three FFT and three or four ordinary multiplications, as if you were applying some kind of reverb on audio. If your convolution kernel is 20-by-20 or 100-by-100, if it's square, circular, doughnut-shaped, penguin-shaped, if it's hard-edged, antialiased, feathered, this algorithm doesn't care and will do the job in always the same amount of time. That's what I mean.
The reason I mention those blurs, is that if one wants to apply variable amounts of blur in realtime, that is readily visible from far away, and that looks what a lens or fog effect would do (that is, not a square kernel), then the only sensible shortcut is the FFT.
The Big-O notation classifies this as being in n*log(n) time for an image area of n pixels, whereas classical convolution takes n*m time for a kernel area of m pixels (or the nonzero kernel area, if you do this optimisation).
(note: Last time we saw each other is at the conference where I demonstrated this FFT effect.)
_ _ __ ___ _____ ________ _____________ _____________________ ... | Mathieu Bouchard, Montréal, Québec. téléphone: +1.514.383.3801