1 | \chapter{Analysis of Visibility in Polygonal Scenes}
|
---|
2 |
|
---|
3 |
|
---|
4 | \section{Related work}
|
---|
5 | \label{VFR3D_RELATED_WORK}
|
---|
6 |
|
---|
7 |
|
---|
8 | Below we briefly discuss the related work on visibility preprocessing
|
---|
9 | in several application areas.
|
---|
10 |
|
---|
11 |
|
---|
12 | \subsection{Aspect graph}
|
---|
13 |
|
---|
14 | The first algorithms dealing with from-region visibility belong to the
|
---|
15 | area of computer vision. The {\em aspect
|
---|
16 | graph}~\cite{Gigus90,Plantinga:1990:RTH, Sojka:1995:AGT} partitions
|
---|
17 | the view space into cells that group viewpoints from which the
|
---|
18 | projection of the scene is qualitatively equivalent. The aspect graph
|
---|
19 | is a graph describing the view of the scene (aspect) for each cell of
|
---|
20 | the partitioning. The major drawback of this approach is that for
|
---|
21 | polygonal scenes with $n$ polygons there can be $\Theta(n^9)$ cells in
|
---|
22 | the partitioning for unrestricted viewspace. A {\em scale space}
|
---|
23 | aspect graph~\cite{bb12595,bb12590} improves robustness of the method
|
---|
24 | by merging similar features according to the given scale.
|
---|
25 |
|
---|
26 |
|
---|
27 | \subsection{Potentially visible sets}
|
---|
28 |
|
---|
29 |
|
---|
30 | In the computer graphics community Airey~\cite{Airey90} introduced
|
---|
31 | the concept of {\em potentially visible sets} (PVS). Airey assumes
|
---|
32 | the existence of a natural subdivision of the environment into
|
---|
33 | cells. For models of building interiors these cells roughly correspond
|
---|
34 | to rooms and corridors. For each cell the PVS is formed by cells
|
---|
35 | visible from any point of that cell. Airey uses ray shooting to
|
---|
36 | approximate visibility between cells of the subdivision and so the
|
---|
37 | computed PVS is not conservative.
|
---|
38 |
|
---|
39 | This concept was further elaborated by Teller et
|
---|
40 | al.~\cite{Teller92phd,Teller:1991:VPI} to establish a conservative
|
---|
41 | PVS. The PVS is constructed by testing the existence of a stabbing
|
---|
42 | line through a sequence of polygonal portals between cells. Teller
|
---|
43 | proposed an exact solution to this problem using \plucker
|
---|
44 | coordinates~\cite{Teller:1992:CAA} and a simpler and more robust
|
---|
45 | conservative solution~\cite{Teller92phd}. The portal based methods
|
---|
46 | are well suited to static densely occluded environments with a
|
---|
47 | particular structure. For less structured models they can face a
|
---|
48 | combinatorial explosion of complexity~\cite{Teller92phd}. Yagel and
|
---|
49 | Ray~\cite{Yagel95a} present an algorithm, that uses a regular spatial
|
---|
50 | subdivision. Their approach is not sensitive to the structure of the
|
---|
51 | model in terms of complexity, but its efficiency is altered by the
|
---|
52 | discrete representation of the scene.
|
---|
53 |
|
---|
54 | Plantinga proposed a PVS algorithm based on a conservative viewspace
|
---|
55 | partitioning by evaluating visual
|
---|
56 | events~\cite{Plantinga:1993:CVP}. The construction of viewspace
|
---|
57 | partitioning was further studied by Chrysanthou et
|
---|
58 | al.~\cite{Chrysanthou:1998:VP}, Cohen-Or et al.~\cite{cohen-egc-98}
|
---|
59 | and Sadagic~\cite{Sadagic}. Sudarsky and
|
---|
60 | Gotsman~\cite{Sudarsky:1996:OVA} proposed an output-sensitive
|
---|
61 | visibility algorithm for dynamic scenes. Cohen-Or et
|
---|
62 | al.~\cite{COZ-gi98} developed a conservative algorithm determining
|
---|
63 | visibility of an $\epsilon$-neighborhood of a given viewpoint that was
|
---|
64 | used for network based walkthroughs.
|
---|
65 |
|
---|
66 | Conservative algorithms for computing PVS developed by Durand et
|
---|
67 | al.~\cite{EVL-2000-60} and Schaufler et al.~\cite{EVL-2000-59} make
|
---|
68 | use of several simplifying assumptions to avoid the usage of 4D data
|
---|
69 | structures. Wang et al.~\cite{Wang98} proposed an algorithm that
|
---|
70 | precomputes visibility within beams originating from the restricted
|
---|
71 | viewpoint region. The approach is very similar to the 5D subdivision
|
---|
72 | for ray tracing~\cite{Simiakakis:1994:FAS} and so it exhibits similar
|
---|
73 | problems, namely inadequate memory and preprocessing complexities.
|
---|
74 | Specialized algorithms for computing PVS in \m25d scenes were proposed
|
---|
75 | by Wonka et al.~\cite{wonka00}, Koltun et al.~\cite{koltun01}, and
|
---|
76 | Bittner et al.~\cite{bittner:2001:PG}.
|
---|
77 |
|
---|
78 | The method presented in the thesis was first outlined
|
---|
79 | in~\cite{bittner99min}. Recently, a similar exact algorithm for PVS
|
---|
80 | computation was developed by Nirenstein et
|
---|
81 | al.~\cite{nirenstein:02:egwr}. This algorithm uses \plucker
|
---|
82 | coordinates to compute visibility in shafts defined by each polygon in
|
---|
83 | the scene.
|
---|
84 |
|
---|
85 |
|
---|
86 | \subsection{Rendering of shadows}
|
---|
87 |
|
---|
88 |
|
---|
89 | The from-region visibility problems include the computation of soft
|
---|
90 | shadows due to an areal light source. Continuous algorithms for
|
---|
91 | real-time soft shadow generation were studied by Chin and
|
---|
92 | Feiner~\cite{Chin:1992:FOP}, Loscos and
|
---|
93 | Drettakis~\cite{Loscos:1997:IHS}, and
|
---|
94 | Chrysanthou~\cite{Chrysantho1996a} and Chrysanthou and
|
---|
95 | Slater~\cite{Chrysanthou:1997:IUS}. Discrete solutions have been
|
---|
96 | proposed by Nishita~\cite{Nishita85}, Brotman and
|
---|
97 | Badler~\cite{Brotman:1984:GSS}, and Soler and Sillion~\cite{SS98}. An
|
---|
98 | exact algorithm computing an antipenumbra of an areal light source was
|
---|
99 | developed by Teller~\cite{Teller:1992:CAA}.
|
---|
100 |
|
---|
101 |
|
---|
102 | \subsection{Discontinuity meshing}
|
---|
103 |
|
---|
104 |
|
---|
105 | Discontinuity meshing is used in the context of the radiosity global
|
---|
106 | illumination algorithm or computing soft shadows due to areal light
|
---|
107 | sources. First approximate discontinuity meshing algorithms were
|
---|
108 | studied by Campbell~\cite{Campbell:1990:AMG, Campbell91},
|
---|
109 | Lischinski~\cite{lischinski92a}, and Heckbert~\cite{Heckbert92discon}.
|
---|
110 | More elaborate methods were developed by
|
---|
111 | Drettakis~\cite{Drettakis94-SSRII, Drettakis94-FSAAL}, and Stewart and
|
---|
112 | Ghali~\cite{Stewart93-OSACS, Stewart:1994:FCSb}. These methods are
|
---|
113 | capable of creating a complete discontinuity mesh that encodes all
|
---|
114 | visual events involving the light source.
|
---|
115 |
|
---|
116 | The classical radiosity is based on an evaluation of form factors
|
---|
117 | between two patches~\cite{Schroder:1993:FFB}. The visibility
|
---|
118 | computation is a crucial step in the form factor
|
---|
119 | evaluation~\cite{Teller:1993:GVA,Haines94,Teller:1994:POL,
|
---|
120 | Nechvile:1996:FFE,Teichmann:WV}. Similar visibility computation takes
|
---|
121 | place in the scope of hierarchical radiosity
|
---|
122 | algorithms~\cite{Soler:1996:AEB, Drettakis:1997:IUG, Daubert:1997:HLS}.
|
---|
123 |
|
---|
124 |
|
---|
125 |
|
---|
126 | \subsection{Global visibility}
|
---|
127 |
|
---|
128 | The aim of {\em global visibility} computations is to capture and
|
---|
129 | describe visibility in the whole scene~\cite{Durand:1996:VCN}. The
|
---|
130 | global visibility algorithms are typically based on some form of {\em
|
---|
131 | line space subdivision} that partitions lines or rays into equivalence
|
---|
132 | classes according to their visibility classification. Each class
|
---|
133 | corresponds to a continuous set of rays with a common visibility
|
---|
134 | classification. The techniques differ mainly in the way how the line
|
---|
135 | space subdivision is computed and maintained. A practical application
|
---|
136 | of most of the proposed global visibility structures for 3D scenes is
|
---|
137 | still an open problem. Prospectively these techniques provide an
|
---|
138 | elegant method for ray shooting acceleration --- the ray shooting
|
---|
139 | problem can be reduced to a point location in the line space
|
---|
140 | subdivision.
|
---|
141 |
|
---|
142 |
|
---|
143 | Pocchiola and Vegter introduced the visibility complex~\cite{pv-vc-93}
|
---|
144 | that describes global visibility in 2D scenes. The visibility complex
|
---|
145 | has been applied to solve various 2D visibility
|
---|
146 | problems~\cite{r-tsvcp-95,r-wvcav-97, r-dvpsv-97,Orti96-UVCRC}. The
|
---|
147 | approach was generalized to 3D by Durand et
|
---|
148 | al.~\cite{Durand:1996:VCN}. Nevertheless, no implementation of the 3D
|
---|
149 | visibility complex is currently known. Durand et
|
---|
150 | al.~\cite{Durand:1997:VSP} introduced the {\em visibility skeleton}
|
---|
151 | that is a graph describing a skeleton of the 3D visibility
|
---|
152 | complex. The visibility skeleton was verified experimentally and the
|
---|
153 | results indicate that its $O(n^4\log n)$ worst case complexity is much
|
---|
154 | better in practice. Pu~\cite{Pu98-DSGIV} developed a similar method to
|
---|
155 | the one presented in this chapter. He uses a BSP tree in \plucker
|
---|
156 | coordinates to represent a global visibility map for a given set of
|
---|
157 | polygons. The computation is performed considering all rays piercing
|
---|
158 | the scene and so the method exhibits unacceptable memory complexity
|
---|
159 | even for scenes of moderate size. Recently, Duguet and
|
---|
160 | Drettakis~\cite{duguet:02:sig} developed a robust variant of the
|
---|
161 | visibility skeleton algorithm that uses robust epsilon-visibility
|
---|
162 | predicates.
|
---|
163 |
|
---|
164 | Discrete methods aiming to describe visibility in a 4D data structure
|
---|
165 | were presented by Chrysanthou et al.~\cite{chrysanthou:cgi:98} and
|
---|
166 | Blais and Poulin~\cite{blais98a}. These data structures are closely
|
---|
167 | related to the {\em lumigraph}~\cite{Gortler:1996:L,buehler2001} or
|
---|
168 | {\em light field}~\cite{Levoy:1996:LFR}. An interesting discrete
|
---|
169 | hierarchical visibility algorithm for two-dimensional scenes was
|
---|
170 | developed by Hinkenjann and M\"uller~\cite{EVL-1996-10}. One of the
|
---|
171 | biggest problems of the discrete solution space data structures is
|
---|
172 | their memory consumption required to achieve a reasonable
|
---|
173 | accuracy. Prospectively, the scene complexity
|
---|
174 | measures~\cite{Cazals:3204:1997} provide a useful estimate on the
|
---|
175 | required sampling density and the size of the solution space data
|
---|
176 | structure.
|
---|
177 |
|
---|
178 |
|
---|
179 | \subsection{Other applications}
|
---|
180 |
|
---|
181 | Certain from-point visibility problems determining visibility over a
|
---|
182 | period of time can be transformed to a static from-region visibility
|
---|
183 | problem. Such a transformation is particularly useful for antialiasing
|
---|
184 | purposes~\cite{grant85a}. The from-region visibility can also be used
|
---|
185 | in the context of simulation of the sound
|
---|
186 | propagation~\cite{Funkhouser98}. The sound propagation algorithms
|
---|
187 | typically require lower resolution than the algorithms simulating the
|
---|
188 | propagation of light, but they need to account for simulation of
|
---|
189 | attenuation, reflection and time delays.
|
---|
190 |
|
---|
191 |
|
---|
192 |
|
---|
193 | \section{Analysis of 2D line space}
|
---|
194 |
|
---|
195 | \label{LINE_SPACE}
|
---|
196 |
|
---|
197 | The proposed visibility algorithm uses a mapping of oriented 2D lines to
|
---|
198 | points in 2D oriented projective space --- {\em line space}. Such a
|
---|
199 | mapping allows to handle sets of lines much easier than in the primal
|
---|
200 | space~\cite{pv-vc-93}.
|
---|
201 |
|
---|
202 | We use a 2D projection of Pl\"ucker
|
---|
203 | coordinates~\cite{Stolfi:1991:OPG} to parametrize lines in the plane.
|
---|
204 | This mapping corresponds to an ``oriented form'' of the duality
|
---|
205 | between points and lines in 2D. Let $l$ be an oriented line in
|
---|
206 | ${\mathcal R}^2$ and let $u=(u_x, u_y)$ and $v=(v_x, v_y)$ be two
|
---|
207 | distinct points lying on $l$. Line $l$ oriented from $u$ to $v$ can be
|
---|
208 | described by the following matrix:
|
---|
209 |
|
---|
210 | $$
|
---|
211 | M_l=\left(
|
---|
212 | \begin{array}{cccc}
|
---|
213 | u_x & u_y & 1 \\
|
---|
214 | v_x & v_y & 1
|
---|
215 | \end{array}
|
---|
216 | \right)
|
---|
217 | $$
|
---|
218 |
|
---|
219 | Pl\"ucker coordinates $l^*$ of $l$ are minors of $M_l$:
|
---|
220 |
|
---|
221 | $$
|
---|
222 | l^* = (l^*_x, l^*_y, l^*_z) = (u_y - v_y, v_x - u_x, u_x v_y - u_y v_x ).
|
---|
223 | $$
|
---|
224 |
|
---|
225 | $l^*$ can be interpreted as homogeneous coordinates of a point in 2D
|
---|
226 | {\em oriented projective space} ${\cal P}^2$. Two oriented lines are
|
---|
227 | equal if and only if their Pl\"ucker coordinates differ only by a
|
---|
228 | positive scale factor. $l^*$ also corresponds to coefficients of the
|
---|
229 | implicit equation of a line: $l'$ expressed as $l': ax + by + c= 0$
|
---|
230 | induces two oriented lines $l^*_1$, $l^*_2$, with Pl\"ucker
|
---|
231 | coordinates $l^*_1 = (a, b, c)$ and $l^*_2 = -(a,b,c)$. The \plucker
|
---|
232 | coordinates of 2D lines defined in this chapter are a simplified form
|
---|
233 | of the \plucker coordinates for 3D lines that will be discussed in
|
---|
234 | Chapter~\ref{chap:rot3d}: \plucker coordinates of a 2D line correspond
|
---|
235 | to the \plucker coordinates of a 3D line embedded in the $z = 0$ plane
|
---|
236 | after removal of redundant coordinates (equal to 0) and permutation of
|
---|
237 | the remaining ones (including some sign changes).
|
---|
238 |
|
---|
239 |
|
---|
240 | Homogeneous coordinates are often normalized, e.g. $l^*_N = (a/b, 1,
|
---|
241 | c/b)$. The normalization introduces a singularity --- in our example
|
---|
242 | vertical lines map to points at infinity. To avoid singularities we
|
---|
243 | treat ${\cal P}^2$ as 3D linear space and call it {\em line space}
|
---|
244 | denoted ${\mathcal L}$. Consequently, $l^*$ represents a halfline in
|
---|
245 | ${\mathcal L}$. All points on halfline $l^*$ represent the same
|
---|
246 | oriented line $l$.
|
---|
247 |
|
---|
248 | To sum up: an oriented line in 2D is mapped to a halfline beginning
|
---|
249 | at the origin in 3D. An example of the concept is depicted in
|
---|
250 | Figures~\ref{lines1}-(a) and ~\ref{lines1}-(b). Further in this
|
---|
251 | chapter we will mostly use ``projected'' 2D illustrations of line
|
---|
252 | space (such as in Figure~\ref{lines1}-(c)). We will still talk about
|
---|
253 | planes and halflines, but they will be depicted as lines and points,
|
---|
254 | respectively, for the sake of clarity of the presentation.
|
---|
255 |
|
---|
256 |
|
---|
257 | \subsection{Lines passing through a point}
|
---|
258 |
|
---|
259 | A {\em pencil of oriented lines} passing through a point $p = (p_x,
|
---|
260 | p_y) \in {\mathcal R}^2$ maps to an oriented plane $p^*$ in line
|
---|
261 | space that is expressed as:
|
---|
262 | $$
|
---|
263 | p^* = \{(x,y,z) | (x,y,z) \in {\mathcal L}, p_x x + p_y y + z = 0\}.
|
---|
264 | $$
|
---|
265 |
|
---|
266 | This plane subdivides ${\mathcal L}$ in two open halfspaces $p^*_+$
|
---|
267 | and $p^*_-$. Points in $p^*_-$ correspond to oriented lines passing
|
---|
268 | clockwise around $p$ (see Figure~\ref{lines1}). Points in $p^*_+$
|
---|
269 | correspond to oriented lines passing counterclockwise around $p$
|
---|
270 | (these relations depend on the orientation of the primal space). We
|
---|
271 | denote $-p^*$ an oriented plane opposite to $p^*$ that can be
|
---|
272 | expressed as:
|
---|
273 | $$
|
---|
274 | -p^* = \{(x,y,z) | (x,y,z) \in {\mathcal L}, -p_x x - p_y y - z = 0\}.
|
---|
275 | $$
|
---|
276 |
|
---|
277 |
|
---|
278 | \begin{figure*}[tb]
|
---|
279 | \rule{0pt}{0pt}\hfill
|
---|
280 | \includegraphics[width=1.0\textwidth,draft=\DRAFTFIGS]{figs/lines1}
|
---|
281 | \hfill\rule{0pt}{0pt}
|
---|
282 | \centerline{\small \hspace{0.01\textwidth}{\bf (a)}\hspace{0.3\textwidth} {\bf (b)} \hspace{0.3\textwidth} {\bf (c)}}
|
---|
283 | \vspace{-1.5em}
|
---|
284 | \caption{
|
---|
285 | {\bf (a)} Four oriented lines in primal space.
|
---|
286 | {\bf (b)} Mappings of the four lines and point p.
|
---|
287 | Lines intersecting p map to plane $p^*$.
|
---|
288 | Lines passing clockwise (counterclockwise) around $p$, map to
|
---|
289 | $p^*_-$ ($p^*_+$).
|
---|
290 | {\bf (c)} The situation after projection to a plane perpendicular to $p^*$. }
|
---|
291 | \label{lines1}
|
---|
292 | \end{figure*}
|
---|
293 |
|
---|
294 | \subsection{Lines passing through a line segment}
|
---|
295 |
|
---|
296 | Oriented lines passing through a line segment can be decomposed into
|
---|
297 | two sets depending on their orientation. Consider a supporting line
|
---|
298 | $l_S$ of a line segment $S$, that partitions the plane in open
|
---|
299 | halfspaces $S^+$ and $S^-$. Denote $a$ and $b$ the two endpoints of
|
---|
300 | $S$ and $a^*$ and $b^*$ their mappings to ${\mathcal L}$. Lines that
|
---|
301 | intersect $S$ and ``come from'' $S^-$ can be expressed in line space
|
---|
302 | as an intersection of halfspaces $a^*_+$ and $b^*_-$. The opposite
|
---|
303 | oriented lines intersecting $S$ are expressed as $a^*_- \cap b^*_+$
|
---|
304 | (see Figure~\ref{lines2}-(a,b)).
|
---|
305 |
|
---|
306 | %\begin{minipage}{\textwidth}
|
---|
307 |
|
---|
308 | \begin{figure}[htb]
|
---|
309 | \rule{0pt}{0pt}\hfill
|
---|
310 | \includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/lines2}
|
---|
311 | \hfill\rule{0pt}{0pt}
|
---|
312 | \centerline{\small
|
---|
313 | \hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
|
---|
314 | }
|
---|
315 | \vspace{-1.5em}
|
---|
316 | \caption{ {\bf (a)} A line segment $S$ and three oriented lines that
|
---|
317 | intersect $S$. {\bf (b)} The situation in line space: the projection of two
|
---|
318 | wedges corresponding to lines intersecting $S$. Mappings of supporting
|
---|
319 | line $l_S$ of $S$ are two halflines that project to point
|
---|
320 | $l_S^*$. Line $k$ intersects point $b$ and therefore maps to plane
|
---|
321 | $b^*$. Lines $m$ and $n$ map to the wedge corresponding to their
|
---|
322 | orientation. }
|
---|
323 | \label{lines2}
|
---|
324 | \end{figure}
|
---|
325 |
|
---|
326 |
|
---|
327 |
|
---|
328 |
|
---|
329 | \subsection{Lines passing through two line segments}
|
---|
330 |
|
---|
331 | \label{sec:blocker_polygon}
|
---|
332 |
|
---|
333 | Consider two disjoint line segments such as those depicted in
|
---|
334 | Figure~\ref{lines3}-(a). The set of lines passing through the two line
|
---|
335 | segments can be described as an intersection of four halfspaces in
|
---|
336 | line space. The four halfspaces correspond to mappings of endpoints of
|
---|
337 | the two line segments. Since the halfspaces pass through the origin
|
---|
338 | of ${\mathcal L}$, their intersection is a pyramid with the apex at
|
---|
339 | the origin. The boundary halflines of the pyramid correspond to
|
---|
340 | mappings of the four {\em extremal lines} induced by the two
|
---|
341 | segments. Denote ${\mathcal P}(S, O)$ a line space pyramid
|
---|
342 | corresponding to oriented lines intersecting line segments $S$ and $O$
|
---|
343 | in this order. We represent the pyramid by a {\em blocker polygon}
|
---|
344 | $B(S, O)$ (see Figure~\ref{lines3}-(b)). Since $B(S, O)$ only
|
---|
345 | represents the pyramid ${\mathcal P}(S, O)$, it need not be a planar
|
---|
346 | polygon, i.e. its vertices may lay anywhere on the boundary halflines
|
---|
347 | of ${\mathcal P}(S, O)$. We normalize the vertex coordinates: they
|
---|
348 | correspond to an intersection of the boundary halfline of ${\mathcal
|
---|
349 | P}(S, O)$ and the unit sphere centered at the origin of ${\mathcal L}$.
|
---|
350 |
|
---|
351 | \begin{figure}[htb]
|
---|
352 | \hfill\rule{0pt}{0pt}
|
---|
353 | \includegraphics[width=0.7\textwidth,draft=\DRAFTFIGS]{figs/lines3}
|
---|
354 | \hfill\rule{0pt}{0pt}
|
---|
355 | \centerline{\small
|
---|
356 | \hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
|
---|
357 | }
|
---|
358 | \vspace{-1.5em}
|
---|
359 | \caption{ {\bf (a)} Two line segments and corresponding four extremal lines
|
---|
360 | oriented from $S$ to $O$. Separating lines $ad$ and $bc$ bound region
|
---|
361 | of partial visibility of $S$ behind $O$ (penumbra). Supporting lines
|
---|
362 | $ac$ and $bd$ bound region where $S$ is invisible (umbra). {\bf (b)}
|
---|
363 | Blocker polygon $B(S,O)$ representing pyramid ${\mathcal
|
---|
364 | P}(S,O)$.
|
---|
365 | }
|
---|
366 | \label{lines3}
|
---|
367 | \end{figure}
|
---|
368 |
|
---|
369 |
|
---|
370 | In Figure~\ref{lines4}-(a), the supporting line of $cd$ intersects $ab$
|
---|
371 | at point $x$. The set of rays passing through $ab$ and $cd$ can be
|
---|
372 | decomposed to rays passing through $ax$ and $cd$, and through $xb$
|
---|
373 | and $cd$. Rays through $ax$ and $cd$ map to a pyramid that is
|
---|
374 | described by intersection of only three halfspaces induced by mappings
|
---|
375 | of $a$, $x$ and $d$. Rays through $xb$ and $cd$ can be
|
---|
376 | described similarly. The configuration in line space is depicted in
|
---|
377 | Figure~\ref{lines4}-(b).
|
---|
378 |
|
---|
379 | \begin{figure}[htb]
|
---|
380 | \rule{0pt}{0pt}\hfill
|
---|
381 | \includegraphics[width=0.7\textwidth,draft=\DRAFTFIGS]{figs/lines4}
|
---|
382 | \hfill\rule{0pt}{0pt}
|
---|
383 | \centerline{\small
|
---|
384 | \hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
|
---|
385 | }
|
---|
386 | \vspace{-1.5em}
|
---|
387 | \caption{ {\bf (a)} Degenerate configuration of line segments: the supporting
|
---|
388 | line of $cd$ intersects $ab$ at point $x$. There are five extremal
|
---|
389 | lines. Note, that there is no umbra region. {\bf (b)} In line space the
|
---|
390 | configuration yields two pyramids sharing a boundary that is a
|
---|
391 | mapping of the oriented line $cd$.
|
---|
392 | }
|
---|
393 | \label{lines4}
|
---|
394 | \end{figure}
|
---|
395 |
|
---|
396 | \subsection{Lines passing through a set of line segments}
|
---|
397 |
|
---|
398 | Consider a set of $n+1$ line segments. We call one line segment the
|
---|
399 | {\em source} (denoted by $S$) and the other $n$ segments we call
|
---|
400 | occluders (denoted by $O_k$, $1 \leq k \leq n$). Further in the
|
---|
401 | chapter we will use the term {\em ray} as a representative of an
|
---|
402 | oriented line that is oriented from the source ``towards'' the
|
---|
403 | occluders.
|
---|
404 |
|
---|
405 | Assume that we can process all occluders in a strict front-to-back
|
---|
406 | order with respect to the given source. We have already processed $k$
|
---|
407 | occluders and we continue by processing $O_{k+1}$. $O_{k+1}$ can be
|
---|
408 | visible through rays that correspond to the pyramid ${\mathcal P}(S,
|
---|
409 | O_{k+1})$. Nevertheless some of these rays can be blocked by
|
---|
410 | combination of already processed occluders $O_x$ ($1\leq x \leq k$).
|
---|
411 | To determine if $O_{k+1}$ is visible we subtract all ${\mathcal
|
---|
412 | P}(S,O_x)$ from ${\mathcal P}(S,O_{k+1})$:
|
---|
413 |
|
---|
414 | $$
|
---|
415 | {\mathcal V}(S,O_{k+1}) = {\mathcal P}(S,O_{k+1})\ - \bigcup_{1 \leq x \leq k} {\mathcal P}(S,O_x)
|
---|
416 | $$
|
---|
417 |
|
---|
418 | ${\mathcal V}(S, O_{k+1})$ is a set pyramids representing rays through
|
---|
419 | which $O_{k+1}$ is visible from $S$. In turn, all rays corresponding
|
---|
420 | to ${\mathcal V}(S,O_{k+1})$ are blocked behind $O_{k+1}$. If
|
---|
421 | ${\mathcal V}(S, O_{k+1})$ is an empty set, occluder $O_{k+1}$ is
|
---|
422 | invisible. This suggest incremental construction of an arrangement of
|
---|
423 | pyramids ${\mathcal A}_k$ that corresponds to rays blocked by the
|
---|
424 | $k$ processed occluders. We determine ${\mathcal V}(S,O_{k+1})$ and
|
---|
425 | ${\mathcal A}_{k+1}$ (${\mathcal A}_0$ is empty):
|
---|
426 |
|
---|
427 | $$
|
---|
428 | {\mathcal V}(S,O_{k+1}) = {\mathcal P}(S,O_{k+1}) \ - \ {\mathcal A}_k,
|
---|
429 | $$
|
---|
430 | $$
|
---|
431 | {\mathcal A}_{k+1} = {\mathcal A}_k \cup {\mathcal P}(S,O_{k+1}) =
|
---|
432 | {\mathcal A}_k \ \cup \ {\mathcal V}(S,O_{k+1}).
|
---|
433 | $$
|
---|
434 |
|
---|
435 | Figures~\ref{lines5}-(a,b) depict a projection of an arrangement
|
---|
436 | ${\mathcal A}_3$ of a source and three occluders. Note that the
|
---|
437 | shorter the source line segment the narrower ($s^*_a$ and $s^*_b$ get
|
---|
438 | closer) are the pyramids ${\mathcal P}(S,O_k)$.
|
---|
439 |
|
---|
440 |
|
---|
441 |
|
---|
442 |
|
---|
443 | \begin{figure}[htb]
|
---|
444 | \rule{0pt}{0pt}\hfill
|
---|
445 | \includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/rot2new}
|
---|
446 | \hfill\rule{0pt}{0pt}
|
---|
447 | \centerline{\small
|
---|
448 | \hspace{0.01\textwidth}{\bf (a)}\hspace{0.2\textwidth} {\bf (b)}
|
---|
449 | }
|
---|
450 | \vspace{-1.5em}
|
---|
451 | \caption{ {\bf (a)} The source line segment $S$ and three
|
---|
452 | occluders. $Q_{1-3}$ denote unoccluded funnels. {\bf (b)} The
|
---|
453 | line space subdivision. For each cell, the corresponding occluder-sequence
|
---|
454 | is depicted. Note the cells $Q^*_1$, $Q^*_2$ and $Q^*_3$
|
---|
455 | corresponding to unoccluded funnels.}
|
---|
456 | \label{lines5}
|
---|
457 | \end{figure}
|
---|
458 |
|
---|
459 | Recall that the pyramid ${\mathcal P}(S,O_k)$ is represented by
|
---|
460 | blocker polygon $B(S,O_k)$. The construction of the arrangement
|
---|
461 | ${\mathcal A}_k$ resembles the from-point visibility problem, more
|
---|
462 | specifically the hidden surface removal applied on the blocker
|
---|
463 | polygons with respect to the origin of ${\mathcal L}$. The difference
|
---|
464 | is that the depth information is irrelevant in line space. The
|
---|
465 | priority of blocker polygons is either completely determined by the
|
---|
466 | processing order of occluders or their depth must be compared in
|
---|
467 | primal space. This observation is supported by the classification of
|
---|
468 | visibility problems presented in
|
---|
469 | Chapter~\ref{chap:classes}. Visibility from point in 3D and visibility
|
---|
470 | from region in 2D induce a two-dimensional problem-relevant line
|
---|
471 | set. This suggests the possibility of mapping one problem to another.
|
---|
472 |
|
---|
473 | In the next section we show how the arrangement ${\mathcal A}_k$ can
|
---|
474 | be maintained consistently and efficiently using the occlusion tree.
|
---|
475 |
|
---|
476 |
|
---|
477 |
|
---|
478 | \section{Pl\"ucker coordinates of lines in 3D}
|
---|
479 |
|
---|
480 | \label{sec:plucker}
|
---|
481 |
|
---|
482 |
|
---|
483 | We will use a mapping that describes an oriented 3D line as a point
|
---|
484 | in a projective 5D space~\cite{Boissonnat98} by means of \plucker
|
---|
485 | coordinates~\cite{Teller92phd,p-rsls-97,yn-sbgtc-97,Pu98-DSGIV}. \plucker
|
---|
486 | coordinates allow to represent sets of lines using 5D polyhedra and to
|
---|
487 | compute visibility by means of polyhedra set operations in 5D.
|
---|
488 |
|
---|
489 | A line in 3D can be described by homogeneous coordinates of two
|
---|
490 | distinct points on that line. Let $l$ be a line in ${\cal R}^3$ and
|
---|
491 | let $\mbi{u}=(u_x, u_y, u_z, u_w)$ and $\mbi{v}=(v_x,v_y,v_z, v_w)$ be
|
---|
492 | two distinct points in homogeneous coordinates lying on $l$. A line
|
---|
493 | $l$ oriented from $\mbi{u}$ to $\mbi{v}$ can be described by the following matrix:
|
---|
494 |
|
---|
495 | \begin{equation}
|
---|
496 | l=\left(
|
---|
497 | \begin{array}{cccc}
|
---|
498 | u_{x} & u_{y} & u_{z} & u_{w} \\
|
---|
499 | v_{x} & v_{y} & v_{z} & v_{w}
|
---|
500 | \end{array}
|
---|
501 | \right)
|
---|
502 | \label{coord_cara}
|
---|
503 | \end{equation}
|
---|
504 |
|
---|
505 | Minors of the matrix correspond to components of the {\em \plucker
|
---|
506 | coordinates} $\bpi_l$ of line $l$:
|
---|
507 |
|
---|
508 | \begin{equation}
|
---|
509 | \begin{array}{ll}
|
---|
510 | \bpi_l & = (\pi_{l0}, \pi_{l1}, \pi_{l2}, \pi_{l3}, \pi_{l4}, \pi_{l5}) = \\
|
---|
511 | & = (\xi_{wx},\xi_{wy},\xi_{wz},\xi_{yz},\xi_{zx},\xi_{xy}),
|
---|
512 | \end{array}
|
---|
513 | \label{eq:plucker_coords_def}
|
---|
514 | \end{equation}
|
---|
515 |
|
---|
516 | where
|
---|
517 |
|
---|
518 | \begin{equation}
|
---|
519 | \xi_{rs} = det\left(
|
---|
520 | \begin{array}{cc}
|
---|
521 | u_{r} & u_{s} \\
|
---|
522 | v_{r} & v_{s}
|
---|
523 | \end{array}
|
---|
524 | \right).
|
---|
525 | \end{equation}
|
---|
526 |
|
---|
527 | Substituting $u_w=1$ and $v_w=1$ into Eq.~\ref{eq:plucker_coords_def}
|
---|
528 | enumerates to:
|
---|
529 |
|
---|
530 | \begin{equation}
|
---|
531 | \begin{array}{l}
|
---|
532 | \pi_{l0} = v_x - u_x\\
|
---|
533 | \pi_{l1} = v_y - u_y\\
|
---|
534 | \pi_{l2} = v_z - u_z\\
|
---|
535 | \pi_{l3} = u_{y}v_{z} - u_{z}v_{y}\\
|
---|
536 | \pi_{l4} = u_{z}v_{x} - u_{x}v_{z}\\
|
---|
537 | \pi_{l5} = u_{x}v_{y} - u_{y}v_{x}
|
---|
538 | \end{array}
|
---|
539 | \label{eq:plucker_coords}
|
---|
540 | \end{equation}
|
---|
541 |
|
---|
542 | The \plucker coordinates $\bpi_l$ can be seen as homogeneous
|
---|
543 | coordinates of a point in a projective five-dimensional space ${\cal
|
---|
544 | P}^5$. We call this point a {\em \plucker point} $\ppoint_l$ of
|
---|
545 | $l$. For a given oriented line $l$ the \plucker coordinates $\bpi_l$
|
---|
546 | are unique and they do not depend on the choice of points $p$ and $q$.
|
---|
547 | We will use the notation of a \plucker point $\ppoint_l$ in the case
|
---|
548 | when we want to stress that the corresponding \plucker coordinates
|
---|
549 | $\bpi_l$ are interpreted as a point in ${\cal P}^5$.
|
---|
550 |
|
---|
551 | Using the projective duality the \plucker coordinates can be
|
---|
552 | interpreted as coefficients of a hyperplane. The {\em \plucker
|
---|
553 | coefficients} $\bomega_l$ of line $l$ are given as:
|
---|
554 |
|
---|
555 |
|
---|
556 | \begin{equation}
|
---|
557 | \begin{array}{ll}
|
---|
558 | \bomega_l
|
---|
559 | & = (\omega_{l0}, \omega_{l1}, \omega_{l2}, \omega_{l3}, \omega_{l4}, \omega_{l5}) = \\
|
---|
560 | & = (\xi_{yz},\xi_{zx},\xi_{xy},\xi_{wx},\xi_{wy},\xi_{wz})
|
---|
561 | \end{array}
|
---|
562 | \label{eq:plucker_coef_def}
|
---|
563 | \end{equation}
|
---|
564 |
|
---|
565 | Substituting Eq.~\ref{eq:plucker_coords} into Eq.~\ref{eq:plucker_coef_def}
|
---|
566 | we get:
|
---|
567 |
|
---|
568 | \begin{equation}
|
---|
569 | \begin{array}{l}
|
---|
570 | \omega_{l0} = \pi_{l3} \\
|
---|
571 | \omega_{l1} = \pi_{l4}\\
|
---|
572 | \omega_{l2} = \pi_{l5}\\
|
---|
573 | \omega_{l3} = \pi_{l0}\\
|
---|
574 | \omega_{l4} = \pi_{l1}\\
|
---|
575 | \omega_{l5} = \pi_{l2}
|
---|
576 | \end{array}
|
---|
577 | \label{eq:plucker_coef}
|
---|
578 | \end{equation}
|
---|
579 |
|
---|
580 |
|
---|
581 | The \plucker coefficients $\bomega_l$ define a {\em \plucker
|
---|
582 | hyperplane} $\pplane_l$. We will use the notation of a \plucker
|
---|
583 | hyperplane $\pplane_l$ when we want to stress that the
|
---|
584 | corresponding \plucker coefficients $\bomega_l$ are interpreted as a
|
---|
585 | hyperplane in ${\cal P}^5$. In terms of \plucker points the \plucker
|
---|
586 | hyperplane can be expressed as:
|
---|
587 |
|
---|
588 | \begin{equation}
|
---|
589 | \label{hyperplane}
|
---|
590 | \begin{array}{l}
|
---|
591 | \pplane_l = \{\ppoint | \ppoint \in {\cal P}^5, \bomega_l \odot \bpi = 0\}
|
---|
592 | \end{array}
|
---|
593 | \end{equation}
|
---|
594 |
|
---|
595 | The \plucker hyperplane induces closed positive and negative halfspaces
|
---|
596 | given as:
|
---|
597 |
|
---|
598 | \begin{equation}
|
---|
599 | \begin{array}{l}
|
---|
600 | \pplane^{+}_l = \{\ppoint | \ppoint \in {\cal P}^{5}, \bomega_l \odot \bpi \geq 0\} \\
|
---|
601 | \pplane^{-}_l = \{\ppoint | \ppoint \in {\cal P}^{5}, \bomega_l \odot \bpi \leq 0\} \\
|
---|
602 | \end{array}
|
---|
603 | \label{eq:def_halfspaces}
|
---|
604 | \end{equation}
|
---|
605 |
|
---|
606 | These definitions of \plucker coordinates and coefficients follow the
|
---|
607 | ``traditional'' convention~\cite{Pu98-DSGIV}. They differ from the
|
---|
608 | definitions used by Teller~\cite{Teller92phd} who used a permuted
|
---|
609 | order of the coordinates. The traditional convention provides an
|
---|
610 | elegant interpretation of \plucker coordinates that will be discussed
|
---|
611 | in Section~\ref{sec:plucker_interp}.
|
---|
612 |
|
---|
613 | If $a$ and $b$ are two directed lines, the relation $side(a,b)$ is
|
---|
614 | defined as an inner product $\bomega_a \odot \bpi_b$ or permuted inner
|
---|
615 | product $\bpi_a \times \bpi_b$:
|
---|
616 |
|
---|
617 | \begin{equation}
|
---|
618 | \begin{array}{ll}
|
---|
619 | side(a,b) & = \bomega_a \odot \bpi_b = \\
|
---|
620 | & = \omega_{a0}\pi_{b0} + \omega_{a1}\pi_{b1} + \omega_{a2}\pi_{b2} +
|
---|
621 | \omega_{a3}\pi_{b3} + \omega_{a4}\pi_{b4} + \omega_{a5}\pi_{b5} = \\
|
---|
622 | & = \bpi_a \times \bpi_b = \\
|
---|
623 | & = \pi_{a0}\pi_{b3} + \pi_{a1}\pi_{b4} + \pi_{a2}\pi_{b5} +
|
---|
624 | \pi_{a3}\pi_{b0} + \pi_{a4}\pi_{b1} + \pi_{a5}\pi_{b2}
|
---|
625 | \end{array}
|
---|
626 | \label{eq:side}
|
---|
627 | \end{equation}
|
---|
628 |
|
---|
629 |
|
---|
630 | This relation can be interpreted with the right-hand rule
|
---|
631 | (Figure~\ref{sidepict}). If the thumb of the right hand is directed
|
---|
632 | along line $a$, then:
|
---|
633 |
|
---|
634 | \begin{itemize}
|
---|
635 | \item $side(a,b)> 0$, if line $b$ is oriented in the direction of the fingers,
|
---|
636 |
|
---|
637 | \item $side(a,b) = 0$, if lines $a$ and $b$ intersect or are parallel,
|
---|
638 |
|
---|
639 | \item $side(a,b) < 0$, if line $b$ points against the direction of the fingers.
|
---|
640 | \end{itemize}
|
---|
641 |
|
---|
642 | \begin{figure}[htb]
|
---|
643 | \centerline{
|
---|
644 | \includegraphics[width=0.8\textwidth,draft=\DRAFTFIGS]{figs/pldual}}
|
---|
645 | \caption{The $side(a,b)$, interpreted as the right-hand rule.}
|
---|
646 | \label{sidepict}
|
---|
647 | \end{figure}
|
---|
648 |
|
---|
649 |
|
---|
650 | \plucker coordinates have an important property: Although every
|
---|
651 | oriented line in ${\cal R}^3$ maps to a point in \plucker coordinates,
|
---|
652 | not every tuple of six real numbers corresponds to a real line. Only
|
---|
653 | the points $\ppoint \in {\cal P}^5$ \plucker coordinates of which
|
---|
654 | satisfy the condition
|
---|
655 |
|
---|
656 | \begin{equation}
|
---|
657 | \bpi \odot \bpi = 0 \qquad \equiv \qquad \pi_{0}\pi_{3} + \pi_{1}\pi_{4} + \pi_{2}\pi_{5} = 0,
|
---|
658 | \label{eq:plucker_quadric}
|
---|
659 | \end{equation}
|
---|
660 |
|
---|
661 | represent real lines in ${\cal R}^3$. All other points correspond to
|
---|
662 | lines which are said to be {\em imaginary}. The set of points in
|
---|
663 | ${\cal P}^5$ satisfying Eq.~\ref{eq:plucker_quadric} forms a 4D
|
---|
664 | hyperboloid of one sheet called the {\em \plucker quadric}, also known
|
---|
665 | as the {\em Klein quadric} or the {\em Grassman manifold}
|
---|
666 | (see Figure~\ref{quadric}).
|
---|
667 |
|
---|
668 |
|
---|
669 | \begin{figure}[htb]
|
---|
670 | \medskip
|
---|
671 | \centerline{
|
---|
672 | \includegraphics[width=0.65\textwidth,draft=\DRAFTFIGS]{figs/reallin}}
|
---|
673 | \caption{Real lines map on points on the Pl\"{u}cker quadric.}
|
---|
674 | \label{quadric}
|
---|
675 | \end{figure}
|
---|
676 |
|
---|
677 | The six \plucker coordinates of a real line are not
|
---|
678 | independent. Firstly, they describe an oriented projective space,
|
---|
679 | secondly, they must satisfy the
|
---|
680 | equation~\ref{eq:plucker_quadric}. Thus there are four degrees of
|
---|
681 | freedom in the description of a 3D line, which conforms with the
|
---|
682 | classification from Chapter~\ref{chap:overview}.
|
---|
683 |
|
---|
684 | \plucker coordinates allow to detect an incidence of two lines by
|
---|
685 | computing an inner product of a homogeneous point (mapping of one
|
---|
686 | line) with a hyperplane (mapping of the other). Lines $l$ and $l'$
|
---|
687 | intersect or are parallel (i.e. meet at infinity) if and only if
|
---|
688 | $\ppoint_l \in \pplane_{l'}$, i.e. $side(l, l') = 0$. Note that according
|
---|
689 | to ~\ref{eq:plucker_quadric} any line always meets itself.
|
---|
690 |
|
---|
691 |
|
---|
692 | \subsection{Geometric interpretation of \plucker coordinates}
|
---|
693 | \label{sec:plucker_interp}
|
---|
694 |
|
---|
695 | For a better understanding of \plucker coordinates it is natural to
|
---|
696 | ask how each individual \plucker coordinate is related to the geometry
|
---|
697 | of the corresponding line. The \plucker coordinates of a given line
|
---|
698 | can be divided to the {\em directional} and the {\em locational}
|
---|
699 | parts. The directional part encodes the direction of the line, the
|
---|
700 | locational part encodes the position of the line. Given \plucker
|
---|
701 | coordinates $\bpi_l$ of a line $l$ we can write:
|
---|
702 |
|
---|
703 | \begin{equation}
|
---|
704 | \begin{array}{lll}
|
---|
705 | \mbi{d}_l & = (\pi_{l0}, \pi_{l1}, \pi_{l2}), \\
|
---|
706 | \mbi{l}_l & = (\pi_{l3}, \pi_{l4}, \pi_{l5}), \\
|
---|
707 | \end{array}
|
---|
708 | \end{equation}
|
---|
709 |
|
---|
710 | where $\mbi{d}_l$ is the {\em directional vector} of $l$ and $\mbi{l}_l$
|
---|
711 | is the {\em locational vector} of $l$. The \plucker coordinates
|
---|
712 | $\bpi_l$ and the \plucker coefficients $\bomega_l$ can be expressed as:
|
---|
713 |
|
---|
714 |
|
---|
715 | \begin{equation}
|
---|
716 | \begin{array}{ll}
|
---|
717 | \bpi_l &= [\mbi{d}_l; \mbi{l}_l],\\
|
---|
718 | \bomega_l &= [\mbi{l}_l; \mbi{d}_l].
|
---|
719 | \end{array}
|
---|
720 | \label{eq:rot3_locdir}
|
---|
721 | \end{equation}
|
---|
722 |
|
---|
723 |
|
---|
724 | \subsubsection{Extracting a point}
|
---|
725 |
|
---|
726 | Often we need to describe a line using a parametric representation by
|
---|
727 | means of an {\em anchor point} and a directional vector. Given a line
|
---|
728 | $l$ the directional vector $\mbi{d}_l$ is embedded in the \plucker
|
---|
729 | coordinates of $l$ (see Eq.~\ref{eq:rot3_locdir}). The anchor point
|
---|
730 | $\mbi{a}_l$ can be computed as:
|
---|
731 |
|
---|
732 | \begin{equation}
|
---|
733 | \mbi{a}_l = (a_x, a_y, a_z) = \frac{\mbi{d}_l \times \mbi{l}_l}{\parallel \mbi{d}_l \parallel ^2}.
|
---|
734 | \end{equation}
|
---|
735 |
|
---|
736 |
|
---|
737 | \subsubsection{Computing the distance}
|
---|
738 |
|
---|
739 | The distance between two lines $l$ and $l'$ can be expressed
|
---|
740 | using their anchor points and the directional vectors:
|
---|
741 |
|
---|
742 | \begin{equation}
|
---|
743 | dist(l, l') = { | (\mbi{a}_l - \mbi{a}_{l'}) \cdot (\mbi{d}_l \times
|
---|
744 | \mbi{d}_{l'}) | \over \parallel \mbi{d}_l \times \mbi{d}_{l'} \parallel }.
|
---|
745 | \end{equation}
|
---|
746 |
|
---|
747 |
|
---|
748 | The distance is the length of the projection of the line segment
|
---|
749 | $\mbi{a}_l,\mbi{a}_{l'}$ onto the direction $\mbi{d}_l \times
|
---|
750 | \mbi{d}_{l'}$.
|
---|
751 |
|
---|
752 |
|
---|
753 |
|
---|
754 | %%%%%%%%%%%%%%%%%%%%%%
|
---|
755 |
|
---|
756 | \section{Visual events}
|
---|
757 |
|
---|
758 | \label{sec:events}
|
---|
759 |
|
---|
760 | This section discusses visual events occurring in polygonal
|
---|
761 | scenes~\cite{Gigus90}. We will focus on the boundaries of visual
|
---|
762 | events and their relation to \plucker coordinates. The understanding
|
---|
763 | of the visual events helps to comprehend the complexity of the
|
---|
764 | from-region visibility in 3D.
|
---|
765 |
|
---|
766 | Any scene can be decomposed into regions from which the scene has a
|
---|
767 | topologically equivalent view~\cite{Gigus90}. Boundaries of such
|
---|
768 | regions correspond to {\em event surfaces}. Crossing an event surface
|
---|
769 | causes a {\em visual event}, i.e. a change in the topology of the view
|
---|
770 | (visibility map). In polygonal scenes there are three types of event
|
---|
771 | surfaces~\cite{Gigus90}:
|
---|
772 |
|
---|
773 | \begin{itemize}
|
---|
774 | \item {\em vertex-edge} (VE) events involving an edge and a vertex
|
---|
775 | of two distinct polygons.
|
---|
776 | \item {\em edge-edge-edge} (EEE) events involving three edges of
|
---|
777 | three distinct polygons.
|
---|
778 | \item {\em supporting} events corresponding to supporting planes of
|
---|
779 | scene polygons. The supporting event can be seen as a degenerated
|
---|
780 | case of VE or EEE events.
|
---|
781 | \end{itemize}
|
---|
782 |
|
---|
783 | The VE events correspond to planes, the EEE events in general form
|
---|
784 | quadratic surfaces. The definitions assume that the scene polygons are
|
---|
785 | in general non-degenerate position. In real world scenes the polygons
|
---|
786 | or their edges polygons can be variously aligned. In such a case these
|
---|
787 | definitions of visibility events form minimal sets of edges and
|
---|
788 | vertices defining an event. For example a VE event can involve a
|
---|
789 | vertex and several edges of scene polygons (see
|
---|
790 | Figure~\ref{fig:degen_event}).
|
---|
791 |
|
---|
792 | \begin{figure}[htb]
|
---|
793 | \centerline{
|
---|
794 | \includegraphics[width=0.45\textwidth,draft=\DRAFTFIGS]{figs/ve_degen}}
|
---|
795 | \caption{Degenerated VE event. The VE event is induced by a vertex and
|
---|
796 | three edges of scene polygons.}
|
---|
797 | \label{fig:degen_event}
|
---|
798 | \end{figure}
|
---|
799 |
|
---|
800 |
|
---|
801 | The intersections of event surfaces correspond to {\em extremal
|
---|
802 | lines}~\cite{Teller92phd}. An extremal line intersects four edges of
|
---|
803 | some scene polygons. There are four types of extremal lines:
|
---|
804 | vertex-vertex (VV) lines, vertex-edge-edge (VEE) lines,
|
---|
805 | edge-vertex-edge (EVE) and quadruple edge (4E) lines. Imagine
|
---|
806 | ``sliding'' an extremal line (of any type) away from its initial
|
---|
807 | position by relaxing exactly one of the four edge constraints
|
---|
808 | determining the line. The section of the event surface swept out by
|
---|
809 | the sliding line is called the {\em swath}. A swath is either planar
|
---|
810 | if it corresponds to a VE event surface or a regulus if it is embedded
|
---|
811 | in an EEE event surface.
|
---|
812 |
|
---|
813 | Figure~\ref{swaths}-(a) shows an extremal VV line tight on four edges
|
---|
814 | A,B,C, and D. Relaxing constraint C yields a VE (planar) swath defined
|
---|
815 | by A,B, and D. When the sliding line encounters an obstacle (edge E) it
|
---|
816 | terminates at a VV extremal line defined by A,B,D, and
|
---|
817 | E. Figure~\ref{swaths}-(b) depicts an extremal 4E line tight on the
|
---|
818 | mutually skew edges A,B,C, and D. Relaxing constraint A produces an EEE
|
---|
819 | event surface that is a regulus intersecting B,C, and D. When the
|
---|
820 | sliding line encounters edge E the swath terminates at an VEE extremal
|
---|
821 | line.
|
---|
822 |
|
---|
823 | \begin{figure}[htb]
|
---|
824 | \centerline{
|
---|
825 | \includegraphics[width=0.75\textwidth,draft=\DRAFTFIGS]{figs/swaths}}
|
---|
826 | \centerline{\small
|
---|
827 | {\bf (a)}\hspace{0.3\textwidth} {\bf (b)}
|
---|
828 | \hspace{0.2\textwidth}}
|
---|
829 | \caption{Swaths of event surfaces. (a) VE swath. (b) EEE swath. }
|
---|
830 | \label{swaths}
|
---|
831 | \end{figure}
|
---|
832 |
|
---|
833 |
|
---|
834 | \subsection{Visual events and \plucker coordinates}
|
---|
835 |
|
---|
836 | \plucker coordinates allow an elegant description of event surfaces.
|
---|
837 | An event surface can be expressed as an intersection of three \plucker
|
---|
838 | hyperplanes, and thus avoiding explicit treatment of quadratic
|
---|
839 | surfaces. The non-linear EEE surfaces correspond to curves embedded in
|
---|
840 | the intersection of the \plucker hyperplanes.
|
---|
841 |
|
---|
842 | Let ${\cal H}$ be an arrangement~\cite{dcg-handbook} of hyperplanes in
|
---|
843 | ${\cal P}^5$ that correspond to \plucker coefficients of edges of the
|
---|
844 | scene polygons. The intersection of the arrangement ${\cal H}$ and the
|
---|
845 | \plucker quadric yields all visual
|
---|
846 | events~\cite{Teller92phd,p-rsls-97,Pu98-DSGIV}.
|
---|
847 |
|
---|
848 | An extremal line $l$ intersects four generator edges. Consequently,
|
---|
849 | the corresponding \plucker point $\ppoint_l$ lies on four \plucker
|
---|
850 | hyperplanes. In 5D the four hyperplanes define an edge of the
|
---|
851 | arrangement ${\cal H}$. Thus, we can find all extremal lines of a
|
---|
852 | given set of polygons by examining the edges of ${\cal H}$ for
|
---|
853 | intersections with the \plucker quadric~\cite{Pu98-DSGIV}.
|
---|
854 |
|
---|
855 |
|
---|
856 | Consider the situation depicted in Figure~\ref{swaths}. In line space
|
---|
857 | the event surfaces correspond to curves embedded in the \plucker
|
---|
858 | quadric. In general these curves are conics defined by an intersection
|
---|
859 | of the 2D-faces of ${\cal H}$ with the \plucker quadric (see
|
---|
860 | Figure~\ref{5Dswaths}).
|
---|
861 |
|
---|
862 | \begin{figure}[htb]
|
---|
863 | \centerline{
|
---|
864 | \includegraphics[width=0.6\textwidth,draft=\DRAFTFIGS]{figs/ipswaths}}
|
---|
865 | \caption{3D swaths correspond to conics on the Pl\"ucker quadric.}
|
---|
866 | \label{5Dswaths}
|
---|
867 | \end{figure}
|
---|
868 |
|
---|
869 |
|
---|
870 |
|
---|
871 | \section{Lines intersecting a polygon}
|
---|
872 |
|
---|
873 | \label{sec:rot3d_singlepoly}
|
---|
874 |
|
---|
875 | \plucker coordinates provide a tool to map lines from primal space to
|
---|
876 | points in line space. This mapping allows to perform operations of
|
---|
877 | sets of lines using set theoretical operations on the corresponding
|
---|
878 | sets of points. In polygonal scenes the {\em elementary set of lines}
|
---|
879 | is formed by lines intersecting a given polygon.
|
---|
880 |
|
---|
881 |
|
---|
882 | Assume that a convex polygon $P$ is defined by edges $e_i, 0\leq i <
|
---|
883 | n$ that are oriented counterclockwise. The set of lines ${\cal L}_P$
|
---|
884 | intersecting the polygon that are oriented in the direction of the
|
---|
885 | polygon's normal satisfies:
|
---|
886 |
|
---|
887 |
|
---|
888 | \begin{equation}
|
---|
889 | {\cal L}_P = \{ l | l \in (R^3, R^3), side(\bpi_l, \bpi_{e_i}) \leq 0, \forall i \in \langle 0,n) \},
|
---|
890 | \label{eq:halfspaces}
|
---|
891 | \end{equation}
|
---|
892 |
|
---|
893 | where $\bpi_l$ are \plucker coordinates of line $l$ and $\bpi_{e_i}$ are
|
---|
894 | \plucker coordinates of $i$-th edge of the polygon. Substituting the
|
---|
895 | Eq.~\ref{eq:side} and rewriting the equation in terms of a set of
|
---|
896 | \plucker points we get:
|
---|
897 |
|
---|
898 | \begin{equation}
|
---|
899 | \begin{array}{ll}
|
---|
900 | {\cal F}_P & = \{ \ppoint | \ppoint \in {\cal P}^5, \bpi \times \bpi_{e_i} \leq 0, \forall i \in \langle 0,n) \} = \\
|
---|
901 | & = \{ \ppoint | \ppoint \in {\cal P}^5, \bpi \odot \bomega_{e_i} \leq 0, \forall i \in \langle 0,n) \},
|
---|
902 | \end{array}
|
---|
903 | \label{eq:feasible}
|
---|
904 | \end{equation}
|
---|
905 |
|
---|
906 | where ${\cal F}_P$ is a set of {\em feasible \plucker points} for
|
---|
907 | polygon $P$. Substituting Eq.~\ref{eq:def_halfspaces}
|
---|
908 | into~\ref{eq:feasible} we obtain:
|
---|
909 |
|
---|
910 | \begin{equation}
|
---|
911 | \begin{array}{ll}
|
---|
912 | {\cal F}_P & = \{ \ppoint | \ppoint \in {\cal P}^5, \bpi \in \pplane^-_{e_i}, \forall i \in \langle 0,n) \}
|
---|
913 | \end{array}
|
---|
914 | \label{eq:intersection}
|
---|
915 | \end{equation}
|
---|
916 |
|
---|
917 | Thus the set of feasible \plucker points is defined by an intersection
|
---|
918 | of halfspaces defined by the \plucker hyperplanes corresponding to edges of the
|
---|
919 | polygon. The set of {\em stabbers} ${\cal S}_P$ is then defined as an
|
---|
920 | intersection of ${\cal F}_P$ with the \plucker quadric:
|
---|
921 |
|
---|
922 | \begin{equation}
|
---|
923 | {\cal S}_P = \{ \ppoint | \ppoint \in {\cal F}_P, \bpi \odot \bpi = 0 \}.
|
---|
924 | \end{equation}
|
---|
925 |
|
---|
926 | The stabbers are \plucker points corresponding to the real lines
|
---|
927 | intersecting the polygon that are oriented in the direction of the
|
---|
928 | normal. Similarly we can define the sets of {\em reverse feasible
|
---|
929 | \plucker points} ${\cal F}^-_P$ and {\em reverse stabbers} ${\cal
|
---|
930 | S}^-_P$ that correspond to opposite oriented lines intersecting the
|
---|
931 | polygon:
|
---|
932 |
|
---|
933 | \begin{equation}
|
---|
934 | \begin{array}{ll}
|
---|
935 | {\cal F}^-_P & = \{ \ppoint | \ppoint \in {\cal P}^5, \ppoint \in \pplane^+_{e_i}, \forall i \in \langle 0,n) \} \\
|
---|
936 | {\cal S}^-_P & = \{ \ppoint | \ppoint \in {\cal F}^-_P, \bpi \odot \bpi = 0 \}.
|
---|
937 | \end{array}
|
---|
938 | \end{equation}
|
---|
939 |
|
---|
940 |
|
---|
941 |
|
---|
942 |
|
---|
943 | \section{Lines between two polygons}
|
---|
944 | \label{sec:rot3d_twopoly}
|
---|
945 |
|
---|
946 | The above presented definitions of elementary line sets allow to
|
---|
947 | handle visibility computations by means of set operations on the sets
|
---|
948 | of feasible \plucker points. Visibility between two polygons $P_j$
|
---|
949 | and $P_k$ can be determined by constructing an intersection of
|
---|
950 | feasible sets of the two polygons ${\cal F}_{P_j}$ and ${\cal
|
---|
951 | F}_{P_k}$ and subtracting all feasible sets of polygons lying between
|
---|
952 | $P_j$ and $P_k$. To obtain the set of unoccluded stabbers we intersect
|
---|
953 | the resulting feasible set with the \plucker quadric.
|
---|
954 |
|
---|
955 | Further in this chapter we restrict our discussion to visibility from
|
---|
956 | a given {\em source polygon} $P_S$. Given any {\em occluder polygon}
|
---|
957 | $P_j$ we first describe lines intersecting both $P_S$ and $P_j$. Lines
|
---|
958 | between $P_S$ and $P_j$ can be described by an intersection of their
|
---|
959 | feasible line sets:
|
---|
960 |
|
---|
961 | \begin{equation}
|
---|
962 | {\cal F}_{P_SP_j} = {\cal F}_{P_S} \cap {\cal F}_{P_j}
|
---|
963 | \end{equation}
|
---|
964 |
|
---|
965 | and thus
|
---|
966 |
|
---|
967 | \begin{equation}
|
---|
968 | {\cal S}_{P_SP_j} = {\cal S}_{P_S} \cap {\cal S}_{P_j}.
|
---|
969 | \end{equation}
|
---|
970 |
|
---|
971 | The feasible \plucker points are defined by an intersection of
|
---|
972 | halfspaces corresponding to edges of $P_S$ and $P_j$. These halfspaces
|
---|
973 | define a {\em blocker polyhedron} $B_{P_SP_j}$ that is described in
|
---|
974 | the next section.
|
---|
975 |
|
---|
976 |
|
---|
977 | \subsubsection{Blocker polyhedron}
|
---|
978 |
|
---|
979 | The blocker polyhedron describes lines intersecting the source
|
---|
980 | polygon and the given occluder. The blocker polyhedron can be seen
|
---|
981 | as an extension of the blocker polygon discussed in
|
---|
982 | Chapters~\ref{chap:rot2d} and~\ref{chap:rot3d} for the from-region
|
---|
983 | visibility in 3D scenes. The blocker polyhedron is a 5D polyhedron in
|
---|
984 | a 5D projective space. To avoid singularities in the projection from
|
---|
985 | ${\cal P}^5$ to ${\cal R}^5$ the polyhedron can be embedded in ${\cal
|
---|
986 | R}^6$ similarly to the embedding of blocker polygon in ${\cal R}^3$
|
---|
987 | (see Section~\ref{sec:blocker_polygon}). Then the polyhedron actually
|
---|
988 | represents a 6D pyramid with an apex at the origin of ${\cal R}^6$.
|
---|
989 |
|
---|
990 |
|
---|
991 | \subsubsection{Cap planes}
|
---|
992 |
|
---|
993 | The blocker polyhedron is defined by an intersection of halfspaces
|
---|
994 | defined by \plucker planes that are mappings of edges of the source
|
---|
995 | polygon and the occluder. As stated above the blocker polyhedron
|
---|
996 | represents the set of feasible \plucker points ${\cal F}_{P_SP_j}$
|
---|
997 | including points not intersecting the \plucker quadric that correspond
|
---|
998 | to imaginary lines. We bound the polyhedron by {\em cap planes}
|
---|
999 | aligned with the \plucker quadric so that the resulting polyhedron is
|
---|
1000 | a tighter representation of the stabbers ${\cal S}_{P_SP_j}$. We need
|
---|
1001 | to ensure that the resulting polyhedron fully contains the stabbers
|
---|
1002 | ${\cal S}_{P_SP_j}$, i.e. contains the cross-section of the \plucker
|
---|
1003 | quadric and ${\cal F}_{P_SP_j}$.
|
---|
1004 |
|
---|
1005 | The cap planes provide the following benefits:
|
---|
1006 |
|
---|
1007 | \begin{itemize}
|
---|
1008 | \item The computation is localized to the proximity of the \plucker
|
---|
1009 | quadric. This reduces the combinatorial complexity of data structure
|
---|
1010 | representing an arrangement of the blocker polyhedra.
|
---|
1011 |
|
---|
1012 | \item The blocker polyhedron is always bounded. Although the set of
|
---|
1013 | lines between two convex polygons is bounded, the set of feasible
|
---|
1014 | \plucker points can be unbounded at the ``direction'' of imaginary
|
---|
1015 | lines. Adding the cap planes we make sure that the polyhedron is
|
---|
1016 | bounded, which allows its easier treatment. By using the cap planes
|
---|
1017 | we avoid the handling of very oblong, almost unbounded polyhedra,
|
---|
1018 | which improves numerical stability of a floating point
|
---|
1019 | implementation of the algorithm.
|
---|
1020 | \end{itemize}
|
---|
1021 |
|
---|
1022 |
|
---|
1023 | We used two cap planes to bound the polyhedron, one for each side of
|
---|
1024 | the \plucker quadric (a side is given by the sign of $\bpi \odot
|
---|
1025 | \bpi$). The cap planes are computed as tangents to the \plucker
|
---|
1026 | quadric at the center of the set of stabbers ${\cal S}_{P_SP_j}$. The
|
---|
1027 | planes are translated each at the opposite direction making sure that
|
---|
1028 | they include the whole set ${\cal S}_{P_SP_j}$.
|
---|
1029 |
|
---|
1030 |
|
---|
1031 |
|
---|
1032 | \subsection{Intersection with the \plucker quadric}
|
---|
1033 | \label{sec:stabbers}
|
---|
1034 |
|
---|
1035 | Given a blocker polyhedron representing the set of feasible lines
|
---|
1036 | ${\cal F}_{P_SP_j}$ we can compute an intersection of the edges of the
|
---|
1037 | polyhedron with the \plucker quadric to determine the set of extremal
|
---|
1038 | lines bounding the set of stabbers ${\cal S}_{P_SP_j}$. An
|
---|
1039 | intersection of an edge of the blocker polyhedron with the \plucker
|
---|
1040 | quadric results in at most two {\em extremal \plucker points} that
|
---|
1041 | correspond extremal lines\footnote{Neglecting the case that the whole
|
---|
1042 | edge is embedded in the \plucker quadric, which results in infinite
|
---|
1043 | number of extremal lines.}. Given an edge of the blocker polyhedron
|
---|
1044 | the intersection with the \plucker quadric is computed by solving the
|
---|
1045 | quadratic equation (Eq.~\ref{eq:plucker_quadric}). A robust algorithm
|
---|
1046 | for computing this intersection was developed by
|
---|
1047 | Teller~\cite{TH83}.
|
---|
1048 |
|
---|
1049 |
|
---|
1050 | Intersecting all edges of the blocker polyhedron with the \plucker
|
---|
1051 | quadric yields all extremal lines of ${\cal
|
---|
1052 | S}_{P_SP_j}$~\cite{Teller:1992:CAA,Pu98-DSGIV}. See
|
---|
1053 | Figure~\ref{fig:rot3_visrays} for an example of extremal lines
|
---|
1054 | computed for the given source polygon and a set of three occluders.
|
---|
1055 |
|
---|
1056 |
|
---|
1057 | \begin{figure}[htb]
|
---|
1058 | \centerline{
|
---|
1059 | \includegraphics[width=0.5\textwidth,draft=\DRAFTIMAGES]{images/rot3_visrays}}
|
---|
1060 | \caption{Extremal lines for the given source polygon (yellow) and three occluders.}
|
---|
1061 | \label{fig:rot3_visrays}
|
---|
1062 | \end{figure}
|
---|
1063 |
|
---|
1064 | The intersection of the 2D faces of the blocker polyhedron with the
|
---|
1065 | \plucker quadric yields swaths of event surfaces of the set of
|
---|
1066 | stabbers ${\cal S}_{P_SP_j}$~\cite{Teller92phd}. In general the
|
---|
1067 | intersection results in 1D conics.
|
---|
1068 |
|
---|
1069 | We can avoid the explicit treatment of conics in 5D by computing the
|
---|
1070 | local topology of the edges of the blocker polyhedron and constructing
|
---|
1071 | the swaths in primal space between the topologically connected
|
---|
1072 | extremal lines~\cite{Teller92phd}. The local topology of an extremal
|
---|
1073 | \plucker point is given by connections with extremal \plucker points
|
---|
1074 | embedded in the same 2D face of the blocker polyhedron. A 2D face of
|
---|
1075 | the blocker polyhedron is given by three \plucker hyperplanes. Thus
|
---|
1076 | the pairs of extremal \plucker points defined by the subset of the
|
---|
1077 | same three \plucker hyperplanes define a swath.
|
---|
1078 |
|
---|
1079 |
|
---|
1080 |
|
---|
1081 | For solution of some from-region visibility problems (e.g. PVS
|
---|
1082 | computation, region-to-region visibility) the event swaths need not be
|
---|
1083 | reconstructed. For example the visibility culling algorithm that will
|
---|
1084 | be discussed in Section~\ref{sec:rot3pvs} only computes extremal
|
---|
1085 | \plucker points and uses them to test an existence of a set of
|
---|
1086 | stabbers of a given size.
|
---|
1087 |
|
---|
1088 |
|
---|
1089 | \subsection{Size of the set of lines}
|
---|
1090 |
|
---|
1091 | \label{sec:size_measure}
|
---|
1092 |
|
---|
1093 | Computing a size measure of a given set of lines is useful for most
|
---|
1094 | visibility algorithms. The computed size measure can be used to drive
|
---|
1095 | the subdivision of the given set of lines or to bound the maximal
|
---|
1096 | error of the algorithm. An analytic algorithm can use the computed
|
---|
1097 | size measure for thresholding by a given $\epsilon$-size to discard
|
---|
1098 | very small line sets. A discrete algorithm can use the size measure
|
---|
1099 | to determine the required density of sampling.
|
---|
1100 |
|
---|
1101 | The size of a set of lines for the from-point visibility can be
|
---|
1102 | formulated easily: the size is given by the area of the intersection
|
---|
1103 | of the line set with a plane. This corresponds to quantifying
|
---|
1104 | visibility of an object according to its projected area. Such a size
|
---|
1105 | is determined in the solution space (viewport). Alternatively we could
|
---|
1106 | use a ``viewport independent measure'' given by a solid angle formed by
|
---|
1107 | the visible part of an object. The size measure for the from-region
|
---|
1108 | visibility problems is more complicated for the following reasons:
|
---|
1109 |
|
---|
1110 | \begin{itemize}
|
---|
1111 | \item The domain of the solution space is four-dimensional.
|
---|
1112 | \item The solution space of the from-region visibility algorithm
|
---|
1113 | generally does not correspond to the solution space of the
|
---|
1114 | application. For example, a visible surface algorithm using a
|
---|
1115 | precomputed PVS works in a 2D domain induced by the given viewport.
|
---|
1116 | \end{itemize}
|
---|
1117 |
|
---|
1118 |
|
---|
1119 | \subsubsection{General size measure}
|
---|
1120 |
|
---|
1121 | A size of a set of lines for the from-region visibility can be
|
---|
1122 | computed by evaluating a 4D integral. Using \plucker coordinates we
|
---|
1123 | can compute a volume of the 4D hyper-surface corresponding to the
|
---|
1124 | given set of lines. The volume however depends on a way of projecting
|
---|
1125 | the blocker polyhedron from ${\cal P}^5$ to ${\cal R}^5$. This
|
---|
1126 | projection has a similar role as the selection of the viewport for the
|
---|
1127 | from-point visibility problem. We can project the blocker polyhedron
|
---|
1128 | from ${\cal P}^5$ to ${\cal R}^5$ by projecting it to a 5D hyperplane
|
---|
1129 | defined by certain reference direction, e.g. the ``center-line'' of
|
---|
1130 | the given set of lines. Pu proposed a different size measure based on
|
---|
1131 | measuring the {\em angular spread} and the {\em distance} between
|
---|
1132 | lines~\cite{Pu98-DSGIV}. Both these quantities can be evaluated in
|
---|
1133 | terms of \plucker coordinates of the set of extremal lines of the
|
---|
1134 | given line set.
|
---|
1135 |
|
---|
1136 |
|
---|
1137 | \subsubsection{Size measure for the PVS computation}
|
---|
1138 |
|
---|
1139 | It can be difficult to relate the size measures described above to
|
---|
1140 | the domain of the result of a subsequently applied visibility
|
---|
1141 | algorithm. We need a simple scheme that fits to the context of the
|
---|
1142 | target application. In this section we suggest a size measure
|
---|
1143 | designed for the PVS computation. When computing a PVS we are
|
---|
1144 | interested in measuring the size of the set of unoccluded lines
|
---|
1145 | (stabbers) between the source polygon $P_S$ and a given scene
|
---|
1146 | polygon. If this size is below an $\epsilon$-threshold, we can
|
---|
1147 | possibly exclude the polygon from the PVS. We suggest to use an
|
---|
1148 | estimate of the minimal angle between the stabbers at a point inside
|
---|
1149 | $P_S$. The idea is to estimate the minimal projected diameter of a
|
---|
1150 | polygon visible through the given set of lines from any point inside
|
---|
1151 | $P_S$. This estimate can be used to bound a maximal error of an image
|
---|
1152 | synthesized with respect to any viewpoint inside $P_S$ for the case that
|
---|
1153 | the corresponding set of lines is neglected.
|
---|
1154 |
|
---|
1155 | %% The size measure approximates the minimal spatial angle given by a
|
---|
1156 | %% cross-section of the given set of lines parallel to the source polygon
|
---|
1157 | %% $P_S$ and the center of $P_S$.
|
---|
1158 |
|
---|
1159 | Given a blocker polyhedron ${\cal F}_{P_SP_j}$ the proposed size
|
---|
1160 | measure can be evaluated as follows:
|
---|
1161 |
|
---|
1162 | \begin{enumerate}
|
---|
1163 |
|
---|
1164 | \item
|
---|
1165 | Compute the extremal lines of the corresponding set of stabbers ${\cal
|
---|
1166 | S}_{P_SP_j}$ as described in Section~\ref{sec:stabbers}.
|
---|
1167 |
|
---|
1168 | \item For each polygon edge $e_i$ bounding the stabbers
|
---|
1169 | determine an extremal line $l_{mi}$ with a maximal distance from the
|
---|
1170 | edge.
|
---|
1171 |
|
---|
1172 | \item For each edge $e_i$ compute a shortest line segment $z_i$
|
---|
1173 | connecting $e_i$ and $l_{mi}$. The length of this line segment is
|
---|
1174 | then scaled according to its distance from the source polygon,
|
---|
1175 | i.e. we compute an angle $\alpha_i$ between the lines connecting the
|
---|
1176 | center of the source polygon and the endpoints of $z_i$.
|
---|
1177 |
|
---|
1178 | \item Select a minimal angle $\alpha_m$ of all $\alpha_i$ as the
|
---|
1179 | estimate of the size of the given line set.
|
---|
1180 |
|
---|
1181 | \end{enumerate}
|
---|
1182 |
|
---|
1183 | The evaluation of the size measure is depicted in
|
---|
1184 | Figure~\ref{fig:linesize}.
|
---|
1185 |
|
---|
1186 | \begin{figure}[htb]
|
---|
1187 | \centerline{
|
---|
1188 | \includegraphics[width=0.4\textwidth,draft=\DRAFTFIGS]{figs/linesize}}
|
---|
1189 | \caption{A 2D example of evaluation of the size of a set of lines. The three
|
---|
1190 | line segments
|
---|
1191 | $z_1$, $z_2$ and $z_3$ maximize the distance of the corresponding
|
---|
1192 | occluder edges from the extremal lines. The line segment $z_3$ spans
|
---|
1193 | a minimal angle $\alpha_m$ with respect to the center of the source
|
---|
1194 | polygon $P_S$.}
|
---|
1195 | \label{fig:linesize}
|
---|
1196 | \end{figure}
|
---|
1197 |
|
---|
1198 | The angle $\alpha_m$ can be related to the angular resolution of the
|
---|
1199 | synthesized image. Given the resolution of the image we can threshold
|
---|
1200 | ``small'' line sets with $\alpha_m$ below the corresponding angular
|
---|
1201 | threshold to achieve a sub-pixel precision of the rendering algorithm.
|
---|
1202 | This measure can also be applied to deal with the finite precision of
|
---|
1203 | the floating point arithmetics by using a small $\epsilon$-threshold
|
---|
1204 | to handle numerical inaccuracies.
|
---|
1205 |
|
---|