[277] | 1 | \chapter{Global Visibility Sampling}
|
---|
[249] | 2 |
|
---|
[277] | 3 | \label{chap:sampling}
|
---|
[249] | 4 |
|
---|
| 5 | The proposed visibility preprocessing framework consists of two major
|
---|
| 6 | steps.
|
---|
[255] | 7 |
|
---|
[249] | 8 | \begin{itemize}
|
---|
[277] | 9 | \item The first step is an aggressive visibility sampling which gives
|
---|
[249] | 10 | initial estimate about global visibility in the scene. The sampling
|
---|
[273] | 11 | itself involves several strategies which will be described bellow.
|
---|
[277] | 12 | The important property of the aggressive sampling step is that it
|
---|
[273] | 13 | provides a fast progressive solution to global visibility and thus it
|
---|
| 14 | can be easily integrated into the game development cycle. The
|
---|
[277] | 15 | aggressive sampling will terminate when the average contribution of new
|
---|
[273] | 16 | ray samples falls bellow a predefined threshold.
|
---|
[249] | 17 |
|
---|
[255] | 18 | \item The second step is mutual visibility verification. This step
|
---|
[277] | 19 | turns the previous aggressive visibility solution into either exact,
|
---|
| 20 | conservative or error bound aggressive solution. The choice of the
|
---|
[255] | 21 | particular verifier is left on the user in order to select the best
|
---|
[266] | 22 | one for a particular scene, application context and time
|
---|
| 23 | constrains. For example, in scenes like a forest an error bound
|
---|
[277] | 24 | aggressive visibility can be the best compromise between the resulting
|
---|
| 25 | size of the PVS (and frame rate) and the visual quality. The exact or
|
---|
[266] | 26 | conservative algorithm can however be chosen for urban scenes where
|
---|
[277] | 27 | omission of even small objects can be more distracting for the
|
---|
| 28 | user. The mutual visibility verification will be described in the next
|
---|
| 29 | chapter.
|
---|
[255] | 30 |
|
---|
[249] | 31 | \end{itemize}
|
---|
| 32 |
|
---|
| 33 | In traditional visibility preprocessing the view space is
|
---|
[272] | 34 | subdivided into view cells and for each view cell the set of visible
|
---|
[277] | 35 | objects --- potentially visible set (PVS) is computed. This framework
|
---|
| 36 | has been used for conservative, aggressive and exact algorithms.
|
---|
[249] | 37 |
|
---|
| 38 | We propose a different strategy which has several advantages for
|
---|
[277] | 39 | sampling based aggressive visibility preprocessing. The strategy is
|
---|
[249] | 40 | based on the following fundamental ideas:
|
---|
| 41 | \begin{itemize}
|
---|
| 42 | \item Compute progressive global visibility instead of sequential from-region visibility
|
---|
[266] | 43 | \item Replace the roles of view cells and objects for some parts of the computation
|
---|
[249] | 44 | \end{itemize}
|
---|
| 45 |
|
---|
[255] | 46 | Both these points will be addressed in this chapter in more detail.
|
---|
[249] | 47 |
|
---|
[255] | 48 | \section{Related work}
|
---|
| 49 | \label{VFR3D_RELATED_WORK}
|
---|
| 50 |
|
---|
[266] | 51 | Below we briefly discuss the related work on visibility preprocessing
|
---|
[255] | 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
|
---|
[266] | 61 | graph}~\cite{Gigus90,Plantinga:1990:RTH, Sojka:1995:AGT} partitions
|
---|
[255] | 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
|
---|
[277] | 67 | the partitioning for unrestricted view space. A {\em scale space}
|
---|
[255] | 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
|
---|
[277] | 125 | lines~\cite{bittner:02:phd,nirenstein:02:egwr,haumont2005:egsr}. This
|
---|
[255] | 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 |
|
---|
[266] | 235 | \section{Algorithm Description}
|
---|
[255] | 236 |
|
---|
[266] | 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 |
|
---|
[273] | 243 | \subsection{View Space Partitioning}
|
---|
[255] | 244 |
|
---|
[273] | 245 |
|
---|
[272] | 246 |
|
---|
| 247 |
|
---|
[273] | 248 | Before the visibility computation itself, we subdivide the space of
|
---|
| 249 | all possible viewpoints and viewing directions into view cells. A good
|
---|
| 250 | partition of the scene into view cells is an essential part of every
|
---|
| 251 | visibility system. If they are chosen too large, the PVS (Potentially
|
---|
[277] | 252 | Visible Set) of a view cells is too large for efficient culling. If
|
---|
[273] | 253 | they are chosen too small or without consideration, then neighbouring
|
---|
| 254 | view cells contain redundant PVS information, hence boosting the PVS
|
---|
| 255 | computation and storage costs for the scene. In the left image of
|
---|
| 256 | figure~\ref{fig:vienna_viewcells} we see view cells of the Vienna
|
---|
| 257 | model, generated by triangulation of the streets. In the closeup
|
---|
| 258 | (right image) we can see that each triangle is extruded to a given
|
---|
| 259 | height to form a view cell prism.
|
---|
[272] | 260 |
|
---|
[277] | 261 | \begin{figure}[htb]
|
---|
| 262 | \centerline{
|
---|
| 263 | \includegraphics[height=0.35\textwidth,draft=\DRAFTFIGS]{images/vienna_viewcells_01}
|
---|
| 264 | \includegraphics[height=0.35\textwidth,draft=\DRAFTFIGS]{images/vienna_viewcells_07}
|
---|
| 265 | }
|
---|
| 266 |
|
---|
| 267 | \caption{(left) Vienna view cells. (right) The view cells are prisms with a triangular base. }
|
---|
| 268 | \label{fig:vienna_viewcells}
|
---|
| 269 | \end{figure}
|
---|
| 270 |
|
---|
[255] | 271 | In order to efficiently use view cells with our sampling method, we
|
---|
| 272 | require a view cell representation which is
|
---|
| 273 |
|
---|
| 274 | \begin{itemize}
|
---|
[272] | 275 | \item optimized for view cell - ray intersection.
|
---|
[255] | 276 | \item flexible, i.e., it can represent arbitrary geometry.
|
---|
[266] | 277 | \item naturally suited for a hierarchical approach. %(i.e., there is a root view cell containing all others)
|
---|
[255] | 278 | \end{itemize}
|
---|
| 279 |
|
---|
[277] | 280 | We meet these requirements by employing spatial subdivisions (i.e.,
|
---|
| 281 | KD trees and BSP trees), to store the view cells. The initial view
|
---|
| 282 | cells are associated with the leaves. The reason why we chose BSP
|
---|
| 283 | trees as view cell representation is that they are very
|
---|
| 284 | flexible. View cells forming arbitrary closed meshes can be closely
|
---|
| 285 | matched. Therefore we are able to find a view cells with only a few
|
---|
| 286 | view ray-plane intersections. Furthermore, the hierarchical
|
---|
| 287 | structures can be exploited as hierarchy of view cells. Interior nodes
|
---|
| 288 | form larger view cells containing the children. If necessary, a leaf
|
---|
| 289 | can be easily subdivided into smaller view cells.
|
---|
[255] | 290 |
|
---|
[277] | 291 | Currently we consider three different approaches to generate the
|
---|
| 292 | initial view cell BSP tree. The third method is not restricted to BSP
|
---|
| 293 | trees, but BSP trees are preferred because of their greater
|
---|
| 294 | flexibility.
|
---|
[255] | 295 |
|
---|
[272] | 296 |
|
---|
| 297 | \begin{table}
|
---|
| 298 | \centering \footnotesize
|
---|
| 299 | \begin{tabular}{|l|c|c|}
|
---|
| 300 | \hline\hline
|
---|
| 301 | View cells & Vienna selection & Vienna full \\\hline\hline
|
---|
| 302 | \#view cells & 105 & 16447 \\\hline\hline
|
---|
| 303 | \#input polygons & 525 & 82235 \\\hline\hline
|
---|
| 304 | BSP tree generation time & 0.016s & 10.328s \\\hline\hline
|
---|
[279] | 305 | %%view cell insertion time & 0.016s & 7.984s \\\hline\hline
|
---|
[272] | 306 | \#nodes & 1137 & 597933 \\\hline\hline
|
---|
[273] | 307 | \#interior nodes & 568 & 298966\\\hline\hline
|
---|
| 308 | \#leaf nodes & 569 & 298967\\\hline\hline
|
---|
| 309 | \#splits & 25 & 188936\\\hline\hline
|
---|
| 310 | max tree depth & 13 & 27\\\hline\hline
|
---|
[277] | 311 | avg tree depth & 9.747 & 21.11\\\hline\hline
|
---|
[273] | 312 |
|
---|
[272] | 313 | \end{tabular}
|
---|
| 314 | \caption{Statistics for view cell BSP tree on the Vienna view cells and a selection of the Vienna view cells.}\label{tab:viewcell_bsp}
|
---|
| 315 | \end{table}
|
---|
| 316 |
|
---|
| 317 |
|
---|
[255] | 318 | \begin{itemize}
|
---|
[266] | 319 |
|
---|
[277] | 320 | \item We use a number of input view cells given in advance. As input
|
---|
| 321 | view cell any closed mesh can be applied. The only requirement is
|
---|
[279] | 322 | that the any two view cells do not overlap. The view cell
|
---|
| 323 | polygons are extracted, storing a pointer to the parent view cell
|
---|
| 324 | with the polygon. The BSP is build from these polygons using
|
---|
| 325 | some global optimizations like tree balancing or least splits. The
|
---|
| 326 | polygons guide the split process as they are filtered down the tree.
|
---|
| 327 | The subdivision terminates when there is only one polygon left, which is coincident
|
---|
| 328 | to the last split plane. Then two leaves are created and the view cell pointer
|
---|
| 329 | (stored with the polygon) is inserted into the leaf representing the inside of the view cell.
|
---|
| 330 | One input view cell can be associated with many leaves in case
|
---|
| 331 | a view cell was split during the traversal. On the other hand, each leafs corresponds
|
---|
| 332 | to exactly one or no view cell. Some statistics about using this
|
---|
[277] | 333 | method on the Vienna view cells set are given in
|
---|
[279] | 334 | table~\ref{tab:viewcell_bsp}.
|
---|
| 335 |
|
---|
| 336 | However, sometimes a good set of view
|
---|
[277] | 337 | cells is not available. Or the scene is changed frequently, and the
|
---|
| 338 | designer does not want to create new view cells on each change. In
|
---|
| 339 | such a case one of the following two methods should rather be chosen,
|
---|
| 340 | which generate view cells automatically.
|
---|
[266] | 341 |
|
---|
| 342 |
|
---|
[272] | 343 | \item We apply a BSP tree subdivision to the scene geometry. Whenever
|
---|
[277] | 344 | the subdivision terminates in a leaf, a view cell is associated with
|
---|
| 345 | the leaf node. This simple approach is justified because it places
|
---|
| 346 | the view cell borders along some discontinuities in the visibility
|
---|
| 347 | function.
|
---|
[272] | 348 |
|
---|
[279] | 349 | \begin{figure}[htb]
|
---|
| 350 | \centerline{
|
---|
| 351 | \includegraphics[height=0.35\textwidth,draft=\DRAFTFIGS]{figs/viewcell_part}
|
---|
| 352 | }
|
---|
| 353 | \caption{A good view cell partition with respect to the sample rays piercing the scene objects
|
---|
| 354 | and the view cell minimizes the number of rays
|
---|
| 355 | piercing more than one view cell. During subdivision, this can be achieved by aligning
|
---|
| 356 | the split plane with one of the long sides of occluder $O$. }
|
---|
| 357 | \label{fig:viewcell_part}
|
---|
| 358 | \end{figure}
|
---|
| 359 |
|
---|
[277] | 360 | \item The view cell generation can be guided by the sampling
|
---|
| 361 | process. We start with with a single initial view cell representing
|
---|
| 362 | the whole space. If a given threshold is reached during the
|
---|
| 363 | preprocessing (e.g., the view cell is pierced by too many rays
|
---|
| 364 | resulting in a large PVS), the view cell is subdivided into smaller
|
---|
| 365 | cells using some criteria.
|
---|
[272] | 366 |
|
---|
[277] | 367 | In order to evaluate the best split plane, we first have to define the
|
---|
| 368 | characteristics of a good view cell partition: The view cells should
|
---|
| 369 | be quite large, while their PVS stays rather small. The PVS of each
|
---|
| 370 | two view cells should be as distinct as possible, otherwise they could
|
---|
| 371 | be merged into a larger view cell if the PVSs are too similar. E.g.,
|
---|
| 372 | for a building, the perfect view cells are usually the single rooms
|
---|
| 373 | connected by portals.
|
---|
[272] | 374 |
|
---|
[277] | 375 | Hence we can define some useful criteria for the split: 1) the number
|
---|
| 376 | of rays should be roughly equal among the new view cells. 2) The split
|
---|
| 377 | plane should be chosen in a way that the ray sets are disjoint, i.e.,
|
---|
| 378 | the number of rays contributing to more than one cell should be
|
---|
| 379 | minimized. 3) For BSP trees, the split plane should be aligned with
|
---|
| 380 | some scene geometry which is large enough to contribute a lot of
|
---|
| 381 | occlusion power. This criterion can be naturally combined with the
|
---|
| 382 | second one. As termination criterion we can choose the minimum PVS /
|
---|
[279] | 383 | piercing ray size or the maximal tree depth. An illustration of
|
---|
| 384 | a good and a bad choice of a split plane is given in figure~\ref{fig:viewcell_part}.
|
---|
[255] | 385 | \end{itemize}
|
---|
| 386 |
|
---|
[273] | 387 |
|
---|
[277] | 388 | % In the future we aim to extend the view cell construction by using
|
---|
| 389 | % feedback from the PVS computation: the view cells which contain many
|
---|
| 390 | % visibility changes will be subdivided further and neighboring view
|
---|
| 391 | % cells with similar PVSs will be merged. We want to gain a more precise
|
---|
| 392 | % information about visibility by selectively storing rays with the
|
---|
| 393 | % view cells and computing visibility statistics for subsets of rays
|
---|
| 394 | % which intersect subregions of the given view cell.
|
---|
[273] | 395 |
|
---|
[279] | 396 | \subsection{From-Object Based Visibility}
|
---|
[249] | 397 |
|
---|
[266] | 398 | Our framework is based on the idea of sampling visibility by casting
|
---|
[249] | 399 | casting rays through the scene and collecting their contributions. A
|
---|
| 400 | visibility sample is computed by casting a ray from an object towards
|
---|
[272] | 401 | the view cells and computing the nearest intersection with the scene
|
---|
[249] | 402 | objects. All view cells pierced by the ray segment can the object and
|
---|
| 403 | thus the object can be added to their PVS. If the ray is terminated at
|
---|
| 404 | another scene object the PVS of the pierced view cells can also be
|
---|
| 405 | extended by this terminating object. Thus a single ray can make a
|
---|
| 406 | number of contributions to the progressively computed PVSs. A ray
|
---|
[272] | 407 | sample piercing $n$ view cells which is bound by two distinct objects
|
---|
| 408 | contributes by at most $2*n$ entries to the current PVSs. Apart from
|
---|
[249] | 409 | this performance benefit there is also a benefit in terms of the
|
---|
| 410 | sampling density: Assuming that the view cells are usually much larger
|
---|
| 411 | than the objects (which is typically the case) starting the sampling
|
---|
| 412 | deterministically from the objects increases the probability of small
|
---|
| 413 | objects being captured in the PVS.
|
---|
| 414 |
|
---|
| 415 | At this phase of the computation we not only start the samples from
|
---|
| 416 | the objects, but we also store the PVS information centered at the
|
---|
[277] | 417 | objects. Instead of storing a PVS consisting of objects visible from
|
---|
[249] | 418 | view cells, every object maintains a PVS consisting of potentially
|
---|
| 419 | visible view cells. While these representations contain exactly the
|
---|
| 420 | same information as we shall see later the object centered PVS is
|
---|
| 421 | better suited for the importance sampling phase as well as the
|
---|
| 422 | visibility verification phase.
|
---|
| 423 |
|
---|
| 424 |
|
---|
[273] | 425 | \subsection{Naive Randomized Sampling}
|
---|
[249] | 426 |
|
---|
[273] | 427 | The naive global visibility sampling works as follows: At every pass
|
---|
| 428 | of the algorithm visits scene objects sequentially. For every scene
|
---|
| 429 | object we randomly choose a point on its surface. Then a ray is cast
|
---|
[277] | 430 | from the selected point according to the randomly chosen direction
|
---|
| 431 | (see Figure~\ref{fig:sampling}). We use a uniform distribution of the
|
---|
| 432 | ray directions with respect to the half space given by the surface
|
---|
| 433 | normal. Using this strategy the samples at deterministically placed at
|
---|
| 434 | every object, with a randomization of the location on the object
|
---|
| 435 | surface. The uniformly distributed direction is a simple and fast
|
---|
| 436 | strategy to gain initial visibility information.
|
---|
[249] | 437 |
|
---|
[273] | 438 | \begin{figure}%[htb]
|
---|
[277] | 439 | \centerline{
|
---|
| 440 | \includegraphics[width=0.4\textwidth, draft=\DRAFTFIGS]{figs/sampling}
|
---|
| 441 | }
|
---|
| 442 |
|
---|
[273] | 443 | %\label{tab:online_culling_example}
|
---|
| 444 | \caption{Three objects and a set of view cells corresponding to leaves
|
---|
| 445 | of an axis aligned BSP tree. The figure depicts several random
|
---|
| 446 | samples cast from a selected object (shown in red). Note that most
|
---|
| 447 | samples contribute to more view cells. }
|
---|
[277] | 448 | \label{fig:sampling}
|
---|
[273] | 449 | \end{figure}
|
---|
[249] | 450 |
|
---|
[273] | 451 | The described algorithm accounts for the irregular distribution of the
|
---|
[249] | 452 | objects: more samples are placed at locations containing more
|
---|
| 453 | objects. Additionally every object is sampled many times depending on
|
---|
| 454 | the number of passes in which this sampling strategy is applied. This
|
---|
| 455 | increases the chance of even a small object being captured in the PVS
|
---|
| 456 | of the view cells from which it is visible.
|
---|
| 457 |
|
---|
[273] | 458 | Each ray sample can contribute by a associating a number of view cells
|
---|
| 459 | with the object from which the sample was cast. If the ray does not
|
---|
| 460 | leave the scene it also contributes by associating the pierced view
|
---|
| 461 | cells to the terminating object. Thus as the ray samples are cast we
|
---|
| 462 | can measure the average contribution of a certain number of most
|
---|
| 463 | recent samples. If this contribution falls bellow a predefined
|
---|
| 464 | constant we move on to the next sampling strategy, which aim to
|
---|
| 465 | discover more complicated visibility relations.
|
---|
| 466 |
|
---|
[249] | 467 |
|
---|
[266] | 468 | \subsection{Accounting for View Cell Distribution}
|
---|
[249] | 469 |
|
---|
[266] | 470 | The first modification to the basic algorithm accounts for irregular
|
---|
[272] | 471 | distribution of the view cells. Such a case is common for example in
|
---|
| 472 | urban scenes where the view cells are mostly distributed in a
|
---|
| 473 | horizontal direction and more view cells are placed at denser parts of
|
---|
[249] | 474 | the city. The modification involves replacing the uniformly
|
---|
| 475 | distributed ray direction by directions distributed according to the
|
---|
[266] | 476 | local view cell directional density. This means placing more samples at
|
---|
| 477 | directions where more view cells are located: We select a random
|
---|
[277] | 478 | view cell which lies at the half space given by the surface normal at the
|
---|
[249] | 479 | chosen point. We pick a random point inside the view cell and cast a
|
---|
| 480 | ray towards this point.
|
---|
| 481 |
|
---|
| 482 |
|
---|
[266] | 483 | \subsection{Accounting for Visibility Events}
|
---|
[249] | 484 |
|
---|
[277] | 485 | Visibility events correspond to appearance and disappearance of
|
---|
[273] | 486 | objects with respect to a moving view point. In polygonal scenes the
|
---|
[266] | 487 | events defined by event surfaces defined by three distinct scene
|
---|
| 488 | edges. Depending on the edge configuration we distinguish between
|
---|
[277] | 489 | vertex-edge events (VE) and triple edge (EEE) events. The VE surfaces
|
---|
[266] | 490 | are planar planes whereas the EEE are in general quadratic surfaces.
|
---|
[249] | 491 |
|
---|
[282] | 492 | To account for these events we explicitly place samples passing by
|
---|
| 493 | the object edges which are directed to edges and/or vertices of other
|
---|
| 494 | objects. In this way we perform stochastic sampling at boundaries of
|
---|
| 495 | the visibility complex~\cite{Durand:1996:VCN}.
|
---|
[249] | 496 |
|
---|
[273] | 497 | The first strategy starts similarly to the above described sampling
|
---|
| 498 | methods: we randomly select an object and a point on its surface. Then
|
---|
| 499 | we randomly pickup an object from its PVS. If we have mesh
|
---|
| 500 | connectivity information we select a random silhouette edge from this
|
---|
| 501 | object and cast a sample which is tangent to that object at the
|
---|
[282] | 502 | selected edge.
|
---|
[249] | 503 |
|
---|
[273] | 504 | The second strategy works as follows: we randomly pickup two objects
|
---|
| 505 | which are likely to see each other. Then we determine a ray which is
|
---|
| 506 | tangent to both objects. For simple meshes the determination of such
|
---|
| 507 | rays can be computed geometrically, for more complicated ones it is
|
---|
| 508 | based again on random sampling. The selection of the two objects works
|
---|
| 509 | as follows: first we randomly select the first object and a random
|
---|
| 510 | non-empty view cell for which we know that it can see the object. Then
|
---|
| 511 | we randomly select an object associated with that view cell as the
|
---|
| 512 | second object.
|
---|
| 513 |
|
---|
| 514 |
|
---|
| 515 |
|
---|
| 516 | \section{Summary}
|
---|
| 517 |
|
---|
[277] | 518 | This chapter described the global visibility sampling algorithm which
|
---|
| 519 | forms a core of the visibility preprocessing framework. The global
|
---|
| 520 | visibility sampling computes aggressive visibility, i.e. it computes a
|
---|
| 521 | subset of the exact PVS for each view cell. The aggressive sampling
|
---|
| 522 | provides a fast progressive solution and thus it can be easily
|
---|
| 523 | integrated into the game development cycle. The sampling itself
|
---|
| 524 | involves several strategies which aim to progressively discover more
|
---|
| 525 | visibility relationships in the scene.
|
---|
[273] | 526 |
|
---|
| 527 | The methods presented in this chapter give a good initial estimate
|
---|
| 528 | about visibility in the scene, which can be verified by the mutual
|
---|
[277] | 529 | visibility algorithms described in the next chapter.
|
---|
[273] | 530 |
|
---|
| 531 |
|
---|
| 532 |
|
---|
| 533 |
|
---|