Introduction
This article is my second of many articles describing the mechanics and elements of a 3D Engine. This article describes how to navigate 3D space programmatically through 4x4 matrix transforms. I discuss basic transforms, model transforms, view transformer and projection transforms. The purpose of the series is intended to consolidate a number of topics written in C# allowing nongame programmers to incorporate the power of 3D drawings into their application. While the vast majority of 3D Engines are used for game development, this type of tool is very useful for visual feedback and graphic data input. This tool began with a focus on simulation modeling but the intent is to maintain a level of performance that will allow realtime graphics.
Fortunately work has been really good; consequenty has work has pushed writing articles down the list priorities. This has took significantly longer than I had planned. I am not a computer programmer by profession and as such I would expect that ideas and algorithms expressed in this series to be rewritten and adapted to your application by “real” programmers.
Topics To Be Discussed
Basics:

Drawing:
 Drawing Points, Lines and Triangles
 Textures and Texture Coordinates
 Loading a Static Mesh Files (.obj)
 SceneGraphs

Standard 3D Objects and Containment:
 Spheres and Oriented Boxes
 Capsules and Cylinders
 Lozenges and Ellipsoids

Sorting Tree and Their Application:
 Octree Tree Sort
 BSP Tree Sort
 Object Picking and Culling

Misc:
 Lights and Special Effects
 Distance Methods
 Intersection Methods


