Started by Sep 09 2012 11:37 AM

,
7 replies to this topic

Posted 09 September 2012 - 11:37 AM

Would this just be plain old a fourier series? It's been a long time since my last math course.

Basically, I would like to have a small number of coefficients that I can use to represent a function that varies with the angle around a point in a 2d plane. This sounds like what spherical harmonics are often used for (global illumination affecting a point) but with one less dimension.

Could anyone suggest a website/tutorial somewhere that could show me how to do this? I have an engineering math background, but it's been about 15 years since I touched it :-).

Basically, I would like to have a small number of coefficients that I can use to represent a function that varies with the angle around a point in a 2d plane. This sounds like what spherical harmonics are often used for (global illumination affecting a point) but with one less dimension.

Could anyone suggest a website/tutorial somewhere that could show me how to do this? I have an engineering math background, but it's been about 15 years since I touched it :-).

Cascade Quest - IceFall Games - Dev blog - twitter - youtube

Posted 09 September 2012 - 06:12 PM

Would this just be plain old a fourier series?

Yes, that's exactly what it is. I don't know of any websites or tutorials that could help you. I also studied this in school 15 years ago, but I happen to remember it.

Try to read just anything you can find on it and it will probably all come back. If it doesn't, feel free to ask more specific questions and I'll try to help.

Posted 10 September 2012 - 12:31 PM

Thanks Alvaro.

I found this slide deck:

http://www.cdeep.iitb.ac.in/nptel/Electrical%20Engineering/Power%20System%20Protection/digital_protection/DPLectures/lec32.pdf

That helped me code up what I want (a series of coefficients that lets me approxiate an arbitrary function).

I found this slide deck:

http://www.cdeep.iitb.ac.in/nptel/Electrical%20Engineering/Power%20System%20Protection/digital_protection/DPLectures/lec32.pdf

That helped me code up what I want (a series of coefficients that lets me approxiate an arbitrary function).

Cascade Quest - IceFall Games - Dev blog - twitter - youtube

Posted 11 September 2012 - 08:12 PM

I was using this to try to generate terrain reflecions in water. I wrote up a brief article describing my findings so far:

http://mtnphil.wordpress.com/2012/09/12/faking-water-reflections-with-fourier-coefficients/

http://mtnphil.wordpress.com/2012/09/12/faking-water-reflections-with-fourier-coefficients/

Cascade Quest - IceFall Games - Dev blog - twitter - youtube

Posted 12 September 2012 - 12:51 AM

I think I can help with the performance issues.

Let's say you have a unit-vector (x,y) that points in a direction, and you want to evaluate a Fourier series up to a few terms at that particular direction. The naive thing to do (and what you seem to be doing) is:

Notice how C_1 is just x and S_1 is just y, so you could skip going through alpha for those terms. Now it turns out that

C_2 = cos(2*alpha) = cos(alpha)*cos(alpha) - sin(alpha)*sin(alpha) = x*x - y*y

S_2 = sin(2*alpha) = 2*cos(alpha)*sin(alpha) = 2*x*y

Similarly, you can compute all the terms in your expression without ever going through alpha, so you don't need to call atan2, sin or cos even once.

The easiest way of getting the formulas right is to think of the complex number z = cos(alpha)+i*sin(alpha) = x+i*y. Now z^n = cos(n*alpha)+i*sin(n*alpha). So by repeated multiplication by z you get all the terms you need.

That's probably enough detail for you, but if it isn't feel free to ask about whatever part isn't clear.

Let's say you have a unit-vector (x,y) that points in a direction, and you want to evaluate a Fourier series up to a few terms at that particular direction. The naive thing to do (and what you seem to be doing) is:

alpha = atan2(y,x); result = C_0 + C_1*cos(alpha) + S_1*sin(alpha) + C_2*cos(2*alpha) + S_2*sin(2*alpha) + ...;

Notice how C_1 is just x and S_1 is just y, so you could skip going through alpha for those terms. Now it turns out that

C_2 = cos(2*alpha) = cos(alpha)*cos(alpha) - sin(alpha)*sin(alpha) = x*x - y*y

S_2 = sin(2*alpha) = 2*cos(alpha)*sin(alpha) = 2*x*y

Similarly, you can compute all the terms in your expression without ever going through alpha, so you don't need to call atan2, sin or cos even once.

The easiest way of getting the formulas right is to think of the complex number z = cos(alpha)+i*sin(alpha) = x+i*y. Now z^n = cos(n*alpha)+i*sin(n*alpha). So by repeated multiplication by z you get all the terms you need.

That's probably enough detail for you, but if it isn't feel free to ask about whatever part isn't clear.

Posted 12 September 2012 - 01:30 AM

Thanks! I've got it down from 65 to about 31 shader instructions using a slightly different method. I'll try yours and see what it gives me.

edit: your post was very helpful, I've got it down to 22 instructions for 8 coefficients. Yay!

edit: your post was very helpful, I've got it down to 22 instructions for 8 coefficients. Yay!

**Edited by phil_t, 12 September 2012 - 02:09 AM.**

Cascade Quest - IceFall Games - Dev blog - twitter - youtube

Posted 12 September 2012 - 10:28 AM

They are probably cheaper instructions as well (I doubt a GPU can do atan2 in a single cycle).

**Edited by alvaro, 12 September 2012 - 10:38 AM.**

Posted 12 September 2012 - 11:59 AM

Yeah, that estimation already takes that into account. An atan2 ends up taking 21 "instruction slots", and a sincos takes 8.

Cascade Quest - IceFall Games - Dev blog - twitter - youtube