Mathematics for 3D Game Programming and Computer Graphics

Eric Lengyel

Mentioned 8

Covers mathematical concepts that are needed to develop 3D game programming and graphics.

More on Amazon.com

Mentioned in questions and answers.

How do games with gravity handle the relationship between moving things like players, monsters, or objects and the floor? Is the player constantly "falling into" the floor and being bounced back up?

Two ways to react to collisions that I have found are moving the player back to his previous location before the collision, and testing the new position before moving to see if it would result in a collision, but I don't see how either of these could deal with a platform that is rising upwards and needs to be able to lift the player. I'm looking at this from a 2D game design perspective, but I imagine that the same problem occurs in 3D game design. Any hints? Any references that I should check out? Thanks.

One of the most complete textbooks on this subject is Realtime Collision Detection by Christer Ericson. He has a companion blog too. Eric Lengyel's Mathematics for 3D Game Programming and Computer Graphics is useful too.

Does anyone have any idea how it would be possible to transition from business to game programming? How would anyone get a start in game programming? It seems much more exciting and rewarding (better paying too?). But it seems like most of the jobs out of school are for business programming. Any advice or insight on how to do it or if it can be done?

It's quite a transition! The biggest difference in mindset is moving away from the business world's reliance on abstraction to one where you're focused much more on the particular hardware you're targeting and getting things to run within strict budgets of time and memory. Game programming is a lot more like embedded programming than it is like web programming -- you have to think about the exact memory footprint of everything and CPU time is at a huge premium.

This is even true of being an MMO server programmer, because a) the server has to answer to each client command within 80 milliseconds to feel responsive, and b) the bigger the footprint of the game on the server, the more hardware you have to buy, and that costs real money.

First up you should learn C++ if you haven't already. Almost every game is written in C or C++ these days. Game consoles have strictly limited memory, and if you allocate one byte past 512mb it doesn't slow down, it crashes; at the same time, each trip through the main app loop has to complete in 33ms or less, so we can't rely on garbage collection and smart pointers. The game-development world is one of those special applications where you really need to do all those optimizations that people here say you never need to do any more.

Also, bone up on your math. Games are built out of linear algebra and kinematics -- not just the graphics, but the state of the world and the behavior of every character and object. I like Eric Lengyel's book for game math; it's been my bible for years (though there are many other good ones).

You could try to learn some graphics math and programming as well, but this is sort of a subspecialty now and typically only a couple of people on a game team are really working at the level of DirectX calls. I suspect you're more interested in game logic and server backend, which is less specialized.

Make games. There are many frameworks to help you get started. XNA has the advantage of being a real-world product that actual games are shipped with, unlike PyGame or SDL which are quick to get up and running but have vanishingly little commercial support.

I want to ask what is the easiest way to make shadow and light volume ? How can I bring to scene more realism? Do you know any nice tricks ? I hear that to make shadow i must use stencil buffer, but I don't know how:/ I can't find any super simple example how to make it.

There's no super simple way to do shadows. Sorry to disappoint you but shadows are one of the more complex problems in computer graphics, especially if they have to look good.

Now with that said here are some maybe helpful links for further reading:

There's a simple example of shadow mapping in the NVIDIA SDK 9 here (Paper) which might be easy to adopt. There's also a section on shadows in all volumes of GPU Gems and a good overview in the Real-Time Rendering book (without code).

In addition to the other useful sources mentioned here, you should consider getting an introductory text on linear algebra, or Eric Lengyel's excellent Mathematics for 3D Game Programming and Computer Graphics, Second Edition. Computer graphics are made of math, and at some level it gets really hard to implement things out of a cookbook without some understanding of the underlying algebra.

I've noticed that a number of top universities are offering courses where students are taught subjects relating to Computer Graphics for their CS majors. Sadly this is something not offered by my university and something I would really like to get into sometime in the next couple of years.

