Tag Archives: Culling

Cull Levels

These are the different levels culling algorithms can work on.

Triangle Level

Description: Determine for each triangle if it should be culled or not.
Primary goal: Minimize triangle count.
Culling technique example: BSP 
Usage: Not used anymore, cost to much CPU.

Object Level

Description: Check each object (a group of triangles in one buffer) if they should be culled or not.
Primary goal: Minimize triangle count and keep state changes low.
Culling technique example: View Frustum Culling of Bounding Box Hierarchies
Usage: Often used.

Batch Level

Description: Will check whole batches (a group of objects in one buffer)  if they should be culled or not.
Primary goal: Minimize draw calls and triangle count.
Culling technique example:  Uniform Grid Culling
Usage: Often used.

Basic Culling Techniques

The best optimization when rendering is to not render anything unnecessary. And that is what culling is about, to find out what can be skipped when rendering because it cannot be visible anyway.  Below are the basic culling techniques which most renderers’ implements. The image is from a course slide.

Culling Techniques

Back Face Culling

Faces that faces away from the camera can not be visible on the screen so they don’t need to be drawn. This is so often used that it’s implemented by the hardware. It roughly cuts the amount of faces drawn in half. Just remember to turn it on!

View frustum Culling

The faces that is outside the view frustum can not be visible on the screen (we don’t bother about reflections now) so they can be culled. This check is done by checking if the geometries bounding volume is outside the view frustum volume or not. So the check will not be done on every face, as that would cost to much. Sometimes, the view frustum culling can cost more than what is gain ( for example when doing instancing). One way to speed up view frustum culling is to use a suitable spatial structure for the scene (octree, BSP or so).

All kind of bounding volume test that you can imagine can be found on this page:
http://www.realtimerendering.com/intersections.html

Info about frustum culling:
http://www.flipcode.com/archives/Frustum_Culling.shtml

Portal Culling

A technique that divides the scene into cells with portals between. When rendering, the camera will be in one of the rooms and that room will be rendered normally. But for each portal that is visible in the room a view frustum is set up for the size of the portal and then the room behind it is rendered. This will work recursively. The result will be that a lot of geometry can be culled by view frustum culling when rendering the other rooms. A very useful technique for indoor scenes.

Detail Culling

When a geometry is so far away that it’s not visible then there is no need to draw it at all so it can safely be culled. A more advanced scheme of detail culling that decreases the amount of details with the distance is LOD (level of detail).

Occlusion Culling

The hardest culling technique to implement. Geometry that is occluded by other geometry does not need to be rendered. One solution is to use the Z-buffer and sort the geometry in a front to back order. But this does not always work and all pixels needs to be checked against the Z-buffer so it will be costly for big scenes. Better occlusion culling techniques culls the geometry before it’s even sent to the GPU.

A good link to a couple of occlusion culling techniques
http://www.gamasutra.com/features/19991109/moller_haines_01.htm

Scene Graph

A scene graph is a tree structure that tries to structure the objects in a scene accordingly to transformations, textures, materials and much more instead of just the geometrical representation of objects like for example a quadtree does. All games does contain a scene graph in some way, in the most simple form it could just be a root node and all other rendered objects as child nodes to the root node.

Here’s a list of useful links concerning scene graphs. Most links are borrowed from a post on gamedev.net but copied to this post so that I could remove broken links and include new ones.

  • Scene Graph Basics
  • Scene Graph design/implementation issues/notes etc
  • SG State Sorting
  • Shader/Material System/Integration
  • Optimizations for scene graphs
  • Spatialization
  • Most of this list was copied from the following gamedev.net forum thread.
    http://www.gamedev.net/community/forums/topic.asp?topic_id=349829

    Quadtree

    Nearly the same as a Octree but instead of dividing the space in cuboids in 3D it’s rectangles in 2D space. This is useful for rendering terrain and you want to cull a lot of the terrain fast.

    Example of the creation of a quadtree

    A visual demonstration of a quadtree used for fast collision detection:
    http://lab.polygonal.de/2007/09/09/quadtree-demonstration/

    Introduction to quadtrees and sample code:
    http://www.gamedev.net/reference/programming/features/quadtrees/

    More info about quadtrees, including source:
    http://www.kyleschouviller.com/wsuxna/quadtree-source-included/