Thomas Révész has an MSc in Engineering Physics from the Royal Institute of Technology, Stockholm, Sweden and an MBA from INSEAD, Fontainebleau, France. He currently works with business development of software services at Digital Equipment Services AB in Sweden. His computer-related interests include object-oriented technology and computer graphics.
Introduction
In computer graphics, clipping is the calculation process where invisible and visible parts of a picture are separated from each other to allow for outputting only the visible parts. Clipping is used to limit output to a certain area on the screen, such as in windowing systems where a picture must not be drawn outside its host window's boundaries (Figure 1) .A general clipping system must be able to handle all possible picture components; points, lines, curves, text, etc. The clipping process can often be simplified by breaking down the different picture elements into straight-line segments, which are run through a line clipping algorithm. For instance, clipping a circle would generate chains of small linear segments, forming one or more circular arcs. In the clipping process, the input graphic entity circle has been transformed into the graphic entity line.
However, for some graphic entities it is advantageous to be able to preserve the entity through the clipping process. This is particularly true of polygons — closed outlines bounded by straight edges — which are used to define areas of colours or patterns. An area that is clipped by a rectange is still an area, albeit smaller. Applying a line clipping algorithm to the perimeter of an area would generate picture B in Figure 2, while the desired result has a closed outline as in picture C in Figure 2.
Hence, we must use an algorithm that clips areas rather than line segments. The algorithm differs from a simple line clipping algorithm in that it must close the area outline with appropriate sections of the clipping area edge. To complicate things further, a concave polygon (one that has at least one interior angle greater than 180 degrees) might be clipped into several smaller polygons.
Sutherland-Hodgman's Algorithm
A solution to these problems is Sutherland-Hodgman's algorithm, as described by Newman and Sproull in their excellent Principles of Interactive Computer Graphics (McGraw-Hill, 1979). The algorithm clips a polygon against each clipping edge in turn, thereby generating intermediate polygons as in Figure 3.Figure 3 shows what may happen when a concave polygon is clipped. The output consists of two polygons connected by a degenerate edge. However, for calculation and display purposes the output can still be treated as a single polygon. Degenerate edges do not interfere with the display of areas, since they outline a zero area.
While the input polygons can be of any shape, the clipping area has to be convex. The algorithm relies on the fact that a point that lies on the invisible side of an edge is always outside the clipping area. This is not true for concave clipping areas. Except for this restriction, neither the number of clipping edges nor their shape is limited. It is perfectly possible to clip polygons against a clipping area outlined by, say, three circular arcs.
The algorithm for clipping against a single edge consists of two parts. The first part is applied to every vertex of the polygon, while the second closes the polygon when all the vertices have been processed. At various points the algorithm outputs a vertex, which may be added to a list representing the output polygon. This polygon is then clipped against the next clipping edge and so on.
Listing 1 shows part 1 of the clipping algorithm, which is applied to every vertex. Listing 2 shows part 2, which closes the output polygon.
One would expect the intermediate polygons to require large amounts of storage, but this is not the case. Only two coordinate pairs need to be stored for each clipping edge. Newman and Sproull say: "The algorithm generates the vertices of the output polygon in sequential order and then feeds each of these vertices in the same order to the next step in the process. Instead of storing each output vertex until the step is complete, the vertex can be passed directly to the next step by invoking the same algorithm in a recursive manner."
What makes things complicated is that the clipping process for each edge is a state machine, since the processing depends on whether the received vertex is the first vertex or not. The clipping processes are not necessarily in the same state. For example, several vertices may be clipped against the first edge and discarded until a first visible vertex is output and clipped against the next edge.
This implies that each recursive step of the algorithm must not only be supplied with data about which clipping edge to use, but also with the state of the clipping process against that edge. Implementing this algorithm in C is feasible, but C++ is by far the superior tool. By representing each clipping edge with a C++ object that contains all the necessary information about the edge, including the processing state, the proposed recursion algorithm becomes a processing pipeline (Figure 4) .
Implementation
The C++ implementation of the algorithm consists of two classes: ClipEdge and LinearEdge. While ClipEdge represents a clipping edge in general, LinearEdge is derived from ClipEdge and implements a linear clipping edge.
Class ClipEdge
ClipEdge contains the function add, which is used for assembling ClipEdge objects to a processing pipeline.The main processing functions are vertex and close, which implement the two parts of the algorithm. vertex takes two parameters, the vertex point itself and a reference to an array where generated output is to be stored. close needs only the first and the last polygon vertex for its processing, which are already stored in the object, and therefore takes only the output array as parameter.
vertex and close send the generated output vertices to the function output, which passes them on to the next ClipEdge object in the pipeline. Only at the end of the chain are vertices written to the output array.
In their processing, vertex and close rely on the virtual functions visible and clip. visible tests whether a point is on the visible side of an edge or not and clip clips a straight line against that edge. visible and clip cannot be defined in ClipEdge since they depend on information that is not available in ClipEdge, namely the edge position and shape. Instead, these functions must be defined in a derived class. This requirement has been enforced by declaring the functions as pure virtual. Class objects that contain pure virtual functions cannot be explicitly constructed, but must be created through a derived class.
Clipping edge intersection is detected by XORing the visibility of the current vertex with the visibility of the previous vertex. If one of the vertices is visible and the other invisible, the line between them must intersect the clipping edge. vertex_received is a state flag that indicates whether the ClipEdge object has received a vertex before or not.
Class LinearEdge
Class LinearEdge implements the linear clipping edge. The edge can have any slope and need not be parallel to the coordinate axe.Since most of the work is done by ClipEdge, the LinearEdge class only has to supply the functions visible and clip.
The visibility is checked by simply deeming all points on the right side of the edge invisible. This definition requires a directed line, a vector, which is achieved by using the first constructor parameter as the line starting point and the other as the line end point. (See the sidebar, Checking the Visibility of a Point.) The algorithm assumes that the coordinate system used is right-handed. In right-oriented coordinate systems the X-axis is always "to the right" of the Y-axis. That is, the X-axis points to the right and the Y-axis points upward, or the X-axis points downward and the Y-axis points to the right, etc.
Left-handed coordinate systems are not very common in printed drawings and diagrams, but are sometimes used to address points (pixels) on computer displays. An example is when the origin is located in the upper left corner of the screen with the X-axis pointing to the right and the Y-axis pointing downward.
The line intersection is calculated by using the parameterized definition of the line:
x = x1 + t*(x2 - x1) -infinity < t < +infinity y = y1 + t*(y2 - y1)where (x1, y1) and (x2, y2) are two points on the line, instead of the more common
y = k*x + c -infinity < k, c < +infinitywhere k is the line slope and c the intersection with the Y-axis.The latter definition requires special treatment of vertical lines, while the parameterized definition is direction independent. This is an advantage from an algorithmic point of view. (See the sidebar, Calculating the Intersection between Two Lines.)
The Test Program
The first section in the test program sets up the clipping pipeline. In this case, the clip area is a tilted quadrant with the corner points (150, 75), (225, 150), (150, 225) and (75, 150). Note how the LinearEdge objects are initialized. The interior of the clipping area is to the left of all edges.The definition of the input polygon is self-explanatory. It is followed by the creation of the array that will hold the vertices of the output polygon. With linear edges, the number of output vertices will always be smaller than two times the number of input vertices plus the number of clip area corners.
The clipping is done by feeding the first ClipEdge object with the vertices of the input polygon. When all vertices have been processed, the output polygon is closed and the result can be enjoyed by viewing the output array, preferably by using the polygon drawing primitive of a graphics library. Figure 5 shows the polygon outline before and after clipping.
Summary
Most graphics libraries support clipping, but only against rectangular areas aligned with the coordinate axes. This program offers a more flexible approach to windowing and clipping. It is also gives a first insight into some mathematical tools that can be put to work in graphics applications.Since ClipEdge is an abstract base class, the implementation can be extended easily without changing the existing code. Note that the implementation already supports the use of convex polygons of any size as clipping areas. It is just a matter of inserting the desired number of LinearEdge objects in the processing pipeline.
An extension of the implementation could supply classes for handling non-linear edges, such as circular or elliptical ones. Or, classes could be derived from LinearEdge to handle vertical and horizontal edges only. This would improve performance, since the multiplication and division operations in visible and clip could be replaced by simple comparisons.
Thanks to the object-oriented features of C++, the implementation becomes really compact and flexible. It would be hard to do it as elegant in another language.