The various Mac rumor/pundit folks have been predicting the demise of the Mac Mini, which was weary because it's a great little machine. I use mine in the living room as a home-theater PC, and it works really well... I plan to write more about that soon. But in any case, it turns out the "reports of its demise have been greatly exaggerated," because today Steve Jobs announced a new, upgraded line of Mac Minis. Yay! Long live the Mini!

I'm glad that Google is in the world, and I imagine that most people would agree. Sure they're practically taking over the Internet, but so far they seem to mostly benevolent about it. Sure they have a few lapses in judgement like China and (more recently) Dell, but mostly they're good guys. I think of them as the BDFL's of the Internet... if they hired Guido they can't be all bad. :-) They set a very high bar for software quality, just like (if I may say so) my employer, Apple. They have an office here in Santa Monica just a few blocks from mine, so I feel a certain connection with them.

That's why I feel obliged to make a suggestion: I've noticed that on Google Maps, the little green arrow is often not quite accurate. It's usually on the right block, but it's often not on the right building... often three or four doors away from the right location. I think it'd make a good project for the "one day a week" that Google engineers are supposed to spend thinking about new, cool stuff. I mean, it's no MentalPlex, but I bet there's some way to analyze a set of data comparing where Google Maps thinks an address is to where it actually is (as manually indicated by human data entry), correlate the errors to some other variable(s), and construct an algorithm that could be used to correct whatever approximations are inherent in the geolocation data sets that they're using. I mean, how cool would that be, if you could type an address into Google Earth and it showed you where the front door was, with an error margin of 3 feet instead of 300 feet?

So that's my idea. I don't have any illusions that Google researchers haven't already thought about this problem, but maybe with a little gentle prodding they'll look at it from a fresh angle. Consider this post a friendly "open letter" to my esteemed neighbors. :-)

Here's another technical article. The last one was about rendering; this time I'm switching to animation (specifically, rotation).

Euler angles have well-known limitations, such as gimbal lock. Another slightly-less-well-known issue is the way in which there are many different (rx,ry,rz) triplets that all encode the same orientation, and writing a program to choose the "right" triplet for a given orientation is sometimes a lot more difficult than it would seem. This problem can come up when implementing a user-interface control for instance, or a dynamics engine. Any time that a program has an non-Euler orientation (expressed as a quaternion, a matrix, and axis and an angle, or whatever) and it has to convert it to a triplet of Euler angles that must fit in smoothly with a sequence of other Euler angles, you have to be careful how you choose which triplet to use.

It's not hard to find convert a quaternion to a valid triplet triplet of Euler angles, of course. Ken Shoemake's article in Graphics Gems IV (for instance) demonstrates how to do that. But applying his recipe to a sequence of smoothly-varying orientations doesn't necessarily produce a sequence of smoothly-varying Euler triplets. For instance, because you can add or subtract any multiple of 360 degrees to any of the three Euler angles and the triplet still describes the same orientation, our valid sequence of Euler triplets might have objectionable 360-degree discontinuities in it. We could make a rule that indicates which value is preferred (like, the angle with the smallest absolute value), but that would only serve to define where the discontinuities occur, not eliminate them. For instance, imagine that we're writing a physics simulator and we run it on an object with a angular velocity around the x-axis. We would expect the x-angle to be a linear function of time, but if compute it by applying Ken's formulae to quaternions, we get a sawtooth function instead:

This problem is solved easily enough by taking the previous frame's Euler angles into account when converting each frame's orientation from a quaternion to Euler angles. After finding a triplet that corresponds to the given quaternion (which probably has angles in some nominal range like -π ... π), we can add or subtract some multiple of 2π to each angle so that it's as close to the previous values as possible. That'll restore our x-angle function to the linear shape that we'd expect it to have.

There's one more problem though, and this one's subtler. If you implement a rotation manipulator and you notice that 180-degree "flips" are creeping into your results, you'll realize there's another choice (like the ±2π one described above) that our conversion has to make. To understand this one, let's start by visualizing an example. Suppose we have an object that's rotated by 180 degrees around its z axis, and -90 degrees around its x axis (assuming ZXY rotation order). That object would be facing up, with its head towards us. Now suppose we took a different object and rotated it by -90 degrees around its x axis, and 180 degrees around its y axis. The second object would be in exactly the same position: facing up, with its head towards us. But these two sets of angles (-90,0,180 and -90,180,0) aren't merely different by multiples of 360 degrees... something else is going on. With a little bit more spatial visualization, we notice that it seems we can generalize it with the following relation:

where X, Y, and Z are rotation operators, and [θ, φ, ψ] is our ZXY Euler triplet. But if we're going to use this "180 degree identity", we need more than spatial intuition... we must show that it's really correct. We can do that by converting the rotation operators to quaternions, so that we have an algebra with which to manipulate them. Because we can express rotation θ around a unit vector a using the quaternion

our three rotation operators become

And the two sides of the 180-degree identity can be written

and

If you multiply-out both of those expressions (keeping in mind that i² = j² = k² = i j k = -1) then you'll find them equal. That's more algebra than I'm going to include in this article; I verified it using Mathematica and you should feel free to convince yourself, too. The point is that you can use this identity (in combination with the 360-degree property mentioned above) to convert quaternions to Euler angles gracefully, as follows:

Algorithm

Here's a summary of this technique, then. If you have a set of "reference" angles [θ, φ, ψ] and a quaternion q′ that you want to convert to "similar" angles [θ′, φ′, ψ′], then first convert the quaternion q′ to a triplet [θ₀, φ₀, ψ₀]. Then add/subtract multiples of 360 degrees:

(where n_θ1, n_φ1, and n_ψ1 are integers) in order to minimize the distance from the reference angles,

do the same thing for the angles produced by the 180-degree identity:

and pick whichever triplet ([&theta₁, &phi₁, &psi₁] or [&theta₂, &phi₂, &psi₂]) is closer to the reference triplet.

Further reading

By the way, if you're interested in this kind of thing, check out James Diebel's "quick reference guide". (Just kidding, it's anything but quick... it's exhaustive!). Also, Andrew J. Hanson is the biggest fan of quaternions that I've ever met and he has a book on visualizing them. I haven't read it, but if it's half as enthusiastic as his lectures then it's probably an insightful read.