Bounding Sphere Tree Culling - Computer Science Department

CSE 381 – Advanced Game Programming
Scene Management
Data Structures & Algorithms
World of Warcraft, Blizzard
Common Types of Scene Graphs
• Bounding Sphere Trees
• Portals
• Binary Space Partitions
• Quadtrees
• Octrees
• Adaptive Binary Trees
Bounding Sphere Trees
Scene graph & frustum culling
Subdivides world hierarchically
Uses spherical regions
Leaves of tree contain bounding sphere of model
Models grouped in parent spheres
Groups grouped into larger spheres
Root sphere has entire scene
Bounding Sphere Tree Culling
1) Make root node the current node
2) If frustum collides with current node sphere:
a) if current node is a leaf, put in display list
b) else send each child node to Step 2) as current node
Spatial Partitioning Bonus
• Reduces what's sent to rendering system
• Reduces collision tests
• Only test models against models in the same group
– leaf vs. leaf
• First, world/map is divided into Sectors
– i.e. areas/zones
• Sectors are connected via Portals
– typically placed manually by level designers
Players and Portals
• Players move about level
• When player is in a Sector:
– send items in that sector for
frustum culling
• Players move between sectors
• Players may see from one
sector into another
Concave vs. Convex
• Sectors are typically Convex
– Why?
Designer Strategy
• Sectors are not typically uniformly shaped
– But must be closed geometry
• No intersecting faces
• No holes
• How can the game designer specify sectors?
– place portals
• placed as very thin box
– add occluders to level:
• walls, fences, buildings, (cannot be planes)
• separate and hide objects in sector from rest of level
– automatically calculate sectors
Solid vs. Hollow Objects
• Models are solid objects
– normals face out
• Rooms (interiors) are hollow
– normals face in
– may not be viewable from outside
• Combinations of these are used to
build levels
Occluders Mesh
• Laid out by level designer
• Joins all occluder meshes in one mesh. Ex:
– in modeler, combine and rename OCCLUDER_MESH
– specify all portals as PORTAL_...
– build and export the level mesh
• A low-res mesh
– simple wall geometry
– typically less than 200 triangles so cheap rendering
Exporting the Mesh Example
• Done using a script
1. Search for the OCCLUDERS_MESH
2. Invert OCCLUDERS_MESH normals
– i.e. make it solid
3. Subtract all PORTAL_*s from OCCLUDERS_MESH
4. Invert the normals for the resulting mesh
– i.e. make it hollow
5. Export the resulting mesh, the OCCLUDERS_MESH,
and the portals to a map file
Sector Generation
• Remember, this must be a closed geometry
• Walk through the vertices:
– visit all those in each closed geometry
– mark each group in common sector
What do you use it for?
• Sector testing. Ex: find the sector a point lies in
– Kind of like frustum culling
– Start at the root node
– Walk down to find sector
• Scene Graph Culling. Ex:
– render Occluder mesh (cheap)
– test portals against frustum
– render sectors connected to portals that pass
BSP Trees
• Binary Space Partition
– to determine what sector an object is in
• Each level uses splitter plane to divide into half spaces
– convex half spaces
• Three Types:
– regular, leafy, and solid node (SNBSP)
It's all about the splitter planes
• They separate objects
Alternative Representation
• B-Rep?
– boundary representation
BSPs help with collision stuff too
• Higher priorities for testing against stuff on the
same side
Object to Plane testing
• Dictates much of BSP construction
• To Build BSPs
– test objects against splitter
– put into different groups
Painter's Algorithm
• Uses regular BSP type
• Separates polygons by half-spaces
• Why?
– polygon-to-polygon occlusion testing
• We don't need this. Why?
– hardware does this anyway
• Good for sector testing
• Build them once:
– select starting splitter plane
– maintains nodes for each sector. Ex:
struct SnBSPNode
plane splitPlane;
// sector ID
SnBSPNode frontNode; NULL represents
SnBSPNode backNode;
hollow region
Portals vs. BSPs
• Commonly used together
• Think a hybrid scene graph
• Portals:
– good for scene graph culling (to reduce
• BSPs:
– good for collision test culling
• Partitions world in 2D
– used for 2D and 3D games
To build a quadtree
1. Compute AABB for each object
2. Compute AABB for entire scene, put objects into this
root node
a. Divide scene AABB into 4 boxes
• not necessarily the same size
b. Put each object in current parent node into a box child node
according to location
c. Repeat a-b until decomposition limit reached
Note: all objects end up in leaf nodes
– may choose to limit at most 2 objects per leaf
To use a quadtree
• Walk down the tree to test points
– for placing objects
• What’s this good for?
– What quads are currently in frustum?
• Scene graph culling
– How far are quads from camera
• LOD for terrain
• An extension of quadtrees
• Work well with outdoor scenes
– or scenes with large empty spaces
Octree Rendering
• Frustum cull as you move down the tree
1. Make root node test node
2. If test node is leaf
– Render leaf contents and exit
3. Else if node is not in frustum
– Exit
4. Else
– For each child node:
• Set child node to test node and go to step 2.
Node Confusion
• With Quad/Octrees, what if an object overlaps a
– split the geometry and put in two nodes?
– store object in common parent node?
• loose octree
– use Adaptive Binary Trees (ABT)?
• Nodes can overlap
• Nodes can change
• Good at managing dynamic geometry at runtime
• By the way, there are many other custom
techniques used as well
So which approach is best?
• There is no “best”?
• Modern game engines usually use hybrid
• Ex: Ogre3D
– Use BSPs for closed areas
– Use Octrees for open areas
Octrees Example
ABT Example
• A tutorial on Binary Space Partitioning Trees by Bruce F.
Naylor, Spatial Labs, Inc.

similar documents