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