News
About
Tutorials
  Linear Algebra
3D Maths
3Dfx
Curves
Win32
DirectX
OpenGL
Articles
  Voxel Worlds
Files
Tom H
Links
3D MATHS
by Iain Hutchison

Contents

Introduction

The purpose of this article is to impart the basic maths that is required for 3D graphics programming. It does not teach you matrix and vector mathematics. You'll need to learn these yourself. This article just tells you how to use matrices and vectors (amongst other things) to do 3D calculations. If you don't know matrices and vectors then I suggest you stop reading now and go read a good book on Linear Algebra.

Notation

All of the vector and matrix algebra that I'm going to be using is done using homogenous coordinates. These are the same as your normal 3D coordinates except that they have an extra coordinate W (giving X,Y,Z,W) that is always 1 (I know it sounds strange but you'll just have to bear with me for now, all will become clear later on). Similarly, vectors are of the form ai + bj + ck + 0h. That's right, the last coefficient is always 0. You may wonder why I bother with it but if you're going to have 4D coordinates then you need to have 4D vectors. Simple.

As a general rule, vectors are denoted using bold underlined lower-case letters (e.g. v, w, vi). Points in space are denoted by bold lower-case letters (e.g. p, q, rj). Points on diagrams tend to be labeled with upper-case letters (just to be awkward). I'll try to stick to this but any time that I break away from this I will say so (and probably explain why). All vectors are assumed to be column vectors. Matrices will be denoted by italicised capitals.

Transformations

For now I'm just going to talk about rigid body transformations and within them only linear transformations will be considered, ie those that satisfy :
P -> LP + c

where LT L = I

The matrix L is a 4x4 matrix that determines what happens to a point when it is transformed.

Rotations

There's no real need to go into how the following matrices are derived so I'll just go right ahead and state them. They assume a right-handed set of coordinate axes.

ROTX = [FIG1]
 
ROTY = [FIG2]
 
ROTZ = [FIG3]

Scaling

Scaling is really simple - you just multiply the x coords by the x scale-factor, the y coords by the y scale-factor and the z coords by the z scale-factor. In matrix form this is :

[FIG4]

Translating

Translating is really simple - you just add the x delta to the x coord, the y delta to the y coord and the z delta to the z coord. In matrix form this is :

[FIG5]

Perspective

This is where things get a little difficult to explain clearly. The best way is to use plenty of diagrams (don't worry, the image files are all pretty small :-). Here's the main one that shows the basic derivation of the equations and what each letter actually represents :

[FIG6]

Now, putting this into matrix form is what requires the use of homogeneous coordinates. Here's the matrix :

[FIG7]

Now here's what happens if you use it on a point x (with P as the perspective matrix given above) :

[FIG8]

The first result vector is what you get if you just do the multiplication. However, the result needs to be re-homogenised so that the 4th coordinate is 1. To do this we divide all coordinates by the 4th one. This gives the right-hand result which holds exactly the same equations as the original diagram. Now isn't that nice?

View Frustrums

A view frustrum is a semi-infinite pyramid, although the base is usually rectangular rather than square because the screen isn't square. In practice, however, it is normal to chop off the frustrum near the point and somewhere further down towards the base. The view frustrum defines what parts of the 3D world can be seen from the camera position when looking through a window (usually the screen). Here's a little piccie to help clarify things a bit (I hope) :

[FIG9]

You can define a frustrum using the view rectangle, the camera origin and the near- and far-plane distances from the camera origin. This information can then be used to make the top, bottom, left, right, near and far planes. All the planes have their normals facing into the frustrum (by convention, doesn't matter so long as they either all point inwards or all point outwards).

Once you have these 6 planes it is easy to determine whether any given point is inside the frustrum or not - you just make sure it is above every plane. You just test it against each plane in turn, rejecting the point if it fails at any point in the test.

Clipping

This follows on from view frustrums really. There are 2 main approaches to clipping 3D scenes. The first is to do the clipping in full 3D before you do the perspective projection. The second (simpler) way is to do the perspective projection and then clip everything in 2D. The first way is more complicated mathematically (and harder to code) but it is actually quicker as you don't have to project every polygon in the scene before clipping it to the view plane (and is very handy when you're using portals).

    3D Clipping

    The first thing to do is to eliminate any polys that lie infront of the near clipping plane or behind the far clipping plane. In most scenes this will reduce the number of polys quite significantly. After that you need to do the left and right planes, then finally the top and bottom planes. Here's how to clip against a plane :

    For a point P, make P' = P-r (where r is any point in the plane). Then calculate the dot product of P' with the normal to the plane. If the result is positive then the point is above the plane, if it is zero then the point is in the plane and if it is negative then the point is below the plane. Because you can represent planes in a number of ways there are other ways of doing this. I usually store a plane as the normal and the perpendicular distance (d) to the origin. Then you just calculate P.n and compare it to d (saves doing a point subtraction).

    2D Clipping

    My favourite 2D clipping algorithm is the Sutherland-Hodgman algorithm. This is a nice, simple and efficient algorithm. Basically, all you need to do is take you perspective transformed polygons and clip them against the 4 sides of the screen 1 at a time (the order isn't particularly important). This method can be improved if you do near- and far-plane clipping before the projection (really easy once everything's been transformed into view-space as you just compare the Z coordinates of the polys against the distances to the planes.

Source Code

OK, here's my library for doing this stuff in C++ (I don't use plain C anymore I'm afraid). It doesn't contain all of the code for doing clipping and stuff - just the stuff for manipulating planes and frustrums (or should that be frustra? bloody latin plurals...) aswell as the stuff for generating the basic primitive matrices. You'll learn more from writing the extra bits for yourself - it'll give you a more solid understanding of what's actually going on.

This code requires the stuff in LA.ZIP from the Linear Algebra tutorial.

   
 
  Last Updated 22nd July 1999