Index: /trunk/VUT/doc/SciReport/preprocessing.tex
===================================================================
--- /trunk/VUT/doc/SciReport/preprocessing.tex	(revision 247)
+++ /trunk/VUT/doc/SciReport/preprocessing.tex	(revision 251)
@@ -119,4 +119,29 @@
 
 
+\subsection{View Cell Representation}
+
+In order to efficiently use view cells with our sampling method, we require a view cell representation which is
+
+\begin{itemize}
+\item optimized for viewcell - ray intersection.
+\item flexible, i.e., it can represent arbitrary geometry.
+\item naturally suited for an hierarchical approach. %(i.e., there is a root view cell containing all others)
+\end{itemize}
+
+We meet these requirements by using a view cell BSP tree, where the BSP leafs are associated with the view cells. 
+Using the BSP tree, we are able to find the initial view cells with only a few view ray-plane intersections. 
+The hierarchical structure of the BSP tree can be exploited as hierarchy of view cells. If neccessary, the BSP 
+approach makes it very easy to further subdivide a view cell.
+
+Currently we use two approaches to generate the initial BSP view cell tree.
+
+\begin{itemize}
+\item We use a number of dedicated input view cells. As input view cell any closed mesh can be applied. The only requirement
+is 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
+the 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
+can be associated with the same input view cell.
+\item We apply the BSP tree subdivision to the scene geometry. When the subdivision terminates, the leaf nodes
+also represent the view cells. 
+\end{itemize}
 
 
@@ -132,6 +157,4 @@
 
 
-
-
 \subsection{Conservative Verifier}
 
Index: /trunk/VUT/doc/SciReport/online.tex
===================================================================
--- /trunk/VUT/doc/SciReport/online.tex	(revision 243)
+++ /trunk/VUT/doc/SciReport/online.tex	(revision 251)
@@ -1,3 +1,3 @@
-\chapter{Online Visibility Culling}
+\chapter{Online Culling Tool}
 %*****************************************************************************
 
@@ -50,5 +50,5 @@
 application of occlusion queries can even decrease the overall
 application performance due the associated CPU stalls and GPU
-starvation. In this paper, we present an algorithm that aims to
+starvation. In this chapter, we present an algorithm that aims to
 overcome these problems by reducing the number of issued queries and
 eliminating the CPU stalls and GPU starvation. To schedule the
@@ -149,5 +149,5 @@
 suffers from the CPU stalls and GPU starvation.
 
-%% The methods proposed in this paper can be used to make use of temporal
+%% The methods proposed in this chapter can be used to make use of temporal
 %% and spatial coherence in the scope of existing visibility algorithms,
 %% that utilise a spatial hierarchy. Examples of these are algorithms
@@ -173,5 +173,5 @@
 acceleration technique for exploiting spatial and temporal coherence
 in hierarchical visibility algorithms. The central idea, which is also
-vital for this paper, is to avoid repeated visibility tests of
+vital for the online culling tool, is to avoid repeated visibility tests of
 interior nodes of the hierarchy. The problem of direct adoption of
 this method is that it is designed for the use with instantaneous CPU
@@ -625,5 +625,5 @@
 
 
- \subsection{Approximate visibility}
+\subsection{Approximate visibility}
 
  The algorithm as presented computes a conservative visibility
@@ -660,4 +660,34 @@
 the constant we conclude that it is too risky to render the node and
 wait till the result of the query becomes available.
+
+\subsection{Initial depth pass}
+\label{sec:initial}
+
+To achieve maximal performance on modern GPU's, one has to take care of a number of issues.
+First, it is very important to reduce material switching. Thus modern rendering engines sort the 
+objects (or patches) by materials in order to eliminate the material switching as good as possible. 
+
+Next, materials can be very costly, sometimes complicated shaders have to be evaluated several times per batch. Hence it should be
+avoided to render the full material for fragments which eventually turn out to be occluded. This can be achieved
+by rendering an initial depth pass (i.e., enabling only depth write to fill the depth
+buffer). Afterwards the geometry is rendered again, this time with full shading. Because the 
+depth buffer is already established, invisible fragments will be discarded before any shading is done calculated.
+
+This approach can be naturally adapted for use with the CHC algorithm. Only an initial depth pass is rendered
+in 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.
+
+\subsection{Batching multiple queries}
+\begin{figure}%[htb]
+{\footnotesize
+  \input{code/pseudocode_batching}
+ }
+  \caption{Pseudo-code of coherent hierarchical culling using multiple queries.}
+  \label{fig:pseudocode_batching}
+\end{figure}
+When occlusion queries are rendered interleaved with geometry, there is always a state change involved. To
+reduce state changes, it is beneficial not to execute one query at a time, but multiple queries at once~\cite{Staneker:2004:EMO}.
+Instead 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.
+To 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}. 
+
 
 \section{Results}