A couple of the projects I've found from some universities are great, although I'm mostly interested in two things:

  • Raytracing:
    • I want to write a Raytracer within the next two years. What do I need to know? I'm not a fantastic programmer yet (Java, C and Prolog are my main languages as of today) but I'm slowly learning every day. Also, my Math background isn't all that great, so any pointers on books to read or advice on writing such a program would be fantastic. I tend to pick these things up pretty quickly so feel free to chuck references at me.
  • Programming 3D Rendered Models
    • I've looked at a couple of projects where students have developed models and used them in games. I've made a couple of 2D games with raster images but have never worked with 3D models. What would I need to learn in regards to programming these models? If it helps I used to be okay with 3D Studio Max and Cinema4D (although every single course seems to use Maya), but haven't touched it in about four years.

Sorry for posting such vague and, let's be honest, stupid questions. It's just something I've wanted to do for a while and something that'd be good as a large project for me to develop in my own time.

Related Questions

The book "Computer Graphics: Principles and Practice" (known in the Computer Graphics circles as the "Foley-VanDam") is the basic for most computer graphics courses, and it covers the topic of implementing a ray-tracer in much detail. It is quite dated, but it's still the best, afaik, and the basic principles remain the same.

I also second the recommendation for Eric Lengyel's Mathematics for 3D Game Programming and Computer Graphics. It's not as thorough, but it's a wonderful review of the math basics you need for 3D programming, it has very useful summaries at the end of each chapter, and it's written in an approachable, not too scary way.

In addition, you'll probably want some OpenGL or DirectX basics. It's easier to start working with a 3D API, then learn the underlying maths than the opposite (in my opinion), but both options are possible. Just look for OpenGL on SO and you should find a couple of good references as well.

I'm looking for sites with examples and tutorials for OpenGL. The OpenGL SuperBible seemed to be a must-have so I just got it and it seems a bit too complicated for me at the moment due to my lack of math knowledge. Therefore, I have decided to start out with simple 2D-games which shouldn't be that hard. The tutorials and examples need to be up-to-date which seems hard to find. I'd love a very simple 2D game example like Pong or similar that I could build upon.

