Table of Contents

1. Installation
2. Notes
3. Reference
   1. Public methods
      1. FFT.fft(data: Array<float>) -> Array<Complex>
      2. FFT.ifft(data: Array<Complex>) -> Array<Complex>
      3. FFT.reals(data: Array<Complex>) -> Array<float>
      4. FFT.imags(data: Array<Complex>) -> Array<float>
      5. FFT.ensure_complex(data: Array<MaybeComplex>) -> Array<Complex>
   2. Internal methods
      1. FFT.conjugate(amplitudes: Array<Complex>) -> Array<Complex>
      2. FFT.keyed(data: Array<Dictionary>, key: String) -> Data<Any>

Fast Fourier Transform in GDScript

Mostly modified from The javascript FFT on rosetta code.

Installation

1. Install addon
2. Enable plugin from the project-settings

The singleton FFT is autoloaded at your project start, so you can simply call the static functionality as shown below.

    var result = FFT.fft([1, 1, 1, 1, 0, 0, 0, 0])
    result = FFT.fft(result)

    for item in result:
        item.log()

Notes

This is an in-place modification for speed, so if you want to ensure functional purity you can duplicate your data array before passing it into the fft or ifft functionality. The data array is also returned.

    var my_arr = [1, 1, 1, 1, 0, 0, 0, 0]
    var result = FFT.fft(my_arr.duplicate(true))
    # my_arr remains unchanged

How fast is it?

288.375 ms per 5,000 items.

Not so fast, but this can be used as an example to convert to C++, or for situations where you don't need to calculate every frame.

Alternately you can sample the data, so instead of taking every item you can take every {5th} item.

This should also be thread safe, so you can run it in the background quite easily using:

var _mutex := Mutex.new()
var _thread := Thread.new()
var _terminated := false

var my_data := []

func _thread_runner() -> void:
    while not self._terminated:
        OS.delay_msec(100)
        mutex.lock()
        FTT.ftt(my_data)
        mutex.unlock()

func _exit_tree() -> void:
    self.terminated = true
    self._thread.wait_to_finish()

func _ready() -> void:a
    thread.start(Callable(self, "_thread_runner"))

func _process(_delta: float) -> void:
    if not _mutex.try_lock():
        return

    print(my_data)
    self._mutex.unlock()

Reference

Public methods

FFT.fft(data: Array<float>) -> Array<Complex>

Forward transformation from data-space into fourier-space.

FFT.ifft(data: Array<Complex>) -> Array<Complex>

Reverse transformation from fourier-space into data-space.

FFT.reals(data: Array<Complex>) -> Array<float>

Returns the real part of each data point.

FFT.imags(data: Array<Complex>) -> Array<float>

Returns the imaginary part of each data point.

FFT.ensure_complex(data: Array<MaybeComplex>) -> Array<Complex>

Ensure that all data items in the array are Complex numbers.

Internal methods

FFT.conjugate(amplitudes: Array<Complex>) -> Array<Complex>

Flips the sign of each amplitude

FFT.keyed(data: Array<Dictionary>, key: String) -> Data<Any>

Returns data[idx][key] for each index.