Changeset 251 for trunk


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

added some optimizations for online culling and view cell generation

Location:
trunk/VUT/doc/SciReport
Files:
1 added
15 edited

Legend:

Unmodified
Added
Removed

  • trunk/VUT/doc/SciReport/Bib/new.bib

    r249 r251  
    2828} 
    2929 
     30@Article{Staneker:2004:EMO, 
     31   AUTHOR = "Dirk Staneker and Dirk Bartz and Wolfgang Strasser", 
     32   TITLE = "Efficient Multiple Occlusion Queries for Scene Graph Systems", 
     33   JOURNAL = "WSI Report (WSI-2004-6)", 
     34   INSTITUTION = {Wilhelm Schickard Institute for Computer Science, Graphical Interactive Systems (WSI/GRIS), University of T{\"u}bingen}, 
     35   YEAR = "2004", 
     36   KEYWORDS = {GRIS} 
     37} 
    3038 
    3139@InProceedings{Meissner01, 

  • 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:\ \ \ $\}$ } 

  • trunk/VUT/doc/SciReport/figs/basic.eps

    r243 r251  
    22%%Title: basic.fig 
    33%%Creator: fig2dev Version 3.2 Patchlevel 4 
    4 %%CreationDate: Mon Aug 22 13:04:52 2005 
    5 %%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000) 
     4%%CreationDate: Tue Aug 23 20:55:48 2005 
     5%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508) 
    66%%BoundingBox: 0 0 793 244 
    77%%Magnification: 1.0000 

  • trunk/VUT/doc/SciReport/figs/cut.eps

    r243 r251  
    22%%Title: cut.fig 
    33%%Creator: fig2dev Version 3.2 Patchlevel 4 
    4 %%CreationDate: Mon Aug 22 13:04:52 2005 
    5 %%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000) 
     4%%CreationDate: Tue Aug 23 20:55:48 2005 
     5%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508) 
    66%%BoundingBox: 0 0 979 330 
    77%%Magnification: 1.0000 

  • trunk/VUT/doc/SciReport/figs/dummy.eps

    r243 r251  
    22%%Title: dummy.fig 
    33%%Creator: fig2dev Version 3.2 Patchlevel 4 
    4 %%CreationDate: Mon Aug 22 13:04:52 2005 
    5 %%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000) 
     4%%CreationDate: Tue Aug 23 20:55:48 2005 
     5%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508) 
    66%%BoundingBox: 0 0 474 443 
    77%%Magnification: 1.0000 

  • trunk/VUT/doc/SciReport/figs/latency.eps

    r243 r251  
    22%%Title: latency.fig 
    33%%Creator: fig2dev Version 3.2 Patchlevel 4 
    4 %%CreationDate: Mon Aug 22 13:04:52 2005 
    5 %%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000) 
     4%%CreationDate: Tue Aug 23 20:55:48 2005 
     5%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508) 
    66%%BoundingBox: 0 0 1153 326 
    77%%Magnification: 1.0000 

  • trunk/VUT/doc/SciReport/figs/latency2.eps

    r243 r251  
    22%%Title: latency2.fig 
    33%%Creator: fig2dev Version 3.2 Patchlevel 4 
    4 %%CreationDate: Mon Aug 22 13:04:52 2005 
    5 %%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000) 
     4%%CreationDate: Tue Aug 23 20:55:48 2005 
     5%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508) 
    66%%BoundingBox: 0 0 992 393 
    77%%Magnification: 1.0000 

  • trunk/VUT/doc/SciReport/online.tex

    r243 r251  
    1 \chapter{Online Visibility Culling} 
     1\chapter{Online Culling Tool} 
    22%***************************************************************************** 
    33 
    … …  
    5050application of occlusion queries can even decrease the overall 
    5151application performance due the associated CPU stalls and GPU 
    52 starvation. In this paper, we present an algorithm that aims to 
     52starvation. In this chapter, we present an algorithm that aims to 
    5353overcome these problems by reducing the number of issued queries and 
    5454eliminating the CPU stalls and GPU starvation. To schedule the 
    … …  
    149149suffers from the CPU stalls and GPU starvation. 
    150150 
    151 %% The methods proposed in this paper can be used to make use of temporal 
     151%% The methods proposed in this chapter can be used to make use of temporal 
    152152%% and spatial coherence in the scope of existing visibility algorithms, 
    153153%% that utilise a spatial hierarchy. Examples of these are algorithms 
    … …  
    173173acceleration technique for exploiting spatial and temporal coherence 
    174174in hierarchical visibility algorithms. The central idea, which is also 
    175 vital for this paper, is to avoid repeated visibility tests of 
     175vital for the online culling tool, is to avoid repeated visibility tests of 
    176176interior nodes of the hierarchy. The problem of direct adoption of 
    177177this method is that it is designed for the use with instantaneous CPU 
    … …  
    625625 
    626626 
    627  \subsection{Approximate visibility} 
     627\subsection{Approximate visibility} 
    628628 
    629629 The algorithm as presented computes a conservative visibility 
    … …  
    660660the constant we conclude that it is too risky to render the node and 
    661661wait till the result of the query becomes available. 
     662 
     663\subsection{Initial depth pass} 
     664\label{sec:initial} 
     665 
     666To achieve maximal performance on modern GPU's, one has to take care of a number of issues. 
     667First, it is very important to reduce material switching. Thus modern rendering engines sort the  
     668objects (or patches) by materials in order to eliminate the material switching as good as possible.  
     669 
     670Next, materials can be very costly, sometimes complicated shaders have to be evaluated several times per batch. Hence it should be 
     671avoided to render the full material for fragments which eventually turn out to be occluded. This can be achieved 
     672by rendering an initial depth pass (i.e., enabling only depth write to fill the depth 
     673buffer). Afterwards the geometry is rendered again, this time with full shading. Because the  
     674depth buffer is already established, invisible fragments will be discarded before any shading is done calculated. 
     675 
     676This approach can be naturally adapted for use with the CHC algorithm. Only an initial depth pass is rendered 
     677in front-to-back order using the CHC algorithm. The initial pass is sufficient to fill the depth buffer and determine the visible geometry. Then only the visible geometry is rendered again, exploiting the full optimization and material sorting capability of the rendering engine. 
     678 
     679\subsection{Batching multiple queries} 
     680\begin{figure}%[htb] 
     681{\footnotesize 
     682  \input{code/pseudocode_batching} 
     683 } 
     684  \caption{Pseudo-code of coherent hierarchical culling using multiple queries.} 
     685  \label{fig:pseudocode_batching} 
     686\end{figure} 
     687When occlusion queries are rendered interleaved with geometry, there is always a state change involved. To 
     688reduce state changes, it is beneficial not to execute one query at a time, but multiple queries at once~\cite{Staneker:2004:EMO}. 
     689Instead of immediately executing a query for a node when we fetch it from the traversal stack, we add it to the {\em pending queue}. If {\em n} of these queries are accumulated in the queue, we can execute them at once. 
     690To optain an optimal value for {\em n}, several some heuristics can be applied, e.g., a fraction of the number of queries issued in the last frame. The new pseudo-code of the algorithm is given in Figure~\ref{fig:pseudocode_batching}.  
     691 
    662692 
    663693\section{Results} 
    … …  
    10281058 stop-and-wait application of occlusion queries. 
    10291059 
     1060 
    10301061  The major potential in improving the method is a better estimation 
    10311062 of changes in the visibility classification of hierarchy nodes. If 
    … …  
    10371068 simpler geometry  can be faster than issuing comparably expensive 
    10381069 occlusion queries. 
    1039  
    10401070 
    10411071 

  • trunk/VUT/doc/SciReport/preprocessing.tex

    r247 r251  
    119119 
    120120 
     121\subsection{View Cell Representation} 
     122 
     123In order to efficiently use view cells with our sampling method, we require a view cell representation which is 
     124 
     125\begin{itemize} 
     126\item optimized for viewcell - ray intersection. 
     127\item flexible, i.e., it can represent arbitrary geometry. 
     128\item naturally suited for an hierarchical approach. %(i.e., there is a root view cell containing all others) 
     129\end{itemize} 
     130 
     131We meet these requirements by using a view cell BSP tree, where the BSP leafs are associated with the view cells.  
     132Using the BSP tree, we are able to find the initial view cells with only a few view ray-plane intersections.  
     133The hierarchical structure of the BSP tree can be exploited as hierarchy of view cells. If neccessary, the BSP  
     134approach makes it very easy to further subdivide a view cell. 
     135 
     136Currently we use two approaches to generate the initial BSP view cell tree. 
     137 
     138\begin{itemize} 
     139\item We use a number of dedicated input view cells. As input view cell any closed mesh can be applied. The only requirement 
     140is that the view cells do not overlap. We insert one view cell after the other into the tree. The polygons of a view cell are filtered down the tree, guiding the insertion process. Once we reach a leaf and there are no more polygons left, we terminate 
     141the tree subdivision. If we are on the inside of the last split plane (i.e., the leaf is representing the inside of the view cell), we associate the leaf with the view cell (i.e., add a pointer to the view cell). Hence a number of leafes 
     142can be associated with the same input view cell. 
     143\item We apply the BSP tree subdivision to the scene geometry. When the subdivision terminates, the leaf nodes 
     144also represent the view cells.  
     145\end{itemize} 
    121146 
    122147 
    … …  
    132157 
    133158 
    134  
    135  
    136159\subsection{Conservative Verifier} 
    137160 

  • trunk/VUT/doc/SciReport/sampling.tex

    r249 r251  
    125125 objects. 
    126126 
    127   
     127 \subsection{View Cell Representation} 
    128128 
     129In order to efficiently use view cells with our sampling method, we require a view cell representation which is 
     130 
     131\begin{itemize} 
     132\item optimized for viewcell - ray intersection. 
     133\item flexible, i.e., it can represent arbitrary geometry. 
     134\item naturally suited for an hierarchical approach. %(i.e., there is a root view cell containing all others) 
     135\end{itemize} 
     136 
     137We meet these requirements by using a view cell BSP tree, where the BSP leafs are associated with the view cells.  
     138Using the BSP tree, we are able to find the initial view cells with only a few view ray-plane intersections.  
     139The hierarchical structure of the BSP tree can be exploited as hierarchy of view cells. If neccessary, we could further subdivide a BSP leaf view cell quite easily. 
     140 
     141Currently we use two approaches to generate the initial BSP view cell tree. 
     142 
     143\begin{itemize} 
     144\item We use a number of dedicated input view cells. As input view cell any closed mesh can be applied. The only requirement 
     145is that the view cells do not overlap. We insert one view cell after the other into the tree. The polygons of a view cell are filtered down the tree, guiding the insertion process. Once we reach a leaf and there are no more polygons left, we terminate 
     146the tree subdivision. If we are on the inside of the last split plane (i.e., the leaf is representing the inside of the view cell), we associate the leaf with the view cell (i.e., add a pointer to the view cell). Hence a number of leafes 
     147can be associated with the same input view cell. 
     148\item We apply the BSP tree subdivision to the scene geometry. When the subdivision terminates, the leaf nodes 
     149also represent the view cells.  
     150\end{itemize} 
     151 
Note: See TracChangeset for help on using the changeset viewer.