Inspired by Evgeny Demidov’s ink droplet simulation, while not content with his Jacobi iterative solver for Poisson equation, I try to use FFT(Fast Fourier Transform) to solve this problem like this paper.

To compute FFT with WebGL, this method is employed. Two key process in this method are *Index Magic* and *Frequency Compression*. *Index Magic* is so magic and it can be extended to other radices, even vector-radix. While *Frequency Compression* can be improved in 2D case. In that paper, two real functions are tangled, FFTed, untangled in one direction then in other direction. Actually two real functions only need to be tangled once before 2D FFT, then untangled once, because the conjugate symmetry also exists in 2D FFT. Using notations in that paper, we can find

So vector-radix FFT can be employed and the whole process can be simplified.

Thank Evgeny Demidov for his kindly remarks.

### Like this:

Like Loading...

*Related*

Hi, this demo doesn’t seem to work anymore, at least on the browsers that I’ve tried (latest versions of Chrome & Firefox). I guess maybe the WebGL spec changed. Do you know what the issue is? I’m very interested in your implementation of FFT in WebGL, so it would be interesting to see a working version.

It seems the computer I was testing on did not have support for the OES_texture_float_linear extension, which is why it didn’t work, sorry.

Does the fragment shader “fs-fftv” do 2D-fft and inverse 2D-fft? I tried to get my head around the code and the papers, but didn’t quite understand how it’s implemented.

fs-fftvuses vector-radix fft. It is not included in the paper. You start atfs-fft, which compute 1D fft for each row or column depending on the uniformdim. uniform sampler2DW_MandW_Nare precomputed complex coefficients.