Clipping - Computer Graphics and Geometric Modeling - page 70

of the window need to be added. These corners are called turning points . The term
was introduced in [LiaB83] and refers to the point at the intersection of two clip-
ping 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.
Polygon-clipping algorithms fall into roughly two categories: turning-point-based
algorithms like the Liang-Barsky and Maillot algorithms, which rely on quickly being
able to find turning points explicitly, and the rest. Turning-point-type 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 Sutherland-Hodgman algorithm treats the clip polygon as the inter-
section of halfplanes and clips the whole subject polygon against each of these half-
planes one at a time. The Weiler, Vatti, and Greiner-Hormann 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 com-
ments on clipping when homogeneous coordinates are used can be found in the next
chapter in Sections 4.6 and 4.10.

3.2 Line-Clipping Algorithms

3.2.1 Cohen-Sutherland Line Clipping

This section describes an algorithm that solves the following planar clipping
problem:

Given a segment [ P 1 , P 2 ], clip it against a rectangular window and return the clipped segment
[ Q 1 , Q 2 ] (which may be empty if the original segment lies entirely outside the window).

The Cohen-Sutherland line-clipping 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 4-bit binary
code. See Figure 3.2. If P is an arbitrary point, then let c( P ) = x 3 x 2 x 1 x 0 , where x i is
either 0 or 1, define this encoding. The bits x i have the following meaning:

Figure 3.2. Cohen-Sutherland point codes.