Clipping (Basic Computer Graphics) Part 2

Liang-Barsky Line Clipping

The Liang-Barsky line-clipping algorithm ([LiaB84]) optimizes the Cyrus-Beck line-clipping algorithm in the case where we are clipping against a rectangle. It starts by treating a segment as a parameterized set. Lettmpc646-293_thumb_thumbA typical pointtmpc646-294_thumb_thumbon    the oriented line L determined by P1 and P2 then has the form

tmpc646-295_thumb_thumbSee Figure 3.5. If we lettmpc646-296_thumb_thumbthen

tmpc646-301_thumb_thumb

If the window W we are clipping against is the rectangle [xmin,xmax] x [ymin,ymax], then P belongs to W if and only if

tmpc646-302_thumb_thumb

that is,

tmpc646-303_thumb_thumb

 

 

Liang-Barsky line clipping.

Figure 3.5. Liang-Barsky line clipping.

To simplify the notation, we introduce variables ck and qk and rewrite these equations as

tmpc646-305_thumb_thumb

Settmpc646-306_thumb_thumbwhenevertmpc646-307_thumb_thumbdenote the left, right, bottom, and top boundary lines of the window, respectively. With this notation we can make the following observations:

(1)    Iftmpc646-308_thumb_thumbthen  L goes from the “inside” to the “outside” of the boundary line Bk as t increases and we shall call tk an exit value.

(2)    Iftmpc646-309_thumb_thumbthen  L goes from the “outside” to the “inside” of the boundary line Bk as t increases and we shall call tk an entry value.

(3)    Iftmpc646-310_thumb_thumbthe L is parallel to Bk, which is outside the window iftmpc646-311_thumb_thumb

The clipping algorithm now proceeds by analyzing the three quantities qk, ck, and tk. Algorithm 3.2.3.1 is a high-level version of the Liang-Barsky algorithm. Algorithm 3.2.3.2 gives the code for the actual Liang-Barsky algorithm.

Example. Consider the segmenttmpc646-312_thumb_thumbin    Figure 3.6. We  see thattmpc646-313_thumb_thumb 0 andtmpc646-314_thumb_thumbIn    other    words,    t1 and t4 are entry values and t2 and t3 are exit values.

The picture bears this out. One can also easily see thattmpc646-315_thumb_thumbTherefore, there is an entry value (t4) that is larger than an exit value (t2). Using the algorithm we conclude that the segment lies entirely outside the window, which is correct.

High-level Liang-Barsky line-clipping algorithm.

Algorithm 3.2.3.1. High-level Liang-Barsky line-clipping algorithm.

The Liang-Barsky line-clipping algorithm.

Algorithm 3.2.3.2. The Liang-Barsky line-clipping algorithm.

The Liang-Barsky line-clipping algorithm.

Algorithm 3.2.3.2. The Liang-Barsky line-clipping algorithm.

Liang-Barsky line-clipping example.

Figure 3.6. Liang-Barsky line-clipping example.

Example. Consider the segmenttmpc646330_thumb2in    Figure    3.7.    In    this    example, c1,

tmpc646331_thumb2so that t1 and t3 are entry values and t2 and t4 are exit values. Furthermore,tmpc646332_thumb2Thistime we cannot reject the segment and must compute t0 = maxtmpc646333_thumb2The    algorithm    tells us that we must clip the segment at the P1 end to get Q but do not need to clip at    the    P2 end. Again this is clearly what had to be done.

In conclusion, the advantage of the Liang-Barsky algorithm over the Cohen-Sutherland algorithm is that it involves less arithmetic and is therefore    faster.    It    needs only two subtractions to get qk and ck and then one division.

Liang-Barsky line-clipping example.

Figure 3.7. Liang-Barsky line-clipping example.

Next post:

Previous post: