h
o
m
e

 
i
n
d
e
x

 
e
m
a
i
l

3D Computer Graphics Tutorials

_
_ _ _
_

Index

Legal: These documents are copyright © 2004,2015 Jim Brooks.
Permission to copy, distribute, link, and reformat is given on condition that authorship is indicated.

3D Graphics

OpenGL

 _
_ _ _
_
_
_ _ _
_

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 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.

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 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 polygon on which it is normal/perpendicular to.

 _
_ _ _
_
_
_ _ _
_

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 animated firing guns in a 1st-person view. The eye matrix maps world-to-eye coordinates. The tracer rounds from the 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 the eye matrix. The transpose of the eye matrix can be used as the local matrix. Although the transposed eye matrix apparently maps eye-to-world coordinates, it will work as the result of the transformation is in world coordinates (on the output side). Local coordinates are substituted for eye coordinates on the input side. A copy of the eye matrix used as the local matrix would not 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).

 _
_ _ _
_
_
_ _ _
_

BSP Trees

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.

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

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 the distance between a partition vs. viewpoint as the criteria for branching left or right. The granularity of sorting is the 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 the Objects of a BSP node is possible if none of the Objects are translucent. Rendering opaque objects out-of-order relies on the hardware Z buffer. Note that the 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 Viewpoint

The key to understanding a BSP tree is that the 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, the branch condition is whether an Object can fit inside a partition. When culling/sorting, the branch condition is determined by distance and orientation of a partition relative to the viewpoint

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 the 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, the partition that is furthest from the viewpoint is selected. A partition's distance and whether inside the frustrum are sub-conditions of the branch condition. The target of the traversal path is to reach the smallest and most distant partition.

The branch condition determines which ways to branch:

  1. If left is farther than right from viewpoint:
    1. If left is facing, branch.
    2. If right is facing, branch.
  2. If right is farther than left from viewpoint:
    1. If right is facing, branch.
    2. If left is facing, branch.

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

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

Adding Objects to a BSP Tree

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

Objects that 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. The 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 the same Object in case the Object occupies at least one partition that wasn't culled, but keep a flag (or frame number) to remember that the 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 the vertex is inside, then the 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 the line SEGMENT.
C is the point to measure its distance from AB.

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

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

According to linear algebra, the dot product can be used to compute a projection of the vector onto another vector. In this case, the 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 the point of intersection I:

I = A + t * (B - A)

Computer implementation:

The goal is find the minimum distance on a point on LINE SEGMENT. If the intersection is outside the LINE SEGMENT, then instead, compute the distances between CA and CB and return the 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).

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

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

        // If intersection is on the 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
        {
            // The intersection is outside the line SEGMENT.
            // Instead, compute the distances between CA and CB
            // and return the 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)
_
_ _ _
_
_
_ _ _
_

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 the collider is a small object and its rate of translation is fine enough, a simple point intersection test of the collidable's BSP tree should suffice.

 _
_ _ _
_
_
_ _ _
_

Line-Plane Intersection

This requires thinking in terms of algebra and finding the 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 the line that has to intersect the plane (ignore other cases for now).
The idea is that there is a distance from the line's beginning to its end.
If a line's normalized direction is multiplied by this distance, that produces the line's end-point.
Likewise, a line's normalized direction can be multiplied an unknown variable d which can produce the line's point of intersection with the plane.

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

C++ code implementation (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
    //
    // The idea is to find the value of the factor d
    // which can be used to multiplied the line direction (distance from line)
    // to a point on the line that intersects the plane.
    //
    // Express the plane as the equation:
    // (p - p0) . n = 0
    // n is the plane's normal vector
    // p0 is a given point on the plane
    // p is a variable to be solved, in this case, the point of intersection
    // 
    // p = d*l + l0
    // l is a direction vector of the line
    // l0 is a point on the line
    // In this C++ function
    // ld = Normalize( lineEnd - lineBegin )
    // l0 = lineBegin
    //
    // Substitute the line into the 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 the plane: 0 / non-zero
    // If line is parallel and on the plane     : 0 / 0
    // Else intersection and d represents the distance along the 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;
    }
}
_
_ _ _
_
_
_ _ _
_

