Graphics Reference
In-Depth Information
SEGM means that the segment is inside the clipping region
CLIP means that the segment is only partly inside the clipping region
NOSEGM means that the segment is outside the clipping region
In conclusion, Maillot claims the following for his algorithm and implementation:
(1) It is up to eight times faster than the Sutherland-Hodgman algorithm and up
to three times faster than the Liang-Barsky algorithm.
(2) It can be implemented using only integer arithmetic.
(3) It would be easy to modify so as to reduce the number of degenerate edges.
With regard to point (3), recall again that the Sutherland-Hodgman and Liang-Barsky
algorithms also produce degenerate edges sometimes. The Weiler and Vatti algorithm
are best in this respect.
3.3.5
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 rectan-
gles. 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) poly-
gons. 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 algo-
rithms. 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 poly-
gons. 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 p 0 , p 1 ,...,
p 8 shown in Figure 3.18(a). The two left bounds have vertices p 0 , p 8 , p 7 , p 6 and p 4 , p 3 ,
p 2 , respectively. The two right bounds have vertices p 0 , p 1 , p 2 and p 4 , p 5 , p 6 .
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
Search WWH ::




Custom Search