Index: trunk/VUT/doc/SciReport/introduction.tex
===================================================================
--- trunk/VUT/doc/SciReport/introduction.tex	(revision 255)
+++ trunk/VUT/doc/SciReport/introduction.tex	(revision 266)
@@ -1,23 +1,17 @@
-\chapter{Overview of visibility problems and algorithms}%\chapter
+\chapter{Introduction to visibility problems and algorithms}%\chapter
 
 \label{chap:overview}
 \label{chap:classes}
 
- This chapter provides a taxonomy of visibility problems encountered
-in computer graphics based on the {\em problem domain} and the {\em
+ This chapter provides introduction to visibility problems and
+algorithms for computer graphics. In particular it presents a taxonomy
+of visibility problems based on the {\em problem domain} and the {\em
 type of the answer}. The taxonomy helps to understand the nature of a
 particular visibility problem and provides a tool for grouping
 problems of similar complexity independently of their target
 application. We discuss typical visibility problems encountered in
-computer graphics and identify their relation to the proposed
-taxonomy. A visibility problem can be solved by means of various
-visibility algorithms. We classify visibility algorithms according to
-several important criteria and discuss important concepts in the
-design of a visibility algorithm. The taxonomy and the discussion of
-the algorithm design sums up ideas and concepts that are independent
-of any specific algorithm. This can help algorithm designers to
-transfer the existing algorithms to solve visibility problems in other
-application areas.
-
+computer graphics including their relation to the presented
+taxonomy. Finally, we classify the latert described visibility tools
+according to the presented taxonomy.
 
 
@@ -314,5 +308,5 @@
 most general visibility problems. In 3D the ${\cal L}_R$ is a 4D
 subset of the 4D line space. In 2D the ${\cal L}_R$ is a 2D subset of
-the 2D line space. Consequently, in the proposed classification
+the 2D line space. Consequently, in the presented classification
 visibility from a region in 2D is equivalent to visibility from a line
 segment in 2D.
@@ -518,4 +512,47 @@
 is neither its subset or its superset for all possible inputs.
 
+ A more precise quality measure of algorithms computing PVSs can be
+expressed by the {\em relative overestimation} and the {\em relative
+underestimation} of the PVS with respect to the exact PVS.  We can
+define a quality measure of an algorithm $A$ on input $I$ as a tuple
+$\mbi{Q}^A(I)$:
+
+\begin{eqnarray}
+  \mbi{Q}^A(I) & = & (Q^A_o(I), Q^A_u(I)), \qquad  I \in {\cal D} \\
+  Q^A_o(I) & = & {|S^A(I) \setminus S^{\cal E}(I)| \over |S^{\cal E}(I)|} \\
+  Q^A_u(I) & = & {|S^{\cal E}(I) \setminus S^A(I) | \over |S^{\cal E}(I)|}
+\end{eqnarray}
+
+where $I$ is an input from the input domain ${\cal D}$, $S^A(I)$ is
+the PVS determined by the algorithm $A$ for input $I$ and $S^{\cal
+E}(I)$ is the exact PVS for the given input. $Q^A_o(I)$ expresses the
+{\em relative overestimation} of the PVS, $Q^A_u(I)$ is the {\em
+relative underestimation}.
+
+The expected quality of the algorithm over all possible inputs can be
+given as:
+
+\begin{eqnarray}
+Q^A & = & E[\| \mbi{Q}^A(I) \|] \\
+    & = & \sum_{\forall I \in {\cal D}} f(I).\sqrt{Q^A_o(I)^2 + Q^A_o(I)^2}
+\end{eqnarray}
+
+where f(I) is the probability density function expressing the
+probability of occurrence of input $I$. The quality measure
+$\mbi{Q}^A(I)$ can be used to classify a PVS algorithm into one of the
+four accuracy classes according to Section~\ref{sec:accuracy}:
+
+\begin{enumerate}
+\item exact\\
+  $\forall I \in {\cal D} :Q_o^A(I) = 0 \wedge Q_u^A(I) = 0$
+\item conservative\\
+  $\forall I \in {\cal D} : Q_o^A(I) \geq 0 \wedge Q_u^A(I) = 0$
+\item aggressive \\
+  $\forall I \in {\cal D} : Q_o^A(I) = 0 \wedge Q_u^A(I) \geq 0$
+\item approximate \\
+  $\qquad \exists I_j, I_k \in {\cal D}: Q_o^A(I_j) > 0 \wedge Q_u^A(I_k) > 0$
+\end{enumerate}
+
+
 
 \subsection{Solution space}
@@ -542,6 +579,5 @@
 
  The classification according to the solution space is easily
-demonstrated on visible surface algorithms (these algorithms will be
-discussed in Section~\ref{chap:traditional}). The
+demonstrated on visible surface algorithms: The
 z-buffer~\cite{Catmull:1975:CDC} is a common example of a discrete
 algorithm. The Weiler-Atherton algorithm~\cite{Weiler:1977:HSR} is an
@@ -583,645 +619,14 @@
 %*****************************************************************************
 
-\section{Visibility algorithm design}
-
- Visibility algorithm design can be decoupled into a series of
-important design decisions. The first step is to clearly formulate a
-problem that should be solved by the algorithm. The  taxonomy stated
-above can help to understand the difficulty of solving the given
-problem and its relationship to other visibility problems in computer
-graphics. The following sections summarize important steps in the
-design of a visibility algorithm and discuss some commonly used
-techniques.
-
-
-\subsection{Scene structuring}
-
- We discuss two issues dealing with structuring of the scene:
-identifying occluders and occludees, and spatial data structures for
-scene description.
-
-\subsubsection{Occluders and occludees}
-%occluders, occludees, 
-
-Many visibility algorithms restructure the scene description to
-distinguish between {\em occluders} and {\em occludees}.  Occluders
-are objects that cause changes in visibility (occlusion). Occludees
-are objects that do not cause occlusion, but are sensitive to
-visibility changes. In other words the algorithm studies visibility of
-occludees with respect to occluders.
-
-The concept of occluders and occludees is used to increase the
-performance of the algorithm in both the running time and the accuracy
-of the algorithm by reducing the number of primitives used for
-visibility computations (the performance measures of visibility
-algorithms will be discussed in
-Section~\ref{sec:performance}). Typically, the number of occluders and
-occludees is significantly smaller than the total number of objects in
-the scene. Additionally, both the occluders and the occludees can be
-accompanied with a topological (connectivity) information that might
-be necessary for an efficient functionality of the algorithm.
-
- The concept of occluders is applicable to most visibility
-algorithms. The concept of occludees is useful for algorithms
-providing answers (1) and (2) according to the taxonomy of
-Section~\ref{sec:answers}. Some visibility algorithms do not
-distinguish between occluders and occludees at all. For example all
-traditional visible surface algorithms use all scene objects as both
-occluders and occludees.
-
- Both the occluders and the occludees can be represented by {\em
-virtual objects} constructed from the scene primitives: the occluders
-as simplified inscribed objects, occludees as simplified circumscribed
-objects such as bounding boxes. Algorithms can be classified according
-to the type of occluders they deal with. The classification follows
-the scene restrictions discussed in
-Section~\ref{sec:scene_restrictions} and adds classes specific to
-occluder restrictions:
-
-\begin{itemize}
-\item
-  vertical prisms,
-\item
-  axis-aligned polygons,
-\item
-  axis-aligned rectangles.
-\end{itemize}
-  
- The vertical prisms that are specifically important for computing
-visibility in \m25d scenes. Some visibility algorithms can deal only
-with axis-aligned polygons or even more restrictive axis-aligned
-rectangles.
-
-
-\begin{figure}[htb]
-\centerline{
-\includegraphics[width=0.7\textwidth,draft=\DRAFTIMAGES]{images/houses}}
-\caption{Occluders in an urban scene. In urban scenes the occluders
-can be considered vertical prisms erected above the ground.}
-\label{fig:houses}
-\end{figure}
-
-Other important criteria for evaluating algorithms according to
-occluder restrictions include:
-
-
-\begin{itemize}
-\item
-  connectivity information,
-\item
-  intersecting occluders.
-\end{itemize}
-
-
-The explicit knowledge of the connectivity is crucial for efficient
-performance of some visibility algorithms (performance measures will
-be discussed in the Section~\ref{sec:performance}). Intersecting
-occluders cannot be handled properly by some visibility algorithms.
-In such a case the possible occluder intersections should be resolved
-in preprocessing.
-
- A similar classification can be applied to occludees. However, the
-visibility algorithms typically pose less restrictions on occludees
-since they are not used to describe visibility but only to check
-visibility with respect to the description provided by the occluders.
-
-
-%occluder selection, occluder LOD, virtual occluders,
-
-\subsubsection{Scene description}
-
- The scene is typically represented by a collection of objects. For
-purposes of visibility computations it can be advantageous to transform
-the object centered representation to a spatial representation by
-means of a spatial data structure.  For example the scene can be
-represented by an octree where full voxels correspond to opaque parts
-of the scene. Such a data structure is then used as an input to the
-visibility algorithm. The spatial data structures for the scene
-description are used for the following reasons:
-
-\begin{itemize}
-
-\item {\em Regularity}. A spatial data structure typically provides a
-  regular description of the scene that avoids complicated
-  configurations or overly detailed input. Furthermore, the
-  representation can be rather independent of the total scene
-  complexity.
-  
-\item {\em Efficiency}. The algorithm can be more efficient in both
-  the running time and the accuracy of the result.
-
-\end{itemize}
-
-
-Additionally, spatial data structures can be applied to structure the
-solution space and/or to represent the desired solution. Another
-application of spatial data structures is the acceleration of the
-algorithm by providing spatial indexing. These applications of spatial
-data structures will be discussed in
-Sections~\ref{sec:solution_space_ds}
-and~\ref{sec:acceleration_ds}. Note that a visibility algorithm can
-use a single data structure for all three purposes (scene
-structuring, solution space structuring, and spatial indexing) while
-another visibility algorithm can use three conceptually different data
-structures.
-
-
-% gernots alg.
-%used as solution space DS and/or acceleration DS
-
-\subsection{Solution space data structures}
-\label{sec:solution_space_ds}
-
-A solution space data structure is used to maintain an intermediate
-result during the operation of the algorithm and it is used to
-generate the result of the algorithm. We distinguish between the
-following solution space data structures:
-
-\begin{itemize}
-
-\item general data structures
-
-  single value (ray shooting), winged edge, active edge table, etc.
-  
-\item primal space (spatial) data structures
-  
-  uniform grid, BSP tree (shadow volumes),
-  bounding volume hierarchy, kD-tree, octree, etc.
-  
-\item image space data structures
-
-  2D uniform grid (shadow map), 2D BSP tree, quadtree, kD-tree, etc.
-
-\item line space data structures
-
-  regular grid, kD-tree, BSP tree, etc.
-  
-\end{itemize}
-
- The image space data structures can be considered a special case of
-the line space data structures since a point in the image represents a
-ray through that point (see also Section~\ref{sec:solspace}).
-
- If the dimension of the solution space matches the dimension of the
-problem-relevant line set, the visibility problem can often be solved
-with high accuracy by a single sweep through the scene. If the
-dimensions do not match, the algorithm typically needs more passes to
-compute a result with satisfying accuracy~\cite{EVL-2000-60,wonka00}
-or neglects some visibility effects altogether~\cite{EVL-2000-59}.
-
-
-%ray shooting none
-%visible surface algorithms - list of scan-line intersections, BSP tree,
-% z-buffer (graphics hardware)
-%shadow computation shadow volumes, BSP tree, shadow map (graphics hardware)
-%PVS for view cell - occlusion tree
-
-
-\subsection{Performance}
-\label{sec:performance}
-
-%output sensitivity, memory consumption, running time, scalability
-
-
-The performance of a visibility algorithm can be evaluated by measuring
-the quality of the result, the running time and the memory consumption.
-In this section we discuss several concepts related to these
-performance criteria.
-
-
-\subsubsection{Quality of the result}
-
- One of the important performance measures of a visibility algorithm
-is the quality of the result. The quality measure depends on the type
-of the answer to the problem. Generally, the quality of the result
-can be expressed as a distance from an exact result in the solution
-space.  Such a quality measure can be seen as a more precise
-expression of the accuracy of the algorithm discussed in
-Section~\ref{sec:accuracy}.
-
-For example a quality measure of algorithms computing a PVS can be
-expressed by the {\em relative overestimation} and the {\em relative
-underestimation} of the PVS with respect to the exact PVS.  We can
-define a quality measure of an algorithm $A$ on input $I$ as a tuple
-$\mbi{Q}^A(I)$:
-
-\begin{eqnarray}
-  \mbi{Q}^A(I) & = & (Q^A_o(I), Q^A_u(I)), \qquad  I \in {\cal D} \\
-  Q^A_o(I) & = & {|S^A(I) \setminus S^{\cal E}(I)| \over |S^{\cal E}(I)|} \\
-  Q^A_u(I) & = & {|S^{\cal E}(I) \setminus S^A(I) | \over |S^{\cal E}(I)|}
-\end{eqnarray}
-
-where $I$ is an input from the input domain ${\cal D}$, $S^A(I)$ is
-the PVS determined by the algorithm $A$ for input $I$ and $S^{\cal
-E}(I)$ is the exact PVS for the given input. $Q^A_o(I)$ expresses the
-{\em relative overestimation} of the PVS, $Q^A_u(I)$ is the {\em
-relative underestimation}.
-
-The expected quality of the algorithm over all possible inputs can be
-given as:
-
-\begin{eqnarray}
-Q^A & = & E[\| \mbi{Q}^A(I) \|] \\
-    & = & \sum_{\forall I \in {\cal D}} f(I).\sqrt{Q^A_o(I)^2 + Q^A_o(I)^2}
-\end{eqnarray}
-
-where f(I) is the probability density function expressing the
-probability of occurrence of input $I$. The quality measure
-$\mbi{Q}^A(I)$ can be used to classify a PVS algorithm into one of the
-four accuracy classes according to Section~\ref{sec:accuracy}:
-
-\begin{enumerate}
-\item exact\\
-  $\forall I \in {\cal D} :Q_o^A(I) = 0 \wedge Q_u^A(I) = 0$
-\item conservative\\
-  $\forall I \in {\cal D} : Q_o^A(I) \geq 0 \wedge Q_u^A(I) = 0$
-\item aggressive \\
-  $\forall I \in {\cal D} : Q_o^A(I) = 0 \wedge Q_u^A(I) \geq 0$
-\item approximate \\
-  $\qquad \exists I_j, I_k \in {\cal D}: Q_o^A(I_j) > 0 \wedge Q_u^A(I_k) > 0$
-\end{enumerate}
-
-
-
-\subsubsection{Scalability}
-
- Scalability expresses the ability of the visibility algorithm to cope
-with larger inputs. A more precise definition of scalability of an
-algorithm depends on the problem for which the algorithm is
-designed. The scalability of an algorithm can be studied with respect
-to the size of the scene (e.g. number of scene objects). Another
-measure might consider the dependence of the algorithm on the number
-of only the visible objects. Scalability can also be studied
-according to the given domain restrictions, e.g. volume of the view
-cell.
-
- A well designed visibility algorithm should be scalable with respect
-to the number of structural changes or discontinuities of
-visibility. Furthermore, its performance should be given by the
-complexity of the visible part of the scene. These two important
-measures of scalability of an algorithm are discussed in the next two
-sections.
-
-\subsubsection{Use of coherence}
-
- Scenes in computer graphics typically consist of objects whose
-properties vary smoothly from one part to another. A view of such a
-scene contains regions of smooth changes (changes in color, depth,
-texture,etc.) and discontinuities that let us distinguish between
-objects. The degree to which the scene or its projection exhibit local
-similarities is called {\em coherence}~\cite{Foley90}.
-
- Coherence can be exploited by reusing calculations made for one part
-of the scene for nearby parts. Algorithms exploiting coherence are
-typically more efficient than algorithms computing the result from the
-scratch.
-
- Sutherland et al.~\cite{Sutherland:1974:CTH} identified several
-different types of coherence in the context of visible surface
-algorithms. We simplify the classification proposed by Sutherland et
-al. to reflect general visibility problems and distinguish between the
-following three types of {\em visibility coherence}:
-
-\begin{itemize}
-
-\item {\em Spatial coherence}. Visibility of points in space tends to
-  be coherent in the sense that the visible part of the scene consists
-  of compact sets (regions) of visible and invisible points. We can
-  reuse calculations made for a given region for the neighboring
-  regions or its subregions.
-
-\item {\em Line-space coherence}. Sets of similar rays tend to have the
-  same visibility classification, i.e. the rays intersect the same
-  object. We can reuse calculations for the given set of rays for its
-  subsets or the sets of nearby rays.
-
-\item {\em Temporal coherence}. Visibility at two successive moments is
-  likely to be similar despite small changes in the scene or a
-  region/point of interest. Calculations made for one frame can be
-  reused for the next frame in a sequence.
-
-\end{itemize}
- 
- The degree to which the algorithm exploits various types of coherence
-is one of the major design paradigms in research of new visibility
-algorithms. The importance of exploiting coherence is emphasized by
-the large amount of data that need to be processed by the current
-rendering algorithms.
-
-
-\subsubsection{Output sensitivity}
-
-
-An algorithm is said to be {\em output-sensitive} if its running time
-is sensitive to the size of output. In the computer graphics community
-the term output-sensitive algorithm is used in a broader meaning than
-in computational geometry~\cite{berg:97}. The attention is paid to a
-practical usage of the algorithm, i.e. to an efficient implementation
-in terms of the practical average case performance. The algorithms are
-usually evaluated experimentally using test data and measuring the
-running time and the size of output of the algorithm. The formal
-average case analysis is usually not carried out for the following two
-reasons:
-
-\begin{enumerate}
-
-\item {\em The algorithm is too obscured}. Visibility algorithms
-exploit data structures that are built according to various heuristics
-and it is difficult to derive proper bounds even on the expected size
-of these supporting data structures.
-
-\item {\em It is difficult to properly model the input data}. In
-general it is difficult to create a reasonable model that captures
-properties of real world scenes as well as the probability of
-occurrence of a particular configuration.
-
-\end{enumerate}
-
- A visibility algorithm can often be divided into the {\em offline}
-phase and the {\em online} phase. The offline phase is also called
-preprocessing. The preprocessing is often amortized over many
-executions of the algorithm and therefore it is advantageous to
-express it separately from the online running time.
-
- For example an ideal output-sensitive visible surface algorithm runs
-in $O(n\log n + k^2)$, where $n$ is the number of scene polygons (size
-of input) and $k$ is the number of visible polygons (in the worst case
-$k$ visible polygons induce $O(k^2)$ visible polygon fragments).
-
-
-
-\subsubsection{Acceleration data structures}
-\label{sec:acceleration_ds}
-
- Acceleration data structures are often used to achieve the performance
-goals of a visibility algorithm. These data structures allow efficient
-point location, proximity queries, or scene traversal required by many
-visibility algorithms.
-
- With a few exceptions the acceleration data structures provide a {\em
-spatial index} for the scene by means of a spatial data structure.
-The spatial data structures group scene objects according to the
-spatial proximity. On the contrary line space data structures group
-rays according to their proximity in line space.
-
-The common acceleration data structures can be divided into the
-following  categories:
-
-\begin{itemize}
-\item Spatial data structures
-  \begin{itemize}
-  \item {\em Spatial subdivisions}
-
-    uniform grid, hierarchical grid, kD-tree, BSP tree, octree, quadtree, etc.
-    
-  \item {\em Bounding volume hierarchies}
-
-    hierarchy of bounding spheres,
-    hierarchy of bounding boxes, etc.
-    
-  \item {\em Hybrid}
-
-    hierarchy of uniform grids, hierarchy of kD-trees, etc.
-
-  \end{itemize}
-  
-\item Line space data structures
-  \begin{itemize}
-  \item {\em General}
-
-    regular grid, kD-tree, BSP tree, etc.
-  \end{itemize}
-  
-\end{itemize}
-
-
-
-\subsubsection{Use of graphics hardware}
-
- Visibility algorithms can be accelerated by exploiting dedicated
-graphics hardware. The hardware implementation of the z-buffer
-algorithm that is common even on a low-end graphics hardware can be
-used to accelerate solutions to other visibility problems. Recall that the
-z-buffer algorithm solves the visibility from a point problem by
-providing a discrete approximation of the visible surfaces.
-%$(3-D-2b(i), A-3b)$ 
-
-A visibility algorithm can be accelerated by the graphics hardware if
-it can be decomposed so that the decomposition includes the
-problem solved by the z-buffer or a series of such problems.
-%$(3-D-2b(i), A-3b)$
-Prospectively, the recent features of the graphics hardware, such as
-the pixel and vertex shaders  allow easier application of the graphics
-hardware for solving specific visibility tasks. The software interface
-between the graphics hardware and the CPU is usually provided by
-OpenGL~\cite{Moller02-RTR}.
-
-
-\section{Visibility in urban environments}
-
- Urban environments constitute an important class of real world scenes
-computer graphics deals with. We can identify two fundamental
-subclasses of urban scenes. Firstly, we consider {\em outdoor} scenes,
-i.e. urban scenes as observed from streets, parks, rivers, or a
-bird's-eye view. Secondly, we consider {\em indoor} scenes, i.e. urban
-scenes representing building interiors. In the following two sections
-we discuss the essential characteristics of visibility in both the
-outdoor and the indoor scenes. The discussion is followed by
-summarizing the suitable visibility techniques.
-
-
-\subsection{Analysis of visibility in outdoor urban areas}
-
-\label{sec:analysis_ue}
-\label{sec:ANALYSIS_UE}
-
-
-Outdoor urban scenes are viewed using two different scenarios. In a
-{\em flyover} scenario the scene is observed from the bird's eye
-view. A large part of the scene is visible. Visibility is  mainly
-restricted due to the structure of the terrain, atmospheric
-constraints (fog, clouds) and the finite resolution of human
-retina. Rendering of the flyover scenarios is usually accelerated
-using LOD, image-based rendering and terrain visibility algorithms,
-but there is no significant potential for visibility culling.
-
-In a {\em walkthrough} scenario the scene is observed from a
-pedestrians point of view and the visibility is often very
-restricted. In the remainder of this section we discuss the walkthrough
-scenario in more detail.
-
-Due to technological and physical restrictions urban scenes viewed
-from outdoor closely resemble a 2D {\em height function}, i.e. a
-function expressing the height of the scene elements above the ground.
-The height function cannot capture certain objects such as bridges,
-passages, subways, or detailed objects such as trees.  Nevertheless
-buildings, usually the most important part of the scene, can be
-captured accurately by the height function in most cases.  For the
-sake of visibility computations the objects that cannot be represented
-by the height function can be ignored. The resulting scene is then
-called a {\em \m25d scene}.
-
- In a dense urban area with high buildings visibility is very
-restricted when the scene is viewed from a street (see
-Figure~\ref{fig:outdoor}-a). Only buildings from nearby streets are
-visible. Often there are no buildings visible above roofs of buildings
-close to the viewpoint. In such a case visibility is essentially
-two-dimensional, i.e. it could be solved accurately using a 2D
-footprint of the scene and a 2D visibility algorithm. In areas with
-smaller houses of different shapes visibility is not so severely
-restricted since some objects can be visible by looking over other
-objects. The view complexity increases (measured in number of visible
-objects) and the height structure becomes increasingly
-important. Complex views with far visibility can be seen also near
-rivers, squares, and parks (see Figure~\ref{fig:outdoor}-b).
-
-\begin{figure}[htb]
-  \centerline{
-    \hfill
-    \includegraphics[width=0.45\textwidth,draft=\DRAFTIMAGES]{images/foto_street1}
-    \hfill
-    \includegraphics[width=0.45\textwidth,draft=\DRAFTIMAGES]{images/foto_castle1}
-    \hfill
-  }
-  \caption{Visibility in outdoor urban areas. (left) In the center of a city
-  visibility is typically restricted to a few nearby streets. (right)
-  Near river banks typically a large part of the city is visible. Note
-  that many distant objects are visible due to the terrain gradation.}
-  \label{fig:outdoor}
-\end{figure}
-
- In scenes with large differences in terrain height the view complexity
-is often very high. Many objects can be visible that are situated for
-example on a hill or on a slope behind a river. Especially in areas
-with smaller housing visibility is much defined by the terrain itself.
-
-We can summarize the observations as follows (based on
-Wonka~\cite{wonka_phd}) :
-
-\begin{itemize}
-  
-\item
-  Outdoor urban environments have basically \m25d structure and
-  consequently visibility is restricted accordingly.
-  
-\item
-  The view is very restricted in certain areas, such as in the
-  city center. However the complexity of the view can vary
-  significantly.  It is always not the case that only few objects are
-  visible.
-  
-\item
-  If there are large height differences in the terrain, many
-  objects are visible for most viewpoints.
-  
-\item
-  In the same view a close object can be visible next to a very
-  distant one.
-
-\end{itemize}
-
-
- In the simplest case the outdoor scene consists only of the terrain
-populated by a few buildings. Then the visibility can be calculated on
-the terrain itself with satisfying
-accuracy~\cite{Floriani:1995:HCH,Cohen-Or:1995:VDZ, Stewart:1997:HVT}.
-Outdoor urban environments have a similar structure as terrains:
-buildings can be treated as a terrain with {\em many discontinuities}
-in the height function (assuming that the buildings do not contain
-holes or significant variations in their fa{\c{c}}ades). To
-accurately capture visibility in such an environment specialized
-algorithms have been developed that compute visibility from a given
-viewpoint~\cite{downs:2001:I3DG} or view
-cell~\cite{wonka00,koltun01,bittner:2001:PG}.
-
-%  The methods presented later in the thesis make use of the specific
-% structure of the outdoor scenes to efficiently compute a PVS for the
-% given view cell.  The key observation is that the PVS for a view cell
-% in a \m25d can be determined by computing visibility from its top
-% boundary edges. This problem becomes a restricted variant of the
-% visibility from a line segment in 3D with $d({\cal L}_R) = 3$.
-
-
-\subsection{Analysis of indoor visibility}
-
-Building interiors constitute another important class of real world
-scenes.  A typical building consists of rooms, halls, corridors, and
-stairways. It is possible to see from one room to another through an
-open door or window. Similarly it is possible to see from one corridor
-to another one through a door or other connecting structure.  In
-general the scene can be subdivided into cells corresponding to the
-rooms, halls, corridors, etc., and transparent portals that connect
-the cells~\cite{Airey90,Teller:1991:VPI}. Some portals
-correspond to the real doors and windows, others provide only a
-virtual connection between cells. For example an L-shaped corridor
-can be represented by two cells and one virtual portal connecting them.
-
-Visibility in a building interior is often significantly restricted
-(see Figure~\ref{fig:indoor}).  We can see the room we are located at
-and possibly few other rooms visible through open doors. Due to the
-natural partition of the scene into cells and portals visibility can
-be solved by determining which cells can be seen through a give set of
-portals and their sequences. A sequence of portals that we can see
-through is called {\em feasible}.
-
-\begin{figure}[htb]
-  \centerline{
-    \hfill
-    \includegraphics[width=0.45\textwidth,draft=\DRAFTIMAGES]{images/foto_chodba1}
-    \hfill
-    \includegraphics[width=0.45\textwidth,draft=\DRAFTIMAGES]{images/foto_sloupy2}
-    \hfill
-  } 
-  \caption{Indoor visibility. (left) Visibility in indoor scenes is typically
-    restricted to a few rooms or corridors. (right) In scenes with more complex
-    interior structure visibility gets more complicated.
-  }
-  \label{fig:indoor}
-\end{figure}
-
-
- Many algorithms for computing indoor visibility~\cite{Airey90,
-Teller92phd, Luebke:1995:PMS} exploit the cell/portal structure of the
-scene. The potential problem of this approach is its strong
-sensitivity to the arrangement of the environment. In a scene with a
-complicated structure with many portals there are many feasible portal
-sequences.  Imagine a hall with columns arranged on a grid. The number
-of feasible portal sequences rapidly increases with the distance from
-the given view cell~\cite{Teller92phd} if the columns are sufficiently
-small (see Figure~\ref{fig:portal_explosion}).  Paradoxically most of
-the scene is visible and there is almost no benefit of using any
-visibility culling algorithm.
-
- The methods presented later in the report partially avoids this
-problem since it does not rely on finding feasible portal sequences
-even in the indoor scenes. Instead of determining what {\em can} be
-visible through a transparent complement of the scene (portals) the
-method determines what {\em cannot} be visible due to the scene
-objects themselves (occluders). This approach also avoids the explicit
-enumeration of portals and the construction of the cell/portal graph.
-
-
-
-\begin{figure}[htb]     
-  \centerline{
-    \includegraphics[width=0.45\textwidth,draft=\DRAFTFIGS]{figs/portals_explosion}}
-    \caption{In sparsely occluded scenes the cell/portal algorithm can
-    exhibit a combinatorial explosion in number of feasible portal
-    sequences. Paradoxically visibility culling provides almost no
-    benefit in such scenes.}
-    \label{fig:portal_explosion}
-\end{figure}
-
 
 
 \section{Summary}
 
- Visibility problems and algorithms penetrate a large part of computer
-graphics research. The proposed taxonomy aims to classify visibility
-problems independently of their target application. The
-classification should help to understand the nature of the given
-problem and it should assist in finding relationships between
-visibility problems and algorithms in different application areas.
-The tools address the following classes of visibility problems:
+The presented taxonomy classifies visibility problems independently of
+their target application. The classification should help to understand
+the nature of the given problem and it should assist in finding
+relationships between visibility problems and algorithms in different
+application areas.  The tools address the following classes of
+visibility problems:
 
 \begin{itemize}
@@ -1242,6 +647,7 @@
 \item Domain:
   \begin{itemize}
-  \item viewpoint (Chapter~\ref{chap:online}),
-  \item polygon or polyhedron (Chapters~\ref{chap:sampling,chap:mutual})
+  \item viewpoint (online culling tool),
+  \item global visibility (global visibility sampling tool)
+  \item polygon or polyhedron (mutual visibility tool)
   \end{itemize}
 \item Scene restrictions (occluders):
@@ -1251,9 +657,8 @@
 \item Scene restrictions (group objects):
   \begin{itemize}
-  \item bounding boxes (Chapters~\ref{chap:rtviscull},~\ref{chap:vismap},~Chapter~\ref{chap:rot25d} and~\ref{chap:rot3d}),
+  \item bounding boxes
   \end{itemize}
 \item Output:
   \begin{itemize}
-  \item Visibility classification of objects or hierarchy nodes
   \item PVS
   \end{itemize}
@@ -1264,19 +669,18 @@
   \item aggresive
   \end{itemize}
-  \item Solution space:
+\item Solution space:
   \begin{itemize}
-  \item discrete (Chapters~\ref{chap:online},~\ref{chap:sampling})
-  \item continuous, line space / primal space (Chapter~\ref{chap:rot25d})
+  \item discrete (online culling tool, global visibility sampling tool, conservative and approximate algorithm from the mutual visibility tool)
+  \item continuous (exact algorithm from mutual visibility tool)
   \end{itemize}
-  \item Solution space data structures: viewport (Chapter~\ref{chap:online}), ray stack (Chapter~\ref{chap:sampling}), ray stack or BSP tree (Chapter~\ref{chap:mutual})
+  \item Solution space data structures: viewport (online culling tool), ray stack (global visibility sampling tool, conservative and approximate algorithm from the mutual visibility tool), BSP tree (exact algorithm from the mutual visibility tool)
   \item Use of coherence of visibility:
     \begin{itemize}
-    \item spatial coherence (all methods)
-    \item temporal coherence (Chapter~\ref{chap:online})
+    \item spatial coherence (all tools)
+    \item temporal coherence (online culling tool)
     \end{itemize}
-  \item Output sensitivity: expected in practice (all methods)
-  \item Acceleration data structure: kD-tree (all methods)
-  \item Use of graphics hardware: Chapter~\ref{chap:online}
-    
+  \item Output sensitivity: expected in practice (all tools)
+  \item Acceleration data structure: kD-tree (all tools)
+  \item Use of graphics hardware: online culling tool
   \end{itemize}
 
Index: trunk/VUT/doc/SciReport/analysis.tex
===================================================================
--- trunk/VUT/doc/SciReport/analysis.tex	(revision 255)
+++ trunk/VUT/doc/SciReport/analysis.tex	(revision 266)
@@ -1,8 +1,15 @@
 \chapter{Analysis of Visibility in Polygonal Scenes}
 
-
-
-
-\section{Analysis of 2D line space}
+This chapter provides analysis of the visibility in polygonal scenes,
+which are the input for all developed tools. The visibility analysis
+uncoveres the complexity of the from-region and global visibility
+problems and thus it especially important for a good design of the
+global visibility preprocessor. To better undestand the visibility
+relationships in primal space we use mapping to line space, where the
+visibility interactions can be observed easily by interactions of sets
+of points. Additionally for the sake of clarity, we first analyze
+visibility in 2D and then extend the analysis to 3D polygonal scenes.
+
+\section{Analysis of visibility in 2D}
 
 \label{LINE_SPACE}
@@ -1017,2 +1024,10 @@
 to handle numerical inaccuracies.
 
+
+\section{Summary}
+
+ In this chapter we discussed the relation of sets of lines in 3D and
+the polyhedra in \plucker coordinates. We proposed a general size
+measure for a set of lines described by a blocker polyhedron and a
+size measure designed for the computation of PVS.
+
Index: trunk/VUT/doc/SciReport/online.tex
===================================================================
--- trunk/VUT/doc/SciReport/online.tex	(revision 253)
+++ trunk/VUT/doc/SciReport/online.tex	(revision 266)
@@ -44,23 +44,23 @@
 \begin{figure}%[htb]
   %\centerline
-	\centering \footnotesize
-	\begin{tabular}{c}
- 	\includegraphics[width=0.6\textwidth, draft=\DRAFTFIGS]{images/ogre_terrain} \\
- 	%\hline 
- 	\includegraphics[width=0.3\textwidth, draft=\DRAFTFIGS]{images/vis_viewfrustum} \hfill \includegraphics[width=0.3\textwidth, draft=\DRAFTFIGS]{images/vis_chc} \\
- 	\end{tabular}
+  \centering \footnotesize
+  \begin{tabular}{c}
+  \includegraphics[width=0.6\textwidth, draft=\DRAFTFIGS]{images/ogre_terrain} \\
+  %\hline 
+  \includegraphics[width=0.3\textwidth, draft=\DRAFTFIGS]{images/vis_viewfrustum} \hfill \includegraphics[width=0.3\textwidth, draft=\DRAFTFIGS]{images/vis_chc} \\
+  \end{tabular}
 %\label{tab:online_culling_example}
   \caption{(top) The rendered terrain scene. (bottom) Visualizion of the rendered / culled objects.
     Using view frustum culling (left image) vs. occlusion queries (right image).
     The yellow boxes show the actually rendered scene objects. The
-  	red boxes depict the view frustum culled hierarchy nodes, the blue boxes depict the
-  	occlusion query culled hierarchy nodes.}
+    red boxes depict the view frustum culled hierarchy nodes, the blue boxes depict the
+    occlusion query culled hierarchy nodes.}
   \label{fig:online_culling_example}
 \end{figure}
 
 Recent graphics hardware natively supports an \emph{occlusion query}
