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

Revision 243, 1.4 KB checked in by bittner, 19 years ago (diff)

SciReport? template

RevLine 
[243]1Algorithm: Traversal of the kD-tree
2TraversalStack.Push(kDTree.Root);
3while ( not TraversalStack.Empty() or
4        not QueryQueue.Empty() ) {
5  //---- PART 1: processing finished occlusion queries
6  while ( not QueryQueue.Empty() and
7          (ResultAvailable(QueryQueue.Front()) or
8           TraversalStack.Empty()) ) {
9    N = QueryQueue.Dequeue();
10    // wait if result not available
11    visiblePixels = GetOcclussionQueryResult(N);
12    if ( visiblePixels > VisibilityThreshold ) {
13      PullUpVisibility(N);
14      TraverseNode(N);
15    }
16  }
17  //---- PART 2: kd-tree traversal
18  if ( not TraversalStack.Empty() ) {
19    N = TraversalStack.Pop();
20    if ( InsideViewFrustum(N) ) {
21      // identify previously visible nodes
22      wasVisible = N.visible && (N.lastVisited == frameID -1);
23      // identify previously opened nodes
24      opened = wasVisible && !IsLeaf(N);
25      // reset node's visibility classification
26      N.visible = false;
27      // update node's visited flag
28      N.lastVisited = frameID;
29      // skip testing all previously opened nodes
30      if ( !opened ) {
31        IssueOcclusionQuery(N); QueryQueue.Enqueue(N);
32      }
33      // traverse a node unless it was invisible
34      if ( wasVisible )
35        TraverseNode(N);
36    }
37  }
38}
39TraverseNode(N) {
40  if ( IsLeaf(N) )
41    Render(N);
42  else
43    TraversalStack.PushChildren(N);
44}
45PullUpVisibility(N) {
46  while (!N.visible) { N.visible = true; N = N.parent; }
47}
Note: See TracBrowser for help on using the repository browser.