Clipping - Computer Graphics and Geometric Modeling - page 72

boundary lines of the window are assumed to be horizontal and vertical). Step 3 is
where the real work might have to be done. We shall have to clip four times in the
worst case. One such worst case is shown in Figure 3.3 where we end up having to
clip successively against each one of the window boundary lines generating the inter-
section points A , B , C , and D .
Algorithm 3.2.1.1 is an implementation of the just-described algorithm. To be
more efficient, all function calls should be replaced by inline code.
Finally, note that the encoding found in the Cohen-Sutherland line-clipping algo-
rithm is driven by determining whether a point belongs to a halfplane. One can easily
generalize this to the case where one is clipping a segment against an arbitrary convex
set X . Assume that X is the intersection of halfplanes H 1 , H 2 ,..., H k . The encoding
of a point P is now a k-bit number c( P ) = X K X K-1 ...X 1 , where

X i is 1 if P lies in H i and 0 otherwise.

Using this encoding one can define a clipping algorithm that consists of essentially
the same steps as those in the Cohen-Sutherland algorithm. One can also extend
this idea to higher dimensions and use it to clip segments against cubes. See
Section 4.6.

3.2.2 Cyrus-Beck Line Clipping

The Cyrus-Beck line-clipping algorithm ([CyrB78]) clips a segment S against an arbi-
trary convex polygon X . Let S = [ P 1 , P 2 ] and X = Q 1 Q 2 ... Q k . Since X is convex, it is
the intersection of halfplanes determined by its edges. More precisely, for each
segment [ Q i , Q i+1 ], i = 1,2,...,k, ( Q k+1 denotes the point Q 1 ) we can choose a normal
vector N i , so that X can be expressed in the form

k

I

XH = ,

i

i = 1

where H i is the halfplane

{

( ) ≥

}

HQNQQ = • - 0 .

i i i

With this choice, the normals will point “into” the polygon. It follows that

k

I

( )

SX «= SH « .

i

i = 1

In other words, we can clip the segment S against X by successively clipping it
against the halfplanes H i . This is the first basic idea behind the Cyrus-Beck clipping
algorithm. The second, is to represent the line L determined by the segment S
parametrically in the form P 1 + t P 1 P 2 and to do the clipping with respect to the
parameter t.