improved loopfinder algorithm
authorRudolf Polzer <divVerent@xonotic.org>
Wed, 12 Oct 2011 12:19:55 +0000 (14:19 +0200)
committerRudolf Polzer <divVerent@xonotic.org>
Wed, 12 Oct 2011 12:19:55 +0000 (14:19 +0200)
sound/weapons/loopfinder/findloop.c
sound/weapons/loopfinder/playloop.sh [new file with mode: 0644]

index 14d12f4..e74d8d0 100644 (file)
@@ -52,22 +52,40 @@ void doFourier(double *input, int channels, sf_count_t len, fftw_complex *output
        fftw_execute_dft_r2c(planlos, windowedData, output);
 }
 
-// idea: if match, then sxx * syy = sxy * sxy
-
-double vectorDot(fftw_complex *v1, fftw_complex *v2, size_t length)
+// return 1.0 for identical, 0.0 for different
+#define VDIFF 1
+#define LDIFF 255
+double vectorSim(fftw_complex *v1, fftw_complex *v2, size_t length)
 {
        size_t i;
        double sum = 0;
+       double div = 0;
        for(i = 0; i < length; ++i)
-               sum += cabs(v1[i]) * cabs(v2[i]);
-       for(i = 0; i < length; ++i)
-               sum += 0.001 * creal(v1[i]) * creal(v2[i]);
-       for(i = 0; i < length; ++i)
-               sum += 0.001 * cimag(v1[i]) * cimag(v2[i]);
-       return sum;
+       {
+               fftw_complex a = v1[i];
+               fftw_complex b = v2[i];
+
+               div += cabs(a) + cabs(b);
+
+               // primitives:
+               //   cabs(a - b)             # 0 .. div
+               //   fabs(cabs(a) - cabs(b)) # 0 .. div
+
+               // component 1: vector diff
+               sum += VDIFF * cabs(a - b); // can be at most 2*div
+
+               // component 2: length diff
+               sum += LDIFF * fabs(cabs(a) - cabs(b));
+       }
+       sum *= (1.0 / (VDIFF + LDIFF));
+       if(div == 0)
+               return -1;
+       if(sum > div || sum < 0)
+               fprintf(stderr, "%f %f\n", sum, div);
+       return 1.0 - (sum / div);
 }
 
-sf_count_t findMaximumSingle(double (*func) (sf_count_t), sf_count_t x0, sf_count_t x1, sf_count_t step)
+sf_count_t findMaximumSingle(double (*func) (sf_count_t), sf_count_t x0, sf_count_t x1, sf_count_t step, double *val)
 {
        sf_count_t bestpos = x1;
        double best = func(x1);
@@ -84,10 +102,12 @@ sf_count_t findMaximumSingle(double (*func) (sf_count_t), sf_count_t x0, sf_coun
                }
        }
 
+       *val = best;
+
        return bestpos;
 }
 
-sf_count_t findMaximum(double (*func) (sf_count_t), sf_count_t x0, sf_count_t xg, sf_count_t xg2, sf_count_t x1)
+sf_count_t findMaximum(double (*func) (sf_count_t), sf_count_t x0, sf_count_t xg, sf_count_t xg2, sf_count_t x1, double *val)
 {
        sf_count_t xg0, xg20;
 
@@ -102,7 +122,7 @@ sf_count_t findMaximum(double (*func) (sf_count_t), sf_count_t x0, sf_count_t xg
                if(size == 0)
                        break;
                //fprintf(stderr, "round:\n");
-               sf_count_t bestguess = findMaximumSingle(func, xg, xg2, size / 32 + 1);
+               sf_count_t bestguess = findMaximumSingle(func, xg, xg2, size / 32 + 1, val);
                xg = MAX(xg0, bestguess - size / 3);
                xg2 = MIN(bestguess + size / 3, xg20);
        }
@@ -171,45 +191,11 @@ int main(int argc, char **argv)
        doFourier(sbuf + (size - fftsize) * chans, chans, fftsize, data_end);
        fprintf(stderr, "end transformed.\n");
 
-       double sxx = vectorDot(data_end + ndata_lowpass, data_end + ndata_lowpass, ndata_highpass - ndata_lowpass);
-       if(sxx == 0)
-               errx(1, "ends with silence... use another end point");
-
-#if 0
-       {
-               sf_count_t i, j;
-               double sum[ndata];
-               double diffsum[ndata];
-               fftw_complex save[ndata];
-               for(i = guess; i < size - fftsize; ++i)
-               {
-                       doFourier(sbuf + i * channels, channels, fftsize, data_cur);
-                       for(j = 0; j < ndata; ++j)
-                       {
-                               fftw_complex x = data_cur[j];
-                               if(i != 0)
-                               {
-                                       fftw_complex y = save[j];
-                                       sum[j] += cabs(x);
-                                       diffsum[j] += cabs(y - x);
-                               }
-                               save[j] = x;
-                       }
-                       fprintf(stderr, "at position %d\n", (int) i);
-               }
-               for(j = 0; j < ndata; ++j)
-                       printf("%d %.9f %.9f\n", j, sum[j], diffsum[j]);
-               return 0;
-       }
-#endif
-
        double similarityAt(sf_count_t i)
        {
                // A trampoline! Wheeeeeeeeeew!
                doFourier(sbuf + i * channels, channels, fftsize, data_cur);
-               double sxy = vectorDot(data_end + ndata_lowpass, data_cur + ndata_lowpass, ndata_highpass - ndata_lowpass);
-               double syy = vectorDot(data_cur + ndata_lowpass, data_cur + ndata_lowpass, ndata_highpass - ndata_lowpass);
-               double v = syy ? ((sxy*sxy) / (sxx*syy)) : -1;
+               double v = vectorSim(data_end + ndata_lowpass, data_cur + ndata_lowpass, ndata_highpass - ndata_lowpass);
                //fprintf(stderr, "Evaluated at %.9f: %f\n", i / (double) infile_info.samplerate, v);
                return v;
        }
@@ -225,8 +211,9 @@ int main(int argc, char **argv)
        }
 #endif
 
-       sf_count_t best = findMaximum(similarityAt, 0, guess - fftsize, guess2 - fftsize, size - 2 * fftsize);
-       fprintf(stderr, "Result: %.9f (sample %ld)\n", (best + fftsize) / (double) infile_info.samplerate, (long) (best + fftsize));
+       double val = -1;
+       sf_count_t best = findMaximum(similarityAt, 0, guess - fftsize, guess2 - fftsize, size - 2 * fftsize, &val);
+       fprintf(stderr, "Result: %.9f (sample %ld) with quality %.9f\n", (best + fftsize) / (double) infile_info.samplerate, (long) (best + fftsize), val);
 
        // Now write it!
 
diff --git a/sound/weapons/loopfinder/playloop.sh b/sound/weapons/loopfinder/playloop.sh
new file mode 100644 (file)
index 0000000..be96e49
--- /dev/null
@@ -0,0 +1,7 @@
+#!/bin/sh
+
+n=`vorbiscomment "$1" | grep LOOP_START= | cut -d = -f 2`
+
+sox "$1" temp.wav trim "$n"s
+play --combine concatenate "$1" temp.wav temp.wav temp.wav temp.wav temp.wav temp.wav temp.wav
+rm -f temp.wav