a3de3792b380060f1c6effe112bfd5a1d0270344
[movit] / fft_pass_effect.cpp
1 #include <GL/glew.h>
2
3 #include "fft_pass_effect.h"
4 #include "effect_util.h"
5 #include "util.h"
6
7 FFTPassEffect::FFTPassEffect()
8         : input_width(1280),
9           input_height(720),
10           direction(HORIZONTAL)
11 {
12         register_int("fft_size", &fft_size);
13         register_int("direction", (int *)&direction);
14         register_int("pass_number", &pass_number);
15         register_int("inverse", &inverse);
16         glGenTextures(1, &tex);
17 }
18
19 FFTPassEffect::~FFTPassEffect()
20 {
21         glDeleteTextures(1, &tex);
22 }
23
24 std::string FFTPassEffect::output_fragment_shader()
25 {
26         char buf[256];
27         sprintf(buf, "#define DIRECTION_VERTICAL %d\n", (direction == VERTICAL));
28         return buf + read_file("fft_pass_effect.frag");
29 }
30
31 void FFTPassEffect::set_gl_state(GLuint glsl_program_num, const std::string &prefix, unsigned *sampler_num)
32 {
33         Effect::set_gl_state(glsl_program_num, prefix, sampler_num);
34
35         int input_size = (direction == VERTICAL) ? input_height : input_width;
36
37         // See the comments on changes_output_size() in the .h file to see
38         // why this is legal. It is _needed_ because it counteracts the
39         // precision issues we get because we sample the input texture with
40         // normalized coordinates (especially when the repeat count along
41         // the axis is not a power of two); we very rapidly end up in narrowly
42         // missing a texel center, which causes precision loss to propagate
43         // throughout the FFT.
44         assert(*sampler_num == 1);
45         glActiveTexture(GL_TEXTURE0);
46         check_error();
47         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
48         check_error();
49         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
50         check_error();
51
52         // The memory layout follows figure 5.2 on page 25 of
53         // http://gpuwave.sesse.net/gpuwave.pdf -- it can be a bit confusing
54         // at first, but is classically explained more or less as follows:
55         //
56         // The classic Cooley-Tukey decimation-in-time FFT algorithm works
57         // by first splitting input data into odd and even elements
58         // (e.g. bit-wise xxxxx0 and xxxxx1 for a size-32 FFT), then FFTing
59         // them separately and combining them using twiddle factors.
60         // So the outer pass (done _last_) looks only at the last bit,
61         // and does one such merge pass of sub-size N/2 (FFT size N).
62         //
63         // FFT of the first part must then necessarily be split into xxxx00 and
64         // xxxx10, and similarly xxxx01 and xxxx11 for the other part. Since
65         // these two FFTs are handled identically, it means we split into xxxx0x
66         // and xxxx1x, so that the second-outer pass (done second-to-last)
67         // looks only at the second last bit, and so on. We do two such merge
68         // passes of sub-size N/4 (sub-FFT size N/2).
69         //
70         // Thus, the inner, Nth pass (done first) splits at the first bit,
71         // so 0 is paired with 16, 1 with 17 and so on, doing N/2 such merge
72         // passes of sub-size 1 (sub-FFT size 2). We say that the stride is 16.
73         // The second-inner, (N-1)th pass (done second) splits at the second
74         // bit, so the stride is 8, and so on.
75
76         assert((fft_size & (fft_size - 1)) == 0);  // Must be power of two.
77         float *tmp = new float[fft_size * 4];
78         int subfft_size = 1 << pass_number;
79         double mulfac;
80         if (inverse) {
81                 mulfac = 2.0 * M_PI;
82         } else {
83                 mulfac = -2.0 * M_PI;
84         }
85
86         assert((fft_size & (fft_size - 1)) == 0);  // Must be power of two.
87         assert(fft_size % subfft_size == 0);
88         int stride = fft_size / subfft_size;
89         for (int i = 0; i < fft_size; ++i) {
90                 int k = i / stride;         // Element number within this sub-FFT.
91                 int offset = i % stride;    // Sub-FFT number.
92                 double twiddle_real, twiddle_imag;
93
94                 if (k < subfft_size / 2) {
95                         twiddle_real = cos(mulfac * (k / double(subfft_size)));
96                         twiddle_imag = sin(mulfac * (k / double(subfft_size)));
97                 } else {
98                         // This is mathematically equivalent to the twiddle factor calculations
99                         // in the other branch of the if, but not numerically; the range
100                         // reductions on x87 are not all that precise, and this keeps us within
101                         // [0,pi>.
102                         k -= subfft_size / 2;
103                         twiddle_real = -cos(mulfac * (k / double(subfft_size)));
104                         twiddle_imag = -sin(mulfac * (k / double(subfft_size)));
105                 }
106
107                 // The support texture contains everything we need for the FFT:
108                 // Obviously, the twiddle factor (in the Z and W components), but also
109                 // which two samples to fetch. These are stored as normalized
110                 // X coordinate offsets (Y coordinate for a vertical FFT); the reason
111                 // for using offsets and not direct coordinates as in GPUwave
112                 // is that we can have multiple FFTs along the same line,
113                 // and want to reuse the support texture by repeating it.
114                 int base = k * stride * 2 + offset;
115                 int support_texture_index;
116                 if (direction == FFTPassEffect::VERTICAL) {
117                         // Compensate for OpenGL's bottom-left convention.
118                         support_texture_index = fft_size - i - 1;
119                 } else {
120                         support_texture_index = i;
121                 }
122                 tmp[support_texture_index * 4 + 0] = (base - support_texture_index) / double(input_size);
123                 tmp[support_texture_index * 4 + 1] = (base + stride - support_texture_index) / double(input_size);
124                 tmp[support_texture_index * 4 + 2] = twiddle_real;
125                 tmp[support_texture_index * 4 + 3] = twiddle_imag;
126         }
127
128         glActiveTexture(GL_TEXTURE0 + *sampler_num);
129         check_error();
130         glBindTexture(GL_TEXTURE_1D, tex);
131         check_error();
132         glTexParameteri(GL_TEXTURE_1D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
133         check_error();
134         glTexParameteri(GL_TEXTURE_1D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
135         check_error();
136         glTexParameteri(GL_TEXTURE_1D, GL_TEXTURE_WRAP_S, GL_REPEAT);
137         check_error();
138
139         // Supposedly FFTs are very sensitive to inaccuracies in the twiddle factors,
140         // at least according to a paper by Schatzman (see gpuwave.pdf reference [30]
141         // for the full reference), so we keep them at 32-bit. However, for
142         // small sizes, all components are exact anyway, so we can cheat there
143         // (although noting that the source coordinates become somewhat less
144         // accurate then, too).
145         glTexImage1D(GL_TEXTURE_1D, 0, (subfft_size <= 4) ? GL_RGBA16F : GL_RGBA32F, fft_size, 0, GL_RGBA, GL_FLOAT, tmp);
146         check_error();
147
148         delete[] tmp;
149
150         set_uniform_int(glsl_program_num, prefix, "support_tex", *sampler_num);
151         ++*sampler_num;
152
153         assert(input_size % fft_size == 0);
154         set_uniform_float(glsl_program_num, prefix, "num_repeats", input_size / fft_size);
155 }