The FFT on a GPU

The Fourier transform is a well known and widely used tool in many scientic and engineering elds. The Fourier transform is essential for many image processing techniques, including ltering, manip-ulation, correction, andcompression. As such, thecomputer graphicscommunitycould benet greatly from such a tool if it were part of the graphics pipeline. As of late, computer graphics hardware has become amazinglycheap, powerful, and exible. This paper describes how to utilize thecurrent generation ofcards to perform the fast Fourier transform (FFT) directly on thecards. We demonstrate a system thatcan synthesize an image byconventional means, perform the FFT, lter the image, and nally apply the inverse FFT in well under 1 second for a 512 by 512 image. This work paves the way for performingcomplicated, real-time image processing as part of the rendering pipeline.