Links (3D Graphics)

  • comp.graphics.algorithms FAQ
  • Geometry Algorithms  [geomalgorithms.com, Dan Sunday]
 _
_ _ _
_
_
_ _ _
_

OpenGL Vertex Transformations

Every successive OpenGL transformation function transforms a coordinate system relative to the prior transformation. These transformation functions are:

glRotate()
glTranslate()
glVertex()

First, don't be confused by the OpenGL programming paradigm of first calling glRotate()/glTranslate() (v.v.) before calling glVertex(). Also don't be confused by the words "model" and "view" in the modelview matrix -- just think of it as a matrix that maps a logical (object) coordinate system to the eye coordinate system. Regardless of the order of calling OpenGL functions, the rendering pipeline resembles:

logical vertex --> modelview matrix --> eye coordinate system --> 2D screen

OpenGL has a notion of a pre-transformed coordinate system since the arguments passed to glVertex*() are coordinates in that system. I'm going to refer to that system as the logical coordinate system (other names such as world/virtual/object are applicable).

When you submit the vertexes of a model via glVertex*(), the model can be thought of as existing first in a logical pre-transformed coordinate system. The functions glTranslate() and glRotate() transform (map) the logical coordinate system (along with the logical vertexes you submitted) to the eye coordinate system.

To illustrate, imagine two squares of slightly different sizes are rendered with logical coordinate system identity mapped to the eye system:

 glVertex().. // large square
 glVertex().. // small square

(Remember the eye coordinate system is fixed and actually exists in physical space.) Next, the logical coordinate system is translated. Ie, the logical coordinate system is moved relative to the fixed eye coordinate system. Note that the same values are submitted to glVertex in every case -- the perceived movements/rotations are all due to glTranslate/glRotate.

 glVertex()..  // large square
 glTranslate() // move logical coordinate system relative to the eye system
 glVertex()..  // small square

glRotate() is called instead of glTranslate which results in the smaller square rotating:

 glVertex()..    // large square
 glRotate(45deg) // rotate logical coordinate system relative to the eye system
 glVertex()..    // small square

Notice how the submitted vertexes are transformed thru the current state of the modelview matrix. Also notice that by transforming the modelview matrix and then submiting the vertexes of a particular object, object animation (transformations around an object's coordinate system) can be done.

Links:
Matrix Operations (blancmange)

 _
_ _ _
_
_
_ _ _
_

OpenGL Anti-aliasing Using Smooth Outlines

A technique to anti-alias polygons is to draw smooth anti-aliased outlines over prior polygons. I learned about this from a post on Usenet by "blammo". This technique probably isn't useful on the latest video cards that can do anti-aliasing with multisampling hardware (and requires the latest OpenGL drivers).

Drawing objects twice may seem slow but the other two techniques are (can be) slower. Using GL_POLYGON_SMOOTH requires doing a complex depth-sort in software. Using the "jitter" technqiue is unacceptably slow on older video cards that lack a hardware accumulation buffer.

// Draw objects with polygon offset.
glEnable( GL_POLYGON_OFFSET_FILL );
glPolygonOffset( 1.0, 1.0 );
DrawObjects();
glDisable( GL_POLYGON_OFFSET_FILL );

// Draw smooth anti-aliased outline over polygons.
glEnable( GL_BLEND );
glEnable( GL_LINE_SMOOTH );
glBlendFunc( GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA );
glPolygonMode( GL_FRONT_AND_BACK, GL_LINE );
DrawObjects();
glPolygonMode( GL_FRONT_AND_BACK, GL_FILL );
glDisable( GL_LINE_SMOOTH );
glDisable( GL_BLEND );
_
_ _ _
_

Last modified: Sun May 25 17:08:52 EDT 2014

IGNORE THESE TWO FIELDS! They trap spam-bots!        

Comment:
Add: 88 + 67 =