Index: trunk/VUT/doc/SciReport/preprocessing.tex
===================================================================
--- trunk/VUT/doc/SciReport/preprocessing.tex	(revision 269)
+++ trunk/VUT/doc/SciReport/preprocessing.tex	(revision 272)
@@ -37,5 +37,5 @@
 
 In traditional visibility preprocessing the view space is
-subdivided into viewcells and for each view cell the set of visible
+subdivided into view cells and for each view cell the set of visible
 objects --- potentially visible set (PVS) is computed. This framewoirk
 has bee used for conservative, aggresive and exact algorithms.
@@ -56,5 +56,5 @@
 casting rays through the scene and collecting their contributions. A
 visibility sample is computed by casting a ray from an object towards
-the viewcells and computing the nearest intersection with the scene
+the view cells and computing the nearest intersection with the scene
 objects. All view cells pierced by the ray segment can see the object and
 thus the object can be added to their PVS. If the ray is terminated at
@@ -62,5 +62,5 @@
 extended by this terminating object. Thus a single ray can make a
 number of contributions to the progressively computed PVSs. A ray
-sample piercing $n$ viewcells which is bound by two distinct objects
+sample piercing $n$ view cells which is bound by two distinct objects
 contributes by at most $2*n$ entries to the current PVSs. Appart from
 this performance benefit there is also a benefit in terms of the
@@ -106,7 +106,7 @@
 
 The first modification to the basic algorithm accounts for
-irregular distribution of the viewcells. Such a case in common for
-example in urban scenes where the viewcells are mostly distributed in
-a horizontal direction and more viewcells are placed at denser parts
+irregular distribution of the view cells. Such a case in common for
+example in urban scenes where the view cells are mostly distributed in
+a horizontal direction and more view cells are placed at denser parts
 of the city. The modification involves replacing the uniformly
 distributed ray direction by direction distribution according to the
@@ -124,5 +124,5 @@
 
 \begin{itemize}
-\item optimized for viewcell - ray intersection.
+\item optimized for view cell - 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)
Index: trunk/VUT/doc/SciReport/figs/latency.eps
===================================================================
--- trunk/VUT/doc/SciReport/figs/latency.eps	(revision 251)
+++ trunk/VUT/doc/SciReport/figs/latency.eps	(revision 272)
@@ -2,5 +2,5 @@
 %%Title: latency.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Tue Aug 23 20:55:48 2005
+%%CreationDate: Thu Sep 15 12:53:15 2005
 %%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 1153 326
Index: trunk/VUT/doc/SciReport/figs/dummy.eps
===================================================================
--- trunk/VUT/doc/SciReport/figs/dummy.eps	(revision 251)
+++ trunk/VUT/doc/SciReport/figs/dummy.eps	(revision 272)
@@ -2,5 +2,5 @@
 %%Title: dummy.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Tue Aug 23 20:55:48 2005
+%%CreationDate: Thu Sep 15 12:53:14 2005
 %%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 474 443
Index: trunk/VUT/doc/SciReport/figs/cut.eps
===================================================================
--- trunk/VUT/doc/SciReport/figs/cut.eps	(revision 251)
+++ trunk/VUT/doc/SciReport/figs/cut.eps	(revision 272)
@@ -2,5 +2,5 @@
 %%Title: cut.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Tue Aug 23 20:55:48 2005
+%%CreationDate: Thu Sep 15 12:53:13 2005
 %%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 979 330
Index: trunk/VUT/doc/SciReport/figs/latency2.eps
===================================================================
--- trunk/VUT/doc/SciReport/figs/latency2.eps	(revision 251)
+++ trunk/VUT/doc/SciReport/figs/latency2.eps	(revision 272)
@@ -2,5 +2,5 @@
 %%Title: latency2.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Tue Aug 23 20:55:48 2005
+%%CreationDate: Thu Sep 15 12:53:16 2005
 %%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 992 393
