Running on Empty

The few things I know, I like to share.

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.

part13.jpg

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.

part13-frustum-culling.jpg

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

 part13-bounding-box.jpg

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

part13-frustum-culling-bounding-box.jpg

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.

About these ads

February 18, 2008 - Posted by | C#, GameComponent, XBOX360, XNA

10 Comments »

  1. These are brilliant, it’s really given me a much deeper understanding of exactly how an engine and a game are composed and will be invaluable when I start on my own projects.
    Gonna spread the word a bit about this series, maybe get some constructive comments in here.

    Comment by kt | February 20, 2008 | Reply

  2. This stuff is great. Whens the next installment? I agree that you should not bother with showing the code unless it is core.

    Comment by Steven | February 21, 2008 | Reply

  3. Thank you Steven and kt, I really appreciate your comments.

    Steven, I agree, the direction I want to take this series is more in depth theory. Code for the sake of showing code is not always helpful. I can post code anytime, it is the ideas behind the code that are important. As for the next installment, I am writing as fast as possible, I’m really excited to see more and more people getting to see some of the details of a game engine.

    kt, I’m really not sure this series is to the point of brilliance yet. I do appreciate the offer for comments though. It is very important to get good peer reviews.

    Comment by roecode | February 21, 2008 | Reply

  4. I think you might find my forum post & the response by ShawMishrak very interesting. (Not that I want to change your direction of articles!)

    http://forums.xna.com/thread/38553.aspx

    Comment by gorky | February 21, 2008 | Reply

  5. Thank you Gorky for your informed suggestion. I do appreciate your comment, however I do find this very interesting, since I tried Occlusion culling without the sort and failed.

    It makes a lot of sense if you think about it. The video card has no way of knowing you want to draw something over the top of the current object later. So you MUST ALWAYS draw closer elements first in order for the occlusion test to work.

    Comment by roecode | February 21, 2008 | Reply

  6. No problem.
    It’s always good to have multiple tricks in ones bag!

    Comment by gorky | February 21, 2008 | Reply

  7. If I may suggest simply adding more in depth theory and keeping the code levels the same? Personally I find it invaluable to see more difficult theory put to practice.

    Either case I’m sure the tutorials will continue to be a solid base, great work!

    Comment by protatoe | February 26, 2008 | Reply

  8. protatoe,
    I will be happy to go into more theory and will support that with code. I don’t think I am going to try to post all the code for any given example. Rather, I will release code along with each entry. It means entries will become less, but with more content.

    I am trying to strike a balance between theory and practice. Theory is great, but doesn’t make games. I am writing this blog to help indie developers make better games, because I want to play them.

    Comment by roecode | February 26, 2008 | Reply

  9. [...] Part 13, Occlusion Culling and Frustum Culling [...]

    Pingback by UH COSC Interactive Game Development » XNA Game Engine Development | May 21, 2008 | Reply

  10. Great article.

    If you guys want some more theory, check out Chap. 29 of the GPU Gems 5 book that is now available online.

    Chapter 29. Efficient Occlusion Culling –
    http://http.developer.nvidia.com/GPUGems/gpugems_ch29.html

    Comment by GravitySpec | July 24, 2008 | Reply


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: