source: trunk/VUT/doc/SciReport/mutual.tex @ 284

Revision 284, 26.4 KB checked in by bittner, 19 years ago (diff)
Line 
1\chapter{Mutual Visibility Verification}
2
3\label{chap:mutual}
4
5The aggressive visibility sampling discussed in the previous chapter is
6a good candidate if a fast visibility solution is required (e.g.
7during the development cycle). However for final solution (production)
8we should either be sure that there can be no visible error due to the
9preprocessed visibility or the error is sufficiently small and thus
10not noticeable.
11
12The mutual visibility verification starts with identifying a minimal
13set of object/view cell pairs which are classified as mutually
14invisible. We process the objects sequentially and for every given
15object we determine the view cells which form the boundary of the
16invisible view cell set.
17
18This boundary it is based on the current view cell visibility
19classifications. We assume that there is a defined connectivity
20between the view cells which is the case for both BSP-tree or kD-tree
21based view cells. Then given a PVS consisting of visible view cells
22(with respect to an object) we can find all the neighbors of the
23visible view cells which are invisible. In order words a view cell
24belongs to this boundary if it is classified invisible and has at
25least one visible neighbor. If all view cells from this boundary are
26proven invisible, no other view cell (behind this boundary) can be
27visible. If the verification determines some view cells as visible,
28the current invisible boundary is extended and the verification is
29applied on the new view cells forming the boundary.
30
31The basic operation of the verification is mutual visibility test
32between an object and a view cell. This test works with a bounding
33volume of the object and the boundary of the view cell. In the most
34general case both are defined bound by a convex polyhedron, in a
35simpler case both are defined by an axis aligned bounding box.
36
37Below, we describe three different mutual visibility verification
38algorithms. The first algorithm which is described in most detail
39computes exact visibility. The second one is a conservative algorithm
40and the third one is an approximate algorithm with a guaranteed error
41bound.
42
43
44\section{Exact Verifier}
45
46The exact mutual visibility verifier computes exact visibility between
47two polyhedrons in the scene. This is computed by testing visibility
48between all pairs of potentially visible polygons of these
49polyhedrons.  For each pair of tested polygons the computation is
50localized into the shaft defined by their convex hull. This shaft is
51used to determine the set of relevant occluders~\cite{Haines94}.
52
53\subsection{Occlusion tree}
54\label{sec:rot3d_ot}
55
56 The occlusion tree for the visibility from region problem is a 5D BSP
57tree maintaining a collection of the 5D blocker
58polyhedra~\cite{bittner:02:phd}. The tree is constructed for each
59source polygon $P_S$ and represents all rays emerging from $P_S$. Each
60node $N$ of the tree represents a subset of line space ${\mathcal
61Q^*_N}$. The root of the tree represents the whole problem-relevant
62line set ${\mathcal L}_R$. If $N$ is an interior node, it is
63associated with a \plucker plane $\pplane_N$.  Left child of $N$
64represents ${\mathcal Q^*_N} \cap \pplane^-_N$, right child ${\mathcal
65Q^*_N} \cap \pplane^+_N$, where $\pplane^-_N$ and $\pplane^+_N$ are
66halfspaces induced by $\pplane_N$.
67
68 Leaves of the occlusion tree are classified $in$ or $out$. If $N$ is
69an $out$-leaf, ${\mathcal Q^*_N}$ represents unoccluded rays emerging
70from the source polygon $P_S$. If $N$ is an $in$-leaf, it is
71associated with an occluder $O_N$ that blocks the corresponding set of
72rays ${\mathcal Q^*_N}$. Additionally $N$ stores a fragment of the
73blocker polyhedron $B_N$ representing ${\mathcal Q^*_N}$. The
74intersection of $B_N$ and the \plucker quadric corresponds to a set of
75stabbers ${\cal S}_N$ through which $O_N$ is visible from $P_S$. A 2D
76example of an occlusion tree is shown at Figure~\ref{fig:ot}.
77
78\begin{figure}[htb]
79\centerline{
80\includegraphics[width=0.9\textwidth,draft=\DRAFTFIGS]{figs/ot1}}
81\caption{A 2D example of an occlusion tree. Rays intersecting scene polygons
82are represented by polyhedra P1, P2 and P3. The occlusion tree represents a union
83of the polyhedra. Note that P2 has been split during the insertion process.}
84\label{fig:ot}
85\end{figure}
86
87
88%%  Consider a source polygon and a single occluder such as in
89%% Figure~\ref{lines3}-(a). The corresponding elementary occlusion tree
90%% has interior nodes associated with \plucker hyperplanes corresponding
91%% to edges of the two polygons.
92
93
94\subsection{Occlusion tree construction}
95
96\label{sec:rot3d_construct}
97
98 The occlusion tree is constructed incrementally by inserting blocker
99polyhedra in the order given by the size of the polygons. When
100processing a polygon $P_j$ the algorithm inserts a polyhedron
101$B_{P_SP_j}$ representing the feasible line set between the source
102polygon $P_S$ and the polygon $P_j$. The polyhedron is split into
103fragments that represent either occluded or unoccluded rays.
104
105 We describe two methods that can be used to insert a blocker
106polyhedron into the occlusion tree. The first method inserts the
107polyhedron by splitting it using hyperplanes encountered during the
108traversal of the tree. The second method identifies hyperplanes that
109split the polyhedron and uses them later for the construction of
110polyhedron fragments in leaf nodes.
111
112
113
114\subsubsection{Insertion with splitting}
115
116\label{sec:rot3_insertwithsplit}
117
118 The polyhedron insertion algorithm maintains two variables --- the
119current node $N_c$ and the current polyhedron fragment
120$B_c$. Initially $N_c$ is set to the root of the tree and $B_c$ equals
121to $B_{P_SP_j}$. The insertion of a polyhedron in the tree proceeds as
122follows: If $N_c$ is an interior node, we determine the position of
123$B_c$ and the hyperplane $\pplane_{N_c}$ associated with $N_c$. If
124$B_c$ lies in the positive halfspace induced by $\pplane_{N_c}$ the
125algorithm continues in the right subtree.  Similarly, if $B_c$ lies in
126the negative halfspace induced by $\pplane_{N_c}$,  the algorithm
127continues in the left subtree. If $B_c$ intersects both halfspaces, it
128is split by $\pplane_{N_{c}}$ into two parts $B^+_{c}$ and $B^-_{c}$
129and the algorithm proceeds in both subtrees of $N_c$ with relevant
130fragments of $B_{c}$.
131
132If $N_{c}$ is a leaf node then we make a decision depending on its
133classification.  If $N_{c}$ is an $out$-leaf then $B_{c}$ is visible
134and $N_c$ is replaced by the elementary occlusion tree of $B_{c}$. If
135$N_{c}$ is an $in$-leaf it corresponds to already occluded rays and no
136modification to the tree necessary. Otherwise we need to {\em merge}
137$B_{c}$ into the tree. The merging replaces $N_{c}$ by the elementary
138occlusion tree of $B_c$ and inserts the old fragment $B_{N_{c}}$ in
139the new subtree.
140
141\subsubsection{Insertion without splitting}
142\label{sec:insertion_nosplit}
143
144 The above described polyhedron insertion algorithm requires that the
145polyhedron is split by the hyperplanes encountered during the
146traversal of the occlusion tree. Another possibility is an algorithm
147that only tests the position of the polyhedron with respect to the
148hyperplane and remembers the hyperplanes that split the polyhedron on
149the path from the root to the leaves. Reaching a leaf node these
150hyperplanes are used to construct the corresponding polyhedron
151fragment using a polyhedron enumeration algorithm.
152
153 The splitting-free polyhedron insertion algorithm proceeds as
154follows: we determine the position of the blocker polyhedron and the
155hyperplane $\pplane_{N_c}$ associated with the current node $N_c$. If
156$B_c$ lies in the positive halfspace induced by $\pplane_{N_c}$ the
157algorithm continues in the right subtree.  Similarly if $B_c$ lies in
158the negative halfspace induced by $\pplane_{N_c}$  the algorithm
159continues in the left subtree. If $B_c$ intersects both halfspaces the
160algorithm proceeds in both subtrees of $N_c$ and $\pplane_{N_c}$ is
161added to the list of splitting hyperplanes with a correct sign for
162each subtree. Reaching an $out$-leaf the list of splitting hyperplanes
163and the associated signs correspond to halfspaces bounding the
164corresponding polyhedron fragment. The polyhedron enumeration
165algorithm is  applied using these halfspaces and the original
166halfspaces defining the blocker polyhedron. Note that it is possible
167that no feasible polyhedron exists since the intersection of
168halfspaces is empty. Such a case occurs due to the conservative
169traversal of the tree that only tests the position of the inserted
170polyhedron with respect to the splitting hyperplanes. If the fragment
171is not empty, the tree is extended as described in the previous
172section.
173
174Reaching an $in$-leaf the polygon positional test is applied. If the
175inserted polygon is closer than the polygon associated with the leaf,
176the polyhedron fragment is constructed and it is merged in the tree as
177described in the previous section. The splitting-free polyhedron
178insertion algorithm has the following properties:
179
180\begin{itemize}
181\item If the polyhedron reaches only $in$-leaves the 5D set operations
182  on the polyhedron are avoided completely.
183\item If the polyhedron reaches only a few leaves the application of the
184  polyhedron enumeration algorithm is potentially more efficient than
185  the sequential splitting. On the contrary, when reaching many
186  $out$-leaves the splitting-free method makes less use of coherence,
187  i.e. the polyhedron enumeration algorithm is applied independently
188  in each leaf even if the corresponding polyhedra are bound by
189  coherent sets of hyperplanes.
190\item An existing implementation of the polyhedron enumeration
191algorithm can be used~\cite{cdd_site,lrs_site}.
192\end{itemize}
193
194
195 The polyhedron enumeration algorithm constructs the polyhedron as an
196intersection of a set of halfspaces. The polyhedron is described as a
197set of {\em vertices} and {\em rays} and their adjacency to the
198hyperplanes bounding the polyhedron~\cite{Fukuda:1996:DDM,avis96}. The
199adjacency information is used to construct a 1D skeleton of the
200polyhedron that is required for computation of the intersection with
201the \plucker quadric.
202
203
204
205\subsection{Visibility test}
206
207\label{sec:rot3d_vistest}
208
209 The visibility test classifies visibility of a given polygon with respect
210to the source polygon. The test can be used to classify visibility of
211a polyhedral region by applying it on the boundary faces of the region
212and combining the resulting visibility states.
213
214%\subsection{Exact visibility test}
215
216 The exact visibility test for a given polyhedral region proceeds as
217follows: for each face of the region facing the given source polygon
218we construct a blocker polyhedron. The blocker polyhedron is then
219tested for visibility by the traversal of the occlusion tree. The
220visibility test proceeds as the algorithms described in
221Section~\ref{sec:rot3d_construct}, but no modifications to the tree
222are performed. If the polyhedron is classified as visible in all
223reached leaves, the current face is fully visible. If the polyhedron
224is invisible in all reached leaves, the face is invisible. Otherwise
225it is partially visible since some rays connecting the face and the
226source polygon are occluded and some are unoccluded. The visibility of
227the whole region can computed using a combination of visibility states
228of its boundary faces according to
229Table~\ref{table:vis_states}. However, since we are interested only in
230verification of mutual invisibility as soon as we find a first visible
231fragment the test can be terminated.
232
233\begin{table}[htb]
234\begin{center}
235\begin{tabular}{|c|c||c|}
236\hline
237Fragment A & Fragment B & A $\cup$ B \\
238\hline
239\hline
240F & F & F\\
241\hline
242I & I & I\\
243\hline
244I & F & P\\
245\hline
246F & I & P\\
247\hline
248P & $*$ & P\\
249\hline
250$*$ & P & P\\
251\hline
252\end{tabular}
253\begin{tabular}{cl}
254I  & -- invisible\\
255P    & -- partially visible\\
256F  & -- fully visible\\
257$*$  & -- any of the I,P,F states
258\end{tabular}
259\end{center}
260\caption{Combining visibility states of two fragments.}
261\label{table:vis_states}
262\end{table}
263
264
265% \subsection{Conservative visibility test}
266
267% \label{sec:rot3_conserva}
268
269%  The conservative visibility test provides a fast estimation of
270% visibility of the given region since it does not require the 5D
271% polyhedra enumeration. Visibility of the given face of the region is
272% determined by a traversal of the occlusion tree and testing the
273% position of the corresponding blocker polyhedron with respect to the
274% encountered hyperplanes as described in
275% Section~\ref{sec:insertion_nosplit}.  If the blocker polyhedron
276% reaches only $in$-leaves and the face is behind the polygon(s)
277% associated with the leaves, the face is classified invisible
278% . Otherwise, it is conservatively classified as visible.  The
279% visibility of the whole region is determined using a combination of
280% visibility of its faces as mentioned in the previous section.
281
282\subsection{Optimizations}
283
284\label{sec:rot3d_optimizations}
285
286 Below we discuss several optimization techniques that can be used to
287improve the performance of the algorithm. The optimizations do not
288alter the accuracy of the visibility algorithm.
289 
290% \subsection{Occluder sorting}
291
292%  Occluder sorting aims to increase the accuracy of the front-to-back
293% ordering determined by the approximate occlusion sweep. Higher
294% accuracy of the ordering decreases the number of the late merging of
295% blocker polyhedra in the tree.  Recall that the merging extends the
296% occlusion tree by a blocker polyhedron corresponding to an occluder
297% that hides an already processed occluder.
298
299%  The occluder sorting is applied when reaching a leaf node of the
300% spatial hierarchy during the approximate occlusion sweep. Given a leaf
301% node $N$ the occluder sorting proceeds as follows:
302
303% \begin{enumerate}
304% \item Determine a ray $r$ piercing the center of the source polygon
305% $P_S$ and the node $N$.
306% \item Compute intersections of $r$ and all supporting planes of the
307% polygons associated with $N$.
308% \item Sort the polygons according to the front-to-back order of the
309% corresponding intersection points along $r$.
310% \end{enumerate}
311
312% The occluder sorting provides an exact priority order within the given
313% leaf in the case that the polygons are pierced by the computed ray $r$
314% and they do not intersect.
315
316
317\subsubsection{Visibility estimation}
318
319 The visibility estimation aims to eliminate the polyhedron
320enumeration in the leaves of the occlusion tree. If we find out that
321the currently processed polygon is potentially visible in the given
322leaf-node (it is an $out$-leaf or it is an $in$-leaf and the
323positional test reports the polygon as the closest), we estimate its
324visibility by shooting random rays. We can use the current occlusion
325tree to perform ray shooting in line space.  We select a random ray
326connecting the source polygon and the currently processed
327polygon. This ray is mapped to a \plucker point and this point is
328tested for inclusion in halfspaces defined by the \plucker planes
329splitting the polyhedron on the path from to root to the given
330leaf. If the point is contained in all tested halfspaces the
331corresponding ray is unoccluded and the algorithm inserts the blocker
332polyhedron into the tree. Otherwise it continues by selecting another
333random ray until a predefined number of rays was tested.
334
335 The insertion of the blocker polyhedron devotes further
336discussion. Since the polyhedron was not enumerated we do not know
337which of its bounding hyperplanes really bound the polyhedron fragment
338and which are redundant for the given leaf.  Considering all
339hyperplanes defining the blocker polyhedron could lead to inclusion of
340many redundant nodes in the tree. We used a simple conservative
341algorithm that tests if the given hyperplane is bounding the
342(unconstructed) polyhedron fragment. For each hyperplane $H_i$
343bounding the blocker polyhedron the algorithm tests the position of
344extremal lines embedded in this hyperplane with respect to each
345hyperplane splitting the polyhedron. If mappings of all extremal lines
346lay in the same open halfspace defined by a splitting hyperplane,
347hyperplane $H_i$ does not bound the current polyhedron fragment and
348thus it can be culled.
349
350
351\subsubsection{Visibility merging}
352
353 Visibility merging aims to propagate visibility classifications from
354the leaves of the occlusion tree up into the interior nodes of the
355hierarchy. Visibility merging is connected with the approximate
356occlusion sweep, which simplifies the treatment of the depth of the
357scene polygons.
358
359The algorithm classifies an interior node of the occlusion tree as
360occluded ($in$) if the following conditions hold:
361
362\begin{itemize}
363\item Both its children are $in$-nodes.
364\item The occluders associated with both children are strictly closer than
365  the closest unswept node of the spatial hierarchy.
366\end{itemize}
367
368 The first condition ensures that both child nodes correspond to
369occluded nodes. The second condition ensures that any unprocessed
370occluder is behind the occluders associated with the children. Using
371this procedure the effective depth of the occlusion becomes
372progressively smaller if more and more rays become occluded.
373
374
375
376\section{Conservative Verifier}
377
378A conservative verifier is a faster alternative to the exact
379visibility verifier described above. The verifier is an extension of
380the strong occlusion algorithm of Cohen-Or et
381al.~\cite{cohen-egc-98}. In particular our verifier refines the search
382for a strong occluder by using a hierarchical subdivision of space of
383lines connecting the two regions tested for mutual
384visibility. Initially the shaft bounding the the tested regions is
385constructed. Rays bounding the shaft are traced through the scene and
386we compute all intersections with the scene objects between the tested
387regions. The the algorithm proceeds as follows:
388
389\begin{itemize}
390\item In the case that any ray does not intersect any object the
391tested regions are classified as visibility and the algorithm
392terminates.
393\item If the rays intersect the same convex object (at any
394depth) this object is a strong occluder with respect to the shaft and
395thus it also hides all rays in the corresponding shaft.
396\item If the rays do not intersect a single convex object four new
397shafts are constructed by splitting both regions in half and the
398process is repeated recursively.
399\end{itemize}
400
401If the subdivision does not terminate till reaching a predefined
402subdivision depth, we conservatively classify the tested regions as
403mutually visible. The conservative verifier is illustrated at
404Figure~\ref{fig:conservative_sampling}.
405
406\begin{figure}[htb]
407\centerline{
408\includegraphics[width=0.7\textwidth,draft=\DRAFTFIGS]{figs/conservative_sampling}}
409\caption{An example of the conservative visibility verification. The figure shows two
410  tested regions (the view cell and the object) and several
411  occluders. For sake of clarity we only show samples which are
412  boundaries of shafts on one path of the line space subdivision tree.
413  The subdivision terminates at the yellow shaft since a single strong
414  occluder has been found. }
415\label{fig:conservative_sampling}
416\end{figure}
417
418
419\section{Error Bound Approximate Verifier}
420
421The approximate verifier will be based on the similar idea as the
422conservative one. However it will behave differently in the finer
423subdivision of the ray shafts. The idea is to use the above algorithm
424as far as the shafts get small enough that we can neglect objects
425which can be seen through such a shaft. Even if not all rays inside
426the shaft are not blocked by scene objects, a pixel error induced due
427to omission of objects potential visible behind the shaft will be
428below a given threshold.
429
430For the computation of the maximal error due to the current shaft we
431assume that one tested region is a view cell, whereas the other is an
432object bounding box or cell of the spatial hierarchy. The threshold is
433computed as follows: We first triangulate the farthest intersection
434points in the shaft as seen from the view cell side of the shaft. Then
435for each computed triangle we calculate a point in the view cell which
436maximizes the projected area of the triangle (see
437Figure~\ref{fig:approximate_sampling}).  The conservative estimate of
438the maximal error is then given by a sum of the computed projected
439areas. If this error is below a specified threshold we terminate the
440subdivision of the current shaft.
441
442%We calculate a point in the view cell which
443%maximizes the projected area of the object with respect to the shaft
444%. The conservative estimate
445%of the maximal error is then given by the computed projected area.
446
447\begin{figure}[htb]
448\centerline{
449\includegraphics[width=0.7\textwidth,draft=\DRAFTFIGS]{figs/approximate_sampling2}}
450\caption{An example of the approximate error bound visibility verification. The figure shows two
451  tested regions (the view cell and the object) and two
452  occluders. Due to the 2D nature of the example the triangulation is depicted as
453  the red line segment. The maximal error for the possible viewpoints in the shaft
454  corresponds to the angle $\alpha$.
455}
456\label{fig:approximate_sampling}
457\end{figure}
458
459%Option: - if there is sufficient number of samples from 1 + 2 and some
460%of their statistic (local spatial and directional density + distances
461%to the visible objects), maybe an error estimate could only be derived
462%from there values.
463
464% a) is perhaps the most interesting since this has not been done so far at all. I though about different methods how to do that (e.g. maintaining a triangulated front visible layer), but I always found some problem. I believe that the method which is almost implemented now is solid and I just wonder what performance it will achieve.
465
466% The basic idea is the following:
467
468% Use 2 plane parametrization for describing all lines intersecting the object and the view cell. The line sets will be described by aligned rectangles on the two planes which allows to construct convex shafts bounded always by only 4 lines. After determing the initial rectangles bounding the whole line set perform recursive subdivsion as follows:
469
470% 1. Cast the 4 corner rays and deterine ALL intersections with the occluding objects
471
472% 2. If any ray is unoccluded termite the whole test with VISIBLE and extend the PVS of the object with the new view cell (and possibly more if the rays goes further). Start the verification for the new view cells in the occluded layer.
473
474% 3. If all 4 rays pierce the same convex mesh, (or mesh triangle for non convex meshes) terminate this branch with INVISIBLE. Note the terminating mesh need not be the front most one.
475
476% 4. Triangulate the depth of the shaft as seen from the viecell side of the shaft and compute the maximal projected area of the 2 computed triangles. This determines the maximal pixel error we can make by terminating this branch as invisible.
477% Note that here it would be the best to selected those intersections for the rays which have the most similar depths to better estimate the maximal error, i.e. the "depth triangles" need not be formed by the first visible layer.
478
479% 5. If 4 does not terminate subdivide either the view cell or the object rectangle depending on the sample depths and error computed.
480
481% It is actually quite simple to create a conservative variant of the algorithm: subdivide only to a given depth and avoid test 4. Then the samples can only be terminated by a "STRONG occluder" which hides the whole shaft. This is similar to Dannys method, but here a hierarchical shaft subdivision is performed which should deliver much more accuracy.
482
483
484% > Partly: area subdivision algorithm does not only cast "corner" rays, but maintains lists of the triangles for the given area. However the basic idea is the same: subdivide the set or rays until there is a trivial decision (a single convex object intersected by all corner rays) or the error is too small. The second criterion is different from the from-poin t setup, since the error cannot be evaluated in a single projection plane.
485% > That is why this triangulation would be done: Imagine that the 4 corner rays of a shaft intersect some object(s) in the scene. Now connect these intersection points by creating two triangles. These triangles do not exist in the scene, but define the largest possible windows through which we can see further in the shaft. Now it is easy to find two points at the origin of the shaft which maximize the projected area of the two triangles. The sum of these areas gives a conservative estimate of the spatial angle error which can be made by not subdividing the shaft any further.
486% > Is this description clearer?
487
488
489% partly - I just don't see it in front of me now. How is the result influenced by which triangles are chosen? Is it so that the nearer the intersections, the bigger the error?
490
491
492
493\section{Summary}
494
495\label{sec:rot3d_summary}
496
497 This chapter presented a mutual visibility verification algorithms, which determine
498 whether two regions in the scene are visible.
499
500 First, we have described an exact visibility algorithm which is a
501simple of modification of an algorithm for computing from-region
502visibility in polygonal scenes. The key idea is a hierarchical
503subdivision of the problem-relevant line set using \plucker
504coordinates and the occlusion tree.  \plucker coordinates allow to
505perform operations on sets of lines by means of set theoretical
506operations on the 5D polyhedra. The occlusion tree is used to maintain
507a union of the polyhedra that represent lines occluded from the given
508region (polygon). We described two algorithms for construction of the
509occlusion tree by incremental insertion of blocker polyhedra. The
510occlusion tree was used to test visibility of a given polygon or
511region with respect to the source polygon/region. We proposed several
512optimization of the algorithm that make the approach applicable to
513large scenes. The principal advantage of the exact method over the
514conservative and the approximate ones is that it does not rely on
515various tuning parameters that are characterizing many conservative or
516approximate algorithms. On the other hand the exactness of the method
517requires higher computational demands and implementation effort.
518
519Second, we have described a conservative verifier which is an
520extension of the algorithm based on strong occluders. The conservative
521verifier requires a specification of the shaft size at which the
522tested regions are conservatively classified as visible.
523
524Third, we have described an approximate error bound verifier which
525extends the conservative verifier by using automatic termination
526criteria based on the estimation of maximal error for the given shaft.
527
Note: See TracBrowser for help on using the repository browser.