Game Development Reference
In-Depth Information
its polygon against the planes bounding the current view frustum. Clipping a pol-
ygon against a plane removes the portion of the polygon lying on the negative
side of the plane, resulting in a new polygon whose interior lies completely on
the positive side of the plane. Clipping a polygon against every plane of the cur-
rent view frustum effectively chops off any part lying outside the volume of
space that is visible to the camera.
V V
and connect to form a convex polygon. When we clip this polygon against a
plane L , we produce a new convex polygon having at most
,
,
,
Suppose we need to clip a portal whose vertices lie at the points
12
n
vertices. We
begin the clipping process by classifying all of the vertices into three categories:
those lying on the positive side of L , those lying on the negative side of L , and
those considered to be lying in the plane L itself. A vertex
n
+
1
V is classified as ly-
ing in the plane if its dot product with L satisfies
ε
<⋅ ≤
LV
0
(8.52)
i
for some small constant ε (typically,
). This prevents problems associat-
ed with round-off error that would otherwise wreak havoc on our visibility tests
by destroying the convexity of the view frustum. If no vertices lie on the positive
side of the plane L , then the portal is not visible, and we do not render anything
in the zone to which it connects. If no vertices lie on the negative side of the
plane L , then no clipping is necessary. Otherwise, we visit every pair of neigh-
boring vertices, looking for edges having one positive vertex and one negative
vertex. As shown in Figure 8.15, new vertices are added to the polygon where
edges intersect the clipping plane, and vertices lying on the negative side of the
plane are removed. Vertices lying on the positive side of the clipping plane or
lying in the clipping plane itself are not affected.
0.001
ε
Suppose that the vertex
V lies on the positive side of the clipping plane L ,
and that the vertex
V
lies on the negative side of L , or equivalently,
i
+
1
L V
L V
>
0
i
i ε
.
(8.53)
+
1
A point W lying on the line segment connecting
V and
can be expressed as
V
i
+
1
()
(
)
WVVV ,
t
=+
t
(8.54)
i
i
+
1
i
where the parameter t satisfies 0
≤≤
t
1
. Solving for the value of t that yields
()
L W
t
=
0
, we have