backface culling

A technique for reducing the amount of work you have to do when rendering 3D computer graphics with polygons. If done right, on average it reduces the number of polygons to be drawn by half.

First, though, you need to understand something about the way polygons are used by computer graphics people. As far as CG people are concerned, polygons only have one side. The other side is considered "see-through" or non-existent. The side which is drawn depends on (a) the order in which the vertices are specified and (b) the "handedness" of the system (usually right handed). So you use the right-hand rule, curled in the order of the vertices. An example:

A 
|\
| \
|  \
|   \
+----\
B    C 

is facing towards you, so would be rendered, but

A 
|\
| \
|  \
|   \
+----\
C    B 

is facing away from you (into the computer) so wouldn't be rendered.

Having one-sided polygons makes a lot of sense, because otherwise you would have to render both sides of a polygon, and since many of the things you are modelling are solid, you can never see both sides of a given polygon anyway. Solid objects tend to be self-occluding. Consider a cube. A computer graphics person would label the corners in such a way that all the faces were facing outwards (i.e. away from the centre of the cube). But at least three faces of the cube are going to be obscured anyway.

Backface culling just takes this a step further. Work out if a polygon is facing away from us, and if so, just drop it right away. In an average scene, half the polygons will be facing away from us. For example, only three faces of the cube will ever be facing towards us anyway. And hence you get a good speedup.

To actually do this:

1. Calculate the Surface Normal to the polygon. One of the ways to do this is to calculate the cross product of two of the sides of the polygon in ymelup's writeup above, eg A - > B, A - > C:

vector U = (Bx-Ax, By-Ay, Bz-Az)
vector V = (Cx-Ax, Cy-Ay, Cz-Az)
vector W = U x V

There are two vectors of non-zero length that are at right angles to U & V, W and -W. Order is important with the cross product: U x V = W and V x U = -W. Since we obtained the values of U and V from the triangle A,B,C above, you can see that the vertex ordering direction is important. Following the right hand rule which states that if you put the base of your palm at the first vertex and curl your fingers around in ascending order, your thumb will point out the vector perpendicular to the polygon.

As we want the normal facing "outwards" from the invisible space "inside" the polygons, we order the verticies in an anti-clockwise order with the outwards side facing us.

2. Calculate the dot product between the surface normal and the sight vector, which is the vector of the camera looking into the world. In camera co-ordinates this would be (0,0,-1) or nothing but Z. You can read about what the inequalities of the dot product mean in it's node, but here are what they mean to us:

< 0 : The polygon is facing away from us, so it is effectively invisible and we can cull it from further rendering.
= 0 : The polygon is side on to us, and since it is 2D and infinitely thin, it is effectively invisible.
> 0 : The polygon is visible.

It is possible for part of a model to be just one polygon thick with no internal invisible space, where both sides are always visible. A flag should be set and backface culling skipped in this case.

---

discofever brought to my attention the optimisation of pre-calculating normals then rotating them with the polygon to avoid recomputing them. Another trick is to initially calculate the magnitude (or vector length) of the normal, which does not change on rotation, only scaling.