source: trunk/VUT/doc/SciReport/analysis.tex @ 283

Revision 283, 41.7 KB checked in by mattausch, 19 years ago (diff)
RevLine 
[249]1\chapter{Analysis of Visibility in Polygonal Scenes}
2
[277]3\label{chap:analysis}
4
[266]5This chapter provides analysis of the visibility in polygonal scenes,
[277]6which are the input for all developed algorithms. The visibility analysis
[266]7uncoveres the complexity of the from-region and global visibility
8problems and thus it especially important for a good design of the
9global visibility preprocessor. To better undestand the visibility
10relationships in primal space we use mapping to line space, where the
11visibility interactions can be observed easily by interactions of sets
12of points. Additionally for the sake of clarity, we first analyze
[277]13visibility in 2D and then extend the analysis to 3D polygonal scenes. Visibility in 3D is described using \plucker
[249]14
[266]15\section{Analysis of visibility in 2D}
[249]16
17\label{LINE_SPACE}
18
19The proposed visibility algorithm uses a mapping of oriented 2D lines to
20points in 2D oriented projective space --- {\em line space}. Such a
21mapping allows to handle sets of lines much easier than in the primal
22space~\cite{pv-vc-93}.
23
24 We use a 2D projection of Pl\"ucker
25coordinates~\cite{Stolfi:1991:OPG} to parametrize lines in the plane.
26This mapping corresponds to an ``oriented form'' of the duality
27between points and lines in 2D.  Let $l$ be an oriented line in
28${\mathcal R}^2$ and let $u=(u_x, u_y)$ and $v=(v_x, v_y)$ be two
29distinct points lying on $l$. Line $l$ oriented from $u$ to $v$ can be
30described by the following matrix:
31
32$$
33M_l=\left(
34\begin{array}{cccc}
35u_x & u_y & 1 \\
36v_x & v_y & 1 
37\end{array}
38\right)
39$$
40
41Pl\"ucker coordinates $l^*$ of $l$ are minors of $M_l$:
42
43$$
44l^* = (l^*_x, l^*_y, l^*_z) = (u_y - v_y, v_x - u_x, u_x v_y - u_y  v_x ).
45$$
46
47$l^*$ can be interpreted as homogeneous coordinates of a point in 2D
48{\em oriented projective space} ${\cal P}^2$. Two oriented lines are
49equal if and only if their Pl\"ucker coordinates differ only by a
50positive scale factor. $l^*$ also corresponds to coefficients of the
51implicit equation of a line: $l'$ expressed as $l': ax + by + c= 0$
52induces two oriented lines $l^*_1$, $l^*_2$, with Pl\"ucker
53coordinates $l^*_1 = (a, b, c)$ and $l^*_2 = -(a,b,c)$.  The \plucker
54coordinates of 2D lines defined in this chapter are a simplified form
[277]55of the \plucker coordinates for 3D lines, which will be discussed
[283]56below in this chapter: \plucker coordinates of a 2D line correspond
[249]57to the \plucker coordinates of a 3D line embedded in the $z = 0$ plane
58after removal of redundant coordinates (equal to 0) and permutation of
59the remaining ones (including some sign changes).
60
61
62 Homogeneous coordinates are often normalized, e.g. $l^*_N = (a/b, 1,
63c/b)$. The normalization introduces a singularity --- in our example
64vertical lines map to points at infinity. To avoid singularities we
65treat ${\cal P}^2$ as 3D linear space and call it {\em line space}
66denoted ${\mathcal L}$. Consequently, $l^*$ represents a halfline in
67${\mathcal L}$. All points on halfline $l^*$ represent the same
68oriented line $l$.
69
70 To sum up: an oriented line in 2D is mapped to a halfline beginning
71at the origin in 3D. An example of the concept is depicted in
72Figures~\ref{lines1}-(a) and ~\ref{lines1}-(b). Further in this
73chapter we will mostly use ``projected'' 2D illustrations of line
74space (such as in Figure~\ref{lines1}-(c)). We will still talk about
75planes and halflines, but they will be depicted as lines and points,
76respectively, for the sake of clarity of the presentation.
77
78
79\subsection{Lines passing through a point}
80
81 A {\em pencil of oriented lines} passing through a point $p = (p_x,
82p_y)  \in {\mathcal R}^2$ maps to an oriented plane $p^*$ in line
83space that is expressed as:
84$$
85p^* = \{(x,y,z) | (x,y,z) \in {\mathcal L}, p_x x + p_y y + z = 0\}.
86$$
87
88This plane subdivides ${\mathcal L}$ in two open halfspaces $p^*_+$
89and $p^*_-$. Points in $p^*_-$ correspond to oriented lines passing
90clockwise around $p$ (see Figure~\ref{lines1}).  Points in $p^*_+$
91correspond to oriented lines passing counterclockwise around $p$
92(these relations depend on the orientation of the primal space). We
93denote $-p^*$ an oriented plane opposite to $p^*$ that can be
94expressed as:
95$$
96-p^* = \{(x,y,z) | (x,y,z) \in {\mathcal L}, -p_x x - p_y y - z = 0\}.
97$$
98
99
100\begin{figure*}[tb]
101\rule{0pt}{0pt}\hfill
102\includegraphics[width=1.0\textwidth,draft=\DRAFTFIGS]{figs/lines1}
103\hfill\rule{0pt}{0pt}
104\centerline{\small \hspace{0.01\textwidth}{\bf (a)}\hspace{0.3\textwidth} {\bf (b)} \hspace{0.3\textwidth} {\bf (c)}}
105\vspace{-1.5em}
106\caption{
107{\bf (a)} Four oriented lines in primal space.
108{\bf (b)} Mappings of the four lines and point p.
109Lines intersecting p map to plane $p^*$.
110Lines passing clockwise (counterclockwise) around $p$, map to
111$p^*_-$ ($p^*_+$).
112{\bf (c)} The situation after projection to a plane perpendicular to $p^*$.  }
113\label{lines1}
114\end{figure*}
115
116\subsection{Lines passing through a line segment}
117
118 Oriented lines passing through a line segment can be decomposed into
119two sets depending on their orientation.  Consider a supporting line
120$l_S$ of a line segment $S$, that partitions the plane in open
121halfspaces $S^+$ and $S^-$. Denote $a$ and $b$ the two endpoints of
122$S$ and $a^*$ and $b^*$ their mappings to ${\mathcal L}$. Lines that
123intersect $S$ and ``come from'' $S^-$ can be expressed in line space
124as an intersection of halfspaces $a^*_+$ and $b^*_-$.  The opposite
125oriented lines intersecting $S$ are expressed as $a^*_- \cap b^*_+$
126(see Figure~\ref{lines2}-(a,b)).
127
128%\begin{minipage}{\textwidth}
129
130\begin{figure}[htb]
131\rule{0pt}{0pt}\hfill
132\includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/lines2}
133\hfill\rule{0pt}{0pt}
134\centerline{\small
135\hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
136}
137\vspace{-1.5em}
138\caption{ {\bf (a)} A line segment $S$ and three oriented lines that
139intersect $S$.  {\bf (b)} The situation in line space: the projection of two
140wedges corresponding to lines intersecting $S$. Mappings of supporting
141line $l_S$ of $S$ are two halflines that project to point
142$l_S^*$. Line $k$ intersects point $b$ and therefore maps to plane
143$b^*$. Lines $m$ and $n$ map to the wedge corresponding to their
144orientation.  }
145\label{lines2}
146\end{figure}
147
148
149
150
151\subsection{Lines passing through two line segments}
152
153\label{sec:blocker_polygon}
154
155Consider two disjoint line segments such as those depicted in
156Figure~\ref{lines3}-(a). The set of lines passing through the two line
157segments can be described as an intersection of four halfspaces in
158line space. The four halfspaces correspond to mappings of endpoints of
159the two line segments.  Since the halfspaces pass through the origin
160of ${\mathcal L}$, their intersection is a pyramid with the apex at
161the origin. The boundary halflines of the pyramid correspond to
162mappings of the four {\em extremal lines} induced by the two
163segments. Denote ${\mathcal P}(S, O)$ a line space pyramid
164corresponding to oriented lines intersecting line segments $S$ and $O$
165in this order.  We represent the pyramid by a {\em blocker polygon}
166$B(S, O)$ (see Figure~\ref{lines3}-(b)). Since $B(S, O)$ only
167represents the pyramid ${\mathcal P}(S, O)$, it need not be a planar
168polygon, i.e. its vertices may lay anywhere on the boundary halflines
169of ${\mathcal P}(S, O)$.  We normalize the vertex coordinates: they
170correspond to an intersection of the boundary halfline of ${\mathcal
171P}(S, O)$ and the unit sphere centered at the origin of ${\mathcal L}$.
172
173\begin{figure}[htb]
174\hfill\rule{0pt}{0pt}
175\includegraphics[width=0.7\textwidth,draft=\DRAFTFIGS]{figs/lines3}
176\hfill\rule{0pt}{0pt}
177\centerline{\small
178\hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
179}
180\vspace{-1.5em}
181\caption{ {\bf (a)} Two line segments and corresponding four extremal lines
182oriented from $S$ to $O$. Separating lines $ad$ and $bc$ bound region
183of partial visibility of $S$ behind $O$ (penumbra). Supporting lines
184$ac$ and $bd$ bound region where $S$ is invisible (umbra). {\bf (b)}
185Blocker polygon $B(S,O)$ representing pyramid ${\mathcal
186P}(S,O)$.
187}
188\label{lines3}
189\end{figure}
190
191
192In Figure~\ref{lines4}-(a), the supporting line of $cd$ intersects $ab$
193at point $x$.  The set of rays passing through $ab$ and $cd$ can be
194decomposed to rays passing through $ax$ and $cd$, and through $xb$
195and $cd$. Rays through $ax$ and $cd$ map to a pyramid that is
196described by intersection of only three halfspaces induced by mappings
197of $a$, $x$ and $d$. Rays through $xb$ and $cd$ can be
198described similarly. The configuration in line space is depicted in
199Figure~\ref{lines4}-(b).
200
201\begin{figure}[htb]
202\rule{0pt}{0pt}\hfill
203\includegraphics[width=0.7\textwidth,draft=\DRAFTFIGS]{figs/lines4}
204\hfill\rule{0pt}{0pt}
205\centerline{\small
206\hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
207}
208\vspace{-1.5em}
209\caption{ {\bf (a)} Degenerate configuration of line segments: the supporting
210line of $cd$ intersects $ab$ at point $x$. There are five extremal
211lines. Note, that there is no umbra region. {\bf (b)} In line space the
212configuration yields two pyramids sharing a boundary that is a
213mapping of the oriented line $cd$.
214}
215\label{lines4}
216\end{figure}
217
218\subsection{Lines passing through a set of line segments}
219
220 Consider a set of $n+1$ line segments. We call one line segment the
221{\em source} (denoted by $S$) and the other $n$ segments we call
222occluders (denoted by $O_k$, $1 \leq k \leq n$).  Further in the
223chapter we will use the term {\em ray} as a representative of an
224oriented line that is oriented from the source ``towards'' the
225occluders.
226
227Assume that we can process all occluders in a strict front-to-back
228order with respect to the given source. We have already processed $k$
229occluders and we continue by processing $O_{k+1}$.  $O_{k+1}$ can be
230visible through rays that correspond to the pyramid ${\mathcal P}(S,
231O_{k+1})$. Nevertheless some of these rays can be blocked by
232combination of already processed occluders $O_x$ ($1\leq x \leq k$).
233To determine if $O_{k+1}$ is visible we subtract all ${\mathcal
234P}(S,O_x)$ from ${\mathcal P}(S,O_{k+1})$:
235
236$$
237{\mathcal V}(S,O_{k+1}) = {\mathcal P}(S,O_{k+1})\ - \bigcup_{1 \leq x \leq k} {\mathcal P}(S,O_x)
238$$
239
240${\mathcal V}(S, O_{k+1})$ is a set pyramids representing rays through
241which $O_{k+1}$ is visible from $S$.  In turn, all rays corresponding
242to ${\mathcal V}(S,O_{k+1})$ are blocked behind $O_{k+1}$.  If
243${\mathcal V}(S, O_{k+1})$ is an empty set, occluder $O_{k+1}$ is
244invisible. This suggest incremental construction of an arrangement of
245pyramids ${\mathcal A}_k$ that corresponds to rays blocked by the
246$k$ processed occluders.  We determine ${\mathcal V}(S,O_{k+1})$ and
247${\mathcal A}_{k+1}$ (${\mathcal A}_0$ is empty):
248
249$$
250{\mathcal V}(S,O_{k+1}) = {\mathcal P}(S,O_{k+1}) \ - \ {\mathcal A}_k,
251$$
252$$
253{\mathcal A}_{k+1} = {\mathcal A}_k \cup {\mathcal P}(S,O_{k+1}) =
254{\mathcal A}_k \ \cup \ {\mathcal V}(S,O_{k+1}).
255$$
256
257 Figures~\ref{lines5}-(a,b) depict a projection of an arrangement
258${\mathcal A}_3$ of a source and three occluders. Note that the
259shorter the source line segment the narrower ($s^*_a$ and $s^*_b$ get
260closer) are the pyramids ${\mathcal P}(S,O_k)$.
261
262
263
264
265\begin{figure}[htb]
266\rule{0pt}{0pt}\hfill
267\includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/rot2new}
268\hfill\rule{0pt}{0pt}
269\centerline{\small
270\hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
271}
272\vspace{-1.5em}
273\caption{  {\bf (a)} The source line segment $S$ and three
274occluders. $Q_{1-3}$ denote unoccluded funnels.  {\bf (b)} The
275line space subdivision. For each cell, the corresponding occluder-sequence
276is depicted.  Note the cells $Q^*_1$, $Q^*_2$ and $Q^*_3$
277corresponding to unoccluded funnels.}
278\label{lines5}
279\end{figure}
280
281Recall that the pyramid ${\mathcal P}(S,O_k)$ is represented by
282blocker polygon $B(S,O_k)$. The construction of the arrangement
283${\mathcal A}_k$ resembles the from-point visibility problem, more
284specifically the hidden surface removal applied on the blocker
285polygons with respect to the origin of ${\mathcal L}$. The difference
286is that the depth information is irrelevant in line space. The
287priority of blocker polygons is either completely determined by the
288processing order of occluders or their depth must be compared in
289primal space. This observation is supported by the classification of
290visibility problems presented in
[277]291Chapter~\ref{chap:introduction}. Visibility from point in 3D and visibility
[249]292from region in 2D induce a two-dimensional problem-relevant line
293set. This suggests the possibility of mapping one problem to another.
294
295In the next section we show how the arrangement ${\mathcal A}_k$ can
296be maintained consistently and efficiently using the occlusion tree.
297
298
299
300\section{Pl\"ucker coordinates of lines in 3D}
301
302\label{sec:plucker}
303
304
305 We will use a mapping that describes an oriented 3D line as a point
306in a projective 5D space~\cite{Boissonnat98} by means of \plucker
307coordinates~\cite{Teller92phd,p-rsls-97,yn-sbgtc-97,Pu98-DSGIV}. \plucker
308coordinates allow to represent sets of lines using 5D polyhedra and to
309compute visibility by means of polyhedra set operations in 5D.
310
311 A line in 3D can be described by homogeneous coordinates of two
312distinct points on that line. Let $l$ be a line in ${\cal R}^3$ and
313let $\mbi{u}=(u_x, u_y, u_z, u_w)$ and $\mbi{v}=(v_x,v_y,v_z, v_w)$ be
314two distinct points in homogeneous coordinates lying on $l$. A line
315$l$ oriented from $\mbi{u}$ to $\mbi{v}$ can be described by the following matrix:
316
317\begin{equation}
318l=\left(
319\begin{array}{cccc}
320u_{x} & u_{y} & u_{z} & u_{w} \\
321v_{x} & v_{y} & v_{z} & v_{w}
322\end{array}
323\right)
324\label{coord_cara}
325\end{equation}
326
327Minors of the matrix correspond to components of the {\em \plucker
328coordinates} $\bpi_l$ of line $l$:
329
330\begin{equation}
331\begin{array}{ll}
332\bpi_l & =  (\pi_{l0}, \pi_{l1}, \pi_{l2}, \pi_{l3}, \pi_{l4}, \pi_{l5}) = \\
333       & =  (\xi_{wx},\xi_{wy},\xi_{wz},\xi_{yz},\xi_{zx},\xi_{xy}),
334\end{array}
335\label{eq:plucker_coords_def}
336\end{equation}
337
338where
339
340\begin{equation}
341\xi_{rs} = det\left(
342\begin{array}{cc}
343u_{r} & u_{s} \\
344v_{r} & v_{s}
345\end{array}
346\right).
347\end{equation}
348
349Substituting $u_w=1$ and $v_w=1$ into Eq.~\ref{eq:plucker_coords_def}
350enumerates to:
351
352\begin{equation}
353\begin{array}{l}
354\pi_{l0} = v_x - u_x\\
355\pi_{l1} = v_y - u_y\\
356\pi_{l2} = v_z - u_z\\
357\pi_{l3} = u_{y}v_{z} - u_{z}v_{y}\\
358\pi_{l4} = u_{z}v_{x} - u_{x}v_{z}\\
359\pi_{l5} = u_{x}v_{y} - u_{y}v_{x}
360\end{array}
361\label{eq:plucker_coords}
362\end{equation}
363
364The \plucker coordinates $\bpi_l$ can be seen as homogeneous
365coordinates of a point in a projective five-dimensional space ${\cal
366P}^5$. We call this point a {\em \plucker point} $\ppoint_l$ of
367$l$. For a given oriented line $l$ the \plucker coordinates $\bpi_l$
368are unique and they do not depend on the choice of points $p$ and $q$.
369We will use the notation of a \plucker point $\ppoint_l$ in the case
370when we want to stress that the corresponding \plucker coordinates
371$\bpi_l$ are interpreted as a point in ${\cal P}^5$.
372
373Using the projective duality the \plucker coordinates can be
374interpreted as coefficients of a hyperplane. The {\em \plucker
375coefficients} $\bomega_l$ of line $l$ are given as:
376
377
378\begin{equation}
379\begin{array}{ll}
380\bomega_l
381 & =  (\omega_{l0}, \omega_{l1}, \omega_{l2}, \omega_{l3}, \omega_{l4}, \omega_{l5}) = \\
382 & =  (\xi_{yz},\xi_{zx},\xi_{xy},\xi_{wx},\xi_{wy},\xi_{wz})
383\end{array}
384\label{eq:plucker_coef_def}
385\end{equation}
386
387Substituting Eq.~\ref{eq:plucker_coords} into Eq.~\ref{eq:plucker_coef_def}
388we get:
389
390\begin{equation}
391\begin{array}{l}
392\omega_{l0} = \pi_{l3} \\
393\omega_{l1} = \pi_{l4}\\
394\omega_{l2} = \pi_{l5}\\
395\omega_{l3} = \pi_{l0}\\
396\omega_{l4} = \pi_{l1}\\
397\omega_{l5} = \pi_{l2}
398\end{array}
399\label{eq:plucker_coef}
400\end{equation}
401
402
403 The \plucker coefficients $\bomega_l$ define a {\em \plucker
404 hyperplane} $\pplane_l$. We will use the notation of a \plucker
405 hyperplane $\pplane_l$ when we want to stress that the
406 corresponding \plucker coefficients $\bomega_l$ are interpreted as a
407 hyperplane in ${\cal P}^5$. In terms of \plucker points the \plucker
408 hyperplane can be expressed as:
409 
410\begin{equation}
411\label{hyperplane}
412\begin{array}{l}
413\pplane_l = \{\ppoint | \ppoint \in {\cal P}^5, \bomega_l \odot \bpi = 0\}
414\end{array}
415\end{equation}
416
417The \plucker hyperplane induces closed positive and negative halfspaces
418given as:
419
420\begin{equation}
421\begin{array}{l}
422\pplane^{+}_l = \{\ppoint | \ppoint \in {\cal P}^{5}, \bomega_l \odot \bpi \geq 0\} \\
423\pplane^{-}_l = \{\ppoint | \ppoint \in {\cal P}^{5}, \bomega_l \odot \bpi \leq 0\} \\
424\end{array}
425\label{eq:def_halfspaces}
426\end{equation}
427
428 These definitions of \plucker coordinates and coefficients follow the
429``traditional'' convention~\cite{Pu98-DSGIV}. They differ from the
430definitions used by Teller~\cite{Teller92phd} who used a permuted
431order of the coordinates. The traditional convention provides an
432elegant interpretation of \plucker coordinates that will be discussed
433in Section~\ref{sec:plucker_interp}.
434
435 If $a$ and $b$ are two directed lines, the relation $side(a,b)$ is
436defined as an inner product $\bomega_a \odot \bpi_b$ or permuted inner
437product $\bpi_a \times \bpi_b$:
438
439\begin{equation}
440\begin{array}{ll}
441  side(a,b) & = \bomega_a \odot \bpi_b = \\
442            & = \omega_{a0}\pi_{b0} + \omega_{a1}\pi_{b1} + \omega_{a2}\pi_{b2} +
443  \omega_{a3}\pi_{b3} + \omega_{a4}\pi_{b4} + \omega_{a5}\pi_{b5} = \\
444            & = \bpi_a \times \bpi_b = \\
445            & = \pi_{a0}\pi_{b3} + \pi_{a1}\pi_{b4} + \pi_{a2}\pi_{b5} +
446  \pi_{a3}\pi_{b0} + \pi_{a4}\pi_{b1} + \pi_{a5}\pi_{b2}
447\end{array}
448\label{eq:side}
449\end{equation}
450
451
452 This relation can be interpreted with the right-hand rule
453(Figure~\ref{sidepict}). If the thumb of the right hand is directed
454along line $a$, then:
455
456\begin{itemize}
457\item $side(a,b)> 0$,  if line $b$ is oriented in the direction of the fingers,
458
459\item $side(a,b) = 0$,  if lines $a$ and $b$ intersect or are parallel,
460
461\item $side(a,b) < 0$, if line $b$ points against the direction of the fingers.
462\end{itemize}
463
464\begin{figure}[htb]
465\centerline{
466  \includegraphics[width=0.8\textwidth,draft=\DRAFTFIGS]{figs/pldual}}
467\caption{The $side(a,b)$, interpreted as the right-hand rule.}
468\label{sidepict}
469\end{figure}
470
471
472\plucker coordinates have an important property: Although every
473oriented line in ${\cal R}^3$ maps to a point in \plucker coordinates,
474not every tuple of six real numbers corresponds to a real line. Only
475the points $\ppoint \in {\cal P}^5$ \plucker coordinates of which
476satisfy the condition
477
478\begin{equation}
479\bpi \odot \bpi = 0 \qquad \equiv \qquad \pi_{0}\pi_{3} + \pi_{1}\pi_{4} + \pi_{2}\pi_{5} = 0,
480\label{eq:plucker_quadric}
481\end{equation}
482
483represent real lines in ${\cal R}^3$. All other points correspond to
484lines which are said to be {\em imaginary}. The set of points in
485${\cal P}^5$ satisfying Eq.~\ref{eq:plucker_quadric} forms a 4D
486hyperboloid of one sheet called the {\em \plucker quadric}, also known
487as the {\em Klein quadric} or the {\em Grassman manifold}
488(see Figure~\ref{quadric}).
489
490
491\begin{figure}[htb]
492\medskip
493\centerline{
494  \includegraphics[width=0.65\textwidth,draft=\DRAFTFIGS]{figs/reallin}}
495\caption{Real lines map on points on the Pl\"{u}cker quadric.}
496\label{quadric}
497\end{figure}
498
499The six \plucker coordinates of a real line are not
500independent. Firstly, they describe an oriented projective space,
501secondly, they must satisfy the
502equation~\ref{eq:plucker_quadric}. Thus there are four degrees of
503freedom in the description of a 3D line, which conforms with the
[277]504classification from Chapter~\ref{chap:introduction}.
[249]505
506 \plucker coordinates allow to detect an incidence of two lines by
507computing an inner product of a homogeneous point (mapping of one
508line) with a hyperplane (mapping of the other). Lines $l$ and $l'$
509intersect or are parallel (i.e. meet at infinity) if and only if
510$\ppoint_l \in \pplane_{l'}$, i.e. $side(l, l') = 0$. Note that according
511to ~\ref{eq:plucker_quadric} any line always meets itself.
512
513
514\subsection{Geometric interpretation of \plucker coordinates}
515\label{sec:plucker_interp}
516
517For a better understanding of \plucker coordinates it is natural to
518ask how each individual \plucker coordinate is related to the geometry
519of the corresponding line. The \plucker coordinates of a given line
520can be divided to the {\em directional} and the {\em locational}
521parts. The directional part encodes the direction of the line, the
522locational part encodes the position of the line. Given \plucker
523coordinates $\bpi_l$ of a line $l$ we can write:
524
525\begin{equation}
526\begin{array}{lll}
527\mbi{d}_l & = (\pi_{l0}, \pi_{l1}, \pi_{l2}), \\
528\mbi{l}_l & = (\pi_{l3}, \pi_{l4}, \pi_{l5}), \\
529\end{array}
530\end{equation}
531
532where $\mbi{d}_l$ is the {\em directional vector} of $l$ and $\mbi{l}_l$
533is the {\em locational vector} of $l$. The \plucker coordinates
534$\bpi_l$ and the \plucker coefficients $\bomega_l$ can be expressed as:
535
536
537\begin{equation}
538\begin{array}{ll}
539\bpi_l &= [\mbi{d}_l; \mbi{l}_l],\\
540\bomega_l &= [\mbi{l}_l; \mbi{d}_l].
541\end{array}
542\label{eq:rot3_locdir}
543\end{equation}
544
545
546\subsubsection{Extracting a point}
547
548Often we need to describe a line using a parametric representation by
549means of an {\em anchor point} and a directional vector. Given a line
550$l$ the directional vector $\mbi{d}_l$ is embedded in the \plucker
551coordinates of $l$ (see Eq.~\ref{eq:rot3_locdir}). The anchor point
552$\mbi{a}_l$ can be computed as:
553
554\begin{equation}
555\mbi{a}_l = (a_x, a_y, a_z) = \frac{\mbi{d}_l \times \mbi{l}_l}{\parallel \mbi{d}_l \parallel ^2}.
556\end{equation}
557 
558
559\subsubsection{Computing the distance}
560
561The distance between two lines $l$ and $l'$ can be expressed
562using their anchor points and the directional vectors:
563
564\begin{equation}
565  dist(l, l') = { | (\mbi{a}_l - \mbi{a}_{l'}) \cdot (\mbi{d}_l \times
566\mbi{d}_{l'}) | \over \parallel \mbi{d}_l \times \mbi{d}_{l'} \parallel }.
567\end{equation}
568
569
570The distance is the length of the projection of the line segment
571$\mbi{a}_l,\mbi{a}_{l'}$ onto the direction $\mbi{d}_l \times
572\mbi{d}_{l'}$.
573
574
575
576%%%%%%%%%%%%%%%%%%%%%%
577
578\section{Visual events}
579
580\label{sec:events}
581
582This section discusses visual events occurring in polygonal
583scenes~\cite{Gigus90}. We will focus on the boundaries of visual
584events and their relation to \plucker coordinates. The understanding
585of the  visual events helps to comprehend the complexity of the
586from-region visibility in 3D.
587
588 Any scene can be decomposed into regions from which the scene has a
589topologically equivalent view~\cite{Gigus90}. Boundaries of such
590regions correspond to {\em event surfaces}. Crossing an event surface
591causes a {\em visual event}, i.e. a change in the topology of the view
592(visibility map). In polygonal scenes there are three types of event
593surfaces~\cite{Gigus90}:
594
595\begin{itemize}
596  \item {\em vertex-edge} (VE) events involving an edge and a vertex
597  of two distinct polygons.
598  \item {\em edge-edge-edge} (EEE) events involving three edges of
599  three distinct polygons.
600  \item {\em supporting} events corresponding to supporting planes of
601  scene polygons. The supporting event can be seen as a degenerated
602  case of VE or EEE events.
603\end{itemize}
604
605The VE events correspond to planes, the EEE events in general form
606quadratic surfaces. The definitions assume that the scene polygons are
607in general non-degenerate position. In real world scenes the polygons
608or their edges polygons can be variously aligned. In such a case these
609definitions of visibility events form minimal sets of edges and
610vertices defining an event. For example a VE event can involve a
611vertex and several edges of scene polygons (see
612Figure~\ref{fig:degen_event}).
613
614\begin{figure}[htb]
615\centerline{
616  \includegraphics[width=0.45\textwidth,draft=\DRAFTFIGS]{figs/ve_degen}}
617\caption{Degenerated VE event. The VE event is induced by a vertex and
618three edges of scene polygons.}
619\label{fig:degen_event}
620\end{figure}
621
622
623 The intersections of event surfaces correspond to {\em extremal
624lines}~\cite{Teller92phd}. An extremal line intersects four edges of
625some scene polygons. There are four types of extremal lines:
626vertex-vertex (VV) lines, vertex-edge-edge (VEE) lines,
627edge-vertex-edge (EVE) and quadruple edge (4E) lines. Imagine
628``sliding'' an extremal line (of any type) away from its initial
629position by relaxing exactly one of the four edge constraints
630determining the line. The section of the event surface swept out by
631the sliding line is called the {\em swath}.  A swath is either planar
632if it corresponds to a VE event surface or a regulus if it is embedded
633in an EEE event surface.
634
635Figure~\ref{swaths}-(a) shows an extremal VV line tight on four edges
636A,B,C, and D. Relaxing constraint C yields a VE (planar) swath defined
637by A,B, and D. When the sliding line encounters an obstacle (edge E) it
638terminates at a VV extremal line defined by A,B,D, and
639E. Figure~\ref{swaths}-(b) depicts an extremal 4E line tight on the
640mutually skew edges A,B,C, and D. Relaxing constraint A produces an EEE
641event surface that is a regulus intersecting B,C, and D. When the
642sliding line encounters edge E the swath terminates at an VEE extremal
643line.
644
645\begin{figure}[htb]
646\centerline{
647  \includegraphics[width=0.75\textwidth,draft=\DRAFTFIGS]{figs/swaths}}
648\centerline{\small
649{\bf (a)}\hspace{0.3\textwidth} {\bf (b)}
650\hspace{0.2\textwidth}}
651\caption{Swaths of event surfaces. (a) VE swath. (b) EEE swath. }
652\label{swaths}
653\end{figure}
654
655
656\subsection{Visual events and \plucker coordinates}
657
658\plucker coordinates allow an elegant description of event surfaces.
659An event surface can be expressed as an intersection of three \plucker
660hyperplanes, and thus avoiding explicit treatment of quadratic
661surfaces. The non-linear EEE surfaces correspond to curves embedded in
662the intersection of the \plucker hyperplanes.
663
664Let ${\cal H}$ be an arrangement~\cite{dcg-handbook} of hyperplanes in
665${\cal P}^5$ that correspond to \plucker coefficients of edges of the
666scene polygons. The intersection of the arrangement ${\cal H}$ and the
667\plucker quadric yields all visual
668events~\cite{Teller92phd,p-rsls-97,Pu98-DSGIV}.
669
670An extremal line $l$ intersects four generator edges. Consequently,
671the corresponding \plucker point $\ppoint_l$ lies on four \plucker
672hyperplanes.  In 5D the four hyperplanes define an edge of the
673arrangement ${\cal H}$. Thus, we can find all extremal lines of a
674given set of polygons by examining the edges of ${\cal H}$ for
675intersections with the \plucker quadric~\cite{Pu98-DSGIV}.
676
677
678Consider the situation depicted in Figure~\ref{swaths}. In line space
679the event surfaces correspond to curves embedded in the \plucker
680quadric. In general these curves are conics defined by an intersection
681of the 2D-faces of ${\cal H}$ with the \plucker quadric (see
682Figure~\ref{5Dswaths}).
683
684\begin{figure}[htb]
685\centerline{
686  \includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/ipswaths}}
687\caption{3D swaths correspond to conics on the Pl\"ucker quadric.}
688\label{5Dswaths}
689\end{figure}
690
691
692
693\section{Lines intersecting a polygon}
694
695\label{sec:rot3d_singlepoly}
696
697 \plucker coordinates provide a tool to map lines from primal space to
698points in line space. This mapping allows to perform operations of
699sets of lines using set theoretical operations on the corresponding
700sets of points. In polygonal scenes the {\em elementary set of lines}
701is formed by lines intersecting a given polygon.
702
703
704 Assume that a convex polygon $P$ is defined by edges $e_i, 0\leq i <
705n$ that are oriented counterclockwise. The set of lines ${\cal L}_P$
706intersecting the polygon that are oriented in the direction of the
707polygon's normal satisfies:
708
709
710\begin{equation}
711{\cal L}_P = \{ l |  l \in (R^3, R^3), side(\bpi_l, \bpi_{e_i}) \leq 0, \forall i \in \langle 0,n) \},
712\label{eq:halfspaces}
713\end{equation}
714
715where $\bpi_l$ are \plucker coordinates of line $l$ and $\bpi_{e_i}$ are
716\plucker coordinates of $i$-th edge of the polygon. Substituting the
717Eq.~\ref{eq:side} and rewriting the equation in terms of a set of
718\plucker points we get:
719
720\begin{equation}
721\begin{array}{ll}
722{\cal F}_P & = \{ \ppoint | \ppoint \in {\cal P}^5, \bpi \times \bpi_{e_i} \leq 0, \forall i \in \langle 0,n) \} = \\
723           & = \{ \ppoint | \ppoint \in {\cal P}^5, \bpi \odot \bomega_{e_i} \leq 0, \forall i \in \langle 0,n) \},
724\end{array}
725\label{eq:feasible}
726\end{equation}
727
728where ${\cal F}_P$ is a set of {\em feasible \plucker points} for
729polygon $P$. Substituting Eq.~\ref{eq:def_halfspaces}
730into~\ref{eq:feasible} we obtain:
731
732\begin{equation}
733\begin{array}{ll}
734{\cal F}_P & = \{ \ppoint | \ppoint \in {\cal P}^5,  \bpi \in \pplane^-_{e_i}, \forall i \in \langle 0,n) \}
735\end{array}
736\label{eq:intersection}
737\end{equation}
738
739Thus the set of feasible \plucker points is defined by an intersection
740of halfspaces defined by the \plucker hyperplanes corresponding to edges of the
741polygon. The set of {\em stabbers} ${\cal S}_P$ is then defined as an
742intersection of ${\cal F}_P$ with the \plucker quadric:
743
744\begin{equation}
745{\cal S}_P = \{ \ppoint | \ppoint \in {\cal F}_P, \bpi \odot \bpi  = 0 \}.
746\end{equation}
747
748The stabbers are \plucker points corresponding to the real lines
749intersecting the polygon that are oriented in the direction of the
750normal. Similarly we can define the sets of {\em reverse feasible
751\plucker points} ${\cal F}^-_P$ and {\em reverse stabbers} ${\cal
752S}^-_P$ that correspond to opposite oriented lines intersecting the
753polygon:
754
755\begin{equation}
756\begin{array}{ll}
757{\cal F}^-_P  & = \{ \ppoint | \ppoint \in {\cal P}^5, \ppoint \in \pplane^+_{e_i}, \forall i \in \langle 0,n) \} \\
758{\cal S}^-_P  & = \{ \ppoint | \ppoint \in {\cal F}^-_P, \bpi \odot \bpi  = 0 \}.
759\end{array}
760\end{equation}
761
762
763
764
765\section{Lines between two polygons}
766\label{sec:rot3d_twopoly}
767
768 The above presented definitions of elementary line sets  allow to
769handle visibility computations by means of set operations on the sets
770of feasible \plucker points.  Visibility between two polygons $P_j$
771and $P_k$ can be determined by constructing an intersection of
772feasible sets of the two polygons ${\cal F}_{P_j}$ and ${\cal
773F}_{P_k}$ and subtracting all feasible sets of polygons lying between
774$P_j$ and $P_k$. To obtain the set of unoccluded stabbers we intersect
775the resulting feasible set with the \plucker quadric.
776
777Further in this chapter we restrict our discussion to visibility from
778a given {\em source polygon} $P_S$. Given any {\em occluder polygon}
779$P_j$ we first describe lines intersecting both $P_S$ and $P_j$. Lines
780between $P_S$ and  $P_j$ can be described by an intersection of their
781feasible line sets:
782
783\begin{equation}
784{\cal F}_{P_SP_j} = {\cal F}_{P_S} \cap {\cal F}_{P_j}
785\end{equation}
786
787and thus
788
789\begin{equation}
790{\cal S}_{P_SP_j} = {\cal S}_{P_S} \cap {\cal S}_{P_j}.
791\end{equation}
792
793 The feasible \plucker points are defined by an intersection of
794halfspaces corresponding to edges of $P_S$ and $P_j$. These halfspaces
795define a {\em blocker polyhedron} $B_{P_SP_j}$ that is described in
796the next section.
797
798
799\subsubsection{Blocker polyhedron}
800
801 The blocker polyhedron describes lines intersecting the source
802 polygon and the given occluder.  The blocker polyhedron can be seen
[277]803 as an extension of the blocker polygon discussed above for the from-region
[249]804 visibility in 3D scenes. The blocker polyhedron is a 5D polyhedron in
805 a 5D projective space.  To avoid singularities in the projection from
806 ${\cal P}^5$ to ${\cal R}^5$ the polyhedron can be embedded in ${\cal
807 R}^6$ similarly to the embedding of blocker polygon in ${\cal R}^3$
808 (see Section~\ref{sec:blocker_polygon}). Then the polyhedron actually
809 represents a 6D pyramid with an apex at the origin of ${\cal R}^6$.
810
811
812\subsubsection{Cap planes}
813
814The blocker polyhedron is defined by an intersection of halfspaces
815defined by \plucker planes that are mappings of edges of the source
816polygon and the occluder. As stated above the blocker polyhedron
817represents the set of feasible \plucker points ${\cal F}_{P_SP_j}$
818including points not intersecting the \plucker quadric that correspond
819to imaginary lines. We bound the polyhedron by {\em cap planes}
820aligned with the \plucker quadric so that the resulting polyhedron is
821a tighter representation of the stabbers ${\cal S}_{P_SP_j}$. We need
822to ensure that the resulting polyhedron fully contains the stabbers
823${\cal S}_{P_SP_j}$, i.e. contains the cross-section of the \plucker
824quadric and ${\cal F}_{P_SP_j}$.
825
826The cap planes provide the following benefits:
827
828\begin{itemize}
829\item The computation is localized to the proximity of the \plucker
830quadric. This reduces the combinatorial complexity of data structure
831representing an arrangement of the blocker polyhedra.
832
833\item The blocker polyhedron is always bounded. Although the set of
834  lines between two convex polygons is bounded, the set of feasible
835  \plucker points can be unbounded at the ``direction'' of imaginary
836  lines. Adding the cap planes we make sure that the polyhedron is
837  bounded, which allows its easier treatment. By using the cap planes
838  we avoid the handling of very oblong, almost unbounded polyhedra,
839  which improves numerical stability of a floating point
840  implementation of the algorithm.
841\end{itemize}
842
843
844 We used two cap planes to bound the polyhedron, one for each side of
845the \plucker quadric (a side is given by the sign of $\bpi \odot
846\bpi$). The cap planes are computed as tangents to the \plucker
847quadric at the center of the set of stabbers ${\cal S}_{P_SP_j}$. The
848planes are translated each at the opposite direction making sure that
849they include the whole set ${\cal S}_{P_SP_j}$.
850
851
852
853\subsection{Intersection with the \plucker quadric}
854\label{sec:stabbers}
855
856Given a blocker polyhedron representing the set of feasible lines
857${\cal F}_{P_SP_j}$ we can compute an intersection of the edges of the
858polyhedron with the \plucker quadric to determine the set of extremal
859lines bounding the set of stabbers ${\cal S}_{P_SP_j}$. An
860intersection of an edge of the blocker polyhedron with the \plucker
861quadric results in at most two {\em extremal \plucker points} that
862correspond extremal lines\footnote{Neglecting the case that the whole
863edge is embedded in the \plucker quadric, which results in infinite
864number of extremal lines.}. Given an edge of the blocker polyhedron
865the intersection with the \plucker quadric is computed by solving the
866quadratic equation (Eq.~\ref{eq:plucker_quadric}). A robust algorithm
867for computing this intersection was developed by
868Teller~\cite{TH83}.
869
870
871Intersecting all edges of the blocker polyhedron with the \plucker
872quadric yields all extremal lines of ${\cal
873S}_{P_SP_j}$~\cite{Teller:1992:CAA,Pu98-DSGIV}. See
874Figure~\ref{fig:rot3_visrays} for an example of extremal lines
875computed for the given source polygon and a set of three occluders.
876
877
878\begin{figure}[htb]
879\centerline{
880  \includegraphics[width=0.5\textwidth,draft=\DRAFTIMAGES]{images/rot3_visrays}}
881\caption{Extremal lines for the given source polygon (yellow) and three occluders.}
882\label{fig:rot3_visrays}
883\end{figure}
884
885 The intersection of the 2D faces of the blocker polyhedron with the
886\plucker quadric yields swaths of event surfaces of the set of
887stabbers ${\cal S}_{P_SP_j}$~\cite{Teller92phd}. In general the
888intersection results in 1D conics.
889
890 We can avoid the explicit treatment of conics in 5D by computing the
891local topology of the edges of the blocker polyhedron and constructing
892the swaths in primal space between the topologically connected
893extremal lines~\cite{Teller92phd}. The local topology of an extremal
894\plucker point is given by connections with extremal \plucker points
895embedded in the same 2D face of the blocker polyhedron.  A 2D face of
896the blocker polyhedron is given by three \plucker hyperplanes. Thus
897the pairs of extremal \plucker points defined by the subset of the
898same three \plucker hyperplanes define a swath.
899
900
901
[277]902% For solution of some from-region visibility problems (e.g. PVS
903% computation, region-to-region visibility) the event swaths need not be
904% reconstructed. For example the visibility culling algorithm that will
905% be discussed in Section~\ref{sec:rot3pvs} only computes extremal
906% \plucker points and uses them to test an existence of a set of
907% stabbers of a given size.
[249]908
909
910\subsection{Size of the set of lines}
911
912\label{sec:size_measure}
913
914Computing a size measure of a given set of lines is useful for most
915visibility algorithms. The computed size measure can be used to drive
916the subdivision of the given set of lines or to bound the maximal
917error of the algorithm. An analytic algorithm can use the computed
918size measure for thresholding by a given $\epsilon$-size to discard
919very small line sets.  A discrete algorithm can use the size measure
920to determine the required density of sampling.
921
922The size of a set of lines for the from-point visibility can be
923formulated easily: the size is given by the area of the intersection
924of the line set with a plane. This corresponds to quantifying
925visibility of an object according to its projected area. Such a size
926is determined in the solution space (viewport). Alternatively we could
927use a ``viewport independent measure'' given by a solid angle formed by
928the visible part of an object. The size measure for the from-region
929visibility problems is more complicated for the following reasons:
930
931\begin{itemize}
932\item The domain of the solution space is four-dimensional.
933\item The solution space of the from-region visibility algorithm
934  generally does not correspond to the solution space of the
935  application. For example, a visible surface algorithm using a
936  precomputed PVS works in a 2D domain induced by the given viewport.
937\end{itemize}
938
939
940\subsubsection{General size measure}
941
942A size of a set of lines for the from-region visibility can be
943computed by evaluating a 4D integral. Using \plucker coordinates we
944can compute a volume of the 4D hyper-surface corresponding to the
945given set of lines. The volume however depends on a way of projecting
946the blocker polyhedron from ${\cal P}^5$ to ${\cal R}^5$. This
947projection has a similar role as the selection of the viewport for the
948from-point visibility problem. We can project the blocker polyhedron
949from ${\cal P}^5$ to ${\cal R}^5$ by projecting it to a 5D hyperplane
950defined by certain reference direction, e.g. the ``center-line'' of
951the given set of lines. Pu proposed a different size measure based on
952measuring the {\em angular spread} and the {\em distance} between
953lines~\cite{Pu98-DSGIV}. Both these quantities can be evaluated in
954terms of \plucker coordinates of the set of extremal lines of the
955given line set.
956
957
958\subsubsection{Size measure for the PVS computation}
959
960 It can be difficult to relate the size measures described above to
961the domain of the result of a subsequently applied visibility
962algorithm. We need a simple scheme that fits to the context of the
963target application.  In this section we suggest a size measure
964designed for the PVS computation. When computing a PVS we are
965interested in measuring the size of the set of unoccluded lines
966(stabbers) between the source polygon $P_S$ and a given scene
967polygon. If this size is below an $\epsilon$-threshold, we can
968possibly exclude the polygon from the PVS.  We suggest to use an
969estimate of the minimal angle between the stabbers at a point inside
970$P_S$. The idea is to estimate the minimal projected diameter of a
971polygon visible through the given set of lines from any point inside
972$P_S$. This estimate can be used to bound a maximal error of an image
973synthesized with respect to any viewpoint inside $P_S$ for the case that
974the corresponding set of lines is neglected.
975
976%%  The size measure approximates the minimal spatial angle given by a
977%% cross-section of the given set of lines parallel to the source polygon
978%% $P_S$ and the center of $P_S$.
979
980Given a blocker polyhedron ${\cal F}_{P_SP_j}$  the proposed size
981measure can be evaluated as follows:
982
983\begin{enumerate}
984
985\item
986 Compute the extremal lines of the corresponding set of stabbers ${\cal
987S}_{P_SP_j}$ as described in Section~\ref{sec:stabbers}.
988
989\item For each polygon edge $e_i$ bounding the stabbers
990  determine an extremal line $l_{mi}$ with a maximal distance from the
991  edge.
992 
993\item For each edge $e_i$ compute a shortest line segment $z_i$
994  connecting $e_i$ and $l_{mi}$.  The length of this line segment is
995  then scaled according to its distance from the source polygon,
996  i.e. we compute an angle $\alpha_i$ between the lines connecting the
997  center of the source polygon and the endpoints of $z_i$.
998 
999\item Select a minimal angle $\alpha_m$ of all $\alpha_i$ as the
1000estimate of the size of the given line set.
1001
1002\end{enumerate}
1003
1004The evaluation of the size measure is depicted in
1005Figure~\ref{fig:linesize}.
1006
1007\begin{figure}[htb]
1008\centerline{
1009  \includegraphics[width=0.4\textwidth,draft=\DRAFTFIGS]{figs/linesize}}
1010\caption{A 2D example of evaluation of the size of a set of lines. The three
1011  line segments
1012  $z_1$, $z_2$ and $z_3$ maximize the distance of the corresponding
1013  occluder edges from the extremal lines. The line segment $z_3$ spans
1014  a minimal angle $\alpha_m$ with respect to the center of the source
1015  polygon $P_S$.}
1016\label{fig:linesize}
1017\end{figure}
1018
1019 The angle $\alpha_m$ can be related to the angular resolution of the
1020synthesized image. Given the resolution of the image we can threshold
1021``small'' line sets with $\alpha_m$ below the corresponding angular
1022threshold to achieve a sub-pixel precision of the rendering algorithm.
1023This measure can also be applied to deal with the finite precision of
1024the floating point arithmetics by using a small $\epsilon$-threshold
1025to handle numerical inaccuracies.
1026
[266]1027
1028\section{Summary}
1029
1030 In this chapter we discussed the relation of sets of lines in 3D and
1031the polyhedra in \plucker coordinates. We proposed a general size
1032measure for a set of lines described by a blocker polyhedron and a
1033size measure designed for the computation of PVS.
1034
Note: See TracBrowser for help on using the repository browser.