![img](./images/icon_long.png) # Table of Contents 1. [Installation](#org8e2e1ee) 2. [Notes](#org88d7ed4) 3. [Reference](#org59f1579) 1. [Public methods](#orgf8d976a) 1. [`FFT.fft(data: Array) -> Array`](#org82c6d20) 2. [`FFT.ifft(data: Array) -> Array`](#org8f8ba68) 3. [`FFT.reals(data: Array) -> Array`](#org2446d66) 4. [`FFT.imags(data: Array) -> Array`](#org38e4f06) 5. [`FFT.ensure_complex(data: Array) -> Array`](#orgb19154d) 2. [Internal methods](#orgae1faf8) 1. [`FFT.conjugate(amplitudes: Array) -> Array`](#org757ca89) 2. [`FFT.keyed(data: Array, key: String) -> Data`](#orgf908bfc) [![img](https://awesome.re/mentioned-badge.svg)](https://github.com/godotengine/awesome-godot) ![img](https://img.shields.io/github/license/tavurth/godot-simple-fps-camera.svg) ![img](https://img.shields.io/github/repo-size/tavurth/godot-simple-fps-camera.svg) ![img](https://img.shields.io/github/languages/code-size/tavurth/godot-simple-fps-camera.svg) Fast Fourier Transform in GDScript Mostly modified from [The javascript FFT on rosetta code](https://rosettacode.org/wiki/Fast_Fourier_transform#JavaScript). # 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. ```gdscript 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. ```gdscript 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? ```shell 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: ```gdscript 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) -> Array` Forward transformation from data-space into fourier-space. ### `FFT.ifft(data: Array) -> Array` Reverse transformation from fourier-space into data-space. ### `FFT.reals(data: Array) -> Array` Returns the real part of each data point. ### `FFT.imags(data: Array) -> Array` Returns the imaginary part of each data point. ### `FFT.ensure_complex(data: Array) -> Array` Ensure that all data items in the array are Complex numbers. ## Internal methods ### `FFT.conjugate(amplitudes: Array) -> Array` Flips the sign of each amplitude ### `FFT.keyed(data: Array, key: String) -> Data` Returns data[idx][key] for each index.