Sutherland-Cohen Line Clipping

Every line endpoint is assigned a 4 bit Region code. The appropriate bit is set depending on the location of the endpoint with respect to that window component as shown below:

Endpoint Left of window then set bit 1 Endpoint Right of window then set bit 2 Endpoint Below window then set bit 3 Endpoint Above window then set bit 4
Example: P1 -> 0001, P 2 -> 1000 P3 -> 0001, P4 -> 0100 P5 -> 0000, P6 -> 0010 P7 -> 0001, P8 -> 0001

Can determine the bit code by testing the endpoints with window as follows:

If x is less than Xwmin then set bit 1
If x is greater than Xwmax then set bit 2
If y is less than Ywmin then set bit 3
If y is greater than Ywmax then set bit 4

Note: can use 4 element Boolean matrix and set C[Left] = true / false (1/0). If both endpoints = 0000 (in window) then display line. If both endpoints have a bit set in same position (P7, P8) then the line is completely outside the window and is rejected.

So: can do logical AND of region codes and reject if result is 0000
Can do logical OR of region codes and accept if result = 0000

For the rest of the lines we must check for intersection with window. May still be outside, e.g. P3 - P4 in the above image. If point is to Left of window then compute intersection with Left window boundary. Do the same for Right, Bottom, and Top. Then recompute region code restest. So the algorithm is as follows:

1. Compute region code for endpoints
2. Check for trivial accept or reject
3. If step 2 unsuccessful then compute window intersections in order: Left, Right, Bottom, Top (only do 1)
4. Repeat steps 1, 2,3 until done.

Example

I. 1) P1 = 0001 2) no 3) P1 = P'1 P2 = 1000 II. 1) P'1= 0000 2) no 3) P2 = P' 2 P2 = 1000 III. 1) P'1 = 0000 2) Yes - accept & display P'2 = 0000

Look at how to compute the line intersections

for P'1: m = dy/dx = (y1 - y'1)/(x1 - x'1) P1(x1, y1)

P'1(x'1, y'1)

or y'1 = y1 + m( x'1 - x1)

but for Left boundary x'1 = Xwmin

for Right boundary x'1 = Xwmax

Similarly for Top / Bottom, e.g. P'3

x'3 = x3 + (y'3 - y3) / m

for Top y'3 = Ywmax for Bottom y'3 = Ywmin

Alternative method for computing window intersections Mid Point binary search:

HyperGraph Table of Contents.

HyperGraph Home page.