Also: what math is necessary for 3D-programming? Would it be possible for me to learn most of it by myself (I'm 15 years old) or do I have to wait for college/late high school?

I would recommend having a look at Joe's Blog as well.

For math, have a look at this book.

As mentioned in other posts, NeHe is great. It is getting a bit old though. Lighthouse 3D is pretty helpful as well. For the most up-to-date references, just go straight to OpenGL. It's a great resource. Real-Time Rendering is a great book for computer graphics. The website has tons of resources as well.

Regarding the math that you should know, linear algebra is a must in computer graphics. Many computer graphics books will provide an overview of the math that you should be familiar with. The book I mentioned above (Real-Time Rendering) provides a great overview. Another decent book relating to the math required for computer graphics is Fundamentals of Computer Graphics. There may be better books out there in terms of the math overview that you're looking for, but I've found these two to be helpful. Be aware, though, that neither of these books will have a lot of examples; they cover some of the more theoretical aspects of computer graphics.

I have been trying to find some well presented and explained Vector and Quaternion resources recently to brush up on my 3D skills, and have been having some trouble.

Most of the resources I have found tend skip over the high-level reason that performing a particular operation is useful, and dives straight into jargon and proofs that tends to loose my attention rather quickly.

I have found that better explained has really good explanations of various math topics, however doesn't have anything for Vectors or quaternions.

Does anyone know of any high level Vector and/or Quaternion tutorials?

Get 3D Math Primer for Graphics and Game Development. It's not a free online tutorial, but I seriously doubt you could find any online tutorial that covers 3D math in such detail while still being very accessible and beginner-friendly. It's got the best coverage of quaternions that I've come across, and it also introduces all the mathematical formulas with a geometric interpretation so that you know how they relate to computer graphics.

Other than that, here's a good basic Vector Math Tutorial. For Quaternions there's the Wikipedia article and some other resources you could find with google, but they all seem too brief or tied to a certain technology. Again, just buy that book (or alternatively this one which covers more topics but spends less time on the basics).

I would like to know How to create a fps-game with SDL lib?

Are there any books that explain with examples?

this wins for most open ended question. You could literally write a book. But lets settle for pointing in the right direction...

Step one, you will need good debugging skills for a project like this. Pick up Code Complete by Steve McConnell. Read the whole thing. The time invested will pay for itself more than anything else you could read/experiment with.

Get your hands on some source code of some game. ANY game. Make sure you see something simple before you see something big and complex, and keep in mind when you look at any game code that they may have had a combined team put WAY more time into it than you will ever have. The point in this is to see code structure.

Get a reference for 3D math, doesn't have to be THAT in depth, but you will need to know stuff like dot products backwards and forwards, be able to figure out how to create the matrix for your camera in the world etc. (even if your writing 0% of the rendering code)

(edit) Here's a great book on 3D mathMathematics for 3D Game Programming and Computer Graphics, Second Edition (Game Development Series) This isn't the kind you learn in college, it's more like a cross between trig and more advanced practical concepts: How to create a toolbox for yourself of simple physics, efficient collision detection, etc.

You will need to know something about rendering, and pipelines. SDL gives you a leg up, but make sure you understand the concepts of what it's doing.

Read up about practical system design. Your various systems will have to interlock. Think it out well. Your system can be just a good in C or in C++, it's the THOUGHT that is put into how your data/control will flow that will count, NOT how perfectly you emulate design patterns (though these are very useful as well of coarse)

Fundamentals of AI, not "real" AI, but functional AI; there is a big difference. State machines are great to start with, and sufficient for a simple FPS.

Learn a little about estimation and planning. You will not have time to do everything you would want to do to properly make an FPS. You will have to both triage AND learn how to triage; they are 2 separate things, the latter being mroe difficult. Experience is the best teacher here of coarse. (though the legendary McConnell has book on this as well)

Have a system to insert your gameplay into your level. If it is JUST you as a programmer, then your best bet is to write a plug in for an already existing editing program such as 3DS Max. I would highly recommend Max over Maya for a programmer. Maya script is nice, but it is more geared toward clever non-programmers. I find 3DS Max to think more along the lines of how a programmer would about creating and editing your world.

You can spend YEARS making tools to let you do this right, so you want to do things in such a way that you can edit fast and accurately If you making your own editor, incorporate it into your game world. If your world is not TRULY 3D and you want to make lots of level fast you can save your level data as something like this, which will save you a lot of time Where X is a wall, the other letters are game objects which a dirt simple parser can translate into game objects and world coordinates

 xxxxxxxxxxxxxxxxxxxxxxxx
 xx..........P..........x
 xxxxxxx...........I....x
 xR....xxx...........E..x
 xx.................0xxxx
 xxxxxxxxxxxxxxxxxxxxxxxx

But it all depends on your game. My point is that you will need to resort to "ghetto coding" how you get your gameplay data into your world is very important and you need to think of something that is both fast for you to implement AND fast with you to work with.

And what it comes down to is what is your goal here? If it's to learn to code something the absolute right way, expect to spend most of your time iterating on code that seemed decent a month ago, but now that you realize what your requirements are, it could really use another pass. Do not be afraid to rewrite, you learn a lot by doing that, but if you goal is functionality, you will probably need to figure out where to hack some things in (like embedding gameplay data nad coordinates into code files) It IS ok to hack as long as you KNOW where you have hacked, and have carefully kept it separate from your good code so you can go back and properly write the code when you get the chance.

The bottom line is, you need to decide what your goal in this is, learning, or functionality and find the happy medium between.

Like the masochistic I am, I'm trying to learn all the matrix math behind creating modelview and perspective matrices so that I can write my own functions for generating them without the use of JS libraries.

I understand the concept of the matrices, but not how to actually generate them. I've been looking very closely at the glMatrix library, and I have the following questions:

1) What is going on in the following mat4.perspecive method?

/**
 * Generates a perspective projection matrix with the given bounds
 *
 * @param {mat4} out mat4 frustum matrix will be written into
 * @param {number} fovy Vertical field of view in radians
 * @param {number} aspect Aspect ratio. typically viewport width/height
 * @param {number} near Near bound of the frustum
 * @param {number} far Far bound of the frustum
 * @returns {mat4} out
 */
