__SUTHERLAND AND COHEN SUBDIVISION LINE CLIPPING ALGORITHM__

This is one of the oldest and most popular line-clipping
algorithm developed by Dan Cohen and Ivan Sutherland. To speed up the
processing this algorithm performs initial tests that reduce the number of
intersections that must be calculated.tf his algorithm uses a four digit (bit)
code to indicate which of nine regions contain the end point of line. The four
bit codes are called region codes or
out codes. These codes identify the location of the point relative to the
boundaries of the clipping rectangle as shown as the figure below.

Each bit position in the region code is used to indicate
one of the four relative coordinate positions of the point with respect to the
clipping window: to the left, right, top or bottom. The rightmost bit is the
first bit and the bits are set to 1 based on the following scheme:

Set Bit 1 - if the end point is to the left of the window

Set Bit 2 - if the end point is to the right of the window

Set Bit 3 - if the end point is to the below of the window

Set Bit 4 - if the end point is to the above of the window Otherwise, the bit
is set to zero.

Once we have established
region codes for all end points, we can determine which lines are completely
inside the clipping window and which are closely outside. Any lines that are
completely inside the window boundaries have a region code of 0000 for end
points and we trivially accept these lines. Any lines that have 1 in the same
bit position in the region codes for each endpoint are completely outside the
clipping rectangle, and we trivially reject these lines. A method used to test
lines for total clipping is equivalent to the logical AND operator. If the
result of the logical AND operation with two end point codes is not 0000, the
line is completely outside the clipping region. The lines that cannot be
identified as completely inside or completely outside a clipping window by
these tests are checked for intersection with the window boundaries.

**SUTHERLAND AND COHEN SUBDIVISION LINE CLIPPING ALGORITHM**

Read
two end points of the line say P

_{1}(x_{1}, y_{1}) and P_{2}(x_{2}, y_{2}).
2. Read two corners (left-top and right-bottom)
of the window, say (Wx

_{1}, Wy_{1}and Wx_{2}, Wy_{2}).
3. Assign the region codes for two endpoints P

_{1}and P_{2}using following steps:
Initialize
code with bits 0000

Set
Bit 1-if (x < Wx

_{1})
Set
Bit 2-if (x > Wx

_{2})
Set
Bit 3-if (x < Wy

_{2})
Set
Bit 4-if (x > Wy

_{1})
4. Check for
visibility of line P

_{1}P_{2}using following steps:
a) If region codes for both endpoints P

_{1}and P_{2}are zero then the line is completely visible. Hence draw the line and go to step 9.
b) If region codes for endpoints are not zero
and the logical ANDing of them is also nonzero then the line is completely
invisible, so reject the line and go to step 9.

c) If region codes for two endpoints do not
satisfy the conditions in 4a) and 4b) the line is partially visible.

5. Determine the intersecting edge of the
clipping window by inspecting the region codes of two endpoints. (P

_{1}P_{2})
a) If region codes for both the end points are
non-zero, find intersection points P

_{1}' and P_{2}' with boundary edges of clipping window with respect to point P_{1}and P_{2}, respectively.
b) If region codes for any one end point is
non-zero then find intersection points P

_{1}' or P_{2}' with the boundary edge of the clipping window with respect to it.
6. Divide the line segments considering
intersection points.

7. Reject the line segment if any one end
point of it appears outsides the clipping window.

8. Draw the remaining line segments.

9. Stop.

## No comments:

## Post a Comment