Build a 3D Engine
From Wikibooks, the open-content textbooks collection
This book describes all the components required to build a 3D Engine. It also looks at the architecture of a 3D Engine and how a 3D engine works. It starts with basic things such as graphics output under Windows to the 3D engine architecture and polygon filling, etc.
Contents |
[edit] Introduction
Welcome to the book about state-of-the-art 3D coding. We are not going to code anything yet, but we will dive into the subject and get our mind focused on what we want. This is a guide to achieving that final, great goal: Learning to program 3D stuff yourself. And not just the average 3D stuff like the spinning wirecube that your uncle once showed you when you where a kid; but rather mouth-watering, fast and realistic cubes. Maybe even spheres. Believe me, it's better than driving lessons. It gives more pleasure than... well, ehm, can't think of anything right now, and ultimately, you can make this world a better place. Or, you can make your own world, and make it a better place.
Let's get a few things clear:
This book focuses on software rendering only. That does not mean that you can stop reading now because you own a Geforce or a Radeon.
Two reasons:
- Most techniques presented here are needed for hardware rendering too, except for the raw metal rasterizing optimization,
- You need to know how real rasterization works to get the most out of accelerated 3D graphics.
A few months ago I spoke to someone who asked me: "Why is it so difficult to make something like Quake? Can't you just toss all the polygons to the card, and let it display them?" - That's what I mean. Keep reading. Second thing I want to make clear right now is that I am not going to do your homework. There might be a snippet of code here and there to clarify stuff, but at the end there will be NO full blazing 3D engine. That's your job. You're supposed to take the ideas, add some intellect, and produce something better. Remember, you wanted to turn your world into a better place.
Okay, on to the real stuff.
This book gets you started on developing a 'Portal Engine'. That's just my choice, I could as well have taught you how to do a BSP engine, or whatever, and most information is also useful if you want to do something completely different.
[edit] What's a portal engine anyway?
Basically, a portal based engine is a way to 'spatially index' the incredibly big datasets that usually make up a world: in other words, how to avoid having to display all that data every frame and instead only draw what's relevant. A good 3D engine should run at a decent speed, no matter what the size of the full world is; speed should be relative to the amount of detail that is actually visible. It would of course be even better if the speed would only depend on the number of pixels you want to draw, but since apparently no one has found an algorithm that does that, we'll go for the next best thing.
A basic portal engine relies on a data set that represents the world. The 'world' is subdivided in areas, that I call 'sectors'. Sectors are connected through 'portals', hence the name 'Portal Engine'. A portal-based engine world can be thought of as a variation of a boundary representation (or B-rep) data structure that is very much special-cased to the properties of a gaming world. The rendering process starts in the sector that the camera is in. It draws the polygons in the current sector, and when a portal is encountered, the adjacent sector is entered, and the polygons in that sector are processed. This would of course still draw every polygon in the world, assuming that all sectors are somehow connected. But, not every portal is visible. And if a portal is not visible, the sector that it links to doesn't have to be drawn. That's logical: A room is only visible if there's a line of sight from the camera to that room, that is not obscured by a wall.
So now we have what we want: If a portal is invisible, tracing stops right there. If there's a huge part of the world behind that portal, that part is never processed. The number of polygons that are actually processed is thus almost exactly equal to the number of visible polygons, plus the inserted portal polygons.
By now it should also be clear where portals should be inserted in a world: Good spots for portals are doors, corridors, windows and so on. That also makes clear why portal engines suck at outdoor scenes: It's virtually impossible to pick good spots for portals there, and each sector can 'see' virtually every other sector in the world. Portal rendering can be perfectly combined with outdoor engines though: If you render your landscape with another type of engine, you could place portals in entrances of caves, buildings and so on. When the 'normal' renderer encounters a portal, you could simply switch to portal rendering for everything behind that portal. That way, a portal engine can even be nice for a 'space-sim'...
[edit] Graphics output under Windows
Here we will discuss things like screen access under Windows. Besides that, some basic information is given on double buffering, pixel plotting and that sort of stuff.
In the old days, there was DOS. And in DOS, there was mode 13. Once initialized, the unsuspecting coder could write to video memory, starting at a fixed address, A0000 if I am correct. All this didn't block the computer, and worked on virtually every VGA card in the world. The mode allowed for output of 256 color graphics, and that was just fine, if you did it well.
But then something really bad happened. SVGA cards started to appear everywhere, and to make things worse, computers became fast enough to do true-color graphics. From that moment on, nothing was certain anymore. You had 15 bit graphics (for some VERY odd reason someone decided to ignore a whole bit), 16 bit graphics, 24 bit, 32 bit, and random orderings of the color components in these arrays of bits. You could for instance encounter a card that did RGB, but also BGR, or RGBA... So the VESA standard was invented. This made things bearable again.
As you know, as soon as a standard pops up, there's always somebody else (Microsoft) who thinks that it can be done better. So, Windows was 'presented' to the world (or shoved down our throats, just what you prefer). From that moment on, you were never certain what your processor was doing at a particular moment. It could be doing your application, but it could also switch to another 'important' application at a critical point in time for your demo... Things get worse when you surrender to Micro$oft and start coding 'native' applications: Drawing to a window is a disaster, requires a 'lock', and is even slower.
OK, enough ranting. Lets try to live with what we have. I always use a buffer, because it looks so much like the old mode 13. When I have such a buffer, I try to get it to a window as efficiently as possible. This is an absolutely necessary but uninteresting step. My favorite 'toolkit' for this is MGL: A rather huge lib from SciTech, the makers of UNIVBE, a.k.a. the 'Display Doctor'. This library allows you to create a window relatively easily, and to get a pointer to it. It still requires the 'lock' however, which means that you can't debug very nicely: During the 'lock', there are no screen updates. This can be partially bypassed by using your own buffer and copying it to the window once you're done. The lock is in this case only required during the copying process, and that's usually not a big problem. There's a small snag about the MGL library: It does much more than just displaying windows. It can for example also draw lines and polygons, and it contains OpenGL stuff. Because of this unnecessary load, you have to link a 1.5Mb library to your program just to open a window... So, there's something easier, which I wish to introduce to you. It's called 'PTC', which is an abbreviation of 'Prometheus True Color', or something like that. It's a really simple Direct X wrapper, and it allows you to do full-screen graphics output at various bit depths and resolutions, and nothing more. Therefore, the library is quite small. Opening the display requires only a couple of (easy to understand and remember) commands. After that, you have full access to the display. One problem remains: The dreadful lock. This can again be bypassed using the buffer copy, however.
A big advantage of PTC that I have to mention is that it is platform independent: PTC is also available for Linux, BeOS and some other OS's. So, if your program uses PTC for it's graphics output, you are merely 'using' Windows, rather than being forced to think towards it. It makes a future move to another OS easier too, since your code will work again with minor modifications.
So, here's a bit of homework for you: Go to http://www.gaffer.org/, and fetch the PTC library. Have a look at some of the example programs, you will notice that they are really extremely simple. Once you've done that, we can proceed.
Here's a small PTC application to play with:
#include "ptc.h" #include <stdlib.h>
int APIENTRY WinMain (HINSTANCE hInst, HINSTANCE hPrevInst,
LPSTR lpCmdLine, int nCmdShow)
{ try
{ Format format(32,0x00FF0000,0x0000ff00,0x000000ff);
Console console;
console.open("demo",320,200,format);
Surface surface(320,200,format);
int32* pixels=(int32*)new int32[320*200];
while (!console.key())
{ int32* surf=(int32*)surface.lock();
for (int i=0; i<(320*200); i++)
*(surf+i)=*(pixels+i); surface.unlock();
surface.copy(console);
console.update();
}
return 0;
}
catch (Error &error)
{ error.report();
}
}
An explanation: Most of the stuff here will probably be quite clear. I've added a couple of lines for the buffer stuff: First I declare a buffer of the same size as the PTC display, which is copied every frame during a 'lock' to the PTC surface. This keeps the time that the surface is actually locked as short as possible, preventing hang-ups for buggy code.
Note:During the rest of this series, we will completely ignore the Windows stuff. It will be assumed that you've somehow managed to get a buffer to draw in, so that we can focus on the interesting stuff: Hardcore-3D.
[edit] 3D Matrix editing
Now that we have had the nasty buffer and windows stuff, it's on to the real matter: Vector mathematics. Matrices are cool. They are also rather hard to understand fully, so if you want to know everything about them, this is the time to find a good site or book about them (preferably a site, and don't forget to submit the link to this site!).
First I want to talk about something else: Gathering knowledge. I often get e-mail from people asking me how I learned all my stuff. "What books can you recommend?" "Where did you start?", questions like that. My usual reaction to that is a chat with my wife about being 'auto-didact': You have to learn things for YOURSELF. Don't be dependent on other people's knowledge, gather your info yourself. And more important: TRY things. You won't get good by reading books, you get good by making mistakes. Gather info by browsing the web, that's the largest source of information in the world. And it's usually more up-to-date than the bookstore. Using this approach, it's possible to develop knowledge that nobody else has: You combine gathered knowledge in a unique way, allowing you to do things that nobody else did, and trying things that nobody thought of. That's how I got my (dubious) knowledge. It's kinda hard to explain, but I hope you get the point. :)
OK, back to the matrices. A matrix can be used to define a rotation in 3D space, and a translation. Therefore I usually use a 4x4 matrix: 3x3 defines an arbitrary rotation, the last column defines the movement, a.k.a. translation. Rotated coordinates can then be calculated by tossing the coordinate (vector) into the matrix.
Suppose you defined your matrix as an array of floats: Four rows by four columns, named for example cell[4][4]. You can 'toss in' a vector using the following formulas:
x_rotated = cell[0][0] * x + cell[1][0] * y + cell[2][0] * z + cell[3][0]
y_rotated = cell[0][1] * x + cell[1][1] * y + cell[2][1] * z + cell[3][1]
z_rotated = cell[0][2] * x + cell[1][2] * y + cell[2][2] * z + cell[3][2]
Note that the last row is not used, so theoretically you don't even have to store it.
So how do we create the matrix itself? We start with the unity matrix:
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
This matrix has the unique property that it does nothing to 3D coordinates: It leaves them perfectly intact. Then we take the desired rotation around the x-axis, which I will call 'rx' here. The matrix for this rotation looks like this:
1 0 0 0
0 cos(rx) sin(rx) 0
0 -sin(rx) cos(rx) 0
0 0 0 1
So, if you just wanted to rotate your 3D coordinates around the x-axis, you could use this matrix. However, if you also want to rotate around the y and z axis, you have to 'concatenate' the x rotation matrix with the y and z rotation matrix. Here they are:
y: cos(ry) 0 -sin(ry) 0
0 1 0 0
sin(ry) 0 cos(ry) 0
0 0 0 1
z: cos(rz) sin(rz) 0 0
-sin(rz) cos(rz) 0 0
0 0 1 0
0 0 0 1
OK, so how do we concatenate matrices? Here's how: Cell [x][y] of the concatenated matrix equals the sum of the rows multiplied by the columns. Some C code explains what I mean:
for (c=0; c<4; c++) for (r=0; r<4; r++)
conc[c][r] = m1[0][r] * m2[c][0] +
m1[1][r] * m2[c][1] +
m1[2][r] * m2[c][2] +
m1[3][r] * m2[c][3];
Note that the order in which you concatenate matrices is important! That's logical: If you first rotate 90 degrees around the x axis, then 45 degrees around the z axis, you get a different rotation than if you would have done these rotations in the opposite order.
That's the basic stuff. Here's how to put it in practice. Imagine you have a cube. It's located at (100,100,100) in 3D space, and should revolt around that coordinate. It's rotation is (rx, ry, rz), and of course we alter rx, ry and rz in a nice loop to have a spinning cube. The vertices of the cube can be defined as follows:
1: -50, -50, -50
2: 50, -50, -50
3: 50, 50, -50
4: -50, 50, -50
5: -50, -50, 50
6: 50, -50, 50
7: 50, 50, 50
8: -50, 50, 50
Note that the cube is initially defined at the 3D origin. That's because we wish to rotate it: If you would rotate a cube that was defined with it's center at (100,100,100) it would revolt around the 3D origin also, causing a huge sweep through 3D space. The center of the cube, a.k.a. it's translation, should be the (100,100,100). So, we construct a matrix, by starting with rx. We construct another matrix, for ry, and concatenate the two. Then we construct another matrix for rz, and concatenate it. Finally the translation is added, this can be done by directly altering the relevant matrix elements, cell[3][0], cell[3][1] and cell[3][2] (for x, y and z respectively). Then we toss the vertices in the final matrix, and voila! The rotated coordinates need to be processed of course to display them on the screen. You could use the following formula for that:
screen_x = rot_x * 500 / rot_z + 160;
screen_y = rot_y * 500 / rot_z + 100;
Note that I used 160 and 100 here as the centre of a 320x200 buffer. The resulting 2D coordinates can directly be plotted on your display, providing that they are NOT off screen.
OK, that's the basic stuff. Here's some more stuff to wet your appetite: You don't have to stop when you've concatenated rx, ry and rz. For example, if you have two cubes, with one circling around the other, you could define a rotation matrix with only a rotation around the x axis for the second cube. If you concatenate that matrix to the matrix of the 'parent' object, the circling cube will be rotated by the matrix of the first cube PLUS it's own matrix. This makes it possible to have a 'hierarchical' system of objects: For example a robot, with arms that rotate relatively to the body of the robot (concatenate arm matrix to robot matrix), and hands rotating relative to the arm (concatenate again).
You can do other nifty things with matrices too, like inverting them. This can be used in quick surface culling, I'll talk more about that later, this article is getting a bit lengthy already.
[edit] Data structures for 3D Graphics
I'm working on Focus, a light-weight 3D engine experiment that I merely use to try out little things like bilinear interpolation, shadows and fast software rendering in general. This little engine is of course not my first engine, and that's why I want to talk a little about 3D data structures. I've discovered that the main reason for dropping an engine and starting over from scratch is 'bad design'. Rewriting is no problem of course: Starting from scratch often improves code, since you can rewrite stuff that you painfully wrote in an earlier engine rather quickly, and usually with far less ugly and more efficient code. Earlier engines often had limitations that I could only get rid of by making heavy changes, or rewriting. Most of these limitations merely consisted of limitations in the data structures. Some examples:
One of my first 3D engines (the E3Dengine) was coded completely in Pascal. Polygons where internally stored as four-sided convex polygons, since my world only consisted of squares, so that seemed fine at first. After some months of coding, I had an indoor rendering engine, with 6DOF (that was before the release of Quake, by the way) and I encountered my first major problem: Clipping against the Z=0 plane. This is necessary for an indoor engine, since polygons often are partially behind you (as opposed to object rendering engines, where the entire object is usually in front of you). Vertices behind the camera do weird things when you apply perspective to them: Remember the perspective formulas from the previous article, where the rotated x and y coords where divided by their depth. The x and y coords are negated by this formula as soon as they pass z=0, and ON z=0, the formula causes a 'divide by zero'. The problem with clipping something off a polygon is that the polygon gets extra or less vertices. My structures could cope with 3 vertices, but not with 5... In this case, I could have increased the space in all the arrays to 5 vertices for each polygon, but that messed up my assembly routines, since they expected certain data to be at fixed positions in memory.
Learned lessons:
- Never use assembler in the early stages of engine development. In Pascal, it was sometimes necessary to use it nevertheless, but the latest C++ compilers really make assembler something to be used ONLY as a last optimization step.
- Never use fixed values for things like the number of vertices in a polygon. More general: Make data structures extendible.
More recent engines had other limitations: Object records couldn't cope with a hierarchical system of objects, polygon records couldn't be easily expanded to hold bump data, and so on. So I guess you might learn something from my scars...
A modern 3D engine needs quite some data, at different levels. Here's what I think you need (top-down):
1. World Structure 2. Sector (Local) Structure 3. Object Structure 4. Polygon Structure
In the ideal case, all this should be as generic as possible, to avoid too much rewriting resulting in possible demotivation and leaving of the 3D scene of a talented new coder. :) That's a bad thing.
OK, on with the details. On the top level (world structure) you should think about how you would organize a world, if you would ever build an engine that needs something like that. I mean, if you are a beginner, you will probably begin with an object renderer, just like I did. So it might be tempting to regard this object as a 'world', since there is no other data to process anyway. You might just declare an array of vertices, rotate them, and dump them to the screen. Fine. But think about this: If your array of vertices would have been stored in a larger structure, called an 'object', you would be tempted (probably) to try to get your engine to work with TWO or even more objects. Here are some things that you should take into account when you are figuring out a good world structure for you:
A world is probably too big to display or even process every frame. So you need some structure that allows partial processing. Unseen world parts and objects must preferably not be taken into account.
That means that there must be a link between the world, and the objects in it. Otherwise you would be rendering all objects, plus the visible part of the world, which could still be far too much work.
You might also want to have a more or less dynamic world. That asks for different data structures again. Here's how I would implement the top level:
class World
{
SectorList* sectors;
};
And here's what a sector looks like:
class Sector
{
PolygonList* polygons;
ObjectList* objects;
};
Most engines work like this: Even a BSP engine. This way, objects are linked directly to the world, as long as they are stored in the right sector every time they move. So the problem of object visibility is now directly linked to the world visibility problem.
The next level you should think about (or the first level, if you're only doing an object engine) is the object data structure. Here's a sample structure:
class Object
{
PolygonList* polies;
ObjectList* childs;
Matrix matrix;
};
There are some interesting things in this structure. First, I always put a pointer to a list of objects in this structure. There's a good reason for this: Many objects are linked in some way. If they are, their matrices are usually determined in an incremental way: An arm for example rotates relative to a torso, and thus it needs both it's own matrix, and the matrix of it's parent (the torso). The torso itself is probably rotated relative to the world: Therefore I also put a matrix in the Object class.
OK, one more level down, the polygon level. Here's a basic polygon class:
class Polygon
{
VertexList* vertices;
Texture* texture;
Sector* sector;
Plane plane;
};
And the vertex class:
class Vertex
{
Coordinate* position;
float U, V;
};
Finally, the coordinate class:
class Coordinate
{
Vertex original;
Vertex rotated;
boolean processed;
};
This is interesting stuff, since even beginning coders will encounter this. Let's start with the polygon class: In this case I have used a VertexList class to hold my vertices. This makes it possible to have an arbitrary number of vertices in a polygon, but there's a drawback: Each list entry also has a 'next' pointer (assuming that it is a linked list). Thus, each vertex takes 4 more bytes than you would expect. If that's not a big problem, consider this: The alternative is an array. An array is stored sequentially, and is usually better for the cache. But an array is fixed size... In Focus, I finally chose the array approach. Therefore, you MUST specify the number of vertices when instantiating the polygon. My polygon class looks like this:
class Polygon
{
Vertex** vertices;
int vertices;
Texture* texture;
Sector* sector;
Plane plane;
};
So, there is a single pointer to a block of memory that holds pointers to vertices. Note that I still use extra memory: An integer for the number of vertices (since there's no NULL pointer at the end of a list any more), and a pointer to the block of pointers.
Another thing to note in the polygon class is the sector pointer. This is used for portal polygons: Since a portal links two sectors, this is the place where you should store this information.
Finally, there is a plane structure. You could also make this a plane pointer, if you want to re-use the plane (for example, if you have a lot of polygons in the same plane). In case you don't know what to do with planes: I'll talk more about that in a later article.
Recycling is also the reason for storing a coordinate pointer in the Vertex class. A cube has eight vertices, but the six sides all have 4 vertices, making a total of 24 vertices. In the cube case, it is obvious that the 3D position of only eight vertices are unique. The texture coordinates however need not be shared by two polygon vertices at the same position. Therefore, a vertex class should contain U/V information (the texture coordinates), and a pointer to a 3D position. This saves space and processing time, since a rotated vertex doesn't have to be rotated again. This brings me to the coordinate class:
In the coordinate class there's maybe a bit more than you would expect. First, there's both an original vector and a rotated vector. You need to keep the original to ensure maximal accuracy: Even high precision floating point arithmetic will introduce numerical instability quickly when you rotate coordinates again and again. The other interesting thing is the 'processed' field: It indicates whether a vertex has been rotated for the current frame or not. This eliminates duplicate rotations.
Here's a small tip for more advanced coders: Instead of a boolean you could also use an integer. If you store the current 'frame ID' in this integer (just increase it each frame) you don't have to reset the 'processed' flag for all rotated vertices each frame. This is particularly handy when it's not so easy to determine which vertices of a huge set where rotated at the end of the drawing process.
OK, that's what I wanted to say about 3D data structures. My intention is to get you thinking about this at an early stage: The way you setup your data is probably the most important decision you make in the design of your engine. Actual tips in short are: Use pointers and lists, and as few arrays as possible. Arrays look simple at first, but they soon make your engine more complicated and force you to do ugly things that C++ was not designed for.
[edit] Coding a wireframe cube
The purpose of this article is to get you going if you really don't know where to start. I can rant about PTC and windows programming, data structures and so on, but in the end there's nothing like a good example. Well, I've just coded a very small program (54 lines of code, in fact) that just shows a wireframe cube, and that might be just what you need. Here's the code:
#include "ptc.h"
#include "math.h"
float angle, x[8], y[8], z[8], rx[8], ry[8], rz[8], scrx[8], scry[8];
void line (unsigned short* buf, float x1, float y1, float x2, float y2)
{ double hl=fabs(x2-x1), vl=fabs(y2-y1), length=(hl>vl)?hl:vl;
float deltax=(x2-x1)/(float)length, deltay=(y2-y1)/(float)length;
for (int i=0; i<(int) length; i++)
{ unsigned long x=(int)(x1+=deltax), y=(int)(y1+=deltay);
if ((x<640)&&(y<480)) *(buf+x+y*640)=65535;
}
}
void render (unsigned short* buf, float xa, float ya, float za)
{ float mat[4][4]; // Determine rotation matrix
float xdeg=xa*3.1416f/180, ydeg=ya*3.1416f/180, zdeg=za*3.1416f/180;
float sx=(float)sin(xdeg), sy=(float)sin(ydeg), sz=(float)sin(zdeg);
float cx=(float)cos(xdeg), cy=(float)cos(ydeg), cz=(float)cos(zdeg);
mat[0][0]=cx*cz+sx*sy*sz, mat[1][0]=-cx*sz+cz*sx*sy, mat[2][0]=cy*sx;
mat[0][1]=cy*sz, mat[1][1]=cy*cz, mat[2][1]=-sy;
mat[0][2]=-cz*sx+cx*sy*sz, mat[1][2]=sx*sz+cx*cz*sy, mat[2][2]=cx*cy;
for (int i=0; i<8; i++) // Rotate and apply perspective
{ rx[i]=x[i]*mat[0][0]+y[i]*mat[1][0]+z[i]*mat[2][0];
ry[i]=x[i]*mat[0][1]+y[i]*mat[1][1]+z[i]*mat[2][1];
rz[i]=x[i]*mat[0][2]+y[i]*mat[1][2]+z[i]*mat[2][2]+300;
scrx[i]=(rx[i]*500)/rz[i]+320, scry[i]=(ry[i]*500)/rz[i]+240;
}
for (i=0; i<4; i++) // Actual drawing
{ line (buf, scrx[i], scry[i], scrx[i+4], scry[i+4]);
line (buf, scrx[i], scry[i], scrx[(i+1)%4], scry[(i+1)%4]);
line (buf, scrx[i+4], scry[i+4], scrx[((i+1)%4)+4], scry[((i+1)%4)+4]);
}
}
int APIENTRY WinMain (HINSTANCE hInst, HINSTANCE hPrevInst, LPSTR lpCmdLine, int nCmdShow)
{ for (int i=0; i<8; i++) // Define the cube
{ x[i]=(float)(50-100*(((i+1)/2)%2));
y[i]=(float)(50-100*((i/2)%2)), z[i]=(float)(50-100*((i/4)%2));
}
Console console; // Initialize PTC and start rendering
Format format (16, 31<<11, 63<<5, 31);
console.open ("3D", 640, 480, format);
Surface surface (640, 480, format);
while (!console.key ())
{ unsigned short* buf=(unsigned short*) surface.lock ();
memset (buf, 0, 640*480*2);
render (buf, angle, 360-angle, 0);
angle+=0.2f; if (angle==360) angle=0;
surface.unlock();
surface.copy (console);
console.update();
}
return 0;
}
Please take a moment to get this stuff running. Using VC5 or 6, create a new Win32 application with no files in it. Add the PTC lib file to the project (using add files) and the ptc.h header file, and of course the source that I just showed. Next you have to disable the inclusion of two default libraries (under the 'linker input settings'), LIBC and LIBCD. Now the program should compile just fine. You might try to make it slightly more readable by splitting lines that do multiple variable initializations on a single line. :)
So what does this program do? Let's start with the program entry, which is in this case the WinMain function. The first thing that happens here is the definition of a cube. A cube has eight vertices, which could be initialized as follows:
1. x: -50 y: -50 z: -50
2. x: 50 y: -50 z: -50
3. x: 50 y: 50 z: -50
4. x: -50 y: 50 z: -50
5. x: -50 y: -50 z: 50
6. x: 50 y: -50 z: 50
7. x: 50 y: 50 z: 50
8. x: -50 y: 50 z: 50
The weird construction with the modulo operators does just that (only shorter:). If you take a moment to visualize this data, you'll see that these are 8 vertices centered around (0, 0, 0), which is handy, because rotations are easy around the origin of 3D space.
After that, we need to set up PTC. I used a 16 bit display in this case, at a resolution of 640x480 pixels. This video mode should work on most computers.
In the main loop the function 'render' is called, with a pointer to the PTC buffer and the rotation around the three axes as input. Note that the rotations are passed in degrees.
The 'render' function is slightly more interesting. Let's see what it needs to do: Ultimately it should draw lines between the rotated vertices, and those lines should be somewhere near the centre of the screen. Rotations are done using a matrix. If you forgot how that worked, browse back to the article that discusses them. As you know, a rotation around three axes can be performed by calculating the matrix for the rotation around each axis, and them concatenating them. In this case, I have done the concatenation for you: The matrix 'mat' is filled with sins and cosines at once. I encourage you to alter the code so that the final matrix is calculated by concatenating the separate matrices, so that you can also rotate around the axes in a different order.
The rotated vertices are still centred at the origin. Since perspective calculations do a nice divide by the z coordinate, we need to move the object away from the camera. This is done by adding 300 to the rotated z. Note that you could also add something to x and y: This is how you rotate an object around something else than the origin. In this case, the object is effectively rotated around (0, 0, 300).
Finally, the perspective is calculated. Note that the object is also centred on screen, by adding 320 to the screen-x coordinate, and 240 to the screen-y coordinate.
Now the lines can be drawn to the screen. The line function that I included is very short, and that's the only thing that is good about it. If you need fast code, ditch this function, and include your own assembler bresenham code. Some comments about this code:
It first determines how many pixels need to be drawn. If the line has a higher vertical than horizontal range, it draws abs(y2-y1) pixels, otherwise abs(x2-x1). This prevents gaps.
When drawing pixels, each subsequent screen location can be calculated by adding something to the first x-coordinate (x1) and to the first y-coordinate (y2). This 'something' is actually the x or y range, divided by the total number of pixels to be drawn. When you think about it, it's logical that you reach (x2,y2) after adding 'n' times a bit to x and y, where 'n' is the calculated number of pixels. Also note that either 'delta-x' or 'delta-y' is exactly 1.
If you want to play a bit around with this code, then here are some suggestions:
- Editor's Note: Feel free to submit any modified versions of this program that you make, and I'll probably post it here with your name.
Alter the line drawing code so that it accepts other colours. Currently the colour is always 65535, which is pure white in a 16 bit colour mode. This colour consists of red, green and blue: Red is 5 bits, green 6, and blue 5. The final colour is calculated with the following formula: red*2048+green*32+blue. Note that red should be an integer between 0 and 31, and so is blue. Green is an integer between 0 and 63.
Play a little with the position of the object. It can also be partially off-screen, the line drawing code doesn't crash.
Try to create something else than a cube. Using this code you could design your own name in glorious 3D.
Extend the data structures so that the connections between vertices are no longer hard coded. You could for example define edges, which should hold a start and an end vertex. Then the rendering code should draw all the edges, which should make the code much nicer if you have a lot of edges. You could also introduce 'polygons', which hold more than two vertices.
Add a cube, and use the stuff from the matrices document to make the second cube spin around the first. To get this right, construct the second cube around (100,0,0), so that the rotation causes it to 'swing' around the first cube.
