Backface Culling
The Problem #
When rendering 3D meshes, you often want to avoid rendering triangles that you don't need to render. Consider the rendering engine below:
This engine is rendering a cube composed of 12 triangles making up its six square faces. However, we should only actually see six faces of the cube. The other six should be currently hidden from view. Why render these polygons if they shouldn't be visible anyway? If we got rid of them, we could speed up rendering. This might not be such a big deal for a cube, but for a more complicated model it could mean the difference between 15 and 30 FPS.
Furthermore, look at how the cube looks right now. Under certain circumstances— despite the fact that we've implemented depth sorting in this engine— it isn't perfect: Some polygons still appear in the wrong order regardless. Getting rid of these wrongly-ordered polygons would mitigate this issue.
The Solution #
The solution to this issue is to implement Backface Culling. The underlying idea of backface culling is the observation that most meshes are "solid" objects with one side facing toward the camera and another side facing away from the camera, allowing us to safely discard any faces that are facing away. These faces which are facing away are known as "backfaces."
There are two main schools of thought when implementing backface culling, which I'll call the "Normal Dot Product" method and the "Winding Order" method. While both methods are quite fast and simple, they each have their trade-offs.
Commonalities Between Both Methods #
Both methods build on the same scaffolding: We are filtering the list of polygons to be drawn, removing all of the backfaces. Be careful when doing this— it will need to play nicely with depth sorting and any other filtering operation (e.g. frustum culling) that you perform on your scene. You'll also need to cull the mesh colors so that they remain 1:1 with the polygons.
The Normal Dot Product Method #
If you have face normals available for your mesh, this method may be for you. As a tl;dr, a face normal is a unit vector which is perpendicular to a face in a mesh. Crucially, it also points in the direction outside of the mesh. This is important if you want to, say, render the outside of the box, versus the inside of a cube-shaped room. For a box, you want the normals to point outward; for a room, you want the normals to point inward.
In other words, a face normal is a compact way of describing the orientation of a face, which is exactly what we need. In order to detect whether a face is a backface using its normal, we can also define what I'll call a "camera vector": a vector pointing from the camera to one of the points in the triangle (doesn't matter which one).
You can infer then that if the face normal and the camera vector are facing toward one another (i.e. are pointing in opposite directions), then the face is not a backface and should stay. Conversely, if the face normal and camera vector are facing in the same direction, then the face is a backface and should be removed.
We can tell whether these vectors are pointing in the same direction (and therefore should be culled) by taking their dot product. If two vectors have an angle of less than 180 degrees, then their dot product is positive, and thus should be culled. Thus, a polygon should stay in the list if and only if this dot product is negative. In other words, given the definition of a dot product, we can use this as our list filter:
Note that the triangle coordinates can be on any point on the triangle, including one of its vertices.
The Winding Order Method #
The Winding Order Method is nice because it doesn't require face normals, which often have to be computed after-the-fact and don't play as nicely with rotated and/or transformed models. That being said, it may be slightly slower in the absence of these advantages (though this is debatable— Desmos performance is largely a mystery!).
This method relies on the assumption that all polygons in the mesh have the same winding order when rendered. The "winding order" of a polygon describes whether its vertices are given in clockwise or counterclockwise order:
Importantly, the winding order of a polygon changes as soon as you flip it over. You can easily demonstrate this by taking a sheet of paper, drawing a bunch of arrows in a circle (or triangle like above) in a thick marker, and then flipping it over. You'll see that the arrows change direction— clockwise to counterclockwise, or vice-versa. What this means is that you can define the "front face" of a triangle by intentionally choosing its winding order when it's projected to 2D. For instance, you could arbitrarily say that any counterclockwise polygon is considered to be facing toward the camera. Therefore, if you were to see that a face is clockwise, you know that it's a backface and therefore must be culled.
This might seem like an annoying technique to set up as it requires careful control over polygons. However, most 3D software today is designed to have this level of control when outputting meshes, because many if not all graphics APIs have backface culling built in using this exact method.
How do we determine winding order? The answer is less complicated than you might expect. Consider one edge of a triangle. This edge has a definite start vertex and a definite end vertex, since we care about the order in which vertices are laid out to determine winding order. These vertices are 2D, since, again, winding order only really makes sense once we project 3D coordinates onto 2D space. Let's define the starting vertex as and the end vertex as .
To get the "contribution" to the winding order from this edge, we calculate . We then repeat this for every other edge in the polygon, and sum all the results together. Assuming the third vertex in the triangle is defined as , the total winding order of a triangle is therefore as follows:
What does this number actually mean though? Long story short, if it's negative, the polygon is counterclockwise. If it's positive, it's clockwise. So, in other words, if you're culling clockwise polygons (which appears to be more standard), you only keep the polygons for which this winding order equation is negative.