source: trunk/VUT/doc/SciReport/introduction.tex @ 255

\chapter{Overview of 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
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.



%% summarize the state of the art
%% visibility algorithms and their relation to the proposed taxonomy of
%% visibility problems. The second part of the survey should serve as a
%% catalogue of visibility algorithms that is indexed by the proposed
%% taxonomy of visibility problems.



\subsection{Problem domain}
\label{sec:prob_domain}

 Computer graphics deals with visibility problems in the context of
2D, \m25d, or 3D scenes. The actual problem domain is given by
restricting the set of rays for which visibility should be
determined.

Below we list common problem domains used and the corresponding domain
restrictions:

\begin{enumerate}
\item
  {\em visibility along a line}
  \begin{enumerate}
  \item line
  \item ray (origin + direction)
  \end{enumerate}
  \newpage
\item
  {\em visibility from a point} ({\em from-point visibility})
  \begin{enumerate}
  \item point
  \item point + restricted set of rays
    \begin{enumerate}
    \item point + raster image (discrete form)
    \item point + beam (continuous form)
    \end{enumerate}
  \end{enumerate}

  
\item
  {\em visibility from a line segment} ({\em from-segment visibility})
  \begin{enumerate}
  \item line segment
  \item line segment + restricted set of rays
  \end{enumerate}
  
\item
  {\em visibility from a polygon} ({\em from-polygon visibility})
  \begin{enumerate}
  \item polygon
  \item polygon + restricted set of rays
  \end{enumerate}
  
\item
  {\em visibility from a region} ({\em from-region visibility})
  \begin{enumerate}
    \item region
    \item region + restricted set of rays
  \end{enumerate}

\item
  {\em global visibility}
  \begin{enumerate}
    \item no further input (all rays in the scene)
    \item restricted set of rays
  \end{enumerate}
\end{enumerate}
  
 The domain restrictions can be given independently of the dimension
of the scene, but the impact of the restrictions differs depending on
the scene dimension. For example, visibility from a polygon is
equivalent to visibility from a (polygonal) region in 2D, but not in
3D.

%*****************************************************************************

\section{Dimension of the problem-relevant line set}

 The six domains of visibility problems stated in
Section~\ref{sec:prob_domain} can be characterized by the {\em
problem-relevant line set} denoted ${\cal L}_R$. We give a
classification of visibility problems according to the dimension of
the problem-relevant line set. We discuss why this classification is
important for understanding the nature of the given visibility problem
and for identifying its relation to other problems.


 For the following discussion we assume that a line in {\em primal
space} can be mapped to a point in {\em line space}. For purposes of
the classification we define the line space as a vector space where a
point corresponds to a line in the primal space\footnote{A classical
mathematical definition says: Line space is a direct product of two
Hilbert spaces~\cite{Weisstein:1999:CCE}. However, this definition
differs from the common understanding of line space in computer
graphics~\cite{Durand99-phd}}.



\subsection{Parametrization of lines in 2D}

 There are two independent parameters that specify a 2D line and thus
the corresponding set of lines is two-dimensional. There is a natural
duality between lines and points in 2D. For example a line expressed
as: $l:y=ax+c$ is dual to a point $p=(-c,a)$. This particular duality
cannot handle vertical lines. See Figure~\ref{fig:duality2d} for an
example of other dual mappings in the plane.  To avoid the singularity
in the mapping, a line $l:ax+by+c=0$ can be represented as a point
$p_l=(a,b,c)$ in 2D projective space ${\cal
P}^2$~\cite{Stolfi:1991:OPG}. Multiplying $p_l$ by a non-zero scalar
we obtain a vector that represents the same line $l$. More details
about this singularity-free mapping will be discussed in
Chapter~\ref{chap:vfr2d}.


\begin{figure}[!htb]
\centerline{
\includegraphics[width=0.9\textwidth,draft=\DRAFTFIGS]{figs/duality2d}}
\caption{Duality between points and lines in 2D.}
\label{fig:duality2d}
\end{figure}





 To sum up: In 2D there are two degrees of freedom in description of a
line and the corresponding line space is two-dimensional. The
problem-relevant line set ${\cal L}_R$ then forms a $k$-dimensional
subset of ${\cal P}^2$, where $0\leq k \leq 2$. An illustration of the
concept of the problem-relevant line set is depicted in
Figure~\ref{fig:classes}.


\begin{figure}[htb]
\centerline{
\includegraphics[width=0.8\textwidth,draft=\DRAFTFIGS]{figs/classes}}
\caption{The problem-relevant set of lines in 2D. The ${\cal L}_R$ for
visibility along a line is formed by a single point that is a mapping
of the given line. The ${\cal L}_R$ for visibility from a point $p$ is
formed by points lying on a line. This line is a dual mapping of the
point $p$. ${\cal L}_R$ for visibility from a line segment is formed
by a 2D region bounded by dual mappings of endpoints of the given
segment.}
\label{fig:classes}
\end{figure}


\subsection{Parametrization of lines in 3D}


Lines in 3D form a four-parametric space~\cite{p-rsls-97}. A line
intersecting a given scene can be described by two points on a sphere
enclosing the scene. Since the surface of the sphere is a two
parametric space, we need four parameters to describe the line.

 The {\em two plane parametrization} of 3D lines describes a line by
points of intersection with the given two
planes~\cite{Gu:1997:PGT}. This parametrization exhibits a singularity
since it cannot describe lines parallel to these planes. See
Figure~\ref{fig:3dlines} for illustrations of the spherical and the
two plane parameterizations.


\begin{figure}[htb]
\centerline{
\includegraphics[width=0.78\textwidth,draft=\DRAFTFIGS]{figs/3dlines}}
\caption{Parametrization of lines in 3D. (left) A line can be
  described by two points on a sphere enclosing the scene. (right) The
  two plane parametrization describes a line by point of intersection
  with two given planes.}
\label{fig:3dlines}
\end{figure}

 Another common parametrization of 3D lines are the {\em \plucker
coordinates}. \plucker coordinates of an oriented 3D line are a six
tuple that can be understood as a point in 5D oriented projective
space~\cite{Stolfi:1991:OPG}. There are six coordinates in \plucker
representation of a line although we know that the ${\cal L}_R$ is
four-dimensional. This can be explained as follows:

\begin{itemize}
  \item Firstly, \plucker coordinates are {\em homogeneous
    coordinates} of a 5D point. By multiplication of the coordinates
    by any positive scalar we get a mapping of the same line.
  \item Secondly, only 4D subset of the 5D oriented projective space
  corresponds to real lines. This subset is a 4D ruled quadric called
  the {\em \plucker quadric} or the {\em Grassman
  manifold}~\cite{Stolfi:1991:OPG,Pu98-DSGIV}.
\end{itemize}

 Although the \plucker coordinates need more coefficients they have no
singularity and preserve some linearities: lines intersecting a set of 
lines in 3D correspond to an intersection of 5D hyperplanes. More details
on \plucker coordinates will be discussed in
Chapters~\ref{chap:vfr25d} and~\ref{chap:vfr3d} where they are used to
solve the from-region visibility problem.

  To sum up: In 3D there are four degrees of freedom in the
description of a line and thus the corresponding line space is
four-dimensional. Fixing certain line parameters (e.g. direction) the
problem-relevant line set, denoted ${\cal L}_R$, forms a
$k$-dimensional subset of ${\cal P}^4$, where $0\leq k \leq 4$.


\subsection{Visibility along a line}

 The simplest visibility problems deal with visibility along a single
line. The problem-relevant line set is zero-dimensional, i.e. it is
fully specified by the given line. A typical example of a visibility
along a line problem is {\em ray shooting}.

 A similar problem to ray shooting is the {\em point-to-point}
visibility.  The  point-to-point visibility determines whether the
line segment between two points is occluded, i.e. it has an
intersection with an opaque object in the scene. Point-to-point
visibility provides a visibility classification (answer 1a), whereas
ray shooting determines a visible object (answer 2a) and/or a point of
intersection (answer 3a). Note that the {\em point-to-point}
visibility can be solved easily by means of ray shooting. Another
constructive visibility along a line problem is determining the {\em
maximal free line segments} on a given line. See Figure~\ref{fig:val}
for an illustration of typical visibility along a line problems.

\begin{figure}[htb]
\centerline{
\includegraphics[width=0.85\textwidth,draft=\DRAFTFIGS]{figs/val}}
\caption{Visibility along a line. (left) Ray shooting. (center) Point-to-point visibility. (right) Maximal free line segments between two points.}
\label{fig:val}
\end{figure}


\subsection{Visibility from a point}

 Lines intersecting a point in 3D can be described  by two
parameters. For example the lines can be expressed by an intersection
with a unit sphere centered at the given point. The most common
parametrization describes a line by a point of intersection with a
given viewport. Note that this parametrization accounts only for a
subset of lines that intersect the viewport (see Figure~\ref{fig:vfp}).

\begin{figure}[htb]
\centerline{
\includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/vfp}}
\caption{Visibility from a point. Lines intersecting a point can be described by a
  point of intersection with the given viewport.}
