Methods to 'cull check' polys in OpenGL

Question

A quick search through the web suggests there's quite a few methods of potentially detecting back-culled faces on the CPU.

The purpose of the check is to evaluate whether to performing other operations such as tessellations is reasonable by dynamically altering the LOD of visible polys based on the number of polys on the screen.

What would your suggestions be for implementing this? Speed isn't necessarily the greatest concern - for this prototype mathematical simplicity is more important. Code snippets welcome :-)

Edit: It seems obvious to me to calculate the dot product based on the camera's viewing vector in world-space against the surface normal vector - but I'm asking this question because I'm intrigued as to why everyone and their (programming genius) dog seems to have an alternative method of handling this.

Answer 1

dot(CameraViewInv.at, SurfaceNormal) can return > 0.0 even if the the surface is visible. Think of a box whose right side normal is slightly away from the camera - as it's moved to the left of the frustum, it can become visible.

What avoids this phenomenon is dot(VecFromCameraToSurface, SurfaceNormal).

Another way is to check the winding of your screen-space vertices (ie. vertices after model, view and projection transform). This is done by checking the sign of the z component of the cross product of two edges on the screen space triangle (or quad). Code is here (not OpenGL specific):

// culls CW verts, passes CCW verts. Invert the condition for opposite behavior.
bool shouldCullTriangleScreenSpace(vec2 points[3])
{
  edgeA = points[1] - points[0];
  edgeB = points[2] - points[0];
  return (edgeA.x * edgeB.y - edgeA.y * edgeB.x) < 0.0;
}

EDIT: I just wanted to mention an extension to the dot(VecFromCameraToSurface, SurfaceNormal) technique that takes into account post-tessellation extrusion.

The idea is to precompute some metadata for the patch from the range of post-tessellation normals. First generate an average normal for the patch, and figure out the maximum angle of deviation for all normals on the patch from that normal.

This can be done like this at precalculation time:

  void getConeAngleForPatch(Patch p, vec3& coneDir, float& cosConeAngle)
  {
    // compute cone direction (average of all normals in the post-tessellation patch)
    vec3 coneDir = 0;
    foreach normal N generated by p
      coneDir += N
    normalize(coneDir);
    // calculate the cos of the maximum angle between normals N and coneDir
    cosConeAngle = 1.0;
    foreach normal N generated by p
      cosConeAngle = min(cosConeAngle, dot(N, coneDir));
  }

Then your patch backface culling trick in the shader becomes:

  dot(UnitVecFromCameraToSurface, coneDir) < -cosConeAngle

...instead of:

  dot(UnitVecFromCameraToSurface, SurfaceNormal) < 0

Answer 2

You can just check to see if your worldspace camera position is on the negative half-space of the the plane of the triangle you are considering (dot product of Normal and camera position and then a comparison to the plane constant).

This can be done hierarchically to be efficient i.e., you group triangle with similar normals together - effectively the normals all fall within some reasonably small cone. Then a test against this cone (effectively a dot product with a more conservative constant), can reject or accept many triangles at once.

In general, it is best to let the hardware do it - the overhead of dynamically altering your index or vertex buffers (when non-indexed) and the coding effort required likely isn't worth it.

Note that in your tessellation example, even if the pre-tessellated triangle or quad is invisible a tessellated AND displaced mesh may still have front facing triangles, so be careful. :-)