G3dQuaternion.mesa
Copyright Ó 1988, 1992 by Xerox Corporation. All rights reserved.
Ken Shoemake, April 12, 1989 2:43:54 am PDT
Bloomenthal, July 14, 1992 1:48 pm PDT
Glassner, July 3, 1990 11:59:47 am PDT
Right-handed world coordinate system (longitude, latitude, altitude).
Quaternions are used for representing and animating orientations/rotations. You can view them not only as homogeneous coordinates, [x, y, z, w], but also as fancy complex numbers w+ix+jy+kz with i2=j2=k2=ijk=—1. Each non-zero quaternion corresponds to a rotation. Like homogeneous coordinates for points, all non-zero scalar multiples of a quaternion give the same rotation, while the zero quaternion does not correspond to any rotation. The product of two quaternions corresponds to the combination of their rotations; the result in both cases is order dependent. The quaternion 1 (i.e., 1+i0+j0+k0) corresponds to the null rotation, a rotation through a zero angle.
Unit quaternions—those with x2+y2+z2+w2=1—have an exceptional status among coordinate systems for rotations. Mathematically, they are unique in matching the natural structure, both metric and topological, of 3D rotations. Computationally, they are both concise and extremely efficient. Unit quaternions lie on a sphere in x-y-z-w space. The length of the arc between two of them is half the angle of rotation between their corresponding orientations; travel along the arc corresponds to performing the rotation.
For more details, refer to:
``Animating Rotation with Quaternion Curves'', SIGGRAPH '85 Proceedings, and
``Quaternion Calculus and Fast Animation,'' in SIGGRAPH '87 tutorial #10.
DIRECTORY
G3dBasic, G3dMatrix, Rope;
G3dQuaternion: CEDAR DEFINITIONS
~ BEGIN
Type Declarations
Pair:  TYPE ~ G3dBasic.Pair;
Triple:  TYPE ~ G3dBasic.Triple;
Quad:  TYPE ~ G3dBasic.Quad;
Matrix:  TYPE ~ G3dMatrix.Matrix;
Quaternion: TYPE ~ G3dBasic.Quad ¬ [x: 0.0, y: 0.0, z: 0.0, w: 1.0];
AxisAngle: TYPE ~ RECORD [unitAxis: Triple, theta: REAL];
QuaternionSequence:  TYPE ~ REF QuaternionSequenceRep;
QuaternionSequenceRep: TYPE ~ RECORD [
length:      CARDINAL ¬ 0,
element:      SEQUENCE maxLength: CARDINAL OF Quaternion
];
Common Values
origin:  Triple ~ G3dBasic.origin;
qZero: READONLY Quaternion; -- All components 0, sum identity, does not give a rotation
quW: READONLY Quaternion; -- Pure w component, product identity, gives null rotation
quX: READONLY Quaternion; -- Pure x component, gives rotation by p around x axis
quY: READONLY Quaternion; -- Pure y component, gives rotation by p around y axis
quZ: READONLY Quaternion; -- Pure z component, gives rotation by p around z axis
Conversion Procedures
FromComponents: PROC [x, y, z, w: REAL] RETURNS [qq: Quaternion];
Construct a (possibly non-unit) quaternion from real components.
FromVectorScalar: PROC [v: Triple, w: REAL ¬ 1.0] RETURNS [qq: Quaternion];
Construct a (possibly non-unit) quaternion from vector (for x, y, z) and real scalar (for w).
Note that FromVectorScalar[v] gives a different scalar component than FromVector[v].
FromVector: PROC [v: Triple] RETURNS [qq: Quaternion];
Construct a (possibly non-unit) quaternion from vector (for x, y, z). Scalar will be 0.
FromScalar: PROC [w: REAL ¬ 1.0] RETURNS [qq: Quaternion];
Construct a (possibly non-unit) quaternion from scalar (for w). Vector will be 0.
FromAxisAngle: PROC [unitAxis: Triple, theta: REAL] RETURNS [qu: Quaternion];
Construct a unit quaternion for rotation around unitAxis by theta radians.
unitAxis should be of unit length.
FromXYZAngles: PROC [forX, forY, forZ: REAL] RETURNS [qu: Quaternion];
Construct a unit quaternion for rotation (in radians) around body z then y then x axis.
FromMatrix: PROC [mat: Matrix] RETURNS [qu: Quaternion];
Construct a unit quaternion from rotation matrix. Assumes matrix is used to multiply row
vector on the right: vnew ← vold mat. Works correctly for right-handed coordinate system
and right-handed rotations. Translation and perspective components ignored.
ToMatrix: PROC [q: Quaternion, out: Matrix ¬ NIL] RETURNS [Matrix];
Construct rotation matrix from (possibly non-unit) quaternion. Assumes matrix is used to
multiply row vector on the right: vnew ← vold mat. Works correctly for right-handed
coordinate system and right-handed rotations. Use out if non-NIL.
ToAxisAngle: PROC [qu: Quaternion] RETURNS [AxisAngle];
Extract rotation axis of unit quaternion qu as a unit vector, along with rotation angle of qu
(in radians). Note that a rotation with an angle of zero will have an undefined axis. Note
also that [v,q] and [—v,—q] are the same rotation (opposite to [v,—q] and [—v,q]).
ToXYZAngles: PROC [qu: Quaternion] RETURNS [Triple];
Return the Euler angles corresponding to the unit quaternion.
Compatibility Procedures
MakeRotateQ: PROC [q: Quaternion, out: Matrix ¬ NIL] RETURNS [Matrix];
Construct rotation matrix from (possibly non-unit) quaternion. Assumes matrix is used to
multiply row vector on the right: vnew ← vold mat. Works correctly for right-handed
coordinate system and right-handed rotations. Use out if non-NIL.
MakeRotateAboutQ: PROC [q: Quaternion, base: Triple ¬ origin, out: Matrix ¬ NIL]
RETURNS [Matrix];
Construct translated rotation matrix from (possibly non-unit) quaternion and base point for
rotation. Assumes matrix is used to multiply row vector on the right: vnew ← vold mat.
Works correctly for right-handed coordinate system and right-handed rotations. Use out if
non-NIL.
Algebraic Procedures
Id: PROC RETURNS [qu: Quaternion];
Return quaternion multiplicative identity, gives null rotation.
Zero: PROC RETURNS [qq: Quaternion];
Return quaternion additive identity, does not give a rotation.
Components: PROC [q: Quaternion] RETURNS [Quad];
Return components of quaternion.
Vector: PROC [q: Quaternion] RETURNS [Triple];
Return vector part of quaternion.
Scalar: PROC [q: Quaternion] RETURNS [REAL];
Return scalar part of quaternion.
PureVector: PROC [q: Quaternion] RETURNS [qq: Quaternion];
Return quaternion with scalar component zero. Can use as cheap cleanup for Ln, since
PureVector[Ln[q]] = Ln[Unit[q]].
Norm: PROC [q: Quaternion] RETURNS [REAL];
Return norm of quaternion; that is, the sum of the squares of components.
Neg: PROC [q: Quaternion] RETURNS [qq: Quaternion];
Return negated quaternion; that is, its additive inverse.
Conjugate: PROC [q: Quaternion] RETURNS [qq: Quaternion];
Return conjugate of quaternion.
Inverse: PROC [q: Quaternion] RETURNS [qq: Quaternion];
Return inverse of quaternion; that is, its multiplicative inverse.
Unit: PROC [q: Quaternion] RETURNS [qu: Quaternion];
Return normalized quaternion; that is, make sum of squares equal 1.
Add: PROC [qL, qR: Quaternion] RETURNS [qq: Quaternion];
Return quaternion sum qL + qR.
Sub: PROC [qL, qR: Quaternion] RETURNS [qq: Quaternion];
Return quaternion difference qL - qR.
Mul: PROC [qL, qR: Quaternion] RETURNS [qq: Quaternion];
Return quaternion product qL * qR. Note: order is important!
Scale: PROC [q: Quaternion, w: REAL] RETURNS [qq: Quaternion];
Return product of quaternion q by scalar w.
Exp: PROC [q: Quaternion] RETURNS [qq: Quaternion];
Return exponentiated quaternion; that is, S qn/n!.
Ln: PROC [q: Quaternion] RETURNS [qq: Quaternion];
Return the natural logarithm of quaternion, inverse function of Exp.
Rot: PROC [qu: Quaternion, v: Triple] RETURNS [vr: Triple];
Return v rotated by unit quaternion qu. Faster for single vector than making qu into matrix.
Dot: PROC [qa, qb: Quaternion] RETURNS [REAL];
Return the 4-D dot product of quaternions qa and qb.
Curve Procedures
Several procedures are given for constructing and evaluating spherical analogs of cubic polynomial curves: Squad, Bezier, and BSpline. Evaluation is based on the spherical analog of linear interpolation, Slerp. The essential difference between Squad and Bezier is that Squad is about twice as fast, while Bezier has more direct tangent control; both interpolate their end points. The BSpline curve allows non-uniform knots, second order continuity, and variation diminution, but does not interpolate. All give local control.
Both Squad and Bezier have control points with which to set the tangents at the end points. The TangentVector procedure will estimate a suitable tangent, while SquadTanFromVector and BezierTanFromVector will construct a control point. The combined effect may be had by using SquadTanFromPoints or BezierTanFromPoints.
[Artwork node; type 'Artwork on' to command tool]
Slerp: PROC [qu0, qu1: Quaternion, t: REAL] RETURNS [qut: Quaternion];
Spherical linear interpolation of unit quaternions. Takes qu0 to qu1 as t goes from 0 to 1.
Bisect: PROC [qu0, qu1: Quaternion] RETURNS [qu: Quaternion];
Fast Slerp for t = 1/2.
Double: PROC [qu0, qu1: Quaternion] RETURNS [qu: Quaternion];
Fast Slerp for t = 2.
Squad: PROC [qu0, qu1, quq0, quq1: Quaternion, t: REAL] RETURNS [qut: Quaternion];
Spherical quadrangle curve from qu0 to qu1, for t IN [0..1], with tangents manipulated by
quadrangle points quq0 and quq1. All quaternions are assumed to be of unit norm.
Bezier: PROC [qu0, qua0, qub1, qu1: Quaternion, t: REAL] RETURNS [qut: Quaternion];
Spherical Bezier curve from qu0 to qu1, for t IN [0..1], with tangents manipulated by Bezier
points qua0 and qub1. All quaternions are assumed to be of unit norm.
BSpline: PUBLIC PROC [qu0, qu1, qu2, qu3: Quaternion, t1, t2, t3, t4, t5, t6, t: REAL]
RETURNS [qut: Quaternion];
Spherical cubic B-Spline curve for control points qu0 to qu3 and knots t1 to t6, t IN [t3..t4].
Must have t1 d t2 d t3 < t4 d t5 d t6. All quaternions are assumed to be of unit norm.
CatmullRom: PUBLIC PROC [qu0, qu1, qu2, qu3: Quaternion, t: REAL]
RETURNS [qut: Quaternion];
Spherical cubic Catmull-Rom curve for control points qu0 to qu3, for t IN [0..1].
All quaternions are assumed to be of unit norm.
TangentVector: PROC [quNm1, quN, quNp1: Quaternion] RETURNS [vt: Triple];
Given unit quaternions quNm1, quN, and quNp1—in that order—estimate the tangent at quN
for a smooth curve passing through all three.
SquadTanFromPoints: PROC [quNm1, quN, quNp1: Quaternion] RETURNS [quqN: Quaternion];
Given unit quaternions quNm1, quN, and quNp1—in that order—estimate the tangent at quN
for a smooth curve passing through all three. Compute quandrangle point quqN for Squad.
BezierTanFromPoints: PROC [quNm1, quN, quNp1: Quaternion] RETURNS [quaN: Quaternion];
Given unit quaternions quNm1, quN, and quNp1—in that order—estimate the tangent at quN
for a smooth curve passing through all three. Compute Bezier point quaN for Bezier.
SquadTanFromVector: PROC [quN, quNp1: Quaternion, vt: Triple]
RETURNS [quqN: Quaternion];
Given unit quaternions quN and quNp1—in that order—and a tangent vector vt at quN,
compute quandrangle point quqN for Squad.
BezierTanFromVector: PROC [quN: Quaternion, vt: Triple] RETURNS [quaN: Quaternion];
Given unit quaternion quN, and a tangent vector vt at quN, compute Bezier point quaN for
Bezier.
Sequence Procedures
ConformQuaternionSequence: PROC [qs: QuaternionSequence];
Make sure each quaternion in the sequence is on the same half-sphere as the preceding element. Note: a cyclic path may return to its origin with a 180-degree phase shift.
CopyQuaternionSequence: PROC [qs: QuaternionSequence]
RETURNS [new: QuaternionSequence];
Return a copy of the input sequence of Quaternions.
AddToQuaternionSequence: PROC [qs: QuaternionSequence, q: Quaternion]
RETURNS [QuaternionSequence];
Add q to the sequence.
LengthenQuaternionSequence: PROC [qs: QuaternionSequence, amount: REAL ¬ 1.3]
RETURNS [new: QuaternionSequence];
Return a copy of the input sequence whose maxLength is amount*input.maxLength.
END.