Graphics Reference
In-Depth Information
x
0
= 1 if and only if
P
lies strictly to the right of the right boundary line.
x
1
= 1 if and only if
P
lies strictly above the top boundary line.
x
2
= 1 if and only if
P
lies strictly to the left of the left boundary line.
x
3
= 1 if and only if
P
lies strictly below the bottom boundary line.
The algorithm now has three steps:
Step 1.
Encode
P
1
and
P
2
. Let c
1
= c(
P
1
) and c
2
= c(
P
2
).
Step 2.
Check if the segment can be trivially rejected, that is, using the bitwise
logical
or
and
and
operators, test whether
(a) c
1
or
c
2
= 0, or
(b) c
1
and
c
2
π 0.
In case (a), the segment is entirely contained in the window since both end-
points are and the window is convex. Return
Q
1
=
P
1
and
Q
2
=
P
2
.
In case (b), the segment is entirely outside the window. This follows because
the endpoints will then lie in the halfplane determined by a boundary line
that is on the other side from the window and halfplanes are also convex.
Return the empty segment.
Step 3.
If the segment cannot be trivially rejected, then we must subdivide the
segment. We clip it against an appropriate boundary line and then start over
with Step 1 using the new segment. Do the following to accomplish this:
(a) First find the endpoint
P
that will determine the line to clip against.
If c
1
= 0000, then
P
1
does not have to be clipped and we let
P
be
P
2
and
Q
be
P
1
.
If c
1
π 0000, then let
P
be
P
1
and
Q
be
P
2
.
(b) The line to clip against is determined by the left-most nonzero bit in
c(
P
). For the example in Figure 3.3,
P
=
P
1
,
Q
=
P
2
, and the line to clip
against is the left boundary line of the window. Let
A
be the intersec-
tion of the segment [
P
,
Q
] with this line.
(c) Repeat Steps 1-3 for the segment [
A
,
Q
].
The algorithm will eventually exit in Step 2.
With respect to the efficiency of the Cohen-Sutherland algorithm, note that the
encoding is easy since it simply involves comparing a number to some constant (the
Figure 3.3.
Cohen-Sutherland line-clipping example.
