XNA Lesson 1 -- Difficulty: Moderate

June 20th, 2007 -- View frustum culling and other optimizations

View frustum culling means to remove from the video card processing anything that the player would not be able to see anyway. Once a game has many different objects or a high poly count level, this becomes an absolute requirement. The good news is that the guys that made XNA knew this and gave us a handy little tool. The BoundingFrustum object lets us check if collision spheres, boxes, planes, and other frustums are colliding with our player's frustum.

Here is an example:

// A view frustum almost always is initialized with the ViewMatrix * ProjectionMatrix BoundingFrustum viewFrustum = new BoundingFrustum(ActivePlayer.ViewMatrix * ProjectionMatrix); // Check every entity in the game to see if it collides with the frustum. foreach (Entity sourceEntity in entityList) {     // Create a collision sphere at the entities location. Collision spheres have a     // relative location to their entity and this translates them to a world location.     BoundingSphere sourceSphere = new BoundingSphere(sourceEntity.Position,                                   sourceEntity.Model.Meshes[0].BoundingSphere.Radius);     // Checks if entity is in viewing range, if not it is not drawn     if (viewFrustum.Intersects(sourceSphere))         sourceEntity.Draw(gameTime); }

Note: Using a model.meshes[0] does not always result in a bounding sphere that will cover the entire model. You may have to create your own bounding sphere to encompass your entire model. This example is usually fine for simple collision checks to get your started. For a more refined game you may need to refine your bounding sphere.

A function similar to this would have to be placed in the game's main draw() function. Unless the player's view is always stationary, the creation of a new frustum every draw loop would be necessary as the frustum box, viewMatrix and ProjectionMatrix would always be changing.
For a good visual representation of this concept, check out Microsoft's page on it here.


A good way to optimize the game even furthur would be to separate a level or map into regions, and then only check entities in the region the player is in, and the ones adjacent to its sides and corners. This would mean that the game still has to check each entity, but checking a region is much faster than creating a sphere and doing the math for collision.
Above the line where the bounding sphere is created you could place something in, like this:

if ( ActivePlayer.CheckAdjacentRegions( sourceEntity ) == true )

The CheckAdjacentRegions function would actually be fairly easy to implement. Each update loop would require you to update the region each entity was in. Then the CheckAdjacentRegions() function could look something like:

// Make sure sourceEntity lies in an adjacent region. // This function returns false if the entity is too great // of a distance from 'this' entity. private bool CheckAdjacentRegions( Entity sourceEntity ) {     if ( sourceEntity.gridPosition.X < this.gridPosition.X - 1 )         return false;     if ( sourceEntity.gridPosition.X > this.gridPosition.X + 1 )         return false;     if ( sourceEntity.gridPosition.Y < this.gridPosition.Y - 1 )         return false;     if ( sourceEntity.gridPosition.Y > this.gridPosition.Y + 1 )         return false;     return true; }

A function like this may not work well for viewing if you had a small map because the size of the grid spaces would have to be the viewing distance you want your player to have, otherwise the player couldn't see someone only 1 space away! An alternative would be to check which adjacent spaces are in the player's FOV, and if the sourceEntity is not in one of those spaces, then they're not drawn. You would need a way to determine if a space was in a player's FOV however, you would likely need to check if any of the corners were in view. A grid setup also works perfectly for culling out collision checks, which brings us to our next XNA Tip.

Next