Is there an algorithm for converting quaternion rotations to Euler angle rotations?

Question

Is there an existing algorithm for converting a quaternion representation of a rotation to an Euler angle representation? The rotation order for the Euler representation is known and can be any of the six permutations (i.e. xyz, xzy, yxz, yzx, zxy, zyx). I've seen algorithms for a fixed rotation order (usually the NASA heading, bank, roll convention) but not for arbitrary rotation order.

Furthermore, because there are multiple Euler angle representations of a single orientation, this result is going to be ambiguous. This is acceptable (because the orientation is still valid, it just may not be the one the user is expecting to see), however it would be even better if there was an algorithm which took rotation limits (i.e. the number of degrees of freedom and the limits on each degree of freedom) into account and yielded the 'most sensible' Euler representation given those constraints.

I have a feeling this problem (or something similar) may exist in the IK or rigid body dynamics domains.

---

Just to clarify - I know how to convert from a quaternion to the so-called 'Tait-Bryan' representation - what I was calling the 'NASA' convention. This is a rotation order (assuming the convention that the 'Z' axis is up) of zxy. I need an algorithm for all rotation orders.

Possibly the solution, then, is to take the zxy order conversion and derive from it five other conversions for the other rotation orders. I guess I was hoping there was a more 'overarching' solution. In any case, I am surprised that I haven't been able to find existing solutions out there.

In addition, and this perhaps should be a separate question altogether, any conversion (assuming a known rotation order, of course) is going to select one Euler representation, but there are in fact many. For example, given a rotation order of yxz, the two representations (0,0,180) and (180,180,0) are equivalent (and would yield the same quaternion). Is there a way to constrain the solution using limits on the degrees of freedom? Like you do in IK and rigid body dynamics? i.e. in the example above if there were only one degree of freedom about the Z axis then the second representation can be disregarded.

---

I have tracked down one paper which could be an algorithm in this pdf but I must confess I find the logic and math a little hard to follow. Surely there are other solutions out there? Is arbitrary rotation order really so rare? Surely every major 3D package that allows skeletal animation together with quaternion interpolation (i.e. Maya, Max, Blender, etc) must have solved exactly this problem?

Answer 1

This looks like a classic case of old technology being overlooked - I managed to dig out a copy of Graphics Gems IV from the garage and it looks like Ken Shoemake has not only an algorithm for converting from Euler angles of arbitrary rotation order, but also answers most of my other questions on the subject. Hooray for books. If only I could vote up Mr. Shoemake's answer and reward him with reputation points.

I guess a recommendation that anybody working with Euler angles should get a copy of Graphics Gems IV from their local library and read the section starting page 222 will have to do. It has to be the clearest and most concise explanation of the problem I have read yet.

---

Here's a useful link I have found since - http://www.cgafaq.info/wiki/Euler_angles_from_matrix - This follows the same system as Shoemake; the 24 different permutations of rotation order are encoded as four separate parameters - inner axis, parity, repetition and frame - which then allows you to reduce the algorithm from 24 cases to 2. Could be a useful wiki in general - I hadn't come across it before.

To old link provided seems to be broken here is another copy of "Computing Euler angles from a rotation matrix ".