This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.
Because the FFT is a divide-and-conquer algorithm, the various steps can be implemented in multiple passes in a shader by rendering the result of each pass to a texture. These steps are called butterflies, because of the shape of the data-flow diagram.
The FFT algorithm recursively breaks down a DFT of composite size N = n1n2 into n1 smaller transforms of size n2.
These smaller DFTs are then combined with size n1 butterflies, which themselves are DFTs of size n1 (performed n2 times on corresponding outputs of the sub-transforms) pre-multiplied by roots of unity (known as twiddle factors).5
The application employs four 2D textures: two for the ping-pong operations, one for the source data (for each pass), and one for holding the indices and weights for performing the butterfly steps.
The textures used for ping-ponging are marked as either a RenderTarget texture or a source depending on whether they are used as destinations or sources in the current pass.
This enables the shader to use the output of the previous pass as input for the current pass. Here are the steps to implement the FFT algorithm.
1. Compute the indices and weights for performing the butterfly operations.
2. Compute the log2(Width) horizontal butterflies.
3. Compute the log2(Height) vertical butterflies.
If the height and width of the image are equal, only one texture can be used for the butterfly values, for both the horizontal and vertical passes. Also note that in the vertical butterfly pass the input is the result of the horizontal butterfly pass.
In each butterfly pass the current pixel is combined with another pixel using a complex multiply and add operation and written to the current location. In other words if the current pixel is a, then
a = a + wb
where w is a complex number representing the weight and b is some other pixel. Each texel of the butterfly texture contains the locations of a, b and the value of w and passed to the shader by the application.
Note that for simplicity, only gray scale images are considered in the current implementation. However, extending the algorithm to multiple color channels is straightforward and only requires more textures for additional channels.