Video Game Design/Programming/Framework/2D vs 3D/3D Engine

3D Engine edit

If the game requires a 3D environment, it signifies that it will use a 3D view that is characterized by the use of polygon based graphics. Polygons are flat shapes and in a low count (low resolution polygon scenes) graphics are often angular.

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 can not do more that attempt to improve upon past work.

This section will attempt to describe the components in the architecture of a 3D Engine. A 3D Engine encompasses a lot of concepts. We will do our best to cover other systems that use 3D engines (such as programs like auto cad, blender, medical programs, etc) but we will focus in specific in 3D engines for games.

Game engines are a very broad complex topic. They have their own architectures and approaches directed toward the features that are necessary to be in a particular game or game type. The way one engine works is not necessarily how all engines work, or even most, that is to say each is a unique creation.

The 3D nature of the world will require that most of the concept art after approval to be scanned and modeled onto planes in a 3D modeling application such as Maya or 3DsMax.

Some popular 3D graphics engines: Crystal Space, Irrlicht, Ogre3D

Examples of 3D modeling and animation: AutoDesk(formerly Alias) Maya, 3dbuzz, AutoDesk 3dsMax, Blender, TrueSpace (now free)


 

To do:
This section was adopted from an orphan transwiki, most of the logic and content of the presentation can be salvage, extended and completed, but the more pressing matter is in rewording it into a presentable state.


Renderer edit

Fix Frame Type edit

 

To do:
Point and click adventures, some 3D platformers, and with extension in spatial effects or side scrolling other types of less visual complex games


Fix Track Type edit

 

To do:
Racing, sports, some 3D platformers, vertical and horizontal 3D scrollers


Area Type edit

Portals edit

Basically, a portal based engine permits the 'spatially indexing' of large datasets that usually make up the virtual world: in other words, it can be a simple technique to avoid having to display all that data in every frame and instead only draw what is relevant even permitting to save fast memory requirements.

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

Open world edit

Space edit
Planetary edit

Your own 3D Engine edit

Sometimes the available offering of 3D engines will not match your game's requirements, the features or licensing. 3D game engines are huge software projects. A single person can indeed write one, but it is not an overnight process. It will probably result in having more than a few megabytes of source code. If one is not to committed to finish it, the attempt will fail and even put the whole game project at risk.

Before start coding the engine some effort is required in planing, just like the game itself, so to determine what will one do with engine or what can be implemented. Most often, the creation 3D engines arises from the requirements of specific games, but they can be seen a product in themselves. Do not expect to write a full engine at the first try, if one must be built and there is a lack of time or knowledge, get the right people to do it or direct the effort toward a smaller game project that has an equal small requirements list for the engine.

Do not just jump in and start coding an engine, as errors will be made and create the need to re-write huge portions of the engine multiple times to add effects and control later. A little forethought into engine design will save headaches and time.

The list of features in a 3D engine can include curved surfaces, dynamic lighting, volumetric fog, mirrors and portals, skyboxes, vertex shaders, particle systems, static mesh models and animated mesh models. If one has a good idea of how all these things work, and the technical capability to implement them, one may probably start putting them together into an his own engine.

In this section we will discusses the elements normally present in a 3D engine. These essentially includes the tools, console, systems, renderer, engine core, game interface and the game itself.

Let's take a look at the basic components, using example of a possible structural division of a full-featured 3D game engine. This is especially directed for those that are reasonably experienced with 3D, but need an overview of how much work and how many parts go into a game engine.

Tools/Data edit

During development, handling specific data will be needed, and unfortunately it is not going to be as easy as writing some text files that define a cube. At least there will be a need to handle data generated by 3d model editors, level editors, and graphics programs.

The tools to create the raw data can be bought or are even available for free. Unfortunately there will be a need for domain specific edits and data handling that are specific to your game, tools than may not exist yet and so they will need to be created.

This can be a level editor, if one is not available that does the things required. One will probably also need to write some code to pack files into an archive since dealing with and distributing hundreds or thousands of files can be a pain. There will also be a need to write converters or plug-ins from various 3d model editors format into your own format, as all the needed tools to process game data, such as visibility computations or lightmaps.

The basic line is that you'll probably have nearly as much or more code in tools than actual game code. You can find formats and tools that you can use, but sooner or later you'll realize you need some things that are very custom to your engine and you'll end up writing your own anyway.

Although there is a probably a big rush to get tools done just so there are usable, do take care in your coding. Someone may actually try to use, extend or modify your tools one day, especially if you make your engine to be opensource or modifiable.

You should probably be prepared to spend as much time making graphics, levels, sound, music and models as you did writing the game, tools, and engine.

System edit

System is the part of the engine that communicates with the machine itself. If an engine is written very well the system is the only part that should need major modifications if porting to a different platform. Within the system are several sub-systems. Graphics, Input, Sound, Timer, Configuration. The System is responsible for initializing, updating, and shutting down all these sub-systems.