Index: trunk/VUT/doc/SciReport/figs/basic.eps
===================================================================
--- trunk/VUT/doc/SciReport/figs/basic.eps	(revision 251)
+++ trunk/VUT/doc/SciReport/figs/basic.eps	(revision 272)
@@ -2,5 +2,5 @@
 %%Title: basic.fig
 %%Creator: fig2dev Version 3.2 Patchlevel 4
-%%CreationDate: Tue Aug 23 20:55:48 2005
+%%CreationDate: Thu Sep 15 12:53:12 2005
 %%For: matt@sakura (matt,U-COMPUTERGRAPHIK\matt,S-1-5-21-1259991482-2646404242-2158041560-3508)
 %%BoundingBox: 0 0 793 244
Index: trunk/VUT/doc/SciReport/mutual.tex
===================================================================
--- trunk/VUT/doc/SciReport/mutual.tex	(revision 269)
+++ trunk/VUT/doc/SciReport/mutual.tex	(revision 272)
@@ -16,11 +16,11 @@
 This boundary it is based on the current view cell visibility
 classifications. We assume that there is a defined connectivity
-between the viewcells which is the case for both BSP-tree or kD-tree
-based view cells. Then given a PVS consisting of visible viewcells
+between the view cells which is the case for both BSP-tree or kD-tree
+based view cells. Then given a PVS consisting of visible view cells
 (with respect to an object) we can find all the neighbors of the
-visible viewcells which are invisible. In order words a view cell
+visible view cells which are invisible. In order words a view cell
 belongs to this boundary if it is classified invisible and has at
 least one visible neighbor. If all view cells from this boundary are
-proven invisible, no other viewcell (behind this boundary) can be
+proven invisible, no other view cell (behind this boundary) can be
 visible. If the verification determines some view cells as visible,
 the current invisible boundary is extended and the verification is
@@ -378,9 +378,9 @@
 
 For the computation of the maximal error due to the current shaft we
-assume that one tested region is a viewcell, whereas the other is an
+assume that one tested region is a view cell, whereas the other is an
 object bounding box or cell of the spatial hierarchy. The threshold is
 computed as follows: We first triangulate the farthest intersection
 points in the shaft as seen from the view cell side of the shaft. Then
-for each computed triangle we calculate a point in the viewcell which
+for each computed triangle we calculate a point in the view cell which
 maximizes the projected area of the triangle. The conservative
 estimate of the maximal error is then given by a sum of the computed
@@ -396,9 +396,9 @@
 % The basic idea is the following:
 
-% Use 2 plane parametrization for describing all lines intersecting the object and the viewcell. The line sets will be described by aligned rectangles on the two planes which allows to construct convex shafts bounded always by only 4 lines. After determing the initial rectangles bounding the whole line set perform recursive subdivsion as follows:
+% Use 2 plane parametrization for describing all lines intersecting the object and the view cell. The line sets will be described by aligned rectangles on the two planes which allows to construct convex shafts bounded always by only 4 lines. After determing the initial rectangles bounding the whole line set perform recursive subdivsion as follows:
 
 % 1. Cast the 4 corner rays and deterine ALL intersections with the occluding objects
 
-% 2. If any ray is unoccluded termite the whole test with VISIBLE and extend the PVS of the object with the new viecell (and possibly more if the rays goes further). Start the verification for the new viewcells in the occluded layer.
+% 2. If any ray is unoccluded termite the whole test with VISIBLE and extend the PVS of the object with the new view cell (and possibly more if the rays goes further). Start the verification for the new view cells in the occluded layer.
 
 % 3. If all 4 rays pierce the same convex mesh, (or mesh triangle for non convex meshes) terminate this branch with INVISIBLE. Note the terminating mesh need not be the front most one.
@@ -407,5 +407,5 @@
 % Note that here it would be the best to selected those intersections for the rays which have the most similar depths to better estimate the maximal error, i.e. the "depth triangles" need not be formed by the first visible layer.
 