-to detect the visibility of an object against the current contents of the
-z-buffer.  Although the query itself is processed quickly using the
-raw power of the graphics processing unit (GPU), its result is not
+to detect the visibility of an object against the current contents of
+the z-buffer.  Although the query itself is processed quickly using
+the raw power of the graphics processing unit (GPU), its result is not
 available immediately due to the delay between issuing the query and
 its actual processing in the graphics pipeline. As a result, a naive
@@ -74,8 +74,10 @@
 simplicity and versatility: the method can be easily integrated in
 existing real-time rendering packages on architectures supporting the
-underlying occlusion query.
-In figure~\ref{fig:online_culling_example}, the same scene (top row) is rendered using view frustum
-culling (visualization in the bottom left image) versus online culling using occlusion queries (visualization 
-in the bottom right image). It can be seen that with view frustum culling only many objects are still rendered.
+underlying occlusion query.  In
+figure~\ref{fig:online_culling_example}, the same scene (top row) is
+rendered using view frustum culling (visualization in the bottom left
+image) versus online culling using occlusion queries (visualization
+in the bottom right image). It can be seen that with view frustum
+culling only many objects are still rendered.
 %Using spatial and assuming temporal coherence
 
@@ -105,9 +107,9 @@
 z-buffer allows to quickly determine if the geometry in question is
 occluded. To a certain extent this idea is used in the current
