Table Of Contents

• Introduction
• The Old Way: 2D Backface Culling
• Culling in 3D
• The Reverse Transformation
• Final Words

• Introduction

  Ok, I guess it's now time to start working on the 3D section of my tutorial pages. 3D backface culling in object space is a topic which is easy to implement but can reduce some of the calculation costs.

  Backface culling is used in 3D rendering. It helps you to sort those polygons out of your scene database that won't be visible. Since you want to remove them as fast as possible. Please note, that in the age of pentiums and other fast processors the overhead of doing this stuff might be higher than the time you can save. I implemented it and found out, that it's not really faster than normal backface culling. However, the results are much more accurate

  One note before we start: Whenever I speak about tranformations I mean linear transformations. A tranformation may be build out of any number in any order combination of the follwing actions: Rotation, Scaling, Shearing (and if you work with 4x4 matrices Translation).

• The Old Way: 2D Backface Culling

  We assume, that all polygons are triangles, and that the vertices are ordered counter-clockwise. (If you're familiar with 3d graphics you'll know what I mean, otherwise you should first take a look at some other 3D tutorials).

  Now just take a polygon, rotate it, scale it, do whatever you want to do with it and then project it into screen coordinates. We can now test if the polygon is visible using the screen coordinates:

  
  
     v1, v2, v3   are the points of the polygons in 2D space.
  
                  (rotated and projected to 2D space)
  
  

  now you calcuate the two direction vectors that makes up the poly:

  
  
     d1.x = v3.x - v1.x
  
     d1.y = v3.y - v1.y
  
     d2.x = v3.x - v2.x
  
     d2.y = v3.y - v2.y
  
  

  If you now would build the crossproduct of these two vectors you'll get another vector. This vector points out of the polygon. (it's called the polygon normal vector if you don't already know this) If the z-component of this vector is negative the polygon faces away from the camera and the polygon can be skipped.
  
  Complete Formula: z = (d1.x * d2.y) - (d1.y * d2.x)
  Normally ca. 50% of your polygons aren't facing the camera. That means, that if you use this approach you would rotate and perspective-project 50% of the polygons without actually drawing them.

• Culling in 3D

  Before we start with the math we have to define some therms.

  The projection plane (your screen!) is located at the origin of the coordinate system, and your camera is in some distance located behind this plane. the distance of the camera to the projection plane is called projection distance.

  
  Here is an image which illustrate these terms

  All the above calculations require, that the object hasn't been rotated or modified in any way. And this is the point of this culling method, we can find out if a face is visible without touching the polygons at all. At first we need the position vector of the camera. If you use the same definitions as I use the vector is
  
  

  CAM = <0, 0, -project_distance>
  Now we reverse transform this vector into object space (that means, if the object would have eyes, where would it see the camera?). I'll discuss how to do this below. Don't mind about it at this moment.

  The polygon is visible if the following equation is true:
  

  dotproduct(normal, CAM) >=cullpoint
  
  
  
  where
  
  
  
  normal    is the normal vector of the polygon (in 3D).
  
  CAM       is the reverse transformated camera location vector.
  
  cullpoint is dotproduct (normal, any vertix of poly).
  
  

  Since the object must not be touched the normal can be calculated once before we start drawing and the cullpoint is a constant which won't change unless you modify the vertices or the normal (thus, compute it along with the normal vector). If your vertices move around or your object morfs you have to calculate the cullpoint and normal vectors every time you do the backface culling. In this special case you should better use the 2D way because the normal vector calculation is very expensive.

  That's all. You need one simple 3D-dotproduct and one compare to check if the polygon is facing you or not.

• The Reverse Transformation

  I already noted, that you need to reverse transform the camera location vector CAM. If you have a good knowlage in math you'll have no problems to do this. For all the other I'll give some comments what I mean and how to do it.

  The backface culling MUST take the object transformation into account. One way to do this would be to transform the object vertices and normals and work with the camera location. This means, that we still have to rotate all the vertices and normals before we know which polygons are visible and which not. We still save the perspective projection compared to the 2D approach, but the advantage of 3D culling has gone.

  The second approach would be only to transform the CAM vector. And this transformation is a little bit special. It must be the complete inversion of the object transformation. That means if you would do the following with your object:

  
  
    rotate x by 30 degree
  
    rotate y by 20 degree
  
    rotate z by 50 degree
  
    translate by &lg1,2,3>
  
  

  you have to do the following with your camera vector:

  
  
    translate by &lg-1,-2,-3>
  
    rotate z by -50 degree
  
    rotate y by -20 degree
  
    rotate x by -30 degree
  
  

  You don't only have to reverse the sign of the transformation but also the ORDER in which you apply these transformations. I spend some days finding my error because I forgot to reverse the order of rotations! So be warned and don't make this mistake.

  If you organized your tranformations in a matrix you can simplyfy this a little bit: Just take your object transformation matrix, build the inverse and multiply it with the CAM vector. The inversion of a transformation matrix does explicitely what you need: it reverses the meaning of a matrix.

  You can calculate the inverse matrix using the GAUSS-JORDAN algorithm, or, if you're clever you find a better way to calculate it. If your matrix is a combination of linear transformations (and I guess it will unless you do very weired stuff) there are more efficient ways to do it. Hint: look into the books Graphic Gems and search for Angle- and Lenghth preserving matrices.

• Final Words

  Many thanks go out to some folks who helped me to derive and implement this stuff. Those two who really helped me are Galvados (Orange) and John Carmack who was smart and friendly enough to help a frustrated 3D coder. Doesn't John proved that he has a good attitude answering my emails? I think he would be a good sceener!

  I'm not sure about all the 2D culling stuff. I typed it out of my mind and didn't tested it.

  If you have any comments, notes or found any bugs please contact me. I'll continue writing tutorials as long as I get some feedback and know that writing this stuff isn't just wasted time.