Computer Graphics Tutorial

Introduction of Computer Graphics History of Computer Graphics Types of Computer Graphics Application of Computer Graphics Input Devices Output Devices Display Devices Display Processor Image Representation Color Model Animation Projection Transformation 2D Translation 2D Rotation 2D Scaling 2D Reflection 2D Shearing 3D Translation 3D Rotation 3D Scaling 3D Reflection 3D Shearing Computer Graphics Window Panning Zooming Clipping Line Clipping Point Clipping Text Clipping Polygon Clipping Scan Conversion Line Drawing Algorithm DDA Line Drawing Algorithm Bresenham’s Line Drawing Algorithm Mid-Point Line Drawing Algorithm Scan Conversion of a circle Bresenham’s Circle Drawing Algorithm Midpoint Circle Drawing Algorithm Scan Conversion of an Ellipse Pointing and positioning Techniques Filled Area Primitives

Misc

2D Transformation in Computer Graphics Types of Computer Graphics Resolution in Computer Graphics Anti-aliasing in Computer Graphics Aspect Ratio in Computer Graphics Composite Transformation in Computer Graphics Homogeneous Coordinates in Computer Graphics Illumination Model in Computer Graphics Rendering in Computer Graphics DPI Meaning in Computer What is Double Buffering?

Polygon Clipping in Computer Graphics
2020-01-30 11:10:37

Polygon Clipping in Computer Graphics

“A Polygon can be described as the enclosed collection or group of the lines.”

In a polygon, all lines are connected. Lines can be a combination of edges and vertices, which together form a polygon. A polygon refers to a two-dimensional architecture made up of a number of straight lines.

Some Examples of the polygon:

  1. Triangles
  2. Pentagons
  3. Hexagons
  4. Quadrilaterals

The polygon’s name defines how many sides the architecture contains.

Triangle: It has three sides.

Polygon Clipping

Pentagon: A pentagon has five sides.

Polygon Clipping2

Hexagon: It contains six sides.

Polygon Clipping3

Quadrilaterals: It contains four sides.

Polygon Clipping4

Types of Polygon

There are two basic types of polygon-

  1. Concave Polygon
  2. Convex Polygon

Concave Polygon: The concave polygon does not have any part of its diagonals in its exterior. In a concave polygon, at least one angle should be greater than 180° (angle >180°). 

Polygon Clipping5

Convex Polygon: The convex polygon has at least one part of diagonal in its exterior. In a convex polygon, all the angles should be less than 180° (angle<180°). 

Polygon Clipping6

Polygon Clipping

Polygon clipping is a process in which we only consider the part which is inside the view pane or window. We will remove or clip the part that is outside the window. We will use the following algorithms for polygon clipping-

  • Sutherland-Hodgeman polygon clipping algorithm
  • Weiler-Atherton polygon clipping algorithm

Sutherland-Hodgeman polygon clipping algorithm

The polygon clipping algorithm deals with four different clipping cases. The output of each case is input for the next case.

Case1) Left clip: In the left side polygon clipping, we only remove the left part of the polygon, which is outside the window. We only save the portion which is inside the window.

Polygon Clipping7
Polygon Clipping

Case2) Right clip: In the right-side polygon clipping, we only remove the right part of the polygon, which is outside the window. We only save the portion which is inside the window.

Polygon Clipping9

Case3) Top clip: On the top side polygon clipping, we only remove the top part of the polygon, which is outside the window. We only save the portion which is inside the window.

Polygon Clipping10

Case4) Bottom clip: In the bottom side polygon clipping, we only remove the bottom part of the polygon, which is outside the window. We only save the portion which is inside the window.

Polygon Clipping11

There should be the following conditions while we clip a polygon.

Condition 1(Out-In): If the first vertex of the polygon is outside and the second vertex is inside the window, then the output will be the intersection point and second vertex.

Polygon Clipping12

Condition 2(In-Out): If the first vertex of the polygon is inside and the second vertex is outside the window, then the output will be the intersection point.

Polygon Clipping13

Condition 3(In-In): If both vertices of the polygon are inside the window, then the output will be the second vertex.

Polygon Clipping14

Condition 4(Out-Out): If both vertices of the polygon are outside the window, then the output will be nothing. It means we found a clipped polygon.

Polygon Clipping15

Weiler-Atherton polygon clipping algorithm

This algorithm helps us to clip a filled area. The filled area may be a convex polygon or concave polygon. This algorithm was introduced to identify the visible surfaces. This algorithm helps to create individual polygons in some cases. In the Weiler-Atherton algorithm, we consider the view pane boundaries instead of edges and vertices of the polygon.

Algorithm of Weiler-Atherton Polygon Clipping

Step 1: First,create a list of intersection points that are in the starting or ending state. (I1, I2……. In).

Step 2: Now, create twomore lists; one for subject polygon and other for clip polygon.Fill both lists with intersection points and vertices of the polygon.

Order of Subject Polygon list- Write down all the vertices of the polygon in the subject polygon column.

Order of Clip Polygon list – Write down the points of the clipping window.

Step 3: Insert the vertices in both lists in such a way that the intersection point exists between the correct vertices.

Step 4: Now, start from the first vertex of the polygon. Select the first intersection point as an entering point and follow the same process until we reach the exiting point.

Step 5:  We can move from clip polygon list to subject polygon list and search for the finishing intersection point. Repeat the process until we find the entering point.

Step 6: Now, the polygon is being clipped. Repeat the same process until each point has been visited once.

Step 7: Stop.

Example: Consider a polygon with vertices ABCDEFG. Apply Weiler- Atherton algorithm to find the clipped polygon?

Solution: Let us assume that the vertices of window = C1, C2, C3, C4

The vertices of polygon = ABCDEFG

First, create two lists, one for subject polygon and second for clip polygon.

Iteration 1-

Polygon Clipping16
Polygon Clipping

The First new list is- A`, B, C, D`, A`.

Iteration 2-

Polygon Clipping17
Polygon Clipping

The Second new list is­- E`, E, F, F`, F`.

Explanation:

  • Check A if it is an intersection point then, start from A otherwise, move to next.
  • A` is an intersection point (A` will be saved in the new list) then check the next vertex.
  • B is not an intersection point save that in the new list. Then move to next.
  • C is also not an intersection point; save it in the new list and move to the next point.
  • Now, move to D` (D` is an intersection point). We jump to clip polygon list to find D`.
  • We will follow the same procedure for the next iteration.
  • This process is repeated until we found the ending point.