-generation of graphics hardware by applying early z-tests of
-fragments in the graphics pipeline (e.g., Hyper-Z technology of ATI or
-Z-cull of NVIDIA). However, the geometry still needs to be sent to the
-GPU, transformed, and coarsely rasterized even if it is later
-determined invisible.
+generation of graphics hardware by applying early z-tests of fragments
+in the graphics pipeline (e.g., Hyper-Z technology of ATI or Z-cull of
+NVIDIA). However, the geometry still needs to be sent to the GPU,
+transformed, and coarsely rasterized even if it is later determined
+invisible.
 
  Zhang~\cite{EVL-1997-163} proposed hierarchical occlusion maps, which
@@ -774,8 +776,8 @@
 %shown in the accompanying video.
 
-The complete power plant model is quite challenging even to load into memory,
-but on the other hand it offers good
-occlusion. This scene is an interesting candidate for testing not only
-due to its size, but also due to significant changes in visibility and depth complexity in
+The complete power plant model is quite challenging even to load into
+memory, but on the other hand it offers good occlusion. This scene is
+an interesting candidate for testing not only due to its size, but
+also due to significant changes in visibility and depth complexity in
 its different parts.
 
@@ -915,6 +917,6 @@
 \caption{Statistics for the three test scenes. VFC is rendering with only view-frustum culling, S\&W is the
   hierarchical stop and wait method, CHC is our new method, and Ideal
-is a perfect method with respect to the given hierarchy. All values are averages over
-all frames (including the speedup).}
+is a perfect method with respect to the given hierarchy. All values
+are averages over all frames (including the speedup).}
 \label{tab:averages}
 \end{table*}
