WebGL Demo: FFT-based droplet simulation

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

$F(u,v)_R = \frac12 \left(H(u,v)_R+H(M-u,N-v)_R\right)$

$F(u,v)_I = \frac12 \left(H(u,v)_I-H(M-u,N-v)_I\right)$

$G(u,v)_R = \frac12 \left(H(u,v)_I+H(M-u,N-v)_I\right)$

$G(u,v)_I = -\frac12 \left(H(u,v)_R-H(M-u,N-v)_R\right)$

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

Thank Evgeny Demidov for his kindly remarks.