source: GTP/trunk/Lib/Vis/Preprocessing/manual/integration.txt @ 2066

Revision 2066, 27.9 KB checked in by mattausch, 17 years ago (diff)

worked on integration manual

Line 
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
492D, \m25d, or 3D scenes. The actual problem domain is given by
50restricting the set of rays for which visibility should be
51determined.
52
53Below we list common problem domains used and the corresponding domain
54restrictions:
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
106of the scene, but the impact of the restrictions differs depending on
107the scene dimension. For example, visibility from a polygon is
108equivalent to visibility from a (polygonal) region in 2D, but not in
1093D.
110
111%*****************************************************************************
112
113\section{Dimension of the problem-relevant line set}
114
115 The six domains of visibility problems stated in
116Section~\ref{sec:prob_domain} can be characterized by the {\em
117problem-relevant line set} denoted ${\cal L}_R$. We give a
118classification of visibility problems according to the dimension of
119the problem-relevant line set. We discuss why this classification is
120important for understanding the nature of the given visibility problem
121and for identifying its relation to other problems.
122
123
124 For the following discussion we assume that a line in {\em primal
125space} can be mapped to a point in {\em line space}. For purposes of
126the classification we define the line space as a vector space where a
127point corresponds to a line in the primal space\footnote{A classical
128mathematical definition says: Line space is a direct product of two
129Hilbert spaces~\cite{Weisstein:1999:CCE}. However, this definition
130differs from the common understanding of line space in computer
131graphics~\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
138the corresponding set of lines is two-dimensional. There is a natural
139duality between lines and points in 2D. For example a line expressed
140as: $l:y=ax+c$ is dual to a point $p=(-c,a)$. This particular duality
141cannot handle vertical lines. %See Figure~\ref{fig:duality2d} for an
142example of other dual mappings in the plane.  To avoid the singularity
143in 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
145P}^2$~\cite{Stolfi:1991:OPG}. Multiplying $p_l$ by a non-zero scalar
146we obtain a vector that represents the same line $l$. More details
147about this singularity-free mapping will be discussed in
148Chapter~\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
163line and the corresponding line space is two-dimensional. The
164problem-relevant line set ${\cal L}_R$ then forms a $k$-dimensional
165subset of ${\cal P}^2$, where $0\leq k \leq 2$. An illustration of the
166concept 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
187Lines in 3D form a four-parametric space~\cite{p-rsls-97}. A line
188intersecting a given scene can be described by two points on a sphere
189enclosing the scene. Since the surface of the sphere is a two
190parametric space, we need four parameters to describe the line.
191
192 The {\em two plane parametrization} of 3D lines describes a line by
193points of intersection with the given two
194planes~\cite{Gu:1997:PGT}. This parametrization exhibits a singularity
195since it cannot describe lines parallel to these planes. See
196%Figure~\ref{fig:3dlines} for illustrations of the spherical and the
197two 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
211coordinates}. \plucker coordinates of an oriented 3D line are a six
212tuple that can be understood as a point in 5D oriented projective
213space~\cite{Stolfi:1991:OPG}. There are six coordinates in \plucker
214representation of a line although we know that the ${\cal L}_R$ is
215four-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
228singularity and preserve some linearities: lines intersecting a set of
229lines in 3D correspond to an intersection of 5D hyperplanes. More
230details on \plucker coordinates will be discussed in
231Chapter~\ref{chap:analysis} and Chapter~\ref{chap:mutual} where they
232are used to solve the from-region visibility problem.
233
234  To sum up: In 3D there are four degrees of freedom in the
235description of a line and thus the corresponding line space is
236four-dimensional. Fixing certain line parameters (e.g. direction) the
237problem-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
244line. The problem-relevant line set is zero-dimensional, i.e. it is
245fully specified by the given line. A typical example of a visibility
246along a line problem is {\em ray shooting}.
247
248 A similar problem to ray shooting is the {\em point-to-point}
249visibility.  The  point-to-point visibility determines whether the
250line segment between two points is occluded, i.e. it has an
251intersection with an opaque object in the scene. Point-to-point
252visibility provides a visibility classification (answer 1a), whereas
253ray shooting determines a visible object (answer 2a) and/or a point of
254intersection (answer 3a). Note that the {\em point-to-point}
255visibility can be solved easily by means of ray shooting. Another
256constructive visibility along a line problem is determining the {\em
257%maximal free line segments} on a given line. See Figure~\ref{fig:val}
258for 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
271parameters. For example the lines can be expressed by an intersection
272with a unit sphere centered at the given point. The most common
273parametrization describes a line by a point of intersection with a
274given 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
286the 4D line space. In 2D the ${\cal L}_R$ is a 1D subset of the 2D
287line space. The typical visibility from a point problem is the visible
288surface determination. Due to its importance the visible surface
289determination is covered by the majority of existing visibility
290algorithms. Other visibility from a point problem is the construction
291of the {\em visibility map} or the {\em point-to-region visibility}
292that classifies a region as visible, invisible, or partially visible
293with 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
299parameters. One parameter fixes the intersection of the line with the
300segment the other two express the direction of the line. The
301problem-relevant line set ${\cal L}_R$ is three-dimensional and it can
302be understood as a 2D cross section of ${\cal L}_R$  swept according
303to 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
319In 2D lines intersecting a line segment form a two-dimensional
320problem-relevant line set. Thus for the 2D case the ${\cal L}_R$ is a
321two-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
327most general visibility problems. In 3D the ${\cal L}_R$ is a 4D
328subset of the 4D line space. In 2D the ${\cal L}_R$ is a 2D subset of
329the 2D line space. Consequently, in the presented classification
330visibility from a region in 2D is equivalent to visibility from a line
331segment in 2D.
332
333 A typical visibility from a region problem is the problem of {\em
334region-to-region} visibility that aims to determine if the two given
335regions in the scene are visible, invisible, or partially visible (see
336%Figure~\ref{fig:vfr}). Another visibility from region problem is the
337computation of a {\em potentially visible set} (PVS) with respect to a
338given view cell. The PVS consists of a set of objects that are
339potentially visible from any point inside the view cell. Further
340visibility from a region problems include computing form factors
341between 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
360seen as an extension of the from-region visibility problems. The
361dimension of the problem-relevant line set is the same ($k=2$ for 2D
362and $k=4$ for 3D scenes). Nevertheless, the global visibility problems
363typically deal with much larger set of rays, i.e.  all rays that
364penetrate the scene. Additionally, there is no given set of reference
365points from which visibility is studied and hence there is no given
366priority ordering of objects along each particular line from ${\cal
367L}_R$. Therefore an additional parameter must be used to describe
368visibility (visible object) along each ray.
369
370
371\subsection{Summary}
372
373 The classification of visibility problems according to the dimension
374of the problem-relevant line set is summarized in
375Table~\ref{table:classification3D}.  This classification provides
376means for understanding how difficult it is to compute, describe, and
377maintain visibility for a particular class of problems. For example a
378data structure representing the visible or occluded parts of the scene
379for the visibility from a point problem needs to partition a 2D ${\cal
380L}_R$ into visible and occluded sets of lines. This observation
381conforms with the traditional visible surface algorithms -- they
382partition a 2D viewport into empty/nonempty regions and associate each
383nonempty regions (pixels) with a visible object. In this case the
384viewport represents the ${\cal L}_R$ as each point of the viewport
385corresponds to a line through that point. To analytically describe
386visibility from a region a subdivision of 4D ${\cal L}_R$ should be
387performed. This is much more difficult than the 2D
388subdivision. Moreover the description of visibility from a region
389involves non-linear subdivisions of both primal space and line space
390even 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
434to 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
445The taxonomy of visibility problems groups similar visibility problems
446in the same class.  A visibility problem can be solved by means of
447various visibility algorithms. A visibility algorithm poses further
448restrictions on the input and output data. These restrictions can be
449seen as a more precise definition of the visibility problem that is
450solved by the algorithm.
451
452 Above we classified visibility problems according to the problem
453domain and the desired answers. In this section we provide a
454classification of visibility algorithms according to other
455important criteria characterizing a particular visibility algorithm.
456
457
458\subsection{Scene restrictions}
459\label{sec:scene_restrictions}
460
461Visibility algorithms can be classified according to the restrictions
462they pose on the scene description.  The type of the scene description
463influences the difficulty of solving the given problem: it is simpler
464to implement an algorithm computing a visibility map for scenes
465consisting of triangles than for scenes with NURBS surfaces. We list
466common restrictions on the scene primitives suitable for visibility
467computations:
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
485Some 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
497The majority of analytic visibility algorithms deals with static
498polygonal scenes without transparency. The polygons are often
499subdivided 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
505the 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
516problem (in practice however this result is typically influenced by
517the finite precision of the floating point arithmetics). A
518conservative algorithm overestimates visibility, i.e. it never
519misses any visible object, surface or point. An aggressive algorithm
520always underestimates visibility, i.e. it never reports an invisible
521object, surface or point as visible.  An approximate algorithm
522provides only an approximation of the result, i.e. it can overestimate
523visibility for one input and underestimate visibility for another
524input.
525
526 The classification according to the accuracy is best illustrated on
527computing PVS: an exact algorithm computes an exact PVS. A
528conservative algorithm computes a superset of the exact PVS.  An
529aggressive algorithm determines a subset of the exact PVS.  An
530approximate algorithm computes an approximation to the exact PVS that
531is neither its subset or its superset for all possible inputs.
532
533 A more precise quality measure of algorithms computing PVSs can be
534expressed by the {\em relative overestimation} and the {\em relative
535underestimation} of the PVS with respect to the exact PVS.  We can
536define 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
545where $I$ is an input from the input domain ${\cal D}$, $S^A(I)$ is
546the PVS determined by the algorithm $A$ for input $I$ and $S^{\cal
547E}(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
549relative underestimation}.
550
551The expected quality of the algorithm over all possible inputs can be
552given as:
553
554\begin{eqnarray}
555Q^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
559where f(I) is the probability density function expressing the
560probability 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
562four 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
582the desired result. Note that the solution space does not need to
583match the domain of the result.
584
585The 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
594space; the solution is typically an approximation of the result. A
595continuous algorithm works in a continuous domain and often computes an
596analytic solution to the given problem. A hybrid algorithm uses both
597the discrete and the continuous solution space.
598
599 The classification according to the solution space is easily
600demonstrated on visible surface algorithms: The
601z-buffer~\cite{Catmull:1975:CDC} is a common example of a discrete
602algorithm. The Weiler-Atherton algorithm~\cite{Weiler:1977:HSR} is an
603example of a continuous one. A hybrid solution space is used by
604scan-line algorithms that solve the problem in discrete steps
605(scan-lines) and for each step they provide a continuous solution
606(spans).
607
608Further classification reflects the semantics of the solution
609space. 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
622visibility between objects without a transformation to a different
623solution space. A line space algorithm studies visibility using a
624transformation of the problem to line space. Image space algorithms
625can be seen as an important subclass of line space algorithms for
626solving visibility from a point problems in 3D. These algorithms cover
627all visible surface algorithms and many visibility culling
628algorithms. They solve visibility in a given image plane that
629represents the problem-relevant line set ${\cal L}_R$ --- each ray
630originating at the viewpoint corresponds to a point in the image plane.
631
632 The described classification differs from the sometimes mentioned
633understanding of image space and object space algorithms that
634incorrectly considers all image space algorithms discrete and all
635object space algorithms continuous.
636
637
638%*****************************************************************************
639
640
641
642\section{Summary}
643
644The presented taxonomy classifies visibility problems independently of
645their target application. The classification should help to understand
646the nature of the given problem and it should assist in finding
647relationships between visibility problems and algorithms in different
648application areas.  The algorithms address the following classes of
649visibility 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
658classification of visibility algorithms. This classification can be
659seen as a finer structuring of the taxonomy of visibility problems. We
660discussed important steps in the design of a visibility algorithm that
661should also assist in understanding the quality of a visibility
662algorithm. According to the classification the visibility algorithms
663described later in the report address algorithms with the following
664properties:
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
Note: See TracBrowser for help on using the repository browser.