9 Line Clipping

T. Raghuveera

Objectives:

Understand Cohen-Sutherland Line Clipping
Solve an example problem.

Discussion:

2D Clipping:

Let’s try to understand the theory behind the Cohen-Sutherland Line clipping algorithm. Recall discussion from the previous module that, clipping is performed before conversion of data to device coordinates. Line clipping is an extension of point clipping, where we check the position of a given line with respect to a standard rectangular clip window region. We need to perform tests to determine whether a line is completely inside or completely outside or partially inside. The portion of the line that is inside is only selected for display. Clipping algorithms identify the intersections of the lines with the clip window region and decide which portion of the line is inside and so can be selected for display. Two popular algorithms for line clipping are “Cohen-Sutherland line clipper” and “Liang-Barsky line clipper.” An algorithm is considered efficient when with few checks if it decides that

the line is completely inside and so can be selected (Trivial Accept) or
the line is completely outside and so can be discarded (Trivial Reject) or
line is partially inside so intersection checks need to be done.

A line has two end points. If both the end points are inside the clip window, it is trivial that the line is completely inside and so can be selected for display. From the figure above it is evident that line

P3P4 is completely inside since both the end points P3 and P4 are inside (Trivial Accept case).
P1P2, P9P10 are completely outside, and so can be discarded. In both these cases both the end points are outside and the line is also completely outside.
P5P6 – A portion of the line is inside and so find intersection point P5’ and select and display the portion of the line that is inside (P4P5’).
P7P8 – Both end points are outside but a portion of the line is inside. For such types we need to calculate two intersection points P7’ and P8’ and display the line P7’P8’.

Both the algorithms for line clipping, Cohen-Sutherland and Liang-Barsky, are efficient algorithms and both can be extended for 3D clipping as well. But it is Liang-Barsky that suits well for implementation in a program.

Cohen-Sutherland Line Clipping Procedure:

This is a rudimentary level line clipping procedure and is efficient. Two scientists Cohen and Sutherland devised this procedure. The method speeds up the processing of line segments by performing initial tests that reduce the number of intersections that must be calculated particularly in the cases of Trivial Accept and Trivial Reject cases. Imagine that we are dividing the whole space into 9 zones or regions using 4 infinitely extending lines, such that the central region is identified as the clip window region, and remaining 8 regions around the central region are identified relative to the central region as shown in the figure below.

Every region is assigned a four digit binary code, called region code that identifies a region. The central region, called the clip window region, is identified with the region code (0000). The region to the left is given a region code 0001. The regions to the right, bottom and top have the region codes, 0010, 0100, and 1000 respectively. The other 4 regions in the corners, top left, top right, bottom left, bottom right have the region codes 1001, 1010, 0101, 0110 respectively.

Let’s see how this region code was arrived at? Each bit position in the region code is used to indicate one of the four surrounding regions relative to the central clip window region. The order of the bits from right to left is as follows

Bit 1 : Left region

Bit 2 : Right region

Bit 3 : Bottom region

Bit 4 : Top region

For Ex: If a region code is given as 1010, this means, The top and right bits are set (indicated by a binary bit 1) while the left and bottom bits are not set (indicated by a binary bit 0). The answer is that the region with the region code 1010 is the top right of the central region. The central region has the region code 0000.

Let’ s try to understand how this region code is useful in determining the relative position of a line against the clip window. The idea is that for the two end points of a given line we shall compute region code and with simple checks we should be able to decide whether to go for intersection calculations or simply end up with a trivial reject or trivial accept case.

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 clip window. The next step is how do we compute region codes for an end point? It is as simple as checking for four conditions (recall the equations from the point clipping discussion in the previous module – 8).

Assume 4 infinitely extending lines defined by xwmin, xwmax, ywmin, ywmax make up the clip window region. For an end point (x,y), check the first condition, if x<xwmin set the left bit of the region code otherwise keep it 0. Than to check the relation for magnitude, it is convenient to check for the sign bit of the relation, x-xwmin , i.e., if the sign bit of the relation is set then set the left bit. We can perform similar checks for other three bit positions.

