Polygon Clipping Algorith
This page is mainly a based on a forum discussion I had on GameDev in 2003. Someone may still find it helpful or interesting.
Author
Robert Andersson <robert on profundis. se (på=@)>
Paper
Here is the old "paper" that describes the algorithm in detail: Polygon Clipping Algorithm (Word document).
Code Example
Here is a C++ implementation of this algorithm. It is not optimized and its main purpose is to demonstrate how it works.
DISCLAIMER: Use it at your own risk. I'm not responsible if it causes your computer to blow up or anything.
Step-by-step Illustration
I wrote down a step-by-step illustration of how my algorithm works.
The current point is (1). It is outside the 1st clip region, so we split it:
Because (1a)'s next point (4) is inside the 1st clip region, we move the point. It is traced on the line towards point (4):
Point (1a) is now inside all clip regions, therefor we're done with it. Next up is point (1b). Its next point (2) is also inside the 1st clip, so we trace it on that line:
All well. Point (2) is inside the 1st, 2nd and 3rd clip region, but outside the 4th. We split it:
Point (2a)''s next point is inside the 4th clip region, so we trace it, as well as with point (2b):
On to point (3). It is outside the 2nd clip region, so it gets split:
Point (3a)''s next point is (2b) which is inside the current clip region, so it is traced:
The same is true for point (3b). Note here that this clip region does not respect the X-value at all:
Hmm... point (3b) is still outside the clip rectangle, namely the 3rd clip region. We split it:
...and, point (3ba) is traced towards (3a):
Now, interesting stuff occurs. Point (3bb)'s next point is point (4), which is also outside the 3rd clip region. When this happens, we disconnects/removes the point:
Onto point (4) which is outside the 3rd clip region. Lets split it:
What happens now, is a bit special and kind of optimazation. Accordning to the rules (4a) should be moved to same position as point (3ba), but when the next point's x-position is equal with the clip regions x-position we behave as it had been outside it. In that case we remove it:
Finally, the last step is to trace (4b) towards (1a).
And we're done!