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

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