\chapter{Analysis of Visibility in Polygonal Scenes}

\label{chap:analysis}

This chapter provides analysis of the visibility in polygonal scenes,
which are the input for all developed algorithms. 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. Visibility in 3D is described using \plucker 

\section{Analysis of visibility in 2D}

\label{LINE_SPACE}

The proposed visibility algorithm uses a mapping of oriented 2D lines to
points in 2D oriented projective space --- {\em line space}. Such a
mapping allows to handle sets of lines much easier than in the primal
space~\cite{pv-vc-93}.

 We use a 2D projection of Pl\"ucker
coordinates~\cite{Stolfi:1991:OPG} to parametrize lines in the plane.
This mapping corresponds to an ``oriented form'' of the duality
between points and lines in 2D.  Let $l$ be an oriented line in
${\mathcal R}^2$ and let $u=(u_x, u_y)$ and $v=(v_x, v_y)$ be two
distinct points lying on $l$. Line $l$ oriented from $u$ to $v$ can be
described by the following matrix:

$$
M_l=\left(
\begin{array}{cccc}
u_x & u_y & 1 \\
v_x & v_y & 1  
\end{array}
\right)
$$

Pl\"ucker coordinates $l^*$ of $l$ are minors of $M_l$:

$$
l^* = (l^*_x, l^*_y, l^*_z) = (u_y - v_y, v_x - u_x, u_x v_y - u_y  v_x ).
$$

$l^*$ can be interpreted as homogeneous coordinates of a point in 2D
{\em oriented projective space} ${\cal P}^2$. Two oriented lines are
equal if and only if their Pl\"ucker coordinates differ only by a
positive scale factor. $l^*$ also corresponds to coefficients of the
implicit equation of a line: $l'$ expressed as $l': ax + by + c= 0$
induces two oriented lines $l^*_1$, $l^*_2$, with Pl\"ucker
coordinates $l^*_1 = (a, b, c)$ and $l^*_2 = -(a,b,c)$.  The \plucker
coordinates of 2D lines defined in this chapter are a simplified form
of the \plucker coordinates for 3D lines, which will be discussed
below in this chapter: \plucker coordinates of a 2D line correspond
to the \plucker coordinates of a 3D line embedded in the $z = 0$ plane
after removal of redundant coordinates (equal to 0) and permutation of
the remaining ones (including some sign changes).


 Homogeneous coordinates are often normalized, e.g. $l^*_N = (a/b, 1,
c/b)$. The normalization introduces a singularity --- in our example
vertical lines map to points at infinity. To avoid singularities we
treat ${\cal P}^2$ as 3D linear space and call it {\em line space}
denoted ${\mathcal L}$. Consequently, $l^*$ represents a halfline in
${\mathcal L}$. All points on halfline $l^*$ represent the same
oriented line $l$.

 To sum up: an oriented line in 2D is mapped to a halfline beginning
at the origin in 3D. An example of the concept is depicted in
Figures~\ref{lines1}-(a) and ~\ref{lines1}-(b). Further in this
chapter we will mostly use ``projected'' 2D illustrations of line
space (such as in Figure~\ref{lines1}-(c)). We will still talk about
planes and halflines, but they will be depicted as lines and points,
respectively, for the sake of clarity of the presentation.


\subsection{Lines passing through a point}

 A {\em pencil of oriented lines} passing through a point $p = (p_x,
p_y)  \in {\mathcal R}^2$ maps to an oriented plane $p^*$ in line
space that is expressed as:
$$
p^* = \{(x,y,z) | (x,y,z) \in {\mathcal L}, p_x x + p_y y + z = 0\}.
$$

This plane subdivides ${\mathcal L}$ in two open halfspaces $p^*_+$
and $p^*_-$. Points in $p^*_-$ correspond to oriented lines passing
clockwise around $p$ (see Figure~\ref{lines1}).  Points in $p^*_+$
correspond to oriented lines passing counterclockwise around $p$
(these relations depend on the orientation of the primal space). We
denote $-p^*$ an oriented plane opposite to $p^*$ that can be
expressed as:
$$
-p^* = \{(x,y,z) | (x,y,z) \in {\mathcal L}, -p_x x - p_y y - z = 0\}.
$$


\begin{figure*}[tb]
\rule{0pt}{0pt}\hfill
\includegraphics[width=1.0\textwidth,draft=\DRAFTFIGS]{figs/lines1}
\hfill\rule{0pt}{0pt}
\centerline{\small \hspace{0.01\textwidth}{\bf (a)}\hspace{0.3\textwidth} {\bf (b)} \hspace{0.3\textwidth} {\bf (c)}}
\vspace{-1.5em}
\caption{
{\bf (a)} Four oriented lines in primal space.
{\bf (b)} Mappings of the four lines and point p.
Lines intersecting p map to plane $p^*$.
Lines passing clockwise (counterclockwise) around $p$, map to
$p^*_-$ ($p^*_+$).
{\bf (c)} The situation after projection to a plane perpendicular to $p^*$.  }
\label{lines1}
\end{figure*}

\subsection{Lines passing through a line segment}

 Oriented lines passing through a line segment can be decomposed into
two sets depending on their orientation.  Consider a supporting line
$l_S$ of a line segment $S$, that partitions the plane in open
halfspaces $S^+$ and $S^-$. Denote $a$ and $b$ the two endpoints of
$S$ and $a^*$ and $b^*$ their mappings to ${\mathcal L}$. Lines that
intersect $S$ and ``come from'' $S^-$ can be expressed in line space
as an intersection of halfspaces $a^*_+$ and $b^*_-$.  The opposite
oriented lines intersecting $S$ are expressed as $a^*_- \cap b^*_+$
(see Figure~\ref{lines2}-(a,b)).

