source: trunk/VUT/doc/SciReport/preprocessing.tex @ 287

Revision 287, 7.5 KB checked in by mattausch, 19 years ago (diff)
Line 
1\chapter{Visibility Preprocessing}
2
3
4\section{Introduction}
5
6
7\section{Related Work}
8
9
10\section{Overview of Visibility Preprocessor}
11
12The proposed visibility preprocessing framework consists of two major
13steps.
14\begin{itemize}
15\item The first step is an aggresive visibility sampling which gives
16initial estimate about global visibility in the scene. The sampling
17itself involves several strategies which will be described in
18section~\ref{sec:sampling}. The imporant property of the aggresive
19sampling step is that it provides a fast progressive solution to
20global visibility and thus it can be easily integrated into the
21game development cycle.
22
23\item The second step is visibility verification. This step turns the
24previous aggresive visibility solution into either exact, conservative
25or error bound aggresive solution. The choice of the particular
26verifier is left on the user in order to select the best for a
27particular scene, application context and time constrains. For
28example, in scenes like a forest an error bound aggresive visibility
29can be the best compromise between the resulting size of the PVS (and
30framerate) and the visual quality. The exact or conservative algorithm
31can however be chosen for urban scenes where of even small objects can
32be more distructing for the user.
33\end{itemize}
34
35
36\section{Aggresive Global Visibility Sampling}
37
38In traditional visibility preprocessing the view space is
39subdivided into view cells and for each view cell the set of visible
40objects --- potentially visible set (PVS) is computed. This framewoirk
41has bee used for conservative, aggresive and exact algorithms.
42
43We propose a different strategy which has several advantages for
44sampling based aggresive visibility preprocessing. The stategy is
45based on the following fundamental ideas:
46\begin{itemize}
47\item Replace the roles of view cells and objects
48\item Compute progressive global visibility instead of sequential from-region visibility
49\end{itemize}
50
51Both of these points are addressed below in more detail.
52
53\subsection{From-object based visibility}
54
55Our framework is based on the idea of sampling visibility by casting
56casting rays through the scene and collecting their contributions. A
57visibility sample is computed by casting a ray from an object towards
58the view cells and computing the nearest intersection with the scene
59objects. All view cells pierced by the ray segment can see the object and
60thus the object can be added to their PVS. If the ray is terminated at
61another scene object the PVS of the pierced view cells can also be
62extended by this terminating object. Thus a single ray can make a
63number of contributions to the progressively computed PVSs. A ray
64sample piercing $n$ view cells which is bound by two distinct objects
65contributes by at most $2*n$ entries to the current PVSs. Appart from
66this performance benefit there is also a benefit in terms of the
67sampling density: Assuming that the view cells are usually much larger
68than the objects (which is typically the case) starting the sampling
69deterministically from the objects increases the probability of small
70objects being captured in the PVS.
71
72At this phase of the computation we not only start the samples from
73the objects, but we also store the PVS information centered at the
74objects. Instead of storing a PVSs consting of objects visible from
75view cells, every object maintains a PVS consisting of potentially
76visible view cells. While these representations contain exactly the
77same information as we shall see later the object centered PVS is
78better suited for the importance sampling phase as well as the
79visibility verification phase.
80
81
82\subsection{Basic Randomized Sampling}
83
84
85The first phase of the sampling works as follows: At every pass of the
86algorithm visits scene objects sequentially. For every scene object we
87randomly choose a point on its surface. Then a ray is cast from the
88selected point according to the randomly chosen direction. We use a
89uniform distribution of the ray directions with respect to the
90halfspace given by the surface normal. Using this strategy the samples
91at deterministicaly placed at every object, with a randomization of
92the location on the object surface. The uniformly distributed
93direction is a simple and fast strategy to gain initial visibility
94information.
95
96
97The described algorithm accounts for the irregular distribution of the
98objects: more samples are placed at locations containing more
99objects. Additionally every object is sampled many times depending on
100the number of passes in which this sampling strategy is applied. This
101increases the chance of even a small object being captured in the PVS
102of the view cells from which it is visible.
103
104
105\subsection{Accounting for View Cell Distribution}
106
107The first modification to the basic algorithm accounts for
108irregular distribution of the view cells. Such a case in common for
109example in urban scenes where the view cells are mostly distributed in
110a horizontal direction and more view cells are placed at denser parts
111of the city. The modification involves replacing the uniformly
112distributed ray direction by direction distribution according to the
113local view cell density. We select a random viecell which lies at the
114halfpace given by the surface normal at the chosen point. We pick a
115random point inside the view cell and cast a ray towards this point.
116
117
118\subsection{Accounting for Visibility Events}
119
120
121\subsection{View Cell Representation}
122
123In order to efficiently use view cells with our sampling method, we require a view cell representation which is
124
125\begin{itemize}
126\item optimized for view cell - ray intersection.
127\item flexible, i.e., it can represent arbitrary geometry.
128\item naturally suited for an hierarchical approach. %(i.e., there is a root view cell containing all others)
129\end{itemize}
130
131We meet these requirements by using a view cell BSP tree, where the
132BSP tree leafs are associated with the view cells.  Using the BSP tree, we
133are able to find the initial view cells with only a few view ray-plane
134intersections.  The hierarchical structure of the BSP tree can be
135exploited as hierarchy of view cells. If neccessary, the BSP  approach
136makes it very easy to further subdivide a view cell.
137Currently there are two approaches to generate the initial BSP view cell tree.
138
139\begin{itemize}
140\item We use a number of dedicated input view cells. As input view
141cell any closed mesh can be applied. The only requirement is that the
142view cells do not overlap. We insert one view cell after the other
143into the tree. The polygons of a view cell are filtered down the tree,
144guiding the insertion process. Once we reach a leaf and there are no
145more polygons left, we terminate the tree subdivision. If we are on
146the inside of the last split plane (i.e., the leaf is representing the
147inside of the view cell), we associate the leaf with the view cell
148(i.e., add a pointer to the view cell). Hence a number of leafes can
149be associated with the same input view cell.
150\item We apply the BSP tree subdivision to the scene geometry. When
151the subdivision terminates, the leaf nodes also represent the view
152cells.
153\end{itemize}
154
155
156\section{Visibility Verification}
157
158
159\subsection{Exact Verifier}
160
161The exact verifier computes exact mutual visibility between two
162polyhedrons in the scene. This is computed by testing visibility
163between all pairs of potentially polygons of these polyhedrons.
164
165
166
167\subsection{Conservative Verifier}
168
169
170\subsection{Error Bound Verifier}
171
172
173
Note: See TracBrowser for help on using the repository browser.