Checking Visibility and Performing Rough Culling
Now that all of the objects have been placed in their proper positions , it is time to decide which objects need to be rendered in the current scene. This process is referred to as culling. Three predominate culling techniques are in use today: Binary Space Partioning (BSP), Portal, and Quadtree.
Culling Techniques
The BSP technique works by dividing and subdividing the entire database and everything in it based on separating planes. By positioning the planes so that they divide areas such that objects on one side of the plane are visible and objects on the opposite are not, we can rapidly work our way through the tree and find which objects are visible. Although this technique is incredibly fast during execution, it does have its drawbacks. BSP works best for indoor areas where walls (typically orthogonal to each other) divide the world up into small sections (e.g., rooms). Separating planes fall naturally along these walls since objects on one side of a wall tend not to be visible from the opposite side of the wall. If a separating plane passes through an object, we also need to subdivide the object into two pieces. Each piece has visibility only on one side of the plane. The intelligent placing of these separating planes typically calls for an experienced BSP model builder and the proper modeling tools geared toward BSP maps.
The second technique is Portal culling. A portal system is designed for indoor maps where each location on the map is in a room and portals into neighboring rooms exist. The portals could be doors, windows , or any other opening that permits visibility out of the current room. In this system, only those objects that are within the room or visible through the portals need to be drawn. The checking is handled recursively so that if a second portal is in view in an adjacent room, we continue on to determine what is visible through that portal. This continues until no portals are in view that have not been processed . This system is extremely fast, but is limited to indoor scenes only.
The final technique is the Quadtree system or its derivative, the Octtree. The Quadtree technique recursively divides the world into four quadrants. Each quadrant is then subdivided the same way. This continues until a specified recursive level or quadrant size is reached. The Octtree technique works the same way, but in three dimensions. If the world you are modeling has a lot of detail in the vertical axis, it might come into play. Instead of dividing each square area into quadrants, each cubic area is divided into eight cubes (i.e., 222 rather than 22). If your world is relatively flat, it is better to stick with a Quadtree to simplify and speed up your culling.
Implementing a Quadtree
Figure 3 “1 is an illustration of traversing a Quadtree structure. The trapezoid in the upper-left corner represents the viewing frustum. If a quad does not intersect the frustum at all, that quad and all of its children are considered culled. If a quad is completely within the frustum , it and all of its children are considered visible. Only when a quad is partly within the frustum does culling continue by checking each of the child quads . This recursion continues until every quad is completely within the frustum or is the lowest level quad. When a quad is found to be visible, all of the objects within the quad are marked as visible.
Figure 3 “1: Quadtree example
The Quad class (shown in Listing 3 “2) encapsulates the nature of a Quadtree node. Each node has a rectangle that defines the axis-aligned boundaries of the quad, a list of objects that occupy the node, and references for any parent and child nodes.
 |
