## 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.

This entry was posted in Computational fluid mechanics and tagged , , . Bookmark the permalink.

### 3 Responses to WebGL Demo: FFT-based droplet simulation

1. 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.

• wildabc says:

fs-fftv uses vector-radix fft. It is not included in the paper. You start at fs-fft, which compute 1D fft for each row or column depending on the uniform dim. uniform sampler2D W_M and W_N are precomputed complex coefficients.