frequency_filter.cpp

Go to the documentation of this file.

/* Copyright (c) 2013 Wildfire Games
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included
 * in all copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */

#include "precompiled.h"
#include "lib/frequency_filter.h"

static const double errorTolerance = 0.25;
static const double sensitivity = 0.10;
static const double sampleTime = 2.0; // seconds

/**
 * variable-width window for frequency determination
 **/
class FrequencyEstimator
{
    NONCOPYABLE(FrequencyEstimator);
public:
    FrequencyEstimator(double resolution)
        : m_minDeltaTime(4.0 * resolution)  // chosen to reduce error but still yield rapid updates.
        , m_lastTime(0) // will be set on first call
        , m_numEvents(0)
    {
        ENSURE(resolution > 0.0);
    }

    bool operator()(double time, double& frequency)
    {
        m_numEvents++;

        if(m_lastTime == 0.0)
            m_lastTime = time;

        // count # events until deltaTime is large enough
        // (reduces quantization errors if resolution is low)
        const double deltaTime = time - m_lastTime;
        if(deltaTime <= m_minDeltaTime)
            return false;

        frequency = m_numEvents / deltaTime;
        m_numEvents = 0;
        m_lastTime = time;
        return true;    // success
    }

private:
    const double m_minDeltaTime;
    double m_lastTime;
    int m_numEvents;
};


/**
 * variable-gain IIR filter
 **/
class IirFilter
{
public:
    IirFilter(double sensitivity, double initialValue)
        : m_sensitivity(sensitivity), m_prev(initialValue)
    {
    }

    // bias = 0: no change. > 0: increase (n-th root). < 0: decrease (^n)
    double operator()(double x, int bias)
    {
        // sensitivity to changes ([0,1]).
        const double gain = pow(m_sensitivity, ComputeExponent(bias));
        return m_prev = x*gain + m_prev*(1.0-gain);
    }

private:
    static double ComputeExponent(int bias)
    {
        if(bias > 0)
            return 1.0 / bias;  // n-th root
        else if(bias == 0)
            return 1.0;     // no change
        else
            return -bias;   // power-of-n
    }

    double m_sensitivity;
    double m_prev;
};


/**
 * regulate IIR gain for rapid but smooth tracking of a function.
 * this is similar in principle to a PID controller but is tuned for
 * the special case of FPS values to simplify stabilizing the filter.
 **/
class Controller
{
public:
    Controller(double initialValue)
        : m_timesOnSameSide(0)
    {
        std::fill(m_history, m_history+m_historySize, initialValue);
    }

    // bias := exponential change to gain, (-inf, inf)
    int ComputeBias(double smoothedValue, double value)
    {
        if(WasOnSameSide(value))    // (must be checked before updating history)
            m_timesOnSameSide++;
        else
            m_timesOnSameSide = 0;

        // update history
        std::copy(m_history, m_history+m_historySize, m_history+1);
        m_history[m_historySize-1] = value;

        // dampen jitter
        if(Change(smoothedValue, value) < 0.04)
            return -1;

        // dampen spikes/bounces.
        if(WasSpike())
            return -2;

        // if the past few samples have been consistently above/below
        // average, the function is changing and we need to catch up.
        // (similar to I in a PID)
        if(m_timesOnSameSide >= 3)
            return std::min(m_timesOnSameSide, 4);

        // suppress large jumps.
        if(Change(m_history[m_historySize-1], value) > 0.30)
            return -4;  // gain -> 0

        return 0;
    }

private:
    bool WasOnSameSide(double value) const
    {
        int sum = 0;
        for(size_t i = 0; i < m_historySize; i++)
        {
            const int vote = (value >= m_history[i])? 1 : -1;
            sum += vote;
        }
        return abs(sum) == (int)m_historySize;
    }

    static double Change(double from, double to)
    {
        return fabs(from - to) / from;
    }

    // /\ or \/ in last three history entries
    bool WasSpike() const
    {
        cassert(m_historySize >= 3);
        const double h2 = m_history[m_historySize-3], h1 = m_history[m_historySize-2], h0 = m_history[m_historySize-1];
        if(((h2-h1) * (h1-h0)) > 0) // no sign change
            return false;
        if(Change(h2, h0) > 0.05)   // overall change from oldest to newest value
            return false;
        if(Change(h1, h0) < 0.10)   // no intervening spike
            return false;
        return true;
    }

    static const size_t m_historySize = 3;
    double m_history[m_historySize];
    int m_timesOnSameSide;
};


class FrequencyFilter : public IFrequencyFilter
{
    NONCOPYABLE(FrequencyFilter);
public:
    FrequencyFilter(double resolution, double expectedFrequency)
        : m_frequencyEstimator(resolution), m_controller(expectedFrequency), m_iirFilter(sensitivity, expectedFrequency)
        , m_stableFrequency((int)expectedFrequency), m_smoothedFrequency(expectedFrequency), m_averagedFrequency(expectedFrequency)
        , m_numberOfSamples((int)(sampleTime * expectedFrequency) + 1)
    {
    }

    virtual void Update(double time)
    {
        double frequency;
        if(!m_frequencyEstimator(time, frequency))
            return;

        const int bias = m_controller.ComputeBias(m_smoothedFrequency, frequency);
        m_smoothedFrequency = m_iirFilter(frequency, bias);

        // Keep a moving average of the frequency over the last two seconds
        // If there is a spike of more than 25% (e.g. loading screen => game)
        // then reset the moving average and reset the number of samples needed
        const double difference = fabs(m_smoothedFrequency - m_averagedFrequency);
        if (difference > errorTolerance * m_averagedFrequency)
        {
            m_averagedFrequency = m_smoothedFrequency;
            m_numberOfSamples = (int)(m_averagedFrequency * sampleTime) + 1;
        }
        else
            m_averagedFrequency = ((double)(m_numberOfSamples - 1) * m_averagedFrequency + m_smoothedFrequency) / (double)m_numberOfSamples;

        // allow the smoothed FPS to free-run until it is no longer near the
        // previous stable FPS value. round up because values are more often
        // too low than too high.
        m_stableFrequency = (int)(m_averagedFrequency + 0.99);
    }

    virtual double SmoothedFrequency() const
    {
        return m_smoothedFrequency;
    }

    virtual int StableFrequency() const
    {
        return m_stableFrequency;
    }

private:
    FrequencyEstimator m_frequencyEstimator;
    Controller m_controller;
    IirFilter m_iirFilter;

    int m_stableFrequency;
    double m_smoothedFrequency;
    double m_averagedFrequency;
    int m_numberOfSamples;
};


PIFrequencyFilter CreateFrequencyFilter(double resolution, double expectedFrequency)
{
    return PIFrequencyFilter(new FrequencyFilter(resolution, expectedFrequency));
}