Scene Graph Visibility Culling

There are many useful operations that a scene graph system provides. Most critical operations involve graph traversals. Just like flattening a transform hierarchy for rendering, scene graphs are traversed to compute global object transforms. Some are also traversed to accumulate the render states when they are not leaf-node based. Sometimes they are traversed for a search to find all nodes of a particular type, and other times for specific individual nodes for game logic processing (that is, find all “door” nodes in a particular area).

One of the most important traversal operations is view culling. View culling is the process of removing from the render pipeline geometry that is not visible in the current view. Visibility-culling algorithms reduce the number of polygons sent down the rendering pipeline based on the simple principle that if something is not seen, it does not have to be drawn.

There are many popular algorithms for visibility culling in scene graphs. They can generally fall into the categories of backface culling, view frustum culling, occlusion culling, and portal culling.

Backface Culling

Backface culling is the simplest culling technique. It removes individual triangles in any given frame that are facing away from the viewer.

The idea is to treat polygons and triangles as essentially one-sided. If the polygon is turned so that the front surface is facing the viewer, then it is called frontfacing. Any polygons that are turned away are called backfacing. A frontfacing polygon needs to be rendered, but a backfacing polygon can be skipped. This step can be expected to cull roughly half of all the polygons in a given view (see Figure 15.5).

image from book
Figure 15.5: Backface culling applied to objects.

The basic test is that if the surface is normal and the vector formed to the viewer from the polygon is greater than 90 degrees (dot < 0.0), then the polygon must be backfacing and can be discarded (see Figure 15.6).

image from book
Figure 15.6: Backface culling single triangles.

There have been many optimizations developed for computing this test. Some attempt to speed surface-normal calculation; others transform the camera view vector into an object’s local space to minimize vertex transformation. Still others use quick screen space algorithms to determine face direction. With graphics hardware ultimately handling the face render, there is little need to directly implement backface culling because it is a feature of modern 3D graphics hardware. Also, it is supported directly in OpenGL, so we can simply enable it through OpenGL in our render engine by adding the state to the Appearance class as an object attribute and update the renderer to use it.

In OpenGL glEnable(GL_CULL_FACE) is used to enable backface culling. As with all states enabled and disabled using glEnable and glDisable, it is disabled by default. In addition, OpenGL is not limited to backface culling. The glCullFace command can be used to specify the type of face culling desired, when face culling is enabled.

View Frustum Culling

View frustum culling is culling that uses the current view frustum to determine what is unseen. Perhaps the most implemented form of culling, it is based on the idea that only the scene objects that are in the current view volume need be drawn. To fully understand view frustum culling, we must first define what a view frustum is.

View Frustum

The view frustum is the shape of the viewing volume of space that includes everything currently visible from the viewpoint. It is defined by six clipping planes in the shape of a pyramid with the top chopped off. The six planes are typically named Near, Far, Top, Bottom, Left, and Right (see Figure 15.7). The Near and Far clipping planes could theoretically be defined as the viewpoint and infinity, but in practice they are not. Usually the Near plane is defined to be at a close forward distance, such as 0.1, and the Far plane at some greater distance relevant to scene size, such as 1000.0.

image from book
Figure 15.7: The view frustum.

If a polygon is entirely outside the view frustum, it cannot be visible and can be discarded. If it is completely inside, it should be sent down the rendering pipeline. If it is partially inside, it may be clipped to the planes so that its outside parts are removed.

Testing each individual polygon as is done with backface culling is almost never done these days because of 3D objects’ complexity. Triangle count can be quite high because of the graphics hardware capabilities. Because the less-capable host CPU is doing the view frustum test, it would get bogged down testing so many triangles. Just as with 2D testing, pixel-to-pixel collision detection is usually preceded with a rectangle- or box-collision detection test to reduce overall tests. In 3D, per-triangle collision detection is first done with bounding volume tests.

Bounding Volumes

