The View Frustum, View Culling, and Secrets of the Projection Matrix

CS 481/681 2007 Lecture, Dr. Lawlor

Say you're drawing a big world, with lots of stuff in it. Most of the stuff is behind your head, or off to the sides of the screen. We saw how you can speed this up with "view culling"--don't draw stuff that's offscreen!

There's a suprisingly nice way to do view culling using the projection matrix directly.

The View Frustum

All the world-space you can see through the screen is the "view frustum". It's bounded by the left, top, right, and bottom edges of the screen (4 sides), and usually also by a "near" and "far" clipping plane. There's even an OpenGL routine called "glFrustum", although I like gluPerspective better.

So you can clip to the visible stuff onscreen by clipping to a set of planes--stuff that's outside of *any* plane is off the screen (or equivalently, you can see stuff that lies in the intersection of the OK regions of all the planes).

View Culling for Clipping Planes

You can define a plane with two vec3's: a point, p, and a normal n. You can then determine if a new point c is "inside the plane" (on the good side) by computing:

(1)	dot(c-p,n) > 0

For example, if p is the origin, and n is the X axis, this reduces to

	dot(c-vec3(0), vec3(1,0,0)) = dot(c,vec3(1,0,0) ) = c.x > 0

which is pretty clearly testing if c.x lies along the positive X axis!

Our choice of ">0" comparison makes the "inside" of the plane the direction n is facing towards.

Our comparison is also equivalent (by distributing the dot product across the subtraction) to:

	dot(c,n) - dot(p,n) > 0

where dot(p,n) is a fixed property of the plane. Hence you can either define a constant float d=-dot(p,n) and compute

	dot(c,n) + d > 0

or you can go all the way and define a plane by a vec4, like N=vec4(n.x,n.y,n.z,d), and then

(2)	dot(C,N) > 0

where you're doing a vec4 dot product using the homogenous point-with-w-coordinate C=vec4(c.x,c.y,c.z,1.0);

Clipping Planes from the Projection Matrix

So that's clipping planes. What you've often got, though, is a projection matrix, which you can read back out of OpenGL like this:

	mat4 m(1.0);
	glGetFloatv(GL_PROJECTION_MATRIX,&m[0][0]);

So given a world-coordinates vec4 v, we can compute the onscreen location (for example, in our vertex shader) like this:

	vec4 s = m * v;
	draw_pixel_at(s.x/s.w, s.y/s.w, s.z/s.w);

OK. The question is, which v's will give you onscreen pixels? Well, let's make our lives a bit simpler--which v's will satisfy this comparison?

(3)	s.x/s.w > t

Here, "t" is our "test" value--for example, t==-1.0 would test if our x coordinate is greater than the left side of the screen.

Now, just looking up the definition of matrix-vector multiplication, we can see:

	s.x = m[0][0]*v.x + m[1][0]*v.y + m[2][0]*v.z + m[3][0]*v.w;

That is, s.x is just the dot product of the 0'th row of the matrix with v:

	s.x = dot(matrixrow(m,0),v);

or defining "mx" as the 0'th row, simply s.x=dot(mx,v);
This is nice, because now we can just rearrange our test equation (3) to solve for v:

	s.x/s.w > t
	s.x > t*s.w
	dot(mx,v) > t*dot(mw,v)
	dot(mx,v) - t*dot(mw,v) > 0
(4)	dot(mx-t*mw,v) > 0

This equation should immediately give you a clue that there's some similarity between rows of your projection matrix and the vec4 planes defining your clipping planes! Specifically, N = mx-t*mw, which is to say you can compute the normal and constant for your X clipping plane from a scaled version of the X and W rows of your projection matrix!