A Line Clipping Algorithm in computer graphics

Look at the following set of lines. The rectangle indicates the screen in which they are to be displayed

A Line Clipping Algorithm
A Line Clipping Algorithm

How to decide which of the lines, or more precisely which part of every line is to be displayed. The concept is simple. Since we know the coordinates of the screen,

i) Any line whose end points lie within the screen coordinate limits will have to display fully (because we cannot have a straight line whose end points are within the screen and any other middle point in outside).

ii) Any line whose end points lie totally outside the screen coordinates will have to examined to see if any intermediate point is inside the screen boundary.

iii) Any line whose one end point lies inside the boundary will have to be identified

In case of (ii) and (iii), we should decide up to what point, the line segment can be displayed. Simply finding the intersection of the line with the screen boundary can do this.

Though on paper the concept appears simple, the actual implementation poses sufficient problems. We now see how to find out whether the respective end points lie inside the screen or not. The subsequent sections will inform us about how to go about getting the intersection points

The Four bit code
The Four bit code

Look at the above division of region. Each region is given a code of 4 bits. They are assigned to their values based on the following criterion

First bit: will be 1 if the point is to the left of the left edge of the screen. (LSB)

Second bit: 1 if the point is to the right of the right edge. Third bit: is 1 if the point is below the bottom edge and Fourth bit: is 1 if the point is to the top of the top edge. (MSB)

The conditions can be checked by simply comparing the screen coordinate values with the coordinates of the endpoints of the line

If for a line, both end points have the bit pattern of 0000, the line can be displayed as it is (trivially).

Otherwise, the pattern of 1’s will indicate as to with respect to which particular edge the intersection of the line is to be verified

For example if one of the points of a straight line shows 1000, then it’s interring section w.r.t. to the top edge needs to be computed (since the point is above the top edge). If for the same line, the other point returns 0010, then since a segment of the line a beyond the right edge, the intersection with the right edge is to be computed.

Algorithm mid point subdivision

Check whether the line P1 P2 can be trivially included. i.e. when both P1 and P2 are visible. If so exit. Else

Check the point P1, which is visible, and the other point P2, which is invisible.

Divide the segment P1 P2 at P1 1 check if P1 1 is visible if so, the farthest point is beyond P11, so proceed by dividing P11 P2 else divide the segment P1 P11

Repeat step (3) until the segment to be divided reduces to a single point. The segment to be displayed is bound by P1 and this point

Leave a Comment