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
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:
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;
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?
draw_pixel_at(s.x/s.w, s.y/s.w, s.z/s.w);
(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*v.x + m*v.y + m*v.z + m*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
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
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