source: GTP/trunk/Lib/Vis/Preprocessing/manual/code/pseudocode_batching.tex @ 2066

Revision 2066, 5.7 KB checked in by mattausch, 18 years ago (diff)

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