Part 9: Clipping and Polygon various Technique algorithm

by Jesmin Akther | Aug 31, 2021 | Computer Graphics

Clipping:

When we have to display a large portion of the picture, then not only scaling & translation is necessary, the visible part of picture is also identified. This process is not easy. Certain parts of the image are inside, while others are partially inside. The lines or elements which are partially visible will be omitted. For deciding the visible and invisible portion, a particular process called clipping is used. Clipping determines each element into the visible and invisible portion. Visible portion is selected. An invisible portion is discarded.

Types of Lines:

Lines are of three types:

1. Visible: A line or lines entirely inside the window is considered visible
2. Invisible: A line entirely outside the window is considered invisible
3. Clipped: A line partially inside the window and partially outside is clipped. For clipping point of intersection of a line with the window is determined.

Clipping can be applied through hardware as well as software. In some computers, hardware devices automatically do work of clipping. In a system where hardware clipping is not available software clipping applied.

Following figure show before and after clipping

The window against which object is clipped called a clip window. It can be curved or rectangle in shape.

Applications of clipping:

1. It will extract part we desire.
2. For identifying the visible and invisible area in the 3D object.
3. For creating objects using solid modeling.
4. For drawing operations.
5. Operations related to the pointing of an object.
6. For deleting, copying, moving part of an object.

Clipping can be applied to world co-ordinates. The contents inside the window will be mapped to device co-ordinates. Another alternative is a complete world co-ordinates picture is assigned to device co-ordinates, and then clipping of viewport boundaries is done.

Types of Clipping:

1. Point Clipping
2. Line Clipping
3. Area Clipping (Polygon)
4. Curve Clipping
5. Text Clipping
6. Exterior Clipping

Point Clipping:

Point Clipping is used to determining, whether the point is inside the window or not. For this following conditions are checked.

1. x ≤ x_max
2. x ≥ x_min
3. y ≤ y_max
4. y ≥ y_min

The (x, y) is coordinate of the point. If anyone from the above inequalities is false, then the point will fall outside the window and will not be considered to be visible.

Program1:

To implement Point Clipping:

Output:

Line Clipping:

It is performed by using the line clipping algorithm. The line clipping algorithms are:

1. Cohen Sutherland Line Clipping Algorithm
2. Midpoint Subdivision Line Clipping Algorithm
3. Liang-Barsky Line Clipping Algorithm

Cohen Sutherland Line Clipping Algorithm:

In the algorithm, first of all, it is detected whether line lies inside the screen or it is outside the screen. All lines come under any one of the following categories:

1. Visible
2. Not Visible
3. Clipping Case

1. Visible: If a line lies within the window, i.e., both endpoints of the line lies within the window. A line is visible and will be displayed as it is.

2. Not Visible: If a line lies outside the window it will be invisible and rejected. Such lines will not display. If any one of the following inequalities is satisfied, then the line is considered invisible. Let A (x₁,y₂) and B (x₂,y₂) are endpoints of line.
3. Clipping Case: If the line is neither visible case nor invisible case. It is considered to be clipped case. First of all, the category of a line is found based on nine regions given below. All nine regions are assigned codes. Each code is of 4 bits. If both endpoints of the line have end bits zero, then the line is considered to be visible.

The center area is having the code, 0000, i.e., region 5 is considered a rectangle window.

Following figure show lines of various types

Line AB is the visible case
Line OP is an invisible case
Line PQ is an invisible line
Line IJ are clipping candidates
Line MN are clipping candidate
Line CD are clipping candidate

Advantage of Cohen Sutherland Line Clipping:

1. It calculates end-points very quickly and rejects and accepts lines quickly.
2. It can clip pictures much large than screen size.

Algorithm of Cohen Sutherland Line Clipping:

Step1:Calculate positions of both endpoints of the line

Step2:Perform OR operation on both of these end-points

Step3:If the OR operation gives 0000
Then
line is considered to be visible
else
Perform AND operation on both endpoints
If And ≠ 0000
then the line is invisible
else
And=0000
Line is considered the clipped case.

Step4:If a line is clipped case, find an intersection with boundaries of the window
m=(y₂-y₁ )(x₂-x₁)

(a) If bit 1 is “1” line intersects with left boundary of rectangle window
y₃=y₁+m(x-X₁)
where X = X_wmin
where X_wminis the minimum value of X co-ordinate of window

(b) If bit 2 is “1” line intersect with right boundary
y₃=y₁+m(X-X₁)
where X = X_wmax
where X more is maximum value of X co-ordinate of the window

(c) If bit 3 is “1” line intersects with bottom boundary
X₃=X₁+(y-y₁)/m
where y = y_wmin
y_wmin is the minimum value of Y co-ordinate of the window

(d) If bit 4 is “1” line intersects with the top boundary
X_3=X1+(y-y₁)/m
where y = y_wmax
y_wmax is the maximum value of Y co-ordinate of the window

