source: trunk/VUT/doc/SciReport/code/pseudocode2.cpp @ 243

Algorithm: Traversal of the kD-tree
TraversalStack.Push(kDTree.Root);
while ( not TraversalStack.Empty() or
        not QueryQueue.Empty() ) {
  //---- PART 1: processing finished occlusion queries
  while ( not QueryQueue.Empty() and
          (ResultAvailable(QueryQueue.Front()) or
           TraversalStack.Empty()) ) {
    N = QueryQueue.Dequeue();
    // wait if result not available
    visiblePixels = GetOcclussionQueryResult(N);
    if ( visiblePixels > VisibilityThreshold ) {
      PullUpVisibility(N);
      TraverseNode(N);
    }
  }
  //---- PART 2: kd-tree traversal
  if ( not TraversalStack.Empty() ) {
    N = TraversalStack.Pop();
    if ( InsideViewFrustum(N) ) {
      // identify previously visible nodes
      wasVisible = N.visible && (N.lastVisited == frameID -1);
      // identify previously opened nodes
      opened = wasVisible && !IsLeaf(N);
      // reset node's visibility classification
      N.visible = false;
      // update node's visited flag
      N.lastVisited = frameID;
      // skip testing all previously opened nodes
      if ( !opened ) {
        IssueOcclusionQuery(N); QueryQueue.Enqueue(N);
      }
      // traverse a node unless it was invisible
      if ( wasVisible )
        TraverseNode(N);
    }
  }
}
TraverseNode(N) {
  if ( IsLeaf(N) )
    Render(N);
  else
    TraversalStack.PushChildren(N);
}
PullUpVisibility(N) {
  while (!N.visible) { N.visible = true; N = N.parent; }
}