Join 3,497 readers in helping fund MetaFilter (Hide)


how to smooth a mouse path
March 23, 2013 4:24 PM   Subscribe

Twisted Oak Studios talk about how they smoothed the mouse path for the desktop port of the game Jack Lumber, with code examples.
posted by SpacemanStix (13 comments total) 13 users marked this as a favorite

 
Interesting solution, I'll have to bookmark that. I've done something similar before by normalising the path into points that are a regular distance apart, then drawing a new curve between those. Though that results in the last "segment" following the mouse around until you move it far enough away from the last point.
posted by lucidium at 5:02 PM on March 23, 2013


At least on my mac, none of the demo areas look any worse, except yes, the second one lags and the third one moves in a kind of weird creepy way.
posted by aubilenon at 5:32 PM on March 23, 2013


This is actually a solved problem, from missile tracking and quant trading.
posted by unSane at 6:29 PM on March 23, 2013 [8 favorites]


Well, I mean, not solved solved, but the Kalman filter is designed for *exactly* this kind of application where you are trying to run a predictive moving average on time-series data in real time. Once you get your head round it, it's easy to program an efficient implementation.
posted by unSane at 6:34 PM on March 23, 2013 [1 favorite]


(in this case, the 'error' that the Kalman Filter is trying to ignore is the wobble in the user's hand -- this is why you can use the Kalman to smooth out a data set, which it does very nicely. It resembles an exponential moving average to look at, but it's less laggy).
posted by unSane at 6:38 PM on March 23, 2013


Hmm. As a first crack at it, I probably would have played with taking some less frequent sampling of points and then reinterpolating between them with a B-spline or something.
posted by Foosnark at 7:38 PM on March 23, 2013


The problem with a spline that it can go way outside the path of the control points.
posted by idiopath at 8:08 PM on March 23, 2013 [1 favorite]


Also with a sampling of the points, you can easily miss the maxima / minima, which combined with a spline can leave a path that is pretty much unrecognizable compared to the input.
posted by idiopath at 8:09 PM on March 23, 2013


The Kalman is designed to minimize the error between the predicted next data point and the actual next data point, given the history of errors and a dynamic physical model of the process. Basically it represents the best guess at where a thing is now, given a time-series of previous data points which may be subject to noise but describe a model-able physical process (such as the flight of a missile which may be changing course constantly, and whose radar-established position may be inaccurate).
posted by unSane at 8:16 PM on March 23, 2013 [2 favorites]


Interesting, because even though the second one lags behind the cursor a bit, I much prefer its smoothing. Their chosen solution looks half-way between the non-smoothed example and the second one, in terms of line smoothness.
posted by sutt at 3:05 AM on March 24, 2013


A Kalman filter isn't necessarily the best choice for this application. The difficulty is that for a Kalman filter to work well, you need to have both a good model for your system, and you also need to know the control inputs. For a rocket in space, this is the case: you know both the dynamics governing the rocket, and you know the control inputs (which thrusters you're turning on at any time). For a human finger tracing a path, you don't necessarily have a good model of the system (because the motion is produced by hidden internal brain processes, and is neither random nor derivable a priori from Newtonian physics), and if you had the control inputs (what the player is trying to do), you wouldn't need to do the smoothing in the first place.

You can of course just make some assumptions (that a human finger is a basic rigid body in free space with inertia, that the control inputs [accelerations/forces] are random normally distributed with zero mean), but that tends to result in a Kalman filter that is not that different from an exponentially decaying weighted moving average.
posted by Pyry at 8:03 AM on March 24, 2013 [1 favorite]


Well it depends what you mean by 'work well'. In this case we aren't so interested in predicting the present position of the finger with enormous accuracy... we want a curve which is nicely smoothed and seems to track the finger in an intuitive way.

What I like about the Kalman filter is that it's so adaptable... in some cases, sure it reduces to a simpler kind of moving average, but generally you get an appropriate one.
posted by unSane at 8:22 AM on March 24, 2013


This set of slides is for one system that tries to cancel out hand tremor in surgical instruments: you can see that they use a moderately complicated Kalman filter to estimate the surgical instrument's position, but then to do the tremor cancellation they do relatively simple frequency-domain filtering (justified by the empirical observation that intentional movements and tremor occur in different frequency bands).
posted by Pyry at 8:34 AM on March 24, 2013 [4 favorites]


« Older The story of a family of dwarves snatched from the...  |  Wondering about your British c... Newer »


This thread has been archived and is closed to new comments