Introduction
Planar clipping algorithms rank as probably the second most important type of algorithm in computer graphics, following right behind linedrawing algorithms in importance. Mathematically to clip one set against another means to find their intersection. In practice, one usually wants also to get this intersection in terms of some predefined data structure.
This chapter discusses some of the wellknown clipping algorithms along with some newer and more efficient ones. The algorithms fall into two types: the lineclipping algorithms, which clip single line segments against rectangular or convex regions, and polygonclipping algorithms, which clip whole polygons against other polygons. The following terminology is used:
Definition. The polygon being clipped is called the subject polygon and the polygon that one is clipping against is called the clip polygon.
The choice of algorithms to discuss was motivated by the following considerations:
(1) It is currently one of the best algorithms of its type.
(2) It is not the best algorithm but still used a lot.
(3) The algorithm was interesting for historical reasons and easy to describe.
(4) It involved the use of some interesting techniques, even though it itself is no longer a recommended method.
Below we list the algorithms described in this chapter and categorize them by considerations (l)(4) above. We also state any assumption regarding their clip polygon and make some comments about them. Some of the algorithms will be discussed in great detail. Others are only described very briefly, especially if they fall under heading (3) or (4) above.
Lineclipping algorithms: 


Category 
Clip Polygon 
Comments 
CohenSutherland 
(2) 
rectangular 
The classic lineclipping algorithm. Still popular because it is so easy to implement. 
CyrusBeck 
(4) 
convex 

LiangBarsky 
(2) 
rectangular 
Faster than CohenSutherland. 
Still popular. Easy to implement. 

NichollLeeNicholl 
(1) 
rectangular 
Purely twodimensional. 
Polygonclipping algorithms:

Category 
Clip Polygon 
Comments 
SutherlandHodgman 
(3) 
convex 

Weiler 
(3), (4) 
arbitrary 

LiangBarsky 
(4) 
rectangular 

Maillot 
(1) 
rectangular 