%\begin{minipage}{\textwidth}

\begin{figure}[htb]
\rule{0pt}{0pt}\hfill
\includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/lines2}
\hfill\rule{0pt}{0pt}
\centerline{\small
\hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
}
\vspace{-1.5em}
\caption{ {\bf (a)} A line segment $S$ and three oriented lines that
intersect $S$.  {\bf (b)} The situation in line space: the projection of two
wedges corresponding to lines intersecting $S$. Mappings of supporting
line $l_S$ of $S$ are two halflines that project to point
$l_S^*$. Line $k$ intersects point $b$ and therefore maps to plane
$b^*$. Lines $m$ and $n$ map to the wedge corresponding to their
orientation.  }
\label{lines2}
\end{figure}




\subsection{Lines passing through two line segments}

\label{sec:blocker_polygon}

Consider two disjoint line segments such as those depicted in
Figure~\ref{lines3}-(a). The set of lines passing through the two line
segments can be described as an intersection of four halfspaces in
line space. The four halfspaces correspond to mappings of endpoints of
the two line segments.  Since the halfspaces pass through the origin
of ${\mathcal L}$, their intersection is a pyramid with the apex at
the origin. The boundary halflines of the pyramid correspond to
mappings of the four {\em extremal lines} induced by the two
segments. Denote ${\mathcal P}(S, O)$ a line space pyramid
corresponding to oriented lines intersecting line segments $S$ and $O$
in this order.  We represent the pyramid by a {\em blocker polygon}
$B(S, O)$ (see Figure~\ref{lines3}-(b)). Since $B(S, O)$ only
represents the pyramid ${\mathcal P}(S, O)$, it need not be a planar
polygon, i.e. its vertices may lay anywhere on the boundary halflines
of ${\mathcal P}(S, O)$.  We normalize the vertex coordinates: they
correspond to an intersection of the boundary halfline of ${\mathcal
P}(S, O)$ and the unit sphere centered at the origin of ${\mathcal L}$.

\begin{figure}[htb]
\hfill\rule{0pt}{0pt}
\includegraphics[width=0.7\textwidth,draft=\DRAFTFIGS]{figs/lines3}
\hfill\rule{0pt}{0pt}
\centerline{\small
\hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
}
\vspace{-1.5em}
\caption{ {\bf (a)} Two line segments and corresponding four extremal lines
oriented from $S$ to $O$. Separating lines $ad$ and $bc$ bound region
of partial visibility of $S$ behind $O$ (penumbra). Supporting lines
$ac$ and $bd$ bound region where $S$ is invisible (umbra). {\bf (b)}
Blocker polygon $B(S,O)$ representing pyramid ${\mathcal
P}(S,O)$.
}
\label{lines3}
\end{figure}


In Figure~\ref{lines4}-(a), the supporting line of $cd$ intersects $ab$
at point $x$.  The set of rays passing through $ab$ and $cd$ can be
decomposed to rays passing through $ax$ and $cd$, and through $xb$
and $cd$. Rays through $ax$ and $cd$ map to a pyramid that is
described by intersection of only three halfspaces induced by mappings
of $a$, $x$ and $d$. Rays through $xb$ and $cd$ can be
described similarly. The configuration in line space is depicted in
Figure~\ref{lines4}-(b).

\begin{figure}[htb]
\rule{0pt}{0pt}\hfill
\includegraphics[width=0.7\textwidth,draft=\DRAFTFIGS]{figs/lines4}
\hfill\rule{0pt}{0pt}
\centerline{\small
\hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
}
\vspace{-1.5em}
\caption{ {\bf (a)} Degenerate configuration of line segments: the supporting
line of $cd$ intersects $ab$ at point $x$. There are five extremal
lines. Note, that there is no umbra region. {\bf (b)} In line space the
configuration yields two pyramids sharing a boundary that is a
mapping of the oriented line $cd$. 
}
\label{lines4}
\end{figure}

\subsection{Lines passing through a set of line segments}

 Consider a set of $n+1$ line segments. We call one line segment the
{\em source} (denoted by $S$) and the other $n$ segments we call
occluders (denoted by $O_k$, $1 \leq k \leq n$).  Further in the
chapter we will use the term {\em ray} as a representative of an
oriented line that is oriented from the source ``towards'' the
occluders.

Assume that we can process all occluders in a strict front-to-back
order with respect to the given source. We have already processed $k$
occluders and we continue by processing $O_{k+1}$.  $O_{k+1}$ can be
visible through rays that correspond to the pyramid ${\mathcal P}(S,
O_{k+1})$. Nevertheless some of these rays can be blocked by 
combination of already processed occluders $O_x$ ($1\leq x \leq k$).
To determine if $O_{k+1}$ is visible we subtract all ${\mathcal
P}(S,O_x)$ from ${\mathcal P}(S,O_{k+1})$:

$$
{\mathcal V}(S,O_{k+1}) = {\mathcal P}(S,O_{k+1})\ - \bigcup_{1 \leq x \leq k} {\mathcal P}(S,O_x)
$$

${\mathcal V}(S, O_{k+1})$ is a set pyramids representing rays through
which $O_{k+1}$ is visible from $S$.  In turn, all rays corresponding
to ${\mathcal V}(S,O_{k+1})$ are blocked behind $O_{k+1}$.  If
${\mathcal V}(S, O_{k+1})$ is an empty set, occluder $O_{k+1}$ is
invisible. This suggest incremental construction of an arrangement of
pyramids ${\mathcal A}_k$ that corresponds to rays blocked by the
$k$ processed occluders.  We determine ${\mathcal V}(S,O_{k+1})$ and
${\mathcal A}_{k+1}$ (${\mathcal A}_0$ is empty):