Background
I am currently rewriting one of my company’s software models and have proposed revamping our GUI interface providing users a drawing interface. This series is a product of a rewrite of my original proof of concept application.
I am an Electrical Engineer with Lea+Elliott and as part of my responsibilies I develop and maintain our company's internal models. That being said, I am not a professional programmer so please keep this in mind as you look through my code.
Prior to Using the Code
Before you can use this code you need to download the Tao Framework to access the Tao namespaces. You also need to reference the AGE_Engine3D.dll, add the AGE_Engine3D to your project or copy the applicable .cs file and add them to your project.
The Basics
Both 3D APIs (DirectX and OpenGL) work with 4D vectors and 4x4 matrixes. I have seen different explanations but this is how I compose my matrix transforms. The basic 4x4 Matrix is a composite of a 3x3 matrixes and 3D vector.
These matrix transformations are combined to orient a model into the correct position to be displayed on screen. Unlike normal multiplication, matrix multiplication is not commutative. With matrixes, A*B does not necessary equal B*A. That being said, the order that these transforms are applied is extremely important. This is discussed more in the subsequent sections. [Note: These samples are written implementing the Tao OpenGL interface, but could very easily be modified to service DirectX or XNA interface.]
All transforms listed in this article are implemented in the AGE_Matrix44
class through static methods. The method's name is a good indication of its propose such as:
public static AGE_Matrix_44 HProjGL(float left,
float right,
float top,
float bottom,
float near,
float far)
{
...
Creates a 4 x 4 Projection Matrix
...
}
Simple Transforms
Scale Matrix (Hs)
The Scale Matrix is used to scale a model in one, two or three dimensions. It is composed of a 4x4 matrix with a 3D scaling vector on the diagonal. The scaling vector components represent a scaling in their respective dimension. It is in the form of:
It is implemented in static AGE_Matrix44
.HWorld method.
public static AGE_Matrix_44 HWorld(ref AGE_Vector3Df Location,
ref AGE_Vector3Df Scale)
{
AGE_Matrix_44 result = AGE_Matrix_44.Identity();
...
result.col[0][0] = Scale.X;
result.col[1][1] = Scale.Y;
result.col[2][2] = Scale.Z;
...
return result;
}
Rotation Matrix (Hr)
There are three rotation matrixes that can be used to rotate a model around the XAxis, YAxis, and ZAxis. There are three variations of a 4x4 matrix with various arrangements on the M matrix mentioned above. It is in the form of:
It is implemented in static AGE_Matrix44
.HRotation method.
public static AGE_Matrix_44 HRotation(float theta_X, float theta_Y, float theta_Z)
{
AGE_Matrix_44 result = AGE_Matrix_44.Identity();
if (theta_X != 0)
{
AGE_Matrix_44 H_Rot_X = AGE_Matrix_44.Identity();
H_Rot_X.col[1][1] = H_Rot_X.col[2][2] = (float)System.Math.Cos(theta_X);
H_Rot_X.col[1][2] = (float)System.Math.Sin(theta_X);
H_Rot_X.col[2][1] = H_Rot_X.col[1][2];
result = result * H_Rot_X;
}
if (theta_Y != 0)
{
AGE_Matrix_44 H_Rot_Y = AGE_Matrix_44.Identity();
H_Rot_Y.col[0][0] = H_Rot_Y.col[2][2] = (float)System.Math.Cos(theta_Y);
H_Rot_Y.col[2][0] = (float)System.Math.Sin(theta_Y);
H_Rot_Y.col[0][2] = H_Rot_Y.col[2][0];
result = result * H_Rot_Y;
}
if (theta_Z != 0)
{
AGE_Matrix_44 H_Rot_Z = AGE_Matrix_44.Identity();
H_Rot_Z.col[0][0] = H_Rot_Z.col[1][1] = (float)System.Math.Cos(theta_Z);
H_Rot_Z.col[0][1] = (float)System.Math.Sin(theta_Z);
H_Rot_Z.col[1][0] = H_Rot_Z.col[0][1];
result = result * H_Rot_Z;
}
return result;
Rotation Matrix via Quaternion (Hq)
I often use quaternion for creating my rotation matrixes. It is simple and intuitive. Creating a quaternion for rotation requires a vector identifying the axis of rotation and the angle of rotation. I believe it is commonly used in ArcBall(add hyperlink to) and other orbiting camera schemes. I will discuss it in another article but if you want to look at the code it is included.
public static AGE_Matrix_44 HRotation(ref AGE_Quaternion Rotation)
Transpose Matrix (Ht)
The Transpose Matrix is used to move a model from one position to another. It is composed of a 4x4 identity matrix with a 3D translation vector in the 4th column. The translation vector represents a change in location. It is in the form of:
It is implemented in static AGE_Matrix44
.HWorld method.
public static AGE_Matrix_44 HWorld(ref AGE_Vector3Df Location,
ref AGE_Vector3Df Scale)
{
AGE_Matrix_44 result = AGE_Matrix_44.Identity();
...
result.col[3][0] = Location.X;
result.col[3][1] = Location.Y;
result.col[3][2] = Location.Z;
return result;
}
World Space (Hw)
The World Space Transform is the first transform usually applied to a model. This transform is normally used to scale and orient the model relative to its world. The Model is defined in a model space coordinate system and needs to be translated to the world coordinate system. Let's assume you have a model of a person and it normalized such that the model dimensions are within the range [1, 1] with an origin of <0,0,0>. You could populate a world with actors referencing this single resource by applying different World Transforms. The World Transform is composed of basic transforms typical applied in this order.
The table (a.k.a. TheTable in the code below) shown in the animation above is a SpatialBaseContainer object. The follow code shows its creation and positioning in 3D space. Note that TheTable only references the table geometry, so if we could have many tables referencing the same geometry using different world transform populating.
override public void InitializeSimulation()
{
...
if (ResourceManager.LoadMeshResouse("Table.obj"))
{
TheTable = new SpatialBaseContainer();
TheTable.Geometry = ResourceManager.GetMeshObject("Table.obj");
this.SceneActors.Add(TheTable);
TheTable.NowRotate(0, 0, AGE_Engine3D.Math.AGE_Functions.PI / 2);
TheTable.NowMove(new AGE_Vector3Df(48.1973f, 222.4320f, 0f));
}
...
}
The order transforms that are applied is important. Had I placed the table in the center of the room then rotated the table, it would be in a completely different spatial place. It would equate to a 322 feet error.
Child Models and Local Transforms
There are many cases where a model may have sub, child or leaf models. These are kin to a glass relative to its parent table. If the table is not already scaled and aligned with the parent node (a room) the table will have to be scaled, rotated and translated to its proper place via a local transform. This is accomplished by combining the basic transform in a specific order in the same matter as the world space transform. If a child model is allowed to change relative to its parent then each child model will have a separate the overall World Transform and its local transform. The Total World Transform would look something like this for various objects.
By specifying that the TheGlass is a child to TheTable, I only have to locate TheGlass relative to the table. The transforms applied to TheTable will be carried forward to TheGlass. I can also create children to TheGlass and locate them relative to TheGlass. The Following code and image demonstrate this concept.
override public void InitializeSimulation()
{
...
if (ResourceManager.LoadMeshResouse("Glass.obj"))
{
TheCups = new SpatialBaseContainer();
TheCups.Geometry = ResourceManager.GetMeshObject("Glass.obj");
TheCups.NowMove(new AGE_Vector3Df(0.0f, 0.0f, 3.083f));
this.TheTable.AddChildren(TheCups);
SpatialBaseContainer NewKid = new SpatialBaseContainer();
NewKid.Geometry = TheCups.Geometry;
NewKid.NowScale(new AGE_Vector3Df(1.0f, 0.75f, 2));
NewKid.NowMove(new AGE_Vector3Df( 3f,0, 0));
TheCups.AddChildren(NewKid);
NewKid = new SpatialBaseContainer();
NewKid.Geometry = TheCups.Geometry;
NewKid.NowScale(new AGE_Vector3Df(1.0f, 3.0f, .5f));
NewKid.NowMove(new AGE_Vector3Df(3f,0, 0));
TheCups.AddChildren(NewKid);
}
...
}
View Space (Hv)
After a model is transformed to its position into World Space it will then be transformed in to View Space or Camera Space. The transform is characterized by Camera Location and the View direction. The Transform is in the form of:
public static AGE_Matrix_44 HView(ref AGE_Vector3Df Eye, ref AGE_Vector3Df Target,
ref AGE_Vector3Df UpVector)
{
AGE_Matrix_44 result = AGE_Matrix_44.Zero();
AGE_Vector3Df VDirection = (Target  Eye);
VDirection = VDirection.UnitVector();
AGE_Vector3Df RightDirection = AGE_Vector3Df.CrossProduct(ref VDirection,
ref UpVector);
RightDirection = RightDirection.UnitVector();
AGE_Vector3Df UpDirection = AGE_Vector3Df.CrossProduct(ref RightDirection,
ref VDirection);
UpDirection = UpDirection.UnitVector();
result.col[0][0] = RightDirection.X;
result.col[1][0] = RightDirection.Y;
result.col[2][0] = RightDirection.Z;
result.col[0][1] = UpDirection.X;
result.col[1][1] = UpDirection.Y;
result.col[2][1] = UpDirection.Z;
result.col[0][2] = 1 * VDirection.X;
result.col[1][2] = 1 * VDirection.Y;
result.col[2][2] = 1 * VDirection.Z;
result.col[3][0] = 1* AGE_Vector3Df.DotProduct(ref RightDirection, ref Eye);
result.col[3][1] = 1 * AGE_Vector3Df.DotProduct(ref UpDirection, ref Eye);
result.col[3][2] = AGE_Vector3Df.DotProduct(ref VDirection, ref Eye);
result.col[3][3] = 1;
return result;
}
Because the OpenGL uses a righthanded coordinate system the D vector is multiplied by 1 in the matrix Q construction, but for lefthanded coordinate system this would not be necessary.[1]
Provided in the zip file are simple camera classes. In the sample application I used the AGE_WalkThroughCamera
class allowing me to create a camera that could move through the building and actively update the camera's focus. This is accomplished by updating the Target and Eye locations, then recalculating the View Matrix. This creates the animation seen in the video above.
Projection Matrixes (Hproj and Hortho)
Perspective Transform
After a model is transformed to its position into View Space, it will then be transformed in to its final viewed position via projection transformation. There are two basic types of projection transforms that I am aware of: Orthographic, and Perspective. The Perspective projection mimics the way we perceive the real world. Objects that are closer appear larger and parallel lines converge at the horizon. Here is how the Perspective transform is constructed.
It is implemented in static HProjGL method.
public static AGE_Matrix_44 HProjGL(float left,
float right,
float top,
float bottom,
float near,
float far)
{
float invRDiff = 1 / (right  left + float.Epsilon);
float invUDiff = 1 / (top  bottom + float.Epsilon);
float invDDiff = 1 / (far  near + float.Epsilon);
AGE_Matrix_44 result = AGE_Matrix_44 .Zero();
result.col[0][0] = 2 * near * invRDiff;
result.col[1][1] = 2 *From Subject Received Size Categories
Newton, Curtis RE: Accident on the DCC System at the Mexico City Airport
1:35 PM 8 KB near * invUDiff;
result.col[2][0] = (right + left) * invRDiff;
result.col[2][1] = (top + bottom) * invUDiff;
result.col[2][2] = 1 * (far + near) * invDDiff;
result.col[2][3] = 1;
result.col[3][2] = 2 * (far * near) * invDDiff;
return result;
}
Orthographic Transform
The Orthographic projection is the somewhat the opposite of the Perspective projection. An object’s depth in the view plane has no bearing of size of the object and parallel lines remain parallel. Here is how the Orthographic transform is constructed.
It is implemented in static HOrtho method.
public static AGE_Matrix_44 HOrtho(float left,
float right,
float top,
float bottom,
float near,
float far)
{
float invRDiff = 1 / (right  left);
float invUDiff = 1 / (top  bottom);
float invDDiff = 1 / (far  near);
AGE_Matrix_44 result = AGE_Matrix_44.Zero();
result.col[0][0] = 2 * invRDiff;
result.col[3][0] = 1 * (right + left) * invRDiff;
result.col[1][1] = 2 * invUDiff;
result.col[3][1] = 1 * (top + bottom) * invUDiff;
result.col[2][2] = 2 * invDDiff;
result.col[3][2] = 1 * (far + near) * invDDiff;
result.col[3][3] = 1;
return result;
}
How to use the Code
Once we have all of these different types of transforms how are they used? In each call to the rendering function the sample application [Implementing the OpenGL interface], the application resets the Projection Matrix (GL_PROJECTION) and the Model/View Matrix (GL_MODELVIEW). Since the Camera and Projection rarely change during each render call, I load both the Projection Matrix and View Matrix into the OpenGL’s Projection Matrix. I also load the identity matrix in the Model/View matrix which will be overloaded as each entity is rendered.
static public void RenderScence()
{
Object LockThis = new Object();
lock (LockThis)
{
Gl.glClear(Gl.GL_COLOR_BUFFER_BIT  Gl.GL_DEPTH_BUFFER_BIT);
...
if (!CurrentCamera.IsInitalized)
CurrentCamera.ResizeWindow(ScreenWidth, ScreenHeight);
AGE_Matrix_44 HTotal = CurrentCamera.HTotal;
Gl.glMatrixMode(Gl.GL_PROJECTION);
Gl.glLoadIdentity();
Gl.glLoadMatrixf(HTotal.GetListValues());
Gl.glMatrixMode(Gl.GL_MODELVIEW);
Gl.glLoadIdentity();
if(
SceneGraph.RenderLights)
Gl.glEnable(Gl.GL_LIGHTING);
foreach (ISpatialNode obj in WorldObjectList)
if (obj.IsVisable) obj.RenderOpenGL();
...
...
Gl.glFinish();
}
}
Now that the setup is complete the application cycles through all of my renderable objects and calls their rendering function. Each object is responsible for setting the Model/View Matrix appropriate to the objects requirements.
public void RenderOpenGL()
{
if (this.IsVisable)
{
Gl.glMatrixMode(Gl.GL_MODELVIEW);
if (!this.IsHModelUpdated)
this.UpdateHModel();
if (!this.IsHTotalUpdated)
this.UpdateHTotal();
Gl.glLoadMatrixf(this.HTotal.GetListValues());
if (Geometry != null)
this.Geometry.RenderOpenGL();
foreach (IRenderOpenGL ChildGeometry in this.Children)
ChildGeometry.RenderOpenGL();
}
}
There is a lot more included in the .zip file not discussed here, but I will go into the other classes and concepts in other articles.
Further Reading
Books
Websites
History
 20090902  Second Article Released.