mat4.perspective = function (out, fovy, aspect, near, far) {
    var f = 1.0 / Math.tan(fovy / 2),
        nf = 1 / (near - far);
    out[0] = f / aspect;
    out[1] = 0;
    out[2] = 0;
    out[3] = 0;
    out[4] = 0;
    out[5] = f;
    out[6] = 0;
    out[7] = 0;
    out[8] = 0;
    out[9] = 0;
    out[10] = (far + near) * nf;
    out[11] = -1;
    out[12] = 0;
    out[13] = 0;
    out[14] = (2 * far * near) * nf;
    out[15] = 0;
    return out;
};

Specifically, I get what Math.tan(fovy / 2) is calculating, but why take the inverse of it? Likewise, why take the inverse of the difference between the near boundary and the far boundary? Also, why is out[11] set to -1 and what is the value stored in out[14] for?

2) The following mat4.lookAt method in the library is also confusing me:

/**
 * Generates a look-at matrix with the given eye position, focal point, 
 * and up axis
 *
 * @param {mat4} out mat4 frustum matrix will be written into
 * @param {vec3} eye Position of the viewer
 * @param {vec3} center Point the viewer is looking at
 * @param {vec3} up vec3 pointing up
 * @returns {mat4} out
 */
mat4.lookAt = function (out, eye, center, up) {
    var x0, x1, x2, y0, y1, y2, z0, z1, z2, len,
        eyex = eye[0],
        eyey = eye[1],
        eyez = eye[2],
        upx = up[0],
        upy = up[1],
        upz = up[2],
        centerx = center[0],
        centery = center[1],
        centerz = center[2];

    if (Math.abs(eyex - centerx) < GLMAT_EPSILON &&
        Math.abs(eyey - centery) < GLMAT_EPSILON &&
        Math.abs(eyez - centerz) < GLMAT_EPSILON) {
        return mat4.identity(out);
    }

    z0 = eyex - centerx;
    z1 = eyey - centery;
    z2 = eyez - centerz;

    len = 1 / Math.sqrt(z0 * z0 + z1 * z1 + z2 * z2);
    z0 *= len;
    z1 *= len;
    z2 *= len;

    x0 = upy * z2 - upz * z1;
    x1 = upz * z0 - upx * z2;
    x2 = upx * z1 - upy * z0;
    len = Math.sqrt(x0 * x0 + x1 * x1 + x2 * x2);
    if (!len) {
        x0 = 0;
        x1 = 0;
        x2 = 0;
    } else {
        len = 1 / len;
        x0 *= len;
        x1 *= len;
        x2 *= len;
    }

    y0 = z1 * x2 - z2 * x1;
    y1 = z2 * x0 - z0 * x2;
    y2 = z0 * x1 - z1 * x0;

    len = Math.sqrt(y0 * y0 + y1 * y1 + y2 * y2);
    if (!len) {
        y0 = 0;
        y1 = 0;
        y2 = 0;
    } else {
        len = 1 / len;
        y0 *= len;
        y1 *= len;
        y2 *= len;
    }

    out[0] = x0;
    out[1] = y0;
    out[2] = z0;
    out[3] = 0;
    out[4] = x1;
    out[5] = y1;
    out[6] = z1;
    out[7] = 0;
    out[8] = x2;
    out[9] = y2;
    out[10] = z2;
    out[11] = 0;
    out[12] = -(x0 * eyex + x1 * eyey + x2 * eyez);
    out[13] = -(y0 * eyex + y1 * eyey + y2 * eyez);
    out[14] = -(z0 * eyex + z1 * eyey + z2 * eyez);
    out[15] = 1;

    return out;
};

Similar to the mat4.perspecive method, why is the inverse of the length of the vector being calculated? Also, why is that value then multiplied by the z0, z1 and z2 values? The same thing is being done for the x0-x2 variables and the y0-y2 variables. Why? Lastly, what is the meaning of the values set for out[12]-out[14]?

