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 keyframe interpolation, I didn't think of compression. Despite my enthusiasm, my teacher didn't show much interest in 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).
![](gfx02.png)
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
![](for00.png)
![](for01.png)
where the values
![](for04.png)
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 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
![](for07.png)
These are the Fourier series (that you probably know already, like many of their cousins - DFT, DCT, Spherical Harmonics, Laplace, etc). Every axis
![](for00.png)
![](for03.png)
Now, to get the coordinates
![](for04.png)
![](for05.png)
![](for06.png)
So, computing the coordinates
![](for04.png)
The concept
Memory refreshed? Ok, let's go on.
Now, by rotating the vector f by the matrix
![](for09.png)
![](for04.png)
![](for00.png)
![](for04.png)
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
![](for04.png)
Next the experiment was to start removing coefficients and see what happened. This in an image using only 80% of the coefficients (40):
![](gfx00.png)
and this is what happens when using just 20% of the data (10 coefficients):
![](gfx01.png)
Results are not as bad as you would 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
![](for04.png)
The code
This live example in Shadertoy shows the approximation of a shape by an increasing number of Fourier coefficients: https://www.shadertoy.com/view/ltKSWDM.
And this one shows the interpolation in action: https://www.shadertoy.com/view/4lGSDw