Rust implementations of Fast Fourier Transform convolution and correlation for n-dimensional arrays

Rhys Newell

Last update: Jan 5, 2023

Related tags

Game development fftconvolve

Overview

fftconvolve

Rust implementations of Fast Fourier Transform convolution and correlation for n-dimensional arrays

Examples

1-dimensional

use fftconvolve::{fftconvolve, Mode}

let in1 = Array1::range(1.0, 4.0, 1.0);
let in2 = Array1::range(6.0, 3.0, -1.0);
let out = fftconvolve(&in1, &in2, Mode::Full).unwrap();
let expected = Array1::<f64>::from_vec(vec![6., 17., 32., 23., 12.]);
out.iter().zip(expected.iter()).for_each(|(a, b)| assert_aclose!(*a, *b, 1e-6));

2-dimensional

use fftconvolve::{fftconvolve, Mode}

let mat = Array2::from_shape_vec((3, 3), 
    vec![
        0.0, 0.0, 0.0,
        0.0, 1.0, 0.0,
        0.0, 0.0, 0.0,
    ]).unwrap();
let kernel = Array2::from_shape_vec((2, 3), 
    vec![
        1., 2., 3., 
        4., 5., 6.,
    ]).unwrap();
let output = fftconvolve(&mat, &kernel, Mode::Full).unwrap();
let expected = Array2::from_shape_vec((4, 5), 
    vec![
        0., 0., 0., 0., 0., 
        0., 1., 2., 3., 0., 
        0., 4., 5., 6., 0.,
        0., 0., 0., 0., 0.,  
    ]).unwrap();
output.iter().zip(expected.iter()).for_each(|(a, b)| assert_aclose!(*a, *b, 1e-6));

Fast minecraft scanner 3

cCheck A util for scanning minecraft servers. Accepts JSON output from Masscan and pings all services found, checking for minecraft servers. Written i

21 Jan 3, 2023

Blazingly Fast 3D ASCII Rubik's Cube

rs-cube Blazingly Fast 3D ASCII Rubik's Cube Screenshot Installation Homebrew brew tap doprz/rs-cube brew install rs-cube Cargo cargo install rs-cube

8 Apr 2, 2023

Victorem - easy UDP game server and client framework for creating simple 2D and 3D online game prototype in Rust.

Victorem Easy UDP game server and client framework for creating simple 2D and 3D online game prototype in Rust. Example Cargo.toml [dependencies] vict

27 Jan 7, 2023

Abstreet - Transportation planning and traffic simulation software for creating cities friendlier to walking, biking, and public transit

A/B Street Ever been stuck in traffic on a bus, wondering why is there legal street parking instead of a dedicated bus lane? A/B Street is a project t

6.8k Jan 9, 2023

"putzen" is German and means cleaning. It helps keeping your disk clean of build and dependency artifacts safely.

Putzen "putzen" is German and means cleaning. It helps keeping your disk clean of build and dependency artifacts safely. About In short, putzen solves

2 Jul 4, 2022

Plugins and helpful methods for using sepax2d with Bevy for 2d overlap detection and collision resolution.

bevy_sepax2d Plugins and helpful methods for using sepax2d with Bevy for 2d overlap detection and collision resolution. Compatible Versions bevy bevy_

7 Nov 14, 2022

This is the core library with the full abstraction and implementation of the Minecraft protocol and logic. (Currently WIP)

MineRust (WIP) This is the core library with the full abstraction and implementation of the Minecraft protocol and logic. This project is currently WI

2 Nov 20, 2022

Rust-and-opengl-lessons - Collection of example code for learning OpenGL in Rust

rust-and-opengl-lessons Project requires Rust 1.31 Collection of example code for learning OpenGL in Rust 00 - Setup 01 - Window 02 - OpenGL Context 0

348 Dec 11, 2022

A Rust wrapper and bindings of Allegro 5 game programming library

RustAllegro A thin Rust wrapper of Allegro 5. Game loop example extern crate allegro; extern crate allegro_font; use allegro::*; use allegro_font::*;

80 Dec 31, 2022

Comments

