Introduction

3D Programming Demos and Tutorials

Back-face Culling
by Simon Brown

Culling
In software 3D programming, the majority of the time taken to render a frame is taken up actually drawing triangles. Therefore there is a direct relationship between the number of triangles you draw, and the time it takes to render a frame. In comparison, the math's that gets your 3D world ready to be drawn usually takes relatively little time.

This means if you can do something with maths to get the amount of triangles you need to draw closer to the amount actually visible, it will significantly improve your frame rates. One of the worst culprits is triangles which fall within the confines of the screen after they have been through your 3D pipeline, but are facing away from the viewer/camera. These triangles are almost as slow to draw as visible triangles. Fortunately there is a way to find out if a triangle is facing away from the viewer, and remove it from your draw list. This process is called Back-face Culling.

Hidden surface removal is a pretty large subject and back-face culling is only a small part of it. Frustum culling will be covered in a later tutorial.

Vectors
A vector is a type of line that specifies a direction, displacement (movement) or location in 3D space. It also has a magnitude, in other words the length of the line. In this case, the vectors we will be using represent a direction. Vectors are specified in terms of their length in the three axis, x, y and z. This makes them easy to work with, and in C/C++ we would use-

float V[3];

to describe a vector. V[0] represents the x component, V[1] the y component and V[2] the z component.

Normals
A surface normal is a vector which is perpendicular (at a right angle) to that surface. A good analogy is the legs of a coffee table. Each leg is at 90 degrees to the surface of the table, so the legs are surface normals to the table surface.

With triangles there are two types of normal, depending on which kind of shading you are using. There are face normals and vertex normals. Face normals are used to determine visibility. A face normal tells us which direction a face (or surface) is facing. Both face normals and vertex normals are used for directional lighting, face normals with flat shading and vertex normals with gouraud shading. At the moment we are only interested in face normals.

A face normal doesn't really have a position, but you can imagine it sitting in the centre of a triangle pointing out at a right angle to the surface of the triangle, as shown in Figure 4.1 below.

Figure 4.1 - An illustration of a face-normal.

In reality however, since we are only interested in the direction the face normal points, and not it's actual position in 3D space, our normals will all be specified as a direction from the origin (0,0,0). It's important when defining your 3D objects, that you specify your vertices in a consistent order, either always clockwise or always anti-clockwise. This is because the face-normal determines which way a face is pointing, and face normals are generated using your vertices. So if you specify your vertices in the wrong order, the triangle will face the wrong way.

Calculating Normals
To calculate a surface normal, we find two vectors that are on the plane of the triangle and take the cross product of them. Taking the cross product of two co-planar vectors will give us a vector perpendicular to that plane, which is exactly what we're after. We'll deal with how to calculate a cross product in a while, but first how do we get two vectors that are on the plane of the triangle?

Another useful property of vectors is that we can subtract them by subtracting the individual x,y and z values. If we take the vector from the origin to one point of our triangle, and then subtract the vector from the origin to another point of our triangle, this gives us the vector between the two points. And, of course, the vector between two points of our triangle must be on the plane of the triangle. The vector from the origin to one point of our triangle is actually just identical to the x,y,z coordinates of that point, since the origin is at (0,0,0).

So if we have the vector-

float v1[3];

and let's say we are using this struct for storing a vertex of a triangle-

struct vertex
{
float x, y, z; // x,y,z coordinates of vertex
};

and this struct for representing a triangle-

struct triangle
{
vertex v[3]; // array of three vertices (of type vertex)
float nx, ny, nz; // x,y,z component of surface normal
};

then to calculate a vector from one point of our triangle to another point (in this circumstance from point 1 to point 0) we do-

// Calculate Vector from point 1 to 0
v1 [0] = v[0].x - v[1].x;
v1 [1] = v[0].y - v[1].y;
v1 [2] = v[0].z - v[1].z;

So we are just basically subtracting the x,y,z coordinates for point 1 from those of point 0. Now we have a vector v1[3] that lies on the plane of our triangle and points the direction from point 1 to point 0. We now need another vector on the plane of our triangle, this time we'll go from point 2 to point 1, so-

float v2 [3];

// Calculate Vector from point 2 to 1
v2 [0] = v[1].x - v[2].x;
v2 [1] = v[1].y - v[2].y;
v2 [2] = v[1].z - v[2].z;

Normalizing Vectors
So, we have our two vectors on the plane of our triangle. Before we can compute the cross product, we need to 'normalize' the vectors. To normalize a vector means to make it of length 1. So after out vector has been normalized, if we used pythagorus theorem in 3D to calculate the length of the vector, we would get 1.0 as the result. To make our vectors of length 1, we first find out their current length, and then divide the x,y,z components of the vector by this length. To calculate their current length, we use Pythagorus theorem, extended to 3D, like so-

// Compute magnitude of both Vectors
float mag1 = sqrt ( ( v1[0] * v1[0] ) + ( v1[1] * v1[1] ) + ( v1[2] * v1[2] ) );
float mag2 = sqrt ( ( v2[0] * v2[0] ) + ( v2[1] * v2[1] ) + ( v2[2] * v2[2] ) );