public class Quad : IDispoable { private Rect m_Bounds; private Quad m_NorthEast = null; private Quad m_NorthWest = null; private Quad m_SouthWest = null; private Quad m_SouthEast = null; private Quad m_Parent = null; private int m_nLevel; private SortedList m_Objects; private float m_fRadius; private Vector3 m_vPosition; private string m_sName; private static Quad m_BaseQuad = null; public Rectangle Bounds { get { return m_Bounds; } } public string Name { get { return m_sName; } } public void Quad( Rectangle bounds, int level, int maxlevel, Quad parent ) { ... }; public void AddObject( Object3D obj ) { ... }; public void RemoveObject( Object3D obj ) { ... }; public void Cull( Camera cam ) { ... }; public void Update( Object3D obj ) { ... }; public void Dispose() { ... }; } | |
We ll start by looking at the constructor of the class (see Listing 3 “3) to see how the tree is built. The constructor initializes itself and then checks to see if the maximum tree level has been reached yet. If this is the very first quad to be initialized, we store the static reference to the base quad. If this is not the first quad initialized , it creates the four smaller quads at its child level. The bounding rectangle for each of the child quads is calculated as one quarter of the quad. The level for the child quad is incremented so that the child is created at the next recursive level. The position at the center of the quad and the radius of a circle around the quad will be used in the future for a quick test to see if an object is within the quad.
| |
Public void Quad ( Rect bounds, int level, int maxlevel, Quad parent ) { if ( m_BaseQuad == null ) { m_BaseQuad = this; } m_Bounds = bounds; m_n Level = level; m_Parent = parent; m_Objects = new SortedList(); m_sName = "L" + level + ":X" + bounds.Left + "Y" + bounds.Top; m_vPosition.X = (bounds.Left + bounds. Right) / 2. 0f; m_vPosition.Y = 0.0f; m_vPosition.Z = (bounds. Top + bounds. Bottom) / 2. 0f; double dx = bounds. Width; double dz = bounds.Height; m_fRadius = (float)Math.Sqrt( dx * dx + dz * dz ) / 2. 0f; if (level < maxlevel) { int nHalfHeight = dz / 2; int nHalfWidth = dx / 2; m_NorthEast = new Quad ( new Rectangle(bounds.Left + nHalfWidth, bounds.Top, bounds.Right, bounds.Top + nHalfHeight), level+1, maxlevel); m_NorthWest = new Quad (new Rectangle (bounds.Left, bounds.Top, bounds.Left + nHalfWidth, bounds.Top + nHalfHeight), level+1, maxlevel); m_SouthWest = new Quad ( new Rectangle (bounds.Left, bounds.Top + nHalfHeight, bounds.Left + nHalfWidth, bounds.Bottom), level+1, maxlevel); m_SouthEast = new Quad (new Rectangle (bounds.Left + nHalfWidth, bounds.Top + nHalfHeight, bounds.Right, bounds.Bottom), level+1, maxlevel); } } | |
There are two methods for managing the objects that reside within the area of the quad: AddObject (Listing 3 “4) and RemoveObject (Listing 3 “5, shown a little later in this section). The AddObject method places a reference to an object into the quad s object list and into the object list of any child quad that the object appears within. Only top-level objects are added to the Quadtree since the culled state of the child objects are dependent on the culled state of the parent. Within this technique an object could be referenced in quite a few quads. Although this redundancy wastes a bit of memory, it makes up for this shortcoming with an increase in processing speed. Once the culling process determines that a quad is completely within view, we do not need to continue iterating down through the tree. We can simply run through the list of objects at this level of the tree and set them to the not culled state.
The method begins by checking to see that we actually were given an object. Assuming we were passed a valid object, it is time to check to ensure that the object is at least partially within this quad. If the object used to be in this quad, we remove it and pass the request back up to the parent quad for repositioning . If the object is in this quad, we check to see if the object is already on our list. If the object is new to the quad, it is added to the list and any valid child quads are informed about the object so that they may add the object to their list if applicable .
| |
public void AddObject( Object3D obj ) { if ( obj != null ) { if ( obj.InRect( m_Bounds ) ) { int nIndex = m_Objects.IndexOfKey( obj.Name ); try { if ( nIndex < 0 ) // Add object if we don't have it yet. { m_Objects.Add(obj.Name, obj ); obj.m_Quads.Add(this); if ( m_NorthEast != null && obj.InRect( m_NorthEast.Bounds ) ) { m_NorthEast.AddObject( obj ); } if ( m_NorthWest != null && obj.InRect( m_NorthWest.Bounds ) ) { m_NorthWest.AddObject( obj ); } if ( m_SouthWest != null && obj.InRect( m_SouthWest.Bounds ) ) { m_SouthWest.AddObject( obj ); } if ( m_SouthEast != null && obj.InRect( m_SouthEast.Bounds ) ) { m_SouthEast.AddObject( obj ); } } else { Console.AddLine("Attempt to add another " + obj.Name ); } } catch (DirectXException d3de) { Console.AddLine("Unable to add object" ); Console.AddLine(d3de.ErrorString); } catch ( Exception e ) { Console.AddLine("Unable to add object" ); Console.AddLine(e.Message); } } else { int nIndex = m_Objects.IndexOfKey( obj.Name ); if ( nIndex >= 0 ) // remove the object if we have it { RemoveObject( obj ); if ( m_Parent != null ) { m_Parent.AddObject( obj ); } } } } } } | |
The second quad method for manipulating objects is RemoveObject (Listing 3 “5). This method reverses the process and removes an object reference from the quad s list if it appears there. If it is in this quad s object list, then it will appear in one or more of the child quad object lists. The RemoveObject method is therefore called for each valid child quad. This method is needed when an object moves from one quad into another quad.
| |
public void RemoveObject ( Object3D obj ) { if ( obj != null ) { int nIndex = m_Objects.IndexOfKey( obj.Name ); if ( nIndex >= 0 ) { try { m_Objects. Remove ( obj.Name ); } catch { Console.AddLine( "failing while removing object from quad object list" ); } try { if ( obj.m_Quads.Count > 0 ) { obj.m_Quads.Clear(); } } catch { Console.AddLine( "failing while clearing objects quad list"); } m_Objects.RemoveAt( nIndex ); if ( m_NorthEast != null ) { m_NorthEast.RemoveObject( obj ); } if ( m_NorthWest != null ) { m_NorthWest.RemoveObject( obj ); } if ( m_SouthWest != null ) { m_SouthWest.RemoveObject( obj ); } if ( m_SouthEast != null ) { m_SouthEast.RemoveObject( obj ); } } } } | |
Implementing Culling
The Cull method (Listing 3 “6) determines which objects should be displayed and which should be culled. The method uses the CheckFrustum method of the Camera class to determine what portion of the quad s bounding rectangle is within the frustum. If the bounding rectangle is completely within the frustum, then we do not need to continue any further down this branch of the tree. All of the objects that are within this quad are marked as not culled (i.e., they are in sight). If the quad is completely outside the frustum, we do not need to do anything with it since all objects default to the culled state. Finally, if the quad is only partially within the frustum, we need to continue down the tree to the next level. Once we hit the bottom of the tree and we are only partially inside the frustum, we must treat the quad as inside.
| |
public void Cull( Camera cam ) { Object3D obj; int i; cam.Reset(); if ( m_Objects.Count > 0 ) { try { switch ( cam.CheckFrustum( m_vPosition, m_fRadius ) ) { case Camera.CullState.AllInside: for ( i = 0; i < m_Objects.Count; i++ ) { obj = (Object3D)m_Objects.GetByIndex(i); obj.Range = cam.GetDistance( obj ); obj.Culled = false; m_Objects.SetByIndex(i, obj); cam.AddVisibleObject( obj ); } break; case Camera.CullState.AllOutside: if ( m_Parent == null ) // i.e., if this is the root quad { goto case Camera.CullState.PartiallyIn; } // do nothing since the default state is true // (reset after each render), break; case Camera.CullState.PartiallyIn: if ( m_NorthEast != null ) { m_NorthEast.Cull( cam ); m_NorthWest.Cull( cam ); m_SouthWest.Cull( cam ); m_SouthEast.Cull( cam ); } else // If partially in at the bottom level treat as in. { for ( i = 0; i < m_Objects.Count; i++ ) { obj = (Object3D)m_Objects.GetByIndex(i); obj.Culled = false; m_Objects.SetByIndex(i, obj); cam.AddVisibleObject( obj ); } } break; } } catch (DirectXException d3de) { Console.AddLine("Unable to cull object" ); Console.AddLine (d3de.ErrorString); } catch ( Exception e ) { Console.AddLine("Unable to cull object" ); Console.AddLine(e.Message); } } | |
Since some objects will be moving throughout the environment, it will be necessary to update the list of objects that are held by the quads. The Update method (shown in Listing 3 “7) provides this service. A reference to the object that has moved is passed into the method as its argument. Since the object holds a collection of the quads that contain the object, we need to check each of these quads. If the object has left any of the quads, then a reset request is triggered. The object is removed from the quads and reinserted into the Quadtree.
| |
public void Update ( Object3D obj ) { bool bResetNeeded = false; try { // Only need to reset the quad for the object if it is // no longer in one of the quads. try { foreach ( Quad q in obj.m_Quads ) { try { if ( !obj.InRect( q.m_Bounds ) ) { bResetNeeded = true; } } catch { Console.AddLine("invalid quad in object quad list"); } } } catch { Console.AddLine("fails in foreach"); } try { if ( bResetNeeded ) { m_BaseQuad.RemoveObject( obj ); m_BaseQuad.AddObject( obj ); } } catch { Console.AddLine("fails in reset needed"); } } catch (DirectXException d3de) { Console.AddLine("Unable to update a Quad " + Name); Console.AddLine(d3de.ErrorString); } catch ( Exception e ) { Console.AddLine("Unable to update a Quad " + Name); Console.AddLine(e.Message); } } | |
The final method in the class at this point is the Dispose method, which is shown in Listing 3 “8. We have not allocated anything in the class that needs to be explicitly disposed of, so we pass the Dispose action on to the child quads only if they exist.
| |
public void Dispose() { if ( m_NorthEast != null ) m_NorthEast.Dispose(); if ( m_NorthWest != null ) m_NorthWest.Dispose(); if ( m_SouthWest != null ) m_SouthWest.Dispose(); if ( m_SouthEast != null ) m_SouthEast.Dispose(); } | |
EAN: 2147483647
Pages: 98