How To: Perform manual frustum culling

r3dux | February 12, 2011

The Problem

Be Careful Machine SignWhen you use OpenGL or DirectX or whatever to draw geometry, the API itself does its own vertex culling (i.e. it doesn’t spend time drawing things which will not be visible on the screen – it opts to not draw them), but it has to do this in the only way it can – by testing each vertex against the projected window-coordinates and making a decision from that. This, as you might not be surprised to learn, is not the most efficient way to consider geometry.

Let’s take an example:

If you had a small sphere visible 5 units directly in front of you, and then you move 10 units forward, the sphere’s obviously now 5 units behind you – but your graphics API won’t (and can’t) care – it’ll just test each vertex of the sphere to see if it’s within your viewing frustum. If the sphere has a couple of hundred vertexes, you’re doing a couple of hundred checks, and making the decision not to draw anything a couple of hundred times. What about if you had ten thousand small spheres 5 units in front of you, and then you move 10 units forward? That’s a lot of per-vertex checking, and it’ll put a significant dent in your frame rate, to draw absolutely nothing at all!

Surely there’s a better way?! You betcha =D

The Solution in Theory

We, or you, know a lot more about the nature of your geometry than your graphics API – which knows nothing at all. It can’t make assumptions, it doesn’t have common sense – we have to provide it. So let’s!

frustrum

Any object that you draw can be enclosed in a sphere, where the size of the sphere will vary depending on the size of the longest axis of the object. Drawing a tree? You can enclose the tree in an imaginary sphere which is the height of the tree and centred on the tree. Drawing a person? You can enclose the person in an imaginary sphere of diameter the person’s height and centred on the person. Once we can check whether this bounding-sphere is within the viewing frustum, we can make a conscious choice as to whether we should even attempt to draw the geometry or not. So if the sphere bounding my tree, or person, or whatever doesn’t at least intersect all 6 planes (top/bottom, left/right, near/far) of my viewing frustum – then it’s not on the screen, and I can choose not to draw it in the first place – thus skipping all that per-vertex checking by applying a little bit of common sense. Sound good?

Closer to Practice

To project a vertex position in world coordinates, say, (-10, 15, 3) [i.e. -10 on the X-Axis, 15 on the Y-Axis, 3 on the Z-Axis], into screen/window coordinates, we can multiply the ModelViewProjection matrix by the vertex position (Careful: The MVP matrix multiplied by the vertex is NOT the same as the vertex multiplied by the MVP matrix! They are not commutative!).

If we then add a radius around that vertex (which is the centre of our object, and something you have to provide – i.e. you need to pick a centre point), we can check if the bounding sphere around that central point intersects any of the six planes of our viewing frustum, and if it doesn’t, we simply don’t even try to draw the object, and gain however-many per-vertex checks for our effort. If you’re checking a single 8 vertex cube you’re not going to gain all much, but if you’re checking multiple 5,000 vertex objects, then you’ll save the GPU that many per-vertex checks per frame! :)

The Solution in Practice

Now that you get the concept, here’s comes the code. This is written in C++, but really, it’s just some math about whether a sphere intercepts or is within the boundary of six planes which comprise our viewing frustum. You can adapt it to anything, and I hope you do :)

The function takes the following parameters:

  1. An array of 16 floating point values which specify the ModelViewProjection Matrix
  2. The x position of the central point
  3. The y position of the central point
  4. The z position of the central point
  5. The radius of the bounding sphere

The function returns a simple boolean of true or false to indicate whether the bounding sphere falls even partially within the viewing frustum.