\label{fig:vfp}
\end{figure}

 In 3D the problem-relevant line set ${\cal L}_R$ is a 2D subset of
the 4D line space. In 2D the ${\cal L}_R$ is a 1D subset of the 2D
line space. The typical visibility from a point problem is the visible
surface determination. Due to its importance the visible surface
determination is covered by the majority of existing visibility
algorithms. Other visibility from a point problem is the construction
of the {\em visibility map} or the {\em point-to-region visibility}
that classifies a region as visible, invisible, or partially visible
with respect to the given point.


\subsection{Visibility from a line segment}

 Lines intersecting a line segment in 3D can be described by three
parameters. One parameter fixes the intersection of the line with the
segment the other two express the direction of the line. The
problem-relevant line set ${\cal L}_R$ is three-dimensional and it can
be understood as a 2D cross section of ${\cal L}_R$  swept according
to the translation on the given line segment (see
Figure~\ref{fig:vls}).


\begin{figure}[htb]
\centerline{
\includegraphics[width=0.8\textwidth,draft=\DRAFTFIGS]{figs/vls}}
\caption{Visibility from a line segment. (left) Line segment, a
  spherical object $O$, and its projections $O^*_0$, $O^*_{0.5}$, $O^*_{1}$
  with respect to the three points on the line segment. (right)
  A possible parametrization of lines that stacks up 2D planes.
  Each plane corresponds to mappings of lines intersecting a given
  point on the line segment.}
