Graphics Reference
In-Depth Information
Figure 3.13.
Testing for turning points.
it is built on the approach they use in their line-clipping algorithm. Furthermore,
another algorithm, the Maillot algorithm, is better. Our discussion here will follow
[FVFH90], who have modified the algorithm so that it is easier to follow although it
has the potential disadvantage of creating more bogus edges.
Consider Figure 3.13. We extend the edges of our rectangular window to divide
the plane into nine regions. If we are at a point of the polygon that lies in one of the
four outside regions that meet the window in an edge, then the next edge of the
polygon can only meet the window in that edge. See Figure 3.13(a). On the other hand,
if the point is in one of the four corner regions, then the next edge could meet the
window in one of two possible edges. Without look-ahead, we really cannot tell
whether the adjacent corner of the window will become a turning point and will
have to be added to the output polygon. In such a situation we shall play it safe and
always include the corner point (even though this may create some of these unwanted
edges that we have been talking about). This is the first point to make about the
algorithm.
The other point is that the algorithm rests on the idea of entry and exit points for
the edges of the polygon that correspond to the entry and exit values used in the line-
clipping algorithm described in Section 3.2.3. By analyzing these points one can tell
if an edge intersects the window or if it gives rise to a turning point. As we work our
way through the edges of the polygon, assume that the current edge
e
= [
p
i
,
p
i+1
] is
neither vertical nor horizontal. Then
e
will intersect all the boundary lines of our
window. If we parameterize the line containing
e
in the form
p
i
+ t
p
i
p
i+1
, then the four
intersection points correspond to four parameter values and can again be classified
as two entry and two exit points. We shall denote these associated parameter values
by t_in1, t_in2, t_out1, and t_out2, respectively. It is easy to see that the smallest of
these is an entry value and we shall let t_in1 be that one. The largest is an exit value
and we shall let t_out2 be that one. Nothing can be said about the relative size of the
remaining two values in general. From Section 3.2.3 we know, however, that if t_in2
< t_out1, then the line intersects the window and if t_out2 < t_in1, then the line inter-
sects a corner region.
If a line does not intersect the window, then it must intersect three corner regions.
The conditions for that are that 0 < t_out1 £ 1 and 0 < t_out2 £ 1. The last statement
also holds if the line intersects the window. Putting all these facts together leads to
Algorithm 3.3.3.1. However, we were assuming in the discussion that edges were
neither horizontal nor vertical. We could deal with such lines by means of special
cases, but the easiest way to deal with them and preserve the structure of Algorithm
3.3.3.1 is to use a trick and assign dummy ±• values to the missing entering and
leaving parameters. See [FVFH90].
