Previous page : 2D FFT explanation
We will here look at some of the code for the 2D FFT
The function epicycles() is the star of the show. The data is split into a real part from the horizontal data and an imaginary part from the vertical data. The data is then centred and padded to be a
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
gunction epicycles() { if (!drawing) return; let aR = []; // The real part of the input. let aI = []; // The imaginary part of the input. let bR = []; // The fft of the real input. let bI = []; // The fft of the imaginary input. mouse.isDown = false; drawing = false; if (draw.drawnXY.length <= 2) { drawing = true; return; } // The input is centred and adjusted to // fit a power of 2 nr of data points.. draw.centredDrawnXY = copyArray(draw.drawnXY); fft.centreData(draw.centredDrawnXY); draw.shownXY = padData(draw.centredDrawnXY); // Split the adjusted input data into a real and // an imaginary part. for (let i = 0; i < draw.shownXY.length; i++) { aR.push([draw.shownXY[i][0], 0]); aI.push([0, draw.shownXY[i][1]]); } |
We do the FFTs, then add vs subtract the result as described on the previous page.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Then we do the fft of the two parts separately. bR = fft.fft(aR); bI = fft.fft(aI); // This will store the combined result. let c = []; // Add the vectors from the two fft's. // This is for the anti clockwise motion. for (let i = 0; i < draw.shownXY.length; i++) { c.push([bR[i][0] + bI[i][0], bR[i][1] + bI[i][1]]); } // Add the vectors from the two fft's. // This is for the anti clockwise motion. for (let i = 1; i < draw.shownXY.length; i++) { c.push([bR[i][0] - bI[i][0], bR[i][1] - bI[i][1]]); } |
We then normalize the result and set the depth (the number of pairs of hands) to half the size of the dataset.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
// Normalize the combined result. fft.data = fft.normalize(c, 1 / 2); // Set the depth (number of circles shown). depth = aR.length / 2; numberOfCirclesInput.max = depth; numberOfCirclesInput.value = depth; running = true; firstTurn = true; cancelAnimationFrame(raf); raf = requestAnimationFrame(theMainLoop); } |
For the FFT we need some complex algebra.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Some complex operations. let complex = { add: function (z, w) { return [z[0] + w[0], z[1] + w[1]]; }, sub: function (z, w) { return [z[0] - w[0], z[1] - w[1]]; }, mul: function (z, w) { return [z[0] * w[0] - z[1] * w[1], z[0] * w[1] + z[1] * w[0]]; }, }; |
Then we have the actual FFT.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
// The fft and helping functions. let fft = { data: [], // For the returned values from the fft. // The main fft-function. fft: function (b, invert = false) { let a = copyArray(b); let n = a.length; if (invert) { let nI = 1 / n; for (let i = 0; i < n; i++) { a[i][0] *= nI; a[i][1] *= nI; } } this.fftAux(a, invert); return a; }, // This is used by the above. Is never called directly. fftAux: function (a, invert = false) { let n = a.length; let nd2 = Math.round(n / 2); if (n === 1) return; let a0 = Array(nd2) .fill(0) .map((v, i) => a[2 * i]); let a1 = Array(nd2) .fill(0) .map((v, i) => a[2 * i + 1]); this.fftAux(a0, invert); this.fftAux(a1, invert); let ang = ((2 * PI) / n) * (invert ? 1 : -1); let w = [1, 0]; let wn = [cos(ang), sin(ang)]; for (let i = 0; i < nd2; i++) { let wa1 = complex.mul(w, a1[i]); a[i] = complex.add(a0[i], wa1); a[i + nd2] = complex.sub(a0[i], wa1); w = complex.mul(w, wn); } }, |
Up a level : Fast Fourier transformPrevious page : 2D FFT explanation
Last modified: