Thread: Re: [Algorithms] Low pass filter on quaternions
Brought to you by:
vexxed72
Menu
▾
▴
gdalgorithms-list
|
From: Juan L. <re...@gm...> - 2010-03-28 17:24:59
|
I don't have any code handy, but since for a lowpass filter you need the "difference", I guess you can obtain that with the inverse or something similar.. Also keep in mind it may be easier to just lowpass a 3x3 matrix since you want to rule out high freq noise ------Original Message------ From: John McCutchan To: Game Development Algorithms ReplyTo: Game Development Algorithms Subject: [Algorithms] Low pass filter on quaternions Sent: Mar 27, 2010 23:14 Hi, I have a sequence of quaternions and want to filter out any high frequency changes. I'm wondering if anyone has a paper or some code for performing a low pass filter on quaternions? Thanks, -- John McCutchan <jo...@jo...> ------------------------------------------------------------------------------ Download Intel® Parallel Studio Eval Try the new software tools for yourself. Speed compiling, find bugs proactively, and fine-tune applications for parallel performance. See why Intel Parallel Studio got high marks during beta. http://p.sf.net/sfu/intel-sw-dev _______________________________________________ GDAlgorithms-list mailing list GDA...@li... https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list Archives: http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
|
From: Jon W. <jw...@gm...> - 2010-03-28 17:58:27
|
The problem is that Quaternions are not quite linear enough. Running a naive filter on the axis component when the rotation is close to identity (and the axis component is small) may cause excessive jitter. The motion capture tools people have had this problem for a long time. I believe they convert to Euler, and run low-pass filtering there (possibly higher than just first order), and then convert back, because Euler is less sensitive around any particular spot. I'd also be interested in hearing from anyone who has done this in anger! Sincerely, jw -- Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable. On Sun, Mar 28, 2010 at 10:22 AM, Juan Linietsky <re...@gm...> wrote: > I don't have any code handy, but since for a lowpass filter you need the > "difference", I guess you can obtain that with the inverse or something > similar.. Also keep in mind it may be easier to just lowpass a 3x3 matrix > since you want to rule out high freq noise > ------Original Message------ > From: John McCutchan > To: Game Development Algorithms > ReplyTo: Game Development Algorithms > Subject: [Algorithms] Low pass filter on quaternions > Sent: Mar 27, 2010 23:14 > > Hi, > > I have a sequence of quaternions and want to filter out any high > frequency changes. I'm wondering if anyone has a paper or some code > for performing a low pass filter on quaternions? > > Thanks, > -- > John McCutchan <jo...@jo...> > > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > |
|
From: Jason H. <jh...@st...> - 2010-03-28 19:59:12
|
The typical way to handle Wiimote pointer jitter (2D) is to attach a simple bimodal spring to the XY position on screen. The clamped mode is enacted anytime the centroid of the last few samples is within some squared tolerance of the samples; return the centroid as long as that's true. When the most recent sample deviates, spring toward the current sample value by lerping toward it at about 30% per frame for a few frames, after which you just return the current sample. This gives a smooth transition between the modes. For motion control, we tended to handle the smoothing within each object control rather than at the hardware driver level, since there were some control schemes that look for spikes and thresholds, and any kind of filters we applied would ultimately mask those sorts of details. I do recall that we tried various methods for smoothing. One of them maintained two axes in space for the up and forward. They were allowed to drift away from orthonormal while smoothing points in space, since we did non-linear smoothing. When returning the orientation of the remote to the game, we would re-orthogonalize the orientation by holding the "important axis" fixed--that is, the one that the user is primarily interested in controlling cleanly during the current activity--without modifying the internal axes we were tracking. Seemed to work ok, but again, the technique should probably match the control in each section of the game. JH Jason Hughes President Steel Penny Games, Inc. Austin, TX On 3/28/2010 12:58 PM, Jon Watte wrote: > The problem is that Quaternions are not quite linear enough. Running a > naive filter on the axis component when the rotation is close to > identity (and the axis component is small) may cause excessive jitter. > > The motion capture tools people have had this problem for a long time. > I believe they convert to Euler, and run low-pass filtering there > (possibly higher than just first order), and then convert back, > because Euler is less sensitive around any particular spot. > > I'd also be interested in hearing from anyone who has done this in anger! > > Sincerely, > > jw > > > -- > Americans might object: there is no way we would sacrifice our living > standards for the benefit of people in the rest of the world. > Nevertheless, whether we get there willingly or not, we shall soon > have lower consumption rates, because our present rates are > unsustainable. > > > > On Sun, Mar 28, 2010 at 10:22 AM, Juan Linietsky <re...@gm... > <mailto:re...@gm...>> wrote: > > I don't have any code handy, but since for a lowpass filter you > need the "difference", I guess you can obtain that with the > inverse or something similar.. Also keep in mind it may be easier > to just lowpass a 3x3 matrix since you want to rule out high freq > noise > ------Original Message------ > From: John McCutchan > To: Game Development Algorithms > ReplyTo: Game Development Algorithms > Subject: [Algorithms] Low pass filter on quaternions > Sent: Mar 27, 2010 23:14 > > Hi, > > I have a sequence of quaternions and want to filter out any high > frequency changes. I'm wondering if anyone has a paper or some code > for performing a low pass filter on quaternions? > > Thanks, > -- > John McCutchan <jo...@jo... > <mailto:jo...@jo...>> > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > <mailto:GDA...@li...> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > <mailto:GDA...@li...> > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list > > > > ------------------------------------------------------------------------------ > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > > > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list |
|
From: Tom P. <ga...@fa...> - 2010-03-29 15:48:00
|
> The problem is that Quaternions are not quite linear enough. Running a > naive filter on the axis component when the rotation is close to identity > (and the axis component is small) may cause excessive jitter. Since the rotation is close to zero, though, it doesn't really matter if your axis flips all around. The net result is still one of very little rotation. > I'd also be interested in hearing from anyone who has done this in anger! Years ago, before I had any idea what quaternions meant, I just did IIR-style filtering on them. You know, "add 10% of this frame's value to 90% of the current frame's value, and use that as the new current value." Despite the fact that this is horrifying to many purists, it actually worked out well for the application I was using it in. Doing this with controller input may lead to an undesirable amount of lag, though. When this question was posed, I started wondering how they do it on mouse drivers, since there is no apparent lag between me moving the mouse and the cursor moving on the screen. Maybe the solution there is that they run at a much higher sample rate? Maybe the filtering is done in hardware? Regardless of the solution for the filtered quaternions, I would think that lag would be preferable to overshoot. The IIR filters certainly meet that criteria. :) -tom! -- |
|
From: Fabian G. <ry...@gm...> - 2010-03-29 17:10:06
|
On 29.03.2010 17:31, Tom Plunket wrote: > >> The problem is that Quaternions are not quite linear enough. Running a >> naive filter on the axis component when the rotation is close to identity >> (and the axis component is small) may cause excessive jitter. > > Since the rotation is close to zero, though, it doesn't really matter if > your axis flips all around. The net result is still one of very little > rotation. > >> I'd also be interested in hearing from anyone who has done this in anger! > > Years ago, before I had any idea what quaternions meant, I just did > IIR-style filtering on them. You know, "add 10% of this frame's value to > 90% of the current frame's value, and use that as the new current value." > Despite the fact that this is horrifying to many purists, it actually > worked out well for the application I was using it in. Doing this with > controller input may lead to an undesirable amount of lag, though. I don't see any problems with this whatsoever, and don't see why "purists" would. Building linear combinations of quaternions (and that's what filters do) is a perfectly well-defined and reasonable thing to do. You should normalize the result before you use it though - but don't feed the normalized output back into IIR filters, use the unnormalized value there (or you introduce nonlinearities into the filter). To be clear, the normalization isn't a hack; it's a perfectly fine projection operator, and normalize(w_0*q_0 + w_1*q_1 + ...) behaves pretty much like one would expect, except for interpolated paths not being constant velocity. But all other parametrizations suffer from other and usually more serious limitations that make them a lot less suitable for filtering in: spherical linear interpolation yields constant velocity but requires you to write linear combination betweeen 3 or more participants as blend tree, and different ways of building this tree yield different results; Euler angles have gimbal lock and the interpolation between rotations "a" and "b" doesn't take the shortest path between them; taking the log of a and b, interpolating, then exponentiating likewise doesn't take the shortest path. The rotation group SO(3) is fundamentally non-flat; as a result, there's no "right" way to linearize rotations and interpolate/filter them, just different ways to get rid of the curvature with different tradeoffs. And yes, the "axis component" is jittery if your rotation is close to identity, but that's perfectly reasonable. A rotation of 1e-5 radians around the x axis *is* similar to a rotation of 1e-5 radians around the axis (0.8,0.6,0), by any reasonable metric - distance of the resulting rotation matrix to the identity matrix in any matrix norm, relative error of transformed points, or plain magnitude of the angle. The axis for small rotations isn't jittery because of anything to do with the quaternion representation, it's jittery because the problem of finding the axis of rotation is inherently ill-posed for a transformation that's close to identity. But the quaternion doesn't store (axis, angle), it stores (cos(angle/2), sin(angle/2)*axis), and that is perfectly well-behaved near identity. > When this question was posed, I started wondering how they do it on mouse > drivers, since there is no apparent lag between me moving the mouse and > the cursor moving on the screen. Maybe the solution there is that they > run at a much higher sample rate? Maybe the filtering is done in > hardware? Mouse driver's dont filter. The only transform applied to the input mickeys (=x/y deltas) is pointer ballistics (which, roughly speaking, makes slow mouse movements slower and fast movements faster), but there's no noise at all in what you get from the hardware. As long as the mouse doesn't move, you really do get exactly zero, every frame. I don't know whether the hardware does any filtering or if the mechanisms are inherently noise-resilient (as old mechanical and opto-mechanical mice were), but what you get from the hardware via USB is already perfectly clean. -Fabian |
|
From: Tom F. <tom...@ee...> - 2010-03-30 17:49:09
|
Linear interpolation and renormalization of quaternions is totally fine. As always, the standard text on this is: http://number-none.com/product/Understanding%20Slerp,%20Then%20Not%20Using%2 0It/ TomF. > -----Original Message----- > From: Fabian Giesen [mailto:ry...@gm...] > Sent: Monday, March 29, 2010 10:10 AM > To: Game Development Algorithms > Subject: Re: [Algorithms] Low pass filter on quaternions > > On 29.03.2010 17:31, Tom Plunket wrote: > > > >> The problem is that Quaternions are not quite linear enough. Running > a > >> naive filter on the axis component when the rotation is close to > identity > >> (and the axis component is small) may cause excessive jitter. > > > > Since the rotation is close to zero, though, it doesn't really matter > if > > your axis flips all around. The net result is still one of very > little > > rotation. > > > >> I'd also be interested in hearing from anyone who has done this in > anger! > > > > Years ago, before I had any idea what quaternions meant, I just did > > IIR-style filtering on them. You know, "add 10% of this frame's > value to > > 90% of the current frame's value, and use that as the new current > value." > > Despite the fact that this is horrifying to many purists, it actually > > worked out well for the application I was using it in. Doing this > with > > controller input may lead to an undesirable amount of lag, though. > > I don't see any problems with this whatsoever, and don't see why > "purists" would. Building linear combinations of quaternions (and > that's > what filters do) is a perfectly well-defined and reasonable thing to > do. > You should normalize the result before you use it though - but don't > feed the normalized output back into IIR filters, use the unnormalized > value there (or you introduce nonlinearities into the filter). > > To be clear, the normalization isn't a hack; it's a perfectly fine > projection operator, and normalize(w_0*q_0 + w_1*q_1 + ...) behaves > pretty much like one would expect, except for interpolated paths not > being constant velocity. But all other parametrizations suffer from > other and usually more serious limitations that make them a lot less > suitable for filtering in: spherical linear interpolation yields > constant velocity but requires you to write linear combination betweeen > 3 or more participants as blend tree, and different ways of building > this tree yield different results; Euler angles have gimbal lock and > the > interpolation between rotations "a" and "b" doesn't take the shortest > path between them; taking the log of a and b, interpolating, then > exponentiating likewise doesn't take the shortest path. The rotation > group SO(3) is fundamentally non-flat; as a result, there's no "right" > way to linearize rotations and interpolate/filter them, just different > ways to get rid of the curvature with different tradeoffs. > > And yes, the "axis component" is jittery if your rotation is close to > identity, but that's perfectly reasonable. A rotation of 1e-5 radians > around the x axis *is* similar to a rotation of 1e-5 radians around the > axis (0.8,0.6,0), by any reasonable metric - distance of the resulting > rotation matrix to the identity matrix in any matrix norm, relative > error of transformed points, or plain magnitude of the angle. The axis > for small rotations isn't jittery because of anything to do with the > quaternion representation, it's jittery because the problem of finding > the axis of rotation is inherently ill-posed for a transformation > that's > close to identity. > > But the quaternion doesn't store (axis, angle), it stores > (cos(angle/2), > sin(angle/2)*axis), and that is perfectly well-behaved near identity. > > > When this question was posed, I started wondering how they do it on > mouse > > drivers, since there is no apparent lag between me moving the mouse > and > > the cursor moving on the screen. Maybe the solution there is that > they > > run at a much higher sample rate? Maybe the filtering is done in > > hardware? > > Mouse driver's dont filter. The only transform applied to the input > mickeys (=x/y deltas) is pointer ballistics (which, roughly speaking, > makes slow mouse movements slower and fast movements faster), but > there's no noise at all in what you get from the hardware. As long as > the mouse doesn't move, you really do get exactly zero, every frame. > > I don't know whether the hardware does any filtering or if the > mechanisms are inherently noise-resilient (as old mechanical and > opto-mechanical mice were), but what you get from the hardware via USB > is already perfectly clean. > > -Fabian > > ----------------------------------------------------------------------- > ------- > Download Intel® Parallel Studio Eval > Try the new software tools for yourself. Speed compiling, find bugs > proactively, and fine-tune applications for parallel performance. > See why Intel Parallel Studio got high marks during beta. > http://p.sf.net/sfu/intel-sw-dev > _______________________________________________ > GDAlgorithms-list mailing list > GDA...@li... > https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list > Archives: > http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms- > list > No virus found in this incoming message. > Checked by AVG - www.avg.com > Version: 8.5.437 / Virus Database: 271.1.1/2742 - Release Date: > 03/29/10 06:32:00 |
|
From: Jon W. <jw...@gm...> - 2010-03-29 18:04:12
|
"90% of this, 10% of that" is exactly a first-order IIR filter implemented as a leaky integrator. However, it's not true that "quick changes" have to be killed by an IIR. If you view this as traditional signal analysis with four channels, and you go higher-order (or multiple second-order, which is generally more stable) you can do things like combining a highpass filter (I suppose to to weed out "wave") with a wide notch filter (to weed out noise, but still allow really strong transients such as presumably "wrist snap" movements). Sincerely, jw -- Americans might object: there is no way we would sacrifice our living standards for the benefit of people in the rest of the world. Nevertheless, whether we get there willingly or not, we shall soon have lower consumption rates, because our present rates are unsustainable. On Mon, Mar 29, 2010 at 8:31 AM, Tom Plunket <ga...@fa...> wrote: > > > The problem is that Quaternions are not quite linear enough. Running a > > naive filter on the axis component when the rotation is close to identity > > (and the axis component is small) may cause excessive jitter. > > Since the rotation is close to zero, though, it doesn't really matter if > your axis flips all around. The net result is still one of very little > rotation. > > > I'd also be interested in hearing from anyone who has done this in anger! > > Years ago, before I had any idea what quaternions meant, I just did > IIR-style filtering on them. You know, "add 10% of this frame's value to > 90% of the current frame's value, and use that as the new current value." > Despite the fact that this is horrifying to many purists, it actually > worked out well for the application I was using it in. Doing this with > controller input may lead to an undesirable amount of lag, though. > > When this question was posed, I started wondering how they do it on mouse > drivers, since there is no apparent lag between me moving the mouse and > the cursor moving on the screen. Maybe the solution there is that they > run at a much higher sample rate? Maybe the filtering is done in > hardware? > > Regardless of the solution for the filtered quaternions, I would think > that lag would be preferable to overshoot. The IIR filters certainly meet > that criteria. :) > > > -tom! > > -- > > |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X