backface culling

Backface culling is a method to reduce the number of triangles that have to be drawn in a scene by working out which ones are facing away from the viewer.

If a triangle is facing away from the camera and is part of a solid object, you can say with certainty that it can't be seen. If you can find a quick and simple way to work out which way a triangle is facing then you can avoid doing the work to draw it to the screen. This saves the wasted effort of calculating lighting, textures and so on, but leaves the on screen result exactly the same.

One simple way to work out if a triangle is facing away from a camera uses a function known as the dot product. This is a vector function that calculates the cosine of the angle between two vectors. Comparing the angle between the vector to the camera and the triangle's normal tells you which direction the polygon is facing.

this could probably do with a simple diagram.

Processing actually supports backface culling internally, so you can just enable that to get the same effect. The code below is supplied as a lesson in how it works, rather than the best way to enable it. It's also worth noting that whilst your camera position does not change and your model does not move, then performing your own backface culling once rather than letting Processing do it every frame could give quite a big speed increase for complex scenes.

This code uses some simple Vector classes and functions to make life easier. The Vector3f class just groups x, y and z float coordinates together, and a triangle is represented as an array of three Vector3fs.

 
/**
backface culling taken from http://processinghacks.com/hacks:backface_culling
@author John Gilbertson
*/
 
/** the Vector3f class, used to store a 3-dimensional vector */
class Vector3f {
  float x,y,z;
  Vector3f(float _x, float _y, float _z) {
    x=_x;
    y=_y;
    z=_z;
  }
}
 
/** calculates the dot product of two Vectors */
float dot(Vector3f a, Vector3f b) {
  return(a.x*b.x + a.y*b.y + a.z*b.z);
}
 
/** calculates the cross product of two Vectors */
Vector3f cross(Vector3f a, Vector3f b) {
  return new Vector3f(a.y*b.z - a.z*b.y, 
                      a.z*b.x - a.x*b.z, 
                      a.x*b.y - a.y*b.x);
}
 
/** checks if the given face is visible from the given camera position */
boolean visible(Vector3f cameraPosition, Vector3f[] face) {
 
  if(face.length!=3) {
    println("This only works with faces with 3 corners");
    return false;
  }
 
  // this works out the vector from the camera to the face.
  Vector3f cameraToFace = new Vector3f(cameraPosition.x-face[0].x,
                                       cameraPosition.y-face[0].y,
                                       cameraPosition.z-face[0].z);
 
  // we need to find out what direction the face is pointing, 
  // known as the normal. to do this we need to do a cross 
  // product of two of the sides of the face.
  // side 1
  Vector3f ab = new Vector3f(face[1].x-face[0].x,
                             face[1].y-face[0].y,
                             face[1].z-face[0].z);
  Vector3f cb = new Vector3f(face[1].x-face[2].x,
                             face[1].y-face[2].y,
                             face[1].z-face[2].z);
  Vector3f faceNormal = cross(cb,ab);
 
  // so that we can draw the normal later on outside of this function.
  triangleNormal = faceNormal;
 
  // We now know the vector from the camera to the face, 
  // and the vector that describes which direction the face 
  // is pointing, so we just need to do a dot-product and 
  // based on that we can tell if it's facing the camera or not
  float result = dot(cameraToFace,faceNormal);
 
  // if the result is positive, then it is facing the camera.
  return result > 0;
}
 
 
Vector3f[] verticies;
Vector3f camPos;
Vector3f triangleNormal;
 
float rotation;
 
void setup() {
  size(400,400,P3D);
  noStroke();
 
  // initialise triangle vertices
  verticies=new Vector3f[3];
  verticies[0]=new Vector3f(-20,-20,0);
  verticies[1]=new Vector3f(0,20,0);
  verticies[2]=new Vector3f(20,-20,0);
}
 
void draw() {
 
  background(0);
 
  // orbit around the triangle
  rotation += 0.01;
 
  camPos = new Vector3f(50*sin(rotation),0,50*cos(rotation));
  camera(camPos.x,camPos.y,camPos.z,0,0,0,0,-1,0);
 
  // We'll use different colours to show wether the triangle is visible
  // or not to make it easier to see that it's definately working. In 
  // practice you'd use the result to decide wether to draw it or not.
  boolean canBeSeen = visible(camPos,verticies);
  if(canBeSeen) {
    fill(128,255,128); 
  }
  else {
    fill(255,128,128); 
  }
 
  beginShape(TRIANGLES);
  vertex(verticies[0].x,verticies[0].y,verticies[0].z);
  vertex(verticies[1].x,verticies[1].y,verticies[1].z);
  vertex(verticies[2].x,verticies[2].y,verticies[2].z);
  endShape();  
 
  // And to make the "normal" of the triangle visible to show 
  // that the correct side of the triangle is being shown...
 
  stroke(0,0,255);
  beginShape(LINES);
  vertex(0,0,0); //the middle of the triangle
  vertex(triangleNormal.x/200,triangleNormal.y/200,triangleNormal.z/200);
  endShape();
  noStroke();
 
}

To enable processing's automatic backface culling if you're using P3D just add the following into your setup() routine.

  ((PGraphics3)g).triangle.setCulling(true);

backface-001.zip

Please list any links you think are essential reading related to this hack:

http://processing.org