@@ -1028,4 +1058,5 @@
  stop-and-wait application of occlusion queries.
 
+
   The major potential in improving the method is a better estimation
  of changes in the visibility classification of hierarchy nodes. If
@@ -1037,5 +1068,4 @@
  simpler geometry  can be faster than issuing comparably expensive
  occlusion queries.
-
 
 
Index: /trunk/VUT/doc/SciReport/figs/cut.eps
===================================================================
--- /trunk/VUT/doc/SciReport/figs/cut.eps	(revision 243)
+++ /trunk/VUT/doc/SciReport/figs/cut.eps	(revision 251)
@@ -2,6 +2,6 @@
 %%Title: cut.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Mon Aug 22 13:04:52 2005
-%%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000)
+%%CreationDate: Tue Aug 23 20:55:48 2005
+%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 979 330
 %%Magnification: 1.0000
Index: /trunk/VUT/doc/SciReport/figs/dummy.eps
===================================================================
--- /trunk/VUT/doc/SciReport/figs/dummy.eps	(revision 243)
+++ /trunk/VUT/doc/SciReport/figs/dummy.eps	(revision 251)
@@ -2,6 +2,6 @@
 %%Title: dummy.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Mon Aug 22 13:04:52 2005
-%%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000)
+%%CreationDate: Tue Aug 23 20:55:48 2005
+%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 474 443
 %%Magnification: 1.0000
Index: /trunk/VUT/doc/SciReport/figs/latency.eps
===================================================================
--- /trunk/VUT/doc/SciReport/figs/latency.eps	(revision 243)
+++ /trunk/VUT/doc/SciReport/figs/latency.eps	(revision 251)
@@ -2,6 +2,6 @@
 %%Title: latency.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Mon Aug 22 13:04:52 2005
-%%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000)
+%%CreationDate: Tue Aug 23 20:55:48 2005
+%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 1153 326
 %%Magnification: 1.0000
Index: /trunk/VUT/doc/SciReport/figs/latency2.eps
===================================================================
--- /trunk/VUT/doc/SciReport/figs/latency2.eps	(revision 243)
+++ /trunk/VUT/doc/SciReport/figs/latency2.eps	(revision 251)
@@ -2,6 +2,6 @@
 %%Title: latency2.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Mon Aug 22 13:04:52 2005
-%%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000)
+%%CreationDate: Tue Aug 23 20:55:48 2005
+%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 992 393
 %%Magnification: 1.0000
Index: /trunk/VUT/doc/SciReport/figs/basic.eps
===================================================================
--- /trunk/VUT/doc/SciReport/figs/basic.eps	(revision 243)
+++ /trunk/VUT/doc/SciReport/figs/basic.eps	(revision 251)
@@ -2,6 +2,6 @@
 %%Title: basic.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Mon Aug 22 13:04:52 2005
-%%For: bittner@NOTES (Jiri Bittner,U-NOTES\bittner,S-1-5-21-1914904292-1436553889-1205156892-1000)
+%%CreationDate: Tue Aug 23 20:55:48 2005
+%%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 793 244
 %%Magnification: 1.0000
Index: /trunk/VUT/doc/SciReport/Bib/new.bib
===================================================================
--- /trunk/VUT/doc/SciReport/Bib/new.bib	(revision 249)
+++ /trunk/VUT/doc/SciReport/Bib/new.bib	(revision 251)
@@ -28,4 +28,12 @@
 }
 