Example of Cohen-Sutherland Line Clipping Algorithm:

Let R be the rectangular window whose lower left-hand corner is at L (-3, 1) and upper right-hand corner is at R (2, 6). Find the region codes for the endpoints in fig:

The region code for point (x, y) is set according to the scheme
Bit 1 = sign (y-y_max)=sign (y-6)         Bit 3 = sign (x-x_max)= sign (x-2)
Bit 2 = sign (y_min-y)=sign(1-y)         Bit 4 = sign (x_min-x)=sign(-3-x)

Here

So

A (-4, 2)→ 0001         F (1, 2)→ 0000
B (-1, 7) → 1000         G (1, -2) →0100
C (-1, 5)→ 0000         H (3, 3) → 0100
D (3, 8) → 1010         I (-4, 7) → 1001
E (-2, 3) → 0000         J (-2, 10) → 1000

We place the line segments in their appropriate categories by testing the region codes found in the problem.

Category1 (visible): EF since the region code for both endpoints is 0000.

Category2 (not visible): IJ since (1001) AND (1000) =1000 (which is not 0000).

Category 3 (candidate for clipping): AB since (0001) AND (1000) = 0000, CD since (0000) AND (1010) =0000, and GH. since (0100) AND (0010) =0000.

The candidates for clipping are AB, CD, and GH.

In clipping AB, the code for A is 0001. To push the 1 to 0, we clip against the boundary line x_min=-3. The resulting

intersection point is I₁ (-3,3). We clip (do not display) AI₁ and I₁ B. The code for I₁is 1001. The clipping category for I₁ B is 3 since (0000) AND (1000) is (0000). Now B is outside the window (i.e., its code is 1000), so we push the 1

to a 0 by clipping against the line y_max=6. The resulting intersection is l₂ (-1,6). Thus I₂ B is clipped. The code for I₂ is 0000. The remaining segment I₁ I₂ is displayed since both endpoints lie in the window (i.e., their codes are 0000).

For clipping CD, we start with D since it is outside the window. Its code is 1010. We push the first 1 to a 0 by clipping against the line y_max=6. The resulting intersection I₃ is (,6),and its code is 0000. Thus I₃ D is clipped and the remaining segment CI₃ has both endpoints coded 0000 and so it is displayed.

For clipping GH, we can start with either G or H since both are outside the window. The code for G is 0100, and we push the 1 to a 0 by clipping against the line y_min=1.The resulting intersection point is I₄ (2,1) and its code is 0010. We clip GI₄ and work on I₄ H. Segment I₄ H is not displaying since (0010) AND (0010) =0010.

Program to perform Line Clipping using Cohen Sutherland Algorithm:

Output:

Mid Point Subdivision Line Clipping Algorithm:

It is used for clipping line. The line is divided in two parts. Mid points of line is obtained by dividing it in two short segments. Again division is done, by finding midpoint. This process is continued until line of visible and invisible category is obtained. Let (x_i,y_i) are midpoint

x₅lie on point of intersection of boundary of window.

Advantage of midpoint subdivision Line Clipping:

It is suitable for machines in which multiplication and division operation is not possible. Because it can be performed by introducing clipping divides in hardware.

Algorithm of midpoint subdivision Line Clipping:

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
X_m=(x₁+x₂)/2
Y_m=(y₁+y₂)/2
X_mis midpoint of X coordinate.
Y_mis 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.

Example: Window size is (-3, 1) to (2, 6). A line AB is given having co-ordinates of A (-4, 2) and B (-1, 7). Does this line visible. Find the visible portion of the line using midpoint subdivision?

Solution:

Step1: Fix point A (-4, 2)

Step2: Find b”=mid of b’and b

So (-1, 5) is better than (2, 4)
Find b”&bb”(-1, 5) b (-1, 7)

So B””to B length of line will be clipped from upper side

Now considered left-hand side portion.

A and B””are now endpoints

Find mid of A and B””

A (-4, 2) B “”(-1, 6)

Liang-Barsky Line Clipping Algorithm:

Liang and Barsky have established an algorithm that uses floating-point arithmetic but finds the appropriate endpoints with at most four computations. This algorithm uses the parametric equations for a line and solves four inequalities to find the range of the parameter for which the line is in the viewport.

Let P(x1, y1), Q(x2, y2) is 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

x=x₁+(x₂-x₁ )*t=x₁+dx*t and y=y₁+(y₂-y₁ )*t=y₁+dy*t

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 of Liang-Barsky Line Clipping:

1. Set t_min=0 and t_max=1

2. Calculate the values t_L,t_R,t_T and t_B(tvalues).
If t<t_{min or t<tmax? ignore it and go to the next edge
Otherwise classify the tvalue as entering or exiting value (using inner product to classify)
If t is entering value set tmin=t if t is exiting value set tmax=t.</t</t}

3. If t_min< t_max? then draw a line from (x1 + dx*t_min, y1 + dy*t_min) to (x1 + dx*t_max?, y1 + dy*t_max? )

