Palomino - 3D Math

©2004,2009  Jim E. Brooks   http://www.palomino3d.org



Coordinate Systems

[2004]

These are the coordinate systems a 3D vertex is transformed thru:

  1. local
  2. world
  3. eye
  4. perspective
  5. viewport
  6. normal

Transformation of a 3D vertex thru coordinate systems:

Local World Eye Perspective 2D viewport

Green indicates transformations done by the engine.
Red indicates transformations done by the gfxsys.
Local:World and World:Eye can be combined by matrix multiplication.

Local Coordinate System

3D objects have their own local coordinate system. Also known as object coordinates.

World Coordinate System

The world coordinate system contains the simulated world (the scene to be rendered). It is mapped to the eye coordinate system by the Eye Matrix.

Altitude correlates to a positive world Y coordinate. (X,Z) correlates to a 2D position ("ground coordinates") somewhere on the modeled terrain/land.

Eye Coordinate System

The eye coordinate system stays mapped to the viewport of the window system. Eye vertexs are the final result of all transformations. They are submitted the gfxsys.

(X,Y) eye coordinates correlate to (X,Y) viewport coordinates. An eye Z coordinate measures the distance from the eye/viewpoint. For an eye vertex, (X,Y) are divided by Z to project the vertex onto the viewport (window). This projection creates the illusion of perspective on a 2D computer display.

Perspective Coordinate System

Eye coordinates are transformed by the gfxsys into perspective coordinates. The view frustum (which exists in eye space) is mapped to perspective coordinates.

Viewport Coordinate System

This is the 2D window on the computer's window system.

Normal Coordinate System

Every normal vector calculated from a cross product exists in its own coordinate system. Its origin (0,0,0) is mapped to a local vertex of the polygon on which it is perpendicular to. Normals depend on the object's transformation in local space. For example, if the vertexs of an aileron are rotated in local space, all normals on the aileron must be rotated likewise (or recalculated)


Normal Vectors, Cross Products, Dot Products

[2004]

The result of the cross product of two vectors extending from a shared vertex on a planar polygon is a normal vector. CrossProduct() uses the first vertex argument as the origin of the normal vector. The resulting vertex on the normal vector is stored in a distinct NormalVertex type as it exists in its own coordinate system.

/*****************************************************************************
 * Calculate a cross product of two vectors which yields a normal vector
 * that is perpendicular to the plane containing the two source vectors.
 * Note: The cross product won't be unit length.
 * c = a x b
 *****************************************************************************/
INLINE NormalVertex
CrossProduct( const Vector3& v1, // origin of normal vector
              const Vector3& v2,
              const Vector3& v3 )
{
    fp a, b, c;
    fp d, e, f;

    a = v2.x - v1.x;
    b = v2.y - v1.y;
    c = v2.z - v1.z;

    d = v3.x - v1.x;
    e = v3.y - v1.y;
    f = v3.z - v1.z;

    return NormalVertex( b*f - c*e,
                         c*d - a*f,
                         a*e - b*d );
}

A dot product is calculated from two vectors extending from a shared vertex. The result is a single value (scalar). If the angle between the two vectors is between 0' and 90', then the dot product will be a positive value. Normal vector, cross products, and dot products are used for culling polygons which aren't facing the viewpoint.


Matrix

[2004,2007/04]

A compact 4x3 matrix is used:

{ Xx, Xy, Xz,    // X axis
  Yx, Yy, Yz,    // Y axis
  Zx, Zy, Zz,    // Z axis
  Ox, Oy, Oz };  // origin

The 9 axis coefficients and the origin are used for matrix rotation and translation.

OpenGL is based on a 4x4 matrix. OpenGL has a 4th column for homogeneous coordinates. Homogenous coordinates applies to projection and scaling. The engine only rotates and translates non-homogeneous coordinates, and never exchanges matrixs with OpenGL, thus allowing a minimized 4x3 matrix to be used.

A vertex is rotated by:
(one coordinate system is rotated relative to another)

x' = x*Xx + y*Xy + z*Xz
y' = x*Yx + y*Yy + z*Yz
z' = x*Zx + y*Zy + z*Zz