The Graphics Sub-System is pretty straightforward. If it deals with putting things on the screen, it goes here. One would most likely write this component using OpenGL, Direct3D, Glide, or software rendering. To get even fancier, you could implement multiple API interfaces and put a Graphics Layer on top of them to give users more choice and more chance for compatibility and performance. This is a bit difficult though, especially since not all API's will have the same feature sets.

The Input Sub-System should take all input (Keyboard, Mouse, Gamepad and Joystick) and unify it and allow for abstraction of control. For example, somewhere in the game logic, there will be a need to see if the user wants to move his or her position forward. Rather than doing multiple checks for each type of input, one would make one call to the input sub-system and it would transparently check all devices. This also allows for ease of configuration by the user, and easily having multiple inputs perform the same action.

The sound system is responsible for loading and playing sounds. Pretty straight forward, but most current games support 3D sound and this will make things a little more complex.

Pretty much everything in a 3d game engine (I'm assuming real-time games here...) is based on time. Hence you need some time management routines in the Timer sub-system. This is actually pretty simple, but since anything that moves will move with time, a decent set of routines will keep you from writing the same code over and over.

The Configuration unit actually sits above all the other sub-systems. It's responsible for reading configuration files, command line parameters, or whatever setup method is used. The other sub-systems query this system when they are initializing and running. This makes it easy to change resolution, color depth, key bindings, sound support options, or even the game that gets loaded. Making your engine very configurable just makes it easier to test and allows users to set things up the way they like.

Graphics output under Windows edit

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

3D Matrix editing edit

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 identity 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 its 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 voilà! 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 its 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.

Support edit

This is a system that is used by pretty much every other system in the engine. This includes all your mathematics routines, (vectors, planes, matrix, etc), memory managers, file loaders, containers (or use STL if you don't roll your own). This stuff is pretty basic and will probably be used in most any project you ever are involved in.

Renderer/Engine Core edit

Ah yes, everyone loves rendering 3D graphics. Because there are so many different methods of rendering 3D worlds, it's nearly impossible to give a description of a graphics pipeline that works in all situations.

Regardless of how you implement your renderer, the most important thing is to make your renderer component based and clean. Make sure you have distinct modules for different things. The sub-sections that I break the renderer into are sections like Visibility, Collision Detection and Response, Camera, Static Geometry, Dynamic Geometry, Particle Systems, Billboarding, Meshes, Skybox, Lighting, Fogging, Vertex Shading, and Output.

Each one of these sections needs to have an interface that easily allows for changes in settings, position, orientation, or any other setting that may be associated with the system.

One major pitfall to look out for is feature bloat. Decide what you are going to implement at the design stage. If you don't adding new features will start to get hard to do and the solutions will be kludgy.

One thing that is nice and convenient is to have all triangles (or faces) ultimately pass through the same point in the render pipeline. (Not a triangle at a time, I'm talking about triangle lists, fans, strips, etc.) It takes a bit more work to get everything into a format that can be passed through the same lighting, fogging, and shading code but in the end you'll be happy that any effect that you can do to one polygon can be done to any polygon in your game simply by changing its material/texture id.

It doesn't hurt to have multiple points from which things are drawn, but it can lead to redundant code if you're not careful.

You'll eventually find out that all those cool effects that you wanted to implement will be 15% or less of the total code you end up writing. That's right, most of a game engine is not graphics.

Data structures for 3D Graphics edit

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 its own matrix, and the matrix of its 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.

Example of coding a wireframe cube edit

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.

Light edit

Fog edit

Liquids edit

Simulating water or other liquids can be extremely hard if realism is intended. Water details changes in regards to how near the observer is, if may have foam, transparency, distortion and specularity. Water surfaces tend to be reflective, random and extremely complex to mimic when the player can interact with it or the physics are changeable, for instance replicating the splash of debris or alterations to the environment that contains the liquid.

Console edit

Ok, I know everyone likes to follow the crowd and have a console like Quake. But it's really a good idea. With console variables and functions you can change settings in your game and your engine without restarting it. It's wonderful for outputting debug information while developing. Oftentimes you'll be needing to examine some variables and outputting the to the console is faster and sometimes better than running a debugger. Once your engine is running, if an error occurs, you don't have to quit the application; you can handle it gracefully and just print an error message. If you don't want your end user to see or use the console, its easy to disable it and no one is the wiser that it's still there.

Game Interface edit

The most important part of a 3D game engine is that it is a game engine. It is not a game. The actual game should never have components that are put into the game engine. Having a thin layer between the engine and the game makes for cleaner code and ease of use. It's a little extra code, but it also makes a game engine very reusable and it becomes much easier to use a scripting language for game logic, or put the game code in a library. If you embed any of your game logic in the engine itself, don't plan on reusing it later without lots of problems and modifications.

So you are probably wondering what this layer between the engine and game provides. The answer is control. For each part of the engine that has any dynamic properties, the engine/game layer provides an interface to modify it. Some things in this category include the camera, model properties, lights, particle system physics, playing sounds, playing music, handling input, changing levels, collision detection and response, and placement of 2D graphics for a heads up display, title screen or whatever. Basically if you want your game to be able to do it, there must be an interface into the engine to do it.