4 ms·

Why not use an exponential filter that only uses a single variable?

kragen 5y ago
The running-sum-difference approach suggested above is a box filter, which has the best possible noise suppression for a given step-function delay, although in the frequency domain it looks appalling. It uses more RAM, but not that much. The single-pole RC filter you're suggesting is much nicer in the frequency domain, but in the time domain it's far worse.
- WanderPanda 5y ago
  Is it „far worse in the time domain“ due to its infinite impulse response?
  - kragen 5y ago
    Not really? Sort of? I don't really have a good answer here. It depends on what you mean by "due to". It's certainly due to the impulse response, since in the sense I meant "far worse" the impulse response is the only thing that matters. Truncating the impulse response after five time constants wouldn't really change its output noticeably, and even if you truncated it after two or three time constants it would still be inferior to the box filter for this application, though less bad. So in that sense the problem isn't that it's infinite. Likewise, you could certainly design a direct-form IIR filter that did a perfectly adequate job of approximating a box filter for this sort of application, and that might actually be a reasonable thing to do if you wanted to do something like this with a bunch of op-amps or microwave passives instead of code. So the fact that the impulse response is infinite is neither necessary nor sufficient for the problem. The problem with the simple single-pole filter is that by putting so much weight on very recent samples, you sort of throw away some information about samples that aren't quite so recent and become more vulnerable to false triggering from a single rapid mouse movement, so you have to set the threshold higher to compensate.
  - Waterluvian 5y ago
    Reading all of you sounding super smart and saying stuff I don’t recognize (but perhaps utilize without knowing the terms) used to make me feel anxious about being an impostor. Now it makes me excited that there’s so many more secrets to discover in my discipline.
    - kragen 5y ago
      Yeah, DSP has a lot of really awesome stuff in it! I recommend https://www.dspguide.com/ https://www.dspguide.com/. It turns out that pretty much any time you have code that interacts with the world outside computers, you end up doing DSP. Graphics processing algorithms are DSP; software-defined radio is DSP; music synthesis is DSP; Kalman filters for position estimation is DSP; PID controllers for thermostats or motor control are DSP; converting sonar echoes into images is DSP; electrocardiogram analysis is DSP; high-frequency trading is DSP (though most of the linear theory is not useful there). So if you're interested in programming and also interested in graphics, sound, communication, or other things outside of computers, you will appreciate having studied DSP.
    - hoseja 5y ago
      Don't worry, this is a domain of magic matlab functions and excel data analysis and multiply-named (separately invented about four times on average in different fields) terms for the same thing, with incomprehensible jargon and no simple explanation untainted by very specific industry application.
hoseja 5y ago
Please elaborate.
- kragen 5y ago
  For both alternatives we begin by computing how far the mouse has gone: int m = abs(dx) + abs(dy); // Manhattan distance For the single-pole RC exponential filter as WanderPanda suggested: c -= c >> 5; // exponential decay without a multiply (not actually faster on most modern CPUs) c += m; For the box filter with the running-sum table as nostrademons suggested: s += m; // update running sum size_t j = (i + 1) % n; // calculate index in prefix sum table to overwrite int d = s - t[j]; // calculate sum of last n mouse movement Manhattan distances t[j] = s; i = j; Here c, i, s, and t are all presumed to persist from one event to the next, so maybe they're part of some context struct, while in old-fashioned C they'd be static variables. If n is a compile-time constant, this will be more efficient, especially if it's a power of 2. You don't really need a separate persistent s; that's an optimization nostrademons suggested, but you could instead use a local s at the cost of an extra array-indexing operation: int s = t[i] + m; Depending on context this might not actually cost any extra time. Once you've computed your smoothed mouse velocity in c or d, you compare it against some kind of predetermined threshold, or maybe apply a smoothstep to it to get the mouse pointer size. Roughly I think WanderPanda's approach is about 12 RISCish CPU instructions, and nostrademons's approach is about 18 but works a lot better. Either way you're probably looking at about 4-8 clock cycles on one core per mouse movement, considerably less than actually drawing the mouse pointer (if you're doing it on the CPU, anyway). Does that help?
Karrot_Kream 5y ago
Agreed, a single-pole IIR filter would be cheaper and have a better frequency domain.