bool objectVisible(const GLfloat &MVPMatrix[16], const GLfloat &xPos, const GLfloat &yPos, const GLfloat &zPos, const GLfloat &radius)
{
	// The equation for a plane is: Ax + By + Cz + D = 0, where A, B and C define the plane's normal vector, D is the distance from the origin to the plane,
	// and x, y and z are any points on the plane.. You can plug any point into the equation and if the result is 0 then the point lies on the plane. If the
	// result is greater than 0 then the point is in front of the plane, and if it's negative the point is behind the plane.
	enum term { A = 0, B, C, D };
 
	GLfloat leftPlane[4];
	leftPlane[A] = MVPMatrix[3]  + MVPMatrix[0];
	leftPlane[B] = MVPMatrix[7]  + MVPMatrix[4];
	leftPlane[C] = MVPMatrix[11] + MVPMatrix[8];
	leftPlane[D] = MVPMatrix[15] + MVPMatrix[12];
 
	// Normalise the plane
	GLfloat length = sqrtf(leftPlane[A] * leftPlane[A] + leftPlane[B] * leftPlane[B] + leftPlane[C] * leftPlane[C]);
	leftPlane[A] /= length;
	leftPlane[B] /= length;
	leftPlane[C] /= length;
	leftPlane[D] /= length;
 
	// Check the point's location with respect to the left plane of our viewing frustrum
	GLfloat distance = leftPlane[A] * xPos + leftPlane[B] * yPos + leftPlane[C] * zPos + leftPlane[D];
	if (distance <= -radius)
	{
		return false; // Bounding sphere is completely outside the left plane
	}
 
	// Check the point's location with respect to the right plane of our viewing frustum
	GLfloat rightPlane[4];
	rightPlane[A] = MVPMatrix[3]  - MVPMatrix[0];
	rightPlane[B] = MVPMatrix[7]  - MVPMatrix[4];
	rightPlane[C] = MVPMatrix[11] - MVPMatrix[8];
	rightPlane[D] = MVPMatrix[15] - MVPMatrix[12];
 
	// Normalise the plane
	length = sqrtf(rightPlane[A] * rightPlane[A] + rightPlane[B] * rightPlane[B] + rightPlane[C] * rightPlane[C]);
	rightPlane[A] /= length;
	rightPlane[B] /= length;
	rightPlane[C] /= length;
	rightPlane[D] /= length;
 
	distance = rightPlane[A] * xPos + rightPlane[B] * yPos + rightPlane[C] * zPos + rightPlane[D];
	if (distance <= -radius)
	{
		return false; // Bounding sphere is completely outside the right plane
	}
 
	// Check the point's location with respect to the bottom plane of our viewing frustum
	GLfloat bottomPlane[4];
	bottomPlane[A] = MVPMatrix[3]  + MVPMatrix[1];
	bottomPlane[B] = MVPMatrix[7]  + MVPMatrix[5];
	bottomPlane[C] = MVPMatrix[11] + MVPMatrix[9];
	bottomPlane[D] = MVPMatrix[15] + MVPMatrix[13];
 
	// Normalise the plane
	length = sqrtf(bottomPlane[A] * bottomPlane[A] + bottomPlane[B] * bottomPlane[B] + bottomPlane[C] * bottomPlane[C]);
	bottomPlane[A] /= length;
	bottomPlane[B] /= length;
	bottomPlane[C] /= length;
	bottomPlane[D] /= length;
 
	distance = bottomPlane[A] * xPos + bottomPlane[B] * yPos + bottomPlane[C] * zPos + bottomPlane[D];
	if (distance <= -radius)
	{
		return false; // Bounding sphere is completely outside the bottom plane
	}
 
	// Check the point's location with respect to the top plane of our viewing frustrum
	GLfloat topPlane[4];
	topPlane[A] = MVPMatrix[3]  - MVPMatrix[1];
	topPlane[B] = MVPMatrix[7]  - MVPMatrix[5];
	topPlane[C] = MVPMatrix[11] - MVPMatrix[9];
	topPlane[D] = MVPMatrix[15] - MVPMatrix[13];
 
	// Normalise the plane
	length = sqrtf(topPlane[A] * topPlane[A] + topPlane[B] * topPlane[B] + topPlane[C] * topPlane[C]);
	topPlane[A] /= length;
	topPlane[B] /= length;
	topPlane[C] /= length;
	topPlane[D] /= length;
 
	distance = topPlane[A] * xPos + topPlane[B] * yPos + topPlane[C] * zPos + topPlane[D];
	if (distance <= -radius)
	{
		return false; // Bounding sphere is completely outside the top plane
	}
 
	// Check the point's location with respect to the near plane of our viewing frustum
	GLfloat nearPlane[4];
	nearPlane[A] = MVPMatrix[3]  + MVPMatrix[2];
	nearPlane[B] = MVPMatrix[7]  + MVPMatrix[6];
	nearPlane[C] = MVPMatrix[11] + MVPMatrix[10];
	nearPlane[D] = MVPMatrix[15] + MVPMatrix[14];
 
	// Normalise the plane
	length = sqrtf(nearPlane[A] * nearPlane[A] + nearPlane[B] * nearPlane[B] + nearPlane[C] * nearPlane[C]);
	nearPlane[A] /= length;
	nearPlane[B] /= length;
	nearPlane[C] /= length;
	nearPlane[D] /= length;
 
	distance = nearPlane[A] * xPos + nearPlane[B] * yPos + nearPlane[C] * zPos + nearPlane[D];
	if (distance <= -radius)
	{
		return false; // Bounding sphere is completely outside the near plane
	}
 
	// Check the point's location with respect to the far plane of our viewing frustum
	GLfloat farPlane[4];
	farPlane[A] = MVPMatrix[3]  - MVPMatrix[2];
	farPlane[B] = MVPMatrix[7]  - MVPMatrix[6];
	farPlane[C] = MVPMatrix[11] - MVPMatrix[10];
	farPlane[D] = MVPMatrix[15] - MVPMatrix[14];
 
	// Normalise the plane
	length = sqrtf(farPlane[A] * farPlane[A] + farPlane[B] * farPlane[B] + farPlane[C] * farPlane[C]);
	farPlane[A] /= length;
	farPlane[B] /= length;
	farPlane[C] /= length;
	farPlane[D] /= length;
 
	distance = farPlane[A] * xPos + farPlane[B] * yPos + farPlane[C] * zPos + farPlane[D];
	if (distance <= -radius)
	{
		return false; // Bounding sphere is completely outside the far plane
	}
 
	// If we got here, then the bounding sphere is within at least all six sides of the view frustum, so it's visible and we should draw it!
	return true;
}

