website articles
fourier series

Motivation


I was introduced to the Fourier transform and series at the age of 19, and the first thing I thought was, "hey, this can be used for the 3d camera movements in my demos". Originally I was more into regular demo making instead of procedural generation and compression, so at that time I wanted to use the new toy of Fourier for key frame interpolation, I didn't think of compression. Despute my enthusiasm, my teacher didn't show much interest about the topic of interpolation. Still I programmed it (results down there) but never used it in any demo because splines were cooler then. Anyways, here it goes (much blah blah and little code this time, sorry, I wrote this back then).


38 data points interpolated with Fourier transform


The maths


You might remember from algebra courses the following idea: take a vector (or function or signal) f, and a set of axes (or "coordinate system" or "basis"), and rewrite f as a linear combination of those axes such that



where the values are called the "coordinates" of the vector f in the new system.

We could choose any coordinate system (Legendre polynomials or simple powers like in Taylor series, you name it). Instead, we take care to choose our axes such that they are orthogonal to each other. Also, we seek for a coordinate system where axes have more and more detail as n increases. There is in fact a very popular coordinate system that fulfills these requirements: the trigonometric family of functions (ie, sinus and cosinus series, that I will write as complex exponentials for a more compact representation) given by



These are the Fourier series (that you probably now already, like many of their cousins - DFT, DCT, Spherical Harmonics, Laplace, etc). Every axis is perpendicular to each other as can be manually checked by dot producing any two of the axes:

Now, to get the coordinates (called "Fourier Coefficients" when using the basis), we just have to do:

, and since we our axes are perpendicular to each other, then we can say

So, computing the coordintes of f is as simple as doing a dot product between the vector and the axes of the new coordinate system (well, their conjugate if they are complex). Just as in regular geometric vector spaces (ie, we are just applying a rotation matrix to our vector f).



The concept


Memory refreshed? Ok, let's go on.

Now, by rotating the vector f by the matrix we have transformed its representation, ie, now it's what we have to store in our demo, not f anymore. As we said, the higher order axes represent the detail structure of f, while the global structure of f gets mostly projected into the lower order axes. Assuming f will represent real world data, like camera movements or shapes, it will probably be quite ok if we only pay attention to its global shape, and we discard the rest of the information (for efficient storage and compression purposes). That means we only need to store few of the coordinates . That's what Jpeg images or Mp3 music do, so it should work for our camera paths too.


The experiments


So I quickly coded a proof of concept. I generated a random two dimensional set of 50 points. Then I computed two Fourier series, one for the x coordinate and another for the y. Each of the Fourier series gives 50 coefficients of course. When using all of them to reconstruct a signal the resulting path exactly passes thru the 50 points. Perfect! that's a good way to do camera interpolation (think of the 50 points as key frames).

Next the experiment was to start removing coefficients and see what happens. This in an image using 80% of the coefficients (40):



and this is what happens when you use 20% of the data (10 coefficients):




Results are not as bad as you could expect, because even the full set of 50 coefficients is very easily compressible, much more than the original description of f. For example, since we know that the last coordinates are going to be smaller than the first, you can actually use less bits for those. Well, there many such tricks, just have a look to the JPEG specification for more inspiration.

The code


This live example in Shadertoy shows the approximation of a shape by an increasing number of Fourier coefficeints: https://www.shadertoy.com/view/ltKSWDM.

And this one shows the interpolation in action: https://www.shadertoy.com/view/4lGSDw