#### The Problem

When 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!

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:

- An array of 16 floating point values which specify the ModelViewProjection Matrix
- The x position of the central point
- The y position of the central point
- The z position of the central point
- 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 |
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:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// 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:

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

Cheers!

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.

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):

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 :)

Thank you, very informative, I hope I can give a little back in return one day!

Thank you, excellent tutorial!

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.

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!

Hello.

Thanks for the nice tutorial.

I have a question. Does it matter which space should the center of the sphere should be ?

As you are testing it against MVP matrix, shouldn’t the centre point as well be on clip space ? And how did you compute the radius ?

Hi Rath,

The simple fact of the matter is that I wrote this so long ago I have no idea about it anymore! As the planes get calculated from the MVP you’d expect everything to be in clip-space, I believe.

As such, the radius should also be in clip-space – so you should be able to take the difference between the world-space centre of your object and the world-space bounding sphere (aka world-space radius) and then multiply that by the MVP to get it in clip-space and pass that in so the units all match up. I think…

As mentioned in previous comments, I took this from “Beginning OpenGL Game Programming (1st ed, p243)” – if what I’ve suggested isn’t doing the job then perhaps take a look at that.

Hope you get it sorted!