View frustum culling questions

Question

So, I'm trying to implement frustum culling. The thing here is that before I can do that, I need to understand some things.

First of which, is plane intersection:

My understanding is that a plane can be defined via 3 points; let's call them p0, p1, and p2.

Given that, we know that the plane's normal can be computed as follows:

(psuedo-code)

vec3 edge0 = p1 - p0;
vec3 edge1 = p2 - p0;

vec3 normal = normalize( cross( edge0, edg1 ) ) // => edge1 X edge2 / length( edge1 X edge2 );

Now, let's say we have a function which basically tells us whether or not a given point "crosses" the plane in some way.

(moar pseudo-code)

bool crossesPlane( vec3 plane[3], vec3 point )
{
    vec3 normal = getNormal( plane ); // perform same operations as described above
    float D = dot( -normal, plane[ 0 ] ); // plane[ 0 ] is arbitrary - could just as well be the 2nd or 3rd point in the array

    float dist = dot(normal, point) + D; 

    return dist >= 0; // dist < 0 means we're on the opposite side of the plane's normal. 
}

---

The logical reasoning behind this is that, since the view-frustum contains six separate planes ( near, far, left, up, right, bottom ), we'd want to grab each of these six planes and essentially "pass" them to the crossesPlane() function, for an individual point (one point, six tests for that point).

If one of these six calls to crossesPlane() returns false, then we want to cull the point in question, thus effectively resulting in the point being culled by the frustum, and of course the point won't be rendered.

Questions

• Is this a correct approach to a properly culled view-frustum?
• If so, would taking an arbitrary list of vertices for a given polygon, and performing this test on each of the vertices using this method, be an effective way of going about it?
• While AABBs can be used in place of polygon's/meshes for cull tests, are they still commonly used for this scenario, and are they still considered the "general" goto approach?

Note

If there are any implementation differences worth mentioning between D3D and OpenGL for this, it would be certainly appreciated.

Answer 1

• Yes, this is essentially the correct approach for frustum culling points.
• No, performing this test on each vertex individually is not an effective way of culling an arbitrary polygon. Consider the case of a single very large triangle that intersects the frustum: all of it's vertices may be outside the frustum but the triangle still intersects the frustum and should be rendered.
• AABBs can be used for frustum culling and are often a good choice, although you still have to handle the case of an AABB having all of it's vertices outside the frustum but intersecting the frustum. Bounding spheres make the inside / outside test somewhat simpler but tend to have looser bounds around the objects they contain. This is often a reasonable tradeoff however.

Answer 2

Your approach is generally correct.
Usually AABBs or bounding spheres are used instead of testing each vertex of an arbitrary shape.
However, for AABBs there are situations where all corners are outside the frustum, but the box still intersects the frustum. A conservative solution is to reject only boxes if all corners are on the outer side of at least one plane.
There is one common optimization for AABBs: For each plane of the frustum, you only need to check the "closest" and the "farthest" corner instead of all 6 corners. A great resource for this and frustum culling in general is this:
http://www.lighthouse3d.com/tutorials/view-frustum-culling/

Edit: Here is one more article how to find AABBs that are not completely one the outer side of one plane, but still do not intersect the frustum:
http://www.iquilezles.org/www/articles/frustumcorrect/frustumcorrect.htm