3D Computer Graphics Tutorials

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

3D Graphics

• Coordinate Systems
• Transpose Matrix
• BSP Trees
• Collision Detection

OpenGL

• OpenGL Vertex Transformations
• OpenGL Anti-aliasing Using Smooth Outlines

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

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

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.

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.

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)

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 );