\label{fig:vls}
\end{figure}

In 2D lines intersecting a line segment form a two-dimensional
problem-relevant line set. Thus for the 2D case the ${\cal L}_R$ is a
two-dimensional subset of 2D line space.


\subsection{Visibility from a region}

 Visibility from a region (or from-region visibility) involves the
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
visibility from a region in 2D is equivalent to visibility from a line
segment in 2D.

 A typical visibility from a region problem is the problem of {\em
region-to-region} visibility that aims to determine if the two given
regions in the scene are visible, invisible, or partially visible (see
Figure~\ref{fig:vfr}). Another visibility from region problem is the
computation of a {\em potentially visible set} (PVS) with respect to a
given view cell. The PVS consists of a set of objects that are
potentially visible from any point inside the view cell. Further
visibility from a region problems include computing form factors
between two polygons, soft shadow algorithms or discontinuity meshing.


\begin{figure}[htb]
\centerline{
\includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/vfr}}
\caption{Visibility from a region --- an example of the region-to-region
  visibility. Two regions and two occluders $A$, $B$
  in a 2D scene.  In line space the region-to-region visibility can be
  solved by subtracting the sets of lines $A^*$ and $B^*$
  intersecting objects $A$ and $B$ from the lines intersecting both
  regions.}
\label{fig:vfr}
\end{figure}


\subsection{Global visibility}

 According to the classification the global visibility problems can be
seen as an extension of the from-region visibility problems. The
dimension of the problem-relevant line set is the same ($k=2$ for 2D
and $k=4$ for 3D scenes). Nevertheless, the global visibility problems
typically deal with much larger set of rays, i.e.  all rays that
penetrate the scene. Additionally, there is no given set of reference
points from which visibility is studied and hence there is no given
priority ordering of objects along each particular line from ${\cal
L}_R$. Therefore an additional parameter must be used to describe
visibility (visible object) along each ray.


\subsection{Summary}

 The classification of visibility problems according to the dimension
