This article describes two methods for quickly and conservatively determining if a group of triangles is back-facing or not. This information can then be used to reject groups of triangles from being drawn, saving graphics processing power.
For a given group of triangles that are close to each other spatially, the face normals associated with these triangles will also tend to be similar to one another. Therefore, it is possible to construct a cone that has its vertex at the origin and that contains all of the face normals for that group of triangles.
In this diagram, face normals are drawn in red, the boundaries of the cone are in green, the axis of the cone and the view vector are drawn in dark red, and a line perpendicular to the axis of the cone is drawn in dark blue.
Determining if a group of triangles is back-facing then is a matter of determining if all of the face normals that fall within the cone are back-facing.
If the dot product of the vector from the view position to the group of triangles and vector V1 is greater than the cosine of angle B, then all of the face normals that fall within the cone are back-facing, and thus the group of triangles is back-facing as well.
Vector V1 and the cosine of angle B can be pre-calculated and stored along with their corresponding groups of triangles. Vector V1 is the normalized average of all the face normals, and angle B is equal to the inverse sine of the smallest dot product between any of the normals and vector V1. These values can then be used for quickly determining if the group of triangles that they correspond to is back-facing or not.
In order to complete the algorithm, the fact that the vector from the view to each triangle in the group of triangles may be different must be taken into account.
This can be solved in one of two ways: either do the back-facing check for every vertex in the convex hull of the group of triangles, or introduce a tolerance factor to take into account the possible values that the view vector may be.
The algorithm to check if a group of triangles is back-facing if the bounding box of those triangles is known is simple. For each corner of the bounding box, calculate the vector from the view position to the position of the corner of the box, normalize this value, and use it as the view vector to calculate if the group of triangles is potentially visible at this point. If all of the corners of the box calculate to being back-facing, the group of triangles is definitely back facing. If any of the corners of the box calculate to being front-facing, the group of triangles may be front facing, and should be drawn.
An optimisation can get rid of the normalization per bounding box corner in the algorithm. The optimised algorithm takes a minimum of 2 adds, 3 subtracts and 3 multiplies for a group of triangles where vector V1 is facing towards the view position, and a maximum of 32 adds, 24 subtracts, 56 multiplies, and 8 divides to determine if a group of triangles is fully back facing.
The algorithm to check if a group of triangles is back-facing using the bounding sphere of those triangles is slightly more difficult, but not that hard. Take the vector from the viewpoint to the center of the bounding sphere as the view vector. Instead of comparing the dot product of this vector and vector V1 with the cosine of angle B, compare it with cos(angle B - asin(bounding sphere radius / distance from viewpoint to center of sphere)). This different calculation takes possible variation in the view vector into account, much the same way that possible variation in the face normal of the group of triangles is taken into account. If the dot product of the normalized vector from the view position to the center of the sphere and vector V1 is greater than this value, the group of triangles is definitely back facing. Otherwise, the group of triangles may be front facing, and should be drawn.
The algorithm takes a minimum of 2 adds, 3 subtracts, and 3 multiplies for a group of triangles where vector V1 is facing towards the view position, and a maximum of 4 adds, 4 subtracts, 8 multiplies, 1 divides, 1 square root, 1 cosine, and 1 inverse cosine per group of triangles.
These methods of rapidly culling groups of back-facing triangles work best on large batches of static geometry. Possible applications include terrain engines based on large tiles of polygons and culling of higher order surfaces based on results of the algorithm calculated on their convex hull.
The calculation of vector V1 and angle B that I described is not optimal. The optimal calculation is as follows:
Calculate the smallest sphere that encloses all of the normals for the group of triangles. Vector V1 is then the normalized direction to the center of the sphere, and Angle B is then equal to asin(radius of the sphere / distance from center of sphere to origin).
Calculating vector V1 and angle B in this manner may lead to more efficient culling of groups of triangles because the cone described by vector V1 and angle B in this situation is the tightest cone possible that encloses all of the normals. I did not implement this method because the method I describe should be more than adequate in most situations, and it is a simpler algorithm.
Hopefully you found the information presented in this article useful. Any questions, comments, or feedback can be sent to jordanisaak@hotmail.com, and a demo with source code demonstrating the algorithms is available at my website.