$$
{\mathcal V}(S,O_{k+1}) = {\mathcal P}(S,O_{k+1}) \ - \ {\mathcal A}_k,
$$
$$
{\mathcal A}_{k+1} = {\mathcal A}_k \cup {\mathcal P}(S,O_{k+1}) =
{\mathcal A}_k \ \cup \ {\mathcal V}(S,O_{k+1}).
$$

 Figures~\ref{lines5}-(a,b) depict a projection of an arrangement
${\mathcal A}_3$ of a source and three occluders. Note that the
shorter the source line segment the narrower ($s^*_a$ and $s^*_b$ get
closer) are the pyramids ${\mathcal P}(S,O_k)$.




\begin{figure}[htb]
\rule{0pt}{0pt}\hfill
\includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/rot2new}
\hfill\rule{0pt}{0pt}
\centerline{\small
\hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
}
\vspace{-1.5em}
\caption{  {\bf (a)} The source line segment $S$ and three
occluders. $Q_{1-3}$ denote unoccluded funnels.  {\bf (b)} The
line space subdivision. For each cell, the corresponding occluder-sequence
is depicted.  Note the cells $Q^*_1$, $Q^*_2$ and $Q^*_3$
corresponding to unoccluded funnels.}
\label{lines5}
\end{figure}

Recall that the pyramid ${\mathcal P}(S,O_k)$ is represented by
blocker polygon $B(S,O_k)$. The construction of the arrangement
${\mathcal A}_k$ resembles the from-point visibility problem, more
specifically the hidden surface removal applied on the blocker
polygons with respect to the origin of ${\mathcal L}$. The difference
is that the depth information is irrelevant in line space. The
priority of blocker polygons is either completely determined by the
processing order of occluders or their depth must be compared in
primal space. This observation is supported by the classification of
visibility problems presented in
Chapter~\ref{chap:introduction}. Visibility from point in 3D and visibility
from region in 2D induce a two-dimensional problem-relevant line
set. This suggests the possibility of mapping one problem to another.

In the next section we show how the arrangement ${\mathcal A}_k$ can
be maintained consistently and efficiently using the occlusion tree.



