How To: Perform manual frustum culling

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.

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:

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

Cheers!

6 thoughts on “How To: Perform manual frustum culling”

  1. Hay this is pretty kickass. I’m going to need something like this for a project i’m working on.

    Did you ever start using asymmetric frustrums in your openGL? I’d love to chat about that as i’m having a bugger of a time of it.

    1. Glad you found it useful, I got it from Beginning OpenGL Game Programming (1st ed, p243).

      I never got around to asymmetric frustums as it happens because it turned out I didn’t particularly need anaglyphic displays, but I had a mess around with using multiple frustums earlier and it didn’t seem too bad (set first frustum, draw something, change to second frustum, draw again etc).

      I also played with setting the separate viewports for the left and right halves of the window (vertical divide in the middle) and drawing into each viewport using the separate frustums and that’s easily done as well. Kinda like on this page: http://www.songho.ca/opengl/gl_transform.html, but using a “virtual divide” instead of two separate windows (find the text: “An example of an asymmetric frustum” to see what I mean).

      This might be a good start on setting up asymetric frustums: http://www.orthostereo.com/geometryopengl.html

      The same page also says (with IOD = intraocular distance – i.e. how far you shift the frustums on the x-axis to match the eye separation):

      To set up an asymmetric frustum, the main thing is deciding how much to shift the frustum by. This is quite easy as long as we assume that we only want to move the camera by +/- IOD/2 along the X-axis. From the geometry it is evident that the ratio of frustum shift to the near clipping plane is equal to the ratio of IOD/2 to the distance from the screenplane.

      It’s definitely something I’d like to get sorted, so if you’d like to discuss and share code n’ stuff I’d be happy to do that – maybe between us we can get proper asymmetric anaglyphs working w/ minimum eye strain :)

  2. Thanks for the tutorial! :) Although you never mentioned whether this matrix was row or column major! Personally I took this approach, and experimented randomly until it works… >.< I'm yet a beginner at linear algebra. Initially it didn't, but after some tweaking I succeeded, so thanks! One thing though that I didn't have to normalize my planes… That only ruined it. So maybe I am doing something totally wrong… Oh well, no errors so far.

    1. Hmm, you’re right – something’s off with this… The clipping often occurs too early (while the bounding sphere is still visible) and the near clipping doesn’t seem to work at all.

      As for the matrices, OpenGL returns matrices in column-major format, so of the array of 16 values, 0..3 / 4..7 / 8..11 / 12..15 will be the columns.

      I’ll work on it and get back to you hopefully soon.

      Cheers!

Leave a Reply

Your email address will not be published.