Index: trunk/VUT/doc/SciReport/figs/portals_explosion.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/portals_explosion.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/portals_explosion.fig	(revision 266)
@@ -0,0 +1,59 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 34 #ff8c0a
+0 35 #ff9c0a
+0 36 #ffb10a
+0 37 #ffc10a
+0 38 #ffd10a
+2 2 0 6 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 2400 2100 9300 2100 9300 7500 2400 7500 2400 2100
+2 1 0 6 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 3900 5175 3900 5775
+2 1 0 6 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 3900 6900 3900 7500
+2 1 0 6 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 3900 2100 3900 2700
+2 1 0 6 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 3900 3675 3900 4275
+2 1 0 6 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 6600 2925 6600 3525
+2 1 0 6 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 6600 6000 6600 6600
+2 1 0 2 35 7 60 0 -1 0.000 0 0 -1 0 0 2
+	 3900 2100 3900 7500
+2 1 0 2 35 7 60 0 -1 0.000 0 0 -1 0 0 2
+	 6600 2100 6600 7500
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 3150 3225 7500 2325
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 3225 2925 8325 4950
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 3225 2625 7050 7350
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 3000 4950 6900 2325
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 2850 4725 7350 4725
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 3075 4275 7350 7350
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 3075 6825 7050 2250
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 3000 6450 7725 4125
+2 1 0 2 35 7 40 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 3000 6150 7875 7050
Index: trunk/VUT/doc/SciReport/figs/vfp.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/vfp.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/vfp.fig	(revision 266)
@@ -0,0 +1,53 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 35 #ff7a0a
+0 36 #ffb10a
+0 37 #ffc10a
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 2700 4200 121 121 2700 4200 2821 4200
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 7500 2250 75 75 7500 2250 7575 2250
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 5700 3450 75 75 5700 3450 5775 3450
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 6600 5400 75 75 6600 5400 6675 5400
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 6000 4575 75 75 6000 4575 6075 4575
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 6900 3900 75 75 6900 3900 6975 3900
+2 1 0 1 0 7 50 0 -1 0.000 0 0 -1 1 1 3
+	1 1 1.00 60.00 120.00
+	1 1 1.00 60.00 120.00
+	 4500 5400 4500 6300 5175 6750
+2 1 0 1 35 7 60 0 -1 0.000 0 0 -1 0 0 3
+	 5100 3525 5700 3450 5700 6300
+2 1 0 2 0 7 67 0 -1 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 2685 4185 11850 510
+2 1 0 2 0 7 67 0 -1 0.000 0 0 7 1 0 2
+	1 1 2.00 120.00 240.00
+	 2700 4200 9855 2445
+2 1 0 2 0 7 67 0 -1 0.000 0 0 7 1 0 2
+	1 1 2.00 120.00 240.00
+	 2775 4200 11355 3570
+2 1 0 2 0 7 67 0 -1 0.000 0 0 7 1 0 2
+	1 1 2.00 120.00 240.00
+	 2700 4200 9840 4980
+2 1 0 2 0 7 67 0 -1 0.000 0 0 7 1 0 2
+	1 1 2.00 120.00 240.00
+	 2700 4200 10785 6690
+2 1 0 1 35 7 60 0 -1 0.000 0 0 7 0 0 3
+	 5085 4455 6000 4575 6000 6525
+2 1 0 1 35 7 60 0 -1 0.000 0 0 7 0 0 3
+	 5100 5025 6600 5400 6600 6750
+2 1 0 1 35 7 60 0 -1 0.000 0 0 7 0 0 3
+	 5100 3975 6900 3900 6900 6975
+2 1 0 1 35 7 60 0 -1 0.000 0 0 7 0 0 3
+	 5100 3000 7500 2250 7500 7275
+2 3 0 3 0 7 60 0 -1 0.000 0 0 7 0 0 5
+	 5100 2400 8100 900 8100 7575 5100 6000 5100 2400
+4 0 0 50 0 0 24 0.0000 4 330 1260 5400 1425 viewport\001
+4 0 0 50 0 0 24 0.0000 4 180 195 4800 6900 x\001
+4 0 0 50 0 0 24 0.0000 4 255 165 4275 5850 y\001
+4 0 0 50 0 0 24 0.0000 4 330 1425 1875 3675 viewpoint\001
Index: trunk/VUT/doc/SciReport/figs/vfr.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/vfr.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/vfr.fig	(revision 266)
@@ -0,0 +1,40 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 34 #ff8c0a
+0 35 #ff9c0a
+0 36 #ffb10a
+0 37 #ffc10a
+0 38 #ffd10a
+2 1 0 8 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 2925 3675 3900 4350
+2 2 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 7200 900 12000 900 12000 5400 7200 5400 7200 900
+2 1 0 8 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 1802 2916 3002 3141
+2 3 1 4 0 27 30 0 -1 6.000 0 0 -1 0 0 5
+	 8156 1881 10856 1431 10631 4206 8981 4581 8156 1881
+2 1 0 2 0 7 85 0 14 0.000 0 0 7 0 0 4
+	 7200 1050 12000 1350 12000 2700 7200 2475
+2 3 0 0 0 36 90 0 20 0.000 0 0 -1 0 0 5
+	 8175 1875 10875 1425 10650 4200 9000 4575 8175 1875
+2 1 0 2 0 7 85 0 14 0.000 0 0 7 0 0 4
+	 7125 3600 12000 3150 12000 4725 7200 4725
+2 2 0 4 0 34 50 0 20 0.000 0 0 7 0 0 5
+	 1500 4200 2400 4200 2400 5100 1500 5100 1500 4200
+2 2 0 4 0 34 50 0 20 0.000 0 0 7 0 0 5
+	 4200 1200 5100 1200 5100 2100 4200 2100 4200 1200
+2 1 0 2 0 36 85 0 20 0.000 0 0 -1 0 0 6
+	 1500 5100 1500 4200 4200 1200 5100 1200 5100 2100 2400 5100
+4 0 0 85 0 0 24 0.0000 4 330 1860 2400 600 primal space\001
+4 0 0 85 0 0 24 0.0000 4 330 1455 8625 600 line space\001
+4 0 0 10 0 0 24 0.0000 4 255 420 7575 4275 B*\001
+4 0 0 85 0 0 24 0.0000 4 255 240 4275 4425 B\001
+4 0 0 85 0 0 24 0.0000 4 255 255 2175 2700 A\001
+4 0 0 10 0 0 24 0.0000 4 255 435 7500 1950 A*\001
Index: trunk/VUT/doc/SciReport/figs/ot1.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/ot1.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/ot1.fig	(revision 266)
@@ -0,0 +1,182 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 34 #ff8c0a
+0 35 #ff9c0a
+0 36 #ffb10a
+0 37 #ffc10a
+0 38 #ffd10a
+6 9225 2925 10425 3225
+4 0 0 50 0 0 24 0.0000 4 30 135 9231 3179 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 10205 3179 +\001
+-6
+6 10875 1650 12150 1875
+4 0 0 50 0 0 24 0.0000 4 30 135 10896 1874 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 11870 1874 +\001
+-6
+6 7725 4875 9000 5175
+4 0 0 50 0 0 24 0.0000 4 30 135 7796 5136 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 8770 5136 +\001
+-6
+6 10050 3975 11325 4200
+4 0 0 50 0 0 24 0.0000 4 30 135 10121 4176 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 11095 4176 +\001
+-6
+6 11775 3900 13050 4200
+4 0 0 50 0 0 24 0.0000 4 30 135 11846 4146 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 12820 4146 +\001
+-6
+6 12525 5625 13800 5850
+4 0 0 50 0 0 24 0.0000 4 30 135 12566 5826 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 13540 5826 +\001
+-6
+6 12675 3000 13950 3225
+4 0 0 50 0 0 24 0.0000 4 30 135 12696 3239 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 13670 3239 +\001
+-6
+6 13650 3900 14925 4125
+4 0 0 50 0 0 24 0.0000 4 30 135 13716 4139 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 14690 4139 +\001
+-6
+6 13125 4725 14400 5025
+4 0 0 50 0 0 24 0.0000 4 30 135 13146 4994 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 14120 4994 +\001
+-6
+6 8475 3975 9750 4200
+4 0 0 50 0 0 24 0.0000 4 30 135 8496 4184 -\001
+4 0 0 50 0 0 24 0.0000 4 180 210 9470 4184 +\001
+-6
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 9794 2900 300 300 9794 2900 10094 3200
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 11459 1595 300 300 11459 1595 11759 1895
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 8366 4865 300 300 8366 4865 8666 5165
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 10691 3905 300 300 10691 3905 10991 4205
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 12416 3875 300 300 12416 3875 12716 4175
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 13136 5555 300 300 13136 5555 13436 5855
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 13259 2960 300 300 13259 2960 13559 3260
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 14279 3860 300 300 14279 3860 14579 4160
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 13709 4715 300 300 13709 4715 14009 5015
+1 3 0 3 -1 7 0 0 -1 0.000 1 0.0000 9059 3905 300 300 9059 3905 9359 4205
+2 1 0 2 0 7 45 0 -1 0.000 0 0 -1 0 0 2
+	 6225 5700 -975 1725
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 3000 3900 -1236 4448
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 75 4275 1314 7223
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 2964 3888 460 500
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 3954 3138 834 1008
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 2634 3393 5389 2873
+2 1 1 4 0 7 50 0 -1 4.000 0 0 -1 0 0 3
+	 2410 2120 1120 3650 3955 3155
+2 2 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 14226 5300 14526 5300 14526 5600 14226 5600 14226 5300
+2 2 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 14811 4445 15111 4445 15111 4745 14811 4745 14811 4445
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 9532 3103 9231 3470
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 10048 3101 10431 3515
+2 2 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 9441 4505 9741 4505 9741 4805 9441 4805 9441 4505
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 11197 1798 10086 2570
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 11713 1796 12996 2630
+2 3 0 5 0 36 50 0 22 0.000 0 0 -1 0 0 5
+	 75 4275 900 6225 4425 4725 3000 3900 75 4275
+2 3 0 5 0 36 55 0 24 0.000 0 0 -1 0 0 4
+	 2400 2100 1125 3675 3975 3150 2400 2100
+2 3 0 5 0 34 50 0 18 0.000 0 0 -1 0 0 4
+	 1575 2025 75 4275 3000 3900 1575 2025
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 8122 5078 7873 5383
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 8608 5071 8893 5391
+2 2 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 8721 5381 9021 5381 9021 5681 8721 5681 8721 5381
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 10447 4118 10198 4423
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 10933 4111 11218 4431
+2 2 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 11046 4421 11346 4421 11346 4721 11046 4721 11046 4421
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 12172 4088 11923 4393
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 12658 4081 12943 4401
+2 2 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 12771 4391 13071 4391 13071 4691 12771 4691 12771 4391
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 12892 5768 12643 6073
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 13378 5761 13663 6081
+2 2 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 13491 6071 13791 6071 13791 6371 13491 6371 13491 6071
+2 2 0 2 0 36 50 0 22 0.000 0 0 -1 0 0 5
+	 7716 5381 8016 5381 8016 5681 7716 5681 7716 5381
+2 2 0 2 0 34 50 0 18 0.000 0 0 -1 0 0 5
+	 10041 4421 10341 4421 10341 4721 10041 4721 10041 4421
+2 2 0 2 0 34 50 0 18 0.000 0 0 -1 0 0 5
+	 11766 4391 12066 4391 12066 4691 11766 4691 11766 4391
+2 2 0 2 0 36 50 0 24 0.000 0 0 -1 0 0 5
+	 12486 6071 12786 6071 12786 6371 12486 6371 12486 6071
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 12997 3163 12771 3470
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 13513 3161 13941 3566
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 14017 4063 13791 4370
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 14533 4061 14961 4466
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 13447 4918 13221 5225
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 13963 4916 14391 5321
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 8797 4108 8571 4415
+2 1 0 2 -1 7 0 0 -1 0.000 0 0 -1 0 0 2
+	 9313 4106 9636 4460
+4 0 0 50 0 0 24 0.0000 4 255 180 2529 6039 d\001
+4 0 0 50 0 0 24 0.0000 4 255 90 3234 2544 i\001
+4 0 0 50 0 0 24 0.0000 4 255 195 3414 3624 h\001
+4 0 0 50 0 0 26 0.0000 4 345 270 597 3846 P\001
+4 0 0 50 0 0 26 0.0000 4 345 270 2529 2946 P\001
+4 0 0 50 0 0 24 0.0000 4 255 345 747 4033 2a\001
+4 0 0 50 0 0 24 0.0000 4 255 345 2735 3115 3a\001
+4 0 0 50 0 0 24 0.0000 4 180 165 3789 4239 a\001
+4 0 0 50 0 0 24 0.0000 4 255 105 564 3219 f\001
+4 0 0 50 0 0 24 0.0000 4 255 180 9716 3069 b\001
+4 0 0 50 0 0 24 0.0000 4 255 180 8231 4989 d\001
+4 0 0 50 0 0 24 0.0000 4 255 105 10646 4059 f\001
+4 0 0 50 0 0 24 0.0000 4 180 165 11381 1734 a\001
+4 0 0 50 0 0 24 0.0000 4 180 165 13181 3084 e\001
+4 0 0 50 0 0 24 0.0000 4 255 105 12311 3999 f\001
+4 0 0 50 0 0 24 0.0000 4 255 195 14201 4014 h\001
+4 0 0 50 0 0 24 0.0000 4 255 90 13676 4869 i\001
+4 0 0 50 0 0 24 0.0000 4 330 90 13091 5709 j\001
+4 0 0 50 0 0 26 0.0000 4 345 270 7742 6113 P\001
+4 0 0 50 0 0 26 0.0000 4 345 270 10086 5176 P\001
+4 0 0 50 0 0 26 0.0000 4 345 270 11811 5138 P\001
+4 0 0 50 0 0 26 0.0000 4 345 270 12505 6807 P\001
+4 0 0 50 0 0 24 0.0000 4 255 180 7891 6320 1\001
+4 0 0 50 0 0 24 0.0000 4 255 345 10273 5345 2a\001
+4 0 0 50 0 0 24 0.0000 4 255 360 11979 5308 2b\001
+4 0 0 50 0 0 24 0.0000 4 255 345 12692 6958 3a\001
+4 0 0 50 0 0 24 0.0000 4 255 180 1824 3864 g\001
+4 0 0 50 0 0 24 0.0000 4 255 180 1854 4434 b\001
+4 0 0 50 0 0 24 0.0000 4 180 165 174 5439 c\001
+4 0 0 50 0 0 24 0.0000 4 180 165 1614 2004 e\001
+4 0 0 50 0 0 24 0.0000 4 330 90 2079 2289 j\001
+4 0 0 50 0 0 26 0.0000 4 345 270 1347 2841 P\001
+4 0 0 50 0 0 24 0.0000 4 255 360 1512 2998 2b\001
+4 0 0 50 0 0 26 0.0000 4 345 270 1742 5060 P\001
+4 0 0 50 0 0 24 0.0000 4 255 180 1880 5218 1\001
+4 0 0 50 0 0 24 0.0000 4 180 165 8981 4059 c\001
Index: trunk/VUT/doc/SciReport/figs/vls.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/vls.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/vls.fig	(revision 266)
@@ -0,0 +1,115 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 34 #ff8c0a
+0 35 #ff9c0a
+0 36 #ffb10a
+0 37 #ffc10a
+0 38 #ffd10a
+6 7800 3525 8250 3975
+4 0 0 50 0 0 24 0.0000 4 255 450 7800 3825 O*\001
+4 0 0 50 0 0 20 0.0000 4 195 135 8025 3975 0\001
+-6
+6 9075 4350 9675 4800
+6 9300 4575 9675 4800
+4 0 0 50 0 0 20 0.0000 4 195 330 9300 4800 0.5\001
+-6
+4 0 0 50 0 0 24 0.0000 4 255 450 9075 4650 O*\001
+-6
+6 4725 2475 5175 2925
+4 0 0 50 0 0 24 0.0000 4 255 450 4725 2775 O*\001
+4 0 0 50 0 0 20 0.0000 4 195 135 4950 2925 0\001
+-6
+6 4725 3600 5325 4050
+6 4950 3825 5325 4050
+4 0 0 50 0 0 20 0.0000 4 195 330 4950 4050 0.5\001
+-6
+4 0 0 50 0 0 24 0.0000 4 255 450 4725 3900 O*\001
+-6
+6 4650 4875 5100 5325
+4 0 0 50 0 0 24 0.0000 4 255 450 4650 5175 O*\001
+4 0 0 50 0 0 20 0.0000 4 195 135 4875 5325 1\001
+-6
+1 1 0 3 0 27 50 0 20 0.000 1 0.0000 4425 2775 225 525 4425 2775 4650 2775
+1 3 0 4 0 34 50 0 20 0.000 1 0.0000 2657 3314 242 242 2657 3314 2899 3314
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 906 2280 75 75 906 2280 981 2280
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 906 3015 75 75 906 3015 981 3015
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 891 3810 75 75 891 3810 966 3810
+1 1 0 4 0 34 50 0 20 0.000 1 0.0000 4426 2774 225 525 4426 2774 4651 2774
+1 1 0 4 0 34 50 0 20 0.000 1 0.0000 10785 4558 240 561 10785 4558 11025 4558
+1 1 0 4 0 34 50 0 20 0.000 1 0.0000 9547 3705 216 528 9547 3705 9763 3705
+1 1 0 4 0 34 50 0 20 0.000 1 0.0000 8175 2775 225 525 8175 2775 8400 2775
+1 1 0 4 0 34 40 0 -1 0.000 1 0.0000 4428 4408 240 561 4428 4408 4668 4408
+1 1 0 4 0 34 55 0 20 0.000 1 0.0000 4427 4409 240 561 4427 4409 4667 4409
+1 1 0 4 0 34 50 0 20 0.000 1 0.0000 4414 3631 216 528 4414 3631 4630 3631
+1 1 0 4 0 34 49 0 -1 0.000 1 0.0000 4426 2745 225 525 4426 2745 4651 2745
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 3600 2400 5400 1500 5400 6975 3600 5400 3600 2400
+2 1 0 6 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 900 2250 900 3825
+2 1 0 2 0 27 50 0 -1 0.000 0 0 -1 1 1 3
+	1 1 2.00 120.00 240.00
+	1 1 2.00 120.00 240.00
+	 3150 4575 3150 5550 3750 6150
+2 1 0 2 0 27 50 0 -1 0.000 0 0 -1 1 1 3
+	1 1 2.00 120.00 240.00
+	1 1 2.00 120.00 240.00
+	 6600 4650 6600 5625 7200 6225
+2 1 0 2 0 27 50 0 20 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 6600 5625 7350 5625
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 900 3825 4425 2250
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 906 3015 4416 3135
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 900 2250 4350 3825
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 900 3825 4425 3300
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 936 3015 4416 4155
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 900 2250 4386 4980
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 9675 2400 12073 1485 12073 6975 9673 5400 9673 2400
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 7275 2400 9075 1500 9075 6975 7275 5400 7273 2400
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 9075 1500 12075 1500
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 9075 6975 12075 6975
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 7275 5400 9675 5400
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 7275 2400 9675 2400
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 8475 2400 10575 1500 10575 6975 8475 5400 8475 2400
+2 1 0 2 0 27 50 0 20 0.000 0 0 -1 1 0 2
+	1 1 2.00 120.00 240.00
+	 150 3600 150 2625
+2 1 0 3 0 37 80 0 20 0.000 0 0 -1 0 0 4
+	 8175 3300 10725 5100 10800 3975 8250 2250
+4 0 0 50 0 0 24 0.0000 4 255 450 10725 5550 O*\001
+4 0 0 50 0 0 20 0.0000 4 195 135 10950 5700 1\001
+4 0 0 50 0 0 24 0.0000 4 255 270 2550 2925 O\001
+4 0 0 50 0 0 20 0.0000 4 195 135 525 2325 1\001
+4 0 0 50 0 0 20 0.0000 4 195 330 375 3075 0.5\001
+4 0 0 50 0 0 20 0.0000 4 195 135 525 3900 0\001
+4 0 0 50 0 0 20 0.0000 4 195 135 9000 7350 0\001
+4 0 0 50 0 0 20 0.0000 4 195 330 10425 7350 0.5\001
+4 0 0 50 0 0 20 0.0000 4 195 135 12075 7350 1\001
+4 0 0 50 0 0 24 0.0000 4 330 1455 9075 1200 line space\001
+4 0 0 50 0 0 24 0.0000 4 330 1260 3825 1200 viewport\001
+4 0 0 50 0 0 24 0.0000 4 300 1260 375 1200 segment\001
+4 0 0 50 0 0 24 0.0000 4 255 165 6300 5250 y\001
+4 0 0 50 0 0 24 0.0000 4 180 195 6600 6150 x\001
+4 0 0 50 0 0 24 0.0000 4 180 195 3150 6075 x\001
+4 0 0 50 0 0 24 0.0000 4 255 165 2850 5175 y\001
+4 0 0 50 0 0 24 0.0000 4 180 195 -150 3300 u\001
+4 0 0 50 0 0 24 0.0000 4 180 195 6900 5475 u\001
Index: trunk/VUT/doc/SciReport/figs/val.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/val.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/val.fig	(revision 266)
@@ -0,0 +1,82 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 35 #ff9c0a
+0 36 #ffb10a
+0 37 #ffc10a
+6 2700 4350 3000 4650
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 2730 4395 2955 4620
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 2955 4395 2730 4620
+-6
+6 13425 4350 13725 4650
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 13470 4395 13695 4620
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 13695 4395 13470 4620
+-6
+6 13500 3675 13875 3975
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 13575 3735 13800 3960
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 13800 3735 13575 3960
+-6
+6 13725 2475 14025 2775
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 13755 2490 13980 2715
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 13980 2490 13755 2715
+-6
+6 13575 3375 13875 3675
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 13620 3420 13845 3645
+2 1 0 3 0 35 50 0 20 0.000 0 0 7 0 0 2
+	 13845 3420 13620 3645
+-6
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 8010 5955 106 106 8010 5955 8116 5955
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 8640 1215 106 106 8640 1215 8746 1215
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 2670 5955 106 106 2670 5955 2776 5955
+1 3 0 3 0 7 50 0 12 0.000 1 0.0000 3225 3075 530 530 3225 3075 3600 3450
+1 3 0 3 0 35 50 0 20 0.000 1 0.0000 8565 3075 530 530 8565 3075 8940 3450
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 13410 5955 106 106 13410 5955 13516 5955
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 14040 1215 106 106 14040 1215 14146 1215
+1 3 0 3 0 35 50 0 20 0.000 1 0.0000 13965 3075 530 530 13965 3075 14340 3450
+2 1 1 3 0 35 80 0 20 8.000 0 0 -1 0 0 2
+	 8003 5969 8633 1169
+2 1 0 2 0 35 50 0 20 0.000 0 0 -1 0 0 2
+	 2670 5970 2850 4515
+2 2 0 3 0 35 50 0 20 0.000 0 0 7 0 0 5
+	 2175 3825 3225 3825 3225 4500 2175 4500 2175 3825
+2 3 0 3 0 7 50 0 12 0.000 0 0 -1 0 0 4
+	 3975 3750 3825 4875 5475 4275 3975 3750
+2 3 0 3 0 7 50 0 12 0.000 0 0 7 0 0 4
+	 4125 2100 4050 3525 5175 1950 4125 2100
+2 2 0 3 0 35 50 0 20 0.000 0 0 7 0 0 5
+	 7515 3825 8565 3825 8565 4500 7515 4500 7515 3825
+2 3 0 3 0 7 50 0 12 0.000 0 0 7 0 0 4
+	 9465 2100 9390 3525 10515 1950 9465 2100
+2 3 0 3 0 7 50 0 12 0.000 0 0 7 0 0 4
+	 9315 3750 9165 4875 10815 4275 9315 3750
+2 1 0 2 0 35 50 0 20 0.000 0 0 -1 0 0 2
+	 13410 5970 13590 4515
+2 1 0 3 0 35 80 0 20 0.000 0 0 -1 0 0 2
+	 13410 5970 14040 1170
+2 2 0 3 0 35 50 0 20 0.000 0 0 7 0 0 5
+	 12915 3825 13965 3825 13965 4500 12915 4500 12915 3825
+2 3 0 3 0 7 50 0 12 0.000 0 0 7 0 0 4
+	 14865 2100 14790 3525 15915 1950 14865 2100
+2 3 0 3 0 7 50 0 12 0.000 0 0 7 0 0 4
+	 14715 3750 14565 4875 16215 4275 14715 3750
+4 0 0 50 0 0 26 0.0000 4 345 360 2910 6165 A\001
+4 0 0 50 0 0 26 0.0000 4 345 360 8310 6150 A\001
+4 0 0 50 0 0 26 0.0000 4 345 330 8955 1365 B\001
+4 0 0 50 0 0 26 0.0000 4 345 1695 8250 5475 invisible\001
+4 0 0 50 0 0 26 0.0000 4 345 360 13710 6150 A\001
+4 0 0 50 0 0 26 0.0000 4 345 330 14355 1365 B\001
Index: trunk/VUT/doc/SciReport/figs/classes.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/classes.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/classes.fig	(revision 266)
@@ -0,0 +1,116 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 32 #ffb10a
+0 35 #ff9c0a
+6 3450 1350 8175 7200
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 3510 6390 8100 1800
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 4305 6885 7050 1575
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 5055 7125 6300 1425
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 6030 7095 5400 1425
+-6
+6 10200 1200 14850 7125
+2 1 0 10 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 11250 3915 12900 4185
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 11973 6945 11343 1275
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 11243 6980 12488 1280
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 10274 6269 14809 1612
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 11518 1335 10993 6915
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 1
+	 10993 6915
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 13498 1575 12103 7080
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 10253 2662 13628 5606
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 10230 5756 13267 1950
+-6
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 5700 4200 90 90 5700 4200 5790 4200
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 3678 9807 90 90 3678 9807 3768 9807
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 4465 10219 90 90 4465 10219 4555 10219
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 5140 10594 90 90 5140 10594 5230 10594
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 6584 11363 90 90 6584 11363 6674 11363
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 7090 11625 90 90 7090 11625 7180 11625
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 6209 11157 90 90 6209 11157 6299 11157
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 -1050 10500 90 90 -1050 10500 -960 10500
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 11290 3938 90 90 11290 3938 11380 3938
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 12865 4163 90 90 12865 4163 12955 4163
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 10615 10088 90 90 10615 10088 10705 10088
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 11683 9863 90 90 11683 9863 11773 9863
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 12471 11982 90 90 12471 11982 12561 11982
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 13446 11119 90 90 13446 11119 13536 11119
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 12058 10913 90 90 12058 10913 12148 10913
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 13821 11757 90 90 13821 11757 13911 11757
+1 3 0 1 0 0 60 0 20 0.000 1 0.0000 10858 11119 90 90 10858 11119 10948 11119
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 4511 2475 6855 5831
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 3874 4687 7567 3675
+2 2 0 1 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 3300 1200 8400 1200 8400 7200 3300 7200 3300 1200
+2 2 0 1 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 3300 8100 8400 8100 8400 14100 3300 14100 3300 8100
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 3300 9600 8400 12300
+2 2 0 1 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 -3300 1200 1800 1200 1800 7200 -3300 7200 -3300 1200
+2 2 0 1 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 9900 1200 15000 1200 15000 7200 9900 7200 9900 1200
+2 2 0 1 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 9900 8100 15000 8100 15000 14100 9900 14100 9900 8100
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 9910 9383 15029 10695
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 9902 11719 15021 12244
+2 2 0 1 0 7 50 0 -1 0.000 0 0 -1 0 0 5
+	 -3300 8100 1800 8100 1800 14100 -3300 14100 -3300 8100
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 0 0 2
+	 -2237 6433 628 1783
+2 1 0 0 0 7 80 0 16 0.000 0 0 -1 0 0 5
+	 9902 9375 15002 10688 15002 12244 9902 11719 9902 9375
+3 0 0 2 35 7 50 0 -1 0.000 0 1 0 3
+	1 1 2.00 120.00 240.00
+	 -1552 5687 -633 7712 -896 10168
+	 0.000 1.000 0.000
+3 0 0 2 35 7 50 0 -1 0.000 0 1 0 4
+	1 1 2.00 120.00 240.00
+	 3801 6324 4232 8387 4195 9174 3895 9568
+	 0.000 1.000 1.000 0.000
+3 0 0 2 35 7 50 0 -1 0.000 0 1 0 4
+	1 1 2.00 120.00 240.00
+	 5864 6849 5676 8312 5957 9699 6276 10843
+	 0.000 1.000 1.000 0.000
+3 0 0 2 35 7 50 0 -1 0.000 0 1 0 3
+	1 1 2.00 120.00 240.00
+	 10936 7093 11030 8424 11555 9605
+	 0.000 1.000 0.000
+3 0 0 2 35 7 50 0 -1 0.000 0 1 0 5
+	1 1 2.00 120.00 240.00
+	 12361 6587 13018 7862 13261 9324 13055 10899 12624 11743
+	 0.000 1.000 1.000 1.000 0.000
+4 0 0 50 0 0 32 0.0000 4 450 1755 -1804 384 visibility\001
+4 0 0 50 0 0 32 0.0000 4 450 1935 -1979 934 along line\001
+4 0 0 50 0 0 32 0.0000 4 450 1755 4596 384 visibility\001
+4 0 0 50 0 0 32 0.0000 4 450 2085 4471 909 from point\001
+4 0 0 50 0 0 32 0.0000 4 450 1755 11371 384 visibility\001
+4 0 0 50 0 0 32 0.0000 4 450 2730 10896 934 from segment\001
+4 0 0 50 0 0 32 0.0000 4 345 525 -684 14799 =0\001
+4 0 0 50 0 0 32 0.0000 4 345 240 -1109 14815 d\001
+4 0 0 50 0 0 32 0.0000 4 345 240 5491 14840 d\001
+4 0 0 50 0 0 32 0.0000 4 345 525 5916 14799 =1\001
+4 0 0 50 0 0 32 0.0000 4 345 240 12291 14815 d\001
+4 0 0 50 0 0 32 0.0000 4 345 525 12716 14799 =2\001
Index: trunk/VUT/doc/SciReport/figs/duality2d.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/duality2d.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/duality2d.fig	(revision 266)
@@ -0,0 +1,174 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 35 #ff9c0a
+6 6750 12675 10950 13050
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 1 1 2
+	1 1 2.00 120.00 210.00
+	1 1 2.00 120.00 210.00
+	 7950 12900 8625 12900
+4 0 0 50 0 0 24 0.0000 4 330 870 6750 12975 p(a,b)\001
+4 0 0 50 0 0 24 0.0000 4 330 2070 8850 12975 p*:ax+by-1=0\001
+-6
+6 12225 -75 16125 300
+2 1 0 2 0 7 50 0 -1 0.000 0 0 7 1 1 2
+	1 1 2.00 120.00 210.00
+	1 1 2.00 120.00 210.00
+	 13350 150 14025 150
+4 0 0 50 0 0 24 0.0000 4 330 870 12225 225 p(a,b)\001
+4 0 0 50 0 0 24 0.0000 4 330 1995 14100 225 p*:2ax-y-b=0\001
+-6
+6 1650 -75 5550 300
+2 1 0 2 0 7 50 0 -1 0.000 0 0 -1 1 1 2
+	1 1 2.00 120.00 210.00
+	1 1 2.00 120.00 210.00
+	 2700 150 3375 150
+4 0 0 50 0 0 24 0.0000 4 330 870 1650 225 p(a,b)\001
+4 0 0 50 0 0 24 0.0000 4 330 1965 3525 225 p*:ax+y+b=0\001
+-6
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 3000 2844 54 54 3000 2844 3052 2860
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 3752 1951 54 54 3752 1951 3804 1967
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 2490 3425 54 54 2490 3425 2542 3441
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 3525 5561 54 54 3525 5561 3577 5577
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 2490 5553 54 54 2490 5553 2542 5569
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 1405 2835 54 54 1405 2835 1457 2851
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 9329 8112 54 54 9329 8112 9381 8128
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 6436 7797 54 54 6436 7797 6488 7813
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 8609 9149 54 54 8609 9149 8661 9165
+1 3 0 1 0 0 40 0 -1 0.000 1 0.0000 8325 8700 1172 1172 8325 8700 9497 8700
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 13012 3234 54 54 13012 3234 13064 3250
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 13720 2094 54 54 13720 2094 13772 2110
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 15082 2839 54 54 15082 2839 15134 2855
+1 3 0 2 0 0 50 0 20 0.000 1 0.0000 13424 3462 54 54 13424 3462 13476 3478
+2 1 0 3 0 0 40 0 20 0.000 0 0 7 0 0 2
+	 592 2844 5685 2844
+2 1 0 2 0 0 40 0 20 0.000 0 0 7 0 0 2
+	 405 2459 5490 4364
+2 1 0 3 0 0 40 0 20 0.000 0 0 7 0 0 2
+	 445 4588 5530 6493
+2 1 0 5 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 5850 3900 0 3900
+2 1 0 5 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 3000 750 3000 7050
+2 1 0 3 0 0 40 0 20 0.000 0 0 7 0 0 2
+	 248 3490 5030 776
+2 1 0 5 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 11175 8700 5325 8700
+2 1 0 5 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 8325 5550 8325 11850
+2 1 0 3 0 0 40 0 20 0.000 0 0 -1 0 0 2
+	 7994 5784 11182 11226
+2 1 0 1 0 0 40 0 20 0.000 0 0 -1 0 0 2
+	 6442 7809 8317 8686
+2 1 0 3 0 0 40 0 20 0.000 0 0 -1 0 0 2
+	 8864 5806 6352 11199
+2 1 0 1 0 0 40 0 20 0.000 0 0 -1 0 0 2
+	 8332 8724 9607 10726
+2 1 0 3 0 0 40 0 20 0.000 0 0 -1 0 0 2
+	 7672 11976 11302 9659
+2 1 0 5 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 16567 3894 10717 3894
+2 1 0 5 0 7 50 0 -1 0.000 0 0 -1 0 0 2
+	 13717 744 13717 7044
+2 1 0 3 0 0 40 0 -1 0.000 0 0 -1 0 0 2
+	 11737 849 14677 6324
+2 1 0 3 0 0 40 0 -1 0.000 0 0 -1 0 0 2
+	 10723 5697 16312 5697
+2 1 0 3 0 0 40 0 -1 0.000 0 0 -1 0 0 2
+	 13237 6334 15202 657
+2 1 0 3 0 0 40 0 -1 0.000 0 0 -1 0 0 2
+	 15464 5974 10852 1744
+2 1 0 3 0 0 40 0 20 0.000 0 0 7 0 0 2
+	 443 6500 5528 4595
+2 1 0 3 0 0 40 0 20 0.000 0 0 7 0 0 2
+	 4717 831 1110 5034
+3 0 0 1 0 0 40 0 -1 0.000 0 0 0 12
+	 12181 624 12456 1734 12629 2289 12831 2814 12924 3049 13049 3301
+	 13139 3439 13234 3584 13339 3714 13444 3809 13544 3874 13716 3886
+	 0.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
+	 1.000 1.000 1.000 0.000
+3 0 0 1 0 0 40 0 -1 0.000 0 0 0 12
+	 15274 609 14997 1733 14824 2288 14622 2813 14529 3048 14404 3300
+	 14314 3438 14219 3583 14114 3713 14009 3808 13909 3873 13737 3885
+	 0.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
+	 1.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 4
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 3645 5555 3975 5475 3945 5383 4125 5175
+	 0.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 4
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 2362 5540 2250 5475 2025 5625 2070 5863
+	 0.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 6
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 2535 2780 2595 2638 2692 2563 2797 2555 2917 2615 2940 2735
+	 0.000 1.000 1.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 5
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 3202 1846 3270 1951 3397 2034 3540 2034 3630 2004
+	 0.000 1.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 4
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 2175 3159 2137 3301 2190 3429 2392 3451
+	 0.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 4
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 9050 7437 9372 7490 9500 7700 9440 8000
+	 0.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 5
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 8735 9140 9200 9312 9455 9635 9732 10137 9890 10430
+	 0.000 1.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 4
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 13847 2187 14192 3004 14440 4414 14560 5614
+	 0.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 4
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 14440 3087 14710 3154 14965 3094 15062 2974
+	 0.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 3
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 12827 3477 13180 3334 13330 3372
+	 0.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 4
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 12880 3222 12662 3177 12535 2967 12632 2697
+	 0.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 6
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 6560 7715 6867 7617 7167 7617 7370 7677 7647 7812 7790 7887
+	 0.000 1.000 1.000 1.000 1.000 0.000
+3 0 0 3 35 0 40 0 -1 0.000 0 1 1 6
+	0 0 2.00 90.00 150.00
+	0 0 2.00 90.00 150.00
+	 1410 2941 1440 3159 1500 3375 1725 3525 2047 3586 2190 3646
+	 0.000 1.000 1.000 1.000 1.000 0.000
+4 0 0 50 0 0 24 0.0000 4 225 555 16050 4275 x, a\001
+4 0 0 50 0 0 24 0.0000 4 330 540 12975 1050 y, b\001
+4 0 0 50 0 0 24 0.0000 4 225 555 10725 9075 x, a\001
+4 0 0 50 0 0 24 0.0000 4 330 540 7650 5625 y, b\001
+4 0 0 50 0 0 24 0.0000 4 225 555 5700 4275 x, a\001
+4 0 0 50 0 0 24 0.0000 4 330 540 2250 975 y, b\001
+4 0 0 50 0 0 24 0.0000 4 330 2115 6750 12450 polar mapping\001
+4 0 0 50 0 0 24 0.0000 4 330 2625 12225 -300 parabola mapping\001
+4 0 0 50 0 0 24 0.0000 4 330 2145 1650 -300 slope mapping\001
Index: trunk/VUT/doc/SciReport/figs/3dlines.fig
===================================================================
--- trunk/VUT/doc/SciReport/figs/3dlines.fig	(revision 266)
+++ trunk/VUT/doc/SciReport/figs/3dlines.fig	(revision 266)
@@ -0,0 +1,51 @@
+#FIG 3.2
+Landscape
+Center
+Inches
+Letter  
+100.00
+Single
+-2
+1200 2
+0 35 #ff9c0a
+0 36 #ffb10a
+0 37 #ffc10a
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 2472 5595 121 121 2472 5595 2593 5595
+1 3 0 1 0 7 50 0 6 0.000 1 0.0000 5322 2925 108 108 5322 2925 5430 2925
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 11174 5420 121 121 11174 5420 11295 5420
+1 3 0 1 0 0 50 0 20 0.000 1 0.0000 15524 2540 121 121 15524 2540 15645 2540
+1 3 0 2 0 7 80 0 17 0.000 1 0.0000 3300 3900 2689 2689 3300 3900 5989 3900
+2 1 0 3 0 7 50 0 -1 0.000 0 0 -1 0 1 2
+	0 0 3.00 180.00 360.00
+	 942 7035 2427 5625
+2 1 0 3 0 7 50 0 -1 0.000 0 0 -1 1 0 2
+	0 0 3.00 180.00 360.00
+	 5637 2640 6972 1380
+2 1 1 3 0 7 60 0 -1 8.000 0 0 -1 0 0 2
+	 975 6990 6825 1515
+2 1 1 3 0 7 60 0 -1 8.000 0 0 -1 0 0 2
+	 9152 6710 17702 1160
+2 1 0 3 0 7 60 0 -1 0.000 0 0 -1 0 1 2
+	0 0 3.00 180.00 360.00
+	 9164 6710 10349 5930
+2 1 0 3 0 7 60 0 -1 0.000 0 0 -1 1 0 2
+	0 0 3.00 180.00 360.00
+	 16334 2060 17669 1175
+2 1 0 3 0 7 55 0 -1 0.000 0 0 -1 0 0 2
+	 11159 5420 12866 4294
+2 1 0 3 0 7 55 0 -1 0.000 0 0 -1 0 0 2
+	 14302 3363 15622 2493
+2 3 0 2 0 7 80 0 17 0.000 0 0 -1 0 0 5
+	 10352 560 12152 1760 12152 5960 10352 7460 10352 560
+2 3 0 2 0 7 80 0 17 0.000 0 0 -1 0 0 5
+	 16329 525 14529 1725 14529 5925 16329 7425 16329 525
+3 1 0 3 0 7 70 0 8 0.000 0 0 0 8
+	 11411 3610 12206 2470 13496 3895 14456 3010 15101 4270 13466 5680
+	 12761 4510 11831 4435
+	 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
+3 1 0 3 0 7 70 0 8 0.000 0 0 0 8
+	 1497 3405 2292 2265 3582 3690 4542 2805 5187 4065 3552 5475
+	 2847 4305 1917 4230
+	 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000
+4 0 0 60 0 0 28 0.0000 4 225 1110 2925 2850 scene\001
+4 0 0 60 0 0 28 0.0000 4 225 1110 12825 3000 scene\001
Index: trunk/VUT/doc/SciReport/mutual.tex
===================================================================
--- trunk/VUT/doc/SciReport/mutual.tex	(revision 249)
+++ trunk/VUT/doc/SciReport/mutual.tex	(revision 266)
@@ -1,5 +1,4 @@
 \chapter{Mutual Visibility Tool}
 