// Normalize both Vectors
for ( int i = 0; i < 3; i++ )
{
v1 [i] = ( v1 [i] / mag1 );
v2 [i] = ( v2 [i] / mag2 );
}

Pythagorus theorem in 3D takes the distance between two points in x, y and z and then calculates the 3D distance, but since the magnitude of a vector is taken from the origin there isn't a great deal of point in writing ((v1[0] - 0.0f) * (v1[0] - 0.0f) ) as I'm sure you will agree, so we can just use ( v1[0] * v1 [0] ).

So, we've now normalized our two vectors. All that remains is to compute the cross product. The formula for the cross product, also known as vector product is-

a x b = ( ay*bz - az*by ) + ( az*bx - ax*bz ) + ( ax*by - ay*bx )

where ay represents the y component of vector a. We can then split this into the three x,y and z components like this (in code)-

result [0] = ( a[1] * b[2] ) - ( a[2] * b[1] );
result [1] = ( a[2] * b[0] ) - ( a[0] * b[2] );
result [2] = ( a[0] * b[1] ) - ( a[1] * b[0] );

so the actual code with the variables we've been using is-

// Compute Cross Product to give surface normal
nx = ( v1[1] * v2[2] ) - ( v1[2] * v2[1] );
ny = ( v1[2] * v2[0] ) - ( v1[0] * v2[2] );
nz = ( v1[0] * v2[1] ) - ( v1[1] * v2[0] );

So that's how to compute a face normal for a triangle, but before we get to how to determine visibility using it, I'm briefly going to discuss the general approach to using normals.

Using Normals
As we've already discussed, a face normal tells us which direction a face or surface is facing. This means if the face rotates, we also need to rotate the face normal. In fact, the normals have to go through roughly the same 3D pipeline that your geometry goes through. Since they only represent direction and not position, you do not need to translate or scale them, but you do need to rotate them through the same x, y and z angle as your geometry goes through to get from local to world space, and then again by the x, y and z angle your geometry goes through to get from global to camera space.

The best approach is to calculate all your face normals when your program first runs, then store them and rotate them every frame. The reason to keep the originals is that if you kept processing the resultant normals every frame, the errors would soon build to the point where the normals were useless. Avoid this by starting with the original data at the beginning of each frame.

Computing Visibility
Now we're ready to find out if our particular triangle is facing the camera or not. For this we need more maths, this time we use the dot product, also known as scalar product. Dot product will give us the Cosine of the angle between two vectors. The formula to compute a dot product is-

a.b = ( ax * bx ) + ( ay * by ) + ( az * bz )

So a and b are vectors and the dot (.) denotes that we are calculating the dot product. ax denotes the x component of the vector a.

You've probably figured out that one of the two vectors above is the surface normal. The other vector is the direction from the camera to the triangle in question. To calculate this we use the cameras position and any point on our triangle, the only difficulty is that the camera and the triangle have to be in the same space. That means we can either use both the triangle and camera position in global space, or the triangle and camera position in camera (view) space. It's likely that you will never have the triangles coordinates in global space, since you will probably find it easier to transform all your triangles from local to global to camera space using a single matrix, as I do. Hence you may just as well use camera space.

The cameras position in camera space is, funnily enough, (0,0,0) since camera space is relative to the camera, so to compute a vector from the camera to our triangle we do this-

float v [3];

// Take Vector from camera to point on triangle
v [0] = cs[0].x;
v [1] = cs[0].y;
v [2] = cs[0].z;

where cs[0].x is the x coordinate of point 0 of our triangle in camera space. Subtracting the camera coordinates isn't necessary because the camera lies at (0,0,0).

So we now have our normal, rotated into camera space, and a vector from the camera to our triangle. The dot product can now be calculated to give us the cosine of the angle between the two vectors. We don't have to worry about converting from the cosine of the angle, to the actual angle, since we only need to know whether the triangle is facing away or not. Hence if the angle is either less than 90 degrees or more than 270 degrees, then the triangle is facing away (since the vector from the camera to the triangle is also facing away from the camera), and the cosine of the angle will be positive. So all we need to do is compute the dot product and cull triangles where the result is positive, like so-

// Calculate cosine of angle between two vectors
float result = 0.0f;
result = ( cs_nx * v[0] ) + ( cs_ny * v[1] ) + ( cs_nz * v[2] );

// Set triangle to be drawn by default
bIsVisible = true;

// Check if triangle is facing away from viewer
if ( result > 0.0f )
bIsVisible = false;

where cs_nx is the x component of the face normal once in camera space, and bIsVisible is a bool for storing visibility of the triangle.

Conclusion
So, that's how Back-face Culling works and it's definitely worth using for speed purposes. I began this section by talking about the other uses for normals, in particular face normals, which can also be used to compute face brightness with respect to a directional light source, and that's the subject of the next tutorial.