source: obsolete/trunk/VUT/doc/SciReport/code/pseudocode_batching.cpp @ 251

Revision 251, 1.8 KB checked in by mattausch, 19 years ago (diff)

added some optimizations for online culling and view cell generation

Line 
1Algorithm: Traversal of the kD-tree applying batching of multiple queries
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                  // add to the pending queue instead of immediate query
32                  if (PendingQueue.size() < n)
33                          PendingQueue.Enqueue(N);
34                  else
35                  {
36                          IssueMultipleOcclusionQueries(PendingQueue);
37                          AddToQueryQueue(PendingQueue, QueryQueue);
38                          PendingQueue.clear();
39                  }
40      }
41      // traverse a node unless it was invisible
42      if ( wasVisible )
43        TraverseNode(N);
44    }
45  }
46
47  // add rest to query queue
48  IssueMultipleOcclusionQueries(PendingQueue);
49  AddToQueryQueue(PendingQueue, QueryQueue);
50  PendingQueue.clear();
51}
52TraverseNode(N) {
53  if ( IsLeaf(N) )
54    Render(N);
55  else
56    TraversalStack.PushChildren(N);
57}
58PullUpVisibility(N) {
59  while (!N.visible) { N.visible = true; N = N.parent; }
60}
Note: See TracBrowser for help on using the repository browser.