Polygon Clipping

Polygon clipping is one of those humble tasks computers do all the time. It's a basic operation in creating graphic output of all kinds.

There are several well-known polygon clipping algorithms, each having its strengths and weaknesses. The oldest one (from 1974) is called the Sutherland-Hodgman algorithm. In its basic form, it is relatively simple. It is also very efficient in two important cases, one being when the polygon is completely inside the boundaries, and the other when it's completely outside.

The Laing-Barsky algorithm (1983) is a good deal more complicated, but in certain cases fewer intersections need to be calculated than for Sutherland-Hodgman. Therefore, it may be somewhat faster when many polygon lines intersect with the clipping boundaries. However, it is more sensitive to 'nasty' polygons.

The Weiler algorithm (1977) is even more complicated, but it is the one you'll need if you want to clip a polygon against a non-rectangular window.

Even more ways to clip a polygon exist. None of them is totally perfect. Often, it is possible to feed a weird polygon to an algorithm and retrieve an incorrect result. One of the vertices will disappear, or a ghost vertex will be created. Therefore, the hunt for the perfect clipping algorithm is still open.

A polygon is generally stored as a collection of vertices. Any clipping algorithm takes one collection, and outputs a new collection. A clipped polygon, after all, is also a polygon. Notice that the clipped polygon often will have more vertices than the unclipped one, but it can also have the same number, or less. If the unclipped polygon lies completely outside the clipping boundary, the clipped polygon even has zero vertices.

Sutherland-Hodgman

After some investigation, I opted for the old and trusted Sutherland-Hodgman method to attack the problem. For the project I was working on, the non-rectangular capabilities of Weiler would be overkill. With the current CPUs and their fast floating point operations, the slightly higher efficiency of Laing-Barsky hardly makes sense. In fact, after a rather crude experiment, I suspect it to be even somewhat slower.

Sutherland-Hodgman uses a divide-and-conquer strategy to attack the problem. First, it clips the polygon against the right clipping boundary. The resulting, partly clipped polygon is then clipped against the top boundary, and then the process is repeated for the two remaining boundaries. (Of course, it also works in another order.) In a way, it is the most natural thing to do. If you had to clip a paper polygon with a pair of scissors, you would probably proceed the same way.

Sutherland-Hodgman's divide-and-conquer strategy. To clip a polygon against a rectangular boundary window, successively clip against each boundary.

To clip against one boundary, the algorithm loops through all polygon vertices. At each step, it considers two of them, called 'previous' and 'current.' First, it determines whether these vertices are inside or outside the clipping boundary. This, of course, is simply a matter of comparing the horizontal or vertical position to the boundary's position.

Then, it applies the following simple rules:

If 'previous' and 'current' are both inside: Output 'current.'
If 'previous' is inside, and 'current' is outside: Output the intersection point of the corresponding edge and the clipping boundary.
If 'previous' and 'current' are both outside: Do nothing.
If 'previous' is outside, and 'current' is inside: Output the intersection point, and then output 'current.'

This way, you get a new polygon, clipped against one boundary, and ready to be clipped against the next boundary. The method works, but has one disadvantage: To clip against all four boundaries, you have to store the intermediate, partly clipped polygons. It's evident that this is a costly operation.

Luckily, there are ways to avoid the intermediate storage. Instead of storing an output point, you can send it to the next stage immediately, where it can be clipped against the next boundary.

The classical way to do this is to make one general boundary-clipping function, which calls itself recursively to put a vertex to the next stage. An extra parameter tells the function which boundary to use for clipping. Inside the function, a few switch statements account for the differences.

A somewhat faster option is to create separate functions for the four boundaries, thus eliminating the nasty switch statements. However, this means developing and debugging four very similar functions, which is an open invitation for all kinds of trouble.

Polygon Clipping

Template Juggling

Luckily, we now have C++ templates. They are the ideal means to create several pieces of code with subtle differences.

My SutherlandHodgman class is a nice example. It isn't a template itself, but uses templates internally. Inside it, a ClipStage template class is defined. It is the workhorse of the clipping process, and implements the four rules stated above.

ClipStage has two template parameters. One is a class from which ClipStage is derived, and which implements the specifics of each boundary. Four of these classes are defined, having names like BoundaryRight and BoundaryTop. These, by the way, are templated classes themselves. To keep the code readable, I typedefed the resulting ClipStage-variants with names like ClipRight and ClipTop.

The cleverest thing, at least in my humble opinion, is ClipStage's second template parameter. This is another ClipStage-variant, and it stands for the next stage in the clipping process.

So, we have things like:

   typedef ClipStage<BoundaryTop, ClipLeft> ClipTop;
   typedef ClipStage<BoundaryRight, ClipTop> ClipRight;

In a very concise way, this says that ClipRight is derived from BoundaryRight, and outputs to ClipTop. Likewise, ClipTop is derived from BoundaryTop, and outputs to ClipLeft.

ClipBottom, which is the last ClipStage-variant in the chain, outputs to yet another class, called OutputStage. This has the same interface as the ClipStage template, but does nothing more than append its input to the final output vector.

The net result of all this template juggling is one neat, black-box class called SutherlandHodgman. Its constructor takes a rectangle to define the clipping boundaries, and it has only one, very simple, member function:

   void Clip(pointVector& input, pointVector& clipped);

Just feed the function a vector of points defining a polygon, and out comes a clipped polygon in the second vector.

I commented the code heavily. I suppose that if my attempts were really professional, I should have templated the whole bunch of classes on the data types as well. I refrained from that, because it would make the code even more complicated.

Demo

To prove that it all works, I threw together a demo in MFC. Just draw a closed polygon by clicking the vertices. A small circle near the cursor indicates that the next click will close the polygon. As soon as the polygon is closed, SutherlandHodgman will clip it. Believe me, it does so really fast.

References

Most good books on computer graphics will have a section about polygon clipping. I used the old and trusted Computer Graphics, Principles and Practice, 2nd Edition, by James D. Foley, Andries van Dam, Steven K. Feiner, and John F. Hughes. Addison-Wesley, 1995. ISBN: 0201848406.

Searching the Internet for 'Sutherland Hodgman' yields dozens of useful, albeit very similar sites. Some are:



Downloads

Comments

  • There are no comments yet. Be the first to comment!

Leave a Comment
  • Your email address will not be published. All fields are required.

Top White Papers and Webcasts

  • With JRebel, developers get to see their code changes immediately, fine-tune their code with incremental changes, debug, explore and deploy their code with ease (both locally and remotely), and ultimately spend more time coding instead of waiting for the dreaded application redeploy to finish. Every time a developer tests a code change it takes minutes to build and deploy the application. JRebel keeps the app server running at all times, so testing is instantaneous and interactive.

  • Instead of only managing projects organizations do need to manage value! "Doing the right things" and "doing things right" are the essential ingredients for successful software and systems delivery. Unfortunately, with distributed delivery spanning multiple disciplines, geographies and time zones, many organizations struggle with teams working in silos, broken lines of communication, lack of collaboration, inadequate traceability, and poor project visibility. This often results in organizations "doing the …

Most Popular Programming Stories

More for Developers

Latest Developer Headlines

RSS Feeds