Fast Fourier Transform

#1 you mean something like this? http://www.gamasutra.com/gdce/jensen/jensen_01.htm

#2 Mike,

I always use "Eric Weisstein's world of mathematics" as a first call for math related issues.

You could try FFT. You could also check out the references at the bottom of the page.

You could also try FFTW.

You could also try VTerrain.org. Select the CHENGINE link and download his code. He has uses FFTW for in his engine.

Hope this helps a little.

- Melv.

p.s. Please tell me that you are implementing a deep water algorithm for Torque!

#3 Ooh man, that would be really really cool. =)

I don't think the framerate would be very good tho.. hehe.

Honestly, I really don't have a clue how the fourier transformation completely works. I came upon this link and one of my engineering friends were trying to explain to me how Compact Disks work. (Now I have a very elementary idea of how CDs work. =P) But I still don't know much about the fourier transformation.

I'm assuming if you can use FFT for things like water waves and whatnot, I'm sure a similar algorightm could be used for smoke, or falling snow or even stuff like large rolling fields of grass, perhaps? Probably not the FFT itself, but some other matrix manipulation of intense CPU proportions similar to it.

For things like water I would think that using some kind if gaussean algo would be more... friendly? Like for example when an object hits the water there is a corresponding 'ring' of waves that originate from the impact and dissepate over time|distance.

I heard Epic has put some kind of neat smoke algorithms for trailing smoke for their new Unreal engine, like for example when you shoot a rocket and a trail of smoke is left behind, you shoot thru that trail of smoke and it swirls accordingly. Anyone know more about it? Or am I taking too many drugs again?

ok, I found this, but I don't have much time to read it right now. Looks pretty interesting. It looks like FFT is also used for lots of stuff, JPEGs, Photoshop filters, weather prediction, and fluid mechanics (like turbulence, etcetera.

But it looks like most of the applications for it require some intense CPU work. Unfortunately, I still don't know much about the fourier transformation. Anyone major in fluid mechanics?

I hope nobody minds me 'polluting' this part of the board with my gabbing. =) It just seemed a little too quiet.

#4 @Alex’s first post:
Jensen’s Gamasutra article is exactly what I mean. That’s where I got the basic algorithm from. I’ve got everything working; it’s just that I have a slow FT in there. I’m having trouble implementing a FFT in there just because I haven’t been able to understand the basic principle of the FFT and why it’s faster than a classic algorithm. I know I’m missing something really basic concept here.

@Melv:
Thanks for the links I’ll check them out. The Vterrain code might be very helpful to me since code is so much easier for me understand than formulas.

I’m not building this for Torque but it would be cool to have in Torque if you don’t mind terrible FPS. J But seriously with a very small height grid with the points stretched way out it might not look too bad and would probably run fast enough to be acceptable. Hmmm…

@Alex’s second post:
Interesting thoughts on smoke rendering with the FFT. I’m sure that this could be applied to smoke but the FFT would be applied to a 3D signal rather than a 1D signal like a wave height map. This would complicate the basic formula only a tiny bit but there would be a ton more data points, assuming a similar resolution (a.k.a. frequency).

You’re right a gaussian algorithm or the like would be a lot more friendly, but I’m aiming for a closer approximation of the look of deep water waves.

That UT smoke thing sounds awesome it’d be cool to hear about how they’re doing that.

The FT is truly a fascinating animal there are so many practical applications across different disciplines for that it simply boggles the mind. It’s weird how something so un-intuitive in concept (at least to me anyway) can be so simple to use and so powerful at the same time. I guess the reason is it allows you to change the model of the problem into a model that can be much easier to work with for your problem. Not only that it allows you to change your new model back to the original problem space after you solved it. Mind blowing stuff.


Please “pollute” more. This part of the board is way too dead for my tastes.

Thanks guys for your help. Time for me to read those links.

#5 Btw, if anyone's interested you can see this little project of mine here -- you may have to login to passport to see it. It's a deep-water wave simulation screensaver.

#6 One good reference book on the FFT, especially if you are more of a mathematician than a physicist, is "Introduction to Algorithms" by Cohen, Leiserson & Rivest. It's a great book for any programming library.

Here's a quick overview of what FFT is actually doing. If anybody spots mistakes here, please correct, I'm paraphrasing and try turn the math into English, which we all know is a much harder transform than the FFT.

Think of a polynomial of order n
A(x) = A(n)x^n + A(n-1)x^n-1 + ... + A(1)x + A(0).

That's the "coefficeint representation", which can also be viewed as a vecotr,

Vector form is great for adding and subtracting polynomials.
A(x) + B(x) = C(x) by adding the vector components. Easy, takes n steps [O(n)]

