Cohen Sutherland Algorithm
Objective: The line to be clipped against the window. This means clip the line segment which is not visible in the window.
Assumptions: x1,y1, and x2,y2 be the starting and endpoints of the line. Xmin, ymin and xmax,ymax be the starting and ending points of the window. As shown in the figure.
This algorithm converts the line into 4-bit region codes based on the logical steps given below.
S-1: Calculate the four-bit region code of the line.
Most Important: The bit starts from LEFT, so the leftmost bit will be the first bit.
– So the first bit will be based on the sign (Plus or Minus) of (y-ymax).
– Second Bit = will be based on sign (Plus or Minus) of (ymin-y).
– Third Bit = will be based on the sign of (x-xmax).
– Fourth Bit = will be based on the sign of (xmin-x).
Very Important:
– If the sign is plus (positive) then value of the bit would be 1.
– If the sign is minus (negative) then value of the bit would be 0.
S-2: Find the line category as per the following rules.
– Visible: The line is visible if four-bit region code is zero.
– Not Visible: The line is not visible if bit wise AND Product of code is not zero.
– Needs Clipping: The line would be clipped if bit wise AND Product of code is zero.
S-3: If the line is category =”Needs Clipping” , then we proceed with the following rule
– Find the point where the boundary line cuts the given line.
– If Bit-1 is 1 then the line cuts the y=ymax.
– If Bit-2 is 1 then the line y=ymin.
– If Bit-3 is 1 then the line x=xmax.
– If Bit-4 is 1 then the line x=xmin.
S-4: Intersection Points of line
– If Bit 1 is 1 then new intersection point would be y=ymax and x= x1+(ymax-y1)/m.
– If Bit 2 is 1 then new intersection point would be y=ymin and x=x1+(ymin-y1)/m.
– If Bit 3 is 1 then new intersection point would be x=xmax and y=y1+m*(xmax-x1)
– If Bit 4 is 1 then new intersection point would be x=xmin and y=y1+m*(xmin-x1)
S-5 : Repeat all the steps till the region code of the line is (0000)=> visible.
Let’s understand by an example:
Clip a line A (-1,5) and B (3,8) using the Cohen Sutherland algorithm with window coordinates (-3,1) and (2,6).
Here xmin =-3 and ymin=1 with xmax =1 and ymax=6 with x1=-1, y1=5 and x2=3, y2=8.
S-1: Find the region code of the line point x1=-1,y1=5 as follows
– Bit 1 = Sign of (y-ymax) = Sign of (5-6) = Negative, so bit 1 would be 0.
– Bit 2 = Sign of (ymin-y) = Sign of (1-6) = Negative, so bit 2 would be 0.
– Bit 3 = Sign of (x-xmax) = Sign of (-1-1) = Negative, so bit 3 would be 0.
– Bit 4 = Sign of (xmin-x) = Sign of (-3-(-1)) = Negative, so bit 4 would be 0.
Find the region code of the line point x2=3,y2=8 as follows.
– Bit 1 = Sign of (y-ymax) = Sign of (8-6) = Positive, so bit 1 would be 1.
– Bit 2 = Sign of (ymin-y) = Sign of (1-8) = Negative, so bit 2 would be 0.
– Bit 3 = Sign of (x-xmax) = Sign of (3-1) = Positive, so bit 3 would be 1.
– Bit 4 = Sign of (xmin-x) = Sign of (-3-3) = Negative, so bit 4 would be 0.
The (x1,y1) has the code (0000) and (x2,y2) has the code (1010). Remember the codes are written from left to right. Left is bit-1.
S-2: Which category this line belongs to: Find, does it require clipping?
– Logical AND of both the region codes are (0000) * (1010) = (0*1, 0*0 ,0*1,0*0) = (0000). Since the logical AND of codes is zero, so the line belongs to third category- Clipping category =>Computer would clip it.
S-3: The line “Needs Clipping” based on the calculation above.
S-4: Since Bit 1 is one therefore intersection point is y=ymax and x=x1+(y1-ymax)/m. => y=6 and x= -1+(6-5)/(3/4) => -1+4/3 => 1/3. So the intersection point would be (x=1/3,y=6).
S-5: Find the region code of newfound point, C(x=1/3 and y=6) =>(0000)
Since the starting point, A(-1,5) has (0000) and new Point C is also (0000) that means both endpoints are visible. The line does not need more clipping. The algorithm would stop here.