[2066] | 1 | Algorithm: Traversal of the kD-tree applying batching of multiple queries |
---|
| 2 | TraversalStack.Push(kDTree.Root); |
---|
| 3 | while ( 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 | } |
---|
| 52 | TraverseNode(N) { |
---|
| 53 | if ( IsLeaf(N) ) |
---|
| 54 | Render(N); |
---|
| 55 | else |
---|
| 56 | TraversalStack.PushChildren(N); |
---|
| 57 | } |
---|
| 58 | PullUpVisibility(N) { |
---|
| 59 | while (!N.visible) { N.visible = true; N = N.parent; } |
---|
| 60 | } |
---|