+@Article{Staneker:2004:EMO,
+   AUTHOR = "Dirk Staneker and Dirk Bartz and Wolfgang Strasser",
+   TITLE = "Efficient Multiple Occlusion Queries for Scene Graph Systems",
+   JOURNAL = "WSI Report (WSI-2004-6)",
+   INSTITUTION = {Wilhelm Schickard Institute for Computer Science, Graphical Interactive Systems (WSI/GRIS), University of T{\"u}bingen},
+   YEAR = "2004",
+   KEYWORDS = {GRIS}
+}
 
 @InProceedings{Meissner01,
Index: /trunk/VUT/doc/SciReport/sampling.tex
===================================================================
--- /trunk/VUT/doc/SciReport/sampling.tex	(revision 249)
+++ /trunk/VUT/doc/SciReport/sampling.tex	(revision 251)
@@ -125,4 +125,27 @@
  objects.
 
- 
+ \subsection{View Cell Representation}
 
+In order to efficiently use view cells with our sampling method, we require a view cell representation which is
+
+\begin{itemize}
+\item optimized for viewcell - ray intersection.
+\item flexible, i.e., it can represent arbitrary geometry.
+\item naturally suited for an hierarchical approach. %(i.e., there is a root view cell containing all others)
+\end{itemize}
+
+We meet these requirements by using a view cell BSP tree, where the BSP leafs are associated with the view cells. 
+Using the BSP tree, we are able to find the initial view cells with only a few view ray-plane intersections. 
+The 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.
+
+Currently we use two approaches to generate the initial BSP view cell tree.
+
+\begin{itemize}
+\item We use a number of dedicated input view cells. As input view cell any closed mesh can be applied. The only requirement
+is 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
+the 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
+can be associated with the same input view cell.
+\item We apply the BSP tree subdivision to the scene geometry. When the subdivision terminates, the leaf nodes
+also represent the view cells. 
+\end{itemize}
+
Index: /trunk/VUT/doc/SciReport/code/actualcode.tex
===================================================================
--- /trunk/VUT/doc/SciReport/code/actualcode.tex	(revision 243)
+++ /trunk/VUT/doc/SciReport/code/actualcode.tex	(revision 251)
Index: /trunk/VUT/doc/SciReport/code/c2tex.tex
===================================================================
--- /trunk/VUT/doc/SciReport/code/c2tex.tex	(revision 243)
+++ /trunk/VUT/doc/SciReport/code/c2tex.tex	(revision 251)
Index: /trunk/VUT/doc/SciReport/code/pseudocode.tex
===================================================================
--- /trunk/VUT/doc/SciReport/code/pseudocode.tex	(revision 243)
+++ /trunk/VUT/doc/SciReport/code/pseudocode.tex	(revision 251)
@@ -1,113 +1,57 @@
 \input default.mac
-\comment{}\leftline{//----\ initialisation
- }
-\normal{}\leftline{ 1:\ \ \ Stack.Push\symbol{}(\normal{}kDTree.Root\symbol{});\normal{}
-\symbol{} }
-\comment{}\leftline{ 2:\ \ \ //----\ while\ there\ are\ some\ nodes\ in\ the\ stack\ or\ the\ query\ queue
- }
-\keya{}\leftline{ 3:\ \ \ while\symbol{}\ (!\normal{}Stack.Empty\symbol{}()\ \normal{}$\symbol{}||\normal{}$\symbol{}\ !\normal{}QueryQueue.Empty\symbol{}())\ $\{$\normal{}
-\symbol{} }
-\leftline{ 4:\ \ \ \ \ \comment{}//----\ PART\ 1:\ processing\ finished\ occlusion\ queries
- }
-\symbol{}\leftline{ 5:\ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}QueryQueue.Empty\symbol{}()\ \&\&\normal{}
-\symbol{} }
-\leftline{ 6:\ \ \ \ \ \ \ \ \ \ \ (\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}())\ \normal{}$\symbol{}||\normal{}$\symbol{}\ \normal{}Stack.Empty\symbol{}()))\ $\{$\normal{}
-\symbol{} }
-\leftline{ 7:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}()))\ $\{$\normal{}
-\symbol{} }
-\leftline{ 8:\ \ \ \ \ \ \ \ \ \comment{}//---\ result\ is\ not\ available\ and\ the\ stack\ is\ empty
- }
-\symbol{}\leftline{ 9:\ \ \ \ \ \ \ \ \ \comment{}//---\ check\ if\ we\ can\ do\ some\ conservative\ decision
- }
-\symbol{}\leftline{10:\ \ \ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.GetLeastCostNode\symbol{}();\normal{}
-\symbol{} }
-\leftline{11:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}N.renderingCost\symbol{}\ <\ \normal{}MaxRenderCost\symbol{})\ $\{$\normal{}
-\symbol{} }
-\leftline{12:\ \ \ \ \ \ \ \ \ \ \normal{}RenderSubtree\symbol{}(\normal{}N\symbol{});\normal{}
-\symbol{} }
-\leftline{13:\ \ \ \ \ \ \ \ \ \ \normal{}QueryQueue.DequeLeastCostNode\symbol{}();\normal{}
-\symbol{} }
-\leftline{14:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ we\ do\ not\ change\ N's\ visibility\ classfication\ -
- }
-\symbol{}\leftline{15:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ N\ remains\ in\ the\ cut\ for\ the\ next\ frame
- }
-\symbol{}\leftline{16:\ \ \ \ \ \ \ \ \ $\}$\ \normal{}else
-\symbol{} }
-\leftline{17:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ wait\ for\ the\ availability\ of\ the\ result
- }
-\symbol{}\leftline{18:\ \ \ \ \ \ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}QueryQueue.ResultAvailable\symbol{})\ \normal{}Wait\symbol{}();\normal{}
-\symbol{} }
-\leftline{19:\ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{}\ $\{$\normal{}
-\symbol{} }
-\leftline{20:\ \ \ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.Dequeue\symbol{}();\normal{}
-\symbol{} }
-\leftline{21:\ \ \ \ \ \ \ \ \ \comment{}//--\ check\ the\ result\ of\ the\ query
- }
-\symbol{}\leftline{22:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}N.visiblePixels\symbol{}\ \normal{}$\symbol{}>\normal{}$\symbol{}\ \normal{}VisibilityThreshold\symbol{}\ )\ \ $\{$\normal{}
-\symbol{} }
-\leftline{23:\ \ \ \ \ \ \ \ \ \ \normal{}N.visibility\symbol{}\ =\ \normal{}VISIBLE\symbol{};\normal{}
-\symbol{} }
-\leftline{24:\ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}IsLeaf\symbol{}(\normal{}N\symbol{}))\normal{}
-\symbol{} }
-\leftline{25:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{});\normal{}
-\symbol{} }
-\leftline{26:\ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{}\ $\{$\normal{}
-\symbol{} }
-\leftline{27:\ \ \ \ \ \ \ \ \ \ \ \ \comment{}//--\ pull\ down
- }
-\symbol{}\leftline{28:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Stack.Push\symbol{}(\normal{}FarChild\symbol{}(\normal{}N\symbol{}));\ \normal{}Stack.Push\symbol{}(\normal{}CloseChild\symbol{}(\normal{}N\symbol{}));\normal{}
-\symbol{} }
-\leftline{29:\ \ \ \ \ \ \ \ \ \ $\}$\normal{}
-\symbol{} }
-\leftline{30:\ \ \ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{}\ $\{$\normal{}
-\symbol{} }
-\leftline{31:\ \ \ \ \ \ \ \ \ \ \normal{}N.visibility\symbol{}\ =\ \normal{}INVISIBLE\symbol{};\normal{}
-\symbol{} }
-\leftline{32:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ pull\ up
- }
-\symbol{}\leftline{33:\ \ \ \ \ \ \ \ \ \ \normal{}PullUpInvisibility\symbol{}(\normal{}N\symbol{});\normal{}
-\symbol{} }
-\leftline{34:\ \ \ \ \ \ \ \ \ $\}$\normal{}
-\symbol{} }
-\leftline{35:\ \ \ \ \ \ \ $\}$\normal{}
-\symbol{} }
-\leftline{36:\ \ \ \ \ $\}$\normal{}
-\symbol{} }
-\leftline{37:\ \ \ \ \ \normal{}
-\symbol{} }
-\leftline{38:\ \ \ \ \ \comment{}//----\ PART\ 2:\ kd-tree\ traversal
- }
-\symbol{}\leftline{39:\ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}Stack.Empty\symbol{}())\ $\{$\normal{}
-\symbol{} }
-\leftline{40:\ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}Stack.Pop\symbol{}();\normal{}
-\symbol{} }
-\leftline{41:\ \ \ \ \ \ \ \normal{}N.lastVisited\symbol{}\ =\ \normal{}frameID\symbol{};\normal{}
-\symbol{} }
-\leftline{42:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}InsideViewFrustum\symbol{}(\normal{}N\symbol{}))\ $\{$\normal{}
-\symbol{} }
-\leftline{43:\ \ \ \ \ \ \ \ \ \comment{}//--\ skip\ testing\ of\ all\ nodes\ above\ the\ cut
- }
-\symbol{}\leftline{44:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}IsAboveTheCut\symbol{}(\normal{}N\symbol{}))\ $\{$\normal{}
-\symbol{} }
-\leftline{45:\ \ \ \ \ \ \ \ \ \ \normal{}IssueOcclustionQuery\symbol{}(\normal{}N\symbol{});\ \normal{}QueryQueue.Enqueue\symbol{}(\normal{}N\symbol{});\normal{}
-\symbol{} }
-\leftline{46:\ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}WasVisible\symbol{}(\normal{}N\symbol{})\ \normal{}$\symbol{}\&\&\normal{}$\symbol{}\ \normal{}IsLeaf\symbol{}(\normal{}N\symbol{}))\normal{}
-\symbol{} }
-\leftline{47:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{});\normal{}
-\symbol{} }
-\leftline{48:\ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{}\ $\{$\normal{}
-\symbol{} }
-\leftline{49:\ \ \ \ \ \ \ \ \ \ \ \ \comment{}//--\ go\ down\ the\ kD-tree
- }
-\symbol{}\leftline{50:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Stack.Push\symbol{}(\normal{}FarChild\symbol{}(\normal{}N\symbol{}));\ \normal{}Stack.Push\symbol{}(\normal{}CloseChild\symbol{}(\normal{}N\symbol{}));\ \normal{}
-\symbol{} }
-\leftline{51:\ \ \ \ \ \ \ \ \ \ $\}$\normal{}
-\symbol{} }
-\leftline{52:\ \ \ \ \ \ \ \ \ $\}$\normal{}
-\symbol{} }
-\leftline{53:\ \ \ \ \ \ \ $\}$\normal{}
-\symbol{} }
-\leftline{54:\ \ \ \ \ $\}$\normal{}
-\symbol{} }
-\leftline{55:\ \ \ $\}$\normal{}
-\symbol{} }
+\comment{}\leftline{//----\ initialisation }
+\normal{}\leftline{ 1:\ \ \ Stack.Push\symbol{}(\normal{}kDTree.Root\symbol{}); }
+\comment{}\leftline{ 2:\ \ \ //----\ while\ there\ are\ some\ nodes\ in\ the\ stack\ or\ the\ query\ queue }
+\keya{}\leftline{ 3:\ \ \ while\symbol{}\ (!\normal{}Stack.Empty\symbol{}()\ \normal{}$\symbol{}||\normal{}$\symbol{}\ !\normal{}QueryQueue.Empty\symbol{}())\ $\{$ }
+\leftline{ 4:\ \ \ \ \ \comment{}//----\ PART\ 1:\ processing\ finished\ occlusion\ queries }
+\symbol{}\leftline{ 5:\ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}QueryQueue.Empty\symbol{}()\ \&\& }
+\leftline{ 6:\ \ \ \ \ \ \ \ \ \ \ (\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}())\ \normal{}$\symbol{}||\normal{}$\symbol{}\ \normal{}Stack.Empty\symbol{}()))\ $\{$ }
+\leftline{ 7:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}ResultAvailable\symbol{}(\normal{}QueryQueue.Front\symbol{}()))\ $\{$ }
+\leftline{ 8:\ \ \ \ \ \ \ \ \ \comment{}//---\ result\ is\ not\ available\ and\ the\ stack\ is\ empty }
+\symbol{}\leftline{ 9:\ \ \ \ \ \ \ \ \ \comment{}//---\ check\ if\ we\ can\ do\ some\ conservative\ decision }
+\symbol{}\leftline{10:\ \ \ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.GetLeastCostNode\symbol{}(); }
+\leftline{11:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}N.renderingCost\symbol{}\ <\ \normal{}MaxRenderCost\symbol{})\ $\{$ }
+\leftline{12:\ \ \ \ \ \ \ \ \ \ \normal{}RenderSubtree\symbol{}(\normal{}N\symbol{}); }
+\leftline{13:\ \ \ \ \ \ \ \ \ \ \normal{}QueryQueue.DequeLeastCostNode\symbol{}(); }
+\leftline{14:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ we\ do\ not\ change\ N's\ visibility\ classfication\ - }
+\symbol{}\leftline{15:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ N\ remains\ in\ the\ cut\ for\ the\ next\ frame }
+\symbol{}\leftline{16:\ \ \ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{} }
+\leftline{17:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ wait\ for\ the\ availability\ of\ the\ result }
+\symbol{}\leftline{18:\ \ \ \ \ \ \ \ \ \ \keya{}while\symbol{}\ (!\normal{}QueryQueue.ResultAvailable\symbol{})\ \normal{}Wait\symbol{}(); }
+\leftline{19:\ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{}\ $\{$ }
+\leftline{20:\ \ \ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}QueryQueue.Dequeue\symbol{}(); }
+\leftline{21:\ \ \ \ \ \ \ \ \ \comment{}//--\ check\ the\ result\ of\ the\ query }
+\symbol{}\leftline{22:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\ \normal{}N.visiblePixels\symbol{}\ \normal{}$\symbol{}>\normal{}$\symbol{}\ \normal{}VisibilityThreshold\symbol{}\ )\ \ $\{$ }
+\leftline{23:\ \ \ \ \ \ \ \ \ \ \normal{}N.visibility\symbol{}\ =\ \normal{}VISIBLE\symbol{}; }
+\leftline{24:\ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}IsLeaf\symbol{}(\normal{}N\symbol{})) }
+\leftline{25:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{}); }
+\leftline{26:\ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{}\ $\{$ }
+\leftline{27:\ \ \ \ \ \ \ \ \ \ \ \ \comment{}//--\ pull\ down }
+\symbol{}\leftline{28:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Stack.Push\symbol{}(\normal{}FarChild\symbol{}(\normal{}N\symbol{}));\ \normal{}Stack.Push\symbol{}(\normal{}CloseChild\symbol{}(\normal{}N\symbol{})); }
+\leftline{29:\ \ \ \ \ \ \ \ \ \ $\}$ }
+\leftline{30:\ \ \ \ \ \ \ \ \ $\}$\ \keya{}else\symbol{}\ $\{$ }
+\leftline{31:\ \ \ \ \ \ \ \ \ \ \normal{}N.visibility\symbol{}\ =\ \normal{}INVISIBLE\symbol{}; }
+\leftline{32:\ \ \ \ \ \ \ \ \ \ \comment{}//--\ pull\ up }
+\symbol{}\leftline{33:\ \ \ \ \ \ \ \ \ \ \normal{}PullUpInvisibility\symbol{}(\normal{}N\symbol{}); }
+\leftline{34:\ \ \ \ \ \ \ \ \ $\}$ }
+\leftline{35:\ \ \ \ \ \ \ $\}$ }
+\leftline{36:\ \ \ \ \ $\}$ }
+\leftline{37:\ \ \ \ \  }
+\leftline{38:\ \ \ \ \ \comment{}//----\ PART\ 2:\ kd-tree\ traversal }
+\symbol{}\leftline{39:\ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}Stack.Empty\symbol{}())\ $\{$ }
+\leftline{40:\ \ \ \ \ \ \ \normal{}N\symbol{}\ =\ \normal{}Stack.Pop\symbol{}(); }
+\leftline{41:\ \ \ \ \ \ \ \normal{}N.lastVisited\symbol{}\ =\ \normal{}frameID\symbol{}; }
+\leftline{42:\ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}InsideViewFrustum\symbol{}(\normal{}N\symbol{}))\ $\{$ }
+\leftline{43:\ \ \ \ \ \ \ \ \ \comment{}//--\ skip\ testing\ of\ all\ nodes\ above\ the\ cut }
+\symbol{}\leftline{44:\ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (!\normal{}IsAboveTheCut\symbol{}(\normal{}N\symbol{}))\ $\{$ }
+\leftline{45:\ \ \ \ \ \ \ \ \ \ \normal{}IssueOcclustionQuery\symbol{}(\normal{}N\symbol{});\ \normal{}QueryQueue.Enqueue\symbol{}(\normal{}N\symbol{}); }
+\leftline{46:\ \ \ \ \ \ \ \ \ \ \keya{}if\symbol{}\ (\normal{}WasVisible\symbol{}(\normal{}N\symbol{})\ \normal{}$\symbol{}\&\&\normal{}$\symbol{}\ \normal{}IsLeaf\symbol{}(\normal{}N\symbol{})) }
+\leftline{47:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Render\symbol{}(\normal{}N\symbol{}); }
+\leftline{48:\ \ \ \ \ \ \ \ \ \ \keya{}else\symbol{}\ $\{$ }
+\leftline{49:\ \ \ \ \ \ \ \ \ \ \ \ \comment{}//--\ go\ down\ the\ kD-tree }
+\symbol{}\leftline{50:\ \ \ \ \ \ \ \ \ \ \ \ \normal{}Stack.Push\symbol{}(\normal{}FarChild\symbol{}(\normal{}N\symbol{}));\ \normal{}Stack.Push\symbol{}(\normal{}CloseChild\symbol{}(\normal{}N\symbol{}));\  }
+\leftline{51:\ \ \ \ \ \ \ \ \ \ $\}$ }
+\leftline{52:\ \ \ \ \ \ \ \ \ $\}$ }
+\leftline{53:\ \ \ \ \ \ \ $\}$ }
+\leftline{54:\ \ \ \ \ $\}$ }
+\leftline{55:\ \ \ $\}$ }
Index: /trunk/VUT/doc/SciReport/code/pseudocode_batching.cpp
===================================================================
--- /trunk/VUT/doc/SciReport/code/pseudocode_batching.cpp	(revision 251)
+++ /trunk/VUT/doc/SciReport/code/pseudocode_batching.cpp	(revision 251)
@@ -0,0 +1,60 @@
+Algorithm: Traversal of the kD-tree applying batching of multiple queries
+TraversalStack.Push(kDTree.Root);
+while ( not TraversalStack.Empty() or
+        not QueryQueue.Empty() ) {
+  //---- PART 1: processing finished occlusion queries
+  while ( not QueryQueue.Empty() and
+	  (ResultAvailable(QueryQueue.Front()) or
+	   TraversalStack.Empty()) ) {
+    N = QueryQueue.Dequeue();
+    // wait if result not available
+    visiblePixels = GetOcclussionQueryResult(N);
+    if ( visiblePixels > VisibilityThreshold ) {
+      PullUpVisibility(N);
+      TraverseNode(N);
+    }
+  }
+  //---- PART 2: kd-tree traversal
+  if ( not TraversalStack.Empty() ) {
+    N = TraversalStack.Pop();
+    if ( InsideViewFrustum(N) ) {
+      // identify previously visible nodes
+      wasVisible = N.visible && (N.lastVisited == frameID -1);
+      // identify previously opened nodes
+      opened = wasVisible && !IsLeaf(N);
+      // reset node's visibility classification
+      N.visible = false;
+      // update node's visited flag
+      N.lastVisited = frameID;
+      // skip testing all previously opened nodes
+      if ( !opened ) {
+		  // add to the pending queue instead of immediate query
+		  if (PendingQueue.size() < n)
+			  PendingQueue.Enqueue(N);
+		  else
+		  {
+			  IssueMultipleOcclusionQueries(PendingQueue);
+			  AddToQueryQueue(PendingQueue, QueryQueue);
+			  PendingQueue.clear();
+		  }
+      }
+      // traverse a node unless it was invisible
+      if ( wasVisible )
+	TraverseNode(N);
+    }
+  }
+
+  // add rest to query queue
+  IssueMultipleOcclusionQueries(PendingQueue);
+  AddToQueryQueue(PendingQueue, QueryQueue);
+  PendingQueue.clear();
+}
+TraverseNode(N) {
+  if ( IsLeaf(N) )
+    Render(N);
+  else
+    TraversalStack.PushChildren(N);
+}
+PullUpVisibility(N) {
+  while (!N.visible) { N.visible = true; N = N.parent; }
+}
Index: /trunk/VUT/doc/SciReport/code/pseudocode2.tex
===================================================================
--- /trunk/VUT/doc/SciReport/code/pseudocode2.tex	(revision 243)
+++ /trunk/VUT/doc/SciReport/code/pseudocode2.tex	(revision 251)