3) Lastly, I have a few questions about the mat4.translate method. Specifically, I bought the book Professional WebGL Programming: Developing 3D Graphics for the Web, and it says that the following 4x4 matrix is used to translate a vertex:

1 0 0 x
0 1 0 y
0 0 1 z
0 0 0 1 

However, when I look at the following mat4.translate method in the glMatrix library, I see that out[12]-out[15] are set via some complex equations. Why are these values set at all?

/**
 * Translate a mat4 by the given vector
 *
 * @param {mat4} out the receiving matrix
 * @param {mat4} a the matrix to translate
 * @param {vec3} v vector to translate by
 * @returns {mat4} out
 */
mat4.translate = function (out, a, v) {
    var x = v[0], y = v[1], z = v[2],
        a00, a01, a02, a03,
        a10, a11, a12, a13,
        a20, a21, a22, a23;

    if (a === out) {
        out[12] = a[0] * x + a[4] * y + a[8] * z + a[12];
        out[13] = a[1] * x + a[5] * y + a[9] * z + a[13];
        out[14] = a[2] * x + a[6] * y + a[10] * z + a[14];
        out[15] = a[3] * x + a[7] * y + a[11] * z + a[15];
    } else {
        a00 = a[0]; a01 = a[1]; a02 = a[2]; a03 = a[3];
        a10 = a[4]; a11 = a[5]; a12 = a[6]; a13 = a[7];
        a20 = a[8]; a21 = a[9]; a22 = a[10]; a23 = a[11];

        out[0] = a00; out[1] = a01; out[2] = a02; out[3] = a03;
        out[4] = a10; out[5] = a11; out[6] = a12; out[7] = a13;
        out[8] = a20; out[9] = a21; out[10] = a22; out[11] = a23;

        out[12] = a00 * x + a10 * y + a20 * z + a[12];
        out[13] = a01 * x + a11 * y + a21 * z + a[13];
        out[14] = a02 * x + a12 * y + a22 * z + a[14];
        out[15] = a03 * x + a13 * y + a23 * z + a[15];
    }

    return out;
};

Thank you all for your time, and sorry for all the questions. I come from a JS background, not an OpenGL/3D programming background, so it's hard for me to understand the math behind all the matrices.

If there are any great resources out there that explain the math used for these equations/methods, then that would be great too. Thanks.

Specifically, I get what Math.tan(fovy / 2) is calculating, but why take the inverse of it?

Because the focal distance d comes from the formula

Math.tan(fovy / 2) = y / d

to get the focal length you need to multiply by

1 / Math.tan(fovy / 2)

why take the inverse of the difference between the near boundary and the far boundary? Also, why is out[11] set to -1 and what is the value stored in out[14] for?

You can project (x,y,z) into (x*d/z, y*d/z) using the focal distance d. This is enough but OpenGL requires a linear transformation to (x,y,z) such as the projection gives coordinates in [-1,1]. Such normalized coordinates simplify clipping and retain the z information used to remove hidden surfaces.

out[11] is set to -1 because there's no linear transformation that gives normalized coordinates unless a reflection is applied. This -1 causes the handedness of the system to be switched with normalized coordinates.

out[14] is used with out[10] to transform z from [-n -f] to [-1 1] after projection.

Similar to the mat4.perspecive method, why is the inverse of the length of the vector being calculated? Also, why is that value then multiplied by the z0, z1 and z2 values? The same thing is being done for the x0-x2 variables and the y0-y2 variables. Why?

To normalize the vectors x, y and z

what is the meaning of the values set for out[12]-out[14]?

A camera is composed of a base of vectors and a position. out[12]-out[14] apply an inverse translation to set the camera position.

However, when I look at the following mat4.translate method in the glMatrix library, I see that out[12]-out[15] are set via some complex equations. Why are these values set at all?

The equations look complex because it's a product of a translation matrix and an existing matrix a.

Professional WebGL Programming: Developing 3D Graphics for the Web

I don't know this book, it might explain some math but if you need detailed explanation you should consider Eric Lengyel's book that explains and derivates the important math used in 3d raster graphics.