1 | \chapter{Global Visibility Sampling Tool}
|
---|
2 |
|
---|
3 |
|
---|
4 | The proposed visibility preprocessing framework consists of two major
|
---|
5 | steps.
|
---|
6 |
|
---|
7 | \begin{itemize}
|
---|
8 | \item The first step is an aggresive visibility sampling which gives
|
---|
9 | initial estimate about global visibility in the scene. The sampling
|
---|
10 | itself involves several strategies which will be described in
|
---|
11 | section~\ref{sec:sampling}. The imporant property of the aggresive
|
---|
12 | sampling step is that it provides a fast progressive solution to
|
---|
13 | global visibility and thus it can be easily integrated into the game
|
---|
14 | development cycle.
|
---|
15 |
|
---|
16 | \item The second step is mutual visibility verification. This step
|
---|
17 | turns the previous aggresive visibility solution into either exact,
|
---|
18 | conservative or error bound aggresive solution. The choice of the
|
---|
19 | particular verifier is left on the user in order to select the best
|
---|
20 | one for a particular scene, application context and time
|
---|
21 | constrains. For example, in scenes like a forest an error bound
|
---|
22 | aggresive visibility can be the best compromise between the resulting
|
---|
23 | size of the PVS (and framerate) and the visual quality. The exact or
|
---|
24 | conservative algorithm can however be chosen for urban scenes where
|
---|
25 | ommision of even small objects can be more distructing for the
|
---|
26 | user. The mutual visibility tool will be described in the next chapter.
|
---|
27 |
|
---|
28 | \end{itemize}
|
---|
29 |
|
---|
30 |
|
---|
31 | In traditional visibility preprocessing the view space is
|
---|
32 | subdivided into view cells and for each view cell the set of visible
|
---|
33 | objects --- potentially visible set (PVS) is computed. This framewoirk
|
---|
34 | has been used for conservative, aggresive and exact algorithms.
|
---|
35 |
|
---|
36 | We propose a different strategy which has several advantages for
|
---|
37 | sampling based aggresive visibility preprocessing. The stategy is
|
---|
38 | based on the following fundamental ideas:
|
---|
39 | \begin{itemize}
|
---|
40 | \item Compute progressive global visibility instead of sequential from-region visibility
|
---|
41 | \item Replace the roles of view cells and objects for some parts of the computation
|
---|
42 | \end{itemize}
|
---|
43 |
|
---|
44 | Both these points will be addressed in this chapter in more detail.
|
---|
45 |
|
---|
46 |
|
---|
47 |
|
---|
48 | \section{Related work}
|
---|
49 | \label{VFR3D_RELATED_WORK}
|
---|
50 |
|
---|
51 | Below we briefly discuss the related work on visibility preprocessing
|
---|
52 | in several application areas. In particular we focus on computing
|
---|
53 | from-region which has been a core of most previous visibility
|
---|
54 | preprocessing techniques.
|
---|
55 |
|
---|
56 |
|
---|
57 | \subsection{Aspect graph}
|
---|
58 |
|
---|
59 | The first algorithms dealing with from-region visibility belong to the
|
---|
60 | area of computer vision. The {\em aspect
|
---|
61 | graph}~\cite{Gigus90,Plantinga:1990:RTH, Sojka:1995:AGT} partitions
|
---|
62 | the view space into cells that group viewpoints from which the
|
---|
63 | projection of the scene is qualitatively equivalent. The aspect graph
|
---|
64 | is a graph describing the view of the scene (aspect) for each cell of
|
---|
65 | the partitioning. The major drawback of this approach is that for
|
---|
66 | polygonal scenes with $n$ polygons there can be $\Theta(n^9)$ cells in
|
---|
67 | the partitioning for unrestricted viewspace. A {\em scale space}
|
---|
68 | aspect graph~\cite{bb12595,bb12590} improves robustness of the method
|
---|
69 | by merging similar features according to the given scale.
|
---|
70 |
|
---|
71 |
|
---|
72 | \subsection{Potentially visible sets}
|
---|
73 |
|
---|
74 |
|
---|
75 | In the computer graphics community Airey~\cite{Airey90} introduced
|
---|
76 | the concept of {\em potentially visible sets} (PVS). Airey assumes
|
---|
77 | the existence of a natural subdivision of the environment into
|
---|
78 | cells. For models of building interiors these cells roughly correspond
|
---|
79 | to rooms and corridors. For each cell the PVS is formed by cells
|
---|
80 | visible from any point of that cell. Airey uses ray shooting to
|
---|
81 | approximate visibility between cells of the subdivision and so the
|
---|
82 | computed PVS is not conservative.
|
---|
83 |
|
---|
84 | This concept was further elaborated by Teller et
|
---|
85 | al.~\cite{Teller92phd,Teller:1991:VPI} to establish a conservative
|
---|
86 | PVS. The PVS is constructed by testing the existence of a stabbing
|
---|
87 | line through a sequence of polygonal portals between cells. Teller
|
---|
88 | proposed an exact solution to this problem using \plucker
|
---|
89 | coordinates~\cite{Teller:1992:CAA} and a simpler and more robust
|
---|
90 | conservative solution~\cite{Teller92phd}. The portal based methods
|
---|
91 | are well suited to static densely occluded environments with a
|
---|
92 | particular structure. For less structured models they can face a
|
---|
93 | combinatorial explosion of complexity~\cite{Teller92phd}. Yagel and
|
---|
94 | Ray~\cite{Yagel95a} present an algorithm, that uses a regular spatial
|
---|
95 | subdivision. Their approach is not sensitive to the structure of the
|
---|
96 | model in terms of complexity, but its efficiency is altered by the
|
---|
97 | discrete representation of the scene.
|
---|
98 |
|
---|
99 | Plantinga proposed a PVS algorithm based on a conservative viewspace
|
---|
100 | partitioning by evaluating visual
|
---|
101 | events~\cite{Plantinga:1993:CVP}. The construction of viewspace
|
---|
102 | partitioning was further studied by Chrysanthou et
|
---|
103 | al.~\cite{Chrysanthou:1998:VP}, Cohen-Or et al.~\cite{cohen-egc-98}
|
---|
104 | and Sadagic~\cite{Sadagic}. Sudarsky and
|
---|
105 | Gotsman~\cite{Sudarsky:1996:OVA} proposed an output-sensitive
|
---|
106 | visibility algorithm for dynamic scenes. Cohen-Or et
|
---|
107 | al.~\cite{COZ-gi98} developed a conservative algorithm determining
|
---|
108 | visibility of an $\epsilon$-neighborhood of a given viewpoint that was
|
---|
109 | used for network based walkthroughs.
|
---|
110 |
|
---|
111 | Conservative algorithms for computing PVS developed by Durand et
|
---|
112 | al.~\cite{EVL-2000-60} and Schaufler et al.~\cite{EVL-2000-59} make
|
---|
113 | use of several simplifying assumptions to avoid the usage of 4D data
|
---|
114 | structures. Wang et al.~\cite{Wang98} proposed an algorithm that
|
---|
115 | precomputes visibility within beams originating from the restricted
|
---|
116 | viewpoint region. The approach is very similar to the 5D subdivision
|
---|
117 | for ray tracing~\cite{Simiakakis:1994:FAS} and so it exhibits similar
|
---|
118 | problems, namely inadequate memory and preprocessing complexities.
|
---|
119 | Specialized algorithms for computing PVS in \m25d scenes were proposed
|
---|
120 | by Wonka et al.~\cite{wonka00}, Koltun et al.~\cite{koltun01}, and
|
---|
121 | Bittner et al.~\cite{bittner:2001:PG}.
|
---|
122 |
|
---|
123 | The exact mutual visibility method presented later in the report is
|
---|
124 | based on method exploting \plucker coordinates of
|
---|
125 | lines~\cite{bittner02phd,nirenstein:02:egwr,haumont2005}. This
|
---|
126 | algorithm uses \plucker coordinates to compute visibility in shafts
|
---|
127 | defined by each polygon in the scene.
|
---|
128 |
|
---|
129 |
|
---|
130 | \subsection{Rendering of shadows}
|
---|
131 |
|
---|
132 |
|
---|
133 | The from-region visibility problems include the computation of soft
|
---|
134 | shadows due to an areal light source. Continuous algorithms for
|
---|
135 | real-time soft shadow generation were studied by Chin and
|
---|
136 | Feiner~\cite{Chin:1992:FOP}, Loscos and
|
---|
137 | Drettakis~\cite{Loscos:1997:IHS}, and
|
---|
138 | Chrysanthou~\cite{Chrysantho1996a} and Chrysanthou and
|
---|
139 | Slater~\cite{Chrysanthou:1997:IUS}. Discrete solutions have been
|
---|
140 | proposed by Nishita~\cite{Nishita85}, Brotman and
|
---|
141 | Badler~\cite{Brotman:1984:GSS}, and Soler and Sillion~\cite{SS98}. An
|
---|
142 | exact algorithm computing an antipenumbra of an areal light source was
|
---|
143 | developed by Teller~\cite{Teller:1992:CAA}.
|
---|
144 |
|
---|
145 |
|
---|
146 | \subsection{Discontinuity meshing}
|
---|
147 |
|
---|
148 |
|
---|
149 | Discontinuity meshing is used in the context of the radiosity global
|
---|
150 | illumination algorithm or computing soft shadows due to areal light
|
---|
151 | sources. First approximate discontinuity meshing algorithms were
|
---|
152 | studied by Campbell~\cite{Campbell:1990:AMG, Campbell91},
|
---|
153 | Lischinski~\cite{lischinski92a}, and Heckbert~\cite{Heckbert92discon}.
|
---|
154 | More elaborate methods were developed by
|
---|
155 | Drettakis~\cite{Drettakis94-SSRII, Drettakis94-FSAAL}, and Stewart and
|
---|
156 | Ghali~\cite{Stewart93-OSACS, Stewart:1994:FCSb}. These methods are
|
---|
157 | capable of creating a complete discontinuity mesh that encodes all
|
---|
158 | visual events involving the light source.
|
---|
159 |
|
---|
160 | The classical radiosity is based on an evaluation of form factors
|
---|
161 | between two patches~\cite{Schroder:1993:FFB}. The visibility
|
---|
162 | computation is a crucial step in the form factor
|
---|
163 | evaluation~\cite{Teller:1993:GVA,Haines94,Teller:1994:POL,
|
---|
164 | Nechvile:1996:FFE,Teichmann:WV}. Similar visibility computation takes
|
---|
165 | place in the scope of hierarchical radiosity
|
---|
166 | algorithms~\cite{Soler:1996:AEB, Drettakis:1997:IUG, Daubert:1997:HLS}.
|
---|
167 |
|
---|
168 |
|
---|
169 |
|
---|
170 | \subsection{Global visibility}
|
---|
171 |
|
---|
172 | The aim of {\em global visibility} computations is to capture and
|
---|
173 | describe visibility in the whole scene~\cite{Durand:1996:VCN}. The
|
---|
174 | global visibility algorithms are typically based on some form of {\em
|
---|
175 | line space subdivision} that partitions lines or rays into equivalence
|
---|
176 | classes according to their visibility classification. Each class
|
---|
177 | corresponds to a continuous set of rays with a common visibility
|
---|
178 | classification. The techniques differ mainly in the way how the line
|
---|
179 | space subdivision is computed and maintained. A practical application
|
---|
180 | of most of the proposed global visibility structures for 3D scenes is
|
---|
181 | still an open problem. Prospectively these techniques provide an
|
---|
182 | elegant method for ray shooting acceleration --- the ray shooting
|
---|
183 | problem can be reduced to a point location in the line space
|
---|
184 | subdivision.
|
---|
185 |
|
---|
186 |
|
---|
187 | Pocchiola and Vegter introduced the visibility complex~\cite{pv-vc-93}
|
---|
188 | that describes global visibility in 2D scenes. The visibility complex
|
---|
189 | has been applied to solve various 2D visibility
|
---|
190 | problems~\cite{r-tsvcp-95,r-wvcav-97, r-dvpsv-97,Orti96-UVCRC}. The
|
---|
191 | approach was generalized to 3D by Durand et
|
---|
192 | al.~\cite{Durand:1996:VCN}. Nevertheless, no implementation of the 3D
|
---|
193 | visibility complex is currently known. Durand et
|
---|
194 | al.~\cite{Durand:1997:VSP} introduced the {\em visibility skeleton}
|
---|
195 | that is a graph describing a skeleton of the 3D visibility
|
---|
196 | complex. The visibility skeleton was verified experimentally and the
|
---|
197 | results indicate that its $O(n^4\log n)$ worst case complexity is much
|
---|
198 | better in practice. Pu~\cite{Pu98-DSGIV} developed a similar method to
|
---|
199 | the one presented in this chapter. He uses a BSP tree in \plucker
|
---|
200 | coordinates to represent a global visibility map for a given set of
|
---|
201 | polygons. The computation is performed considering all rays piercing
|
---|
202 | the scene and so the method exhibits unacceptable memory complexity
|
---|
203 | even for scenes of moderate size. Recently, Duguet and
|
---|
204 | Drettakis~\cite{duguet:02:sig} developed a robust variant of the
|
---|
205 | visibility skeleton algorithm that uses robust epsilon-visibility
|
---|
206 | predicates.
|
---|
207 |
|
---|
208 | Discrete methods aiming to describe visibility in a 4D data structure
|
---|
209 | were presented by Chrysanthou et al.~\cite{chrysanthou:cgi:98} and
|
---|
210 | Blais and Poulin~\cite{blais98a}. These data structures are closely
|
---|
211 | related to the {\em lumigraph}~\cite{Gortler:1996:L,buehler2001} or
|
---|
212 | {\em light field}~\cite{Levoy:1996:LFR}. An interesting discrete
|
---|
213 | hierarchical visibility algorithm for two-dimensional scenes was
|
---|
214 | developed by Hinkenjann and M\"uller~\cite{EVL-1996-10}. One of the
|
---|
215 | biggest problems of the discrete solution space data structures is
|
---|
216 | their memory consumption required to achieve a reasonable
|
---|
217 | accuracy. Prospectively, the scene complexity
|
---|
218 | measures~\cite{Cazals:3204:1997} provide a useful estimate on the
|
---|
219 | required sampling density and the size of the solution space data
|
---|
220 | structure.
|
---|
221 |
|
---|
222 |
|
---|
223 | \subsection{Other applications}
|
---|
224 |
|
---|
225 | Certain from-point visibility problems determining visibility over a
|
---|
226 | period of time can be transformed to a static from-region visibility
|
---|
227 | problem. Such a transformation is particularly useful for antialiasing
|
---|
228 | purposes~\cite{grant85a}. The from-region visibility can also be used
|
---|
229 | in the context of simulation of the sound
|
---|
230 | propagation~\cite{Funkhouser98}. The sound propagation algorithms
|
---|
231 | typically require lower resolution than the algorithms simulating the
|
---|
232 | propagation of light, but they need to account for simulation of
|
---|
233 | attenuation, reflection and time delays.
|
---|
234 |
|
---|
235 | \section{Algorithm Description}
|
---|
236 |
|
---|
237 | This section first describes the setup of the global visibility
|
---|
238 | sampling algorithm. In particular we describe the view cell
|
---|
239 | representation and the novel concept of from-object based
|
---|
240 | visibility. The we outline the different visibility sampling
|
---|
241 | strategies.
|
---|
242 |
|
---|
243 | \subsection{View Cell Representation}
|
---|
244 |
|
---|
245 | \begin{figure}[htb]
|
---|
246 | \centerline{
|
---|
247 | \includegraphics[height=0.35\textwidth,draft=\DRAFTFIGS]{images/vienna_viewcells_01}
|
---|
248 | \includegraphics[height=0.35\textwidth,draft=\DRAFTFIGS]{images/vienna_viewcells_07}
|
---|
249 | }
|
---|
250 |
|
---|
251 | \caption{(left) Vienna viewcells. (right) The view cells are prisms with a triangular base. }
|
---|
252 | \label{fig:vienna_viewcells}
|
---|
253 | \end{figure}
|
---|
254 |
|
---|
255 |
|
---|
256 | A good partition of the scene into view cells is an essential part of every visibility
|
---|
257 | system. If they are chosen too large, the PVS (Potentially Visibible Set)
|
---|
258 | of a view cells is too large for efficient culling. If they are chosen too small or
|
---|
259 | without consideration, then neighbouring view cells contain redundant PVS information,
|
---|
260 | hence boosting the PVS computation and storage costs for the scene. In the left image of figure~\ref{fig:vienna_viewcells} we see view cells of the Vienna model, generated by triangulation of the streets.
|
---|
261 | In the closeup (right image) we can see that each triangle is extruded to a given height to form a view cell prism.
|
---|
262 |
|
---|
263 | In order to efficiently use view cells with our sampling method, we
|
---|
264 | require a view cell representation which is
|
---|
265 |
|
---|
266 | \begin{itemize}
|
---|
267 | \item optimized for view cell - ray intersection.
|
---|
268 | \item flexible, i.e., it can represent arbitrary geometry.
|
---|
269 | \item naturally suited for a hierarchical approach. %(i.e., there is a root view cell containing all others)
|
---|
270 | \end{itemize}
|
---|
271 |
|
---|
272 | We meet these requirements by employing spatial subdivisions (i.e.,
|
---|
273 | KD trees and BSP trees), to store the view cells. The initial view cells are
|
---|
274 | associated with the leaves. The reason why we chose BSP trees as view cell representation
|
---|
275 | is that they are very flexible. View cells forming arbitrary closed meshes can be closely matched.
|
---|
276 | Therefore we are able to find a view cells with only a few view ray-plane
|
---|
277 | intersections. Furthermore, the hierarchical structures can be
|
---|
278 | exploited as hierarchy of view cells. Interior nodes form larger view cells
|
---|
279 | containing the children. If neccessary, a leaf can be easily subdivided into smaller view cells.
|
---|
280 |
|
---|
281 | Currently we consider three different approaches to generate the initial view cell BSP tree.
|
---|
282 | The third method is not restricted to BSP trees, but BSP trees are prefered
|
---|
283 | because of their greater flexibility.
|
---|
284 |
|
---|
285 |
|
---|
286 | \begin{table}
|
---|
287 | \centering \footnotesize
|
---|
288 | \begin{tabular}{|l|c|c|}
|
---|
289 | \hline\hline
|
---|
290 | View cells & Vienna selection & Vienna full \\\hline\hline
|
---|
291 | \#view cells & 105 & 16447 \\\hline\hline
|
---|
292 | \#input polygons & 525 & 82235 \\\hline\hline
|
---|
293 | BSP tree generation time & 0.016s & 10.328s \\\hline\hline
|
---|
294 | view cell insertion time & 0.016s & 7.984s \\\hline\hline
|
---|
295 | \#nodes & 1137 & 597933 \\\hline\hline
|
---|
296 | \#interior nodes & 568 & 298966\\\hline\hline
|
---|
297 | \#leaf nodes & 569 & 298967\\\hline\hline
|
---|
298 | \#splits & 25 & 188936\\\hline\hline
|
---|
299 | max tree depth & 13 & 27\\\hline\hline
|
---|
300 | avg tree depth & 9.747 & 21.11\\\hline\hlien
|
---|
301 |
|
---|
302 | \end{tabular}
|
---|
303 | \caption{Statistics for view cell BSP tree on the Vienna view cells and a selection of the Vienna view cells.}\label{tab:viewcell_bsp}
|
---|
304 | \end{table}
|
---|
305 |
|
---|
306 |
|
---|
307 | \begin{itemize}
|
---|
308 |
|
---|
309 | \item We use a number of input view cells given in advance. As input view cell
|
---|
310 | any closed mesh can be applied. The only requirement is that the
|
---|
311 | any two view cells do not overlap.
|
---|
312 | First the view cell polygons are extracted, and the BSP is build from
|
---|
313 | these polygons using some global optimizations like tree balancing or
|
---|
314 | least splits. Then one view cell after the other
|
---|
315 | is inserted into the tree to find out the leafes where they are contained
|
---|
316 | in. The polygons of the view cell are filtered down the tree,
|
---|
317 | guiding the insertion process. Once we reach a leaf and there are no
|
---|
318 | more polygons left, we terminate the tree subdivision. If we are on
|
---|
319 | the inside of the last split plane (i.e., the leaf represents the
|
---|
320 | inside of the view cell), we associate the leaf with the view cell
|
---|
321 | (i.e., add a pointer to the view cell). One input view cell can
|
---|
322 | be associated with many leafes, whereas each leafs has only one view cell.
|
---|
323 | Some statistics about using this method on the vienna view cells set are given in table~\ref{tab:viewcell_bsp}.
|
---|
324 | However, sometimes a good set of view cells is not available. Or the scene
|
---|
325 | is changed frequently, and the designer does not want to create new view cells on each change.
|
---|
326 | In such a case one of the following two methods should rather be chosen, which generate view cells
|
---|
327 | automatically.
|
---|
328 |
|
---|
329 |
|
---|
330 | \item We apply a BSP tree subdivision to the scene geometry. Whenever
|
---|
331 | the subdivision terminates in a leaf, a view cell is associated with the leaf node.
|
---|
332 | This simple approach is justified because it places the view cell borders
|
---|
333 | along some discontinuities in the visibility function.
|
---|
334 |
|
---|
335 | \item The view cell generation can be guided by the sampling process. We start with
|
---|
336 | with a single initial view cell representing the whole space. If a given threshold
|
---|
337 | is reached during the preprocessing (e.g., the view cell is pierced by too many rays
|
---|
338 | resulting in a large PVS), the view cell is subdivided into smaller cells using some criteria.
|
---|
339 |
|
---|
340 | In order to evaluate the best split plane, we first have to define the characteristics of a
|
---|
341 | good view cell partition: The view cells should be quite large, while their PVS stays rather small.
|
---|
342 | The PVS of each two view cells should be as distinct as possible, otherwise they could be
|
---|
343 | merged into a larger view cell if the PVSs are too similar.
|
---|
344 | E.g., for a building, the perfect view cells are usually the single rooms connected by portals.
|
---|
345 |
|
---|
346 | Hence we can define some useful criteria for the split: 1) the number of rays should be roughly equal among the new view cells. 2) The split plane should be chosen in a way that the rays are maximal distinct, i.e., the number
|
---|
347 | of rays contributing to more than one cell should be minimized => the PVSs are also distinct. 3) For BSP trees,
|
---|
348 | the split plane should be aligned with some scene geometry which is large enough to contribute
|
---|
349 | a lot of occlusion power. This criterium can be naturally combined with the second one.
|
---|
350 | As termination criterium we can choose the minimum PVS / piercing ray size or the maximal tree depth.
|
---|
351 | \end{itemize}
|
---|
352 |
|
---|
353 | \subsection{From-object based visibility}
|
---|
354 |
|
---|
355 | Our framework is based on the idea of sampling visibility by casting
|
---|
356 | casting rays through the scene and collecting their contributions. A
|
---|
357 | visibility sample is computed by casting a ray from an object towards
|
---|
358 | the view cells and computing the nearest intersection with the scene
|
---|
359 | objects. All view cells pierced by the ray segment can the object and
|
---|
360 | thus the object can be added to their PVS. If the ray is terminated at
|
---|
361 | another scene object the PVS of the pierced view cells can also be
|
---|
362 | extended by this terminating object. Thus a single ray can make a
|
---|
363 | number of contributions to the progressively computed PVSs. A ray
|
---|
364 | sample piercing $n$ view cells which is bound by two distinct objects
|
---|
365 | contributes by at most $2*n$ entries to the current PVSs. Apart from
|
---|
366 | this performance benefit there is also a benefit in terms of the
|
---|
367 | sampling density: Assuming that the view cells are usually much larger
|
---|
368 | than the objects (which is typically the case) starting the sampling
|
---|
369 | deterministically from the objects increases the probability of small
|
---|
370 | objects being captured in the PVS.
|
---|
371 |
|
---|
372 | At this phase of the computation we not only start the samples from
|
---|
373 | the objects, but we also store the PVS information centered at the
|
---|
374 | objects. Instead of storing a PVS consting of objects visible from
|
---|
375 | view cells, every object maintains a PVS consisting of potentially
|
---|
376 | visible view cells. While these representations contain exactly the
|
---|
377 | same information as we shall see later the object centered PVS is
|
---|
378 | better suited for the importance sampling phase as well as the
|
---|
379 | visibility verification phase.
|
---|
380 |
|
---|
381 |
|
---|
382 | \subsection{Basic Randomized Sampling}
|
---|
383 |
|
---|
384 |
|
---|
385 | The first phase of the sampling works as follows: At every pass of the
|
---|
386 | algorithm visits scene objects sequentially. For every scene object we
|
---|
387 | randomly choose a point on its surface. Then a ray is cast from the
|
---|
388 | selected point according to the randomly chosen direction. We use a
|
---|
389 | uniform distribution of the ray directions with respect to the
|
---|
390 | halfspace given by the surface normal. Using this strategy the samples
|
---|
391 | at deterministicaly placed at every object, with a randomization of
|
---|
392 | the location on the object surface. The uniformly distributed
|
---|
393 | direction is a simple and fast strategy to gain initial visibility
|
---|
394 | information.
|
---|
395 |
|
---|
396 |
|
---|
397 | The described algorithm accounts for the irregular distribution of the
|
---|
398 | objects: more samples are placed at locations containing more
|
---|
399 | objects. Additionally every object is sampled many times depending on
|
---|
400 | the number of passes in which this sampling strategy is applied. This
|
---|
401 | increases the chance of even a small object being captured in the PVS
|
---|
402 | of the view cells from which it is visible.
|
---|
403 |
|
---|
404 |
|
---|
405 | \subsection{Accounting for View Cell Distribution}
|
---|
406 |
|
---|
407 | The first modification to the basic algorithm accounts for irregular
|
---|
408 | distribution of the view cells. Such a case is common for example in
|
---|
409 | urban scenes where the view cells are mostly distributed in a
|
---|
410 | horizontal direction and more view cells are placed at denser parts of
|
---|
411 | the city. The modification involves replacing the uniformly
|
---|
412 | distributed ray direction by directions distributed according to the
|
---|
413 | local view cell directional density. This means placing more samples at
|
---|
414 | directions where more view cells are located: We select a random
|
---|
415 | viecell which lies at the halfpace given by the surface normal at the
|
---|
416 | chosen point. We pick a random point inside the view cell and cast a
|
---|
417 | ray towards this point.
|
---|
418 |
|
---|
419 |
|
---|
420 | \subsection{Accounting for Visibility Events}
|
---|
421 |
|
---|
422 | Visibility events correspond to appearance and disapearance of
|
---|
423 | objects with respect to a moving view point. In polygonal scenes the
|
---|
424 | events defined by event surfaces defined by three distinct scene
|
---|
425 | edges. Depending on the edge configuration we distinguish between
|
---|
426 | vertex-edge events (VE) and tripple edge (EEE) events. The VE surfaces
|
---|
427 | are planar planes whereas the EEE are in general quadratic surfaces.
|
---|
428 |
|
---|
429 | To account for these event we explicitly place samples passing by the
|
---|
430 | object edges which are directed to edges and/or vertices of other
|
---|
431 | objects.
|
---|
432 |
|
---|
433 |
|
---|