\section{Pl\"ucker coordinates of lines in 3D}

\label{sec:plucker}


 We will use a mapping that describes an oriented 3D line as a point
in a projective 5D space~\cite{Boissonnat98} by means of \plucker
coordinates~\cite{Teller92phd,p-rsls-97,yn-sbgtc-97,Pu98-DSGIV}. \plucker
coordinates allow to represent sets of lines using 5D polyhedra and to
compute visibility by means of polyhedra set operations in 5D.

 A line in 3D can be described by homogeneous coordinates of two
distinct points on that line. Let $l$ be a line in ${\cal R}^3$ and
let $\mbi{u}=(u_x, u_y, u_z, u_w)$ and $\mbi{v}=(v_x,v_y,v_z, v_w)$ be
two distinct points in homogeneous coordinates lying on $l$. A line
$l$ oriented from $\mbi{u}$ to $\mbi{v}$ can be described by the following matrix:

\begin{equation}
l=\left(
\begin{array}{cccc}
u_{x} & u_{y} & u_{z} & u_{w} \\
v_{x} & v_{y} & v_{z} & v_{w} 
\end{array}
\right)
\label{coord_cara}
\end{equation}

Minors of the matrix correspond to components of the {\em \plucker
coordinates} $\bpi_l$ of line $l$:

\begin{equation}
\begin{array}{ll}
\bpi_l & =  (\pi_{l0}, \pi_{l1}, \pi_{l2}, \pi_{l3}, \pi_{l4}, \pi_{l5}) = \\
       & =  (\xi_{wx},\xi_{wy},\xi_{wz},\xi_{yz},\xi_{zx},\xi_{xy}),
\end{array}
\label{eq:plucker_coords_def}
\end{equation}

where

\begin{equation}
\xi_{rs} = det\left(
\begin{array}{cc}
u_{r} & u_{s} \\
v_{r} & v_{s}
\end{array}
\right).
\end{equation}

Substituting $u_w=1$ and $v_w=1$ into Eq.~\ref{eq:plucker_coords_def}
enumerates to:

\begin{equation}
\begin{array}{l}
\pi_{l0} = v_x - u_x\\
\pi_{l1} = v_y - u_y\\
\pi_{l2} = v_z - u_z\\
\pi_{l3} = u_{y}v_{z} - u_{z}v_{y}\\
\pi_{l4} = u_{z}v_{x} - u_{x}v_{z}\\
\pi_{l5} = u_{x}v_{y} - u_{y}v_{x}
\end{array}
\label{eq:plucker_coords}
\end{equation}

The \plucker coordinates $\bpi_l$ can be seen as homogeneous
coordinates of a point in a projective five-dimensional space ${\cal
P}^5$. We call this point a {\em \plucker point} $\ppoint_l$ of
$l$. For a given oriented line $l$ the \plucker coordinates $\bpi_l$
are unique and they do not depend on the choice of points $p$ and $q$.
We will use the notation of a \plucker point $\ppoint_l$ in the case
when we want to stress that the corresponding \plucker coordinates
$\bpi_l$ are interpreted as a point in ${\cal P}^5$.

Using the projective duality the \plucker coordinates can be
interpreted as coefficients of a hyperplane. The {\em \plucker
coefficients} $\bomega_l$ of line $l$ are given as:


\begin{equation}
\begin{array}{ll}
\bomega_l
 & =  (\omega_{l0}, \omega_{l1}, \omega_{l2}, \omega_{l3}, \omega_{l4}, \omega_{l5}) = \\
 & =  (\xi_{yz},\xi_{zx},\xi_{xy},\xi_{wx},\xi_{wy},\xi_{wz})
\end{array}
\label{eq:plucker_coef_def}
\end{equation}

Substituting Eq.~\ref{eq:plucker_coords} into Eq.~\ref{eq:plucker_coef_def}
we get:

\begin{equation}
\begin{array}{l}
\omega_{l0} = \pi_{l3} \\
\omega_{l1} = \pi_{l4}\\
\omega_{l2} = \pi_{l5}\\
\omega_{l3} = \pi_{l0}\\
\omega_{l4} = \pi_{l1}\\
\omega_{l5} = \pi_{l2}
\end{array}
\label{eq:plucker_coef}
\end{equation}


 The \plucker coefficients $\bomega_l$ define a {\em \plucker
 hyperplane} $\pplane_l$. We will use the notation of a \plucker
 hyperplane $\pplane_l$ when we want to stress that the
 corresponding \plucker coefficients $\bomega_l$ are interpreted as a
 hyperplane in ${\cal P}^5$. In terms of \plucker points the \plucker
 hyperplane can be expressed as:
 
\begin{equation}
\label{hyperplane}
\begin{array}{l}
\pplane_l = \{\ppoint | \ppoint \in {\cal P}^5, \bomega_l \odot \bpi = 0\}
\end{array}
\end{equation} 

The \plucker hyperplane induces closed positive and negative halfspaces
given as:

\begin{equation}
\begin{array}{l}
\pplane^{+}_l = \{\ppoint | \ppoint \in {\cal P}^{5}, \bomega_l \odot \bpi \geq 0\} \\
\pplane^{-}_l = \{\ppoint | \ppoint \in {\cal P}^{5}, \bomega_l \odot \bpi \leq 0\} \\
\end{array}
\label{eq:def_halfspaces}
\end{equation} 

 These definitions of \plucker coordinates and coefficients follow the
``traditional'' convention~\cite{Pu98-DSGIV}. They differ from the
definitions used by Teller~\cite{Teller92phd} who used a permuted
order of the coordinates. The traditional convention provides an
elegant interpretation of \plucker coordinates that will be discussed
in Section~\ref{sec:plucker_interp}.

 If $a$ and $b$ are two directed lines, the relation $side(a,b)$ is
defined as an inner product $\bomega_a \odot \bpi_b$ or permuted inner
product $\bpi_a \times \bpi_b$:

\begin{equation}
\begin{array}{ll}
  side(a,b) & = \bomega_a \odot \bpi_b = \\
            & = \omega_{a0}\pi_{b0} + \omega_{a1}\pi_{b1} + \omega_{a2}\pi_{b2} +
  \omega_{a3}\pi_{b3} + \omega_{a4}\pi_{b4} + \omega_{a5}\pi_{b5} = \\
            & = \bpi_a \times \bpi_b = \\
            & = \pi_{a0}\pi_{b3} + \pi_{a1}\pi_{b4} + \pi_{a2}\pi_{b5} +
  \pi_{a3}\pi_{b0} + \pi_{a4}\pi_{b1} + \pi_{a5}\pi_{b2}
\end{array}
\label{eq:side}
\end{equation}


 This relation can be interpreted with the right-hand rule
(Figure~\ref{sidepict}). If the thumb of the right hand is directed
along line $a$, then:

\begin{itemize}
\item $side(a,b)> 0$,  if line $b$ is oriented in the direction of the fingers, 

\item $side(a,b) = 0$,  if lines $a$ and $b$ intersect or are parallel,

\item $side(a,b) < 0$, if line $b$ points against the direction of the fingers.
\end{itemize}

\begin{figure}[htb]
\centerline{
  \includegraphics[width=0.8\textwidth,draft=\DRAFTFIGS]{figs/pldual}}
\caption{The $side(a,b)$, interpreted as the right-hand rule.} 
\label{sidepict}
\end{figure}


\plucker coordinates have an important property: Although every
oriented line in ${\cal R}^3$ maps to a point in \plucker coordinates,
not every tuple of six real numbers corresponds to a real line. Only
the points $\ppoint \in {\cal P}^5$ \plucker coordinates of which
satisfy the condition

\begin{equation}
\bpi \odot \bpi = 0 \qquad \equiv \qquad \pi_{0}\pi_{3} + \pi_{1}\pi_{4} + \pi_{2}\pi_{5} = 0,
\label{eq:plucker_quadric}
\end{equation}

represent real lines in ${\cal R}^3$. All other points correspond to
lines which are said to be {\em imaginary}. The set of points in
${\cal P}^5$ satisfying Eq.~\ref{eq:plucker_quadric} forms a 4D
hyperboloid of one sheet called the {\em \plucker quadric}, also known
as the {\em Klein quadric} or the {\em Grassman manifold}
(see Figure~\ref{quadric}).


\begin{figure}[htb]
\medskip
\centerline{
  \includegraphics[width=0.65\textwidth,draft=\DRAFTFIGS]{figs/reallin}}
\caption{Real lines map on points on the Pl\"{u}cker quadric.} 
\label{quadric}
\end{figure}

The six \plucker coordinates of a real line are not
independent. Firstly, they describe an oriented projective space,
secondly, they must satisfy the
equation~\ref{eq:plucker_quadric}. Thus there are four degrees of
freedom in the description of a 3D line, which conforms with the
classification from Chapter~\ref{chap:introduction}.

 \plucker coordinates allow to detect an incidence of two lines by
computing an inner product of a homogeneous point (mapping of one
line) with a hyperplane (mapping of the other). Lines $l$ and $l'$
intersect or are parallel (i.e. meet at infinity) if and only if
$\ppoint_l \in \pplane_{l'}$, i.e. $side(l, l') = 0$. Note that according
to ~\ref{eq:plucker_quadric} any line always meets itself.


\subsection{Geometric interpretation of \plucker coordinates}
\label{sec:plucker_interp}

For a better understanding of \plucker coordinates it is natural to
ask how each individual \plucker coordinate is related to the geometry
of the corresponding line. The \plucker coordinates of a given line
can be divided to the {\em directional} and the {\em locational}
parts. The directional part encodes the direction of the line, the
locational part encodes the position of the line. Given \plucker
coordinates $\bpi_l$ of a line $l$ we can write:

\begin{equation}
\begin{array}{lll}
\mbi{d}_l & = (\pi_{l0}, \pi_{l1}, \pi_{l2}), \\
\mbi{l}_l & = (\pi_{l3}, \pi_{l4}, \pi_{l5}), \\
\end{array}
\end{equation}

where $\mbi{d}_l$ is the {\em directional vector} of $l$ and $\mbi{l}_l$
is the {\em locational vector} of $l$. The \plucker coordinates
$\bpi_l$ and the \plucker coefficients $\bomega_l$ can be expressed as:


\begin{equation}
\begin{array}{ll}
\bpi_l &= [\mbi{d}_l; \mbi{l}_l],\\
\bomega_l &= [\mbi{l}_l; \mbi{d}_l].
\end{array}
\label{eq:rot3_locdir}
\end{equation}


\subsubsection{Extracting a point}

Often we need to describe a line using a parametric representation by
means of an {\em anchor point} and a directional vector. Given a line
$l$ the directional vector $\mbi{d}_l$ is embedded in the \plucker
coordinates of $l$ (see Eq.~\ref{eq:rot3_locdir}). The anchor point
$\mbi{a}_l$ can be computed as:

\begin{equation}
\mbi{a}_l = (a_x, a_y, a_z) = \frac{\mbi{d}_l \times \mbi{l}_l}{\parallel \mbi{d}_l \parallel ^2}.
\end{equation}
  

\subsubsection{Computing the distance}

The distance between two lines $l$ and $l'$ can be expressed 
using their anchor points and the directional vectors:

\begin{equation}
  dist(l, l') = { | (\mbi{a}_l - \mbi{a}_{l'}) \cdot (\mbi{d}_l \times
\mbi{d}_{l'}) | \over \parallel \mbi{d}_l \times \mbi{d}_{l'} \parallel }.
\end{equation}


The distance is the length of the projection of the line segment
$\mbi{a}_l,\mbi{a}_{l'}$ onto the direction $\mbi{d}_l \times
\mbi{d}_{l'}$.



%%%%%%%%%%%%%%%%%%%%%%

\section{Visual events}

\label{sec:events}

This section discusses visual events occurring in polygonal
scenes~\cite{Gigus90}. We will focus on the boundaries of visual
events and their relation to \plucker coordinates. The understanding
of the  visual events helps to comprehend the complexity of the
from-region visibility in 3D.

 Any scene can be decomposed into regions from which the scene has a
topologically equivalent view~\cite{Gigus90}. Boundaries of such
regions correspond to {\em event surfaces}. Crossing an event surface
causes a {\em visual event}, i.e. a change in the topology of the view
(visibility map). In polygonal scenes there are three types of event
surfaces~\cite{Gigus90}:

\begin{itemize}
  \item {\em vertex-edge} (VE) events involving an edge and a vertex
  of two distinct polygons.
  \item {\em edge-edge-edge} (EEE) events involving three edges of
  three distinct polygons.
  \item {\em supporting} events corresponding to supporting planes of
  scene polygons. The supporting event can be seen as a degenerated
  case of VE or EEE events.
\end{itemize}

The VE events correspond to planes, the EEE events in general form
quadratic surfaces. The definitions assume that the scene polygons are
in general non-degenerate position. In real world scenes the polygons
or their edges polygons can be variously aligned. In such a case these
definitions of visibility events form minimal sets of edges and
vertices defining an event. For example a VE event can involve a
vertex and several edges of scene polygons (see
Figure~\ref{fig:degen_event}).

\begin{figure}[htb]
\centerline{
  \includegraphics[width=0.45\textwidth,draft=\DRAFTFIGS]{figs/ve_degen}}
\caption{Degenerated VE event. The VE event is induced by a vertex and
three edges of scene polygons.} 
\label{fig:degen_event}
\end{figure}


 The intersections of event surfaces correspond to {\em extremal
lines}~\cite{Teller92phd}. An extremal line intersects four edges of
some scene polygons. There are four types of extremal lines:
vertex-vertex (VV) lines, vertex-edge-edge (VEE) lines,
edge-vertex-edge (EVE) and quadruple edge (4E) lines. Imagine
``sliding'' an extremal line (of any type) away from its initial
position by relaxing exactly one of the four edge constraints
determining the line. The section of the event surface swept out by
the sliding line is called the {\em swath}.  A swath is either planar
if it corresponds to a VE event surface or a regulus if it is embedded
in an EEE event surface.

Figure~\ref{swaths}-(a) shows an extremal VV line tight on four edges
A,B,C, and D. Relaxing constraint C yields a VE (planar) swath defined
by A,B, and D. When the sliding line encounters an obstacle (edge E) it
terminates at a VV extremal line defined by A,B,D, and
E. Figure~\ref{swaths}-(b) depicts an extremal 4E line tight on the
mutually skew edges A,B,C, and D. Relaxing constraint A produces an EEE
event surface that is a regulus intersecting B,C, and D. When the
sliding line encounters edge E the swath terminates at an VEE extremal
line.

\begin{figure}[htb]
\centerline{
  \includegraphics[width=0.75\textwidth,draft=\DRAFTFIGS]{figs/swaths}}
\centerline{\small
{\bf (a)}\hspace{0.3\textwidth} {\bf (b)}
\hspace{0.2\textwidth}}
\caption{Swaths of event surfaces. (a) VE swath. (b) EEE swath. }
\label{swaths}
\end{figure}


\subsection{Visual events and \plucker coordinates}

\plucker coordinates allow an elegant description of event surfaces.
An event surface can be expressed as an intersection of three \plucker
hyperplanes, and thus avoiding explicit treatment of quadratic
surfaces. The non-linear EEE surfaces correspond to curves embedded in
the intersection of the \plucker hyperplanes.

Let ${\cal H}$ be an arrangement~\cite{dcg-handbook} of hyperplanes in
${\cal P}^5$ that correspond to \plucker coefficients of edges of the
scene polygons. The intersection of the arrangement ${\cal H}$ and the
\plucker quadric yields all visual
events~\cite{Teller92phd,p-rsls-97,Pu98-DSGIV}.

An extremal line $l$ intersects four generator edges. Consequently,
the corresponding \plucker point $\ppoint_l$ lies on four \plucker
hyperplanes.  In 5D the four hyperplanes define an edge of the
arrangement ${\cal H}$. Thus, we can find all extremal lines of a
given set of polygons by examining the edges of ${\cal H}$ for
intersections with the \plucker quadric~\cite{Pu98-DSGIV}.


Consider the situation depicted in Figure~\ref{swaths}. In line space
the event surfaces correspond to curves embedded in the \plucker
quadric. In general these curves are conics defined by an intersection
of the 2D-faces of ${\cal H}$ with the \plucker quadric (see
Figure~\ref{5Dswaths}).

\begin{figure}[htb]
\centerline{
  \includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/ipswaths}}
\caption{3D swaths correspond to conics on the Pl\"ucker quadric.} 
\label{5Dswaths}
\end{figure}



\section{Lines intersecting a polygon}

\label{sec:rot3d_singlepoly}

 \plucker coordinates provide a tool to map lines from primal space to
points in line space. This mapping allows to perform operations of
sets of lines using set theoretical operations on the corresponding
sets of points. In polygonal scenes the {\em elementary set of lines}
is formed by lines intersecting a given polygon.


 Assume that a convex polygon $P$ is defined by edges $e_i, 0\leq i <
n$ that are oriented counterclockwise. The set of lines ${\cal L}_P$
intersecting the polygon that are oriented in the direction of the
polygon's normal satisfies:


\begin{equation}
{\cal L}_P = \{ l |  l \in (R^3, R^3), side(\bpi_l, \bpi_{e_i}) \leq 0, \forall i \in \langle 0,n) \},
\label{eq:halfspaces}
\end{equation}

where $\bpi_l$ are \plucker coordinates of line $l$ and $\bpi_{e_i}$ are
\plucker coordinates of $i$-th edge of the polygon. Substituting the
Eq.~\ref{eq:side} and rewriting the equation in terms of a set of
\plucker points we get:

\begin{equation}
\begin{array}{ll}
{\cal F}_P & = \{ \ppoint | \ppoint \in {\cal P}^5, \bpi \times \bpi_{e_i} \leq 0, \forall i \in \langle 0,n) \} = \\
           & = \{ \ppoint | \ppoint \in {\cal P}^5, \bpi \odot \bomega_{e_i} \leq 0, \forall i \in \langle 0,n) \},