Vatti 
(1) 
arbitrary 
Fast, versatile, and can generate a trapezoidal decomposition of the intersection. 
GreinerHormann 
(1) 
arbitrary 
As general as Vatti. Simpler and potentially faster, but no trapezoidal decomposition. 
Lineclipping algorithms fall into two types: those that use encoding of the endpoints of the segment (CohenSutherland) and those that use a parameterization of the line determined by the segment (CyrusBeck, LiangBarsky, and NichollLeeNicholl). 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 problem to a sequence of lineclipping problems, but that is not necessarily the most efficient way to do it, because, at the very least, there would be additional bookkeeping 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 of the window need to be added.
Figure 3.1. Turning points in polygon clipping.
These corners are called turning points. The term was introduced in [LiaB83] and refers to the point at the intersection of two clipping region edges that has to be added to preserve the connectivity of the original polygon. This is the reason that polygon clipping is treated separately from line clipping.
Polygonclipping algorithms fall into roughly two categories: turningpointbased algorithms like the LiangBarsky and Maillot algorithms, which rely on quickly being able to find turning points explicitly, and the rest. Turningpointtype algorithms scan the segments of the subject polygon and basically clip each against the whole window. The rest tend to find turning points implicitly, in the sense that one does not look for them directly but that they are generated “automatically” as the algorithm proceeds. The SutherlandHodgman algorithm treats the clip polygon as the intersection of halfplanes and clips the whole subject polygon against each of these halfplanes one at a time. The Weiler, Vatti, and GreinerHormann algorithms find the turning points from the clip polygon in the process of tracing out the bounding curves of the components of the polygon intersection, although they trace the boundaries in different ways.
The chapter ends with some comments on clipping text. Some additional comments on clipping when homogeneous coordinates are used can be found in the next chapter in Sections 4.6 and 4.10.
LineClipping Algorithms
CohenSutherland Line Clipping
This section describes an algorithm that solves the following planar clipping problem:
Given a segment [P1, P2], clip it against a rectangular window and return the clipped segment [Q1, Q] (which may be empty if the original segment lies entirely outside the window).
The CohenSutherland lineclipping algorithm is probably the most popular of such algorithms because of its simplicity. It starts out by encoding the nine regions into which the boundary lines of the window divide the whole plane with a 4bit binary code. See Figure 3.2. If P is an arbitrary point, then let c(P) = x3x2x1x0, where xi is either 0 or 1, define this encoding. The bits xi have the following meaning:
Figure 3.2. CohenSutherland point codes.
The algorithm now has three steps:
Step 2. Check if the segment can be trivially rejected, that is, using the bitwise logical or and and operators, test whether
In case (a), the segment is entirely contained in the window since both endpoints are and the window is convex. Return
In case (b), the segment is entirely outside the window. This follows because the endpoints will then lie in the halfplane determined by a boundary line that is on the other side from the window and halfplanes are also convex. Return the empty segment.
Step 3. If the segment cannot be trivially rejected, then we must subdivide the segment. We clip it against an appropriate boundary line and then start over with Step 1 using the new segment. Do the following to accomplish this: (a) First find the endpoint P that will determine the line to clip against.
(b) The line to clip against is determined by the leftmost nonzero bit in c(P). For the example in Figure 3.3,, and the line to clip
against is the left boundary line of the window. Let A be the intersection of the segment [P,Q] with this line.
(c) Repeat Steps 13 for the segment [A,Q].
The algorithm will eventually exit in Step 2.
With respect to the efficiency of the CohenSutherland algorithm, note that the encoding is easy since it simply involves comparing a number to some constant (the boundary lines of the window are assumed to be horizontal and vertical). Step 3 is where the real work might have to be done. We shall have to clip four times in the worst case. One such worst case is shown in Figure 3.3 where we end up having to clip successively against each one of the window boundary lines generating the intersection points A, B, C, and D.
Figure 3.3. CohenSutherland lineclipping example.
Algorithm 3.2.1.1 is an implementation of the justdescribed algorithm. To be more efficient, all function calls should be replaced by inline code.
Finally, note that the encoding found in the CohenSutherland lineclipping algorithm is driven by determining whether a point belongs to a halfplane. One can easily generalize this to the case where one is clipping a segment against an arbitrary convex set X. Assume that X is the intersection of halfplanesThe encoding of a point P is now a kbit numberwhere
Using this encoding one can define a clipping algorithm that consists of essentially the same steps as those in the CohenSutherland algorithm. One can also extend this idea to higher dimensions and use it to clip segments against cubes. See Section 4.6.
CyrusBeck Line Clipping
The CyrusBeck lineclipping algorithm ([CyrB78]) clips a segment S against an arbitrary convex polygonSince X is convex, it is
the intersection of halfplanes determined by its edges. More precisely, for each segmentdenotes the point Q1) we can choose a normal vector Ni, so that X can be expressed in the form
With this choice, the normals will point “into” the polygon. It follows that
In other words, we can clip the segment S against X by successively clipping it against the halfplanes Hi. This is the first basic idea behind the CyrusBeck clipping algorithm. The second, is to represent the line L determined by the segment S parametrically in the formand to do the clipping with respect to the parameter t.
Algorithm 3.2.1.1. The CohenSutherland lineclipping algorithm.
Algorithm 3.2.1.1. The CohenSutherland lineclipping algorithm.
Let Li be the line determined by the segmentDefine intervals as follows:
Case 1: L is parallel to Li.
Case 2: L is not parallel to Li.
In this case L will intersect Li in some pointWe distinguish between the case where the line L “enters" the halfplane Hi and where the line "exits" Hi.
See Figure 3.4, where a segmentis being clipped against a triangle
Note that finding the intersection point P in Case 2 is easy. All we have to do is solve the equation
Now let Io = [ao,bo] = [0,1]. The interval Io is the set of parameters of points which lie is S. It is easy to see that the interval is the set of parameters for the points in
Figure 3.4. CyrusBeck line clipping.
In other words, if I is not empty, then
We shall explain this process with the example in Figure 3.4. In this example,
which clearly gives the right answer.