Clipping - Computer Graphics and Geometric Modeling - page 83

To deal with symmetry only rotations through 90, 180, and 270 degrees about the
origin and reflections about the lines x =-y and the x-axis are needed. These opera-
tions are extremely simple and involve only negation and assignment. See [NiLN87]
for further details.
This finishes our survey of line-clipping algorithms. Next, we turn our attention
to polygon-clipping algorithms.

3.3 Polygon-Clipping Algorithms

3.3.1 Sutherland-Hodgman Polygon Clipping

One of the earliest polygon-clipping algorithms is the Sutherland-Hodgman algorithm
([SutH74]). It is based on clipping the entire subject polygon against an edge of the
window (more precisely, the halfplane determined by that edge which contains the
clip polygon), then clipping the new polygon against the next edge of the window, and
so on, until the polygon has been clipped against all of the four edges. An important
aspect of their algorithm is that one can avoid generating a lot of intermediate data.
Representing a polygon as a sequence of vertices P 1 , P 2 ,..., P n , suppose that we
want to clip against a single edge e . The algorithm considers the input vertices P i one
at a time and generates a new sequence Q 1 , Q 2 ,..., Q m . Each P i generates 0, 1, or 2
of the Q j , depending on the position of the input vertices with respect to e . If we con-
sider each input vertex P , except the first, to be the terminal vertex of an edge, namely
the edge defined by P and the immediately preceding input vertex, call it S , then the
Q 's generated by P depend on the relationship between the edge [ S , P ] and the line L
determined by e . There are four possible cases. See Figure 3.9. The window side of
the line is marked as “inside.” The circled vertices are those that are output. Figure
3.10 shows an example of how the clipping works. Clipping the polygon with vertices
labeled P i against edge e 1 produces the polygon with vertices Q i . Clipping the new
polygon against edge e 2 produces the polygon with vertices R i .
Note that we may end up with some bogus edges. For example, the edge R 5 R 6 in
Figure 3.10 is not a part of the mathematical intersection of the subject polygon with

Figure 3.9. The four cases in Sutherland-

Hodgman polygon clipping.