-\section{Introduction}
 
 If a fast visibility solution is required such as during the
@@ -13,5 +12,5 @@
 cell pairs which are classified as mutually invisible. We process the
 objects sequentially and for every given object we determine the view
-cell which form the boundary of the invisible view cell set.
+cells which form the boundary of the invisible view cell set.
 
 This boundary it is based on the current view cell visibility
@@ -34,4 +33,9 @@
 simpler case both are defined by an axis aligned bounding box.
 
+Below, we describe three different mutual visibility verification
+algorithms. The first algorithm which is described in most detail
+computes exact visibility. The second one is a coservative algorithm
+and the third one is an approximate algorithm with a guaranteed error
+bound.
 
 
@@ -40,6 +44,8 @@
 The exact mutual visibility test computes exact visibility between two
 polyhedrons in the scene. This is computed by testing visibility
-between all pairs of potentially polygons of these polyhedrons.
-
+between all pairs of potentially visible polygons of these
+polyhedrons.  For each pair of tested polygons the computation is
+localized into the shaft defined by their convex hull. This shaft is
+used to determine the set of relevant occluders~\cite{Haines94}.
 
 \section{Occlusion tree}
@@ -59,10 +65,21 @@
  Leaves of the occlusion tree are classified $in$ or $out$. If $N$ is
 an $out$-leaf, ${\mathcal Q^*_N}$ represents unoccluded rays emerging
