Ignore:
Timestamp:
08/25/05 18:16:07 (19 years ago)
Author:
mattausch
Message:

added some optimizations for online culling and view cell generation

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/VUT/doc/SciReport/code/pseudocode.tex

    r243 r251  
    11\input default.mac 
    2 \comment{}\leftline{//----\ initialisation 
    3  } 
    4 \normal{}\leftline{ 1:\ \ \ Stack.Push\symbol{}(\normal{}kDTree.Root\symbol{});\normal{} 
    5 \symbol{} } 
    6 \comment{}\leftline{ 2:\ \ \ //----\ while\ there\ are\ some\ nodes\ in\ the\ stack\ or\ the\ query\ queue 
    7  } 
    8 \keya{}\leftline{ 3:\ \ \ while\symbol{}\ (!\normal{}Stack.Empty\symbol{}()\ \normal{}$\symbol{}||\normal{}$\symbol{}\ !\normal{}QueryQueue.Empty\symbol{}())\ $\{$\normal{} 
    9 \symbol{} } 
    10 \leftline{ 4:\ \ \ \ \ \comment{}//----\ PART\ 1:\ processing\ finished\ occlusion\ queries 
    11  } 
    12 \symbol{}\leftline{ 5:\ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}QueryQueue.Empty\symbol{}()\ \&\&\normal{} 
    13 \symbol{} } 
    14 \leftline{ 6:\ \ \ \ \ \ \ \ \ \ \ (\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}())\ \normal{}$\symbol{}||\normal{}$\symbol{}\ \normal{}Stack.Empty\symbol{}()))\ $\{$\normal{} 
    15 \symbol{} } 
    16 \leftline{ 7:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}()))\ $\{$\normal{} 
    17 \symbol{} } 
    18 \leftline{ 8:\ \ \ \ \ \ \ \ \ \comment{}//---\ result\ is\ not\ available\ and\ the\ stack\ is\ empty 
    19  } 
    20 \symbol{}\leftline{ 9:\ \ \ \ \ \ \ \ \ \comment{}//---\ check\ if\ we\ can\ do\ some\ conservative\ decision 
    21  } 
    22 \symbol{}\leftline{10:\ \ \ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.GetLeastCostNode\symbol{}();\normal{} 
    23 \symbol{} } 
    24 \leftline{11:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}N.renderingCost\symbol{}\ <\ \normal{}MaxRenderCost\symbol{})\ $\{$\normal{} 
    25 \symbol{} } 
    26 \leftline{12:\ \ \ \ \ \ \ \ \ \ \normal{}RenderSubtree\symbol{}(\normal{}N\symbol{});\normal{} 
    27 \symbol{} } 
    28 \leftline{13:\ \ \ \ \ \ \ \ \ \ \normal{}QueryQueue.DequeLeastCostNode\symbol{}();\normal{} 
    29 \symbol{} } 
    30 \leftline{14:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ we\ do\ not\ change\ N's\ visibility\ classfication\ - 
    31  } 
    32 \symbol{}\leftline{15:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ N\ remains\ in\ the\ cut\ for\ the\ next\ frame 
    33  } 
    34 \symbol{}\leftline{16:\ \ \ \ \ \ \ \ \ $\}$\ \normal{}else 
    35 \symbol{} } 
    36 \leftline{17:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ wait\ for\ the\ availability\ of\ the\ result 
    37  } 
    38 \symbol{}\leftline{18:\ \ \ \ \ \ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}QueryQueue.ResultAvailable\symbol{})\ \normal{}Wait\symbol{}();\normal{} 
    39 \symbol{} } 
    40 \leftline{19:\ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{}\ $\{$\normal{} 
    41 \symbol{} } 
    42 \leftline{20:\ \ \ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.Dequeue\symbol{}();\normal{} 
    43 \symbol{} } 
    44 \leftline{21:\ \ \ \ \ \ \ \ \ \comment{}//--\ check\ the\ result\ of\ the\ query 
    45  } 
    46 \symbol{}\leftline{22:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}N.visiblePixels\symbol{}\ \normal{}$\symbol{}>\normal{}$\symbol{}\ \normal{}VisibilityThreshold\symbol{}\ )\ \ $\{$\normal{} 
    47 \symbol{} } 
    48 \leftline{23:\ \ \ \ \ \ \ \ \ \ \normal{}N.visibility\symbol{}\ =\ \normal{}VISIBLE\symbol{};\normal{} 
    49 \symbol{} } 
    50 \leftline{24:\ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}IsLeaf\symbol{}(\normal{}N\symbol{}))\normal{} 
    51 \symbol{} } 
    52 \leftline{25:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{});\normal{} 
    53 \symbol{} } 
    54 \leftline{26:\ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{}\ $\{$\normal{} 
    55 \symbol{} } 
    56 \leftline{27:\ \ \ \ \ \ \ \ \ \ \ \ \comment{}//--\ pull\ down 
    57  } 
    58 \symbol{}\leftline{28:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Stack.Push\symbol{}(\normal{}FarChild\symbol{}(\normal{}N\symbol{}));\ \normal{}Stack.Push\symbol{}(\normal{}CloseChild\symbol{}(\normal{}N\symbol{}));\normal{} 
    59 \symbol{} } 
    60 \leftline{29:\ \ \ \ \ \ \ \ \ \ $\}$\normal{} 
    61 \symbol{} } 
    62 \leftline{30:\ \ \ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{}\ $\{$\normal{} 
    63 \symbol{} } 
    64 \leftline{31:\ \ \ \ \ \ \ \ \ \ \normal{}N.visibility\symbol{}\ =\ \normal{}INVISIBLE\symbol{};\normal{} 
    65 \symbol{} } 
    66 \leftline{32:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ pull\ up 
    67  } 
    68 \symbol{}\leftline{33:\ \ \ \ \ \ \ \ \ \ \normal{}PullUpInvisibility\symbol{}(\normal{}N\symbol{});\normal{} 
    69 \symbol{} } 
    70 \leftline{34:\ \ \ \ \ \ \ \ \ $\}$\normal{} 
    71 \symbol{} } 
    72 \leftline{35:\ \ \ \ \ \ \ $\}$\normal{} 
    73 \symbol{} } 
    74 \leftline{36:\ \ \ \ \ $\}$\normal{} 
    75 \symbol{} } 
    76 \leftline{37:\ \ \ \ \ \normal{} 
    77 \symbol{} } 
    78 \leftline{38:\ \ \ \ \ \comment{}//----\ PART\ 2:\ kd-tree\ traversal 
    79  } 
    80 \symbol{}\leftline{39:\ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}Stack.Empty\symbol{}())\ $\{$\normal{} 
    81 \symbol{} } 
    82 \leftline{40:\ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}Stack.Pop\symbol{}();\normal{} 
    83 \symbol{} } 
    84 \leftline{41:\ \ \ \ \ \ \ \normal{}N.lastVisited\symbol{}\ =\ \normal{}frameID\symbol{};\normal{} 
    85 \symbol{} } 
    86 \leftline{42:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}InsideViewFrustum\symbol{}(\normal{}N\symbol{}))\ $\{$\normal{} 
    87 \symbol{} } 
    88 \leftline{43:\ \ \ \ \ \ \ \ \ \comment{}//--\ skip\ testing\ of\ all\ nodes\ above\ the\ cut 
    89  } 
    90 \symbol{}\leftline{44:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}IsAboveTheCut\symbol{}(\normal{}N\symbol{}))\ $\{$\normal{} 
    91 \symbol{} } 
    92 \leftline{45:\ \ \ \ \ \ \ \ \ \ \normal{}IssueOcclustionQuery\symbol{}(\normal{}N\symbol{});\ \normal{}QueryQueue.Enqueue\symbol{}(\normal{}N\symbol{});\normal{} 
    93 \symbol{} } 
    94 \leftline{46:\ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}WasVisible\symbol{}(\normal{}N\symbol{})\ \normal{}$\symbol{}\&\&\normal{}$\symbol{}\ \normal{}IsLeaf\symbol{}(\normal{}N\symbol{}))\normal{} 
    95 \symbol{} } 
    96 \leftline{47:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{});\normal{} 
    97 \symbol{} } 
    98 \leftline{48:\ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{}\ $\{$\normal{} 
    99 \symbol{} } 
    100 \leftline{49:\ \ \ \ \ \ \ \ \ \ \ \ \comment{}//--\ go\ down\ the\ kD-tree 
    101  } 
    102 \symbol{}\leftline{50:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Stack.Push\symbol{}(\normal{}FarChild\symbol{}(\normal{}N\symbol{}));\ \normal{}Stack.Push\symbol{}(\normal{}CloseChild\symbol{}(\normal{}N\symbol{}));\ \normal{} 
    103 \symbol{} } 
    104 \leftline{51:\ \ \ \ \ \ \ \ \ \ $\}$\normal{} 
    105 \symbol{} } 
    106 \leftline{52:\ \ \ \ \ \ \ \ \ $\}$\normal{} 
    107 \symbol{} } 
    108 \leftline{53:\ \ \ \ \ \ \ $\}$\normal{} 
    109 \symbol{} } 
    110 \leftline{54:\ \ \ \ \ $\}$\normal{} 
    111 \symbol{} } 
    112 \leftline{55:\ \ \ $\}$\normal{} 
    113 \symbol{} } 
     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 TracChangeset for help on using the changeset viewer.