-% 5. If 4 does not terminate subdivide either the viewcell or the object rectangle depending on the sample depths and error computed.
+% 5. If 4 does not terminate subdivide either the view cell or the object rectangle depending on the sample depths and error computed.
 
 % It is actually quite simple to create a conservative variant of the algorithm: subdivide only to a given depth and avoid test 4. Then the samples can only be terminated by a "STRONG occluder" which hides the whole shaft. This is similar to Dannys method, but here a hierarchical shaft subdivision is performed which should deliver much more accuracy.
Index: trunk/VUT/doc/SciReport/sampling.tex
===================================================================
--- trunk/VUT/doc/SciReport/sampling.tex	(revision 266)
+++ trunk/VUT/doc/SciReport/sampling.tex	(revision 272)
@@ -30,5 +30,5 @@
 
 In traditional visibility preprocessing the view space is
-subdivided into viewcells and for each view cell the set of visible
+subdivided into view cells and for each view cell the set of visible
 objects --- potentially visible set (PVS) is computed. This framewoirk
 has been used for conservative, aggresive and exact algorithms.
@@ -243,40 +243,110 @@
 \subsection{View Cell Representation}
 
+\begin{figure}[htb]
+  \centerline{
+    \includegraphics[height=0.35\textwidth,draft=\DRAFTFIGS]{images/vienna_viewcells_01}
+     \includegraphics[height=0.35\textwidth,draft=\DRAFTFIGS]{images/vienna_viewcells_07}
+    }
+
+  \caption{(left) Vienna viewcells. (right) The view cells are prisms with a triangular base. }
+  \label{fig:vienna_viewcells}
+\end{figure}
+
+
+A good partition of the scene into view cells is an essential part of every visibility
+system. If they are chosen too large, the PVS (Potentially Visibible Set) 
+of a view cells is too large for efficient culling. If they are chosen too small or
+without consideration, then neighbouring view cells contain redundant PVS information,
+hence boosting the PVS computation and storage costs for the scene. In the left image of figure~\ref{fig:vienna_viewcells} we see view cells of the Vienna model, generated by triangulation of the streets. 
+In the closeup (right image) we can see that each triangle is extruded to a given height to form a view cell prism.
+
 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 optimized for view cell - ray intersection.
 \item flexible, i.e., it can represent arbitrary geometry.
 \item naturally suited for a 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.
+We meet these requirements by employing spatial subdivisions (i.e., 
+KD trees and BSP trees), to store the view cells. The initial view cells are
+associated with the leaves. The reason why we chose BSP trees as view cell representation 
+is that they are very flexible. View cells forming arbitrary closed meshes can be closely matched.
+Therefore we are able to find a view cells with only a few view ray-plane
+intersections.  Furthermore, the hierarchical structures can be
+exploited as hierarchy of view cells. Interior nodes form larger view cells
+containing the children. If neccessary, a leaf can be easily subdivided into smaller view cells.
+
+Currently we consider three different approaches to generate the initial view cell BSP tree.
+The third method is not restricted to BSP trees, but BSP trees are prefered 
+because of their greater flexibility.
+
+
+\begin{table}
+\centering \footnotesize
+\begin{tabular}{|l|c|c|}
+  \hline\hline
+  View cells & Vienna selection & Vienna full \\\hline\hline
+  \#view cells & 105 & 16447 \\\hline\hline
+  \#input polygons & 525 & 82235 \\\hline\hline
+  BSP tree generation time & 0.016s & 10.328s \\\hline\hline
+  view cell insertion time & 0.016s & 7.984s \\\hline\hline
+  \#nodes & 1137 & 597933 \\\hline\hline
+	\#interior nodes & 568 & 298966\\\hline\hline
+	\#leaf nodes  & 569 & 298967\\\hline\hline
+	\#splits & 25 & 188936\\\hline\hline
+	max tree depth & 13 & 27\\\hline\hline
+	avg tree depth & 9.747 & 21.11\\\hline\hlien
+	
+ \end{tabular}
+ \caption{Statistics for view cell BSP tree on the Vienna view cells and a selection of the Vienna view cells.}\label{tab:viewcell_bsp}
+\end{table}
+
 
 \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,
