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

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

added some optimizations for online culling and view cell generation

Line 
1\input default.mac
2\comment{}\leftline{//----\ initialisation }
3\normal{}\leftline{ 1:\ \ \ Stack.Push\symbol{}(\normal{}kDTree.Root\symbol{}); }
4\comment{}\leftline{ 2:\ \ \ //----\ while\ there\ are\ some\ nodes\ in\ the\ stack\ or\ the\ query\ queue }
5\keya{}\leftline{ 3:\ \ \ while\symbol{}\ (!\normal{}Stack.Empty\symbol{}()\ \normal{}$\symbol{}||\normal{}$\symbol{}\ !\normal{}QueryQueue.Empty\symbol{}())\ $\{$ }
6\leftline{ 4:\ \ \ \ \ \comment{}//----\ PART\ 1:\ processing\ finished\ occlusion\ queries }
7\symbol{}\leftline{ 5:\ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}QueryQueue.Empty\symbol{}()\ \&\& }
8\leftline{ 6:\ \ \ \ \ \ \ \ \ \ \ (\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}())\ \normal{}$\symbol{}||\normal{}$\symbol{}\ \normal{}Stack.Empty\symbol{}()))\ $\{$ }
9\leftline{ 7:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}()))\ $\{$ }
10\leftline{ 8:\ \ \ \ \ \ \ \ \ \comment{}//---\ result\ is\ not\ available\ and\ the\ stack\ is\ empty }
11\symbol{}\leftline{ 9:\ \ \ \ \ \ \ \ \ \comment{}//---\ check\ if\ we\ can\ do\ some\ conservative\ decision }
12\symbol{}\leftline{10:\ \ \ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.GetLeastCostNode\symbol{}(); }
13\leftline{11:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}N.renderingCost\symbol{}\ <\ \normal{}MaxRenderCost\symbol{})\ $\{$ }
14\leftline{12:\ \ \ \ \ \ \ \ \ \ \normal{}RenderSubtree\symbol{}(\normal{}N\symbol{}); }
15\leftline{13:\ \ \ \ \ \ \ \ \ \ \normal{}QueryQueue.DequeLeastCostNode\symbol{}(); }
16\leftline{14:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ we\ do\ not\ change\ N's\ visibility\ classfication\ - }
17\symbol{}\leftline{15:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ N\ remains\ in\ the\ cut\ for\ the\ next\ frame }
18\symbol{}\leftline{16:\ \ \ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{} }
19\leftline{17:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ wait\ for\ the\ availability\ of\ the\ result }
20\symbol{}\leftline{18:\ \ \ \ \ \ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}QueryQueue.ResultAvailable\symbol{})\ \normal{}Wait\symbol{}(); }
21\leftline{19:\ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{}\ $\{$ }
22\leftline{20:\ \ \ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.Dequeue\symbol{}(); }
23\leftline{21:\ \ \ \ \ \ \ \ \ \comment{}//--\ check\ the\ result\ of\ the\ query }
24\symbol{}\leftline{22:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}N.visiblePixels\symbol{}\ \normal{}$\symbol{}>\normal{}$\symbol{}\ \normal{}VisibilityThreshold\symbol{}\ )\ \ $\{$ }
25\leftline{23:\ \ \ \ \ \ \ \ \ \ \normal{}N.visibility\symbol{}\ =\ \normal{}VISIBLE\symbol{}; }
26\leftline{24:\ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}IsLeaf\symbol{}(\normal{}N\symbol{})) }
27\leftline{25:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{}); }
28\leftline{26:\ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{}\ $\{$ }
29\leftline{27:\ \ \ \ \ \ \ \ \ \ \ \ \comment{}//--\ pull\ down }
30\symbol{}\leftline{28:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Stack.Push\symbol{}(\normal{}FarChild\symbol{}(\normal{}N\symbol{}));\ \normal{}Stack.Push\symbol{}(\normal{}CloseChild\symbol{}(\normal{}N\symbol{})); }
31\leftline{29:\ \ \ \ \ \ \ \ \ \ $\}$ }
32\leftline{30:\ \ \ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{}\ $\{$ }
33\leftline{31:\ \ \ \ \ \ \ \ \ \ \normal{}N.visibility\symbol{}\ =\ \normal{}INVISIBLE\symbol{}; }
34\leftline{32:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ pull\ up }
35\symbol{}\leftline{33:\ \ \ \ \ \ \ \ \ \ \normal{}PullUpInvisibility\symbol{}(\normal{}N\symbol{}); }
36\leftline{34:\ \ \ \ \ \ \ \ \ $\}$ }
37\leftline{35:\ \ \ \ \ \ \ $\}$ }
38\leftline{36:\ \ \ \ \ $\}$ }
39\leftline{37:\ \ \ \ \  }
40\leftline{38:\ \ \ \ \ \comment{}//----\ PART\ 2:\ kd-tree\ traversal }
41\symbol{}\leftline{39:\ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}Stack.Empty\symbol{}())\ $\{$ }
42\leftline{40:\ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}Stack.Pop\symbol{}(); }
43\leftline{41:\ \ \ \ \ \ \ \normal{}N.lastVisited\symbol{}\ =\ \normal{}frameID\symbol{}; }
44\leftline{42:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}InsideViewFrustum\symbol{}(\normal{}N\symbol{}))\ $\{$ }
45\leftline{43:\ \ \ \ \ \ \ \ \ \comment{}//--\ skip\ testing\ of\ all\ nodes\ above\ the\ cut }
46\symbol{}\leftline{44:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}IsAboveTheCut\symbol{}(\normal{}N\symbol{}))\ $\{$ }
47\leftline{45:\ \ \ \ \ \ \ \ \ \ \normal{}IssueOcclustionQuery\symbol{}(\normal{}N\symbol{});\ \normal{}QueryQueue.Enqueue\symbol{}(\normal{}N\symbol{}); }
48\leftline{46:\ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}WasVisible\symbol{}(\normal{}N\symbol{})\ \normal{}$\symbol{}\&\&\normal{}$\symbol{}\ \normal{}IsLeaf\symbol{}(\normal{}N\symbol{})) }
49\leftline{47:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{}); }
50\leftline{48:\ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{}\ $\{$ }
51\leftline{49:\ \ \ \ \ \ \ \ \ \ \ \ \comment{}//--\ go\ down\ the\ kD-tree }
52\symbol{}\leftline{50:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Stack.Push\symbol{}(\normal{}FarChild\symbol{}(\normal{}N\symbol{}));\ \normal{}Stack.Push\symbol{}(\normal{}CloseChild\symbol{}(\normal{}N\symbol{}));\  }
53\leftline{51:\ \ \ \ \ \ \ \ \ \ $\}$ }
54\leftline{52:\ \ \ \ \ \ \ \ \ $\}$ }
55\leftline{53:\ \ \ \ \ \ \ $\}$ }
56\leftline{54:\ \ \ \ \ $\}$ }
57\leftline{55:\ \ \ $\}$ }
Note: See TracBrowser for help on using the repository browser.