Date: Mon, 15 Jul 2002 01:20:22 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: Rotation interpolation, the topic that will never die [VERY LONG] ([CENSORED], [CENSORED], and myself were having a discussion about how crappy "Linear Combination of Transformations" was in this year's SIGGRAPH - the discussion recently led to some stuff that is probably of general interest, so I am moving the thread over here). -------------- I am having a thought. The reason you cannot commute rotations, or do direct multi-point combinations, in rotation space is because you are on the surface of a sphere. If we assume that quaternions are a good mapping for the actual space of rotations (which I believe they are), we're talking about the unit 4D hypersphere. OK, so now I tell you that I want commutivity back, and I will give up something in return. Adding quaternion components directly gives this to you by linearizing the space into the same euclidean coordinates that the sphere is embedded in. For the case of three or less points, it is just a plane, the plane that contains the three or less points on the surface of the sphere. This plane is then projected back onto the sphere during normalization. So, that is the mapping. Now here's the thought part, which is admittedly not a very large thought, but one I haven't had before. Specifically, since the exponential map _also_ linearizes the space, but does not produce the same results, it must have some other easily visualizable projection. ie., I can visualize the concept of a planar shape projected outward onto a sphere, and that kind of linearization makes clear sense. But what is the mental model for the kind of linearization that the exponential map is doing? So that made me want to visualize it. Well, it turns out it's actually really straightforward to visualize it - essentially you can think of it as "cutting" the hypersphere along the w-equator, and stretching it out so that even slices along the w axis map to concentric rings on a 4D hyperplane (which is, of course, are the familiar 3D spherical shells). Now, these aren't actually equidistant, I don't think, because the w axis of the sphere is cos(theta/2), whereas the exponential map radius is theta, so the rings can only be equidistant on one side of the map. So people say that the exponential map is a 3D thing, and I guess it is for purposes of its properties, but _that's not what it really is_. What it really is is a 4D thing; a point on the surface of 4D hyperplane, which was constructed via projection of the hypersphere. Now that I think about it, I guess this could be why the geometry algebra people store 4 elements for the exponential map? I have no idea, I don't know geometry algebra at all. Anyhow, all this lead me to a fascinating realization, which I should have come to long, long, long ago, but which became apparent to me only just now. The linear addition of quaternions method warps the internal spacing of a interpolation patch grid so that movement inside it is commutative - the exponential map, on the other hand, warps the _edges_ so that the inside has constant spacing! That is so enlightening to me, I don't know why I didn't think of it that way before, because it's really quite obvious considering the visualizations I posted last year about this time (the interpolation graphs). I had internalized the concept of the internal warping for quats, but I hadn't groked the edge warping for the exponential map, because I just wasn't thinking in that direction. Here are some constructions you can use to demonstrate how this happens. Take a 3D sphere, because it is easier to visualize (you can visualize this with the real 4D hypersphere as well, so it's not a trick to do it lower - it works the same in both). Now, if you do the exponential map warping of it like I described previously, then you have essentially a 2D "bullseye" pattern, where the rings of the bullseye correspond to slices through your 3D sphere along one axis, let's say the Z axis. Now, suppose you have two points you are going to interpolate, both of which lie on the same Z-slice (the same ring of the bullseye). If you are doing quat interpolation, then any interpolation always stays on the z-slice. YOU CANNOT LEAVE THE Z-SLICE IN QUATS. You can (and will) leave the sphere, but you cannot leave the z-slice with only two quats to interpolate between. On the other hand, if you interpolate in exponential space, you are interpolating in the bullseye. The interpolation line leaves the bullseye ring - it tunnels through it just like quats tunnel through the ring on the sphere. However, because the mapping is different, look at what that means - because the _length_ of a vector in the bullseye corresponds to the location of the _slice_ on the original sphere, the fact that you're not traveling along the bullseye ring means that you will actually _leave _ the z-slice and come back onto it only at the very end of the interpolation. In a sense, you have _warped_ the rings of the sphere to give yourself linearity. Instead of changing the length of your steps along the interpolation arc, you changed the length of the arc itself. An intuitive result is that this means the amount of warping you get is proportional to the distance between the orientations your interpolating. This is analagous to the distance warping that's happening in quatland - so they both share this property. I assume this makes karmic sense, because hey, small interpolations are practically linear already, so it makes sense that you need more warping the bigger (and more obviously nonlinear) you get. All this was relatively mind-expanding for me, because I am bad in four dimensions. But I kind of felt like I was really getting it for a while today. When I got back from playing DDR, I decided that all of this must have already been known to some smart people, so I flipped through all of "Geometry from a Differential Viewpoint", which has been sitting on my shelf forever but which I'd never opened. It turns out I should've opened it sooner, because basically this entire book is about this problem - like, literally, it could have been titled "understanding spheres". It's like, hey, let's talk about non-Euclidean geometry, and all the properties you can have for moving between points on its surface, and how we prove those. In the hour or so that I looked through it, I obviously didn't grok a whole lot of the specifics, because it's pretty notation-heavy. However, I was able to learn a something that is interesting: we all know that the exponential map is a "map", because hey, it's the "exponential map" after all. But is normalized lerping of quaternions a map, in the sense that some smart person thought of it and gave it a name and it got into math books at some point? From my cursory reading, the answer appears to be yes. It is called "central projection", and it is the projection that (surprise surprise) maps great circles to lines. In other words, the shortest path on the sphere becomes the shortest path on the plane, exactly what we've observed (and proved) regarding normalized lerping of quaternions. Now, some guy named Beltrami apparently worked out a bunch of crap relating to this projection, such as doing the math to rigorously define the curvature that's induced due to the planar preservation of the shortest path. However, it was pretty dense and I'm tired, so I will have to take a look at it another day. Also, it wasn't clear about whether or not the analyses generalized to 4D hyperspheres (the central projection was only discussed for 3D spheres). Although if it doesn't, I'm sure someone has done it subsequently, because these differential geometer guys are really into their coordinate freeness. More important than all this, of course, was that I realized that there's really no reason why we have to pigeonhole ourselves into thinking of rotation linearization in terms of exponential map vs. slerp vs. normalized quaternion lerp. In fact, we could use _any_ kind of linearization technique - there must be at least one, if not many, more ways we could think of to take a set of points on a sphere and map them onto a plane. I assume we could "just use" any cartography projection, right? I mean, what would it mean to have a mercator projection interpolant? Would that be interesting? I'm going to write a mathvis module tomorrow night that draws interpolation grids for all the projections I can think of, so I can see what the situation is. This is very interesting. At some point a while back, Charles sent out a message about some other paper on interpolating rotations that he found - I assume that this was a similar situation, ie., another linearization of the sphere that someone had tried. I'll have to look at that as well. - Casey Date: Thu, 25 Jul 2002 09:26:18 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: RE: Rotation interpolation, the topic that will never die [VERY LONG] > As an example. Imagine your neck is looking directly left. Then you want > to look directly to the right. > With a slerp or a quaternion lerp (as per Johnathan Blow's article) the > rotation axis is not well defined, with a naive lerp of RP you get a nice > trajectory. What about the quaternion methods is not well defined? In this example, lets say Y is up, Z is forward. Looking 90 degrees to the left is: 0, sin(Pi/4), 0, cos(Pi/4) Looking 90 degrees to the right is: 0, sin(-Pi/4), 0, cos(-Pi/4) Both a slerp and a lerp will use Y as the rotation axis (obviously), because both are linear blends of those two values, so they can't do anything _else_ (the x and z components are 0). - Casey Date: Thu, 25 Jul 2002 10:33:46 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: RE: Rotation interpolation, the topic that will never die [VERY LONG] > I was completely out to lunch on the Lerp thing (unless a quat is negative), > but I think that a slerp might could be +Y or -Y. I think luncheon might still be on. Lerp and Slerp always pick the same trajectory - so they're essentially equivalent. It's just that the interpolation speed is not constant on a lerp, whereas it is on a slerp. With both methods, you always pre-condition so that they're in the same hemi-hypersphere, or hyper-hemisphere, depending on your choice of hyphenation. > If you have (pi/4 + epsilon) your trajectory is not ergonomically optimal. Well if you specifically _don't_ want the shortest path rotation, then just don't precondition and use the full 720 degree rotation. Then neither will ever pick the "bad" rotation you're alluding to, which is the rotate around the back like some kind of fucked up Excorcist baby rotation, because remember that quaternions use half-angles, so "pi/4 + epsilon" does not look qualitatively any different than pi/4 itself. So, you kind of get the best of both worlds this way - if you want shortest-path, do the dot-product pre-conditioner. If you don't, then don't, and it will remember the winding. - Casey Date: Sat, 27 Jul 2002 10:34:31 -0700 (Pacific Daylight Time) From: Casey Muratori Subject: RE: Rotation interpolation, the topic that will never die [VERY LONG] > In which case dq is not well defined for a 180 degree rotation as the path > of minimal distance on the sphere could go either way. Well, in less I'm being equally dense (not an unusual situation), then no, because the angles are theta/2, not theta, so there is no ambiguity at 180. The ambiguity is at 360. Does that make sense? That's why I was saying "if you don't want it to take the shortest path, then don't do the dot-product flip". In other words, most people do: if (a dot b) < 0 then a = -a before they slerp, which maps the 720 degree space of quaternions onto a 360 degree space. In this situation, then yes, you get the 180 degree ambiguity. But that _is not_ inherent in quaternions, because they understand the full 360 degrees as being unique and that the shortest path is always to unwind fully until you've gone one full revolution. It's only once you've handicapped them with the negation that they will have an ambiguity at 180. I could be smoking crack here, but I'm fairly certain. I mean, the way I think of it, the "half way" point in quaternions is one _full_ revolution. So if you ask a quaternion to go from, say, 270 degrees to 0 degrees, it's NOT going to go "up" in degrees to 360. It's going to go all the way back. People do the flip trick to _make_ it go up instead, but that's not what it will normally do. I always thought of the 720 range as somewhat useless, but your example was very enlightening because it made me realize that you can actually use it your advantage all over the place if you're not dealing with random artist-created crap (which is what I deal with). If you set up things as a physics system, then you can actually have it remember the twist properly, and that's awesome. > Disclaimer: I typically use PD controllers for my interpolation so I may > have this formulation completely wrong. It should work equivalently for a PD controller, again, provided you don't flip your quaternions to reduce the range. - Casey