coordinate systems

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

  1. local
  2. world
  3. eye
  4. perspective
  5. view-port
  6. normal

Transformation of a 3D vertex thru coordinate systems:

local --> world --> eye --> perspective --> 2D view-port

Green indicates transformations done by engine.
Red indicates transformations done by gfx-sys.
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

World coordinate system contains simulated world (scene to be rendered). It is mapped to eye coordinate system by eye matrix.

eye coordinate system

Eye coordinate system stays mapped to view-port of window system. Eye vertexs are final result of all transformations, which are submitted to gfx-sys.

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

perspective coordinate system

Eye coordinates are transformed by underlying graphics system into perspective coordinates. View frustrum (which exists in eye space) is mapped to perspective coordinates.

view-port coordinate system

This is 2D window on 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 vertexs on a polygon on which it is normal/perpendicular to.


transpose matrix

A matrix maps one coordinate system to another. Mapping is directed. Mapping can be reversed by transposing a matrix. This is done by turning each row into a column. Note: transpose matrix and 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 animated firing guns in a 1st-person view. Eye matrix maps world-to-eye coordinates. Tracer rounds from gun 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 eye matrix. Transpose of eye matrix can be used as local matrix. Although transposed eye matrix apparently maps eye-to-world coordinates, it will work as result of transformation is in world coordinates (on output side). Local coordinates are substituted for eye coordinates on input side. A copy of eye matrix used as local matrix would not work because two transformations from local-to-world and world-to-eye would nonsensically pass thru eye matrix (which is meant for latter transformation only).


BSP trees

"BSP" usually refers to an AA-BSP tree.

overview

Two kinds of BSP trees are axis-aligned and polygon-aligned (AA-BSP and PA-BSP). A BSP node has two child nodes metaphorically named left and right.

axis-aligned BSP trees

