How to draw only visible models of the game?

Suppose I have an array of models, each having it’s own “position” in the world space (scale*translation matrix). And I have an orthogonal camera. How can I test if model is “visible”, i.e. is in the range of the camera? Like this:

        +--------------+
|              |
xxxxxxxx|xxxxxxxxxxxxxx|xxxxxxxxx
|              |
+--------------+


I want to know whether x is in a frame or not. Thank you very much in advance, I know it should be a fairly simple (if not trivial) task :)

• You can probably find your answer with some more searching. Anyway, you want to cull the objects. Your ortho camera creates a box, and it's probably axis-aligned; look for bounding box collision tests for the logic. Jan 2, 2012 at 15:26
• @stephelton Searching for answers with search engines implies that you have clearly defined your question. I didn’t knew my problem is somehow related to collision detection :)
– oddy
Jan 2, 2012 at 16:06
• That's why I tried to drop you a few keywords to use :) Jan 2, 2012 at 17:03

Here's one way to do it if you don't mind taking advantage of XNA's API, which should work for every case. I can think of a few alternatives but they would involve doing more calculations manually, by taking advantage of the fact that your camera is orthogonal (i.e. the BoundingFrustum is just a box too).

Step 1) Store BoundingSphere (or BoundingBox) for each model

You can create the BoundingSphere using the following helper method:

BoundingSphere boundingSphere = BoundingSphere.CreateFromPoints(model.Vertices);


Ideally this should be done in the content processor and stored in the model, but you can also do it at load time. Don't forget to also Transform the BoundingSphere whenever you move the model.

Step 2) Create a BoundingFrustum for your camera

The constructor takes the ViewProrjectionMatrix:

BoundingFrustum frustum = new BoundingFrustum(viewMatrix * projectionMatrix);


Step 3) Check for Intersection

Draw only the models whose BoundingSpheres intersect (or are contained) by the BoundingFrustum:

models.Where(m => frustum.Contains(m.BoundingSphere) != ContainmentType.Disjoint).Draw();


Extra Notes (Edit)

I'd like to add a few notes. First the BoundingFrustum check is the simplest way to implement it because it's already provided for you by XNA. But it's not the most efficient for this case because, since your camera is orthogonal the frustum could be stored as a normal BoundingBox. Unfortunately there's no built in way to get this BoundingBox calculated for you automatically. Personally, I wouldn't bother with it until I noticed any performance issues.

Also, one advantage of using a BoundingSphere versus a BoundingBox for your models (like I commented on Ciarian's post) is that you can easily "move it along" with the model (even when it rotates or scales). This is because for translation you only need to move the center of the sphere, for scaling you only need to scale the radius, and for rotation you don't need to do anything. It's so simple that XNA already has a method for it, i.e. BoundingSphere.Transform().

The BoundingBox class on the other hand, doesn't have this facility because it must remain axis aligned. To properly transform an axis aligned bounding box, you need to transform all of its corners and then fit a new bounding box around them!

Some people may tell you to simply transform the BoundingBox's Min and Max values, but that is not correct and you'd run into trouble with transformed models - this is a very common pitfall. I repeat,don't transform an AABB just by transforming its Min/Max values. I made this picture that shows this problem in 2D but it's exactly the same thing in 3D:

• That’s perfect. My models are more like cubes so I probably try to create BoundingBox but that does not change your answer in no way. Thank you.
– oddy
Jan 2, 2012 at 16:10
• Added a few extra notes, but just moved them to the main post. Jan 2, 2012 at 16:27
• @oddy As for your models being more like cubes, a BoundingSphere might indeed not be the best fit. But even if they don't fit the models perfectly, that might not be a problem. It would if you were using them for collision detection, but since it's just for culling, using the less accurate BoundingSphere might outweight having to handle BoundingBox transformations correctly and work just as well. Jan 2, 2012 at 16:57
• Yeah, few minutes ago I read about performance issues related to non-aligned bounding boxes on create.msdn forum. AABB is a bit harder to implement so BoundingSphere, been invariant to rotation, is in good balance between performance and simplicity. Thank you again, David :)
– oddy
Jan 2, 2012 at 17:08
• It actually worked! :D I’m storing BoundingSphere in Tag property of the ModelContent in my pipeline processor as you suggested.
– oddy
Jan 2, 2012 at 17:31

