XNA Framework GameEngine Development. (Part 13, Occlusion Culling and Frustum Culling)

Introduction

Welcome to Part 13 of the XNA Framework GameEngine Development series.  Yet another slight departure from my planned series.  This article will focus on culling, both using the Frustum and OcclusionQuery.  I know I covered Culling in Part 12, but going back to look at that article I realized I was falling sadly short on explaination.  So rather than confuse readers by going back to make changes in previous articles, I will simply explain sections of code and release code with each sample.  Hopefully, this new format will be beneficial to readers.

Release

If you enjoy these articles please leave a comment, here is the sourcecode.  Eventually, I am going to run out of things to talk about, your feedback is very important to me and helps formulate future articles.

Built-in Frustum Culling

The frustum is an imaginary trapezoid that defines the area that a camera can view.  In general this trapezoid can be defined using a near plane, the far plane, and the field of view.  There are plenty of articles that you can find online that describe the frustum in far more elegant ways than I can, but I think of the frustum as the following.

Imagine you are looking out of a window in your room, in real physical terms, the distance you are sitting from that window is the same as the near plane distance.  If you moved closer to the window your near plane distance would be smaller, easy enough. 

The far plane is a little harder to describe, it is the farthest viewable distance that you can see.  It literally is a wall that sits out in space and covers up everything beyond.  Finally, there is the field of View, this is how wide your periferal vision extends.  Anybody who has looked through a telescope, camera lens, or binoculars should notice this.

So what does this mean to a game engine?  Quite simply if we dont see it in our frustum, we dont need to draw it.  Modern video cards do this very well, they simply do not render pixels that lay outside of the frustum, you should know however, the draw call is sent to the video card though. 

This is a very important distiction to make, depending on the video card to cull objects outside of the view frustum is not enough.  Why send instructions to the video card if it is just going to not draw an object?  So, we cull the items that never are going to be drawn before they go to the video card.

Frustum Culling

So the whole point of frustum culling is to reduce the number of objects we send to the video card to be drawn.  This is usually done by testing simple geometry for inclusion in the scene, enter the BoundingBox and BoundingSphere.  A BoundingBox or BoundingSphere is a very simple mathematical shape that we can use to test for inclusion in the frustum.  These shapes are just large enough to completely enclose the entire object.  See image below (Notice, the bounding box is a perfect square, even though the top and bottom sides of the random object do not touch the edge).

 

Now that we have a bounding box or sphere, we can get to some serious work.  See the image below for the new comparison.

Wow!  If you are thinking we just reduced the number of objects sent to the video card in this scene by half, you are correct. 

Obviously, this sort of culling is very important for scene optimization, so how do we get this magic to work in the Engine?

First, create an interface so that we can identify Cullable SceneObjects

using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Graphics;

namespace RoeEngine2.Interfaces
{
    /// <summary>
    /// Every RoeSceneObject that implements this interface will be culled using its bounding object.
    /// </summary>
    public interface IRoeCullable : IRoeSceneObject
    {
        bool DrawBoundingBox
        {
            get;
            set;
        }

        bool Culled
        {
            get;
            set;
        }

        bool BoundingBoxCreated
        {
            get;
        }

        BoundingBox BoundingBox
        {
            get;
        }

        BoundingBox GetBoundingBoxTransformed();
    }
}

Next, implement DrawCulling in the Node.cs class.

        public virtual void DrawCulling(GameTime gameTime)
        {
            _nodes.ForEach(
               delegate(Node node)
               {
                   node.DrawCulling(gameTime);
               });
        }

Do the same in the SceneObjectNode.cs class, but this time do some work if the sceneobject is cullable.

        public override void DrawCulling(GameTime gameTime)
        {
            if (SceneObject is IRoeCullable)
            {
                ((IRoeCullable)SceneObject).Culled = false;
                if (CameraManager.ActiveCamera.Frustum.Contains(((IRoeCullable)SceneObject).GetBoundingBoxTransformed()) == ContainmentType.Disjoint)
                {
                    ((IRoeCullable)SceneObject).Culled = true;
                }
                else
                {
                    SceneObject.DrawCulling(gameTime);
                }
            }
        }

Implement DrawCulling in the SceneGraphManager.cs as well.  I am also going to implement a static int so we can indicate if anything has been culled.

 public static int culled = 0;
        
 public static void DrawCulling(GameTime gameTime)
        {
            culled = 0;
            occluded = 0;
            _root.DrawCulling(gameTime);
        }

Finally in RoeSceneObject add a virtual so we can override it with cullable objects and draw culling objects.

        public virtual void DrawCulling(GameTime gameTime)
        {

        }

