CS-460/560, Week 8-C
Spring, 1998
R. Eckert
LINE CLIPPING: THE COHEN-SUTHERLAND LINE CLIPPING ALGORITHM
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
THE ALGORITHM--
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]
PSEUDO-CODE:
CS_LineClip(xmin,ymin,xmax,ymax,x1,y1,x2,y2,AC)
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
Else
If ((rc1 AND rc2) != 0) // Category 2, Trivial Reject
done = TRUE
AC = FALSE
Else
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
Else
If (R-bit of rc1 is set) // x1xx
x1 = xmax
y1 = m*x1 + b
Else
If (B-bit of rc1 is set) // xx1x
y1 = ymin
x1 = (y1-b)/m
Else // xxx1
y1 = ymax
x1 = (y1-b)/m