Vatti Polygon Clipping
Quite a few polygon-clipping algorithms have been published. We have discussed several. The Liang-Barsky and Maillot algorithms are better than the Sutherland-Hodgman algorithm, but these algorithms only clip polygons against simple rectangles. This is adequate for many situations in graphics. On the other hand, the Sutherland-Hodgman and Cyrus-Beck algorithms are more general and allow clipping against any convex polygon. The restriction to convex polygons is caused by the fact that the algorithm clips against a sequence of halfplanes and therefore only applies to sets that are the intersection of halfplanes, in other words, convex (linear) polygons. There are situations however where the convexity requirement is too restrictive. The Weiler algorithm is more general yet and works for non-convex polygons. The final two algorithms we look at, the Vatti and Greiner-Hormann algorithms, are also extremely general. Furthermore, they are the most efficient of these general algorithms. The polygons are not constrained in any way now. They can be concave or convex. They can have self-intersections. In fact, one can easily deal with lists of polygons. We begin with Vatti’s algorithm ([Vatt92]).
Call an edge of a polygon a left or right edge if the interior of the polygon is to the right or left, respectively. Horizontal edges are considered to be both left and right edges. A key fact that is used by the Vatti algorithm is that polygons can be represented via a set of left and right bounds, which are connected lists of left and right edges, respectively, that come in pairs. Each of these bounds starts at a local minimum of the polygon and ends at a local maximum. Consider the “polygon” with vertices p8 shown in Figure 3.18(a). The two left bounds have vertices p2, respectively. The two right bounds have vertices
Note. In this section the y-axis will be pointing up (rather than down as usual for a viewport).
Here is an overview of the Vatti algorithm. The first step of the algorithm is to determine the left and right bounds of the clip and subject polygons and to store this information in a local minima list (LML). This list consists of a list of matching pairs of left-right bounds and is sorted in ascending order by the y-coordinate of the corresponding local minimum. It does not matter if initial horizontal edges are put into a left or right bound. Figure 3.18(b) shows the LML for the polygon in Figure 3.18(a). The algorithm for constructing the LML is a relatively straightforward programming exercise and will not be described here. It can be done with a single pass of the clip and subject polygons.
Figure 3.18. Polygon bounds.
The bounds on the LML were specified to have the property that their edges are either all left edges or all right edges. However, it is convenient to have a more general notion of a left or right bound. Therefore, from now on, a left or right bound will denote any connected sequence of edges only whose first edge is required to be a left or right edge, respectively. We still assume that a bound starts at a local minimum and ends at a local maximum. For example, we shall allow the polygon in Figure 3.18(a) to be described by one left bound with vertices: and one right bound with vertices
The clipped or output polygons we are after will be built in stages from sequences of "partial" polygons, each of which is a "V-shaped" list of vertices with the vertices on the left side coming from a left bound and those on the right side coming from a right bound with the two bounds having one vertex in common, namely, the one at the bottom of the "V", which is at a local minimum. Let us use the notation ~ to denote the partial polygon with verticesis the first point andthe last. The pointst are the top of the partial left and right bound, respectively. Some vertex pm will be the vertex at a local minimum that connects the two bounds but, since it will not be used for anything, there is no need to indicate this index m in the notation. For example, one way to represent the polygon in Figure 3.18(a) would be as(with m being 3 in this case).
Notice how the edges in the left and right bounds are not always to the right or left of the interior of the polygon here. In the case of a “completed" polygon, po and pn will be the same vertex at a local maximum, but at all the other intermediate stages in the construction of a polygon the vertices po and pn may not be equal. However, po and pn will always correspond to top vertices of the current left and right partial bounds, respectively. For example,(with m equal to 2) is a legitimate expression describing partial left and right bounds for the polygon in Figure 3.18(a).
A good way to implement these partial polygons is via a circularly linked list, or cycle, and a pointer that points to the last element of the list.
The algorithm now computes the bounds of the output polygons from the LML by scanning the world from the bottom to the top using what are called scan beams. A scan beam is a horizontal section between two scan lines (not necessarily adjacent), so that each of these scan lines contains at least one vertex from the polygons but there are no vertices in between them. Figure 3.18(a) shows the scan beams and the scan lines that determine them for that particular polygon. The scan beams are the regions between the horizontal lines. It should be noted here that the scan lines that determine the scan beams are not computed all at once but incrementally in a bottom-up fashion. The information about the scan beams is kept in a scan beam list (SBL), which is an ordered list ordered by the y-coordinates of all the scan lines that define the scan beams. This list of increasing values will be thought of as a stack. As we scan the world, we also maintain an active edge list (AEL), which is an ordered list consisting of all the edges intersected by the current scan beam.
When we begin processing a scan beam, the first thing we do is to check the LML to see if any of its bound pairs start at the bottom of the scan beam. These bounds correspond to local minima and may start a new output polygon or break one into two depending on whether the local minimum starts with a left-right or right-left edge pair. After any new edges from the LML are added to the AEL, we need to check for intersections of edges within a scan beam. These intersections affect the output polygons and are dealt with separately first. Finally, we process the edges on the AEL. Algorithm 220.127.116.11 summarizes this overview of the Vatti algorithm.
To understand the algorithm a little better we look at some more of its details. The interested reader can find a much more thorough discussion with abstract programs and explicit data structures in the document VattiClip on the accompanying CD. The UpdateLMLandSBL procedure in Algorithm 18.104.22.168 finds the bounds of a polygon, adds them to LML, and also updates SBL. Finding a bound involves finding the edges that make them up and initializing their data structure that maintains the information that we need as we go along. For example, we keep track of the x-coor-dinate of their intersection with the bottom of the current scan beam. We call this the x-value of the edge. The edges of the AEL are ordered by these values with ties being broken using their slope. We also record the kind of an edge which refers to whether it belongs to the clip or subject polygon. Two edges are called like edges if they are of the same kind and unlike edges otherwise. The partial polygons that are built and that, in the end, may become the polygons that make up the clipped polygon are called the adjacent polygons of their edges.
Because horizontal edges complicate matters, in order to make dealing with horizontal edges easier, one assumes that the matching left and right bound pairs in the LML list are “normalized”. A normalized left and right bound pair satisfies the following properties:
(1) All consecutive horizontal edges are combined into one so that bounds do not have two horizontal edges in a row.
(2) No left bound has a bottom horizontal edge (any such edges are shifted to the right bound).
(3) No right bound has a top horizontal edge (any such edges are shifted to the left bound).
Algorithm 22.214.171.124. The Vatti polygon-clipping algorithm.
We introduce some more terminology. Some edges and vertices that one encounters or creates for the output polygons will belong to the bounds of the clipped polygon, others will not. Let us call a vertex or an edge a contributing or noncontributing vertex or edge depending on whether or not it belongs to the output polygons. With regard to vertices, if a vertex is not a local minimum or maximum, then it will be called a left or right intermediate vertex depending on whether it belongs to a left or right bound, respectively. Because the overall algorithm proceeds by taking the appropriate action based on the vertices that are encountered, we shall see that it therefore basically reduces to a careful analysis of the following three cases:
(1) The vertex is a local minimum.
(2) The vertex is a left or right intermediate vertex.
(3) The vertex is a local maximum.
Local minima are encountered when elements on the LML become active. Intermediate vertices and local maxima are encountered when scanning the AEL. Intersections of edges also give rise to these three cases.
Returning to Algorithm 126.96.36.199, the first thing that happens in the main loop is to check for new bound pairs that start at the bottom of the current scan beams. If any such pairs exist, then we have a case of two bounds starting at a vertex p that is a local minimum. We add their first nonhorizontal edges to the AEL and the top y-values of these to the SBL. The edges are flagged as being a left or right edge. We determine if the edges are contributing by a parity test and flag them accordingly. An edge of the subject polygon is contributing if there are an odd number of edges from the clip polygon to its left in the AEL. Similarly, an edge of the clip polygon is contributing if there are an odd number of edges from the subject polygon to its left in the AEL. If the vertex is contributing, then we create a new partial polygon P[p] and associate this polygon to both edges. Note that to determine whether or not an edge is contributing or noncontributing we actually have to look at the geometry only for the first nonhorizontal edge of each bound. The bound’s other edges will be of the same type as that one.
The central task of the main loop in the Vatti algorithm is to process the edges on the AEL. If edges intersect, we shall have to do some preprocessing (procedure ProcessIntersections), but right now let us skip that and describe the actual processing, namely, procedure ProcessEdgesInAEL. Because horizontal edges cause substantial complications, we separate the discussion into two cases. We shall discuss the case where there are no horizontal edges first.
If an edge does not end at the top of the current scan beam, then we simply update its x-value to the x-coordinate of the intersection of the edge with the scan line at the top of the scan beam. If an edge does end at the top of the scan beam, then the action we take is determined by the type of the top end vertex p. The vertex can either be an intermediate vertex or a local maximum.
If the vertex p is a left or right intermediate vertex, then the vertex is added at the beginning or end of the vertex list of its adjacent polygon, depending on whether it is a left or right edge, respectively. The edge is replaced on the AEL by its successor edge which inherits the adjacent polygon and left/right flag of the old edge.
If the vertex p is a local maximum of the original clip or subject polygons, then a pair of edges from two bounds meet in the point p. If p is a contributing vertex, then the two edges may belong either to the same or different (partial) polygons. If they have the same adjacent polygons, then this polygon will now be closed once the point p is added. If they belong to different polygons, say P and Q, respectively, then we need to merge these polygons. Let e1 and e2 be the top edges for P and f1 and f2, the top edges for Q, so that e1 and f1 meet in p with f1 the successor to e1 in the AEL. See Figure 3.19. Figures 3.19(a) and (c) show specific examples and (b) and (d) generic cases. If e1 is a left edge of P (Figures 3.19(a) and (b)), then we append the vertices of Q to the begin- ning of the vertex list of P. If e1 is a right edge of P (Figures 3.19(c) and (d)), then we append the vertices of P to the end of the vertex list of Q. Note that each of the polygons has two top contributing edges. In either case, after combining the vertices of P and Q, the two edges e1 and f1 become noncontributing. If e1 was a left edge, then f2 will be contributing to P and the adjacent polygon of f2 will become P. If e1 was a right edge, then e2 will be contributing to Q. Therefore, the adjacent polygon of e2 will become Q.
Figure 3.19. Merging polygons.
When we find a local maximum we know two top edges right away, but if these have different adjacent polygons, then we need to find the other two top edges for these polygons. There are two ways to handle this. One could maintain pointers in the polygons to their current top edges, or one could do a search of the AEL. The first method gives us our edges without a search, but one will have to maintain the pointers as we move from one edge to the next. Which method is better depends on the number of edges versus the number of local maxima. Since there probably are relatively few local maxima, the second method is the recommended one.
Finally, we look at how one deals with intersections of edges within a scan beam. The way that these intersections are handled depends on whether we have like or unlike edges. Like intersections need only be considered if both edges are contributing and in that case the intersection point should be treated as both a left and right intermediate vertex. (Note that in the case of like intersections, if one edge is contributing, then the other one will be also.) Unlike intersections must always be handled. How their intersection point is handled depends on their type, side, and relative position in the AEL.
It is possible to give some precise rules on how to classify intersection points. The classification rules are shown in Table 188.8.131.52 in an encoded form. Edges have been specified using the following two-letter code: The first letter indicates whether the edge is a left (L) or right (R) edge, and the second letter specifies whether it belongs to the subject (S) or clip (C) polygon. The resulting vertex type is also specified by a two-letter code: local minimum (MN), local maximum (MX), left intermediate (LI), and right intermediate (RI). Edge codes are listed in the order in which their edges appear in the AEL.
For example, Rule 1 translates into the following: The intersection of a left clip edge and a left subject edge, or the intersection of a left subject edge and a left clip edge, produces a left intermediate vertex. Rules 1-4 are shown graphically in Figure 3.20(a). Figure 3.20(b) shows an example of how the rules apply to some real polygon intersections.
Table 184.108.40.206 Rules that Classify the Intersection Point Between Edges
Figure 3.20. Intersection rules.
As one moves from scan beam to scan beam, one updates the x-values of all the edges (unless they end at the top of the scan beam). Although the AEL is sorted as one enters a new scan beam, if any intersections are found in a scan beam, the AEL will no longer be sorted after the x-values are updated. The list must therefore be resorted, but this can be done in the process of dealing with the intersections. Vatti used a temporary sorted edge list (SEL) and an intersection list (IL) to identify and store all the intersections in the current scan beam. The SEL is ordered by the x-coor-dinate of the intersection of the edge with the top of the scan beam similarly to the way that the AEL is ordered by the intersection values with the bottom of the scan beams. The IL is a list of nodes specifying the two intersecting edges and also the intersection itself. It is sorted in an increasing order by the y-coordinate of the intersection. The SEL is initialized to empty. One then makes a pass over the AEL comparing the top x-value of the current edge with the top x-values of the edges in the SEL starting at the right of the SEL. There will be an intersection each time the AEL edge has a smaller top x-value than the SEL edge. Note that the number of intersections that are found is the same as the number of edge exchanges in the AEL it takes to bring the edge into its correct place at the top of the scan beam.
Intersection points of edges are basically treated as vertices. Such “vertices” will be classified in a similar way as the regular vertices. If we get a local maximum, then there are two cases. If two unlike edges intersect, then a contributing edge becomes a noncontributing edge and vice versa. This is implemented by simply swapping the output polygon pointers. If two like edges intersect, then a left edge becomes a right edge and a right edge becomes a left edge. One needs to swap the intersecting edges in the AEL to maintain the x-sort.
This finishes our discussion of the Vatti algorithm in the case where there are no horizontal edges. Now we address the more complicated general case that allows horizontal edges to exist. (However, we never allow edges to overlap, that is, where they share a common segment.) The only changes we have to make are in procedure ProcessEdgesInAEL. On an abstract level, it is easy to see how horizontal edges should be handled. The classification of vertices described above should proceed as if such edges were absent (had been shrunk to a point). Furthermore, if horizontal edges do not intersect any other edge, then for all practical purposes they could be ignored. The problems arise when intersections exist.
Imagine that the polygons were rotated slightly so that there were no horizontal edges. The edges that used to be horizontal would now be handled without any problem. This suggests how they should be treated when they are horizontal. One should handle horizontal edges the same way that intersections are handled. Note that horizontal edge intersections occur only at the bottom or top of a scan beam. Horizontal edges at local minima should be handled in the AddNewBoundPairs procedure. The others are handled as special cases in that part of the algorithm that tests whether or not an edge ends in the current scan beam. If it does, we also need to look for horizontal edges at the top of the current scan beam and the type classification of a vertex should then distinguish between a local maximum, left intermediate vertex, or right intermediate vertex cases. The corresponding procedures need to continue scanning the AEL for edges that intersect the horizontal edge until one gets past it. One final problem occurs with horizontal edges that are oriented to the left. These would be detected too late, that is, by the time one finds the edge to which they are the successor, we would have already scanned past the AEL edges that intersected them. To avoid this, the simplest solution probably is to make an initial scan of the AEL for all such edges before one checks events at the top of the scan beam and put them into a special left-oriented horizontal edge list (LHL) ordered by the x-values of their left endpoints. Then as one scans the AEL one needs to constantly check the top x-value of an edge for whether it lies inside one of these horizontal edges.
This completes our description of the basic Vatti algorithm. The algorithm can be optimized in the common case of rectangular clip bounds. Another optimization is possible if the clip polygon is fixed (rectangular or not) by computing its bounds only once and initializing the LML to these bounds at the beginning of a call to the clip algorithm.
An attractive feature of Vatti’s algorithm is that it can easily be modified to generate trapezoids. This is particularly convenient for scan line-oriented rendering algorithms. Each local minimum starts a trapezoid or breaks an existing one into two depending on whether the local minimum starts with a left-right (contributing case) or right-left (noncontributing case) edge pair. At a contributing local minimum we create a trapezoid. Trapezoids are output at local maxima and left or right intermediate vertices. A noncontributing local minimum should output the trapezoid it is about to split and update the trapezoid pointers of the relevant edges to the two new trapezoids. Vatti compared the performance of the trapezoid version of his algorithm to the Sutherland-Hodgman algorithm and found it to be roughly twice as fast for clipping (the more edges, the more the improvement) and substantially faster if one does both clipping and filling. Because Section 14.4 will describe a special case of the trapezoid form of the Vatti algorithm for use with trimmed surfaces, we postpone any further details on how to deal with trapezoids to there.
Finally, we can also use the Vatti algorithm for other operations than just intersection. All we have to do is replace the classification rules. For example, if we want to output the union of two polygons, use the rules
Local minima of the subject polygon that lie outside the clip polygon and local minima of the clip polygon that lie outside the subject polygon should be treated as contributing local minima.
For the difference of two polygons (subject polygon minus clip polygon) use the rules
Local minima of the subject polygon that lie outside the clip polygon should be treated as contributing local minima.