of the problem-relevant line set is summarized in
Table~\ref{table:classification3D}.  This classification provides
means for understanding how difficult it is to compute, describe, and
maintain visibility for a particular class of problems. For example a
data structure representing the visible or occluded parts of the scene
for the visibility from a point problem needs to partition a 2D ${\cal
L}_R$ into visible and occluded sets of lines. This observation
conforms with the traditional visible surface algorithms -- they
partition a 2D viewport into empty/nonempty regions and associate each
nonempty regions (pixels) with a visible object. In this case the
viewport represents the ${\cal L}_R$ as each point of the viewport
corresponds to a line through that point. To analytically describe
visibility from a region a subdivision of 4D ${\cal L}_R$ should be
performed. This is much more difficult than the 2D
subdivision. Moreover the description of visibility from a region
involves non-linear subdivisions of both primal space and line space
even for polygonal scenes~\cite{Teller:1992:CAA,Durand99-phd}.

\begin{table*}[htb]
\begin{small}
\begin{center}
\begin{tabular}{|l|c|l|}
\hline
\multicolumn{3}{|c|}{2D} \\
\hline
\mc{domain} & $d({\cal L}_R)$ & \mc{problems} \\
\hline
\hline
\begin{tabular}{l}visibility along a line\end{tabular}         & 0 &  \begin{tabular}{l}ray shooting, point-to-point visibility\end{tabular}\\
\hline
\begin{tabular}{l}visibility from a point\end{tabular}         & 1 &  \begin{tabular}{l}view around a point, point-to-region visibility\end{tabular}\\
\hline
\begin{tabular}{l} visibility from a line segment \\ visibility from region \\ global visibility \end{tabular}
   & 2 & \begin{tabular}{l} region-to-region visibility, PVS \end{tabular}\\
\hline
\hline
\multicolumn{3}{|c|}{3D} \\
\hline
\mc{domain} & $d({\cal L}_R)$ & \mc{problems} \\
\hline
\hline
\begin{tabular}{l}visibility along a line\end{tabular}  & 0 & \begin{tabular}{l} ray shooting, point-to-point visibility \end{tabular}\\
\hline
\begin{tabular}{l}from point in a surface\end{tabular}  & 1 & \begin{tabular}{l} see visibility from point in 2D \end{tabular}\\
\hline
\begin{tabular}{l}visibility from a point\end{tabular}  & 2 & \begin{tabular}{l} visible (hidden) surfaces, point-to-region visibility,\\
                                      visibility map, hard shadows
                               \end{tabular} \\
\hline
\begin{tabular}{l}visibility from a line segment\end{tabular} & 3 & \begin{tabular}{l} segment-to-region visibility (rare) \end{tabular}\\
\hline
\begin{tabular}{l}visibility from a region\\global visibility\end{tabular}       & 4 & \begin{tabular}{l} region-region visibility, PVS, aspect graph,\\
                                            soft shadows, discontinuity meshing
                                     \end{tabular} \\

\hline  
\end{tabular}
\end{center}
\end{small}
\caption{Classification of visibility problems in 2D and 3D according
to the dimension of the problem-relevant line set.}
\label{table:classification3D}
\end{table*}





\section{Classification of visibility algorithms}


The taxonomy of visibility problems groups similar visibility problems
in the same class.  A visibility problem can be solved by means of
various visibility algorithms. A visibility algorithm poses further
restrictions on the input and output data. These restrictions can be
seen as a more precise definition of the visibility problem that is
solved by the algorithm.

 Above we classified visibility problems according to the problem
domain and the desired answers. In this section we provide a
classification of visibility algorithms according to other
important criteria characterizing a particular visibility algorithm.


\subsection{Scene restrictions}
\label{sec:scene_restrictions}

Visibility algorithms can be classified according to the restrictions
they pose on the scene description.  The type of the scene description
influences the difficulty of solving the given problem: it is simpler
to implement an algorithm computing a visibility map for scenes
consisting of triangles than for scenes with NURBS surfaces. We list
common restrictions on the scene primitives suitable for visibility
computations:


\begin{itemize}
\item
  triangles, convex polygons, concave polygons,
  
\item
  volumetric data,

\item
  points,

\item
  general parametric, implicit, or procedural surfaces.

\end{itemize}

Some attributes of scenes objects further increase the complexity of the visibility computation:

\begin{itemize}

\item
  transparent objects,

\item
  dynamic objects.

\end{itemize}

The majority of analytic visibility algorithms deals with static
polygonal scenes without transparency. The polygons are often
subdivided into triangles for easier manipulation and representation.

\subsection{Accuracy}
\label{sec:accuracy}

 Visibility algorithms can be classified according to the accuracy of
the result as:

\begin{itemize}
\item exact,
\item conservative,
\item aggressive,
\item approximate.
\end{itemize}


 An exact algorithm provides an exact analytic result for the given