A vertex is translated by:
(one coordinate system is translated relative to another)

x' = x + Ox
y' = y + Oy
z' = z + Oz

Eye Matrix

The eye matrix maps the world coordinate system to the eye coordinate system. A peculiarity of the eye matrix is that its offsets (Ox,Oy,Oz) are all negative.

Object Matrix

The Object class has a transform hierarchy which transform vertexs from local space to eye space.

Transpose Matrix

A matrix maps one coordinate system to another. The mapping is directed. The mapping can be reversed by transposing a matrix. This is done by turning each row into a column. Note: a transpose matrix and an inverse matrix are different mathematical concepts.

 [ Xx Xy Xz ]     [ Xx Yx Zx ]
 [ Yx Yy Yz ]     [ Xy Yy Zy ]
 [ Zx Zy Zz ]     [ Xz Yz Zz ]

An example of using a transpose matrix is the animation of tracer bullets in a first-person view. The eye matrix maps world-to-eye coordinates. The tracer bullets are modeled starting from a local coordinate system. What's needed is a local matrix that maps local-to-world coordinates and it must be aligned with the eye matrix. The transpose of the eye matrix is that local matrix. Although the transposed eye matrix maps eye-to-world coordinates, it can work because the result of the transformation is in world coordinates (on the output side), and by substituting local coordinates instead of eye coordinates on the input side. A copy of the eye matrix used as the local matrix wouldn't work because the two transformations from local-to-world and world-to-eye would nonsensically pass thru the eye matrix (which is meant for the latter transformation only).


Matrix Rotation

[2004,2007/04]

Two different descriptions about rotating a 3D matrix around its axises:
Matrix Rotation [1990]
Matrix Rotation [2004]

Matrix Rotation [2004]

[Updated 2007/04. This code evolved into the Matrix class.]

The following notes were written in 2004 as a rewrite of notes from 1990. It distinguishes the two ways to rotate a matrix. Rotation around a fixed coordinate system is for rotating a first-person view (Eye). Rotation around a local coordinate system is for rotating dynamic objects. Both are implemented [2007] as Matrix::RotateFixed() and Matrix::RotateLocal().