Warp mode

Hey Is there any way to "warp" convolution? I mean, when kernel is reaching outside, missing values are taken from the opposite edge or corner. I've tried to manually extend ndarray ( add last rows behind first... ), but without any success. If you are wondering I just need to "tunnel entities through walls" in discrete version of Game of Life. Thanks in advance

opened by HVisMyLife 2

Consider switching to easyfft

I've created a wrapping library called easyfft that provides the same ergonomics as matlab and the like. Let me know what you think. Happy for any feedback.

commit 6f49e9cbd89fe55ab9679197ac78a8974f6995c1 (HEAD -> main, origin/main, origin/HEAD)
Author: Walter Smuts <[email protected]>
Date:   Fri Nov 25 16:31:21 2022 +0700

    Switch to easyfft instead of plain rustfft

    easyfft is a ergonomic wrapper around rustfft that manages the planner
    for you (among other things). Previously, each call to the convolution
    function would create a new planner. Now easyfft manages the planner in
    the background, re-using the planner on successive calls from the same
    thread.

    Future releases of easyfft might also remove the need to allocate a
    scratch buffer for each call, re-using the buffer where appropriate.

    Caveat:
    easyfft stores the planner in thread-local storage, meaning this it's
    currently not a performance improvement for libraries/applications that
    create new threads for each fft call, instead incurring a slight
    performance overhead.

commit 8aaebb44042550b0fea255f469b3d96c2936e778
Author: Walter Smuts <[email protected]>
Date:   Fri Nov 25 16:25:03 2022 +0700

    Apply rustfmt

opened by WalterSmuts 1

Choosing optimal arrays size

What array size to choose? I understand, that it should be a power of 2, but it seems otherwise, eg. somewhat random, with huge fps drops across values...

opened by HVisMyLife 3
Upgrade to easyfft v0.3

Unfortunately this requires an extra Default trait bound which results in requiring a major version change for fftconvolve.

Practically it's not an issue since all elements that you'd want to convolve would implement Default, but it's a bit annoying.

Default is required for initializing the scratch-buffer, which is strictly not necessary but requires changes to rustfft. It's currently pending this issue in rustfft: https://github.com/ejmahler/RustFFT/issues/105

opened by WalterSmuts 2

Owner

Rhys Newell

Bioinformatics Software Engineer @ Microba. Awaiting for my PhD to be examined. Specialises in software development and analysis of big genomic data

GitHub

Rust implementations of Fast Fourier Transform convolution and correlation for n-dimensional arrays

Related tags

Overview

fftconvolve

Examples

1-dimensional

2-dimensional

You might also like...

Fast minecraft scanner 3

Blazingly Fast 3D ASCII Rubik's Cube

Victorem - easy UDP game server and client framework for creating simple 2D and 3D online game prototype in Rust.

Abstreet - Transportation planning and traffic simulation software for creating cities friendlier to walking, biking, and public transit

"putzen" is German and means cleaning. It helps keeping your disk clean of build and dependency artifacts safely.

Plugins and helpful methods for using sepax2d with Bevy for 2d overlap detection and collision resolution.

This is the core library with the full abstraction and implementation of the Minecraft protocol and logic. (Currently WIP)

Rust-and-opengl-lessons - Collection of example code for learning OpenGL in Rust

A Rust wrapper and bindings of Allegro 5 game programming library

Comments

Warp mode

Consider switching to easyfft

Choosing optimal arrays size

Upgrade to easyfft v0.3

Owner

Rhys Newell

Rust-lang Continuous Wavelet Transform(CWT) library inspired by fCWT.

Transform your terminal into an art canvas where you can draw stuff!

Transform tagged Markdown string to HTML during build time.

Rollback-safe implementations and utilities for Bevy Engine

A safe, fast and cross-platform 2D component-based game framework written in rust

Bindings to TinyGL, a Small, Free and Fast Subset of OpenGL

A fast 24 points game solver written in rust.

🦅🦁 Fast, simple 2D text renderer for wgpu

A sandbox library for making FAST voxel games

CLI game to see how fast you can guess the language of a code block!