\end{array}
\label{eq:feasible}
\end{equation}

where ${\cal F}_P$ is a set of {\em feasible \plucker points} for
polygon $P$. Substituting Eq.~\ref{eq:def_halfspaces}
into~\ref{eq:feasible} we obtain:

\begin{equation}
\begin{array}{ll}
{\cal F}_P & = \{ \ppoint | \ppoint \in {\cal P}^5,  \bpi \in \pplane^-_{e_i}, \forall i \in \langle 0,n) \}
\end{array}
\label{eq:intersection}
\end{equation}

Thus the set of feasible \plucker points is defined by an intersection
of halfspaces defined by the \plucker hyperplanes corresponding to edges of the
polygon. The set of {\em stabbers} ${\cal S}_P$ is then defined as an
intersection of ${\cal F}_P$ with the \plucker quadric:

\begin{equation}
{\cal S}_P = \{ \ppoint | \ppoint \in {\cal F}_P, \bpi \odot \bpi  = 0 \}.
\end{equation}

The stabbers are \plucker points corresponding to the real lines
intersecting the polygon that are oriented in the direction of the
normal. Similarly we can define the sets of {\em reverse feasible
\plucker points} ${\cal F}^-_P$ and {\em reverse stabbers} ${\cal
S}^-_P$ that correspond to opposite oriented lines intersecting the
polygon:

\begin{equation}
\begin{array}{ll}
{\cal F}^-_P  & = \{ \ppoint | \ppoint \in {\cal P}^5, \ppoint \in \pplane^+_{e_i}, \forall i \in \langle 0,n) \} \\
{\cal S}^-_P  & = \{ \ppoint | \ppoint \in {\cal F}^-_P, \bpi \odot \bpi  = 0 \}.
\end{array}
\end{equation}




\section{Lines between two polygons}
\label{sec:rot3d_twopoly}

 The above presented definitions of elementary line sets  allow to
handle visibility computations by means of set operations on the sets
of feasible \plucker points.  Visibility between two polygons $P_j$
and $P_k$ can be determined by constructing an intersection of
feasible sets of the two polygons ${\cal F}_{P_j}$ and ${\cal
F}_{P_k}$ and subtracting all feasible sets of polygons lying between
$P_j$ and $P_k$. To obtain the set of unoccluded stabbers we intersect
the resulting feasible set with the \plucker quadric.

Further in this chapter we restrict our discussion to visibility from
a given {\em source polygon} $P_S$. Given any {\em occluder polygon}
$P_j$ we first describe lines intersecting both $P_S$ and $P_j$. Lines
between $P_S$ and  $P_j$ can be described by an intersection of their
feasible line sets:

\begin{equation}
{\cal F}_{P_SP_j} = {\cal F}_{P_S} \cap {\cal F}_{P_j}
\end{equation}

and thus

\begin{equation}
{\cal S}_{P_SP_j} = {\cal S}_{P_S} \cap {\cal S}_{P_j}. 
\end{equation}

 The feasible \plucker points are defined by an intersection of
halfspaces corresponding to edges of $P_S$ and $P_j$. These halfspaces
define a {\em blocker polyhedron} $B_{P_SP_j}$ that is described in
the next section.


\subsubsection{Blocker polyhedron}

 The blocker polyhedron describes lines intersecting the source
 polygon and the given occluder.  The blocker polyhedron can be seen
 as an extension of the blocker polygon discussed above for the from-region
 visibility in 3D scenes. The blocker polyhedron is a 5D polyhedron in
 a 5D projective space.  To avoid singularities in the projection from
 ${\cal P}^5$ to ${\cal R}^5$ the polyhedron can be embedded in ${\cal
 R}^6$ similarly to the embedding of blocker polygon in ${\cal R}^3$
 (see Section~\ref{sec:blocker_polygon}). Then the polyhedron actually
 represents a 6D pyramid with an apex at the origin of ${\cal R}^6$.


\subsubsection{Cap planes}

The blocker polyhedron is defined by an intersection of halfspaces
defined by \plucker planes that are mappings of edges of the source
polygon and the occluder. As stated above the blocker polyhedron
represents the set of feasible \plucker points ${\cal F}_{P_SP_j}$
including points not intersecting the \plucker quadric that correspond
to imaginary lines. We bound the polyhedron by {\em cap planes}
aligned with the \plucker quadric so that the resulting polyhedron is
a tighter representation of the stabbers ${\cal S}_{P_SP_j}$. We need
to ensure that the resulting polyhedron fully contains the stabbers
${\cal S}_{P_SP_j}$, i.e. contains the cross-section of the \plucker
quadric and ${\cal F}_{P_SP_j}$.

The cap planes provide the following benefits:

\begin{itemize}
\item The computation is localized to the proximity of the \plucker
quadric. This reduces the combinatorial complexity of data structure
representing an arrangement of the blocker polyhedra.

\item The blocker polyhedron is always bounded. Although the set of
  lines between two convex polygons is bounded, the set of feasible
  \plucker points can be unbounded at the ``direction'' of imaginary
  lines. Adding the cap planes we make sure that the polyhedron is
  bounded, which allows its easier treatment. By using the cap planes
  we avoid the handling of very oblong, almost unbounded polyhedra,
  which improves numerical stability of a floating point
  implementation of the algorithm.
\end{itemize}


 We used two cap planes to bound the polyhedron, one for each side of
the \plucker quadric (a side is given by the sign of $\bpi \odot
\bpi$). The cap planes are computed as tangents to the \plucker
quadric at the center of the set of stabbers ${\cal S}_{P_SP_j}$. The
planes are translated each at the opposite direction making sure that
they include the whole set ${\cal S}_{P_SP_j}$.



\subsection{Intersection with the \plucker quadric}
\label{sec:stabbers}

Given a blocker polyhedron representing the set of feasible lines
${\cal F}_{P_SP_j}$ we can compute an intersection of the edges of the
polyhedron with the \plucker quadric to determine the set of extremal
lines bounding the set of stabbers ${\cal S}_{P_SP_j}$. An
intersection of an edge of the blocker polyhedron with the \plucker
quadric results in at most two {\em extremal \plucker points} that
correspond extremal lines\footnote{Neglecting the case that the whole
edge is embedded in the \plucker quadric, which results in infinite
number of extremal lines.}. Given an edge of the blocker polyhedron
the intersection with the \plucker quadric is computed by solving the
quadratic equation (Eq.~\ref{eq:plucker_quadric}). A robust algorithm
for computing this intersection was developed by
Teller~\cite{TH83}.


Intersecting all edges of the blocker polyhedron with the \plucker
quadric yields all extremal lines of ${\cal
S}_{P_SP_j}$~\cite{Teller:1992:CAA,Pu98-DSGIV}. See
Figure~\ref{fig:rot3_visrays} for an example of extremal lines
computed for the given source polygon and a set of three occluders.


\begin{figure}[htb]
\centerline{
  \includegraphics[width=0.5\textwidth,draft=\DRAFTIMAGES]{images/rot3_visrays}}
\caption{Extremal lines for the given source polygon (yellow) and three occluders.}
\label{fig:rot3_visrays}
\end{figure}

 The intersection of the 2D faces of the blocker polyhedron with the
\plucker quadric yields swaths of event surfaces of the set of
stabbers ${\cal S}_{P_SP_j}$~\cite{Teller92phd}. In general the
intersection results in 1D conics.

 We can avoid the explicit treatment of conics in 5D by computing the
