-
Notifications
You must be signed in to change notification settings - Fork 91
/
FastFourierTransform.compute
118 lines (107 loc) · 3.14 KB
/
FastFourierTransform.compute
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#pragma kernel PrecomputeTwiddleFactorsAndInputIndices
#pragma kernel HorizontalStepFFT
#pragma kernel VerticalStepFFT
#pragma kernel HorizontalStepInverseFFT
#pragma kernel VerticalStepInverseFFT
#pragma kernel Scale
#pragma kernel Permute
static const float PI = 3.1415926;
RWTexture2D<float4> PrecomputeBuffer;
Texture2D<float4> PrecomputedData;
RWTexture2D<float2> Buffer0;
RWTexture2D<float2> Buffer1;
bool PingPong;
uint Step;
uint Size;
float2 ComplexMult(float2 a, float2 b)
{
return float2(a.r * b.r - a.g * b.g, a.r * b.g + a.g * b.r);
}
float2 ComplexExp(float2 a)
{
return float2(cos(a.y), sin(a.y)) * exp(a.x);
}
[numthreads(1, 8, 1)]
void PrecomputeTwiddleFactorsAndInputIndices(uint3 id : SV_DispatchThreadID)
{
uint b = Size >> (id.x + 1);
float2 mult = 2 * PI * float2(0, 1) / Size;
uint i = (2 * b * (id.y / b) + id.y % b) % Size;
float2 twiddle = ComplexExp(-mult * ((id.y / b) * b));
PrecomputeBuffer[id.xy] = float4(twiddle.x, twiddle.y, i, i + b);
PrecomputeBuffer[uint2(id.x, id.y + Size / 2)] = float4(-twiddle.x, -twiddle.y, i, i + b);
}
[numthreads(8, 8, 1)]
void HorizontalStepFFT (uint3 id : SV_DispatchThreadID)
{
float4 data = PrecomputedData[uint2(Step, id.x)];
uint2 inputsIndices = (uint2)data.ba;
if (PingPong)
{
Buffer1[id.xy] = Buffer0[uint2(inputsIndices.x, id.y)]
+ ComplexMult(data.rg, Buffer0[uint2(inputsIndices.y, id.y)]);
}
else
{
Buffer0[id.xy] = Buffer1[uint2(inputsIndices.x, id.y)]
+ ComplexMult(data.rg, Buffer1[uint2(inputsIndices.y, id.y)]);
}
}
[numthreads(8, 8, 1)]
void VerticalStepFFT(uint3 id : SV_DispatchThreadID)
{
float4 data = PrecomputedData[uint2(Step, id.y)];
uint2 inputsIndices = (uint2)data.ba;
if (PingPong)
{
Buffer1[id.xy] = Buffer0[uint2(id.x, inputsIndices.x)]
+ ComplexMult(data.rg, Buffer0[uint2(id.x, inputsIndices.y)]);
}
else
{
Buffer0[id.xy] = Buffer1[uint2(id.x, inputsIndices.x)]
+ ComplexMult(data.rg, Buffer1[uint2(id.x, inputsIndices.y)]);
}
}
[numthreads(8, 8, 1)]
void HorizontalStepInverseFFT(uint3 id : SV_DispatchThreadID)
{
float4 data = PrecomputedData[uint2(Step, id.x)];
uint2 inputsIndices = (uint2)data.ba;
if (PingPong)
{
Buffer1[id.xy] = Buffer0[uint2(inputsIndices.x, id.y)]
+ ComplexMult(float2(data.r, -data.g), Buffer0[uint2(inputsIndices.y, id.y)]);
}
else
{
Buffer0[id.xy] = Buffer1[uint2(inputsIndices.x, id.y)]
+ ComplexMult(float2(data.r, -data.g), Buffer1[uint2(inputsIndices.y, id.y)]);
}
}
[numthreads(8, 8, 1)]
void VerticalStepInverseFFT(uint3 id : SV_DispatchThreadID)
{
float4 data = PrecomputedData[uint2(Step, id.y)];
uint2 inputsIndices = (uint2)data.ba;
if (PingPong)
{
Buffer1[id.xy] = Buffer0[uint2(id.x, inputsIndices.x)]
+ ComplexMult(float2(data.r, -data.g), Buffer0[uint2(id.x, inputsIndices.y)]);
}
else
{
Buffer0[id.xy] = Buffer1[uint2(id.x, inputsIndices.x)]
+ ComplexMult(float2(data.r, -data.g), Buffer1[uint2(id.x, inputsIndices.y)]);
}
}
[numthreads(8, 8, 1)]
void Scale(uint3 id : SV_DispatchThreadID)
{
Buffer0[id.xy] = Buffer0[id.xy] / Size / Size;
}
[numthreads(8, 8, 1)]
void Permute(uint3 id : SV_DispatchThreadID)
{
Buffer0[id.xy] = Buffer0[id.xy] * (1.0 - 2.0 * ((id.x + id.y) % 2));
}