GROUP 6

CLIPPING: LINE AND POLYGON CLIPPING ALGORITHM

Clipping: Line and Polygon Clipping Algorithms

The primary use of clipping in computer graphics is to remove objects, lines, or line segments
that are outside the viewing pane.

Line Clipping: Is the process of removing (clipping) lines or portions of lines outside an area of
interest (viewport or view volume). Typically, any part of a line which is outside of the viewing
area is removed.

Examples of Line Clipping algorithm:

 Cohen Sutherland Line Clipping Algorithm

 Liang-Barsky Line Clipping Algorithm
 Midpoint Subdivision Line Clipping Algorithm

Cohen Sutherland Line Clipping Algorithm: This algorithm divides a 2D space into 9 regions,
of which only the middle part (viewport) is visible. The minimum coordinate for the clipping
region is (XWmin, YWmin) and the maximum coordinate for the clipping region is (XWmax,
YWmax).

Algorithm:
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)

Line AB is a clipped case, Line CD is completely visible, Line EF is completely

invisible, Line GH is a clipped case, Line KL is completely invisible and Line IJ is a
clipped case.

There are 3 possibilities for the line:

1. Line can be completely inside the window. (These lines should be accepted).
 2. Line can be completely outside of the window. (These lines will be completely removed
from the region).
3. Line can be partially inside the window. (We will find intersection point and draw only
that portion of line that is inside region).

Advantages:
1. It is easy to implement and use.
2. We can perform clipping and testing in a particular manner.
3. It is a fast algorithm.
Disadvantage:
1. Sometimes it performs needless clipping.

Liang-Barsky Line Clipping Algorithm: The Liang–Barsky algorithm uses the parametric
equation of a line and solves four inequalities to find the range of the parameter for which the
line is in viewport. This algorithm is significantly more efficient than Cohen–Sutherland, but
Cohen–Sutherland does trivial accepts and rejects much faster, so it should be considered instead
if most of the lines you need to clip would be completely in or out of the clip window.

Let P(X1, Y1), Q(X2, Y2) be the line which we want to study. The parametric equation of the
line segment from gives x-values and y-values for every point in terms of a parameter that ranges
from 0 to 1. The equations are

 and 

We can see that when t = 0, the point computed is P(x1,y1); and when t = 1, the point computed
is Q(x2,y2).
Algorithm:

1. Set   and 
2. Calculate the values of tL, tR, tT, and tB (tvalues).
o if   or   ignore it and go to the next edge
o otherwise classify the tvalue as entering or exiting value (using inner product to
classify)
o if t is entering value set  ; if t is exiting value set 
3. If   then draw a line from (x1 + dx*tmin, y1 + dy*tmin) to (x1 + dx*tmax, y1
+ dy*tmax)
4. If the line crosses over the window, you will see (x1 + dx*tmin, y1 + dy*tmin) and (x1 +
dx*tmax, y1 + dy*tmax) are intersection between line and edge

Midpoint Subdivision Line Clipping Algorithm: Midpoint subdivision algorithm is an

extension of the Cyrus Beck algorithm. This algorithm is mainly used to compute visible
areas of lines that are present in the view port are of the sector or the image. It follows the
principle of the bisection method and works similarly to the Cyrus Beck algorithm by
bisecting the line in to equal halves. But unlike the Cyrus Beck algorithm, which only bisects
the line once, Midpoint Subdivision Algorithm bisects the line numerous times.

Algorithm:

Step1: Calculate the position of both endpoints of the line

Step2: Perform OR operation on both of these endpoints

Step3: If the OR operation gives 0000

            then
                    Line is guaranteed to be visible
          else
                  Perform AND operation on both endpoints.
                  If AND ≠ 0000
            then the line is invisible
      else
            AND=6000
            then the line is clipped case.

