CS-460/560, Week 8-C
Spring, 1998
R. Eckert


Given the endpoint coordinates (x1,y1) and (x2,y2) of a line, determine
what part of that line lies inside the rectangular clip area whose
lefthand border is x=xmin, righthand border x=xmax, bottom border y=ymin,
and top border y=ymax.

Could do point test for all points on the line--i.e., for a point x,y:

   if ((x<=xmax) && (x>=xmin) && (y<=ymax) && (y>=ymin))
       the point x,y lies inside the clip area

Too much work!

We want a simple test involving the line's endpoint coordinates.

Observation-- All lines fall into one of three categories

   1. Both endpoints inside rectangle (Trivially accept entire line)

   2. Both endpoints outside rectangle on the same side of one of its
      borders (Trivially reject entire line)

   3. Neither 1 or 2 ==> chop off the part of the line outside one of
      borders (which gives a new endpoint) and see if the resulting
      line has been reduced to Category 1 or Category 2.

A tool to use in assigning lines to Category 1 or 2: a 4-bit region code
(RC) that can be assigned to an endpoint (x,y) . Any set bit means the
endpoint is outside of one of the 4 borders of the clip rectangle--

   RC = LRBA,   L=left   (if x<xmin, L=1, else L=0)
                R=Right  (if x>xmax, R=1, else R=0)
                B=Bottom (if y<ymin, B=1, else B=0)
                T=Top    (if y>ymax, T=1, else B=0)

The entire x-y plane can be divided into 9 regions, depending on the
value of the Region Code:

            |      |
      1001  | 0001 |  0101
            |      |
            |      |
      1000  | 0000 |  0100
            |      |
            |      |
      1010  | 0010 |  0110
            |      |

Points inside the clip region have a region code of 0000. Assume that the
region codes for the two endpoints of a line are RC1 and RC2. A bitwise
OR of RC1 with RC2 will give zero only if all bits of both are zero:

       if (RC1 OR RC2 == 0)
          both RCs are 0000, and both endpoints are inside
          ==> Category 1 (trivial accept)

If both endpoints are outside the SAME border of the clip region
(Category 2 line), then both endpoint region codes will have the SAME bit
set in one of the four bit positions. A bitwise AND of RC1 with RC2 will
give a nonzero result if that is the case:

       if (RC1 AND RC2 != 0)
          Both endpoints are outside of the same border
          ==> Category 2 (trivial reject)

What about category 3 lines?

First observe that Category 3 lines may have both endpoints (P1 and P2)
outside different borders of the clip region. In that case it is not
important which end of the line is chopped off first. But if we have a
case where one endpoint is inside and the other is outside, we want to
chop off the end that is outside. To simplify things, we'll always assume
that it is endpoint P1 which is the one that is the outside point. (If
that is not the case, P1 and P2 will be swapped.)

How do we do the chopping? (i.e., how do we determine the new endpoint?)
Assume we have the slope (m) and intercept (b) of the line (which can be
computed from the original endpoint coordinates).

Look the region code of point P1 for each of four possible cases:

If RC == 1xxx (P1 is to the left of xmin)
    The new endpoint should be on the left boundary:
                                   x1 <---xmin
                                   y1 <---m*xmin + b
                                   Reset the RC's L bit

if RC == x1xx (P1 is to the right of xmax)
    The new endpoint should be on the right boundary:
                                   x1 <---xmax
                                   y1 <---m*xmax + b
                                   Reset the RC's R bit

if RC == xx1x (P1 is to the below of ymin)
    The new endpoint should be on the bottom boundary:
                                   y1 <---ymin
                                   x1 <---(ymin-b)/m
                                   Reset the RC's B bit

if RC == xx1x (P1 is to the below of ymin)
    The new endpoint should be on the top boundary:
                                   y1 <---ymax
                                   x1 <---(ymax-b)/m
                                   Reset the RC's T bit


Input: Original endpoints (x1,y1,x2,y2)
       Clip region boundaries (xmin,ymin,xmax,ymax)

Output: Accept Code (AC==TRUE ==> Some part of the line was inside
                     AC==FALSE ==> no part of the line was inside)
        Clipped Line endpoints (x1,y1,x2,y2) [if AC == TRUE]


   Calculate m and b from x1,y1,x2,y2
   done = FALSE
   While (NOT done)
      Calculate endpoint codes rc1, rc2
      If ((rc1 OR rc2) == 0)      // Category 1, Trivial Accept
         done = TRUE
         AC = TRUE
         If ((rc1 AND rc2) != 0)  // Category 2, Trivial Reject
            done = TRUE
            AC = FALSE
            If (P1 is inside)
               Swap x1,x2, y1,y2, and rc1,rc2
            If (L-bit of rc1 is set)          // 1xxx
               x1 = xmin
               y1 = m*x1 + b
               If (R-bit of rc1 is set)       // x1xx
                  x1 = xmax
                  y1 = m*x1 + b
                  If (B-bit of rc1 is set)    // xx1x
                     y1 = ymin
                     x1 = (y1-b)/m
                  Else                        // xxx1
                     y1 = ymax
                     x1 = (y1-b)/m