\input default.mac
\keya{}\leftline{Algorithm\symbol{}:\ \normal{}Traversal\symbol{}\ \normal{}of\symbol{}\ \normal{}the\symbol{}\ \normal{}kD\symbol{}-\normal{}tree\symbol{}\ \normal{}applying\symbol{}\ \normal{}batching\symbol{}\ \normal{}of\symbol{}\ \normal{}multiple\symbol{}\ \normal{}queries\symbol{} }
\normal{}\leftline{ 1:\ \ \ TraversalStack.Push\symbol{}(\normal{}kDTree.Root\symbol{}); }
\keya{}\leftline{ 2:\ \ \ while\symbol{}\ (\ \keya{}not\symbol{}\ \normal{}TraversalStack.Empty\symbol{}()\ \keya{}or\symbol{} }
\leftline{ 3:\ \ \ \ \ \ \ \ \ \ \ \keya{}not\symbol{}\ \normal{}QueryQueue.Empty\symbol{}()\ )\ $\{$ }
\leftline{ 4:\ \ \ \ \ \comment{}//----\ PART\ 1:\ processing\ finished\ occlusion\ queries }
\symbol{}\leftline{ 5:\ \ \ \ \ \keya{}while\symbol{}\ (\ \keya{}not\symbol{}\ \normal{}QueryQueue.Empty\symbol{}()\ \keya{}and\symbol{} }
\leftline{ 6:\ \ \ \ \ \ \ \ \ \ \ \ (\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}())\ \keya{}or\symbol{} }
\leftline{ 7:\ \ \ \ \ \ \ \ \ \ \ \ \ \normal{}TraversalStack.Empty\symbol{}())\ )\ $\{$ }
\leftline{ 8:\ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.Dequeue\symbol{}(); }
\leftline{ 9:\ \ \ \ \ \ \ \comment{}//\ wait\ if\ result\ not\ available }
\symbol{}\leftline{10:\ \ \ \ \ \ \ \normal{}visiblePixels\symbol{}\ =\ \normal{}GetOcclussionQueryResult\symbol{}(\normal{}N\symbol{}); }
\leftline{11:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}visiblePixels\symbol{}\ >\ \normal{}VisibilityThreshold\symbol{}\ )\ $\{$ }
\leftline{12:\ \ \ \ \ \ \ \ \ \normal{}PullUpVisibility\symbol{}(\normal{}N\symbol{}); }
\leftline{13:\ \ \ \ \ \ \ \ \ \normal{}TraverseNode\symbol{}(\normal{}N\symbol{}); }
\leftline{14:\ \ \ \ \ \ \ $\}$ }
\leftline{15:\ \ \ \ \ $\}$ }
\leftline{16:\ \ \ \ \ \comment{}//----\ PART\ 2:\ kd-tree\ traversal }
\symbol{}\leftline{17:\ \ \ \ \ \keya{}if\symbol{}\ (\ \keya{}not\symbol{}\ \normal{}TraversalStack.Empty\symbol{}()\ )\ $\{$ }
\leftline{18:\ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}TraversalStack.Pop\symbol{}(); }
\leftline{19:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}InsideViewFrustum\symbol{}(\normal{}N\symbol{})\ )\ $\{$ }
\leftline{20:\ \ \ \ \ \ \ \ \ \comment{}//\ identify\ previously\ visible\ nodes }
\symbol{}\leftline{21:\ \ \ \ \ \ \ \ \ \normal{}wasVisible\symbol{}\ =\ \normal{}N.visible\symbol{}\ \&\&\ (\normal{}N.lastVisited\symbol{}\ ==\ \normal{}frameID\symbol{}\ -\normal{}1\symbol{}); }
\leftline{22:\ \ \ \ \ \ \ \ \ \comment{}//\ identify\ previously\ opened\ nodes }
\symbol{}\leftline{23:\ \ \ \ \ \ \ \ \ \normal{}opened\symbol{}\ =\ \normal{}wasVisible\symbol{}\ \&\&\ !\normal{}IsLeaf\symbol{}(\normal{}N\symbol{}); }
\leftline{24:\ \ \ \ \ \ \ \ \ \comment{}//\ reset\ node's\ visibility\ classification }
\symbol{}\leftline{25:\ \ \ \ \ \ \ \ \ \normal{}N.visible\symbol{}\ =\ \normal{}false\symbol{}; }
\leftline{26:\ \ \ \ \ \ \ \ \ \comment{}//\ update\ node's\ visited\ flag }
\symbol{}\leftline{27:\ \ \ \ \ \ \ \ \ \normal{}N.lastVisited\symbol{}\ =\ \normal{}frameID\symbol{}; }
\leftline{28:\ \ \ \ \ \ \ \ \ \comment{}//\ skip\ testing\ all\ previously\ opened\ nodes }
\symbol{}\leftline{29:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ !\normal{}opened\symbol{}\ )\ $\{$ }
\leftline{30:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \comment{}//\ add\ to\ the\ pending\ queue\ instead\ of\ immediate\ query }
\symbol{}\leftline{31:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}PendingQueue.size\symbol{}()\ <\ \normal{}n\symbol{}) }
\leftline{32:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \normal{}PendingQueue.Enqueue\symbol{}(\normal{}N\symbol{}); }
\leftline{33:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{} }
\leftline{34:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\{$ }
\leftline{35:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \normal{}IssueMultipleOcclusionQueries\symbol{}(\normal{}PendingQueue\symbol{}); }
\leftline{36:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \normal{}AddToQueryQueue\symbol{}(\normal{}PendingQueue\symbol{},\ \normal{}QueryQueue\symbol{}); }
\leftline{37:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \normal{}PendingQueue.clear\symbol{}(); }
\leftline{38:\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ $\}$ }
\leftline{39:\ \ \ \ \ \ \ \ \ $\}$ }
\leftline{40:\ \ \ \ \ \ \ \ \ \comment{}//\ traverse\ a\ node\ unless\ it\ was\ invisible }
\symbol{}\leftline{41:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}wasVisible\symbol{}\ ) }
\leftline{42:\ \ \ \ \ \ \ \ \ \ \normal{}TraverseNode\symbol{}(\normal{}N\symbol{}); }
\leftline{43:\ \ \ \ \ \ \ $\}$ }
\leftline{44:\ \ \ \ \ $\}$ }
\leftline{45:\ \ \  }
\leftline{46:\ \ \ \ \ \comment{}//\ add\ rest\ to\ query\ queue }
\symbol{}\leftline{47:\ \ \ \ \ \normal{}IssueMultipleOcclusionQueries\symbol{}(\normal{}PendingQueue\symbol{}); }
\leftline{48:\ \ \ \ \ \normal{}AddToQueryQueue\symbol{}(\normal{}PendingQueue\symbol{},\ \normal{}QueryQueue\symbol{}); }
\leftline{49:\ \ \ \ \ \normal{}PendingQueue.clear\symbol{}(); }
\leftline{50:\ \ \ $\}$ }
\normal{}\leftline{51:\ \ \ TraverseNode\symbol{}(\normal{}N\symbol{})\ $\{$ }
\leftline{52:\ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}IsLeaf\symbol{}(\normal{}N\symbol{})\ ) }
\leftline{53:\ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{}); }
\leftline{54:\ \ \ \ \ \keya{}else\symbol{} }
\leftline{55:\ \ \ \ \ \ \ \normal{}TraversalStack.PushChildren\symbol{}(\normal{}N\symbol{}); }
\leftline{56:\ \ \ $\}$ }
\normal{}\leftline{57:\ \ \ PullUpVisibility\symbol{}(\normal{}N\symbol{})\ $\{$ }
\leftline{58:\ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}N.visible\symbol{})\ $\{$\ \normal{}N.visible\symbol{}\ =\ \normal{}true\symbol{};\ \normal{}N\symbol{}\ =\ \normal{}N.parent\symbol{};\ $\}$ }
\leftline{59:\ \ \ $\}$ }