2D FFT how is it done? I have a texture that I want to perform the 2DFFT on and I am trying to understand the &quot;Row/Column&quot; or &quot;Column/Row&quot; idea but I am unsure if I have understood it correctly. Hoping some one can explain it a bit better from my current understanding because it seems my current understanding of it requires a lot of FFTs which does not seem right to me.
If I have a 256 by 256 texture and I perform a 2DFFT on the image. Lets say I chose columns/row order so I do columns first, so does that mean I first perform:
256 1DFFT's... one for each column &quot;image.x&quot;, containing 256 samples:
1DFFT for x = 0 -&gt; Samples: image[0,0], image[0,1] ... image[0,255]
1DFFT for x = 1 -&gt; Samples: image[1,0], image[1,1] ... image[1,255]
...
1DFFT for x = 255 -&gt; Samples: image[255,0], image[255,1] ... image[255,255]

Then I have to do another 256 1DFFT's along the rows &quot;image.y&quot;, containing 256 samples:
1DFFT for y = 0 -&gt; Samples: image[0,0], image[1,0] ... image[255,0]
1DFFT for y = 1 -&gt; Samples: image[0,1], image[1,1] ... image[255,1]
...
1DFFT for y = 255 -&gt; Samples: image[0,255], image[1,255] ... image[255,255]

So in total I do 256 + 256 = 512 1DFFTs ? Is that correct?
Yes, you are right. It is a lot of FFTs, but remember it is a lot of samples as well.
If you have a FFT algorithm with complexity $O(n \cdot log(n))$, then for the 2D scenario you will have an algorithm with complexity $O(M \cdot (N \cdot log(N)) + N\cdot (M \cdot log(M)))$
but if you express this in terms of $M \cdot N$, what you get is.
$O(M \cdot N \cdot (log(N) + log(M)))$ and finally with the log sum identity you get $O(M \cdot N \cdot log( M \cdot N ))$
The complexity in terms of number of samples is the same