Step4: For the line to be clipped. Find midpoint

            Xm= (x1+x2)/2
            Ym= (y1+y2)/2
        Xm is midpoint of X coordinate.
        Ym is midpoint of Y coordinate.
Step5: Check each midpoint, whether it nearest to the boundary of a window or not.

Step6: If the line is totally visible or totally rejected not found then repeat step 1 to 5.

Step7: Stop algorithm.
Polygon Clipping: Polygon clipping is defined by Liang and Barsky (1983) as the process of
removing those parts of a polygon that lie outside a clipping window. The polygon clipping is
required to deal different cases. Usually it clips the four edges in the boundary of the clip
rectangle. The clip boundary determines the visible and invisible regions of polygon clipping and
it is categorized as four.
• Visible region is wholly inside the clip window – saves endpoint.
• Visible exits the clip window – Save the interaction.
• Visible region is wholly outside the clip window – nothing to save.
• Visible enters the clip window – save endpoint and intersection.

Examples of Polygon Clipping Algorithm:

 Sutherland-Hodgman polygon clipping Algorithm

 Weiler-Atherton polygon clipping Algorithm

Sutherland-Hodgman polygon clipping Algorithm: It is performed by processing the

boundary of polygon against each window corner or edge. First of all entire polygon is clipped
against one edge, then resulting polygon is considered, then the polygon is considered against the
second edge, so on for all four edges.

Four possible situations for any given edge of given polygon against current clipping edge:

1. Both vertices are inside: Only the second vertex is added to the output list.
2. First vertex is outside while second one is inside: Both the point of intersection of the
edge with the clip boundary and the second vertex are added to the output list.
3. First vertex is inside while second one is outside: Only the point of intersection of the
edge with the clip boundary is added to the output list.
4. Both vertices are outside: No vertices are added to the output list.
Advantages:

 It is easy to implement.
 It is very useful for clipping polygons.

Disadvantage:

This method requires a considerable amount of memory. The first of all polygons are stored in
original form, clipping against left edge done and output is stored, clipping against right edge
done, then top edge. Finally, the bottom edge is clipped. The results of all these operations are
stored in memory, so there is wastage of memory for storing intermediate polygons.
Weiler-Atherton polygon clipping Algorithm: Weiler Atherton Polygon Clipping Algorithm
is an algorithm made to allow clipping of even concave algorithms to be possible. Unlike
Sutherland – Hodgman polygon clipping algorithm, this algorithm is able to clip concave
polygons without leaving any residue behind. Given polygon A as the clipping region and
polygon B as the subject polygon to be clipped, the algorithm consists of the following steps:

1. List the vertices of the clipping-region polygon A and those of the subject polygon B.
2. Label the listed vertices of subject polygon B as either inside or outside of clipping
region A.
3. Find all the polygon intersections and insert them into both lists, linking the lists at the
intersections.
4. Generate a list of "inbound" intersections – the intersections where the vector from the
intersection to the subsequent vertex of subject polygon B begins inside the clipping
region.
5. Follow each intersection clockwise around the linked lists until the start position is found.

Here V1, V2, V3, V4, V5 are the vertices of the polygon. C4, C2, C3, C4 are the vertices of
the clip polygon and I1, I2, I3, I4 are the intersection points of polygon and clip polygon.

In this algorithm we take a starting vertex like I1 and traverse the polygon like I1, V3, and I2.
At occurrence of leaving intersection the algorithm follows the clip polygon vertex list from
leaving vertex in downward direction. At occurrence of entering intersection the algorithm
follows subject polygon vertex list from the entering intersection vertex. This process is
repeated till we get starting vertex. This process has to be repeated for all remaining entering
intersections which are not included in the previous traversing of vertex list. Since I3 was not
included in first traverse, hence, we start the second traversal from I3. Therefore, first
traversal gives polygon as: I1, V3, I2, I1 and second traversal gives polygon as: I3, V5, I4,
and I3.

Advantage:

 Able to clip concave polygons without leaving any residue behind.