That is pretty much all there is to do for culling.  The real work is done by the SceneObjectNode class.  The line CameraManager.ActiveCamera.Frustum.Contains(((IRoeCullable)SceneObject).GetBoundingBoxTransformed()) == ContainmentType.Disjoint essentially is testing to see if the cullable object is intersecting/within the frustum and simply marking the object as culled if it is not.  Now we can test for culled when we draw.

Add the following code to SceneObjectNode.cs

        public override void Draw(GameTime gameTime)
        {
            if (SceneObject is IRoeCullable && ((IRoeCullable)SceneObject).Culled)
            {
                SceneGraphManager.culled++;
            }         
            else
            {
                SceneObject.Draw(gameTime);
            }
        }

Excellent, that is all there is to do for frustum culling.

Occlusion Culling

Now this is a little bit more complex form of culling, but it is a very important concept to learn for good culling and portal scene management.  Occlusion is what happens when one object passes in front of another object.  In reality the object that was occluded still exists and the same is true in our engine, accept in our engine we no longer have to draw the complex geometry of the occluded object.

This is usually accomplished by drawing less geometrically complex and somewhat larger scale object.  We are obviously drawing more geometry per object, but hopefully less geometry overall by doing this simple test.  In this engine, I will accomplish this task in two “passes”.  First a pass of simple geometry to test for occlusion, and second the final geometry for the scene.

I start by creating a simple interface to identify Occlusion sceneobjects

using System;
using System.Collections.Generic;
using System.Text;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework;

namespace RoeEngine2.Interfaces
{
    /// <summary>
    /// Test if an object is occluded in the scene.
    /// </summary>
    public interface IRoeOcclusion : IRoeCullable, IRoeSceneObject
    {
        string OcclusionModelName
        {
            get;
            set;
        }

        OcclusionQuery Query
        {
            get;
        }

        bool Occluded
        {
            get;
            set;
        }

        void DrawCulling(GameTime gameTime);
    }
}

Notice IRoeOcclusion also implements IRoeCullable, this is very important, you NEVER EVER want to Occlusion cull something that is already Frustum culled.  A simple rule to live by.

Since occlusion culling is a geometry based technique, we also need to implement an object modle for the occluder.  Finally, we want to force the object to implement the DrawCulling override.

IT IS VERY IMPORTANT TO NOTE, when doing occlusion culling your objects must be sorted by their distance to the camera.  You want to draw objects nearer to the camera first, this will reduce overdraw in the scene and make your graphics card very happy.  Also, occlusion culling just doesn’t work if you dont.  So we have to make our Node class an IComparable, I wont explain all of this, if you have questions about what is going on feel free to use MSN.

Node.cs should implement IComparable and add the following code

        int IComparable.CompareTo(object obj)
        {
            SceneObjectNode node1 = (SceneObjectNode)this; 
            SceneObjectNode node2 = (SceneObjectNode)obj;

            if (node1.SceneObject.Distance < node2.SceneObject.Distance)
                return -1;
            else if (node1.SceneObject.Distance > node2.SceneObject.Distance)
                return 1;
            else
                return 0;
        }

        public void Sort()
        {
            _nodes.Sort();
        }

In the SceneGraphManager.DrawCulling method add the following code

        public static void DrawCulling(GameTime gameTime)
        {
            _root.Sort();
            culled = 0;
            occluded = 0;
            _root.DrawCulling(gameTime);
        }

That is bascially all we really have to do to implement Occlusion culling, well all accept the real work.  Now we have to test for occlusion.  The very basic implementation looks something like this.

      OcclusionQuery query = new OcclusionQuery(EngineManager.Device);

      query.Begin();
      // Drawing simple objects, bounding areas, etc.
      query.End();

      // Do additional work here to provide enough time for the GPU to complete query execution.
      
      // Draw additional models
      if (query.IsComplete == true && query.PixelCount > )
      {
      // A non-zero pixel count means some of the low res model is visible
      // so let's draw the real version of it
      }

That isn’t so bad.  so now we can test occluders and simply not draw an object if it is occluded.  We can accomplish that task like this.

        public override void Draw(GameTime gameTime)
        {
            if (SceneObject is IRoeCullable && ((IRoeCullable)SceneObject).Culled)
            {
                SceneGraphManager.culled++;
            }
            else if (SceneObject is IRoeOcclusion && ((IRoeOcclusion)SceneObject).Occluded)
            {
                SceneGraphManager.occluded++;
            }            
            else
            {
                SceneObject.Draw(gameTime);
            }
        }

Please feel free to look at the code linked at the top of this page.  I will no longer add every line of code I write to the blog.

Conclusion

In this article I introduced Frustum and Occlusion Query culling.  These techniques are used to reduce the number of complex geomotry draw calls that we need to make to the graphics card.

I very much enjoy your comments, if you found something here that was helpful or interesting please leave some feedback.  Hope you are enjoying reading these articles as much as I am creating them.