How to draw only visible models of the game?

Question

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

Answer 1

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:

Answer 2

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.

Answer 3

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.

Answer 4

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