4 #include "effect_chain.h"
5 #include "effect_util.h"
7 #include "fft_pass_effect.h"
14 FFTPassEffect::FFTPassEffect()
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);
26 FFTPassEffect::~FFTPassEffect()
28 glDeleteTextures(1, &tex);
31 string FFTPassEffect::output_fragment_shader()
34 sprintf(buf, "#define DIRECTION_VERTICAL %d\n", (direction == VERTICAL));
35 return buf + read_file("fft_pass_effect.frag");
38 void FFTPassEffect::set_gl_state(GLuint glsl_program_num, const string &prefix, unsigned *sampler_num)
40 Effect::set_gl_state(glsl_program_num, prefix, sampler_num);
42 int input_size = (direction == VERTICAL) ? input_height : input_width;
44 // This is needed because it counteracts the precision issues we get
45 // because we sample the input texture with normalized coordinates
46 // (especially when the repeat count along the axis is not a power of
47 // two); we very rapidly end up in narrowly missing a texel center,
48 // which causes precision loss to propagate throughout the FFT.
49 Node *self = chain->find_node_for_effect(this);
50 glActiveTexture(chain->get_input_sampler(self, 0));
52 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
54 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
57 // The memory layout follows figure 5.2 on page 25 of
58 // http://gpuwave.sesse.net/gpuwave.pdf -- it can be a bit confusing
59 // at first, but is classically explained more or less as follows:
61 // The classic Cooley-Tukey decimation-in-time FFT algorithm works
62 // by first splitting input data into odd and even elements
63 // (e.g. bit-wise xxxxx0 and xxxxx1 for a size-32 FFT), then FFTing
64 // them separately and combining them using twiddle factors.
65 // So the outer pass (done _last_) looks only at the last bit,
66 // and does one such merge pass of sub-size N/2 (FFT size N).
68 // FFT of the first part must then necessarily be split into xxxx00 and
69 // xxxx10, and similarly xxxx01 and xxxx11 for the other part. Since
70 // these two FFTs are handled identically, it means we split into xxxx0x
71 // and xxxx1x, so that the second-outer pass (done second-to-last)
72 // looks only at the second last bit, and so on. We do two such merge
73 // passes of sub-size N/4 (sub-FFT size N/2).
75 // Thus, the inner, Nth pass (done first) splits at the first bit,
76 // so 0 is paired with 16, 1 with 17 and so on, doing N/2 such merge
77 // passes of sub-size 1 (sub-FFT size 2). We say that the stride is 16.
78 // The second-inner, (N-1)th pass (done second) splits at the second
79 // bit, so the stride is 8, and so on.
81 assert((fft_size & (fft_size - 1)) == 0); // Must be power of two.
82 fp16_int_t *tmp = new fp16_int_t[fft_size * 4];
83 int subfft_size = 1 << pass_number;
91 assert((fft_size & (fft_size - 1)) == 0); // Must be power of two.
92 assert(fft_size % subfft_size == 0);
93 int stride = fft_size / subfft_size;
94 for (int i = 0; i < fft_size; ++i) {
95 int k = i / stride; // Element number within this sub-FFT.
96 int offset = i % stride; // Sub-FFT number.
97 double twiddle_real, twiddle_imag;
99 if (k < subfft_size / 2) {
100 twiddle_real = cos(mulfac * (k / double(subfft_size)));
101 twiddle_imag = sin(mulfac * (k / double(subfft_size)));
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
107 k -= subfft_size / 2;
108 twiddle_real = -cos(mulfac * (k / double(subfft_size)));
109 twiddle_imag = -sin(mulfac * (k / double(subfft_size)));
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 + offset;
120 int support_texture_index = i;
122 int src2 = base + stride;
123 if (direction == FFTPassEffect::VERTICAL) {
124 // Compensate for OpenGL's bottom-left convention.
125 support_texture_index = fft_size - support_texture_index - 1;
126 src1 = fft_size - src1 - 1;
127 src2 = fft_size - src2 - 1;
129 tmp[support_texture_index * 4 + 0] = fp64_to_fp16((src1 - support_texture_index) / double(input_size));
130 tmp[support_texture_index * 4 + 1] = fp64_to_fp16((src2 - support_texture_index) / 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);
135 glActiveTexture(GL_TEXTURE0 + *sampler_num);
137 glBindTexture(GL_TEXTURE_2D, tex);
139 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
141 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
143 glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
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.
154 // Note that the source coordinates become somewhat less accurate too, though.
155 glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA16F, fft_size, 1, 0, GL_RGBA, GL_HALF_FLOAT, tmp);
160 set_uniform_int(glsl_program_num, prefix, "support_tex", *sampler_num);
163 assert(input_size % fft_size == 0);
164 set_uniform_float(glsl_program_num, prefix, "num_repeats", input_size / fft_size);