ImageTank Community

ImageTank
Print

Using FFTW with DTSource

Updated

FFTW (site) is a widely used software library to compute the Discrete Fourier Transform.

The FFTW library is based on creating a data structure called a plan that is created based on the dimensions, if it is a forward or backward transform and the pointer for the input and output data. This is done to limit memory allocations and pre compute data structures.

This shows how to create two functions, the FFT for forward and iFFT for the backward transform. These are not optimal if you plan on calling the FFT multiple times but show how to use the DTSource array library with the FFTW library. Note that this is for the 2D fft. Change the plan function if you are doing 1D fft.

#include <fftw3.h>

DTMutableDoubleComplexArray FFT(const DTDoubleComplexArray &A)
{
    int m = int(A.m());
    int n = int(A.n());
    DTMutableDoubleComplexArray toReturn(m,n);
    fftw_complex *in = (fftw_complex *)A.Pointer();
    fftw_complex *out = (fftw_complex *)toReturn.Pointer();
	
    fftw_plan p = fftw_plan_dft_2d(n, m, in, out, FFTW_FORWARD, FFTW_ESTIMATE);
    fftw_execute(p);
    fftw_destroy_plan(p);

    return toReturn;
}

And the inverse

DTMutableDoubleComplexArray iFFT(const DTDoubleComplexArray &A)
{
    int m = int(A.m());
    int n = int(A.n());
    DTMutableDoubleComplexArray toReturn(m,n);
    fftw_complex *in = (fftw_complex *)A.Pointer();
    fftw_complex *out = (fftw_complex *)toReturn.Pointer();
	
    fftw_plan p = fftw_plan_dft_2d(n, m, in, out, FFTW_BACKWARD, FFTW_ESTIMATE);
    fftw_execute(p);
    fftw_destroy_plan(p);
	
    return toReturn;
}

Note that when these

Lets dig into the details of this a little bit. The DTDoubleComplexArray is a class that is in many ways similar to DTDoubleArray. It wraps around an underlying data store that contains the array as a sequence of (real,imag) values for each index in a 1,2 or 3 dimensional array.

Getting the data

fftw_complex *in = (fftw_complex *)A.Pointer();

A.Pointer() gives the pointer to the underlying data for the complex array. This uses the same memory layout for a number as FFTW so you can cast that pointer into a fftw_complex pointer without problems.

Memory ownership

Note that the fftw_plan object does not copy the data but instead shares the memory with the DTDoubleComplexArray object. That means that the DTDoubleComplexArray needs to stay valid while you use the plan. Here it happens because the fftw_destroy_plan function is called before the array goes out of scope.

Layout

FFTW uses Row Major layout for memory, but DTSource uses Column Major. This is the reason why n goes before m in the line

fftw_plan p = fftw_plan_dft_2d(n, m, in, out, ...

Creating a complex array

The input and output are complex arrays. To convert your array to a complex array use

DTMutableDoubleComplexArray c = ConvertToDoubleComplex(d);

If d is a DTDoubleArray. It returns a mutable array but you can hand that into functions that expect a DTDoubleComplexArray. Make sure that you include that header file at the top of your source file

#include "DTDoubleComplexArray.h"

Converting from Complex to Real

To go back you can use

DTMutableDoubleArray real = RealPart(c);
DTMutableDoubleArray imag = ImaginaryPart(c);

Installing FFTW

Download fftw, go into the download directory and run the following commands in the terminal. The first command might be different depending on where your fftw was downloaded and uncompressed.

cd ~/Downloads/fftw-3.3.9/
./configure
make -j 5
sudo make install

You can test to make sure that things are installed by doing

ls /usr/local/include/
ls /user/local/lib/

Xcode

Including libfftw3 in your Xcode project includes two steps. You need to add an entry to the header search path so that you can include the fftw3.h header file and you need to include the library so that your program will link against it.

Add the header path. Note that you select the entry in the “Project” tab

Add the library

To include the library go into the main project entry (top of the list in the project folder listing), select your target, select the Build Phases tab and add the library into the “Link Binary With Libraries”

Note that when you hit the + button you get the following window.

Select “Add Files…” here

To go into the /usr/local/lib/ folder, you need to hit the “/” to get the following window. Make sure that you are not typing in the search bar. This is one of the hidden tricks to go to a particular folder. The /usr/ folder is not visible in the Finder by default. You can also show this folder by clicking shift-command-G.

Select libfftw.a

Search path for libraries

On some systems (Xcode 12) this is not enough to find the libary. In the same location as you used for the header search path there is a library search path. Add /usr/local/lib/ into that as well.

Updated
On This Page