Graphics Reference
In-Depth Information
Line-clipping algorithms:
Category
Clip Polygon
Comments
Cohen-Sutherland
(2)
rectangular
The classic line-clipping algorithm. Still
popular because it is so easy to implement.
Cyrus-Beck
(4)
convex
Liang-Barsky
(2)
rectangular
Faster than Cohen-Sutherland.
Still popular. Easy to implement.
Nicholl-Lee-Nicholl
(1)
rectangular
Purely two-dimensional.
Polygon-clipping algorithms:
Category
Clip Polygon
Comments
Sutherland-Hodgman
(3)
convex
Weiler
(3), (4)
arbitrary
Liang-Barsky
(4)
rectangular
Maillot
(1)
rectangular
Vatti
(1)
arbitrary
Fast, versatile, and can generate a trape-
zoidal decomposition of the intersection.
Greiner-Hormann
(1)
arbitrary
As general as Vatti. Simpler and potentially
faster, but no trapezoidal decomposition.
Line-clipping algorithms fall into two types: those that use encoding of the end-
points of the segment (Cohen-Sutherland) and those that use a parameterization of
the line determined by the segment (Cyrus-Beck, Liang-Barsky, and Nicholl-Lee-
Nicholl). In Section 4.6 we discuss a hybrid of the two approaches that works well for
the clipping needed in the graphics pipeline.
Frequently, one needs to clip more than one edge at a time, as is the case when
one wants to clip one polygon against another. One could try to reduce this prob-
lem to a sequence of line-clipping problems, but that is not necessarily the most
efficient way to do it, because, at the very least, there would be additional book-
keeping involved. The clipped figure may involve introducing some vertices that were
not present in the original polygon. In Figure 3.1 we see that the corners A and B
Figure 3.1.
Turning points in polygon clipping.
Search WWH ::




Custom Search