# Palomino Design

©1986,2006 Jim E. Brooks http://www.palomino3d.org http://www.jimbrooks.org/sim

See also Palomino Implementation and Palomino Modules.
This document should be neither too abstract nor too detailed.
vertexs/matrixs [sic] are spelled for searchability.
gfxsys is an abbreviation for the underlying graphics system (OpenGL).
Diagrams were drawn using GNOME dia.

# Contents

- World and Quadrants
- Coordinate Systems
- Matrix
- Matrix Rotation
- Rendering and the Locus
- Objects
- Object Lists
- Visibility Testing and Level-of-detail
- Normal Vectors, Cross Products, Dot Products
- Culling
- Collision Detection
- Collision Detection at a Polygon
- Cache
- Interface between 3D Engine and Modules

## World and Quadrants

The "world" is divided into "quadrants". Each quadrant is given its own random seed and a list of 3D objects. The 3D engine renders a locus of 3x3 quadrants at a time.

The world is made (initialized) by creating a 2D square array of quadrants. Every quadrant is given a seed for randomly constructing/placing some objects (other objects may be constructed from models or given a fixed placement). Figuratively, the quadrants are a 2D array of structs:

    struct Quadrant
    {
        uint    seed;
        Object* objects;
    };
    Quadrant quadrants[QUADRANTS_SQRT][QUADRANTS_SQRT];

The purpose of quadrants is to constrain the amount of objects that the 3D engine must calculate at a viewpoint. The 3D engine renders from a locus of 9 quadrants arranged in a 3x3 square (Tic-Tac-Toe) where the viewpoint/eye is in the middle quadrant. 3x3 was chosen over a single quadrant locus because the latter has the problem of the 3/4 of the world disappearing when the viewpoint moves to a corner. The placements of objects within one quadrant should be done so that a locus of 3x3 quadrants will generate a full scene for the viewer.

Dividing the world into quadrants (as opposed to a list of every object) provides the implementation choice of demand-constructed objects. For example, the program will startup faster and use less memory by constructing only those objects in the locus. As the viewpoint is translated, the locus moves into other adjacent quadrants which demands the construction of objects residing in those quadrants. A background thread could be used to construct the quadrants adjacent to the locus in anticipation of the locus being moved.

If memory consumption needs to be reduced, objects can be freed in constructed quadrants which the locus no longer occupies (viewpoint moved away). The quadrant struct itself won't be freed to keep the seed value which must persist in order to reconstruct the quadrant using a replay of the same psuedo-random number sequence (passing the same seed value to srandom() will cause random() to produce the same sequences of numbers).

## Coordinate Systems

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:

    [ local --> ] world --> eye --> perspective --> 2D viewport

Green indicates the transformations processed by the program.
Red indicates the transformations processed by the underlying graphics system.
Not all objects have local coordinate systems.

### Local Coordinate System

Dynamic objects (such as aircraft) have their own local coordinate system of which the vertexs of a dynamic object are defined. As a dynamic object is rotated or translated, the results of local transformation are in world vertexs. That is, the world vertexs change, not the local vertexs.

### 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. The local vertexs of dynamic objects transformed into world vertexs which put dynamic objects into the world.

Altitude correlates to a positive world Y coordinate. (X,Z) correlates to a 2D position ("ground coordinates") somewhere on the modeled terrain/land. North/south/east/west aren't currently defined (regardless of a few comments in the C++ code).

### Eye Coordinate System

The eye coordinate system is always mapped to the viewport of the window system. Eye vertexs are the final result of all transformations and are submitted to the graphic driver (eg OpenGL).

