From: Boris Zbarsky <bzbarsky@MIT.EDU>

Date: Wed, 20 Oct 2010 14:19:02 -0400

Message-ID: <4CBF3296.5030805@mit.edu>

To: www-style list <www-style@w3.org>

Date: Wed, 20 Oct 2010 14:19:02 -0400

Message-ID: <4CBF3296.5030805@mit.edu>

To: www-style list <www-style@w3.org>

This is a message that was sent to me with the intent of it being forwarded on to this list. It describes some problems with the existing setup for interpolating transforms and suggests alternatives. -------- Original Message -------- http://dev.w3.org/csswg/css3-2d-transforms/#animation describes the current method. As I see it, there are two main problems with the current approach: the interpolation of rotations and the handling of matrices with negative determinant. Rotations are currently decomposed into a series of Euler angles, and the angle values interpolated directly. Such a situation is notoriously susceptible to Gimbal lock: http://en.wikipedia.org/wiki/Gimbal_lock This results in numeric instability near the poles: the value of one of the angles derived from a rotation matrix becomes almost arbitrary, depending on numerical rounding error, which can result in macroscopic deviations in the animation. A much better approach is to use quaternions: http://en.wikipedia.org/wiki/Quaternions_and_spatial_rotation Simple ways to interpolate rotations with quaternions have long been known: http://portal.acm.org/citation.cfm?doid=325334.325242 They completely avoid Gimbal lock, and provide a number of other benefits, like "binvariance": given three rotations Q, R, and S, and a path between Q and R, denoted P(t), then the path between S.Q and S.R is given by S.P(t) (left invariance), and the path between R.S and Q.S is given by P(t).S (right invariance). Direct interpolation via Euler angles does not have this property. The best approach I've found for converting a 3x3 rotation matrix into a quaternion is: #define MAX(a,b) ((a)>(b)?(a):(b)) w=0.5*sqrt(MAX(1+row[0][0]+row[1][1]+row[2][2],0)); x=0.5*sqrt(MAX(1+row[0][0]-row[1][1]-row[2][2],0)); y=0.5*sqrt(MAX(1-row[0][0]+row[1][1]-row[2][2],0)); z=0.5*sqrt(MAX(1-row[0][0]-row[1][1]+row[2][2],0)); if(row[2][1]<row[1][2])x=-x; if(row[0][2]<row[2][0])y=-y; if(row[1][0]<row[0][1])z=-z; The result, {w,x,y,z}, is a unit quaternion. You may need to flip the direction of the comparisons in the last three rows if you're applying your rotation matrices from the right instead of the left. This is the only approach I've seen that requires no divisions at all. It also requires no epsilons or other fudge factors that would complicate the definition of a standard. It is numerically stable for rotations near 0, 90, and 180 degrees around any axis, unlike many other approaches. The definition of the macro MAX here is very specific. The second argument must be the default when the two compare equal. Otherwise the arithmetic in the first argument can produce -0 as a result, causing sqrt to return NaN even with the check in place. This entire discussion only applies to 3D rotations: for 2D rotations quaternions are equivalent to Euler angles, because all rotations can be represented by a single angle describing the rotation around the Z axis. However, it becomes relevant when coupled with the next issue. David Baron outlined some of the problems with matrices with a negative determinant in http://lists.w3.org/Archives/Public/www-style/2010Jun/0602.html He comes up with two possibilities for decomposing them into a series of 2D transforms: a) Invert scaleY and XYshear (i.e., multiply by {{1,0,0},{0,-1,0},{0,0,1}} on the right). b) Invert scaleX, XYshear (i.e., multiply by {{-1,0},{0,1}} on the left), and A, B, C, and D (so that the rotation computed from A and B ends up in the opposite quadrant). There is yet a third option that I will argue makes much more intuitive sense, which is this: when converting from a 2D matrix to a 3D matrix, set matrix[2][2]=sign(det(matrix2d)), i.e., force the determinant of the 3D matrix to be positive. The reasoning behind this is as follows. The space of invertible matrices forms a mathematical structure known as the "General Linear Group", which is differentiable (a Lie group) and has smooth manifold structure. As a smooth manifold, it has two, disjoint pieces: those with positive determinant, and those with negative determinant. Thus there can be _no_ smooth path that moves from a matrix with a positive determinant to one with a negative determinant. Any path between those two matrices must pass through a singular matrix at some point. There are many possible paths, but one that has some intuitive conceptual meaning is to view a 2D matrix as a projection of a 3D matrix. This is how the current interpolation scheme is defined. As stated above, any invertible 2D matrix can be extended to a 3D matrix with positive determinant. Then, there is a smooth path between such matrices, and its projection back down to 2D gives the "natural" appearance of a flat object being flipped over. Compare to the current behavior of http://dbaron.org/css/test/2010/transition-negative-determinant When combined with the quaternion approach for interpolating rotations, the result is very intuitive: the first example in the "no skew, negative determinant line" simply flips the rectangle around the X axis (compared to the current behavior of some kind of combined rotation and flip). The behavior of the second example remains the same: a simple flip around the Y axis. The next two examples are simple flips across the two 45-degree diagonals, instead of more combined rotation-flips. There has been some complaint that all of the 3D math is over-complicated for 2D transforms, and there is a proposal to simplify it: http://lists.w3.org/Archives/Public/www-style/2010Sep/0697.html I believe this approach of a guaranteeing a positive determinant of the 3D transformation and interpolating rotations with quaternions has a similar, simple 2D form. One finds that the projection of just the rotation component from 3D to 2D during the animation always has det(rot(t))=cos(t*pi) (or cos((1-t)*pi) if going from negative to positive determinant), and that the scaling is along a single axis. I haven't worked through the details of the algebra to derive an expression for the axis for the case of more general rotations. Such a simplification for 2D could probably produce a generalization for 3D as well. This would avoid the need to go to 4D rotations in order to handle 3D matrices with a negative determinant, which is a much harder thing to argue for. Unlike 2D, there's no obvious intuitive advantage of the result that would justify the complexity, and a solution described analogous generality to the one presented here becomes much more complex for 4D than it is for 3D.Received on Wednesday, 20 October 2010 18:19:41 GMT

*
This archive was generated by hypermail 2.3.1
: Tuesday, 26 March 2013 17:20:33 GMT
*