source: trunk/VUT/doc/SciReport/code/pseudocode2.tex @ 251

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

added some optimizations for online culling and view cell generation
RevLine 
[251]1\input default.mac
2\keya{}\leftline{Algorithm\symbol{}:\ \normal{}Traversal\symbol{}\ \normal{}of\symbol{}\ \normal{}the\symbol{}\ \normal{}kD\symbol{}-\normal{}tree\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:\ \ \ \ \ \ \ \ \ \ \normal{}IssueOcclusionQuery\symbol{}(\normal{}N\symbol{});\ \normal{}QueryQueue.Enqueue\symbol{}(\normal{}N\symbol{}); }
33\leftline{31:\ \ \ \ \ \ \ \ \ $\}$ }
34\leftline{32:\ \ \ \ \ \ \ \ \ \comment{}//\ traverse\ a\ node\ unless\ it\ was\ invisible }
35\symbol{}\leftline{33:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}wasVisible\symbol{}\ ) }
36\leftline{34:\ \ \ \ \ \ \ \ \ \ \normal{}TraverseNode\symbol{}(\normal{}N\symbol{}); }
37\leftline{35:\ \ \ \ \ \ \ $\}$ }
38\leftline{36:\ \ \ \ \ $\}$ }
39\leftline{37:\ \ \ $\}$ }
40\normal{}\leftline{38:\ \ \ TraverseNode\symbol{}(\normal{}N\symbol{})\ $\{$ }
41\leftline{39:\ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}IsLeaf\symbol{}(\normal{}N\symbol{})\ ) }
42\leftline{40:\ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{}); }
43\leftline{41:\ \ \ \ \ \keya{}else\symbol{} }
44\leftline{42:\ \ \ \ \ \ \ \normal{}TraversalStack.PushChildren\symbol{}(\normal{}N\symbol{}); }
45\leftline{43:\ \ \ $\}$ }
46\normal{}\leftline{44:\ \ \ PullUpVisibility\symbol{}(\normal{}N\symbol{})\ $\{$ }
47\leftline{45:\ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}N.visible\symbol{})\ $\{$\ \normal{}N.visible\symbol{}\ =\ \normal{}true\symbol{};\ \normal{}N\symbol{}\ =\ \normal{}N.parent\symbol{};\ $\}$ }
48\leftline{46:\ \ \ $\}$ }
Note: See TracBrowser for help on using the repository browser.