+\item We use a number of input view cells given in advance. As input view cell 
+any closed mesh can be applied. The only requirement is that the
+any two view cells do not overlap. 
+First the view cell polygons are extracted, and the BSP is build from
+these polygons using some global optimizations like tree balancing or
+least splits. Then one view cell after the other
+is inserted into the tree to find out the leafes where they are contained
+in. The polygons of the 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
+the inside of the last split plane (i.e., the leaf represents 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.
-
+(i.e., add a pointer to the view cell). One input view cell can
+be associated with many leafes, whereas each leafs has only one view cell.
+Some statistics about using this method on the vienna view cells set are given in table~\ref{tab:viewcell_bsp}.
+However, sometimes a good set of view cells is not available. Or the scene
+is changed frequently, and the designer does not want to create new view cells on each change.
+In such a case one of the following two methods should rather be chosen, which generate view cells
+automatically.
+
+
+\item We apply a BSP tree subdivision to the scene geometry. Whenever
+the subdivision terminates in a leaf, a view cell is associated with the leaf node.
+This simple approach is justified because it places the view cell borders 
+along some discontinuities in the visibility function.
+
+\item  The view cell generation can be guided by the sampling process. We start with
+with a single initial view cell representing the whole space. If a given threshold
+is reached during the preprocessing (e.g., the view cell is pierced by too many rays 
+resulting in a large PVS), the view cell is subdivided into smaller cells using some criteria.
+
+In order to evaluate the best split plane, we first have to define the characteristics of a
+good view cell partition:  The view cells should be quite large, while their PVS stays rather small.
+The PVS of each two view cells should be as distinct as possible, otherwise they could be
+merged into a larger view cell if the PVSs are too similar. 
+E.g., for a building, the perfect view cells are usually the single rooms connected by portals.
+
+Hence we can define some useful criteria for the split: 1) the number of rays should be roughly equal among the new view cells. 2) The split plane should be chosen in a way that the rays are maximal distinct, i.e., the number
+of rays contributing to more than one cell should be minimized => the PVSs are also distinct. 3) For BSP trees,
+the split plane should be aligned with some scene geometry which is large enough to contribute
+a lot of occlusion power. This criterium can be naturally combined with the second one.
+As termination criterium we can choose the minimum PVS / piercing ray size or the maximal tree depth.
 \end{itemize}
 
@@ -286,5 +356,5 @@
 casting rays through the scene and collecting their contributions. A
 visibility sample is computed by casting a ray from an object towards
-the viewcells and computing the nearest intersection with the scene
+the view cells and computing the nearest intersection with the scene
 objects. All view cells pierced by the ray segment can the object and
 thus the object can be added to their PVS. If the ray is terminated at
@@ -292,6 +362,6 @@
 extended by this terminating object. Thus a single ray can make a
 number of contributions to the progressively computed PVSs. A ray
-sample piercing $n$ viewcells which is bound by two distinct objects
-contributes by at most $2*n$ entries to the current PVSs. Appart from
+sample piercing $n$ view cells which is bound by two distinct objects
+contributes by at most $2*n$ entries to the current PVSs. Apart from
 this performance benefit there is also a benefit in terms of the
 sampling density: Assuming that the view cells are usually much larger
@@ -302,5 +372,5 @@
 At this phase of the computation we not only start the samples from
 the objects, but we also store the PVS information centered at the
-objects. Instead of storing a PVSs consting of objects visible from
+objects. Instead of storing a PVS consting of objects visible from
 view cells, every object maintains a PVS consisting of potentially
 visible view cells. While these representations contain exactly the
@@ -336,7 +406,7 @@
 
  The first modification to the basic algorithm accounts for irregular
-distribution of the viewcells. Such a case is common for example in
-urban scenes where the viewcells are mostly distributed in a
-horizontal direction and more viewcells are placed at denser parts of
+distribution of the view cells. Such a case is common for example in
+urban scenes where the view cells are mostly distributed in a
+horizontal direction and more view cells are placed at denser parts of
 the city. The modification involves replacing the uniformly
 distributed ray direction by directions distributed according to the
