Graphics Reference
In-Depth Information
Figure 3.12.
Different types of turning
points.
Assume that [
P
1
,
P
2
] is an edge of a polygon. It is easy to see that the only time that
this edge is relevant to the issue of turning points is if it enters or exits a corner region
associated to the window. Figure 3.12 shows some cases of polygons (the shaded
regions) and how the exiting edge [
P
1
,
P
2
] affects whether or not the corner
C
becomes
a turning point and needs to be added to the output. One sees the following:
(1) The analysis divides into two cases: whether the polygon is to the right or left
of the edge. (Figure 3.12(a,b) versus Figure 3.12(c,d))
(2) There are two subcases that depend on which side of the ray from
P
2
to
C
the
segment [
P
2
,
P
3
] is located.
(3) The decision as to whether a turning point will be needed cannot be made on
the basis of only a few edges. In principle one might have to look at all the
edges of the polygon first.
It is observation (3) that complicates life for polygon-clipping algorithms that process
edges sequentially in one pass. One could simplify life and generate a turning point
whenever
we run into an edge that enters, lies in, or exits a corner region. The
problem with this approach is that one will generate bogus edges for our clipped
polygon. The polygon in Figure 3.12(c) would generate the “dangling” edge [
B
,
C
].
Bogus edges were already encountered in Sutherland-Hodgman clipping (but for dif-
ferent reasons). These edges might not cause any problems, as in the case where one
is simply filling two-dimensional regions. On the other hand, one would like to min-
imize the number of such edges, but avoiding them entirely would be very compli-
cated with some algorithms like the Liang-Barsky and Maillot algorithm.
With this introduction, let us describe the Liang-Barsky algorithm. We shall be
brief because it does not contain much in the way of new insights given the fact that