This matrix rotation formula is actually rotation around a fixed coordinate system (this fact wasn't originally documented). For example, in the formula for rotation around the X axis...

X Pitch
-------

c = cos(radian)
s = sin(radian)

m[Yx] = m[Yx]*c - m[Zx]*s  // Y = Ycos - Zsin
m[Yy] = m[Yy]*c - m[Zy]*s
m[Yz] = m[Yz]*c - m[Zz]*s

m[Zx] = m[Yx]*s + m[Zx]*c  // Z = Ysin + Zcos
m[Zy] = m[Yy]*s + m[Zy]*c
m[Zz] = m[Yx]*s + m[Zz]*c

...notice that the X coordinate doesn't change (X is 1:1). Thus the rotation is around a fixed X axis. The formulas are correct for rotating the viewpoint (first-person perspective) or in other words the eye coordinate system.

But to rotate an object relative to its own local coordinate system, additional math must be done. Recall that a local coordinate system is mapped to the eye coordinate system. After random rotations around all 3 axises of the local coordinate system, eventually, the X coordinate, for instance, should be transformed to a different value.

These are the steps to rotate a coordinate system relative to itself (local rotation):

  1. Let m be the matrix that defines a local coordinate system.
  2. Load identity into temporary matrix r.
  3. Rotate matrix r around one of its axises using the formula for rotation around a fixed axis.
  4. Transform matrix r thru matrix m. Ie, transform r thru m as if r were the rotated coordiates (1.0, 1.0, 1.0).
  5. m = r

The trick is transforming the result of the rotation of a fixed coordinate system into the local coordinate system.

/*****************************************************************************
 * Rotate a matrix around a fixed axis.
 * This function is suited to rotating the viewpoint/eye.
 * The word "fixed" should be clear by looking at the math.
 * Eg, the value of the X coord won't be changed by a rotation around the X axis.
 *****************************************************************************/
void
Matrix::RotateFixed( uint axis, Radian rad )
{
    FPM s, c; SinCos( rad, s, c );
    Matrix n = *this;  // dest = src
    switch ( axis )
    {
        // X : Pitch
        case AXIS_X:
        n[Yx] = m[Yx]*c - m[Zx]*s;      // Y = Ycos - Zsin
        n[Yy] = m[Yy]*c - m[Zy]*s;
        n[Yz] = m[Yz]*c - m[Zz]*s;

        n[Zx] = m[Yx]*s + m[Zx]*c;      // Z = Ysin + Zcos
        n[Zy] = m[Yy]*s + m[Zy]*c;
        n[Zz] = m[Yz]*s + m[Zz]*c;
        break;

        // Y : Yaw
        case AXIS_Y:
        n[Xx] = m[Xx]*c - m[Zx]*s;      // X = Xcos - Zsin
        n[Xy] = m[Xy]*c - m[Zy]*s;
        n[Xz] = m[Xz]*c - m[Zz]*s;

        n[Zx] = m[Xx]*s + m[Zx]*c;      // Z = Xsin + Zcos
        n[Zy] = m[Xy]*s + m[Zy]*c;
        n[Zz] = m[Xz]*s + m[Zz]*c;
        break;

        // Z : Roll
        case AXIS_Z:
        n[Xx] = m[Xx]*c - m[Yx]*s;      // X = Xcos - Ysin
        n[Xy] = m[Xy]*c - m[Yy]*s;
        n[Xz] = m[Xz]*c - m[Yz]*s;

        n[Yx] = m[Xx]*s + m[Yx]*c;      // Y = Xsin + Ycos
        n[Yy] = m[Xy]*s + m[Yy]*c;
        n[Yz] = m[Xz]*s + m[Yz]*c;
        break;

        default: ASSERT(0); return;
    }

    *this = n;  // dest = src
}

/*****************************************************************************
 * Rotate matrix around local axis.
 * Rotate a local coordinate system around its own axis.
 * This function is suited to rotating an independent object.
 * The rotation is relative to local coodinate system (not the fixed/eye system).
 * The trick is to load an identity-mapped matrix and rotate it, then transform
 * it thru the given matrix (which defines the local coordinate system)
 * as though it was the coords (1.0, 1.0, 1.0).  These coords of course define
 * the X,Y,Z axises.  The transformation is effectively a local rotation.
 *****************************************************************************/
void
Matrix::RotateLocal( uint axis, Radian rad )
{
    // Identity (1:1) matrix r.
    Matrix r;

    // Rotate matrix r.
    r.RotateFixed( axis, rad );

    // Transform r thru m.
    // Ie, thru matrix m, pass r as if it were the rotated coords (1.0, 1.0, 1.0).
    Matrix t;
    t[Xx] = r.RotateTranslateX( m[Xx], m[Xy], m[Xz] );
    t[Xy] = r.RotateTranslateY( m[Xx], m[Xy], m[Xz] );
    t[Xz] = r.RotateTranslateZ( m[Xx], m[Xy], m[Xz] );

    t[Yx] = r.RotateTranslateX( m[Yx], m[Yy], m[Yz] );
    t[Yy] = r.RotateTranslateY( m[Yx], m[Yy], m[Yz] );
    t[Yz] = r.RotateTranslateZ( m[Yx], m[Yy], m[Yz] );

    t[Zx] = r.RotateTranslateX( m[Zx], m[Zy], m[Zz] );
    t[Zy] = r.RotateTranslateY( m[Zx], m[Zy], m[Zz] );
    t[Zz] = r.RotateTranslateZ( m[Zx], m[Zy], m[Zz] );

    // m = r excluding origin elements.
    m[Xx] = t[Xx];
    m[Xy] = t[Xy];
    m[Xz] = t[Xz];

    m[Yx] = t[Yx];
    m[Yy] = t[Yy];
    m[Yz] = t[Yz];

    m[Zx] = t[Zx];
    m[Zy] = t[Zy];
    m[Zz] = t[Zz];
}


Last modified: Sat Nov 7 14:44:41 CST 2009