4. If the line crosses over the window, you will see (x1 + dx*t_min, y1 + dy*t_min) and (x1 + dx*t_max? , y1 + dy*t_max?) are intersection between line and edge.

Text Clipping:

Several methods are available for clipping of text. Clipping method is dependent on the method of generation used for characters. A simple method is completely considered, or nothing considers method. This method is also called as all or none. If all characters of the string are inside window, then we will keep the string, if a string character is outside then whole string will be discarded in fig (a). Another method is discarded those characters not completely inside the window. If a character overlap boundary of window. Those will be discarded in fig (b).In fig (c) individual character is treated. Character lies on boundary is discarded as which it is outside the window.

Curve Clipping:

Curve Clipping involves complex procedures as compared to line clipping. Curve clipping requires more processing than for object with linear boundaries. Consider window which is rectangular in shape. The circle is to consider against rectangle window. If circle is completely inside boundary of the window, it is considered visible. So save the circle. If a circle is in outside window, discard it. If circle cut the boundary then consider it to be clipping case.

Exterior Clipping:

It is opposite to previous clipping. Here picture which is outside the window is considered. The picture inside the rectangle window is discarded. So part of the picture outside the window is saved.

Uses of Exterior Clipping:

1. It is used for displaying properly the pictures which overlap each other.
2. It is used in the concept of overlapping windows.
3. It is used for designing various patterns of pictures.
4. It is used for advertising purposes.
5. It is suitable for publishing.
6. For designing and displaying of the number of maps and charts, it is also used.

Polygon Clipping:

Polygon clipping is applied to the polygons. The term polygon is used to define objects having outline of solid. These objects should maintain property and shape of polygon after clipping.

Polygon:

Polygon is a representation of the surface. It is primitive which is closed in nature. It is formed using a collection of lines. It is also called as many-sided figure. The lines combined to form polygon are called sides or edges. The lines are obtained by combining two vertices.

Example of Polygon:

1. Triangle
2. Rectangle
3. Hexagon
4. Pentagon

Following figures shows some polygons.

Types of Polygons

1. Concave
2. Convex

A polygon is called convex of line joining any two interior points of the polygon lies inside the polygon. A non-convex polygon is said to be concave. A concave polygon has one interior angle greater than 180°. So that it can be clipped into similar polygons.

A polygon can be positive or negative oriented. If we visit vertices and vertices visit produces counterclockwise circuit, then orientation is said to be positive.

Sutherland-Hodgeman Polygon Clipping:

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 while processing

1. If the first vertex is an outside the window, the second vertex is inside the window. Then second vertex is added to the output list. The point of intersection of window boundary and polygon side (edge) is also added to the output line.
2. If both vertexes are inside window boundary. Then only second vertex is added to the output list.
3. If the first vertex is inside the window and second is an outside window. The edge which intersects with window is added to output list.
4. If both vertices are the outside window, then nothing is added to output list.

Following figures shows original polygon and clipping of polygon against four windows.

Disadvantage of Cohen Hodgmen Algorithm:

This method requires a considerable amount of memory. The first of all polygons are stored in original form. Then clipping against left edge done and output is stored. Then clipping against right edge done, then top edge. Finally, the bottom edge is clipped. Results of all these operations are stored in memory. So wastage of memory for storing intermediate polygons.

Weiler-Atherton Polygon Clipping:

Let the clipping window be initially called clip polygon and the polygon to be clipped the subject polygon. We start with an arbitrary vertex of the subject polygon and trace around its border in the clockwise direction until an intersection with the clip polygon is encountered:

1. If the edge enters the clip polygon, record the intersection point and continue to trace the subject polygon.

2. If the edge leaves the clip polygon, record the intersection point and make a right turn to follow the clip polygon in the same manner (i.e., treat the clip polygon as subject polygon and the subject polygon as clip polygon and proceed as before).

Whenever our path of traversal forms a sub-polygon we output the sub-polygon as part of the overall result. We then continue to trace the rest of the original subject polygon from a recorded intersection point that marks the beginning of a not-yet traced edge or portion of an edge. The algorithm terminates when the entire border of the original subject polygon has been traced exactly once.

For example, the number in fig (a) indicates the order in which the edges and portion of edges are traced. We begin at the starting vertex and continue along the same edge (from 1 to 2) of the subject polygon as it enters the clip polygon. As we move along the edge that is leaving the clip polygon, we make a right turn (from 4 to 5) onto the clip polygon, which is now considered the subject polygon. Following the same logic leads to the next right turn (from 5 to 6) onto the current clip polygon, this is the original subject polygon. With the next step done (from 7 to 8) in the same way, we have a sub-polygon for output in fig (b). We then resume our traversal of the original subject polygon from the recorded intersection point where we first changed our course. Going from 9 to 10 to 11 produces no output. After skipping the already traversed 6 and 7, we continue with 12 and 13 and come to an end. The fig (b) is the final result.