11: Culling

Culling is more or less exactly what the name says: We filter out some of the triangles that are drawn. Which ones? The basic idea is: we only see the front faces for opaque objects. And, assuming closed 3D objects, we first need to render the faces facing away from us (the back of the object) and then the ones facing towards us (the front of the object). This would mean rendering each transparent object twice, once for the back, once for the front. To avoid this additional computations, we could also just show the front for transparent objects.

Discardig the triangles facing away from us is called Backface Culling and similarly discarding the ones facing us Frontface Culling

You can find the full rasterization code here: Rasterizer 11

Computing face directions

So, how do we determine, how a polygon (since after clipping, we potentially get polygons) is oriented? Let's label the points with their indices pi\mathbf{p}_i. We start with a triangle. If we define the vertices counter-clockwise, the normal computed as n=(p1−p0)×(p2−p0)\mathbf{n} = (\mathbf{p}_1 - \mathbf{p}_0) \times (\mathbf{p}_2 - \mathbf{p}_0) will point outside the screen. In a right hand system (our original view space), the zz axis also points outside. What we will do now, is compute the dot product of the normal with the zz axis. If that is positive, then the triangle is front-facing, otherwards back-facing.

The nice thing is, that the dot product will just give us the zz component of the cross product. Let us write this out for two points:

(pi×pj)⋅z=xiyj−xjyi(\mathbf{p}_i \times \mathbf{p}_j)\cdot \mathbf{z} = x_i y_j - x_j y_i

Note: Due to the property of the cross product, this is also twice the area of the screen triangle.

Next, we will rearrange the expression for the normal, but for later reasons, we will use three indices i,j,ki,j,k, the ordered indices of the three triangle points.

(pj−pi)×(pk−pi)=pj×(pk−pi)−pi×(pk−pi)=pj×pk−pj×pi−pi×pk+pi×pi⏟=0=pj×pk−pj×pi−pi×pk=pj×pk+pi×pj+pk×pi=pi×pj+pj×pk+pk×pi=∑i=02pi×pi⨁1\begin{align*} &(\mathbf{p}_j - \mathbf{p}_i) \times (\mathbf{p}_k - \mathbf{p}_i) \\ &= \mathbf{p}_j \times (\mathbf{p}_k - \mathbf{p}_i) - \mathbf{p}_i \times (\mathbf{p}_k - \mathbf{p}_i) \\ &= \mathbf{p}_j \times \mathbf{p}_k - \mathbf{p}_j \times \mathbf{p}_i - \mathbf{p}_i \times \mathbf{p}_k + \underbrace{\mathbf{p}_i \times \mathbf{p}_i }_{=\mathbf{0}} \\ &= \mathbf{p}_j \times \mathbf{p}_k - \mathbf{p}_j \times \mathbf{p}_i - \mathbf{p}_i \times \mathbf{p}_k \\ &= \mathbf{p}_j \times \mathbf{p}_k + \mathbf{p}_i \times \mathbf{p}_j + \mathbf{p}_k \times \mathbf{p}_i \\ &= \mathbf{p}_i \times \mathbf{p}_j + \mathbf{p}_j \times \mathbf{p}_k + \mathbf{p}_k \times \mathbf{p}_i \\ &= \sum_{i=0}^{2}\mathbf{p}_i \times \mathbf{p}_{i\bigoplus 1} \end{align*}

In the last line, we have just noticed the index pattern and put it into a sum. In accordance to the OpenGL specificiation, we will use ⨁\bigoplus to mean "addition with wrap-around". So for the triangle, the index 2⨁12 \bigoplus 1 is 00.

The dot product with z\mathbf{z} then gives us the nice formula:

(pj−pi)×(pk−pi)⋅n=∑i=02xiyi⨁1−xi⨁1yi\begin{align*} (\mathbf{p}_j - \mathbf{p}_i) \times (\mathbf{p}_k - \mathbf{p}_i) \cdot \mathbf{n} &= \sum_{i=0}^{2}x_i y_{i\bigoplus 1} - x_{i\bigoplus 1} y_i \end{align*}

So, unlikely, but depending on the clipping planes, there might be some zero-triangles there, so to be robust, we will split up the polygon and add up the normal of all triangles. As we only care about the sign and therefore direction, we don't care about the length, so you can think about this like an average normal.

If we get a fourth point, we can make two triangles (0,1,2)(0,1,2) and (0,2,3)(0,2,3). Let's compute the normal (even if it is a bit tedious)!

(p1−p0)×(p2−p0)+(p2−p0)×(p3−p0)=p0×p1+p1×p2+p2×p0+p0×p2⏟=−p2×p0+p2×p3+p3×p0=p0×p1+p1×p2+p2×p3+p3×p0=∑i=03pi×pi⨁1\begin{align*} &(\mathbf{p}_1 - \mathbf{p}_0) \times (\mathbf{p}_2 - \mathbf{p}_0) + (\mathbf{p}_2 - \mathbf{p}_0) \times (\mathbf{p}_3 - \mathbf{p}_0) \\ &= \mathbf{p}_0 \times \mathbf{p}_1 + \mathbf{p}_1 \times \mathbf{p}_2 \\ & + \mathbf{p}_2 \times \mathbf{p}_0 + \underbrace{\mathbf{p}_0 \times \mathbf{p}_2}_{= - \mathbf{p}_2 \times \mathbf{p}_0} + \mathbf{p}_2 \times \mathbf{p}_3 + \mathbf{p}_3 \times \mathbf{p}_0 \\ &= \mathbf{p}_0 \times \mathbf{p}_1 + \mathbf{p}_1 \times \mathbf{p}_2 + \mathbf{p}_2 \times \mathbf{p}_3 + \mathbf{p}_3 \times \mathbf{p}_0 \\ &= \sum_{i=0}^{3}\mathbf{p}_i \times \mathbf{p}_{i\bigoplus 1} \end{align*}

So our formula stays exactly the same, since when adding a point, the duplicate line runs in another direction and cancels out!

In general we have for a polygon with nn vertices:

n=∑i=0n−1pi×pi⨁1n⋅z=∑i=0n−1xiyi⨁1−xi⨁1yi\begin{align*} \mathbf{n} &= \sum_{i=0}^{n-1}\mathbf{p}_i \times \mathbf{p}_{i\bigoplus 1} \\ \mathbf{n} \cdot \mathbf{z} &= \sum_{i=0}^{n-1}x_i y_{i\bigoplus 1} - x_{i\bigoplus 1} y_i \end{align*}

As before, we want to make our culling adjustable, so we add some paramters to our pipeline:

const Culling = {
  /** Cull front faces */
  FRONT: 0,
  /** Cull back faces */
  BACK: 1,
  /** Cull front and back faces */
  FRONT_AND_BACK: 2
};

function create_culling_options({ 
  enabled = false,
  cull_face = Culling.BACK
  } = {}) {
    return {
        enabled,
        cull_face
    };
}

class Pipeline {
  constructor({
    ...
    culling_options = create_culling_options(),
  }= {}) {
    ...
    this.culling_options = culling_options;
  }
  }

Now the only thing left to do is augmenting our process_triangle method to take into account the face direction! To illustrate the point, a simple routine was added after the definition of the objects in the scene, that randomly reorders faces. You can see the effect this has when running the unchanged exercise code.

The solution is below as always.

Exercise:

Solution:

See the solution