git.sesse.net Git - movit/blob - fft_pass_effect.cpp

   1 #include <epoxy/gl.h>
   2 #include <math.h>
   3
   4 #include "effect_util.h"
   5 #include "fp16.h"
   6 #include "fft_pass_effect.h"
   7 #include "util.h"
   8
   9 using namespace std;
  10
  11 namespace movit {
  12
  13 FFTPassEffect::FFTPassEffect()
  14         : input_width(1280),
  15           input_height(720),
  16           direction(HORIZONTAL)
  17 {
  18         register_int("fft_size", &fft_size);
  19         register_int("direction", (int *)&direction);
  20         register_int("pass_number", &pass_number);
  21         register_int("inverse", &inverse);
  22         glGenTextures(1, &tex);
  23 }
  24
  25 FFTPassEffect::~FFTPassEffect()
  26 {
  27         glDeleteTextures(1, &tex);
  28 }
  29
  30 string FFTPassEffect::output_fragment_shader()
  31 {
  32         char buf[256];
  33         sprintf(buf, "#define DIRECTION_VERTICAL %d\n", (direction == VERTICAL));
  34         return buf + read_file("fft_pass_effect.frag");
  35 }
  36
  37 void FFTPassEffect::set_gl_state(GLuint glsl_program_num, const string &prefix, unsigned *sampler_num)
  38 {
  39         Effect::set_gl_state(glsl_program_num, prefix, sampler_num);
  40
  41         int input_size = (direction == VERTICAL) ? input_height : input_width;
  42
  43         // See the comments on changes_output_size() in the .h file to see
  44         // why this is legal. It is _needed_ because it counteracts the
  45         // precision issues we get because we sample the input texture with
  46         // normalized coordinates (especially when the repeat count along
  47         // the axis is not a power of two); we very rapidly end up in narrowly
  48         // missing a texel center, which causes precision loss to propagate
  49         // throughout the FFT.
  50         assert(*sampler_num == 1);
  51         glActiveTexture(GL_TEXTURE0);
  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 < fft_size; ++i) {
  96                 int k = i / stride;         // Element number within this sub-FFT.
  97                 int offset = i % stride;    // Sub-FFT number.
  98                 double twiddle_real, twiddle_imag;
  99
 100                 if (k < subfft_size / 2) {
 101                         twiddle_real = cos(mulfac * (k / double(subfft_size)));
 102                         twiddle_imag = sin(mulfac * (k / double(subfft_size)));
 103                 } else {
 104                         // This is mathematically equivalent to the twiddle factor calculations
 105                         // in the other branch of the if, but not numerically; the range
 106                         // reductions on x87 are not all that precise, and this keeps us within
 107                         // [0,pi>.
 108                         k -= subfft_size / 2;
 109                         twiddle_real = -cos(mulfac * (k / double(subfft_size)));
 110                         twiddle_imag = -sin(mulfac * (k / double(subfft_size)));
 111                 }
 112
 113                 // The support texture contains everything we need for the FFT:
 114                 // Obviously, the twiddle factor (in the Z and W components), but also
 115                 // which two samples to fetch. These are stored as normalized
 116                 // X coordinate offsets (Y coordinate for a vertical FFT); the reason
 117                 // for using offsets and not direct coordinates as in GPUwave
 118                 // is that we can have multiple FFTs along the same line,
 119                 // and want to reuse the support texture by repeating it.
 120                 int base = k * stride * 2 + offset;
 121                 int support_texture_index;
 122                 if (direction == FFTPassEffect::VERTICAL) {
 123                         // Compensate for OpenGL's bottom-left convention.
 124                         support_texture_index = fft_size - i - 1;
 125                 } else {
 126                         support_texture_index = i;
 127                 }
 128                 tmp[support_texture_index * 4 + 0] = fp64_to_fp16((base - support_texture_index) / double(input_size));
 129                 tmp[support_texture_index * 4 + 1] = fp64_to_fp16((base + stride - support_texture_index) / double(input_size));
 130                 tmp[support_texture_index * 4 + 2] = fp64_to_fp16(twiddle_real);
 131                 tmp[support_texture_index * 4 + 3] = fp64_to_fp16(twiddle_imag);
 132         }
 133
 134         glActiveTexture(GL_TEXTURE0 + *sampler_num);
 135         check_error();
 136         glBindTexture(GL_TEXTURE_2D, tex);
 137         check_error();
 138         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_NEAREST);
 139         check_error();
 140         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_NEAREST);
 141         check_error();
 142         glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT);
 143         check_error();
 144
 145         // Supposedly FFTs are very sensitive to inaccuracies in the twiddle factors,
 146         // at least according to a paper by Schatzman (see gpuwave.pdf reference [30]
 147         // for the full reference); however, practical testing indicates that it's
 148         // not a problem to keep the twiddle factors at 16-bit, at least as long as
 149         // we round them properly--it would seem that Schatzman were mainly talking
 150         // about poor sin()/cos() approximations. Thus, we store them in 16-bit,
 151         // which gives a nice speed boost.
 152         //
 153         // Note that the source coordinates become somewhat less accurate too, though.
 154         glTexImage2D(GL_TEXTURE_2D, 0, GL_RGBA16F, fft_size, 1, 0, GL_RGBA, GL_HALF_FLOAT, tmp);
 155         check_error();
 156
 157         delete[] tmp;
 158
 159         set_uniform_int(glsl_program_num, prefix, "support_tex", *sampler_num);
 160         ++*sampler_num;
 161
 162         assert(input_size % fft_size == 0);
 163         set_uniform_float(glsl_program_num, prefix, "num_repeats", input_size / fft_size);
 164 }
 165
 166 }  // namespace movit