More info

Friday, 7 March 2014

Computer Graphics Notes - Lab 25 - SUTHERLAND AND COHEN SUBDIVISION LINE CLIPPING ALGORITHM

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 P1 (x1, y1) and P2 (x2, y2).
2.     Read two corners (left-top and right-bottom) of the window, say (Wx1, Wy1 and Wx2, Wy2).
3.     Assign the region codes for two endpoints P1 and P2 using following steps:
Initialize code with bits 0000
Set Bit 1-if (x < Wx1)
Set Bit 2-if (x > Wx2)
Set Bit 3-if (x < Wy2)
Set Bit 4-if (x > Wy1)


4.     Check for visibility of line P1 P2 using following steps:      
a)     If region codes for both endpoints P1 and P2 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. (P1 P2)
a)     If region codes for both the end points are non-zero, find intersection points P1' and P2' with boundary edges of clipping window with respect to point P1 and P2, respectively.
b)     If region codes for any one end point is non-zero then find intersection points P1' or P2' 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.


Computer Graphics Notes - Lab 25 - 2D CLIPPING

INTRODUCTION

The procedure that identifies the portions of a picture that are either inside or outside of a specified region of space is referred to as clipping. The region against which an object is to be clipped is called a clip window or clipping window. It is in a rectangular in shape.

The clipping algorithm determines which points, lines or portions of lines lay within the clipping window. These points, lines or portions of lines are retained for display. All others are discarded. We will consider algorithms for clipping the following primitive types
•    Point Clipping
•    Line Clipping
•    Polygon Clipping

POINT CLIPPING

Assuming that the clip window is a rectangle in standard position, we save a point P = (x, y) for display if the following inequalities are satisfied:
XWmin ≤ X ≤ XWmax
ywmin ≤ y ≤ ywmax
where the edge of the clip window (xwmin , xwmax, ywmin , ywmax) can be either the world-coordinate window boundaries or viewport boundaries. If any one of these four inequalities is not satisfied, the point is clipped (not saved for display).

Although point clipping is applied less often than line or polygon clipping, some application may require a point-clipping procedure.

Point Clipping

 LINE CLIPPING

The lines are said to be interior to the clipping window and hence visible if both end points are interior to the window, e.g., line psp4 in the figure. However, if both end points of a line are exterior to the window, the line is not necessarily completely exterior to the window, e.g., line p7p8 in the figure. If both end points of a line are completely to the right of, completely to the left of, completely above, or completely below the window, then the line is completely exterior to the window and hence invisible, e.g., line p1p2 and p9p10 in the figure.
Line Clipping
Find the part of a line inside the clip window

The lines which across one or more clipping boundaries require calculation of multiple intersection points to decide the visible portion of them. To minimize the intersection calculations and to increase the efficiency of the clipping algorithm, initially, completely visible and invisible lines are identified and then intersection points are calculated for remaining lines.

Line Clipping
Find the part of a line inside the clip window