The line clipping is a process in which we can cut the part of the line, which lies outside the view pane. Only those lines are visible, which lie inside the view pane.   

The line clipping process is implemented by following line clipping algorithms

  • Cohen Sutherland Line Clipping Algorithm
  • Liang-Barsky Line Clipping Algorithm
  • Midpoint Subdivision Line Clipping Algorithm

Cohen Sutherland Line Clipping Algorithm

This algorithm was named by “Danny Cohen” and “Ivan Sutherland.”

The algorithm will work in the following steps:

  • In this algorithm, we will divide the view pane into nineequal segments (as shown in the below figure) that only serve the viewport.
  • Now, we will represent the top, bottom, left, and right corner of the window with 4 bits. This 4bit can be described with the following point that:
  • If an object lies within any particular corner position, that corner value will be 1, else it will be 0.
  • The allocation of bits depends on “TBRL” (Top, Bottom, Right, Left) rule.
  • Suppose, if the point of a line appears in the top-left corner, then according to TBRL, the value is 1001. We will allot the bits as-
  • For the top corner, because the object is present at the top corner.
  • For the bottom corner, because the object does not lie at the bottom.
  • For the right corner, because the object does not lie at the right side.
  • For the left corner, because the object lies at the top-left corner.
  • In this way, we check TBRL for each segment and allot the bits accordingly.  
Line Clipping

In Cohen- Sutherland Algorithm we will divide the lines into following Sections-

  • Visible Line: When both points (starting and ending) of the line are entirely situated inside the window.
  • Invisible Line: When both points (Starting and ending) of the line are completely situated outside the window.    

If we have (xmin, xmax) and (ymin, ymax) coordinates of the view pane (window).

Then, it should be described as-

x­­­0, x1 > xmax

y0, y1 > ymax

x0, x1 < xmin

y0, y1 < ymin

  • Clipped Line: Everyline has two endpoints. Let (x­­­0, 0) and (x1, y1) are points of the line. If one point of the line situated inside the window and the other one is outside the window, then the line is known as Clipped Line.
Line Clipping2

Algorithm of Cohen-Sutherland Line Clipping:

Step 1: Assign the bit code for both endpoints of the line.

Step 2: Now,implement OR operation on both endpoints of the line.

Step 3: If the OR = 0000,

             Then

                       {The line is acceptable (Visible)}

             Else

                        {Implement AND operation on endpoints}

              Then

                        If AND ≠ 0000

              Then  

                        {The line is not acceptable (Invisible)}

               Else

                          AND = 0000

                            {The line needs to be clip}               

Step 4: If a line needs to be clipped, first find an intersection point of all boundaries with the following formula-

                m = (y1-y0) (x1-x0)

Step 4.1: When the line intersects the left side boundary of the window port.

                y0 = y1+ m(x-x1)

               Here x = xwmin (Minimum value of x coordinate)  

Step 4.2: When the line intersects the right-side boundary of the window port.

                y0 = y1+m(x-x1)

               Here x = xwmax (Maximum value of x coordinate)

Step 4.3: When the line intersects Top side boundary of the window port.      

                x0 = x1+(y-y1)/m                    

                Here y = ywmax (Maximum value of y coordinate)

Step 4.4: When the line intersects the bottom side boundary of the window port.                       

                 x0 = x1+(y-y1)/m

                 Here y = ywmin (Minimum value of y coordinate)

Example: In the below-mentioned example, we have different lines. The different category of the line-

Line Clipping3

Line AB is a clipped case.

The line CD is completely visible.

Line EF is completely invisible.

Line GH is a clipped case.

Line KL is completely invisible.

Line IJ is a clipped case.

The endpoints of lines are lies as follows-

A → 0000

B → 1010

C → 0000

D → 0000

E → 0100

F → 0100

G → 0001

H → 0000

I → 0000

J → 0010

K → 1000

L → 1000

Advantages:

  1. It is easy to use and implement.
  2. We can perform clipping and testing in a particular manner.
  3. It is a fast algorithm.

Disadvantages:

  1.  Sometimes it performs needless clipping.

Liang-Barsky Line Clipping Algorithm:

The algorithm was introduced by “You-Dong Liang” and “Brian A. Barsky.” It is used for line clipping. It is a more powerful algorithm than the Cohen-Sutherland algorithm.

We use the following concepts in this algorithm-

  • We can use the parametric equation of line and inequalities.
  • These are used to describe the range of windows to find out the intersection points between the line and the clipping window.
  • The parametric line is also known as “Cyrus-Beck.”

In this algorithm, we have to find the intersection point based on a time interval.  

Time interval (t) can be defined as travelling time between initial position (0) to final position (1). Then we have,

0 < t < 1 (Here, t lies between 0 and 1)

We have the formula to find x and y points of the line-

x= x1 + t. x (For point x)

y= y1 + t. y (For point y)

To check that the point lies between the window or outside the equation is-

Xwmin <= x1 + t. x <= Xwmax

Ywmin <= y1 + t. y <= Ywmax

These two conditions can be written as-

x1 + t. x >= Xwmin

x1 + t. x <= Xwmax

y1 + t. y >= Ywmin

y1 + t. y <= Ywmax

We can take a common expression for above four conditions. It will be-

t.pk <= qk (Here the value of k is multiple)

t = qk / pk

              p1 = x                   q1 = x1 – xwmin (For left boundary)

    p2 = x                     q2 = xwmax – x1 (For right boundary)

    p3 = y                    q3 = y1 – ywmin (For bottom boundary)

    p4 = y                     q4 = ywmax – y1(For top Boundary) 

Algorithm of Liang-Barsky Line Clipping:

Step 1: Set the endpoints of the line (x1, y1) and (x2, y2).

Step 2: Calculate the value of p1, p2,p3, p4 ­and q1, q2, q3,q4.

Step 3:  Now we calculate the value of t

               t1 = 0 (For initial point)

               t2 = 1 (For final point)

Step 4: Now, we have to calculate the value of pk and qk

             If  

                    pk = 0

             then

                    {The line is parallel to the window}

              If

                     Qk < 0

               then

                       {The line is completely outside the window}

Step 5: If we have non zero value of pk

                    If

                     pk < 0

           then

                     t1 = max (0, qk / pk)

            If  

                     pk > 0

            then             

                      t2 = min (1, qk / pk)

Now, if t1 < t2 {If t1 value is changed

                         Then the first point is outside the window.

                                 If t2 value is changed

                          Then the second point is outside the window}

        else

                t1 > t2

        then

                 {Line is completely outside the window}

Step 6: Stop.

Example:

Let a rectangular window size with (5, 9). The points of the line are (4, 12) and (8, 8). Use the Liang- Barsky algorithm to clip the line and find the intersection point.   

Solution:

We have,

The initial point of the line (p1) = (4, 12)

The ending point of the line (p2) = (8, 8)

 x1 = 4, x2 = 8

 y1 = 12, y2 = 8

xw­min = 5, xw­max = 9

yw­min = 5, yw­max = 9

Step 1: We have to calculate the value of x andy-

              x = x2– x1= 8-4 = 4

              y = y2– y1= 8-12 = -4

Step 2: Now, we will calculate-

                p1 = -4              q1 = 4-5 = -1

                p2 = 4                q2 = 9-4 = 5

                p3 = 4                q3 = 12-5 = 7

                p4 = -4               q4 = 9-12 = -3

Step 3: Now we will calculate t1 value

          If p1, p4 < 0

          Then t1 =max (0, qk /pk)

                     =max (0, q1 /p1, q4 /p4)

              =max (0, 1/4, 3/4)

           t1 = 3/4

If p2, p3 > 0

Then t2 = min (1, qk /pk)

            = min (1, q2 /p2, q3 /p3)

            = min (1, 5/4, 7/4)

         t2 = 1

Step 4: Now, we have to calculate the intersection point.

           x = x1 + t1. ▲x= 4+ 3/4 * 4 = 7

                 y = y1 + t1. ▲y= 12+ 3/4 *(-4) = 9

The coordinates intersection point = (7, 9)

Line Clipping4
Line Clipping5

Midpoint Subdivision Line Clipping Algorithm:

The midpoint subdivision algorithm is used to clip the line. The algorithm is based on finding the midpoint of the line. We can divide the line into two equal parts. There should be following categories of the line-

Visible line  

 Invisible line

Partially visible

We can calculate the midpoint of the line by the following formula-

Line Clipping6

pm = (p1 + p2)/2

Algorithm Midpoint Subdivision Line Clipping:

Step 1: Assign the bit code for both endpoints of the line.

Step 2: Now,implement OR operation on both endpoints of the line.

Step 3: If the OR = 0000,

             Then

                       {The line is Visible}

             Else

                        {Implement AND operation on endpoints}

              Then

                        If AND ≠ 0000

              Then  

                        {The line is Invisible}

               Else

                          AND = 0000

                            {The line is the partially visible}

Step 4:  For partially visible line, we need to find the midpoint.

              Xm = (x1 + x2)/2 (For x coordinate)            

              Ym = (y1 + y2)/2 (For y coordinate)

Step 5: Weneed to check that the line is near to the boundary of the window or not.

Step 6: If the line is visible or invisible, then repeat steps 1 to 5.

Step 7: Stop.

Example: A window contains the size (0, 50, 0, 50). A line PQ has the coordinates (-10, 40) and (30, -20). Find the visible point of the line using midpoint subdivision.

Solution: We have,

The coordinates for x and y = P (-10, 40)

The coordinates for x and y = Q (30, -20)

Now,

Step 1: We have to compute the midpoint of the line segment PQ.

Q = [(-10 + 30) /2, (40 – 20)/2]

    = (10, 10)

Now the new coordinates of Q = (10, 10)

Step 2: Now, we will find

Q’’ = midpoint of the Q’ and Q

Q’’ = [(10 + 30) /2, (10 + (-20))/2]  

       = (20, -5)

Now the new coordinates of Q’’ = (20, -5)

Here (20, -5) is much better than (10, 10)

Now we have to find Q’’’ then,

Q’’’ = [(20 + 30) /2, (-5 + (-20))/2]

        = (25, -12.5)

Now the new coordinates of Q’’’ = (25, -12.5)

We can clip the line from Q’’ to Q from the top side.

Step 3: Now, we will take left hand side part. The endpoints are P and Q’’’

We will find the midpoint of P and Q’’’

P (-10,40) and Q’’’ (25, -12.5)

P’ = [(-10 + 25) /2, (40 + (-12.5))/2]

    = (7.5, 27.5)

Now we will find the midpoint of P and P’’

P (-10, 40) and P’ (7.5, 27.5)

P’’ = [(-10 + 7.5) /2, (40 + (27.5))/2]

      = (-1.25, 33.75)

Now we will find midpoint of P’’ and P

P’’’ = P (-10, 40) and P’’ (-1.25, 33.75)

       = [(-10 + (-1.25)) /2, (40 + 33.75)/2]

        = (5.62, 36.87)

Now we will clip the line from P to P’’’

Finally, we have P’’’ = (5.62, 36.87)

                            Q’’’ = (25, -12.5)

Line Clipping7

Pin It on Pinterest

Share This