But multiplying in this form requires a lot more work, and is O(n^2). Not trivial for large values of n.

Instead of coefficient representation, you can also completely define a polynomial of order n by evaluating it at n distinct points and using those points. This is point-value form
A(x) = <(x0, A(x0)), (x1, A(x1)), ..., (xn, A(xn))>

If you use the same points x0...xn for two polynomails, then you can added them coponentwise
A(x)+B(x) = <(x0, A(x0)+B(x0)), ...(xn, A(xn)+B(xn)>

Where this gets useful, however, is that for multiplication, you can just multiply componentwise, with one important caveat. You must have N points in the list, where N = degree(A) + degree(B). So if you multiply two 4th degree polynomials, you need 8 points.

Converting from coefficient to point form, however, is an O(n) operation. So we don't gain anything at all from doing this...

...unless we have a trick up our sleeve. It turns out that by choosing N points x0, x1, ...x2n such that N is a power of 2, and then making those N points the "nth roots of unity", we can take advantage of the mathematical properties of these roots. xk = e^(2*pi*i*k/N). It turns out that these are a group, and that xn=e^(2*pi*i\n). And if you didn't follow that, I'll just jump to the English ramifications.

The FFT takes advantage of these particular roots in a divide and conquer format. We need to solve A(x) for N points. Divide A(x) up into Ae(x) and Ao(x), one for the even terms of the polynomial, one for the odd. Now we have
A(x) = Ae(x) + x*Ao(x).
But note that all our x values are roots of unity. Since every term of Ae(x) and Ao(x) is effectively now an "x^2" term, we could evaluate them at the N/2 roots of unity. We have divided the problem into two smaller problems, each half the size. Binary search, anyone? This takes O(n*log(n)) time, which is much faster than n^2.

The inverse FFT is the operation to get from point form back to coefficient form. So, to multiply two functions, you
-Extend the degree of each to be bounded by N, where N is the next power of 2 greater than the degree of the largest polynomials - O(n)
-Do an FFT on each polynomial O(n log(n))
-Multiply componentwise - O(n)
-Inverse FFT - O(n log n)

You can do lots with Fourier transforms, but this is the root of it all. You are transforming from one representation to another, and in turn making operations faster.

I hope that clears up why this thing works. If it didn't, then just keep on using it wherever you need to. But knowing why something works is always the first step to applying it correctly.

Brian Marshall
PlayTank, Inc.

#7 I guess you havn't played UT2k3, but the game has almost no smoke. I read about the neat engine stuff, and was looking forward to checking out features like that, among others. The deal is, the rocket leaves about a 4 foot long trail of smoke, so you can't play with it.

And I think the smoke just gets pushed away, doesn't do any fancy swirling.... but this is just the way I interpreted it.

#8 Brain,

Thanks for your well thought out post. What you're saying makes sense. My confusion with all this FFT stuff seems to lie in why the following bits are true:

xk = e^(2*pi*i*k/N) 
    xn = e^(2*pi*i/n)

Can you possibly shed some light on this for me? Or maybe point me to a good book to explain this if this is too involved for discussion here.

Thanks,
Mike

#9 Hmm, has anyone already implemented some transform functions that could be plugged into, say, Tribes 2? ;) I would like to have some unique smoke trails, weapons, projectils, etc., for my T2 mod, but my math skills are not as well developed as they could be. :|

#10 I don't see the connection between smoke / fluid dynamics and the FFT. All the Fourier transform does is take things from the time domain to the frequency domain and vice versa. To translate, that means taking a sound sample and changing the sine waves into data that represents what frequencies are present (over the entire sample). So if you have a 440Hz sine wave, when you run it through the FT you will get a single tall spike at the place that represents 440Hz. Then you can shift that line, say, to 600Hz, run it back through the FT (or more properly, the inverse FT), and your sine wave has changed to 600Hz.
All of this also applies to images (they can also be made from "frequencies" e.g. 2D sine waves), and could certainly apply to 3D... but... smoke?

Well, I decided to google it, and sure enough, there are smoke effects done using FFT.
See here
Note that the method is patented, so be careful how you use it. It would take a lot of trickery to get this working at a reasonable FPS in 3D.

As far as plugging it into tribes 2, I doubt that's possible, since scripting would be too slow. FFT is rather processor-intensive, which basically means you'd slow to a crawl writing it in script even on an extremely fast machine. That's assuming you can even write the code for it (you might be able to fake it with particles).
If you want unique smoke trails, I'd recommend using the existing particle system and experimenting with it. Try using animated textures on the particles. You can get pretty creative with the T2 particle system.

#11 Thanks, John. No need to reinvent the wheel . . . :)