[2066] | 1 |
|
---|
| 2 |
|
---|
| 3 |
|
---|
| 4 | \chapter{Introduction}%\chapter
|
---|
| 5 | \label{chap:introduction}
|
---|
| 6 |
|
---|
| 7 | \section{Structure of the report}
|
---|
| 8 |
|
---|
| 9 | The report consists of two introductory chapters, which provide a
|
---|
| 10 | theoretical background for description of the algorithms, and three
|
---|
| 11 | chapters dealing with the actual visibility algorithms.
|
---|
| 12 |
|
---|
| 13 | This chapter provides an introduction to visibility by using a
|
---|
| 14 | taxonomy of visibility problems and algorithms. The taxonomy is used
|
---|
| 15 | to classify the later described visibility
|
---|
| 16 | algorithms. Chapter~\ref{chap:analysis} provides an analysis of
|
---|
| 17 | visibility in 2D and 3D polygonal scenes. This analysis also includes
|
---|
| 18 | formal description of visibility using \plucker coordinates of
|
---|
| 19 | lines. \plucker coordinates are exploited later in algorithms for
|
---|
| 20 | mutual visibility verification (Chapter~\ref{chap:mutual}).
|
---|
| 21 |
|
---|
| 22 | Chapter~\ref{chap:online} describes a visibility culling algorithm
|
---|
| 23 | used to implement the online visibility culling module. This
|
---|
| 24 | algorithm can be used accelerate rendering of fully dynamic scenes
|
---|
| 25 | using recent graphics hardware. Chapter~\ref{chap:sampling}
|
---|
| 26 | describes global visibility sampling algorithm which forms a core of
|
---|
| 27 | the PVS computation module. This chapter also describes view space
|
---|
| 28 | partitioning algorithms used in close relation with the PVS
|
---|
| 29 | computation. Finally, Chapter~\ref{chap:mutual} describes mutual
|
---|
| 30 | visibility verification algorithms, which are used by the PVS
|
---|
| 31 | computation module to generate the final solution for precomputed
|
---|
| 32 | visibility.
|
---|
| 33 |
|
---|
| 34 |
|
---|
| 35 |
|
---|
| 36 |
|
---|
| 37 | %% summarize the state of the art
|
---|
| 38 | %% visibility algorithms and their relation to the proposed taxonomy of
|
---|
| 39 | %% visibility problems. The second part of the survey should serve as a
|
---|
| 40 | %% catalogue of visibility algorithms that is indexed by the proposed
|
---|
| 41 | %% taxonomy of visibility problems.
|
---|
| 42 |
|
---|
| 43 |
|
---|
| 44 |
|
---|
| 45 | \section{Domain of visibility problems}
|
---|
| 46 | \label{sec:prob_domain}
|
---|
| 47 |
|
---|
| 48 | Computer graphics deals with visibility problems in the context of
|
---|
| 49 | 2D, \m25d, or 3D scenes. The actual problem domain is given by
|
---|
| 50 | restricting the set of rays for which visibility should be
|
---|
| 51 | determined.
|
---|
| 52 |
|
---|
| 53 | Below we list common problem domains used and the corresponding domain
|
---|
| 54 | restrictions:
|
---|
| 55 |
|
---|
| 56 | \begin{enumerate}
|
---|
| 57 | \item
|
---|
| 58 | {\em visibility along a line}
|
---|
| 59 | \begin{enumerate}
|
---|
| 60 | \item line
|
---|
| 61 | \item ray (origin + direction)
|
---|
| 62 | \end{enumerate}
|
---|
| 63 | \newpage
|
---|
| 64 | \item
|
---|
| 65 | {\em visibility from a point} ({\em from-point visibility})
|
---|
| 66 | \begin{enumerate}
|
---|
| 67 | \item point
|
---|
| 68 | \item point + restricted set of rays
|
---|
| 69 | \begin{enumerate}
|
---|
| 70 | \item point + raster image (discrete form)
|
---|
| 71 | \item point + beam (continuous form)
|
---|
| 72 | \end{enumerate}
|
---|
| 73 | \end{enumerate}
|
---|
| 74 |
|
---|
| 75 |
|
---|
| 76 | \item
|
---|
| 77 | {\em visibility from a line segment} ({\em from-segment visibility})
|
---|
| 78 | \begin{enumerate}
|
---|
| 79 | \item line segment
|
---|
| 80 | \item line segment + restricted set of rays
|
---|
| 81 | \end{enumerate}
|
---|
| 82 |
|
---|
| 83 | \item
|
---|
| 84 | {\em visibility from a polygon} ({\em from-polygon visibility})
|
---|
| 85 | \begin{enumerate}
|
---|
| 86 | \item polygon
|
---|
| 87 | \item polygon + restricted set of rays
|
---|
| 88 | \end{enumerate}
|
---|
| 89 |
|
---|
| 90 | \item
|
---|
| 91 | {\em visibility from a region} ({\em from-region visibility})
|
---|
| 92 | \begin{enumerate}
|
---|
| 93 | \item region
|
---|
| 94 | \item region + restricted set of rays
|
---|
| 95 | \end{enumerate}
|
---|
| 96 |
|
---|
| 97 | \item
|
---|
| 98 | {\em global visibility}
|
---|
| 99 | \begin{enumerate}
|
---|
| 100 | \item no further input (all rays in the scene)
|
---|
| 101 | \item restricted set of rays
|
---|
| 102 | \end{enumerate}
|
---|
| 103 | \end{enumerate}
|
---|
| 104 |
|
---|
| 105 | The domain restrictions can be given independently of the dimension
|
---|
| 106 | of the scene, but the impact of the restrictions differs depending on
|
---|
| 107 | the scene dimension. For example, visibility from a polygon is
|
---|
| 108 | equivalent to visibility from a (polygonal) region in 2D, but not in
|
---|
| 109 | 3D.
|
---|
| 110 |
|
---|
| 111 | %*****************************************************************************
|
---|
| 112 |
|
---|
| 113 | \section{Dimension of the problem-relevant line set}
|
---|
| 114 |
|
---|
| 115 | The six domains of visibility problems stated in
|
---|
| 116 | Section~\ref{sec:prob_domain} can be characterized by the {\em
|
---|
| 117 | problem-relevant line set} denoted ${\cal L}_R$. We give a
|
---|
| 118 | classification of visibility problems according to the dimension of
|
---|
| 119 | the problem-relevant line set. We discuss why this classification is
|
---|
| 120 | important for understanding the nature of the given visibility problem
|
---|
| 121 | and for identifying its relation to other problems.
|
---|
| 122 |
|
---|
| 123 |
|
---|
| 124 | For the following discussion we assume that a line in {\em primal
|
---|
| 125 | space} can be mapped to a point in {\em line space}. For purposes of
|
---|
| 126 | the classification we define the line space as a vector space where a
|
---|
| 127 | point corresponds to a line in the primal space\footnote{A classical
|
---|
| 128 | mathematical definition says: Line space is a direct product of two
|
---|
| 129 | Hilbert spaces~\cite{Weisstein:1999:CCE}. However, this definition
|
---|
| 130 | differs from the common understanding of line space in computer
|
---|
| 131 | graphics~\cite{Durand99-phd}}.
|
---|
| 132 |
|
---|
| 133 |
|
---|
| 134 |
|
---|
| 135 | \subsection{Parametrization of lines in 2D}
|
---|
| 136 |
|
---|
| 137 | There are two independent parameters that specify a 2D line and thus
|
---|
| 138 | the corresponding set of lines is two-dimensional. There is a natural
|
---|
| 139 | duality between lines and points in 2D. For example a line expressed
|
---|
| 140 | as: $l:y=ax+c$ is dual to a point $p=(-c,a)$. This particular duality
|
---|
| 141 | cannot handle vertical lines. %See Figure~\ref{fig:duality2d} for an
|
---|
| 142 | example of other dual mappings in the plane. To avoid the singularity
|
---|
| 143 | in the mapping, a line $l:ax+by+c=0$ can be represented as a point
|
---|
| 144 | $p_l=(a,b,c)$ in 2D projective space ${\cal
|
---|
| 145 | P}^2$~\cite{Stolfi:1991:OPG}. Multiplying $p_l$ by a non-zero scalar
|
---|
| 146 | we obtain a vector that represents the same line $l$. More details
|
---|
| 147 | about this singularity-free mapping will be discussed in
|
---|
| 148 | Chapter~\ref{chap:analysis}.
|
---|
| 149 |
|
---|
| 150 |
|
---|
| 151 | %\begin{figure}[!htb]
|
---|
| 152 | %\centerline{
|
---|
| 153 | %\includegraphics[width=0.9\textwidth,draft=\DRAFTFIGS]{figs/duality2d}}
|
---|
| 154 | %\caption{Duality between points and lines in 2D.}
|
---|
| 155 | %\label{fig:duality2d}
|
---|
| 156 | %\end{figure}
|
---|
| 157 |
|
---|
| 158 |
|
---|
| 159 |
|
---|
| 160 |
|
---|
| 161 |
|
---|
| 162 | To sum up: In 2D there are two degrees of freedom in description of a
|
---|
| 163 | line and the corresponding line space is two-dimensional. The
|
---|
| 164 | problem-relevant line set ${\cal L}_R$ then forms a $k$-dimensional
|
---|
| 165 | subset of ${\cal P}^2$, where $0\leq k \leq 2$. An illustration of the
|
---|
| 166 | concept of the problem-relevant line set is depicted in
|
---|
| 167 | %Figure~\ref{fig:classes}.
|
---|
| 168 |
|
---|
| 169 |
|
---|
| 170 | %\begin{figure}[htb]
|
---|
| 171 | %\centerline{
|
---|
| 172 | %\includegraphics[width=0.8\textwidth,draft=\DRAFTFIGS]{figs/classes}}
|
---|
| 173 | %\caption{The problem-relevant set of lines in 2D. The ${\cal L}_R$ for
|
---|
| 174 | %visibility along a line is formed by a single point that is a mapping
|
---|
| 175 | %of the given line. The ${\cal L}_R$ for visibility from a point $p$ is
|
---|
| 176 | %formed by points lying on a line. This line is a dual mapping of the
|
---|
| 177 | %point $p$. ${\cal L}_R$ for visibility from a line segment is formed
|
---|
| 178 | %by a 2D region bounded by dual mappings of endpoints of the given
|
---|
| 179 | %segment.}
|
---|
| 180 | %\label{fig:classes}
|
---|
| 181 | %\end{figure}
|
---|
| 182 |
|
---|
| 183 |
|
---|
| 184 | \subsection{Parametrization of lines in 3D}
|
---|
| 185 |
|
---|
| 186 |
|
---|
| 187 | Lines in 3D form a four-parametric space~\cite{p-rsls-97}. A line
|
---|
| 188 | intersecting a given scene can be described by two points on a sphere
|
---|
| 189 | enclosing the scene. Since the surface of the sphere is a two
|
---|
| 190 | parametric space, we need four parameters to describe the line.
|
---|
| 191 |
|
---|
| 192 | The {\em two plane parametrization} of 3D lines describes a line by
|
---|
| 193 | points of intersection with the given two
|
---|
| 194 | planes~\cite{Gu:1997:PGT}. This parametrization exhibits a singularity
|
---|
| 195 | since it cannot describe lines parallel to these planes. See
|
---|
| 196 | %Figure~\ref{fig:3dlines} for illustrations of the spherical and the
|
---|
| 197 | two plane parameterizations.
|
---|
| 198 |
|
---|
| 199 |
|
---|
| 200 | %\begin{figure}[htb]
|
---|
| 201 | %\centerline{
|
---|
| 202 | %\includegraphics[width=0.78\textwidth,draft=\DRAFTFIGS]{figs/3dlines}}
|
---|
| 203 | %\caption{Parametrization of lines in 3D. (left) A line can be
|
---|
| 204 | % described by two points on a sphere enclosing the scene. (right) The
|
---|
| 205 | % two plane parametrization describes a line by point of intersection
|
---|
| 206 | % with two given planes.}
|
---|
| 207 | %\label{fig:3dlines}
|
---|
| 208 | %\end{figure}
|
---|
| 209 |
|
---|
| 210 | Another common parametrization of 3D lines are the {\em \plucker
|
---|
| 211 | coordinates}. \plucker coordinates of an oriented 3D line are a six
|
---|
| 212 | tuple that can be understood as a point in 5D oriented projective
|
---|
| 213 | space~\cite{Stolfi:1991:OPG}. There are six coordinates in \plucker
|
---|
| 214 | representation of a line although we know that the ${\cal L}_R$ is
|
---|
| 215 | four-dimensional. This can be explained as follows:
|
---|
| 216 |
|
---|
| 217 | \begin{itemize}
|
---|
| 218 | \item Firstly, \plucker coordinates are {\em homogeneous
|
---|
| 219 | coordinates} of a 5D point. By multiplication of the coordinates
|
---|
| 220 | by any positive scalar we get a mapping of the same line.
|
---|
| 221 | \item Secondly, only 4D subset of the 5D oriented projective space
|
---|
| 222 | corresponds to real lines. This subset is a 4D ruled quadric called
|
---|
| 223 | the {\em \plucker quadric} or the {\em Grassman
|
---|
| 224 | manifold}~\cite{Stolfi:1991:OPG,Pu98-DSGIV}.
|
---|
| 225 | \end{itemize}
|
---|
| 226 |
|
---|
| 227 | Although the \plucker coordinates need more coefficients they have no
|
---|
| 228 | singularity and preserve some linearities: lines intersecting a set of
|
---|
| 229 | lines in 3D correspond to an intersection of 5D hyperplanes. More
|
---|
| 230 | details on \plucker coordinates will be discussed in
|
---|
| 231 | Chapter~\ref{chap:analysis} and Chapter~\ref{chap:mutual} where they
|
---|
| 232 | are used to solve the from-region visibility problem.
|
---|
| 233 |
|
---|
| 234 | To sum up: In 3D there are four degrees of freedom in the
|
---|
| 235 | description of a line and thus the corresponding line space is
|
---|
| 236 | four-dimensional. Fixing certain line parameters (e.g. direction) the
|
---|
| 237 | problem-relevant line set, denoted ${\cal L}_R$, forms a
|
---|
| 238 | $k$-dimensional subset of ${\cal P}^4$, where $0\leq k \leq 4$.
|
---|
| 239 |
|
---|
| 240 |
|
---|
| 241 | \subsection{Visibility along a line}
|
---|
| 242 |
|
---|
| 243 | The simplest visibility problems deal with visibility along a single
|
---|
| 244 | line. The problem-relevant line set is zero-dimensional, i.e. it is
|
---|
| 245 | fully specified by the given line. A typical example of a visibility
|
---|
| 246 | along a line problem is {\em ray shooting}.
|
---|
| 247 |
|
---|
| 248 | A similar problem to ray shooting is the {\em point-to-point}
|
---|
| 249 | visibility. The point-to-point visibility determines whether the
|
---|
| 250 | line segment between two points is occluded, i.e. it has an
|
---|
| 251 | intersection with an opaque object in the scene. Point-to-point
|
---|
| 252 | visibility provides a visibility classification (answer 1a), whereas
|
---|
| 253 | ray shooting determines a visible object (answer 2a) and/or a point of
|
---|
| 254 | intersection (answer 3a). Note that the {\em point-to-point}
|
---|
| 255 | visibility can be solved easily by means of ray shooting. Another
|
---|
| 256 | constructive visibility along a line problem is determining the {\em
|
---|
| 257 | %maximal free line segments} on a given line. See Figure~\ref{fig:val}
|
---|
| 258 | for an illustration of typical visibility along a line problems.
|
---|
| 259 |
|
---|
| 260 | %\begin{figure}[htb]
|
---|
| 261 | %\centerline{
|
---|
| 262 | %\includegraphics[width=0.85\textwidth,draft=\DRAFTFIGS]{figs/val}}
|
---|
| 263 | %\caption{Visibility along a line. (left) Ray shooting. (center) Point-to-point visibility. (right) Maximal free line segments between two points.}
|
---|
| 264 | %\label{fig:val}
|
---|
| 265 | %\end{figure}
|
---|
| 266 |
|
---|
| 267 |
|
---|
| 268 | \subsection{Visibility from a point}
|
---|
| 269 |
|
---|
| 270 | Lines intersecting a point in 3D can be described by two
|
---|
| 271 | parameters. For example the lines can be expressed by an intersection
|
---|
| 272 | with a unit sphere centered at the given point. The most common
|
---|
| 273 | parametrization describes a line by a point of intersection with a
|
---|
| 274 | given viewport. Note that this parametrization accounts only for a
|
---|
| 275 | %subset of lines that intersect the viewport (see Figure~\ref{fig:vfp}).
|
---|
| 276 |
|
---|
| 277 | %\begin{figure}[htb]
|
---|
| 278 | %\centerline{
|
---|
| 279 | %\includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/vfp}}
|
---|
| 280 | %\caption{Visibility from a point. Lines intersecting a point can be described by a
|
---|
| 281 | % point of intersection with the given viewport.}
|
---|
| 282 | %\label{fig:vfp}
|
---|
| 283 | %\end{figure}
|
---|
| 284 |
|
---|
| 285 | In 3D the problem-relevant line set ${\cal L}_R$ is a 2D subset of
|
---|
| 286 | the 4D line space. In 2D the ${\cal L}_R$ is a 1D subset of the 2D
|
---|
| 287 | line space. The typical visibility from a point problem is the visible
|
---|
| 288 | surface determination. Due to its importance the visible surface
|
---|
| 289 | determination is covered by the majority of existing visibility
|
---|
| 290 | algorithms. Other visibility from a point problem is the construction
|
---|
| 291 | of the {\em visibility map} or the {\em point-to-region visibility}
|
---|
| 292 | that classifies a region as visible, invisible, or partially visible
|
---|
| 293 | with respect to the given point.
|
---|
| 294 |
|
---|
| 295 |
|
---|
| 296 | \subsection{Visibility from a line segment}
|
---|
| 297 |
|
---|
| 298 | Lines intersecting a line segment in 3D can be described by three
|
---|
| 299 | parameters. One parameter fixes the intersection of the line with the
|
---|
| 300 | segment the other two express the direction of the line. The
|
---|
| 301 | problem-relevant line set ${\cal L}_R$ is three-dimensional and it can
|
---|
| 302 | be understood as a 2D cross section of ${\cal L}_R$ swept according
|
---|
| 303 | to the translation on the given line segment (see
|
---|
| 304 | %Figure~\ref{fig:vls}).
|
---|
| 305 |
|
---|
| 306 |
|
---|
| 307 | %\begin{figure}[htb]
|
---|
| 308 | %\centerline{
|
---|
| 309 | %\includegraphics[width=0.8\textwidth,draft=\DRAFTFIGS]{figs/vls}}
|
---|
| 310 | %\caption{Visibility from a line segment. (left) Line segment, a
|
---|
| 311 | % spherical object $O$, and its projections $O^*_0$, $O^*_{0.5}$, $O^*_{1}$
|
---|
| 312 | % with respect to the three points on the line segment. (right)
|
---|
| 313 | % A possible parametrization of lines that stacks up 2D planes.
|
---|
| 314 | % Each plane corresponds to mappings of lines intersecting a given
|
---|
| 315 | % point on the line segment.}
|
---|
| 316 | %\label{fig:vls}
|
---|
| 317 | %\end{figure}
|
---|
| 318 |
|
---|
| 319 | In 2D lines intersecting a line segment form a two-dimensional
|
---|
| 320 | problem-relevant line set. Thus for the 2D case the ${\cal L}_R$ is a
|
---|
| 321 | two-dimensional subset of 2D line space.
|
---|
| 322 |
|
---|
| 323 |
|
---|
| 324 | \subsection{Visibility from a region}
|
---|
| 325 |
|
---|
| 326 | Visibility from a region (or from-region visibility) involves the
|
---|
| 327 | most general visibility problems. In 3D the ${\cal L}_R$ is a 4D
|
---|
| 328 | subset of the 4D line space. In 2D the ${\cal L}_R$ is a 2D subset of
|
---|
| 329 | the 2D line space. Consequently, in the presented classification
|
---|
| 330 | visibility from a region in 2D is equivalent to visibility from a line
|
---|
| 331 | segment in 2D.
|
---|
| 332 |
|
---|
| 333 | A typical visibility from a region problem is the problem of {\em
|
---|
| 334 | region-to-region} visibility that aims to determine if the two given
|
---|
| 335 | regions in the scene are visible, invisible, or partially visible (see
|
---|
| 336 | %Figure~\ref{fig:vfr}). Another visibility from region problem is the
|
---|
| 337 | computation of a {\em potentially visible set} (PVS) with respect to a
|
---|
| 338 | given view cell. The PVS consists of a set of objects that are
|
---|
| 339 | potentially visible from any point inside the view cell. Further
|
---|
| 340 | visibility from a region problems include computing form factors
|
---|
| 341 | between two polygons, soft shadow algorithms or discontinuity meshing.
|
---|
| 342 |
|
---|
| 343 |
|
---|
| 344 | %\begin{figure}[htb]
|
---|
| 345 | %\centerline{
|
---|
| 346 | %\includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/vfr}}
|
---|
| 347 | %\caption{Visibility from a region --- an example of the region-to-region
|
---|
| 348 | % visibility. Two regions and two occluders $A$, $B$
|
---|
| 349 | % in a 2D scene. In line space the region-to-region visibility can be
|
---|
| 350 | % solved by subtracting the sets of lines $A^*$ and $B^*$
|
---|
| 351 | % intersecting objects $A$ and $B$ from the lines intersecting both
|
---|
| 352 | % regions.}
|
---|
| 353 | %\label{fig:vfr}
|
---|
| 354 | %\end{figure}
|
---|
| 355 |
|
---|
| 356 |
|
---|
| 357 | \subsection{Global visibility}
|
---|
| 358 |
|
---|
| 359 | According to the classification the global visibility problems can be
|
---|
| 360 | seen as an extension of the from-region visibility problems. The
|
---|
| 361 | dimension of the problem-relevant line set is the same ($k=2$ for 2D
|
---|
| 362 | and $k=4$ for 3D scenes). Nevertheless, the global visibility problems
|
---|
| 363 | typically deal with much larger set of rays, i.e. all rays that
|
---|
| 364 | penetrate the scene. Additionally, there is no given set of reference
|
---|
| 365 | points from which visibility is studied and hence there is no given
|
---|
| 366 | priority ordering of objects along each particular line from ${\cal
|
---|
| 367 | L}_R$. Therefore an additional parameter must be used to describe
|
---|
| 368 | visibility (visible object) along each ray.
|
---|
| 369 |
|
---|
| 370 |
|
---|
| 371 | \subsection{Summary}
|
---|
| 372 |
|
---|
| 373 | The classification of visibility problems according to the dimension
|
---|
| 374 | of the problem-relevant line set is summarized in
|
---|
| 375 | Table~\ref{table:classification3D}. This classification provides
|
---|
| 376 | means for understanding how difficult it is to compute, describe, and
|
---|
| 377 | maintain visibility for a particular class of problems. For example a
|
---|
| 378 | data structure representing the visible or occluded parts of the scene
|
---|
| 379 | for the visibility from a point problem needs to partition a 2D ${\cal
|
---|
| 380 | L}_R$ into visible and occluded sets of lines. This observation
|
---|
| 381 | conforms with the traditional visible surface algorithms -- they
|
---|
| 382 | partition a 2D viewport into empty/nonempty regions and associate each
|
---|
| 383 | nonempty regions (pixels) with a visible object. In this case the
|
---|
| 384 | viewport represents the ${\cal L}_R$ as each point of the viewport
|
---|
| 385 | corresponds to a line through that point. To analytically describe
|
---|
| 386 | visibility from a region a subdivision of 4D ${\cal L}_R$ should be
|
---|
| 387 | performed. This is much more difficult than the 2D
|
---|
| 388 | subdivision. Moreover the description of visibility from a region
|
---|
| 389 | involves non-linear subdivisions of both primal space and line space
|
---|
| 390 | even for polygonal scenes~\cite{Teller:1992:CAA,Durand99-phd}.
|
---|
| 391 |
|
---|
| 392 | \begin{table*}[htb]
|
---|
| 393 | \begin{small}
|
---|
| 394 | \begin{center}
|
---|
| 395 | \begin{tabular}{|l|c|l|}
|
---|
| 396 | \hline
|
---|
| 397 | \multicolumn{3}{|c|}{2D} \\
|
---|
| 398 | \hline
|
---|
| 399 | \mc{domain} & $d({\cal L}_R)$ & \mc{problems} \\
|
---|
| 400 | \hline
|
---|
| 401 | \hline
|
---|
| 402 | \begin{tabular}{l}visibility along a line\end{tabular} & 0 & \begin{tabular}{l}ray shooting, point-to-point visibility\end{tabular}\\
|
---|
| 403 | \hline
|
---|
| 404 | \begin{tabular}{l}visibility from a point\end{tabular} & 1 & \begin{tabular}{l}view around a point, point-to-region visibility\end{tabular}\\
|
---|
| 405 | \hline
|
---|
| 406 | \begin{tabular}{l} visibility from a line segment \\ visibility from region \\ global visibility \end{tabular}
|
---|
| 407 | & 2 & \begin{tabular}{l} region-to-region visibility, PVS \end{tabular}\\
|
---|
| 408 | \hline
|
---|
| 409 | \hline
|
---|
| 410 | \multicolumn{3}{|c|}{3D} \\
|
---|
| 411 | \hline
|
---|
| 412 | \mc{domain} & $d({\cal L}_R)$ & \mc{problems} \\
|
---|
| 413 | \hline
|
---|
| 414 | \hline
|
---|
| 415 | \begin{tabular}{l}visibility along a line\end{tabular} & 0 & \begin{tabular}{l} ray shooting, point-to-point visibility \end{tabular}\\
|
---|
| 416 | \hline
|
---|
| 417 | \begin{tabular}{l}from point in a surface\end{tabular} & 1 & \begin{tabular}{l} see visibility from point in 2D \end{tabular}\\
|
---|
| 418 | \hline
|
---|
| 419 | \begin{tabular}{l}visibility from a point\end{tabular} & 2 & \begin{tabular}{l} visible (hidden) surfaces, point-to-region visibility,\\
|
---|
| 420 | visibility map, hard shadows
|
---|
| 421 | \end{tabular} \\
|
---|
| 422 | \hline
|
---|
| 423 | \begin{tabular}{l}visibility from a line segment\end{tabular} & 3 & \begin{tabular}{l} segment-to-region visibility (rare) \end{tabular}\\
|
---|
| 424 | \hline
|
---|
| 425 | \begin{tabular}{l}visibility from a region\\global visibility\end{tabular} & 4 & \begin{tabular}{l} region-region visibility, PVS, aspect graph,\\
|
---|
| 426 | soft shadows, discontinuity meshing
|
---|
| 427 | \end{tabular} \\
|
---|
| 428 |
|
---|
| 429 | \hline
|
---|
| 430 | \end{tabular}
|
---|
| 431 | \end{center}
|
---|
| 432 | \end{small}
|
---|
| 433 | \caption{Classification of visibility problems in 2D and 3D according
|
---|
| 434 | to the dimension of the problem-relevant line set.}
|
---|
| 435 | \label{table:classification3D}
|
---|
| 436 | \end{table*}
|
---|
| 437 |
|
---|
| 438 |
|
---|
| 439 |
|
---|
| 440 |
|
---|
| 441 |
|
---|
| 442 | \section{Classification of visibility algorithms}
|
---|
| 443 |
|
---|
| 444 |
|
---|
| 445 | The taxonomy of visibility problems groups similar visibility problems
|
---|
| 446 | in the same class. A visibility problem can be solved by means of
|
---|
| 447 | various visibility algorithms. A visibility algorithm poses further
|
---|
| 448 | restrictions on the input and output data. These restrictions can be
|
---|
| 449 | seen as a more precise definition of the visibility problem that is
|
---|
| 450 | solved by the algorithm.
|
---|
| 451 |
|
---|
| 452 | Above we classified visibility problems according to the problem
|
---|
| 453 | domain and the desired answers. In this section we provide a
|
---|
| 454 | classification of visibility algorithms according to other
|
---|
| 455 | important criteria characterizing a particular visibility algorithm.
|
---|
| 456 |
|
---|
| 457 |
|
---|
| 458 | \subsection{Scene restrictions}
|
---|
| 459 | \label{sec:scene_restrictions}
|
---|
| 460 |
|
---|
| 461 | Visibility algorithms can be classified according to the restrictions
|
---|
| 462 | they pose on the scene description. The type of the scene description
|
---|
| 463 | influences the difficulty of solving the given problem: it is simpler
|
---|
| 464 | to implement an algorithm computing a visibility map for scenes
|
---|
| 465 | consisting of triangles than for scenes with NURBS surfaces. We list
|
---|
| 466 | common restrictions on the scene primitives suitable for visibility
|
---|
| 467 | computations:
|
---|
| 468 |
|
---|
| 469 |
|
---|
| 470 | \begin{itemize}
|
---|
| 471 | \item
|
---|
| 472 | triangles, convex polygons, concave polygons,
|
---|
| 473 |
|
---|
| 474 | \item
|
---|
| 475 | volumetric data,
|
---|
| 476 |
|
---|
| 477 | \item
|
---|
| 478 | points,
|
---|
| 479 |
|
---|
| 480 | \item
|
---|
| 481 | general parametric, implicit, or procedural surfaces.
|
---|
| 482 |
|
---|
| 483 | \end{itemize}
|
---|
| 484 |
|
---|
| 485 | Some attributes of scenes objects further increase the complexity of the visibility computation:
|
---|
| 486 |
|
---|
| 487 | \begin{itemize}
|
---|
| 488 |
|
---|
| 489 | \item
|
---|
| 490 | transparent objects,
|
---|
| 491 |
|
---|
| 492 | \item
|
---|
| 493 | dynamic objects.
|
---|
| 494 |
|
---|
| 495 | \end{itemize}
|
---|
| 496 |
|
---|
| 497 | The majority of analytic visibility algorithms deals with static
|
---|
| 498 | polygonal scenes without transparency. The polygons are often
|
---|
| 499 | subdivided into triangles for easier manipulation and representation.
|
---|
| 500 |
|
---|
| 501 | \subsection{Accuracy}
|
---|
| 502 | \label{sec:accuracy}
|
---|
| 503 |
|
---|
| 504 | Visibility algorithms can be classified according to the accuracy of
|
---|
| 505 | the result as:
|
---|
| 506 |
|
---|
| 507 | \begin{itemize}
|
---|
| 508 | \item exact,
|
---|
| 509 | \item conservative,
|
---|
| 510 | \item aggressive,
|
---|
| 511 | \item approximate.
|
---|
| 512 | \end{itemize}
|
---|
| 513 |
|
---|
| 514 |
|
---|
| 515 | An exact algorithm provides an exact analytic result for the given
|
---|
| 516 | problem (in practice however this result is typically influenced by
|
---|
| 517 | the finite precision of the floating point arithmetics). A
|
---|
| 518 | conservative algorithm overestimates visibility, i.e. it never
|
---|
| 519 | misses any visible object, surface or point. An aggressive algorithm
|
---|
| 520 | always underestimates visibility, i.e. it never reports an invisible
|
---|
| 521 | object, surface or point as visible. An approximate algorithm
|
---|
| 522 | provides only an approximation of the result, i.e. it can overestimate
|
---|
| 523 | visibility for one input and underestimate visibility for another
|
---|
| 524 | input.
|
---|
| 525 |
|
---|
| 526 | The classification according to the accuracy is best illustrated on
|
---|
| 527 | computing PVS: an exact algorithm computes an exact PVS. A
|
---|
| 528 | conservative algorithm computes a superset of the exact PVS. An
|
---|
| 529 | aggressive algorithm determines a subset of the exact PVS. An
|
---|
| 530 | approximate algorithm computes an approximation to the exact PVS that
|
---|
| 531 | is neither its subset or its superset for all possible inputs.
|
---|
| 532 |
|
---|
| 533 | A more precise quality measure of algorithms computing PVSs can be
|
---|
| 534 | expressed by the {\em relative overestimation} and the {\em relative
|
---|
| 535 | underestimation} of the PVS with respect to the exact PVS. We can
|
---|
| 536 | define a quality measure of an algorithm $A$ on input $I$ as a tuple
|
---|
| 537 | $\mbi{Q}^A(I)$:
|
---|
| 538 |
|
---|
| 539 | \begin{eqnarray}
|
---|
| 540 | \mbi{Q}^A(I) & = & (Q^A_o(I), Q^A_u(I)), \qquad I \in {\cal D} \\
|
---|
| 541 | Q^A_o(I) & = & {|S^A(I) \setminus S^{\cal E}(I)| \over |S^{\cal E}(I)|} \\
|
---|
| 542 | Q^A_u(I) & = & {|S^{\cal E}(I) \setminus S^A(I) | \over |S^{\cal E}(I)|}
|
---|
| 543 | \end{eqnarray}
|
---|
| 544 |
|
---|
| 545 | where $I$ is an input from the input domain ${\cal D}$, $S^A(I)$ is
|
---|
| 546 | the PVS determined by the algorithm $A$ for input $I$ and $S^{\cal
|
---|
| 547 | E}(I)$ is the exact PVS for the given input. $Q^A_o(I)$ expresses the
|
---|
| 548 | {\em relative overestimation} of the PVS, $Q^A_u(I)$ is the {\em
|
---|
| 549 | relative underestimation}.
|
---|
| 550 |
|
---|
| 551 | The expected quality of the algorithm over all possible inputs can be
|
---|
| 552 | given as:
|
---|
| 553 |
|
---|
| 554 | \begin{eqnarray}
|
---|
| 555 | Q^A & = & E[\| \mbi{Q}^A(I) \|] \\
|
---|
| 556 | & = & \sum_{\forall I \in {\cal D}} f(I).\sqrt{Q^A_o(I)^2 + Q^A_o(I)^2}
|
---|
| 557 | \end{eqnarray}
|
---|
| 558 |
|
---|
| 559 | where f(I) is the probability density function expressing the
|
---|
| 560 | probability of occurrence of input $I$. The quality measure
|
---|
| 561 | $\mbi{Q}^A(I)$ can be used to classify a PVS algorithm into one of the
|
---|
| 562 | four accuracy classes according to Section~\ref{sec:accuracy}:
|
---|
| 563 |
|
---|
| 564 | \begin{enumerate}
|
---|
| 565 | \item exact\\
|
---|
| 566 | $\forall I \in {\cal D} :Q_o^A(I) = 0 \wedge Q_u^A(I) = 0$
|
---|
| 567 | \item conservative\\
|
---|
| 568 | $\forall I \in {\cal D} : Q_o^A(I) \geq 0 \wedge Q_u^A(I) = 0$
|
---|
| 569 | \item aggressive \\
|
---|
| 570 | $\forall I \in {\cal D} : Q_o^A(I) = 0 \wedge Q_u^A(I) \geq 0$
|
---|
| 571 | \item approximate \\
|
---|
| 572 | $\qquad \exists I_j, I_k \in {\cal D}: Q_o^A(I_j) > 0 \wedge Q_u^A(I_k) > 0$
|
---|
| 573 | \end{enumerate}
|
---|
| 574 |
|
---|
| 575 |
|
---|
| 576 |
|
---|
| 577 | \subsection{Solution space}
|
---|
| 578 |
|
---|
| 579 | \label{sec:solspace}
|
---|
| 580 |
|
---|
| 581 | The solution space is the domain in which the algorithm determines
|
---|
| 582 | the desired result. Note that the solution space does not need to
|
---|
| 583 | match the domain of the result.
|
---|
| 584 |
|
---|
| 585 | The algorithms can be classified as:
|
---|
| 586 |
|
---|
| 587 | \begin{itemize}
|
---|
| 588 | \item discrete,
|
---|
| 589 | \item continuous,
|
---|
| 590 | \item hybrid.
|
---|
| 591 | \end{itemize}
|
---|
| 592 |
|
---|
| 593 | A discrete algorithm solves the problem using a discrete solution
|
---|
| 594 | space; the solution is typically an approximation of the result. A
|
---|
| 595 | continuous algorithm works in a continuous domain and often computes an
|
---|
| 596 | analytic solution to the given problem. A hybrid algorithm uses both
|
---|
| 597 | the discrete and the continuous solution space.
|
---|
| 598 |
|
---|
| 599 | The classification according to the solution space is easily
|
---|
| 600 | demonstrated on visible surface algorithms: The
|
---|
| 601 | z-buffer~\cite{Catmull:1975:CDC} is a common example of a discrete
|
---|
| 602 | algorithm. The Weiler-Atherton algorithm~\cite{Weiler:1977:HSR} is an
|
---|
| 603 | example of a continuous one. A hybrid solution space is used by
|
---|
| 604 | scan-line algorithms that solve the problem in discrete steps
|
---|
| 605 | (scan-lines) and for each step they provide a continuous solution
|
---|
| 606 | (spans).
|
---|
| 607 |
|
---|
| 608 | Further classification reflects the semantics of the solution
|
---|
| 609 | space. According to this criteria we can classify the algorithms as:
|
---|
| 610 |
|
---|
| 611 | \begin{itemize}
|
---|
| 612 | \item primal space (object space),
|
---|
| 613 | \item line space,
|
---|
| 614 | \begin{itemize}
|
---|
| 615 | \item image space,
|
---|
| 616 | \item general,
|
---|
| 617 | \end{itemize}
|
---|
| 618 | \item hybrid.
|
---|
| 619 | \end{itemize}
|
---|
| 620 |
|
---|
| 621 | A primal space algorithm solves the problem by studying the
|
---|
| 622 | visibility between objects without a transformation to a different
|
---|
| 623 | solution space. A line space algorithm studies visibility using a
|
---|
| 624 | transformation of the problem to line space. Image space algorithms
|
---|
| 625 | can be seen as an important subclass of line space algorithms for
|
---|
| 626 | solving visibility from a point problems in 3D. These algorithms cover
|
---|
| 627 | all visible surface algorithms and many visibility culling
|
---|
| 628 | algorithms. They solve visibility in a given image plane that
|
---|
| 629 | represents the problem-relevant line set ${\cal L}_R$ --- each ray
|
---|
| 630 | originating at the viewpoint corresponds to a point in the image plane.
|
---|
| 631 |
|
---|
| 632 | The described classification differs from the sometimes mentioned
|
---|
| 633 | understanding of image space and object space algorithms that
|
---|
| 634 | incorrectly considers all image space algorithms discrete and all
|
---|
| 635 | object space algorithms continuous.
|
---|
| 636 |
|
---|
| 637 |
|
---|
| 638 | %*****************************************************************************
|
---|
| 639 |
|
---|
| 640 |
|
---|
| 641 |
|
---|
| 642 | \section{Summary}
|
---|
| 643 |
|
---|
| 644 | The presented taxonomy classifies visibility problems independently of
|
---|
| 645 | their target application. The classification should help to understand
|
---|
| 646 | the nature of the given problem and it should assist in finding
|
---|
| 647 | relationships between visibility problems and algorithms in different
|
---|
| 648 | application areas. The algorithms address the following classes of
|
---|
| 649 | visibility problems:
|
---|
| 650 |
|
---|
| 651 | \begin{itemize}
|
---|
| 652 | \item Visibility from a point in 3D $d({\cal L}_R)=2$.
|
---|
| 653 | \item Global visibility in 3D $d({\cal L}_R)=4$.
|
---|
| 654 | \item Visibility from a region in 3D, $d({\cal L}_R)=4$.
|
---|
| 655 | \end{itemize}
|
---|
| 656 |
|
---|
| 657 | This chapter discussed several important criteria for the
|
---|
| 658 | classification of visibility algorithms. This classification can be
|
---|
| 659 | seen as a finer structuring of the taxonomy of visibility problems. We
|
---|
| 660 | discussed important steps in the design of a visibility algorithm that
|
---|
| 661 | should also assist in understanding the quality of a visibility
|
---|
| 662 | algorithm. According to the classification the visibility algorithms
|
---|
| 663 | described later in the report address algorithms with the following
|
---|
| 664 | properties:
|
---|
| 665 |
|
---|
| 666 | \begin{itemize}
|
---|
| 667 | \item Domain:
|
---|
| 668 | \begin{itemize}
|
---|
| 669 | \item viewpoint (online visibility culling),
|
---|
| 670 | \item global visibility (global visibility sampling)
|
---|
| 671 | \item polygon or polyhedron (mutual visibility verification)
|
---|
| 672 | \end{itemize}
|
---|
| 673 | \item Scene restrictions (occluders):
|
---|
| 674 | \begin{itemize}
|
---|
| 675 | \item meshes consisting of convex polygons
|
---|
| 676 | \end{itemize}
|
---|
| 677 | \item Scene restrictions (group objects):
|
---|
| 678 | \begin{itemize}
|
---|
| 679 | \item bounding boxes
|
---|
| 680 | \end{itemize}
|
---|
| 681 | \item Output:
|
---|
| 682 | \begin{itemize}
|
---|
| 683 | \item PVS
|
---|
| 684 | \end{itemize}
|
---|
| 685 | \item Accuracy:
|
---|
| 686 | \begin{itemize}
|
---|
| 687 | \item conservative
|
---|
| 688 | \item exact
|
---|
| 689 | \item aggresive
|
---|
| 690 | \end{itemize}
|
---|
| 691 | \item Solution space:
|
---|
| 692 | \begin{itemize}
|
---|
| 693 | \item discrete (online visibility culling, global visibility sampling, conservative and approximate algorithm from the mutual visibility verification)
|
---|
| 694 | \item continuous (exact algorithm from mutual visibility verification)
|
---|
| 695 | \end{itemize}
|
---|
| 696 | \item Solution space data structures: viewport (online visibility culling), ray stack (global visibility sampling, conservative and approximate algorithm from the mutual visibility verification), BSP tree (exact algorithm from the mutual visibility verification)
|
---|
| 697 | \item Use of coherence of visibility:
|
---|
| 698 | \begin{itemize}
|
---|
| 699 | \item spatial coherence (all algorithms)
|
---|
| 700 | \item temporal coherence (online visibility culling)
|
---|
| 701 | \end{itemize}
|
---|
| 702 | \item Output sensitivity: expected in practice (all algorithms)
|
---|
| 703 | \item Acceleration data structure: kD-tree (all algorithms)
|
---|
| 704 | \item Use of graphics hardware: online visibility culling
|
---|
| 705 | \end{itemize}
|
---|
| 706 |
|
---|
| 707 |
|
---|