The running-sum-difference approach suggested above is a box filter, which has the best possible noise suppression for a given step-function delay, although in the frequency domain it looks appalling. It uses more RAM, but not that much. The single-pole RC filter you're suggesting is much nicer in the frequency domain, but in the time domain it's far worse.

WanderPanda 5y ago
Is it „far worse in the time domain“ due to its infinite impulse response?
- kragen 5y ago
  Not really? Sort of? I don't really have a good answer here. It depends on what you mean by "due to". It's certainly due to the impulse response, since in the sense I meant "far worse" the impulse response is the only thing that matters. Truncating the impulse response after five time constants wouldn't really change its output noticeably, and even if you truncated it after two or three time constants it would still be inferior to the box filter for this application, though less bad. So in that sense the problem isn't that it's infinite. Likewise, you could certainly design a direct-form IIR filter that did a perfectly adequate job of approximating a box filter for this sort of application, and that might actually be a reasonable thing to do if you wanted to do something like this with a bunch of op-amps or microwave passives instead of code. So the fact that the impulse response is infinite is neither necessary nor sufficient for the problem. The problem with the simple single-pole filter is that by putting so much weight on very recent samples, you sort of throw away some information about samples that aren't quite so recent and become more vulnerable to false triggering from a single rapid mouse movement, so you have to set the threshold higher to compensate.
- Waterluvian 5y ago
  Reading all of you sounding super smart and saying stuff I don’t recognize (but perhaps utilize without knowing the terms) used to make me feel anxious about being an impostor. Now it makes me excited that there’s so many more secrets to discover in my discipline.
  - kragen 5y ago
    Yeah, DSP has a lot of really awesome stuff in it! I recommend https://www.dspguide.com/ https://www.dspguide.com/. It turns out that pretty much any time you have code that interacts with the world outside computers, you end up doing DSP. Graphics processing algorithms are DSP; software-defined radio is DSP; music synthesis is DSP; Kalman filters for position estimation is DSP; PID controllers for thermostats or motor control are DSP; converting sonar echoes into images is DSP; electrocardiogram analysis is DSP; high-frequency trading is DSP (though most of the linear theory is not useful there). So if you're interested in programming and also interested in graphics, sound, communication, or other things outside of computers, you will appreciate having studied DSP.
  - hoseja 5y ago
    Don't worry, this is a domain of magic matlab functions and excel data analysis and multiply-named (separately invented about four times on average in different fields) terms for the same thing, with incomprehensible jargon and no simple explanation untainted by very specific industry application.

hoseja 5y ago

Please elaborate.

kragen 5y ago
For both alternatives we begin by computing how far the mouse has gone: int m = abs(dx) + abs(dy); // Manhattan distance For the single-pole RC exponential filter as WanderPanda suggested: c -= c >> 5; // exponential decay without a multiply (not actually faster on most modern CPUs) c += m; For the box filter with the running-sum table as nostrademons suggested: s += m; // update running sum size_t j = (i + 1) % n; // calculate index in prefix sum table to overwrite int d = s - t[j]; // calculate sum of last n mouse movement Manhattan distances t[j] = s; i = j; Here c, i, s, and t are all presumed to persist from one event to the next, so maybe they're part of some context struct, while in old-fashioned C they'd be static variables. If n is a compile-time constant, this will be more efficient, especially if it's a power of 2. You don't really need a separate persistent s; that's an optimization nostrademons suggested, but you could instead use a local s at the cost of an extra array-indexing operation: int s = t[i] + m; Depending on context this might not actually cost any extra time. Once you've computed your smoothed mouse velocity in c or d, you compare it against some kind of predetermined threshold, or maybe apply a smoothstep to it to get the mouse pointer size. Roughly I think WanderPanda's approach is about 12 RISCish CPU instructions, and nostrademons's approach is about 18 but works a lot better. Either way you're probably looking at about 4-8 clock cycles on one core per mouse movement, considerably less than actually drawing the mouse pointer (if you're doing it on the CPU, anyway). Does that help?

Karrot_Kream 5y ago

Agreed, a single-pole IIR filter would be cheaper and have a better frequency domain.