A bounding volume is a simplified approximation of the volume of a 3D object, used in, for example, view frustum culling. Although it is commonly a box, it can be almost any shape, such as a sphere, cylinder, or convex polyhedron (see Figure 15.8). Different shapes may be selected, depending on the nature of how the 3D object will be manipulated.

image from book
Figure 15.8: Example bounding volume types.

Often movable 3D objects will use a sphere because it requires minimal operations to update the sphere with the objects’ motion, whereas static 3D worlds fill space with boxes that fit tightly together.

In a simple version of view frustum culling, each 3D object’s bounding volume in the scene is tested against the six planes. Although this is a huge improvement over testing each individual polygon, the running cost of the algorithm scales linearly with scene object count. For a few hundred 3D objects, this may be okay, but for larger, more complex scenes, we can do much better than this by using a bounding volume hierarchy.

Bounding Volume Hierarchies

Bounding volume hierarchies are hierarchal data structures where each group node’s bounds surrounds all of its children’s bounds. Just as matrix hierarchies are a natural evolution for singly transformed 3D objects, bounding volume hierarchies help 3D object bounding volume tests scale to much larger 3D object groups.

There are two major types of bounding volume hierarchies—hierarchies that fit the underlining 3D objects as closely as possible, and spatial partitioning hierarchies that completely fill space so that every location within the hierarchies falls into at least one bounding volume.

Bounding volumes can start off simple but can quickly become complex, depending on the objects or scene, as shown in Figure 15.9 and Figure 15.10.

image from book
Figure 15.9: Simple bounding volume hierarchies.

image from book
Figure 15.10: Complex bounding volume hierarchies.

For view frustum culling, the bounding volume hierarchy is traversed top-down. If a node’s bounds are completely in the view frustum, that entire subgraph can be marked for rendering or added to the render bins. If a node’s bounds are completely out of the view frustum, the node and its remaining child graph can be skipped. If the bounds cross the frustum planes, then recursion continues on all of the children until done.

Spatial Partitioning Hierarchies

Spatial partitioning hierarchies typically subdivide 3D space into smaller sections using different dividing techniques, such as boxes or planes, and their resulting hierarchical organizational structures.

Two popular related techniques are the Quadtree and the Octree. Both use axis-aligned bounding boxes that are progressively subdivided into smaller boxes until some criteria is satisfied to stop the subdivision process (see Figure 15.11). This criteria is usually box size or number of objects contained in the box. Densely occupied areas will have many small bounds, whereas larger empty areas will be bounded with just one large box.

image from book
Figure 15.11: Quad tree spatial partitioning structure.

Occlusion Culling

Occlusion culling is a type of view culling where geometry that is occluded is not rendered, that is, geometry that is inside the view frustum but not visible in the final image because it is blocked from view by other geometry. This type of culling can offer an excellent performance gain for certain scenes with large numbers of 3D objects and large-size objects that block the view. An example case is a city scene, where large buildings block the view of many other large buildings.

Occlusion culling for static-world geometry can be precomputed somewhat, but for dynamic objects it is costly to determine totally correct occlusion culling. Finding occluded objects is akin to shadow algorithms and is typically more expensive to compute than the gain from removing the occluded objects. Other techniques such as cells and portals offer a good gaming alternative.

Cells and Portals

Full treatment of cells and portals are beyond the scope of this book but are mentioned because they are in growing use among 3D game renderers. The basic idea is to partition the world into chunks or cells, usually based on the geometry of the world. Portals connect the cells to each other, very much like nodes are connected by links in a graph structure. In the 3D world, the portals are typical doorways, windows, or other objects that the view can see through to other cells. The render pass begins in whatever cell the view is currently, and only needs to process this cell and any cells reachable through this cell’s portals. With a well-organized cell-and-portal system, the renderer will be able quickly to cull large portions of the surrounding world.



Practical Java Game Programming
Practical Java Game Programming (Charles River Media Game Development)
ISBN: 1584503262
EAN: 2147483647
Year: 2003
Pages: 171

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net