Culling 3D triangles

The CLOD algorithms i've found describe how finely to subdivide the faces of a surface from a given viewpoint, but they don't explicitly mention how to make use of view culling to reduce the amount of work.  If faces can be quickly rejected as being outside the view volume, they don't have to be evaluated for subdivision!

I went looking for online and print resources describing how to cull 3D triangles against a view volume.  Surprisingly, there were no references online.

• no mention in the Graphics Gems books
• the standard reference Foley-van Dam has a section 6.5.3: Clipping Against a Canonical View Volume in 3D, however, it only discusses line segments, not triangles
• [Henry Hoff at UNC] had plenty of descriptions and code for test bounding boxes against a view volume, but not triangles
• MarkMorley's Frustum Culling in OpenGL (now offline?) describes testing triangles, but doesn't handle all cases.

My early attempt to solve this problem (1999):

Test: 3D triangle vs. view volume

The triangle is given as three 3D points.  The view volume is given as 6 plane equations, or for the purposes of this description, 4 plane equations.  The result of the test should indicate how much of the triangle is inside the view volume: ALL IN, PART IN, or NONE IN.

One way is to to turn the triangle into a sphere, by averaging to find the center and radius, then test the sphere against the view volume.  This is straightforward, but very conservative and, when i tried it, very slow.

We can test each point individually against each of the 4 planes.  Just like 2D clipping, this gives 9 possible 4-bit "outcodes" for each vertex.  Cases:

1. All points are in the view volume -> ALL IN
2. Either 1 or 2 points are in the view volume: -> PART IN
3. All points are outside the view volume, and no part of the triangle intersects the volume -> NONE IN
4. All points are outside the view volume, but some part of the triangle intersects the volume -> PART IN

Cases 1 and 2 are easy to detect:

• If all outcodes are 0, it's case 1.
• If only 1 or 2 outcodes is 0, it's case 2.

If all 3 outcode are not 0, how do we tell cases 3 and 4 apart?  We could binary-and the outcodes together.

• If (outcode1 & outcode2 & outcode3) != 0, then it's case 3.

That leaves the complicated case of triangles that straddle the view volume and may or may not intersect.  I think it would take a lot more calculation to determine whether or not it actually intersects.  We could test each of the 4 rays that define the edges of the view volume for intersection with the triangle, using a ray-vs-triangle algorithm.  There may be other approaches as well.  However, since this is a relatively unusual case, we could just conservatively declare at this point that the triangle is PART IN, with the understanding that in some cases it's actually not.

Update (2006):

From: Sergi [mailto:zgoonza@hotmail.com]
Sent: Sunday, November 12, 2006 4:28 AM
Subject: Culling triangles against a view volume

If you are interested in culling triangles against a view volume, you can use 3D Cohen-Sutherland line clipping algorithm. In Cohen-Sutherland 2D line clipping algorithm, the endpoints of a line are classified into 9 regions. In 3d, each endpoint is classified into 27 regions.

Useful information about the algorithm can be found here:
http://www.cs.drexel.edu/~david/Classes/CS430/Lectures/L-14_CullingZbufRays.6.pdf

To cull a triangle, once you have classified the 3 triangle points, check the following conditions:

if ( (outcodes[0] | outcodes[1]) == 0 && (outcodes[1] | outcodes[2]) == 0 )
{
  // all points in
  early_in++;
}
else if ( (outcodes[0] == outcodes[1]) && (outcodes[0] == outcodes[2]) )
{
  // all points out
  early_out++;
}
else
{
  // part of the triangle is inside the viewing volume
}

I'm using this algorithm in my software rasterizer and it works well.