Graphics Reference
In-Depth Information
p
:=
p
0
; c
p
:= c(
p
);
for
i:=1
to
n+1
do
begin
q
:=
p
i
; c
q
:= c(
q
);
{ Clip the segment [
p
,
q
] as in Cohen-Sutherland algorithm }
DoCSClip ();
if
segment [
p
,
q
] is outside clipping region
then
TestForComplexCase;
DoBasicTurningPointTest ();
p
:=
q
; c
p
:= c
q
;
end
;
Algorithm 3.3.4.1.
Overview of Maillot polygon-clipping algorithm.
Figure 3.14.
A turning point case.
corners outside the window. One probably needs to add a turning point to the clipped
polygon in this case. See Figure 3.14. We said “probably” because if the current point
is considered in isolation (without looking at its predecessors), then to always auto-
matically add the point may cause us to add the same corner several times in a row.
See points
p
i
,
p
i+1
, and
p
i+2
in Figure 3.14. In the implementation of Maillot's algo-
rithm, we do not try to eliminate such redundancies. If this is not desired, then extra
code will have to be added to avoid it.
If all of a polygon's edges meet the window, then the basic turning point test is all
that is needed to clip it correctly. For polygons that have edges entirely
outside
the
clipping region, one needs to do more. Figure 3.15 shows all (up to symmetry) generic
cases that need to be handled in this more complex situation. The following termi-
nology is useful for the case of edges outside the clipping region.
Notation.
A point that lies in a region with code 0001, 0010, 0100, or 1000 will be
called a
1-bit point
. A point that lies in a region with code 0011, 0110, 1100, or 1001
