Click here to Skip to main content
Click here to Skip to main content

Space and Matrix Transformations - Building a 3D Engine

By , 4 Sep 2009
Rate this:
Please Sign up or sign in to vote.
WalkThrough2.gif

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 non-game 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 real-time 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.

Basic Matrix

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:

Scale Matrix

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 X-Axis, Y-Axis, and Z-Axis. There are three variations of a 4x4 matrix with various arrangements on the M matrix mentioned above. It is in the form of:

Scale Matrix

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();
            //Rotate about the X-Axis
            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;
            }
            
            //Rotate about the Y-Axis
            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;
            }
            
            //Rotate about the Z-Axis
            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:

Transpose Matrix

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.

World Transform

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.

Child Transform

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);
        //Child Cup #1
        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);
        //Child Cup #2
        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);
    }
    ...

}

Child Transforms 2

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:

View Transform

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 right-handed coordinate system the D vector is multiplied by -1 in the matrix Q construction, but for left-handed 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.

Projection Transform

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

Projection Transform

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.

Ortho Transform

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

Projection Transform

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);
        ...
        //Verify the Current Camrea is Initalized
        if (!CurrentCamera.IsInitalized)
            CurrentCamera.ResizeWindow(ScreenWidth, ScreenHeight);
        
        //Get the Combined Projection and View Transform
        AGE_Matrix_44 HTotal = CurrentCamera.HTotal;
        
        //Load it in to OpenGl
        Gl.glMatrixMode(Gl.GL_PROJECTION);
        Gl.glLoadIdentity();
        Gl.glLoadMatrixf(HTotal.GetListValues());
        Gl.glMatrixMode(Gl.GL_MODELVIEW);
        Gl.glLoadIdentity();
        
        //If there are lights turn lighting on
        if(
        SceneGraph.RenderLights)
            Gl.glEnable(Gl.GL_LIGHTING);
            
        //Render each visable Spatial Object
        foreach (ISpatialNode obj in WorldObjectList)
            if (obj.IsVisable) obj.RenderOpenGL();
        ...
        //Render HUD
        ...
        
        //Display the new screen
        Gl.glFinish();
    }
}

Now that the setup is complete the application cycles through all of my render-able objects and calls their rendering function. Each object is responsible for setting the Model/View Matrix appropriate to the objects requirements.

//In the SpatialBaseContainer Class
public void RenderOpenGL()
{
    if (this.IsVisable)
    {
        Gl.glMatrixMode(Gl.GL_MODELVIEW);
        //Verify the Model Transform is Updated
        if (!this.IsHModelUpdated)
            this.UpdateHModel();
        
        //Verfiy any Parent Transfor is Included
        if (!this.IsHTotalUpdated)
            this.UpdateHTotal();
        
        //Load the Model Transform in to OpenGL
        Gl.glLoadMatrixf(this.HTotal.GetListValues());
        
        //Render Parent Geometry
        if (Geometry != null)
            this.Geometry.RenderOpenGL();
            
          //Render any children
        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

  • 2009-09-02 - Second Article Released.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

About the Author

ARon_
Other Lea+Elliott, Inc.
United States United States
I am a licensed Electrical Engineer at Lea+Elliott, Inc. We specialize in the planning, procurement and implementation of transportation systems, with special emphasis on automated and emerging technologies.

Comments and Discussions

 
QuestionHelp PinmemberMaxime Gerbe15-Nov-11 11:43 
AnswerRe: Help PinmemberARon_16-Nov-11 4:11 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140415.2 | Last Updated 4 Sep 2009
Article Copyright 2009 by ARon_
Everything else Copyright © CodeProject, 1999-2014
Terms of Use
Layout: fixed | fluid