Looking at the page source they seem to be using the library from Project Nayuki[0]. I'm actually quite amazed at how few lines of code are required for an FFT implementation[1].
Anyway, I might give a simple draw-on-canvas website a go, give me a few hours.
If you don't need it in real time and don't have a whole lot of points, you can do discrete Fourier transforms in even less code by just doing FT instead of FFT. Modern computers are fast enough that the most straightforward O(n^2) algorithm that is immediately obvious from the definition of the discrete Fourier transform given in Wikipedia will often be fast enough. E.g., something like this in C:
typedef struct {
double r;
double i;
} complex;
void fourier(complex * x, complex * y, int np)
{
int n, k;
for (k = 0; k < np; ++k)
{
y[k].r = y[k].i = 0;
for (n = 0; n < np; ++n)
{
double c = cos(2*M_PI*k*n/np);
double s = sin(2*M_PI*k*n/np);
y[k].r += x[n].r * c + x[n].i * s;
y[k].i += -x[n].r * s + x[n].i * c;
}
}
}
20 years ago, on a middle of the road desktop, that was fast enough that I was able to do an almost real time guitar tuner with it.
I remember getting a very helpful tip as an undergrad Math major: once you start doing senior undergrad/early graduate level classes, expect each textbook page to take a long time to read. Upwards of an hour is not uncommon. And I found this to be very true in my own experience.
I'm always struck by this thought when I see code like this. It's not a lot of code, but if I had to actually go through and internalize it, it would certainly take me a while.
> It's not a lot of code, but if I had to actually go through and internalize it, it would certainly take me a while.
Oh yeah, I definitely didn't mean to imply that it was easy code. It has that elegance that you really only see in the kind of concise code that can only be written by people who really grok the underlying system (both programming and FFT).
For sure. As Brooks might say, code like that is high in "essential complexity". There's almost no boilerplate - there's a nearly 1:1 ratio of lines of code to important idea.
I don't think this exactly what you want, but you might like it anyway. You draw and it breaks it down into the 2D fourier series, and you can control the number of fourier terms which essentially acts like a crude high pass filter:
You can't just "draw" on the Fourier side because it actually consists of complex numbers, and only the magnitude is plotted. And the Fourier plot needs to be rotationally symmetric. The closest you could get is increasing or decreasing the magnitude of pixel regions.
Maybe a DCT would be more amenable to hand-editing because it's real and has no symmetry constraints.
I should have a 2d line chart, and I should be able to draw magnitude at each frequency. It rotates and filters. Right now, a line chart consists of 1 between two frequencies, and 0 elsewhere.
Or I should have a 2d image, and I draw dark/light. It reflects appropriately to get the other half, and multiplies the image (without rotating). Right now, this image looks like a donut.
I'm drawing the filter, you see. It applies the filter, and shows me:
* The source image FFT(what I drewFFT(image))
The point spread function / convolution kernel FFT(what I drew)
> I'd love to be able to draw on the Fourier side.
Notice that the direct and inverse transforms are essentially the same transformation. So you can draw on the image side and swap both images on your mind.
I don't want to draw an image. I want to draw a filter of an image. Right now, I have a rock-hard cutoff at two frequencies. I'd like to draw a curve, and have it Fourier filter based on that curve.
