Date: Fri, 29 Jun 2001 03:12:05 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Quaternions / I am the ass part two This is another one of my e-mails where I embarass myself in public as penance for doing something stupid for a prolonged period of time. So, favorite topic, namely quaternions. At the [CENSORED] meeting I was complaining that quaternions were problematic because they had no multi-linear blend, and even for the case where one is known (a single linear blend), it's slow (it involves an atan2). Well, I've been meaning for some time to write an interpolation visualization app so I could look at quaternions in more detail and see if there was some way to devise fixes for these problems. I finally got around to writing one this evening, and all told it took about four hours. Now that it's working, I can safely say that it was about four hours and two years too late. I could've saved myself and our customers about four billion evaluations of atan2 if I'd done this _before_ writing the quaternion code for Granny, as opposed to after the product is nearing its second full year of existence. To make a long story short, it turns out that simply adding quaternions together as if they were regular vectors, then renormalizing, is extraordinarily close to a perfect spherical linear interpolant. It's so close, in fact, that only for very large angles (greater than 90 degrees) and watching very closely can you even tell the difference at all (by very closely, I mean your proximity to the rotating object - at a certain distance per interpolated angle, the curves are visually equivalent). So, if you have the standard "my artist made 9 poses of this guy pointing his gun around", and you want to blend them together, well guess what. You just add the quaternions and normalize. That's it. It's as easy as Euler angles, but you don't need all the cumbersome sines and cosines, and you have no gimbal lock. It gets BETTER. Since you're normalizing the quaternion anyway, you don't actually have to normalize the input coefficients. It "just works". This also explains why the 4-vector splines I've been using to play back orientation curves work so damn well - it's because they're actually pretty damn close to correct! I thought it was the adaptive tolerance fitting process that was making them come out OK, but not so. You could probably animate directly with these and it'd work just fine. I feel like the biggest ass. I'm going to add some more controls to the visualizer tomorrow, so expect another e-mail about some other part of my code that's been taking the special olympics route for the past two years. Cheers, - Casey Date: Fri, 29 Jun 2001 11:27:13 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Re: Quaternions / I am the ass part two > Here's a wacky observation, tell me if I'm wrong: literally doing > the above--that is, not weighting the quaternions, literally > averaging them--should produce the exactly correct results for > a t=0.5 interpolation, due to symmetry. So that suggests that if > you had some particular weighting, say t = 3/8, then you could > "binary search" to it, and get exact results--but the cost would > be that you'd have to renormalize at every step. Yes, that is correct. The arc is identical, its just the speed that varies - it reaches a (very slightly) greated top speed. But they both hit the midpoint at the same time. > By "the curves are visually equivalent", I hope you mean curves > over time, or with the parameterization marked out, since they > *will* "describe the same curve" (in the sense of the unparameterized > spatial curve). Yes, I mean marked. > Cool. It's very cool. > Well, has anyone else ever published that it's ok? Not that I've found, but someone's probably published it somewhere... > (Hmm, actually I think somebody's article in GD mag talked about > lerping quats instead of slerping them, but I forget who wrote > it--Jeff Lander maybe? But I remember being unclear on how much it was > a hack vs. how much it was reasonable.) Typically I believe it's discussed during the slerp operator discussion, in that slerp routines fall back to lerp routines when the quaternions are very close together (because the slerp will fail). However, the key thing here is that it works for arbitrarily large angles - there is no "very close together" condition. I always knew you could lerp close quaternions, but now I know you can lerp distant ones, and that's pretty damn important to know. - Casey Date: Fri, 29 Jun 2001 11:28:05 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Re: Quaternions / I am the ass part two > Does this produce results any different from lerping matrices? Don't know yet - I'll add that to the test. > I've used lerped+re-orthogonalized matrices many times w/out trouble. Me too - that's what I used to use before quaternions. - Casey Date: Fri, 29 Jun 2001 11:35:54 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Re: Quaternions / I am the ass part two > Linearly interpolating "quaternions" is like linearly interpolating the > arctangent of two angles -- reasonable approximation for small angles, > bizarre for large ones. Well, that's what I thought too. But that doesn't actually appear to be true. It isn't bizarre, it's perfectly reasonable. There is certainly error, so the result is "incorrect" - but it is very small error, so it turns out that it's actually a great approximation. > Note that you can do proper angular (arc length) higher-order interpolation > and multilinear interpolation of "quaternions" -- just do in linearly on the > logarithm of the quaternions. That is another thing I've wanted to test with this app, so I will be adding them shortly. More on that later. - Casey Date: Fri, 29 Jun 2001 14:47:37 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: As I expected > Note that you can do proper angular (arc length) higher-order interpolation > and multilinear interpolation of "quaternions" -- just do in linearly on the > logarithm of the quaternions. I added this to the app, and as I expected (or I should say, as I read in JGT a while back), it is not proper angular interpolation. The exponential map is not a geodesic interpolant. So you take your chances. The only time it is a geodesic is if the axes of rotation are the same, but the angles are different (for obvious reasons). If the axes are different, the interpolation becomes further and further from geodesic (ie, it diverges significantly from the slerp). However it is constant speed, unlike the normalized direct addition. So you can sort of "pick", I guess: 1. Exponential map = right speed, wrong arc 2. Quaternion addition / normalization = wrong speed, right arc 3. Slerp = right speed, right arc, can't do more than one blend I believe the exponential map also suffers from its singularities, in that if the 2pi shells of your two (or multiple) interpolants are not consistent, you will get massive error. This is roughly equivalent to the problem of having your quaternions in the wrong hemi-hypersphere, but whereas that problem is trivial to correct, picking 2pi shells seems like a nightmare, involving multiple square roots and such. But I have not tested this yet so that may be incorrect. Also I ordered the Hestenes book, as well as the Dirac book, and will read up on the exponential map once they arrive. Right now I have a very limited understanding of exponential maps so it may be that there are easy ways around some of the problems. - Casey Date: Fri, 29 Jun 2001 15:08:03 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Divergence screenshot For those interested: http://www.funkytroll.com/rotation/divergent.jpg. Red = quaternion addition / normalization Green = standard slerp Blue = quaternion log / addition / quaternion exponential Notice that the red and green curves are identical, as you would expect, but the hash marks are off. This is the "wrong speed" problem with quaternion addition plus normalization. Notice that the blue curve is "doing its own thing". This is the "wrong arc" problem with the exponential map. But, it's hash marks are equally spaced, unlike the red curve. This is for an interpolation where each axis has about a 90 degree spread. If you get down to about 45 degrees or less, all the curves converge and its all white - the exponential map's arc is visually correct, and the addtion/normalization speed is visually correct. So it's only when you hit 60 degrees and up that you start to see the two slerp alternatives screw up (see http://www.funkytroll.com/rotation/equivalent.jpg). Apologies to [CENSORED] for not showing the matrix lerp. I ran out of primary colors. - Casey Date: Fri, 29 Jun 2001 15:43:16 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Multi-point interpolation So, I tested multi-point interpolation on exponential maps as well, and not surprisingly, they give almost identical results to quaternion addition + normalization, however, since they don't have a normalization step, they do not have the nice property of "automatically adjusting their coefficients". So for non-normalized coefficients (ie, they don't sum to one), the exponential map is completely wrong (as you would expect), but for normalized coefficients both methods give the same visual results. I can construct cases where they diverge by picking largely spaced samples to interpolate between, but in these cases I have no arbiter so I don't actually know who is more "correct". I suspect the same conditions are true, however: the addition + normalization curve moves through the space non-linearly, but along more correct arcs, whereas the exponential map version moves linearly but along less correct arcs. It would be interesting to implement a "correct" multi-point orientation blend, whereby correct I mean it satisfies some criteria that everyone agrees is optimal for multi-point blending, and test the other two methods against it. Is there such a method? - Casey Date: Fri, 29 Jun 2001 20:29:44 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Questionable interpolation with exponential map See http://www.funkytroll.com/rotation/expsucking.jpg. Notice that the red (addition+normalization) and green (slerp) curves do the sane thing, but the blue (exponential map) curves are off in complete nonsenseland. This is further evidence that, in addition to being slow, the exponential map is also unreliable. It could just be that I have a bug in my exponential map code, but I dropped the code that Tim posted on flipcode in and it does the exact same thing, so I don't think I have a typo or anything. When I get the Clifford Algebra books I'll come back and re-check all the exponential map code and verify this, but otherwise, I'd say the exponential map is not a good choice for animation purposes (although it obviously has important uses elsewhere). It appears to be both more expensive and less robust. - Casey Date: Tue, 3 Jul 2001 11:24:46 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Re: Quaternions / I am the ass part two > On a similar note, on Flight Combat I was interpolating matrices > directly and renormalizing them. Well, actually just interpolating > the X and Y vector, then crossing them to get the Z vector, then > recrossing Z and X to get Y. Works great. I know its goofy, but > again, works pretty nicely. Actually after posting the previous screenshots I did go back and add this in to the visualizer, and unless I have a bug somewhere, it actually is a pretty nasty interpolator. I imagine it's good for orientations that are really close to eachother (interpolating orientations sent over the net is maybe what you were using it for?), but for the case we're trying to solve (blending several different animations together), it looks like it would be disastrous. From playing with it, not only is your interpolation massively nonlinear (VERY different from adding and normalizing in quaternion space, even though they seem like similar operations, because they're interpreted very differently out the back end). You can get all kinds of twists and distortions introduced - really nasty stuff. It's much worse than the exponential map curves, which looked like they would be workable, albeit not as nice as the add-plus-normalize in terms of speed and interpolation quality. - Casey Date: Wed, 4 Jul 2001 09:11:59 -0700 (PDT) From: Casey Muratori Subject: Re: Quaternions / I am the ass part two > Okay, I want to defend my noble algorithm against Caseys calling it "nasty". Sorry - didn't mean to hurt the interpolator's feelings! Sometimes I don't respect the emotions of our mathematical constructions as much as I should :) > It's primary virtue is speed. The inputs and outputs are both in the > space we ultimately care about for transforming points, which is to > say, matrices. Actually, I'm not convinced that it's faster than quaternion add-then-normalize. Because you have to do 6 mac's per orientation, as opposed to 4 mac's in the quaternion addition case, and then the back end requires 2 cross-products and 2 normalizations. The back end for quaternion-to-matrix requires only one normalization (which, other than the sqrt, can be rolled into the quaternion-to-matrix multiplies so you don't get 4 extra multiplies), and is slightly more expensive than 2 cross-products. So in general matrix interpolation is a bad idea, because not only does it produce bad curves, but it also scales worse with more orientations and eats more sqrts on the back-end (which I suppose you don't care about on 3DNow or something, but on the Pentium it's death warmed over). > But the speed advantage is large, it only takes a few multiplies, 2 inverse > square roots. I don't think it has a speed advantage. I think it would beat slerp'ing, and it may or may not beat exponential map, but I'd put hard money on it losing to add-then-normalize if one were to hand-optimize each. > And if you can contrive to keep the matrices close, like, > each axis within 90 degrees, it seemed to work well (though I confess I have > not exhaustively tested it myself). At 45 it's just unpleasant, and at 90 it starts doing really bad things. It can do things you had no idea were possible during an interpolation :) The problem is that the third axis (the one not being interpolated directly) starts moving in patterns that aren't even arcs - they're like squiggles and things, and they make really sharp turns like right angles and stuff. > It may be that some of the particular nastinesses you saw, flipping, and the > like could be mimimized by picking the two axes better. For example, > crossing the axis that moves the most with the one that moves the least, or > something like that. I have no clue there. That is certainly possible. I haven't played with it much. - Casey Date: Thu, 3 Jan 2002 13:35:57 -0800 (Pacific Standard Time) From: Casey Muratori Subject: Re: New gdmag article "Hacking Quaternions" > But, I'd like to incorporate any comments that people have. Looks good to me - just one comment: > If q0 and q1 lie on opposing points of the sphere, the chord will pass > through the origin and normalization will be undefined. But that's > okay -- unless you're doing something wacky, you don't want your > quaternions to be further than 90 degrees apart in the first place. > (Because every rotation has 2 quaternion representations on the unit > sphere, and you want to pick the closest ones to interpolate between.) It might be worth emphasizing here that _no_ quaternion interpolation has to involve a greater than 90 degree separation - you can always pick some <= 90 degree case that is equivalent. You and I both know that this is not the same as saying that you can't interpolate between two quaternions whose _rotations_ are > 90 degrees apart, but I'm not sure people reading the article will... you know what I mean? So it might be worth taking a second to explain why this is not a restriction in any way. - Casey