-from the source polygon $P_S$. If $N$ is an $in$-leaf, it is associated
-with an occluder $O_N$ that blocks the corresponding set of rays
-${\mathcal Q^*_N}$. Additionally $N$ stores a fragment of the blocker
-polyhedron $B_N$ representing ${\mathcal Q^*_N}$. The intersection of
-$B_N$ and the \plucker quadric corresponds to a set of stabbers ${\cal
-S}_N$ through which $O_N$ is visible from $P_S$.
+from the source polygon $P_S$. If $N$ is an $in$-leaf, it is
+associated with an occluder $O_N$ that blocks the corresponding set of
+rays ${\mathcal Q^*_N}$. Additionally $N$ stores a fragment of the
+blocker polyhedron $B_N$ representing ${\mathcal Q^*_N}$. The
+intersection of $B_N$ and the \plucker quadric corresponds to a set of
+stabbers ${\cal S}_N$ through which $O_N$ is visible from $P_S$. A 2D
+example of an occlusion tree is shown at Figure~\ref{fig:ot}.
+
+\begin{figure}[htb]
+\centerline{
+\includegraphics[width=0.9\textwidth,draft=\DRAFTFIGS]{figs/ot1}}
+\caption{A 2D example of an occlusion tree. Rays intersecting scene polygons
+are represented by polyhedra P1, P2 and P3. The occlusion tree represents a union
+of the polyhedra. Note that P2 has been split during the insertion process.}
+\label{fig:duality2d}
+\end{figure}
+
 
 %%  Consider a source polygon and a single occluder such as in