problem (in practice however this result is typically influenced by
the finite precision of the floating point arithmetics). A
conservative algorithm overestimates visibility, i.e. it never
misses any visible object, surface or point. An aggressive algorithm
always underestimates visibility, i.e. it never reports an invisible
object, surface or point as visible.  An approximate algorithm
provides only an approximation of the result, i.e. it can overestimate
visibility for one input and underestimate visibility for another
input.

 The classification according to the accuracy is best illustrated on
computing PVS: an exact algorithm computes an exact PVS. A
conservative algorithm computes a superset of the exact PVS.  An
aggressive algorithm determines a subset of the exact PVS.  An
approximate algorithm computes an approximation to the exact PVS that
is neither its subset or its superset for all possible inputs.


\subsection{Solution space}

\label{sec:solspace}

 The solution space is the domain in which the algorithm determines
the desired result. Note that the solution space does not need to
match the domain of the result.

The algorithms can be classified as:

\begin{itemize}
  \item discrete,
  \item continuous,
  \item hybrid.
\end{itemize}

 A discrete algorithm solves the problem using a discrete solution
space; the solution is typically an approximation of the result. A
continuous algorithm works in a continuous domain and often computes an
analytic solution to the given problem. A hybrid algorithm uses both
the discrete and the continuous solution space.

 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
z-buffer~\cite{Catmull:1975:CDC} is a common example of a discrete
algorithm. The Weiler-Atherton algorithm~\cite{Weiler:1977:HSR} is an
example of a continuous one. A hybrid solution space is used by
scan-line algorithms that solve the problem in discrete steps
(scan-lines) and for each step they provide a continuous solution
(spans).

Further classification reflects the semantics of the solution
space. According to this criteria we can classify the algorithms as:

\begin{itemize}
  \item primal space (object space),
  \item line space,
    \begin{itemize}
    \item image space,
    \item general,
    \end{itemize}
  \item hybrid.
\end{itemize}

 A primal space algorithm solves the problem by studying the
visibility between objects without a transformation to a different
solution space. A line space algorithm studies visibility using a
transformation of the problem to line space. Image space algorithms
can be seen as an important subclass of line space algorithms for
solving visibility from a point problems in 3D. These algorithms cover
all visible surface algorithms and many visibility culling
algorithms. They solve visibility in a given image plane that
represents the problem-relevant line set ${\cal L}_R$ --- each ray
originating at the viewpoint corresponds to a point in the image plane.

 The described classification differs from the sometimes mentioned
understanding of image space and object space algorithms that
incorrectly considers all image space algorithms discrete and all
object space algorithms continuous.


%*****************************************************************************

\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:

\begin{itemize}
\item Visibility from a point in 3D $d({\cal L}_R)=2$.
\item Global visibility in 3D $d({\cal L}_R)=4$.
\item Visibility from a region in 3D, $d({\cal L}_R)=4$.
\end{itemize}

 This chapter discussed several important criteria for the
classification of visibility algorithms. This classification can be
seen as a finer structuring of the taxonomy of visibility problems. We
discussed important steps in the design of a visibility algorithm that
should also assist in understanding the quality of a visibility
algorithm. According to the classification the tools address
algorithms with the following properties:

\begin{itemize}
\item Domain:
  \begin{itemize}
  \item viewpoint (Chapter~\ref{chap:online}),
  \item polygon or polyhedron (Chapters~\ref{chap:sampling,chap:mutual})
  \end{itemize}
\item Scene restrictions (occluders):
  \begin{itemize}
  \item meshes consisting of convex polygons
  \end{itemize}
\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}),
  \end{itemize}
\item Output:
  \begin{itemize}
  \item Visibility classification of objects or hierarchy nodes
  \item PVS
  \end{itemize}
\item Accuracy:
  \begin{itemize}
  \item conservative
  \item exact
  \item aggresive
  \end{itemize}
  \item Solution space:
  \begin{itemize}
  \item discrete (Chapters~\ref{chap:online},~\ref{chap:sampling})
  \item continuous, line space / primal space (Chapter~\ref{chap:rot25d})
  \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 Use of coherence of visibility:
    \begin{itemize}
    \item spatial coherence (all methods)
    \item temporal coherence (Chapter~\ref{chap:online})
    \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}
    
  \end{itemize}