Another possibility in addition to the boundingbox/sphere techniques given above is to use an occlusion query.

Basically how it works is you render a low quality version (unshaded, untextured, possibly just a bounding box itself) and you check to see if there where any fragments actually written. If there where you go ahead and render the full mesh otherwise you can toss out the mesh.

The advantage to this is that if you have a mesh behind an object but still in your fov then it wont get rendered. Of course in order for that to be really effective you need depth-last sorting of your objects (except the transparent ones which are depth-first unless your using some kind of order independent transparency). Transparency ordering is vastly helped by decent spacial data structures.

OpenGL has dedicated occlusion query api functions. I'm not sure about XNA/Direct3D.

In addition to that if you have your meshes stored in a decent spacial data structure (ie BSPs or Octrees) you will probably find that there are quick ways to throw out entire chunks of areas. For example the regions behind your camera can be pruned. In an Octree you could render the entire cube region as just a cube in an occlusion query and see if that entire region needs to be processed at all which would let you skip even bothering to check bounding boxes.

Finally be careful that very large meshes or ones that cross boundaries don't get cut. You could find that you need to calculate the bounding box of the region itself as being bigger than the actual region if you have a large mesh that's half off the region. A simple hack would be to just add the largest bounding box to the regions size.

So basically you can combine all of the above into the following steps:

1. Cull entire regions from BSP/Octree/Quadtree.

2. Perform quick bound checking for more stuff to drop.

3. Render scene depth sorted with occlusion tests and drop anything not rendered.

You can also look at using different level of detail meshes (LODs) based on the distance from the camera (or generating them at real time using geometry/tessellation sharers.

If its an othogonal projection then the Z co-ordinate can be ignored and you can treat it as a 2D bounding box collision problem. Each object should have a bounding box computed for it. You can do this at startup if the objects don't move. The check for trivial rejection using box to box is faster than box to spheres/circles.

Good empirical test and algorithm shown here:

http://www.h3xed.com/programming/bounding-box-vs-bounding-circle-collision-detection-performance-as3

As Dave rightly comments below, moving and rotating the object is more expensive with a bounding box. However if you are doing more drawing ops than update ops, then the trivial reject test is sure to be faster with the BB. With a circle, there are 3 multiplications to compare the distance between two points with a radius value in 2D.

"Final" edit: Test circle vs bounding box trivial reject on your platform for comparison. On a recent C++ test, the two performed more or less the same.

• But a BoundingSphere is easier to transform when the object moves or scales (just change position and radius). Also, rotation also has no effect on the BoundingSphere. On the other hand a BoundingBox needs to be completely recalculated when the object rotates or scales because of its need to remain axis aligned. Jan 2, 2012 at 16:03
• @ciaran David answered my question already. But thank you for the link, hope that means that using BoundingBox will improve performance to some extent :)
– oddy
Jan 2, 2012 at 16:14
• @oddy Read the amendment I made to my post, and then decide if it's worth the trouble. Jan 2, 2012 at 16:55
• @David Your picture of the rotating 2D sprite is good. But it describes a problem that canbe avoided. I would make the bounding boxes square in the first place. Therefore rotations would not have a performance hit. And we don't care about the BB being oversized because we are doing trivial rejection of large numbers of objects. This technique works well for collision detection and drawing. The objects that remain can be put through a more accurate test. Jan 2, 2012 at 17:55
• @Ciarian I can agree with most of your post although I still see the benefits as negligible. But the part where you said this technique works well for collision detection is obviously wrong. Try fitting a square bounding box around a 100x1x1 sort of model (e.g. something like a very thin and long pencil model) and you'd get a huge 100x100x100 bounding box with the model occupying 0,01% of the space. Granted that a bounding sphere would fare horribly too, this sort of bounding box would be even worse. Imagine using that for collision detection! Jan 2, 2012 at 18:05

Just thought of this now, if you have your for loop, and a camera in your draw statement make it like so:

for(int y = camera.pos.y -= viewHeight / 2; y < camera.pos.y + viewHeight / 2; y++)
for(int x = camera.pos.x -= viewWidth / 2; x < camera.pos.x + viewWidth / 2; x++)
sprite.draw(x, y);