Culling your scene to the View Frustum.

By Steve Baker

Frustum:

Something that causes

Frustration and an

occasional Tantrum.

Culling your scene to the View Frustum.

OpenGL can correctly reject polygons that lie 'off the edge' of the screen - and clip those that straddle the edge of the screen, but the cost of transmitting all those vertices to OpenGL only to have them thrown away is pretty high.

You could write code to reject those polygons yourself - but that would be pretty pointless because it would probably take as long - if not longer - than OpenGL takes.

The optimal solution is to do a coarse level cull in your application - rejecting entire objects that lie completely off the screen - and let OpenGL do the fine-grained cull at the level of individual polygons. This approach will greatly speed up most OpenGL applications.

This paper describes one efficient method for attacking this problem.

What is a "View Volume" ?

The first thing to observe is that the screen is a 2D thing - but the objects we are culling are 3D. The way to resolve that is to imagine you are culling to a pyramid-shaped 3D volume with the apex of the pyramid at your eye - and with the four triangular faces of the pyramid lined up with the edges of the screen. The far end of the pyramid is cut off at the "far clip plane".

There is also a need to cull objects that are closer than the plane of the screen (including objects that are behind the user's head). Hence, the cull operation actually works in a truncated pyramid. The correct mathematical term for such a solid is a 'Frustum' (frequently mis-spelled Frustrum or Fustrum for some reason).

Everything that's completely inside the 'view frustum' needs to be drawn - everything that's completely outside can certainly be thrown away - anything that crosses the frustum is...erm... something we'll let OpenGL worry about at the polygon level - so we'll need to draw those objects also.

How do you Cull to a View Frustum?

Well, think of the frustum as four intersecting infinite planes (actually, it's six because near and far are also clipping planes - if you are using the custom clip planes that OpenGL supports, you might want to toss those in too).

Since we don't want to duplicate the work of OpenGL at the vertex level, we'll want to test an entire object in one go - without looking at each vertex in turn. The way to do that is to 'summarise' the extent of the object using either a sphere or cubeoid that just encloses all of the objects' vertices. This is called a 'bounding volume'.

Personally, I prefer to use a bounding sphere - but opinions vary on this point.

So, the problem boils down to "How do I tell if an arbitary sphere is either inside or crossing the six planes of the frustum?" - Fortunately, there is a really easy way to do that.

Sphere/Frustum Intersection Tests

We'll need to figure out the plane equation for each one of those six planes:


   A*x + B*y + C*z + D = 0

...that plane equation calculation can be done one-time whenever the view frustum is set up.

Note that for an arbitary point (px,py,pz), the distance to the plane is:


  d = A*px + B*py + C*pz + D

...so for each vertex of your bounding volume, you can measure the distance to each of those planes.

For a sphere: Just toss the center point of the sphere into the equation above - and if the (signed) distance places the center point more than 'radius' units outside any of the planes then you can cull the object.

That was easy!

Efficiency Improvements

But what happens if you have a LOT of objects? One solution is to arrange to group several objects together - compute a bounding sphere that contains ALL of them and test that first. If this 'super-sphere' is entirely outside the view frustum then there is no need to test the objects inside that super-sphere - they can all be culled instantly. Similarly, if the super-sphere lies entirely INSIDE the view frustum, you can go on and draw all those lesser objects without testing them further.

Only if the super-sphere straddles the frustum do you need to go and test all of those smaller objects.

To generalize this, you might want a hierarchy of spheres- containing-spheres - how deep and how 'wide' that tree needs to be depends on your application.

If do you use a heirarchical bounding volume scheme - then you can do more: You can (for example) flag *which* planes you were entirely 'inside' of and not re-test them for lesser objects.

Still, for each sphere, you may need to do as many as six sphere-center-to-plane distance calculations.

...Or do you?

If you have a relatively 'normal' symmetrical view frustum, there are some simplifications that save a lot of CPU time in calculating those six distances. Notice that:

In the plane equation mentioned above, (A,B,C) is the surface normal of the plane (I make them all face inwards) and D is the distance from the origin to the plane - measured such that D is positive for planes that face the origin and negative from those that don't.
For near and far planes, you know that A and B are zero, C is either +1 or -1 and D is plus or minus the distance to the plane.
For the left and right plane B is zero and so is D.
For the top and bottom planes A is zero and so is D.
C is the same for the left and right planes and also the same for top and bottom planes.
A is positive for the left plane and negative for the right, but the magnitudes are the same.
B is positive for the top plane and negative for the bottom, but the magnitudes are the same.

Knowing this can make testing much cheaper. Just a handful of multiplies per sphere in general.