@@ -77,9 +94,9 @@
 
  The occlusion tree is constructed incrementally by inserting blocker
-polyhedra in the order given by the approximate occlusion sweep of the
-scene polygons. When processing a polygon $P_j$ the algorithm inserts
-a polyhedron $B_{P_SP_j}$ representing the feasible line set between
-the source polygon $P_S$ and the polygon $P_j$. The polyhedron is
-split into fragments that represent either occluded or unoccluded rays.
+polyhedra in the order given by the size of the polygons. When
+processing a polygon $P_j$ the algorithm inserts a polyhedron
+$B_{P_SP_j}$ representing the feasible line set between the source
+polygon $P_S$ and the polygon $P_j$. The polyhedron is split into
+fragments that represent either occluded or unoccluded rays.
 
  We describe two methods that can be used to insert a blocker
@@ -113,12 +130,9 @@
 classification.  If $N_{c}$ is an $out$-leaf then $B_{c}$ is visible
 and $N_c$ is replaced by the elementary occlusion tree of $B_{c}$. If
-$N_{c}$ is an $in$-leaf, the mutual position of the currently
-processed polygon $B_j$ and the polygon $B_{N_{c}}$ associated with
-$N_{c}$ is determined. This test will be described in
-Section~\ref{sec:position}. If $B_{c}$ is behind $B_{N_{c}}$ it is
-invisible and no modification to the tree necessary. Otherwise we need
-to {\em merge} $B_{c}$ into the tree. The merging replaces $N_{c}$ by
-the elementary occlusion tree of $B_c$ and inserts the old fragment
-$B_{N_{c}}$ in the new subtree.
+$N_{c}$ is an $in$-leaf it corresponds to already occluded rays and no
+modification to the tree necessary. Otherwise we need to {\em merge}
+$B_{c}$ into the tree. The merging replaces $N_{c}$ by the elementary
+occlusion tree of $B_c$ and inserts the old fragment $B_{N_{c}}$ in
+the new subtree.
 
 \subsection{Insertion without splitting}
@@ -142,7 +156,7 @@
 continues in the left subtree. If $B_c$ intersects both halfspaces the
 algorithm proceeds in both subtrees of $N_c$ and $\pplane_{N_c}$ is
-added to the list of splitting hyperplanes with a correct sign for each
-subtree. Reaching an $out$-leaf the list of splitting hyperplanes and
-the associated signs correspond to halfspaces bounding the
+added to the list of splitting hyperplanes with a correct sign for
+each subtree. Reaching an $out$-leaf the list of splitting hyperplanes
+and the associated signs correspond to halfspaces bounding the
 corresponding polyhedron fragment. The polyhedron enumeration
 algorithm is  applied using these halfspaces and the original
@@ -151,8 +165,7 @@
 halfspaces is empty. Such a case occurs due to the conservative
 traversal of the tree that only tests the position of the inserted
-polyhedron with respect to the splitting hyperplanes\footnote{Such a
-traversal was also used in Section~\ref{sec:rtviscull_conserva} in the
-context of the from-point visibility culling.}. If the fragment is not
-empty, the tree is extended as described in the previous section.
+polyhedron with respect to the splitting hyperplanes. If the fragment
+is not empty, the tree is extended as described in the previous
+section.
 
 Reaching an $in$-leaf the polygon positional test is applied. If the
@@ -186,29 +199,4 @@
 
 
-\subsection{Polygon positional test}
-\label{sec:position}
-
-The polygon positional test aims to determine the order of two
-polygons $P_i$ and $P_j$ with respect to the source polygon
-$P_S$~\cite{Chrysantho1996a}. We assume that polygons $P_i$ and $P_j$
-do not intersect, i.e. all potential polygon intersections were
-resolved in preprocessing. The test is applied to determine which of
-the two polygons is closer to $P_S$ with respect to the given set of
-rays intersecting both polygons. The test proceeds as follows:
-
-\begin{enumerate}
-\item If $P_i$ lays in the positive/negative halfspace defined by
-$P_j$, it is before/behind $P_j$. Otherwise, proceed with the next step.
-\item If $P_j$ lays in the positive/negative halfspace defined by
-$P_i$, it is before/behind $P_i$. Otherwise, proceed with the next step.
-\item Find a ray from the given set of rays that intersects both
-polygons. Compute an intersection of the ray with $P_i$ and $P_j$ and
-determine the position of the polygons according to the order of
-intersection points along the ray.
-\end{enumerate}
-
-The first two steps aim to determine the absolute priority of one of
-the polygons. If these steps fail, the order of the polygons is
-determined using a sample ray in step 3.
 
 \section{Visibility test}
@@ -263,91 +251,29 @@
 alter the accuracy of the visibility algorithm.
  
-\subsection{Shaft culling}
-
-\label{sec:rot3_shaft}
-
-The algorithm as described computes and maintains visibility of all
-polygons facing the given source polygon. In complex scenes the
-description of visibility from the source polygon can reach $O(n^4)$
-complexity in the worse
-case~\cite{Teller92phd,p-rsls-97,Durand99-phd}. The size of the
-occlusion tree is then bound by $O(n^5)$. Although such a
-configuration occurs rather rare in practice we need to apply some
-general technique to avoid the worst-case memory complexity. If the
-algorithm should provide an exact analytic solution to the problem, we
-cannot avoid the $O(n^4\log n)$ worst-case computational complexity,
-but the computation can be decoupled to reduce memory requirements.
-
- We propose to use the {\em shaft culling}~\cite{Haines94} method that
-divides the computation into series of from-region visibility
-problems restricted by a given shaft of lines. Ideally the shafts are
-determined so that the {\em visibility complexity} in the shaft is
-bound by a given constant. This is however the from-region visibility
-problem itself. We can use an estimate based on a number of polygons
-in the given shaft. First, the hemicube is erected over the source
-polygon and it is used to construct five shafts corresponding to the
-five faces  of the hemicube. The shafts are then subdivided as
-follows: if a given shaft intersects more than a predefined number of
-polygons the corresponding hemicube face is split in two and the new
-shafts are processed recursively.  Visibility in the shaft is
-evaluated using all polygons intersecting the shaft. When the
-computation for the shaft is finished the occlusion tree is
-destroyed. The algorithm then proceeds with the next shaft until all
-generated shafts have been processed. See Figure~\ref{fig:rot3_shafts}
-for an example of a regular subdivision of the problem-relevant line
-set into 80 shafts.
-
-
-This technique shares a similarity with the algorithm recently
-published by Nirenstein et al.~\cite{nirenstein:02:egwr} that uses
-shafts between the source polygon and each polygon in the
-scene. Our technique provides the following benefits:
-
-\begin{itemize}
-\item The shaft can contain thousands of polygons, which allows to
-better exploit the coherence of visibility. The hierarchical line
-space subdivision allows efficient searches and updates.
-
-\item The method is applicable even in scenes with big differences in
-polygon sizes. Unlike the method of Nirenstein et
-al.~\cite{nirenstein:02:egwr}, the proposed technique generates shafts
-to find balance between the use of coherence and the memory
-requirements. Due to the hierarchical subdivision of the
-problem-relevant line set our method can handle the case when there is
-a huge number of polygons in a single shaft between two large scene
-polygons.
-
-\item Visibility in the whole shaft is described in a unified data
-  structure, which can serve for further computations (e.g. extraction
-  of event surfaces, hierarchical representation of visibility, etc.).
-\end{itemize}
-
-
-
-\subsection{Occluder sorting}
-
- Occluder sorting aims to increase the accuracy of the front-to-back
-ordering determined by the approximate occlusion sweep. Higher
-accuracy of the ordering decreases the number of the late merging of
-blocker polyhedra in the tree.  Recall that the merging extends the
-occlusion tree by a blocker polyhedron corresponding to an occluder
-that hides an already processed occluder.
-
- The occluder sorting is applied when reaching a leaf node of the
-spatial hierarchy during the approximate occlusion sweep. Given a leaf
-node $N$ the occluder sorting proceeds as follows:
-
-\begin{enumerate}
-\item Determine a ray $r$ piercing the center of the source polygon
-$P_S$ and the node $N$.
-\item Compute intersections of $r$ and all supporting planes of the
-polygons associated with $N$.
-\item Sort the polygons according to the front-to-back order of the
-corresponding intersection points along $r$.
-\end{enumerate}
-
-The occluder sorting provides an exact priority order within the given
-leaf in the case that the polygons are pierced by the computed ray $r$
-and they do not intersect.
+% \subsection{Occluder sorting}
+
+%  Occluder sorting aims to increase the accuracy of the front-to-back
+% ordering determined by the approximate occlusion sweep. Higher
+% accuracy of the ordering decreases the number of the late merging of
+% blocker polyhedra in the tree.  Recall that the merging extends the
+% occlusion tree by a blocker polyhedron corresponding to an occluder
+% that hides an already processed occluder.
+
+%  The occluder sorting is applied when reaching a leaf node of the
+% spatial hierarchy during the approximate occlusion sweep. Given a leaf
+% node $N$ the occluder sorting proceeds as follows:
+
+% \begin{enumerate}
+% \item Determine a ray $r$ piercing the center of the source polygon
+% $P_S$ and the node $N$.
+% \item Compute intersections of $r$ and all supporting planes of the
+% polygons associated with $N$.
+% \item Sort the polygons according to the front-to-back order of the
+% corresponding intersection points along $r$.
+% \end{enumerate}
+
+% The occluder sorting provides an exact priority order within the given
+% leaf in the case that the polygons are pierced by the computed ray $r$
+% and they do not intersect.
 
 
@@ -413,6 +339,51 @@
 \section{Conservative Verifier}
 