local topology of the edges of the blocker polyhedron and constructing
the swaths in primal space between the topologically connected
extremal lines~\cite{Teller92phd}. The local topology of an extremal
\plucker point is given by connections with extremal \plucker points
embedded in the same 2D face of the blocker polyhedron.  A 2D face of
the blocker polyhedron is given by three \plucker hyperplanes. Thus
the pairs of extremal \plucker points defined by the subset of the
same three \plucker hyperplanes define a swath.



% For solution of some from-region visibility problems (e.g. PVS
% computation, region-to-region visibility) the event swaths need not be
% reconstructed. For example the visibility culling algorithm that will
% be discussed in Section~\ref{sec:rot3pvs} only computes extremal
% \plucker points and uses them to test an existence of a set of
% stabbers of a given size.


\subsection{Size of the set of lines}

\label{sec:size_measure}

Computing a size measure of a given set of lines is useful for most
visibility algorithms. The computed size measure can be used to drive
the subdivision of the given set of lines or to bound the maximal
error of the algorithm. An analytic algorithm can use the computed
size measure for thresholding by a given $\epsilon$-size to discard
very small line sets.  A discrete algorithm can use the size measure
to determine the required density of sampling.

The size of a set of lines for the from-point visibility can be
formulated easily: the size is given by the area of the intersection
of the line set with a plane. This corresponds to quantifying
visibility of an object according to its projected area. Such a size
is determined in the solution space (viewport). Alternatively we could
use a ``viewport independent measure'' given by a solid angle formed by
the visible part of an object. The size measure for the from-region
visibility problems is more complicated for the following reasons:

\begin{itemize}
\item The domain of the solution space is four-dimensional.
\item The solution space of the from-region visibility algorithm
  generally does not correspond to the solution space of the
  application. For example, a visible surface algorithm using a
  precomputed PVS works in a 2D domain induced by the given viewport.
\end{itemize}


\subsubsection{General size measure}

A size of a set of lines for the from-region visibility can be
computed by evaluating a 4D integral. Using \plucker coordinates we
can compute a volume of the 4D hyper-surface corresponding to the
given set of lines. The volume however depends on a way of projecting
the blocker polyhedron from ${\cal P}^5$ to ${\cal R}^5$. This
projection has a similar role as the selection of the viewport for the
from-point visibility problem. We can project the blocker polyhedron
from ${\cal P}^5$ to ${\cal R}^5$ by projecting it to a 5D hyperplane
defined by certain reference direction, e.g. the ``center-line'' of
the given set of lines. Pu proposed a different size measure based on
measuring the {\em angular spread} and the {\em distance} between
lines~\cite{Pu98-DSGIV}. Both these quantities can be evaluated in
terms of \plucker coordinates of the set of extremal lines of the
given line set.


\subsubsection{Size measure for the PVS computation}

 It can be difficult to relate the size measures described above to
the domain of the result of a subsequently applied visibility
algorithm. We need a simple scheme that fits to the context of the
target application.  In this section we suggest a size measure
designed for the PVS computation. When computing a PVS we are
interested in measuring the size of the set of unoccluded lines
(stabbers) between the source polygon $P_S$ and a given scene
polygon. If this size is below an $\epsilon$-threshold, we can
possibly exclude the polygon from the PVS.  We suggest to use an
estimate of the minimal angle between the stabbers at a point inside
$P_S$. The idea is to estimate the minimal projected diameter of a
polygon visible through the given set of lines from any point inside
$P_S$. This estimate can be used to bound a maximal error of an image
synthesized with respect to any viewpoint inside $P_S$ for the case that
the corresponding set of lines is neglected.

%%  The size measure approximates the minimal spatial angle given by a
%% cross-section of the given set of lines parallel to the source polygon
%% $P_S$ and the center of $P_S$.

Given a blocker polyhedron ${\cal F}_{P_SP_j}$  the proposed size
measure can be evaluated as follows:

\begin{enumerate}

\item
 Compute the extremal lines of the corresponding set of stabbers ${\cal
S}_{P_SP_j}$ as described in Section~\ref{sec:stabbers}.

\item For each polygon edge $e_i$ bounding the stabbers
  determine an extremal line $l_{mi}$ with a maximal distance from the
  edge.
  
\item For each edge $e_i$ compute a shortest line segment $z_i$
  connecting $e_i$ and $l_{mi}$.  The length of this line segment is
  then scaled according to its distance from the source polygon,
  i.e. we compute an angle $\alpha_i$ between the lines connecting the
  center of the source polygon and the endpoints of $z_i$.
  
\item Select a minimal angle $\alpha_m$ of all $\alpha_i$ as the
estimate of the size of the given line set.

\end{enumerate}

The evaluation of the size measure is depicted in
Figure~\ref{fig:linesize}.

\begin{figure}[htb]
\centerline{
  \includegraphics[width=0.4\textwidth,draft=\DRAFTFIGS]{figs/linesize}}
\caption{A 2D example of evaluation of the size of a set of lines. The three
  line segments
  $z_1$, $z_2$ and $z_3$ maximize the distance of the corresponding
  occluder edges from the extremal lines. The line segment $z_3$ spans
  a minimal angle $\alpha_m$ with respect to the center of the source
  polygon $P_S$.}
\label{fig:linesize}
\end{figure}

 The angle $\alpha_m$ can be related to the angular resolution of the
synthesized image. Given the resolution of the image we can threshold
``small'' line sets with $\alpha_m$ below the corresponding angular
threshold to achieve a sub-pixel precision of the rendering algorithm.
This measure can also be applied to deal with the finite precision of
the floating point arithmetics by using a small $\epsilon$-threshold
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.