CHC - Coherent Hierarchical Culling

Abstract

On this page a demo for the Coherent Hierarchical Culling algorithm described in the paper "Coherent Hierarchical Culling: Hardware Occlusion Queries Made Useful" by Jiri Bittner, Michael Wimmer, Harald Piringer and Werner Purgathofer is presented. The demo presented here is on the CD of the XXXXXXX book (to appear in 2005), accompanying the article: "Hardware Occlusion Queries Made Useful". The author expects prior knowledge of computer graphics, an understanding of the occlusion query construct and of the Coherent Hierarchical Culling algorithm as described in the paper.

The Algorithm

One problem with hardware occlusion queries are stalls of the cpu. We need to get the query result back from the graphics card and this requires a round trip of the graphics hardware(issuing the query, waiting for completion and reading the result back) and destroys the asynchronous execution of code on the CPU and GPU. The Coherent Hierarchical Culling algorithm tries to minimize this stalls by using the wait time for issuing other, unrelated occlusion queries.

Implementation

In this chapter we will develop the actual code of the demo and explain which design considerations where made and why. The implementation of the algorithm is straight forward. We need 3 data structures:

A hierarchical structure to hold the bounding box hierarchie: kd-tree, scenegraph, ...

A queue to hold the currently running occlusion queries

A stack or even better a priority queue to hold the nodes of our hierarchy we need to traverse

Given the pseudo-code from the article:

TraverseNode(node) 
{
  if ( IsLeaf(node) )
    Render(node);
  else
    TraversalStack.PushChildren(node);
}

PullUpVisibility(node) 
{
  while (!node.visible) 
  { 
    node.visible = true; 
    node = node.parent; 
  }
}

TraversalStack.Push(hierarchy.Root);
while ( not TraversalStack.Empty() or
        not QueryQueue.Empty() ) 
{
  //-- PART 1: process finished occlusion queries
  while ( not QueryQueue.Empty() and
         (ResultAvailable(QueryQueue.Front()) or
          TraversalStack.Empty()) ) 
  {
    node = QueryQueue.Dequeue();
    // wait if result not available
    visiblePixels = GetOcclusionQueryResult(node);
    if ( visiblePixels > VisibilityThreshold ) 
    {
      PullUpVisibility(node);
      TraverseNode(node);
    }
  }
  
  //-- PART 2: hierarchical traversal
  if ( not TraversalStack.Empty() ) 
  {
    node = TraversalStack.Pop();
    if ( InsideViewFrustum(node) ) 
    {
      // identify previously visible nodes
      wasVisible = node.visible and 
                   (node.lastVisited == frameID - 1);
      // identify nodes that we cannot skip queries for
      leafOrWasInvisible = not wasVisible or IsLeaf(node);
      // reset node's visibility classification
      node.visible = false;
      // update node's visited flag
      node.lastVisited = frameID;
      // skip testing previously visible interior nodes
      if ( leafOrWasInvisible ) 
      {
        IssueOcclusionQuery(node); 
        QueryQueue.Enqueue(node);
      }
      // always traverse a node if it was visible
      if ( wasVisible )
        TraverseNode(node);
    }
  }
}