If you’re not sure how to get the ModelViewProjection matrix, you can calculate it by mulitplying the Projection matrix by the ModelView matrix (in that specific order!).

So in OpenGL fixed-pipeline code, you could get it into a 16 element array like this:

// Get the Projection matrix
GLfloat projectionMatrix[16];
glGetFloatv(GL_PROJECTION_MATRIX, projectionMatrix);
 
// Get the ModelView matrix
GLfloat modelViewMatrix[16];
glGetFloatv(GL_MODELVIEW_MATRIX, MVMatrix);
 
// To calculate the ModelViewProjection matrix...
glMatrixMode(GL_PROJECTION);                          // Set our mode to the Projection matrix
glPushMatrix();                                       // Save a copy
	glMultMatrixf(modelViewMatrix);               // Multiply the current matrix (i.e. the Projection matrix) by our copy of the ModelView matrix and store the result in the Projection Matrix
	GLfloat modelViewProjectionMatrix[16];        // Create an array to hold this ModelViewProjection matrix
	glGetFloatv(GL_PROJECTION_MATRIX, MVPMatrix); // Grab our ModelViewProjection matrix (which was stored in the Projection matrix)
glPopMatrix();                                        // Restore our original Projection matrix by discarding the top level we used to calculate the MVP matrix

While if you were working from the OpenGL SuperBible 5th Edition, you could just throw it into the function like this:

bool vis = objectVisible(transformPipeline.GetModelViewProjectionMatrix(), some-x-vertex, some-y-vertex, some-z-vertex, some-bounding-radius);

Cheers!

Comments
4 Comments »
Categories
Imagery, OpenGL
Tags
, , , , , , ,
Comments rss Comments rss
Trackback Trackback