Mumbai University > Computer Engineering > Sem 4 > Computer Graphics

Marks: 10 Marks

Year: Dec 2016

The Weiler–Atherton is a polygon-clipping algorithm. It is used in the areas like computer graphics, games development and others where clipping of polygon is needed. It allows clipping of a subject or candidate polygon by an arbitrarily shaped clipping polygon/area/region.

It is generally applicable only in 2D. However, it can be used in 3D through visible surface determination and with improved efficiency through Z-ordering

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.

This algorithm is used for clipping concave polygons. 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, 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, I3.