-
-\section{Error Bound Verifier}
+A conservative verifier is a faster alternative to the exact
+visibility verifier described above. The verifier is an extension of
+the strong occlusion algorithm of Cohen-Or et
+al.~\cite{cohen-egc-98}. In particular our verfier refines the search
+for a strong occluder by using a hiearrchical subdivision of space of
+lines connecting the two regions tested for mutual
+visibility. Initially the shaft bounding the the tested regions is
+constructed. Rays bounding the shaft are traced through the scene and
+we compute all intersections with the scene objects between the tested
+regions. The the algorithm proceeds as follows:
+
+\begin{itemize}
+\item In the case that any ray does not intersect any object the
+tested regions are classified as visibility and the algorithm
+terminates.
+\item If the rays intersect the same convex object (at any
+depth) this object is a strong occluder with respect to the shaft and
+thus it also hides all rays in the corresponding shaft.
+\item If the rays do not intersect a single convex object four new
+shafts are constructed by splitting both regions in half and the
+process is repeated recursivelly.
+\end{itemize}
+
+If the subdivision does not terminate till reaching a predefined
+subdivision depth, we conservativelly classify the tested regions as
+mutually visible.
+
+
+\section{Error Bound Approximate Verifier}
+
+The approximate verifier will be based on the similar idea as the
+conservative one. However it will behave differently in the finer
+subdivision of the ray shafts. The idea is to use the above algorithm
+as far as the shafts get small enough that we can guarantee that even
+if the shaft is not blocked by the scene objects, a pixel error
+induced due to omission of objects potential visible behind the shaft
+is bellow a given threshold.
+
+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
+object bounding box or cell of the spatial hierarchy. The threshold is
+computed as follows: We first triangulate the farthest intesection
+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
+maximizes the projected area of the triangle. The conservative
+estimate of the maximal error is then given by a sum of the computed
+projected areas.
 
 %Option: - if there is sufficient number of samples from 1 + 2 and some
@@ -421,30 +392,30 @@
 %from there values.
 
-a) is perhaps the most interesting since this has not been done so far at all. I though about different methods how to do that (e.g. maintaining a triangulated front visible layer), but I always found some problem. I believe that the method which is almost implemented now is solid and I just wonder what performance it will achieve.
-
-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:
-
-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.
-
-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.
-
-4. Triangulate the depth of the shaft as seen from the viecell side of the shaft and compute the maximal projected area of the 2 computed triangles. This determines the maximal pixel error we can make by terminating this branch as invisible.
-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.
-
-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.
-
-
-> Partly: area subdivision algorithm does not only cast "corner" rays, but maintains lists of the triangles for the given area. However the basic idea is the same: subdivide the set or rays until there is a trivial decision (a single convex object intersected by all corner rays) or the error is too small. The second criterion is different from the from-poin t setup, since the error cannot be evaluated in a single projection plane.
-> That is why this triangulation would be done: Imagine that the 4 corner rays of a shaft intersect some object(s) in the scene. Now connect these intersection points by creating two triangles. These triangles do not exist in the scene, but define the largest possible windows through which we can see further in the shaft. Now it is easy to find two points at the origin of the shaft which maximize the projected area of the two triangles. The sum of these areas gives a conservative estimate of the spatial angle error which can be made by not subdividing the shaft any further.
-> Is this description clearer?
-
-
-partly - I just don't see it in front of me now. How is the result influenced by which triangles are chosen? Is it so that the nearer the intersections, the bigger the error?
+% a) is perhaps the most interesting since this has not been done so far at all. I though about different methods how to do that (e.g. maintaining a triangulated front visible layer), but I always found some problem. I believe that the method which is almost implemented now is solid and I just wonder what performance it will achieve.
+
+% 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:
+
+% 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.
+
+% 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.
+
+% 4. Triangulate the depth of the shaft as seen from the viecell side of the shaft and compute the maximal projected area of the 2 computed triangles. This determines the maximal pixel error we can make by terminating this branch as invisible.
+% 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.
+
+% 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.
+
+
+% > Partly: area subdivision algorithm does not only cast "corner" rays, but maintains lists of the triangles for the given area. However the basic idea is the same: subdivide the set or rays until there is a trivial decision (a single convex object intersected by all corner rays) or the error is too small. The second criterion is different from the from-poin t setup, since the error cannot be evaluated in a single projection plane.
+% > That is why this triangulation would be done: Imagine that the 4 corner rays of a shaft intersect some object(s) in the scene. Now connect these intersection points by creating two triangles. These triangles do not exist in the scene, but define the largest possible windows through which we can see further in the shaft. Now it is easy to find two points at the origin of the shaft which maximize the projected area of the two triangles. The sum of these areas gives a conservative estimate of the spatial angle error which can be made by not subdividing the shaft any further.
+% > Is this description clearer?
+
+
+% partly - I just don't see it in front of me now. How is the result influenced by which triangles are chosen? Is it so that the nearer the intersections, the bigger the error?
 
 
@@ -454,35 +425,34 @@
 \label{sec:rot3d_summary}
 
- This chapter presented a new method for computing from-region
-visibility in polygonal scenes. The method is based on the concept of
-line space subdivision, approximate occlusion sweep and hierarchical
-visibility tests. The key idea is a hierarchical subdivision of the
-problem-relevant line set using \plucker coordinates and the occlusion
-tree.  \plucker coordinates allow to perform operations on sets of
-lines by means of set theoretical operations on the 5D polyhedra. The
-occlusion tree is used to maintain a union of the polyhedra that
-represent lines occluded from the given region (polygon).
-
- We discussed the relation of sets of lines in 3D and the polyhedra in
-\plucker coordinates. We proposed a general size measure for a set of
-lines described by a blocker polyhedron and a size measure designed
-for the computation of PVS. The chapter presented two algorithms for
-construction of the occlusion tree by incremental insertion of blocker
-polyhedra. The occlusion tree was used to test visibility of a given
-polygon or region with respect to the source polygon/region. We
-proposed several optimization of the algorithm that make the approach
-applicable to large scenes. The chapter discussed three possible
-applications of the method: discontinuity meshing, visibility culling,
-and occluder synthesis.
-
-The implementation of the method was evaluated on scenes consisting of
-randomly generated triangles, structured scenes, and a real-world
-urban model. The evaluation was focused on the application method for
-PVS computation.  By computing a PVS in a model of the city of Graz it
-was shown that the approach is suitable for visibility preprocessing
-in urban scenes. The principal advantage of the method is that it does
-not rely on various tuning parameters that are characterizing many
-conservative or approximate algorithms. On the other hand the
-exactness of the method requires higher computational demands and
-implementation effort.
-
+ This chapter presented a mutuaql visibility tool, which determines
+ whether two regions in the scene are visible.
+
+ First, we have described an advanced exact visibility algorithm which
+is a simple of modification of an algorithm for computing from-region
+visibility in polygonal scenes. The key idea is a hierarchical
+subdivision of the problem-relevant line set using \plucker
+coordinates and the occlusion tree.  \plucker coordinates allow to
+perform operations on sets of lines by means of set theoretical
+operations on the 5D polyhedra. The occlusion tree is used to maintain
+a union of the polyhedra that represent lines occluded from the given
+region (polygon). We described two algorithms for construction of the
+occlusion tree by incremental insertion of blocker polyhedra. The
+occlusion tree was used to test visibility of a given polygon or
+region with respect to the source polygon/region. We proposed several
+optimization of the algorithm that make the approach applicable to
+large scenes. The principal advantage of the exact method over the
+conservative and the approximate ones is that it does not rely on
+various tuning parameters that are characterizing many conservative or
+approximate algorithms. On the other hand the exactness of the method
+requires higher computational demands and implementation effort.
+
+Second, we have described a conservative verifier which is an
+extension of the algorithm based on strong occluders. The conservative
+verifier is requires a specification of the shaft size at which the
+tested regions are conservativelly classfied as visible.
+
+Third, we have described an approximate error bound verifier which is
+an extension of the algorithm based on strong occluders. The
+conservative verifier is requires a specification of the shaft size at
+which the tested regions are conservativelly classfied as visible.
+
Index: trunk/VUT/doc/SciReport/sampling.tex
===================================================================
--- trunk/VUT/doc/SciReport/sampling.tex	(revision 255)
+++ trunk/VUT/doc/SciReport/sampling.tex	(revision 266)
@@ -1,6 +1,3 @@
 \chapter{Global Visibility Sampling Tool}
-
-
-\section{Introduction}
 
 
@@ -21,11 +18,11 @@
 conservative or error bound aggresive solution. The choice of the
 particular verifier is left on the user in order to select the best
-for a particular scene, application context and time constrains. For
-example, in scenes like a forest an error bound aggresive visibility
-can be the best compromise between the resulting size of the PVS (and
-framerate) and the visual quality. The exact or conservative algorithm
-can however be chosen for urban scenes where of even small objects can
-be more distructing for the user. The mutual visibility tool will be
-described in the next chapter.
+one for a particular scene, application context and time
+constrains. For example, in scenes like a forest an error bound
+aggresive visibility can be the best compromise between the resulting
+size of the PVS (and framerate) and the visual quality. The exact or
+conservative algorithm can however be chosen for urban scenes where
+ommision of even small objects can be more distructing for the
+user. The mutual visibility tool will be described in the next chapter.
 
 \end{itemize}
@@ -35,5 +32,5 @@
 subdivided into viewcells 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.
+has been used for conservative, aggresive and exact algorithms.
 
 We propose a different strategy which has several advantages for
@@ -41,6 +38,6 @@
 based on the following fundamental ideas:
 \begin{itemize}
-\item Replace the roles of view cells and objects
 \item Compute progressive global visibility instead of sequential from-region visibility
+\item Replace the roles of view cells and objects for some parts of the computation
 \end{itemize}
 
@@ -52,6 +49,5 @@
 \label{VFR3D_RELATED_WORK}
 
-
- Below we briefly discuss the related work on visibility preprocessing
+Below we briefly discuss the related work on visibility preprocessing
 in several application areas. In particular we focus on computing
 from-region which has been a core of most previous visibility
@@ -63,5 +59,5 @@
 The first algorithms dealing with from-region visibility belong to the
 area of computer vision. The {\em aspect
-graph}~\cite{Gigus90,Plantinga:1990:RTH, Sojka:1995:AGT} partitions
+  graph}~\cite{Gigus90,Plantinga:1990:RTH, Sojka:1995:AGT} partitions
 the view space into cells that group viewpoints from which the
 projection of the scene is qualitatively equivalent. The aspect graph
@@ -237,5 +233,11 @@
 attenuation, reflection and time delays.
 
-\section{Algorithm Setup}
+\section{Algorithm Description}
+
+This section first describes the setup of the global visibility
+sampling algorithm. In particular we describe the view cell
+representation and the novel concept of from-object based
+visibility. The we outline the different visibility sampling
+strategies.
 
 \subsection{View Cell Representation}
@@ -247,5 +249,5 @@
 \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)
+\item naturally suited for a hierarchical approach. %(i.e., there is a root view cell containing all others)
 \end{itemize}
 
@@ -257,7 +259,9 @@
 subdivide a BSP leaf view cell quite easily.
 
-Currently we use two approaches to generate the initial BSP view cell tree.
+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
@@ -270,12 +274,14 @@
 (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}
 
 \subsection{From-object based visibility}
 
-Our framework is based on the idea of sampling visibility by casting
+ Our framework is based on the idea of sampling visibility by casting
 casting rays through the scene and collecting their contributions. A
 visibility sample is computed by casting a ray from an object towards
@@ -304,5 +310,5 @@
 
 
-\section{Basic Randomized Sampling}
+\subsection{Basic Randomized Sampling}
 
 
@@ -319,5 +325,5 @@
 
 
-The described algorithm accounts for the irregular distribution of the
+ The described algorithm accounts for the irregular distribution of the
 objects: more samples are placed at locations containing more
 objects. Additionally every object is sampled many times depending on
@@ -327,14 +333,14 @@
 
 
-\section{Accounting for View Cell Distribution}
-
-The first modification to the basic algorithm accounts for irregular
-distribution of the viewcells. Such a case in common for example in
+\subsection{Accounting for View Cell Distribution}
+
+ 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
 the city. The modification involves replacing the uniformly
 distributed ray direction by directions distributed according to the
-local view cell directional density. It means placing more samples at
-directions where more view cells are located. We select a random
+local view cell directional density. This means placing more samples at
+directions where more view cells are located: We select a random
 viecell which lies at the halfpace given by the surface normal at the
 chosen point. We pick a random point inside the view cell and cast a
@@ -342,16 +348,16 @@
 
 
-\section{Accounting for Visibility Events}
+\subsection{Accounting for Visibility Events}
 
  Visibility events correspond to appearance and disapearance of
  objects with respect to a moving view point. In polygonal scenes the
- events defined by event surfaces defined by three distinct scene
- edges. Depending on the edge configuration we distinguish between
- vertex-edge events (VE) and tripple edge (EEE) events. The VE surfaces
- are planar planes whereas the EEE are in general quadratic surfaces.
+events defined by event surfaces defined by three distinct scene
+edges. Depending on the edge configuration we distinguish between
+vertex-edge events (VE) and tripple edge (EEE) events. The VE surfaces
+are planar planes whereas the EEE are in general quadratic surfaces.
 
  To account for these event we explicitly place samples passing by the
- object edges which are directed to edges and/or vertices of other
- objects.
-
-
+object edges which are directed to edges and/or vertices of other
+objects.
+
+