Axis-aligned is much simpler and faster to construct than polygon-aligned. Axis-aligned is useful for containing 3D objects in rectangular volumes. Objects can be coarsely (imprecisely) sorted in back-to-front order by traversing an axis-aligned using distance between a partition vs. view-point as criteria for branching left or right. Granularity of sorting is rectangular volume of a BSP node. A BSP node may contain multiple Objects, but sorting (by BSP traversal) goes no further (this is why sorting isn't precise). Bypassing finely sorting Objects of a BSP node is possible if none of Objects are translucent. Rendering opaque objects out-of-order relies on hardware Z buffer. Note that purpose of sorting is to properly alpha-blend translucent Objects.

polygon-aligned BSP trees

Polygon-aligned BSP trees are well-suited for precise collision-detection of objects having irregular shapes. Though they have disadvantages such as being complex and slow to construct. Polygons intersecting a plane must be split into two polygons.

traversal path of BSP varies according to view-point

Key to understanding a BSP tree is that traversal path varies according to a branch condition and a stop condition. Unlike a regular binary tree, these conditions are variable. For example, when adding Objects, branch condition is whether an Object can fit inside a partition. When culling/sorting, branch condition is determined by distance and orientation of a partition relative to view-point

culling and sorting objects by traversing

Culling and sorting objects are done simultaneously by traversing a BSP tree. Traversing is sorting. Reaching a stop condition that evaluates true is culling.

A BSP node and its descendants outside view frustum are culled since they won't be visible. This culling method is efficient, since a whole subtree of invisible objects are eliminated in one step.

To properly render translucent polygons, furthest-to-nearest order is necessary. During traversal, if two partitions are visible, partition that is furthest from view-point is selected. A partition's distance and whether inside frustrum are sub-conditions of branch condition. Target of traversal path is to reach smallest and most distant partition.

Branch condition determines which ways to branch:

    If left is farther than right from view-point:
        If left is facing, branch.
        If right is facing, branch.
    If right is farther than left from view-point:
        If right is facing, branch.
        If left is facing, branch.

Stop condition determines when to stop recursing:
if partition is not facing or partition is outside view frustrum.

Ignoring view frustrum for a moment, possibly all partitions or none will be visible. For example, if view-point is at corner of a partition and facing outwards, then none are visible. If view-point is rotated 180 deg, then all become visible.

adding objects to a BSP Tree

Adding objects to a AA-BSP is similar to octrees. Tree is recursed until a node (corresponding to an octant) is found that object doesn't fit or maximum depth is reached, then object is attached to its parent node.

objects which intersect a BSP Plane

There are several cases where an Object can intersect a BSP plane. One case is a Dyna that moves between any two partitions. Worst case is a very large Object that, besides intersecting one or more planes, overlays partitions in multiple BSP trees.

A way to solve intersection is to let multiple BSP nodes reference same Object in case Object occupies at least one partition that wasn't culled, but keep a flag (or frame number) to remember that Object was drawn in a frame in case one or more of its partitions are visible (to avoid redraw).

collision-detection using a polygon-aligned BSP tree

Testing if a 3D vertex is inside a PA-BSP is done by traversing. If vertex is inside, then vertex will be behind every polygon encountered during traversal. Eventually, traversal will stop at a leaf node, which means a collision was detected.


minimum distance between point and line segment

AB is line SEGMENT.
C is point to measure its distance from AB.

Shortest line from a point to a line is an orthogonal line. Orthogonal line intersects at a tangent. If orthogonal line were rotated in either direction, it would move off other line and would have to be increased to remain in intersection, thus it is has minimum distance.

A-------------B
       |
       |
       C

According to linear algebra, dot product can be used to compute a projection of vector onto another vector. In this case, projection of C onto AB.

        AC . AB
t = --------------
    ||AB|| * ||AB||


    DotProduct( AC, AB )
t = --------------------
    DistanceSquared( B )  = DotProduct( AB, AB )

t is a scalar that can be used to compute point of intersection I:

I = A + t * (B - A)

computer implementation:

Goal is find minimum distance on a point on LINE SEGMENT. If intersection is outside LINE SEGMENT, then instead, compute distances between CA and CB and return minimum.

This C++ code is meant for testing/demonstration. It is implemented as a class/object as a lot of results are computed which are stored in data members (too complex for a function's return value).

C++ code implementation:

(written by Jim Brooks)

////////////////////////////////////////////////////////////////////////////////
///
class DistancePointLineSegment
{
public:
    /*****************************************************************************
     * This constructor is minimum distance function.
     *****************************************************************************/
    DistancePointLineSegment( const Vector2& a,
                              const Vector2& b,
                              const Vector2& c )
    {
        // AC and AB are vectors with A as origin.
        // Compute orthogonal projection of C onto AB as scalar t.
        const Vector2 ac( c - a );
        const Vector2 ab( b - a );
        mT = DotProduct( ac, ab )
           / DotProduct( ab, ab );

        // If intersection is on line SEGMENT (within A..B),
        // then t = {0,..,1}.
        if ( (mT >= 0.0f) and (mT <= 1.0f) )
        {
            mIfIntersectsLineSegment = true;
            mIntersection.x          = a.x + mT * (b.x - a.x);
            mIntersection.y          = a.y + mT * (b.y - a.y);
            mDistance                = Distance( mIntersection - c );
        }
        else
        {
            // Intersection is outside line SEGMENT.
            // Instead, compute distances between CA and CB
            // and return minimum.
            mIfIntersectsLineSegment = false;
          //mIntersection.x          = N/A
          //mIntersection.y          = N/A
            mDistance                = std::min( Distance( c-a ), Distance( c-b ) );
        }
    }

public:
    bool        mIfIntersectsLineSegment;   ///< true if intersection on LINE SEGMENT (false if outside segment)
    fp          mT;                         ///< always valid
    Vector2     mIntersection;              ///< N/A if not mIfIntersectsLineSegment
    fp          mDistance;                  ///< minimum distance between point C and line segment AB
};

Test results:
"intersection = " means intersection within line segment (not infinite line)

----------------------------------------
Diagonal line from +Y to -X.  Midpoint/intersection is obvious.
line     = Vector2:(0,500) Vector2:(-500,0) 
point    = Vector2:(0,0) 
t        = 0.5
distance = 353.553
intersection = Vector2:(-250,250)
----------------------------------------
Horizontal line that spans -X..+X.  Intersection is obvious.
line     = Vector2:(-50,50) Vector2:(50,50) 
point    = Vector2:(0,0) 
t        = 0.5
distance = 50
intersection = Vector2:(0,50)
----------------------------------------
Diagonal thru origin.
line     = Vector2:(-50,50) Vector2:(100,-100) 
point    = Vector2:(0,0) 
t        = 0.333333
distance = 0
intersection = Vector2:(0,0)
----------------------------------------
Diagonal aiming at origin but halfway there.
line     = Vector2:(-50,50) Vector2:(-25,25) 
point    = Vector2:(0,0) 
t        = 2
distance = 35.3553
intersection = none
----------------------------------------
Diagonal aiming at origin but halfway there (swap a,b).
line     = Vector2:(-25,25) Vector2:(-50,50) 
point    = Vector2:(0,0) 
t        = -1
distance = 35.3553
intersection = none
----------------------------------------
Directly aims at origin but does not quite reach.
line     = Vector2:(-50,-50) Vector2:(-0.1,-0.1) 
point    = Vector2:(0,0) 
t        = 1.002
distance = 0.141421
intersection = none
----------------------------------------
Directly aims at origin but does not reach (swap a,b).
line     = Vector2:(-0.1,-0.1) Vector2:(-50,-50) 
point    = Vector2:(0,0) 
t        = -0.00200401
distance = 0.141421
intersection = none
----------------------------------------
Skewed above origin towards NE.
line     = Vector2:(-100,10) Vector2:(100,500) 
point    = Vector2:(0,0) 
t        = 0.0539093
distance = 96.3637
intersection = Vector2:(-89.2181,36.4156)

References:
- "Linear Algebra", Tom Apostol
- comp.graphics.algorithms FAQ


line-plane intersection

This requires thinking in terms of algebra and finding value of a variable. Known is a plane defined by its position and its normal vector. And known is a line segment defined by two vectors for its end points.

Thinking logically, there is a point on line that has to intersect plane (ignore other cases for now). Idea is that there is a distance from line's beginning to its end. If a line's normalized direction is multiplied by this distance, that produces line's end-point. Likewise, a line's normalized direction can be multiplied an unknown variable d which can produce line's point of intersection with plane.

line plane intersection pix

C++ code implementation:

(written by Jim Brooks)

/*******************************************************************************
 * 
 *******************************************************************************/
bool IntersectionPlaneLine(       Vector3& intersection, // OUT
                            const Vector3& planePos,
                            const Vector3& planeNormalVector,
                            const Vector3& lineBegin,
                            const Vector3& lineEnd )
{
    // Based on:
    // Algrebraic form
    // http://en.wikipedia.org/wiki/Line-plane_intersection
    // doc/html/math/linePlaneIntersection.html
    //
    // Idea is to find value of factor d
    // which can be used to multiplied line direction (distance from line)
    // to a point on line that intersects plane.
    //
    // Express plane as equation:
    // (p - p0) . n = 0
    // n is plane's normal vector
    // p0 is a given point on plane
    // p is a variable to be solved, in this case, point of intersection
    // 
    // p = d*l + l0
    // l is a direction vector of line
    // l0 is a point on line
    // In this C++ function
    // ld = Normalize( lineEnd - lineBegin )
    // l0 = lineBegin
    //
    // Substitute line into plane equation:
    // ((d*l + l0) - p0) . n = 0
    //
    // Distribute n:
    // d*l . n + (l0 - p0) . n = 0
    //
    // Solve for d (line factor):
    //     (p0 - l0) . n
    // d = -------------
    //         l . n
    //
    // If line is parallel and outside plane: 0 / non-zero
    // If line is parallel and on plane     : 0 / 0
    // Else intersection and d represents distance along line from l0

    const Vector3& p0 = planePos;               // alias for math
    const Vector3& l0 = lineBegin;              // alias for math
    const Vector3& n  = planeNormalVector;      // alias for math
    const Vector3  l  = Normalize( lineEnd - lineBegin );  // line direction, unit

    const fpx numerator   = DotProduct3( p0 - l0, n );
    const fpx denominator = DotProduct3( l, n );

    if ( ABS(denominator) < 0.0001 )
    {
        return false;
    }
    else
    {
        const fpx d = numerator / denominator;
        intersection = lineBegin + (l * d);
        return true;
    }
}

References:
http://en.wikipedia.org/wiki/Line-plane_intersection
http://paulbourke.net/geometry/planeline/


collision detection

For small objects, simple calculations based on bounding box or spheres should suffice.

For objects that are large and have irregular shapes, polygon-aligned BSP trees are necessary to accurately detect collisions. If collider is a small object and its rate of translation is fine enough, a simple point intersection test of collidable's BSP tree should suffice.