Gamasutra is part of the Informa Tech Division of Informa PLC

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.


Gamasutra: The Art & Business of Making Gamesspacer
Sponsored Feature: Implementation of Fast Fourier Transform for Image Processing in DirectX 10
arrowPress Releases
December 14, 2019
Games Press
View All     RSS







If you enjoy reading this site, you might also want to check out these UBM Tech sites:


 

Sponsored Feature: Implementation of Fast Fourier Transform for Image Processing in DirectX 10


April 16, 2009 Article Start Previous Page 2 of 3 Next
 

Implementation Details

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.

---

5 http://en.wikipedia.org/wiki/Butterfly_(FFT_algorithm)


Article Start Previous Page 2 of 3 Next

Related Jobs

SimX, Inc.
SimX, Inc. — Mountain View, California, United States
[12.13.19]

Remote or Local Unity VR Engineer
Disbelief
Disbelief — Chicago, Illinois, United States
[12.13.19]

Senior Programmer, Chicago
Disbelief
Disbelief — Chicago, Illinois, United States
[12.13.19]

Junior Programmer, Chicago
Game Closure
Game Closure — San Francisco, California, United States
[12.13.19]

Senior Game Engineer





Loading Comments

loader image