fft-shader
FFT/Concolution/...
direkte Faltung: bei Inputs f1 und f2 mit größe n sei f2´ die invertierung der indizes von f2, sodass f2[0] == f2´[n] usw., dann werden f1 und f2´ so angelegt, dass sich f1[0] und f2´[n] gegenüberstehen und das skalarprodukt gebildet, dieses bildet index 0 vom neuen array f3, dann wird f2´ um einen index weitergeschoben, sodass sich f1[0] gegenüber von f2´[n-1] steht und f1[1] gegenüber von f2´[n], wieder skalarprodukt, dieses wird in f3[1] geschrieben und weiterschieben bis sich am schluss nur noch f2´[0] und f1[n] gegenüberstehen, deren skalarprodukt f3[2*n-1] ergibt. f3 ist das ergebnis der faltung und wird returned
faltung im frequenzraum: bei inputs f1 und f2 mit größe n = 2^I wird jeweils einzeln eine Fourier-Transformation angewendet, die resultierenden arrays f1´ und f2´ haben die größe n/2. Von f1´ und f2´ werden die jeweils gleichlautenden indizes multipliziert und in f3´ geschrieben (also f3´[0] = f1´[0] * f2´[0], f3´[1] = f1´[1] * f2´[1]). Auf das Ergebnis f3´ wird die inverse Fourier-Transformation angewendet. Das Ergebnis f3 hat die größe n (damit die doppelte größe von f3´) und wird returned.
Implementierungen (nicht nur) in Shader-Language: https://www.shadertoy.com/view/4dGyWD (nur FFT, 2D, für Lens-Flares)
https://github.com/Aleksoid1978/VideoRenderer/blob/master/Shaders/d3d11/ps_convolution.hlsl (hlsl, direkte Faltung mit vorgegebenen f2, wobei f2 deutlich kleiner als f1 ist, 2D, für Blur-Effekte)
https://github.com/pure-data/pure-data/blob/master/src/d_fft.c (radix-2^n algorithmus in c++ aus dem Quellcode von Pure Data, 1D, Audio-orientiert)
https://gist.github.com/jcksnvllxr80/290f284abf4112dedae63f8c7289502f (FFT in python händisch umgesetzt, für python gibt es eigentlich mehrere Implementierungen einer library die in C umgesetzt ist, deshalb ist das hier spannend um zu sehen wie der algorithmus formuliert wird, 1D und 2D, für Bildanalyse)
https://github.com/gasgiant/FFT-Ocean/blob/main/Assets/ComputeShaders/FastFourierTransform.compute (computeshader für unity, 3D, zur Meereswellen-Simulation, nur FFT)
https://github.com/johang88/TR.Stride/blob/master/TR.Stride.Ocean/FastFourierTransform.cs (fft in c# für Stride, stride-implementierung des obigen unity-projekts)
weitere mögliche herangehensweisen: FFT und IFFT in vvvv mit dem Audiopack umsetzen Vorteile: FFT schon implementiert, muss also nicht selbst passieren; Audio-rate scheduling krempel schon erledigt Nachteile: läuft dann auf der CPU; geht out of the Box nur für sound, um die Topologischen Lidardaten zu falten müssten diese vor der Transformation in Sound und danach wieder zurück gewandelt werden; hatte letztes mal das gefühl die ist nicht vollständig und es geht was verloren Die parallelen Multiplikationen würden nach wie vor performant auf der GPU laufen, die (bei radix-2^n) parallelen subtransformationen von time-domain zu frequency-domain und zurück würden aber auf der CPU bleiben
Aufgaben:
-
node20-workshops zu stride und shadern anschauen -
nochmal FFT aus dem Audiopack testen um zu schauen ob sie evtl doch vollständig ist -
falls ja, V2A und A2V Konversionen mit den Bilddaten erproben -
falls ja, frequenz-bins in shader rein und wieder rauskriegen
Edit: ausprobiert, die fft aus VL.audio verwirft tatsächlich die imaginären Anteile und gibt nur die realen raus, sodass die ifft unvollständigen Käse ausgibt weil die Hälfte fehlt, ist seltsam weil die ifft aus VL.audio imaginäre Werte erwartet
libraries:
-
fftsharp -
Naudio (basis von VL.Audio) -
FFTW.NET -
DspSharpFftw (c# implementierung der fftw-library)