Set Bit 1(left): Sign(x – xwmin)

Set Bit 2(right): sign(xwmax – x )

Set Bit 3 (bottom): sign(y – ywmin )

Set Bit 4 (top): sign(ywmax – y)

Compute the region codes for both the end points of a given line. If both the end points have a region code of 0000, then it is a Trivial Accept case, i.e., the line is completely inside and so can be considered for display. In general, a line that is parallel and outside the clip window region, will have, one bit position commonly set in both the region codes of the two end points. For Ex: consider a line that is parallel to the top boundary and is outside will have its region codes, 1001, 1010. From the region codes we can simply conclude that the line has one bit position commonly set, i.e. the top bit, so the line is parallel to the top boundary and is outside and so can be discarded.

*************************************************************************************************Steps in the algorithm are as follows

For each end point of a line, compute region code
If both the end points have a region code of 0000, then it is a Trivial Accept case, i.e., the line is completely inside and so can be considered for display
Otherwise perform a bit wise AND operation for the two region codes of the two end points of a line, and if the operation results in a non-zero value, then it can be concluded that the line is outside and is parallel to that boundary represented by that bit position that is is set in the result, and so is a Trivial Reject case. (Ex: consider two region codes 1010, 0110. Performing bit-wise AND operation we get, 0010, which is a non-zero value and the bit position commonly set in both the region codes is the right bit position. The result says that the line is an outside line and is parallel to the right boundary.)
Otherwise, if the bit-wise AND operation results in a zero value, the line intersects the clip window and we need to go for intersection calculations. (Ex: Consider a line with region codes for its end points as 0100 and 0010. The line is an inclined line, no bit position is commonly set and bit-wise AND operation results in a zero value. So it’s obvious to go for intersection calculations.)
If the above cases fail we need to go for intersection calculations.

***********************************************************************************************

It is known that, there will be a maximum of two intersection points for a given line, when it intersects clip window, but assuming infinitely extending clip window boundaries, and the line to be clipped being longer, there will be four intersection points, as shown below. The four dots represent the four intersection points, the maximum possible for a line.

We need to check for a maximum of 4 intersection points, for the maximum possible line as shown in the figure above. Intersection points with a clipping boundary can be calculated using the slope-intercept form of the line equation.

= −

The y coordinate of the intersection point at vertical line can be computed using the formula

− = ( − ) where x is either xw_min or xw_max

The x coordinate of the intersection point at horizontal line can be computed using the equation

= + –

where y is either ywmin or ywmax.

*********************************************************************************************

Example:

Compute the clipped portion of the line at [(0,0), (8,5)], when clipped against the clip window between [(1,2), (7, 6)].

Solution: From the problem, we can note the following data

xwmin = 1

xwmax = 7

ywmin = 2

ywmax = 6

Starting with left boundary we can calculate intersection points, and continue with the right, bottom, top boundaries.

**********************************************************************************************

In the solution shown above, after the line is clipped against the left boundary, we get an intersection point, P1’, discard the portion from P1 to P1’ and the line to be sent to the next clipper (right) is P1’P2. With respect to the right clipper, when we clip the line we get another intersection point, P2’, and discard the portion from P2 to P2’. Now the line between P1’P2’ is sent to the bottom clipper. When we clip the portion of the line with respect to the bottom clipper, we compute another intersection point, P1’’, and discard the line from P1’ to P1’’. When the line is finally sent to the top clipper, no intersection point needs to be computed as the line is completely inside with respect to top boundary. The computation ends and finally the line to be displayed is the line between P1’ to P2’’.

Summary:

We have learnt how Cohen-Sutherland line clipping works
This algorithm also works for clipping in 3D as well.
An example problem has been solved