(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 underlying graphics system into perspective coordinates. The view frustrum (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

A normal vector calculated by a cross product exists in its own coordinate system where its origin is one of the vertexs on a polyon on which it is normal/perpendicular to.

## Matrix

Palomino is based on a 4x3 matrix:

    { Xx, Xy, Xz,
      Yx, Yy, Yz,
      Zx, Zy, Zz,
      Ox, Oy, Oz };

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 homogenous coordinates. Homogenous coordinates applies to projection and scaling. Palomino only rotates and translates non-homogenous 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.

### Local Matrix

Dynamic Objects have their own local coordinate system and local matrix. The local matrix maps the Local Coordinate System to the World Coordinate System.

### 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 application of a transpose matrix is the animation of firing guns in a first-person view. The eye matrix maps world-to-eye coordinates. The gun tracers are modeled starting from a local coordinate system. What is 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

Two illucid descriptions about rotating a 3D matrix around its axises:
Matrix Rotation (1990).
Matrix Rotation (2004).

### Matrix Rotation (2004)

The following are notes written in 2004 about notes from 1990 (notes over notes).
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.
Palomino implements both as C++ template functions
RotateMatrixFixed() and RotateMatrixLocal() in gfx_math_matrix.hh.

My matrix rotation formula is actually rotation around a fixed coordinate system (this fact I didn't originally document). 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 (eg an enemy aircraft), 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.

From Palomino source code gfx_math_matrix.hh (Aug 2006):

    /*****************************************************************************
     * 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.
     *****************************************************************************/
    template<typename FP, typename MATRIX>
    void
    RotateMatrixFixed( uint axis, FP degree, MATRIX& m /*OUT*/ )
    {
        const FP rad = deg2rad( degree );
        const FP s = sin( rad );
        const FP c = cos( rad );
        MATRIX n;
        CopyMatrix( n, m ); // 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;
        }

        CopyMatrix( m, n ); // dest,src
    }

    /*****************************************************************************
     * 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.
     *****************************************************************************/
    template<typename FP, typename MATRIX>
    void
    RotateMatrixLocal( uint axis, FP degree, MATRIX& m /*OUT*/ )
    {
        // Identity (1:1) matrix r.
        MATRIX r;
        IdentityMatrix( r );

        // Rotate matrix r.
        RotateMatrixFixed( axis, degree, r );

        // 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] = RotTransX( m[Xx], m[Xy], m[Xz], r );
        t[Xy] = RotTransY( m[Xx], m[Xy], m[Xz], r );
        t[Xz] = RotTransZ( m[Xx], m[Xy], m[Xz], r );

        t[Yx] = RotTransX( m[Yx], m[Yy], m[Yz], r );
        t[Yy] = RotTransY( m[Yx], m[Yy], m[Yz], r );
        t[Yz] = RotTransZ( m[Yx], m[Yy], m[Yz], r );

        t[Zx] = RotTransX( m[Zx], m[Zy], m[Zz], r );
        t[Zy] = RotTransY( m[Zx], m[Zy], m[Zz], r );
        t[Zz] = RotTransZ( m[Zx], m[Zy], m[Zz], r );

        // 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];
    }

## Rendering and the Locus

The locus is the 3x3 quadrants (arranged in a tic-tac-toe pattern) where the eye resides in the middle quadrant. The locus is the set of quadrants that are visible.
See World and Quadrants.

The top-level rendering function iterates thru the 9 object lists (one list for each of the 3x3 quadrants in the Locus and invoking the overridden Object::Draw() methods.

## Objects

There are two basic classes of 3D objects: Fixed and Dyna.

### Fixed Objects

Fixed objects exist in world space and aren't animated.

### Dynamic Objects

Dynamic objects are represented by the C++ Dyna class. Dyna objects have their own local coordinate system and matrix, and are animated by Dyna::Animate().

## Object Lists

As described by World and Quadrants, every quadrant has its own list of Objects. Craft and Tracer objects are linked into lists belonging to the Game class.

## Visibility Testing and Level-of-detail

See Visible() implementation.

Most objects in a large 3D world aren't visible. Therefore, net time can be saved by conducting visibility tests on a few vertexs before a model algorithm transforms/submits all of the eye vertexs.

A set of visibility tests are executed by the virtual method Object::Visible() (which can be redefined by a derived class). The tests are conducted in order: distance, facing/Z, and 2D viewport. Each successive test is slower-but-more-accurate than the previous.

The distance test quickly deterimines which objects are too far to be visible. Even large objects, whose size would make them visible, won't be visible from long distances because of fog.

The facing/Z tests transforms only the object's position. This quick test suffices for small objects, but large objects are excluded to avoid the problem of a large object sporadically appearing and disappearing in rare cases depending the position of the eye.

To save time in the usual not-visible case, the 2D viewport test approximates the 3D object by only transforming the object's center vertex into Eye space, and adding and subtracting a radius to eye.x and eye.y to form a flat 2D rectangle in 3D eye space, then projecting only those two corner vertexs.

The result of Object::Visible() is either 0 (not-visible) or an approximate width in 2D viewport pixels. The 2D width of the object relative to the viewport gives an indication of the LOD necessary to render the object. This dynamic LOD may be overriden by the user-configurable LOD. For example, if the net LOD is low, an object's texturing or some of its polygons could be bypassed in order to render more quickly without degrading image quality.

## Normal Vectors, Cross Products, Dot Products

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 to yield a normal vector.
     * c = a x b
     *****************************************************************************/
    static inline void
    CrossProduct( NormalVertex& n, /*OUT*/
                  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;

        n.x = b*f - c*e;
        n.y = c*d - a*f;
        n.z = 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 and collision-detection.

See Culling and Collision Detection.

## Culling

Culling means to bypass rendering polygons which don't face the line-of-sight. The normal vector of every polygon is created by calculating the cross product of two vectors that originate from vertex #0 and extend to vertex #1 and vertex #2. The polygon is culled if the dot product of its normal vector and the line-of-sight vector is negative (the angle is over 90' so the polygon isn't facing the eye or v.v.).

The current implementation (Aug 2006) uses culling for Dyna objects in which the calculation of (world) normal vectors, cross products, and dot products are done in world coordinate space. Calculated world normals are discarded as they change every frame (some Objects, such as DynaMesh, keep local normals which are const).

An alternative with a speed/space trade-off is to store the normal vectors as local coordinates. The normals would never be transformed. Rather, in reverse, the eye/viewpoint would be transformed into the object's local coordinate space in which the culling calculations would be done.

## Collision Detection

Collision-detection has 3 different algorithms with increasing precision and computation expense. The first two tests are approximate. The final test is considered exact. The applicability of each test is explained later.

### Approximate Tests

The first collision-detection test is approximate and measures the distance a Dyna object is from an object and tests if the distance is less than the radius of the object.

[Side-note: An octree test could replace or follow the slice test]

The second collision-detection test is approximate and uses an algorithm that conceptually divides a 3D object into a stack of rectangular slices and constructs a rectangle to enclose each slice (slices are stacked vertically in the world Y axis). A simple comparison of 2D min/max (X,Z) pairs of the slice (correlating to the dyna's Y altitude) versus the dyna's X,Z offset indicates if a Dyna object has moved inside of any slice (which would indicate a collision). Example of how a mountain would be sliced:

The approximate tests execute quickly but may falsely detect a collision. But the error/inaccuracy only occurs in false collisions: the tests can exactly identify a non-collision condition. The false collision isn't a real problem as it will be resolved by the final more-precise test. The approximate tests save net time by more quickly identifying the non-collision common case than the precise/slower test could.

### More Precise Test

-- superceded by Collision Detection at a Polygon --

The final collision-detection test is considered more precise, and is based on facing-polygons: it determines if the origin of a Dyna object has moved inside of another object. The test uses normal vectors, cross products, dot products. This technique is similar in concept to polygon culling except that the Dyna object's origin is used instead of the eye/viewpoint. If all polygons of the other object are facing outward from the Dyna's origin, the Dyna have moved inside the other object (a collision occurred). This technique is not 100% precise as a vertex of the Dyna could be inside before the origin has moved inside. For the sake of speed, testing every Dyna vertex for being inside the other object is not done.

But accurate collision-detection using dot products must account for the complexity and concavity of an object's shape. Obviously, for a perfect cube, a collision has occurred if a every cube polygon is back-facing WRT to a Dyna object. But for complex concave shapes (such as a mountain with irregular eroded fans at its base), a Dyna object could indeed be inside the mountain even though some of the mountain's polygons are front-facing (WRT to the Dyna object). One way to test visibility in such cases is to only calculate the dot products of a few polygons that are nearest to the Dyna object. The nearest polygons are the best indicators of whether the Dyna is inside or outside a concave object. Testing only the nearest polygons should therefore exclude the polygons on the concave parts of the object.

To reduce memory consumption, the collision-detection code is designed to request normal vectors from an iterator which caches its data on a LRU basis (see Cache). Thus, when a Dyna approaches another object, the iterator will bring data into the cache and later the data can be discared after the Dyna moves away. Associated with every normal vector in the array is a reference to the vertex that serves as the origin of the normal vector.

### Applicability of the Tests

Which or both of the collision-detection tests is appropriate depends on the shape and size of the objects. Collision detection of an aircraft into a mountain uses both tests because a radius would not model a mountain's outline adequately. But collision detection between two aircraft uses only the first radius-based test. The radius used in the test of either aircraft probably may need to be magnified in case either aircraft are being translated by large strides. Because of the large strides, the second polygon-facing test could very likely fail to ever detect a collision since an aircraft's origin could move very near to another aircraft but without ever moving inside.

## Cache

"objects" here mean C++ objects, not 3D objects, unless otherwise written

To reduce memory consumption, a cache with a LRU policy is used. Lengthy C++ objects that are needed temporarily and can be recomputed are suited to being put into a cache. A cache will automatically free cached objects when they become least-recently-used.

The rationale for using a cache is shown by the problem of needing to have the normal vectors of a nearby 3D object for collision detection. A one-time calculation and storing them indefinitely incurs a memory expense, versus recalculating on-demand and discarding them every frame incurs a CPU expense. A cache offers a good compromise. Using a cache constrains recalculation to only the time when the 3D object transitions from far to near (which triggers collision detection). The cache will reclaim memory after the 3D object moves far enough away as the cached normal vectors will eventually become LRU.

A get-and-put programming paradigm is used to take and return objects from a cache. The results of a calculation can be stored in a C++ object that can be put into a cache by calling `Put()`. The cached object can be retrieved by calling Get(). Get() may return NULL in which case the needed results must be recalculated.

A cache is implemented as a list: a cached object retrieved by Get() is pulled out of the list and prepended at the head of the list. This action maintains the LRU policy by causing less-recently-used objects to migrate towards the end of the list where they will eventually be evicted out of the cache.

The cache functions as a hash during a search as the list's link structs associate a key with a pointer to a cached object. The pointers to the C++ objects associated with (that own) the cached objects are used as the keys.

The cache code is implemented as a C++ template class in gfx_cache.hh. An instantiated cache manages only one type of object. C++ objects put into a cache must be created by the C++ `new` operator because the cache code will free them using the C++ `delete` operator.

Last modified: Wed Aug 16 16:48:49 EDT 2006