Cohen-Sutherland line clipping

The Cohen-Sutherland algorithm clips a line against a rectangular window quickly, by first testing trivially for acceptance or rejection using 4-bit region codes.

Region codes

The plane is divided into 9 regions around the window; each end point gets a code of 4 bits T B R L:

 1001 | 1000 | 1010
 -----+------+-----
 0001 | 0000 | 0010      (middle = window)
 -----+------+-----
 0101 | 0100 | 0110

• bit 1 (L) = 1 if x < xmin; bit 2 (R) = 1 if x > xmax
• bit 3 (B) = 1 if y < ymin; bit 4 (T) = 1 if y > ymax

Algorithm

1. Find the region codes of P1 and P2.
2. If both codes are 0000: the line is completely inside, accept.
3. If (code1 AND code2) ≠ 0000: both end points are outside the same
   edge, completely outside, reject.
4. Otherwise (partly inside): 
   a. choose an end point with a non-zero code;
   b. find the intersection of the line with the window edge indicated
      by the first bit set (L, R, B, T order);
        x = xmin or xmax:  y = y1 + m(x − x1)
        y = ymin or ymax:  x = x1 + (y − y1)/m
   c. replace the end point by the intersection point, recompute its code;
   d. go to step 2.

Example

Window: xmin = 0, ymin = 0, xmax = 50, ymax = 50. Line P1(−20,20) to P2(60,80). Slope m = (80−20)/(60+20) = 0.75.

P1=(-20,20) code 0001; P2=(60,80) code 1010
Clip P1 against x = xmin = 0: new point (0,35)
P1=(0,35) code 0000; P2=(60,80) code 1010
Clip P2 against x = xmax = 50: new point (50,72.5)
P1=(0,35) code 0000; P2=(50,72.5) code 1000
Clip P2 against y = ymax = 50: new point (20,50)
P1=(0,35) code 0000; P2=(20,50) code 0000
Both codes 0000: accept

Codes: P1 = 0001 (left), P2 = 1010 (top and right). AND = 0000, so the line is partly visible and needs clipping. After the clipping steps above, the visible part is from (0,35) to (20,50).

Answer: clipped line (0,35) to (20,50). A line such as (10,10)-(40,40) (both codes 0000) is accepted directly, and (60,10)-(70,40) (both codes 0010, AND ≠ 0) is rejected directly.