Black Art of 3D Game Programming, Chapter 13: Universal Transformations
From Dpfileswiki
We have learned how to create 3D and how to display 3D objects. It’s now time to bring our static objects to life. Within this chapter, we are going to breach all the barriers of time and space and learn how to move around in the 3D virtual worlds that we have created. We are going to cover in detail the complex chain of transformations necessary to move the player’s viewpoint anywhere in the universe and then project the images from Cyberspace onto the video screen. By the end of this chapter, you’ll be able to traverse and explore the parallel dimension of Cyberspace as if you were there.
The Player and the Universe
Thus far, we have thought of the player as being located at some specific viewpoint in the universe with a specific set of viewing angles. This is shown in Figure 13-1. However, due to limitations in our current graphics engine, we haven’t had much control over the position and orientation of the player. We have been fixing the position of the player at the origin (0,0,0) and setting the view angles at (0,0,0). Hence, the player has been sitting at the origin of the world coordinate system looking down the positive Z axis, as shown in Figure 13-2.
The reason we have kept the player’s viewpoint at (0,0,0) and set the view angles
to (0,0,0) is that it makes the world to camera transformation easy. Basically, camera coordinates are equal to world coordinates in this case; hence, the transformation is nothing more than a simple assignment. However, that’s all about to change. The main point of a 3D game is to allow the player to move around in the universe while at the same time changing the angles of his viewing direction.
- The local to world transformation.
- The world to camera transformation.
- The final perspective projection to screen coordinates.
Actually, we have already spoken of all of these concepts in the theoretical discussions in Chapter 10, and we’ve even implemented much of the transformations in the previous two chapters. Now we are going to formally write functions that perform these operations at the object level.
Moving the Player and the Camera
The first thing we need to be able to do is move the player’s viewpoint and change the orientation of the viewing angles. This is accomplished by setting the viewpoint to the desired position in world coordinates and the view angle to the desired X, Y, Z view angles in degrees (relative to the axes). For example, we know that the viewpoint of the engine is contained in the global variable view_point, which is simply a point in 3D space, along with the homogenizing component w, which is usually set to 1.0. Therefore, if we wanted to position the camera at (1000,2000,3000) in world coordinates, we would perform the following assignment:
view_point.x = 1000; view_point.y = 2000; view_point.z = 3000; view_point.w = 1;
Then the viewpoint or camera position would be that shown in Figure 13-3. Positioning the viewpoint is not enough. We must also set the view direction. Normally, the view direction is along the positive Z axis. However, we may want to change this. Making this change is as simple as changing another triplet of data–that is, the view angles stored in the global variable view_angle. As an example, say we wanted to set the view angles equal to the view direction of (45,45,45), as shown in Figure 13-4. The assignments would be:
view_angle.ang_x = 45; view_angle.ang_y = 45; view_angle.ang_z = 45;
Notice that the angles are in degrees rather than radians. This is because we aren’t using the built-in transcendental functions. We are instead using precomputed look-up tables that are stored as linear arrays of 360 elements, one element for each value of SIN and COSINE from 0 to 360 degrees (we have used these before for the object rotations in Chapter 11). Negative values are also legal, but a preprocessing filter must be used to convert the negative angle to a positive one via the formula:
if (angle<0) angle+=360;
Finally, no one said that the camera had to be attached to the player. For example, we might want to make a 3D game that has a second person’s view, so we can see ourselves in front of the view screen. Thus, the camera viewpoint and view angles need not be the same as the player’s, if that’s what we wish. Furthermore, we can implement multiple cameras and switch amongst them by creating an array or similar structure and then assigning the desired virtual camera position and orientation to the global variables view_point and view_angles whenever a different camera angle is desired. An example of this might be a 3D sports game, or maybe a combat game, in which the player has a team on his side and from time to time may want to see out of each of his teammate’s eyes.
Positioning the Virtual Viewpoint at the Origin
Now that we have the technology to move the viewpoint around and change the view angles, how do we take this into account to generate the final image on the screen? Well, we have already seen a form of this during both of the demos WIREDEMO.EXE and SOLIDEMO.EXE. Both of these have a bit of code that transforms the local coordinates of each object into world coordinates, but they lack the world to camera transform. The local to world transformation is the only step necessary because the viewpoint is at the origin and the view angles are all zero; that is, the camera is looking down the positive Z axis. Basically, it is in a neutral position. This is a must!
To perform a 3D projection, we must position and rotate the objects such that the camera is located at (0,0,0) with view angles of (0,0,0), as shown in Figure 13- 5. How can this be done? Well, it’s accomplished by moving the entire universe relative to the camera position and rotating the entire universe relative to the view angles. After the transformation, all the objects will have been transformed so that they are all located in positions such that the camera seems to be at (0,0,0) with view angles (0,0,0). This is called the camera transformation and is the one we have been leaving out. Once we have figured out how to perform this transformation, our viewing system is complete. We can then fly around in our virtual game universe and explore it at will. But before we do this, let’s formally write out the local to world transformation function for an object.
The Local to World Transformation
When each object is loaded into the computer, it is relative to its own local coordinate space, as shown in Figure 13-6. This is to facilitate local transformations such as rotation and scaling. However, when we want to view an object, we must move it into position in the game universe. This is accomplished by adding to each vertex of the local vertex list the position of the object in world coordinates. This world position is recorded in the world_pos field of each object. So a function that converts local coordinates to world coordinates should simply loop through all the vertices of the local vertex list and add the world_pos to each vertex. The results should then be stored in the world vertex list of the object. Listing 13-1 does just that.
Listing 13-1 Function that converts local coordinates of an object into world coordinates and stores the results in the world vertex list of the object
void Local_To_World_Object(object_ptr the_object)
{
// this function converts an object's local coordinates to world coordinates
// by translating each point in the object by the objects current position
int index; // looping variable
// move object from local position to world position
for (index=0; index<the_object->num_vertices; index++)
{
the_object->vertices_world[index].x = the_object->vertices_local[index].x +
the_object->world_pos.x;
the_object->vertices_world[index].y = the_object->vertices_local[index].y +
the_object->world_pos.y;
the_object->vertices_world[index].z = the_object->vertices_local[index].z +
the_object->world_pos.z;
} // end for index
// reset visibility flags for all polys
for (index=0; index<the_object->num_polys; index++)
{
the_object->polys[index].visible = 1;
the_object->polys[index].clipped = 0;
} // end for
} // end Local_To_World_Object
The function Local_To_World_Object( ) takes a single parameter, which is the object to be transformed. The function computes the world coordinates of the object and then resets the visibility and clipped flags of each polygon (just as a precaution). You may or may not want this reset to be performed, so keep it in mind. After processing an object with the above function, the previous vertices_world[ ] array will become invalidated and refreshed with the current world coordinates of the object.
The next step is to convert the world coordinates into camera coordinates relative to the viewpoint and view angles. Therefore, we need a world to camera transformation.
The World to Camera Transformation
The world to camera transformation is probably the most complex thing to understand of all this material, so once we’ve got it, it’s all downhill! What we want to do is move all the objects in such a way that the viewpoint seems to be at (0,0,0), and rotate all the objects in such a way that the view angles seem to be at (0,0,0). We will do this in two steps. The first step is the translation. During this step we take the position of the viewpoint or camera and subtract it from each object in world coordinates. In other words, we multiply each object by a translation matrix that is the inverse of the viewpoint translation matrix.
For example, if the viewpoint was at (10,50,–30), we would want to translate each object by the amounts (–10,–50,30) or, in matrix form, we would multiply each object’s world vertex list by:
|1 0 0 0|
T^-1= |0 1 0 0| = the inverse of the viewpoint translation matrix
|0 0 1 0|
|-10 -50 30 1|
The next step is a bit more complex. We must rotate the objects in world coordinates in such a way that the camera is positioned so that its view angles are (0,0,0). This may seem hard, but it is achieved in a similar way as the translation: the inverse of the view angle rotation is computed and applied to each vertex of each object in world coordinates. Thus, if the view angles are (5,10,–5), which means 5 degrees around the X axis, 10 degrees around the Y axis, and –5 degrees around the Z axis, then the inverse of this would be (–5,–10,5). In other words, to rotate the objects into the camera position, we rotate them the opposite of the camera angles. In matrix form, this is a bit easier to see. We must perform three separate operations, one for each axis. Then if we wish, we can concatenate them. Thus, we must compute:
- The world to camera transformation = T–1* Rx–1* Ry–1* Rz–1 = WC
This states that the final world to camera transformation is the result of multiplying the inverse of the player’s translation matrix along with the inverse of the player’s X, Y, and Z rotation matrices. The final result, WC (world to camera), can then be multiplied by each vertex of each object’s world coordinate, and the results will be camera coordinates ready for projection.
Therefore, assuming we have computed WC, the function to perform the world to camera transformation is shown in Listing 13-2.
Listing 13-2 Function that converts world coordinates to camera coordinates
void World_To_Camera_Object(object_ptr the_object)
{
// this function converts an object's world coordinates to camera coordinates
// by multiplying each point of the object by the inverse viewing transformation
// matrix which is generated by concatenating the inverse of the view position
// and the view angles the result of which is in global_view
int index; // looping variable
// iterate thru all vertices of object and transform them into camera coordinates
for (index=0; index<=the_object->num_vertices; index++)
{
// multiply the point by the viewing transformation matrix
// x component
the_object->vertices_camera[index].x =
the_object->vertices_world[index].x * global_view[0][0] +
the_object->vertices_world[index].y * global_view[1][0] +
the_object->vertices_world[index].z * global_view[2][0] +
global_view[3][0];
// y component
the_object->vertices_camera[index].y =
the_object->vertices_world[index].x * global_view[0][1] +
the_object->vertices_world[index].y * global_view[1][1] +
the_object->vertices_world[index].z * global_view[2][1] +
global_view[3][1];
// z component
the_object->vertices_camera[index].z =
the_object->vertices_world[index].x * global_view[0][2] +
the_object->vertices_world[index].y * global_view[1][2] +
the_object->vertices_world[index].z * global_view[2][2] +
global_view[3][2];
} // end for index
} // end World_To_Camera_Object
Similarly to the Local_To_World_Object( ) function, the World_To_Camera_Object( ) function takes as a single parameter a pointer to the object to be transformed. The results of the transformation are placed into the vertices_camera[] array of the object’s data structure. The function needs the global world to camera transformation global_view matrix to be precomputed. Also, note that instead of making a separate call to one of the matrix multiplying functions, the function manually performs the matrix multiplication a component at a time, solving for x, y, and then z of each transformed point. This is for speed. The question is, where are we going to get the global world to camera transformation matrix? Well, we need to write a function that computes it.
Implementing the Global Transformation Matrix
The global transformation matrix is named global_view, and it contains the product of the inverses of the viewing position and viewing angle rotation matrices. Computing this matrix can be done in five steps:
- Compute the inverse of the translation matrix of the viewpoint.
- Compute the inverse of the X rotation matrix of the view angles.
- Compute the inverse of the Y rotation matrix of the view angles.
- Compute the inverse of the Z rotation matrix of the view angles.
- Compute the product of all of them and store the result in global_view.
The function shown in Listing 13-3 does just that.
Listing 13-3 Function that creates the global_view world to camera transformation matrix
void Create_World_To_Camera(void)
{
// this function creates the global inverse transformation matrix
// used to transform world coordinates to camera coordinates
matrix_4x4 translate, // the translation matrix
rotate_x, // the x,y and z rotation matrices
rotate_y,
rotate_z,
result_1,
result_2;
// create identity matrices
Mat_Identity_4x4(translate);
Mat_Identity_4x4(rotate_x);
Mat_Identity_4x4(rotate_y);
Mat_Identity_4x4(rotate_z);
// make a translation matrix based on the inverse of the viewpoint
translate[3][0] = -view_point.x;
translate[3][1] = -view_point.y;
translate[3][2] = -view_point.z;
// make rotation matrices based on the inverse of the view angles
// note that since we use lookup tables for sin and cosine, it's hard to
// use negative angles, so we will use the fact that cos(-x) = cos(x)
// and sin(-x) = -sin(x) to implement the inverse instead of using
// an offset in the lookup table or using the technique that
// a rotation of -x = 360-x. note the original rotation formulas will be
// kept in parentheses, so you can better see the inversion
// x matrix
rotate_x[1][1] = ( cos_look[view_angle.ang_x]);
rotate_x[1][2] = -( sin_look[view_angle.ang_x]);
rotate_x[2][1] = -(-sin_look[view_angle.ang_x]);
rotate_x[2][2] = ( cos_look[view_angle.ang_x]);
// y matrix
rotate_y[0][0] = ( cos_look[view_angle.ang_y]);
rotate_y[0][2] = -(-sin_look[view_angle.ang_y]);
rotate_y[2][0] = -( sin_look[view_angle.ang_y]);
rotate_y[2][2] = ( cos_look[view_angle.ang_y]);
// z matrix
rotate_z[0][0] = ( cos_look[view_angle.ang_z]);
rotate_z[0][1] = -( sin_look[view_angle.ang_z]);
rotate_z[1][0] = -(-sin_look[view_angle.ang_z]);
rotate_z[1][1] = ( cos_look[view_angle.ang_z]);
// multiply all the matrices together to obtain a final world to camera
// viewing transformation matrix i.e.
// translation * rotate_x * rotate_y * rotate_z
Mat_Mul_4x4_4x4(translate,rotate_x,result_1);
Mat_Mul_4x4_4x4(result_1,rotate_y,result_2);
Mat_Mul_4x4_4x4(result_2,rotate_z,global_view);
} // end Create_World_To_Camera
The function is fairly straightforward except maybe for a little trick. You may notice that the rotation equation seems a bit reversed. You may think that we would use negative angles to obtain the inverse, and we could, but I decided to use identities along with negative angles. For example, if we wanted the
- cos(–x)
then this is equivalent to:
- –cos(x)
Furthermore, the sin(–x) is equivalent to:
- –sin(x)
Therefore, we can plug these rules into the rotation equations and save a few sign inversions, and so forth.
We are almost ready to go! Assuming that we have defined and loaded an object named obj_1, we could transform it into camera coordinates and prepare it for projection with the following calls:
Local_To_World_Object((object_ptr)&obj_1); Create_World_To_Camera Local_To_World_Object((object_ptr)&obj_1);
That’s it!
Now that we have a camera-ready object(s), let’s take a look at how to project it to make sure we really understand it.
Projecting the Universe on the Screen
We have already seen the functions that can draw objects on the screen; however, later we will want to remodel our little engine a bit to break each object down into polygons and then project them on the screen. But let’s stick to objects for now. As an example of using our new functions, let’s once again rewrite the demo program so that it allows us to move the viewpoint and change the view angles in real-time while viewing a solid object. The only real changes to the SOLIDEMO.C program are going to be calls to the new transformation functions along with some keyboard support to change both the viewing position and viewing angles. Moreover, we are going to remove the code that moves the object and simply fix it in space.
The name of the demo program that does all this is SOL2DEMO.EXE and the source is called SOL2DEMO.C. To generate your own executable, you will have to link in the module BLACK11.C if it isn’t already in your library. This chapter as well as the last chapter haven’t added any new library modules–we are still exploring the large set of functions from BLACK11.C and BLACK11.H. Anyway, let’s take a look at the control and execution of the program. Table 13-1 lists the keys we will use to move the viewpoint and orientation.
To run the program, you must feed it a PLG file. Within this chapter’s directory, you will find:
- CUBE.PLG - A cube
- PYRAMID.PLG - A four-sided pyramid
- CRYSTAL.PLG - A crystal-looking object (sorta!)
For example, to load the cube, you would type:
- SOL2DEMO CUBE.PLG
The source for the program is shown in Listing 13-4.
Listing 13-4 Demo of the complete local to camera transformation pipeline
// I N C L U D E S ///////////////////////////////////////////////////////////
#include <io.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <bios.h>
#include <fcntl.h>
#include <memory.h>
#include <malloc.h>
#include <math.h>
#include <string.h>
#include <search.h> // this one is needed for qsort()
// include all of our stuff
#include "black3.h"
#include "black4.h"
#include "black5.h"
#include "black6.h"
#include "black8.h"
#include "black9.h"
#include "black11.h"
// G L O B A L S /////////////////////////////////////////////////////////////
object test_object; // the test object
// M A I N ////////////////////////////////////////////////////////////////////
void main(int argc,char **argv)
{
int index, // looping variable
done=0; // exit flag
char buffer[80]; // used to print strings
// load in the object from the command line
if (!PLG_Load_Object(&test_object,argv[1],1))
{
printf("\nCouldn't find file %s",argv[1]);
return;
} // end if
// position the object 300 units in front of user
Position_Object((object_ptr)&test_object,0,0,300);
// set the viewpoint
view_point.x = 0;
view_point.y = 0;
view_point.z = 0;
// create the sin/cos lookup tables used for the rotation function
Build_Look_Up_Tables();
// set graphics to mode 13h
Set_Graphics_Mode(GRAPHICS_MODE13);
// allocate double buffer
Create_Double_Buffer(200);
// read the 3d color palette off disk
Load_Palette_Disk("standard.pal",(RGB_palette_ptr)&color_palette_3d);
Write_Palette(0,255,(RGB_palette_ptr)&color_palette_3d);
// install the isr keyboard driver
Keyboard_Install_Driver();
// set viewing distance
viewing_distance = 250;
// main event loop
while(!done)
{
// compute starting time of this frame
starting_time = Timer_Query();
// erase the screen
Fill_Double_Buffer(0);
// test what key(s) user is pressing
// test if user is moving viewpoint in positive X
if (keyboard_state[MAKE_RIGHT])
view_point.x+=5;
// test if user is moving viewpoint in negative X
if (keyboard_state[MAKE_LEFT])
view_point.x-=5;
// test if user is moving viewpoint in positive Y
if (keyboard_state[MAKE_UP])
view_point.y+=5;
// test if user is moving viewpoint in negative Y
if (keyboard_state[MAKE_DOWN])
view_point.y-=5;
// test if user is moving viewpoint in positive Z
if (keyboard_state[MAKE_PGUP])
view_point.z+=5;
// test if user is moving viewpoint in negative Z
if (keyboard_state[MAKE_PGDWN])
view_point.z-=5;
// this section takes care of view angle rotation
if (keyboard_state[MAKE_Z])
{
if ((view_angle.ang_x+=10)>360)
view_angle.ang_x = 0;
} // end if
if (keyboard_state[MAKE_A])
{
if ((view_angle.ang_x-=10)<0)
view_angle.ang_x = 360;
} // end if
if (keyboard_state[MAKE_X])
{
if ((view_angle.ang_y+=10)>360)
view_angle.ang_y = 0;
} // end if
if (keyboard_state[MAKE_S])
{
if ((view_angle.ang_y-=5)<0)
view_angle.ang_y = 360;
} // end if
if (keyboard_state[MAKE_C])
{
if ((view_angle.ang_z+=5)>360)
view_angle.ang_z = 0;
} // end if
if (keyboard_state[MAKE_D])
{
if ((view_angle.ang_z-=5)<0)
view_angle.ang_z = 360;
} // end if
// test for exit key
if (keyboard_state[MAKE_ESC])
done=1;
// rotate the object on all three axes
Rotate_Object((object_ptr)&test_object,2,4,6);
// convert to world coordinates
Local_To_World_Object((object_ptr)&test_object);
// shade and remove backfaces, ignore the backface part for now
// notice that backface shadin and backface removal is done in world coordinates
Remove_Backfaces_And_Shade((object_ptr)&test_object);
// create the global world to camera transformation matrix
Create_World_To_Camera();
// convert to camera coordinates
World_To_Camera_Object((object_ptr)&test_object);
// draw the object
Draw_Object_Solid((object_ptr)&test_object);
// print out viewpoint
sprintf(buffer,"Viewpoint is at (%d,%d,%d) ",(int)view_point.x,
(int)view_point.y,
(int)view_point.z);
Print_String_DB(0,0,9,buffer,0);
sprintf(buffer,"Viewangle is at (%d,%d,%d) ",(int)view_angle.ang_x,
(int)view_angle.ang_y,
(int)view_angle.ang_z);
Print_String_DB(0,10,9,buffer,0);
// display double buffer
Display_Double_Buffer(double_buffer,0);
// lock onto 18 frames per second max
while((Timer_Query()-starting_time)<1);
} // end while
// restore graphics mode back to text
Set_Graphics_Mode(TEXT_MODE);
// restore the old keyboard driver
Keyboard_Remove_Driver();
} // end main
Visually, the program doesn’t seem to do much more than the SOLIDEMO.EXE program. But internally, as we know, it is doing far more.
We actually have enough software at this point to fly freely in a 3D universe. Of course, we are still lacking the knowledge about hidden surface removal and 3D clipping, but we’re getting there!
Order of Operations
We are reaching a point of sophistication and complexity in our software where we need to start thinking about the order that we are performing various operations. We have talked about the graphics pipeline a few times now, and it’s becoming clear that as we learned, the pipeline can be executed in more than one order depending on the situation. We already have software for local to world transformations, world to camera transformations, shading, back-face culling (even though we are going to cover it in the next chapter), and 2D screen projections. We should start asking ourselves, do we need to perform all of these operations in the order we have been performing them? And, do we need to perform all of them all of the time?
The answer to both questions is no! In fact, as long as the final results are the desired picture, the less we have to do, the better. So, keep this in mind as we cover the material. By fully understanding each component of the pipeline, you may find ways to improve and make it faster that aren’t shown in this book!
Summary
This chapter has been a nice break from the complexity of the others. Basically, we formalized some concepts such as local to world and world to camera transformations. We also pinned down the difference between the camera and the player and how they can be separate.
The demi-gods of Cyberspace are getting worried–soon we will master their universe and control their minds… ha ha ha! Sorry about that; I get carried away sometimes. Anyway, now it’s time to learn how to remove the unwanted polygons from our displays; otherwise known as hidden surface removal.
Continue
- Black Art of 3D Game Programming: Writing Your Own High-Speed 3D Polygon Video Games in C Table of Contents
- Black Art of 3D Game Programming, Chapter 14: Hidden Surface and Object Removal
| Copyright 2006 Andre LaMothe |
|
