Essential Math WeblogThoughts on math for games

3/25/2005

Angular Dynamics: Matrices or Quaternions?

Filed under: Mathematical,Tutorial — Jim @ 9:00 pm

One of the questions asked during the tutorial was whether matrices or quaternions were more efficient for angular rigid body dynamics. My response was that a matrix would be more efficient, because a quaternion requires a conversion to a matrix to compute the transformed inertial tensor matrix. If we analyze the operation count, this certainly appears to be true:

Matrix:
Integration: 21 multiplies, 18 adds
Total: 21 multiplies, 18 adds

Quaternion:
Integration: 16 multiplies, 12 adds
Convert to matrix: 12 multiplies, 12 adds
Total: 28 multiplies, 24 adds

The matrix conversion operation count assumes that the quaternion is pre-normalized. So it’s close, but the matrix is still cheaper.

However, as Erin Catto (again) pointed out to me afterwards, this doesn’t take orthonormalization of the matrix into account. One thing I forgot is that because of floating point error, the rotation matrix can drift away from being orthogonal, i.e. the basis vectors can become non-normalized and no longer perpendicular.

To correct this, Gram-Schmidt orthonormalization needs to be performed after integrating. This consists of normalizing the first basis vector, and then subtracting out the non-perpendicular components of the other two (relative to the other vectors) and normalizing them as well (I’m paraphrasing greatly here — see the book or this reference for more information). Each normalization takes 6 multiplies, 2 adds and a reciprocal square root (approximation or no, you still need to compute something). Orthogonalizing the three vectors takes 18 multiplies and 15 adds. The total is 36 multiplies, 21 adds, and three reciprocal square roots.

The equivalent operation for a quaternion is a simple normalization. This takes 8 multiplies, 3 adds and a reciprocal square root. Technically we can still rotate vectors with an unnormalized quaternion, but keeping the values of the quaternion close to 0 maintains a higher level of precision.

Now if we compare the operation counts, we get:

Matrix:
Integration: 21 multiplies, 18 adds
Orthonormalization: 36 multiplies, 21 adds, 3 reciprocal square roots
Total:57 multiplies, 39 adds, 3 reciprocal square roots

Quaternion:
Integration: 16 multiplies, 12 adds
Normalization: 8 multiplies, 3 adds, 1 reciprocal square root
Convert to matrix: 12 multiplies, 12 adds
Total: 36 multiplies, 27 adds, 1 reciprocal square root

Taking this into account — and even assuming we have a fast method for computing the reciprocal square root — the quaternion clearly wins on speed. It also takes less space. So unless someone else has another correction for me, I’m not sure why you’d ever use matrices as your base format for physical simulation.

1. http://www.gamedev.ru/articles/graph/20040603.zip
take code from here

Quaternions don’t have to be normalized , it just need to have stable lengtn.

to integrate quaternion we need

1. current orientation (nonunit) multiply by timestamp quaternion
2. convert ( nonunit ) to matrix with some 4 additional multiplications (compared to normalized) “to_matrix”
3. convert matrix to NONunit stable length quaternion “from_matrix” (using some 7 additions )

Comment by minorlogic — 4/28/2005 @ 8:24 am

2. Uh, and what about all the other stuff you need to transform (not just the inertia tensor)? The matrix is way cheaper computationally, and for goodness sake, you don’t have to re-orthonormalize it constantly, especially if you have a proper rotational integrator.

Comment by Franklin — 12/15/2008 @ 1:50 pm

3. In my example, we create rotation matrix on every step. So it is not the problem.

Pro:
sheap integration
automatic orthonormalization on EVERY step
Cons:
conversion to matrix and back eat some performance

Comment by minorlogic — 4/30/2009 @ 8:14 am

4. Very very nice blog!!
Hi there,I enjoy reading through your article post, I wanted to write a little comment to support you and wish you a good continuationAll the best for all your blogging efforts.
sap fica online training
sap fico online training

Comment by magnifictraining — 7/29/2016 @ 12:03 am

RSS feed for comments on this post.