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

Revision 277, 27.9 KB checked in by bittner, 19 years ago (diff)

changes in the structure: renamed tools to algorithms

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