Archived

This topic is now archived and is closed to further replies.

CuteBug

Polygon Clipping Algorithm

Recommended Posts

Hey thank u... but actually what I wanted to know was that if we had a polygon like this




/\ V1
/ \
/ \
/ \
V1 / \ V2
\ /
\ /
\ /
\ /
\/ V3


and we had to clip it against a rectangle in such a way that this polygon is at the left bottom corner of the rectangle


-----------------
| b |
| /\ |
|/ \ |
a / \ |
/| \ c |
/ -------\---------
\ d /
\ /
\ /
\ /
\/

Thru the polygon clipping algorithm we can obtain the points a, b and c...
but how do we obtain point d?

-----------------
| b |
| /\ |
|/ \ |
a / \ |
| \ c |
d -------\---------




"A byte is a large bit to crunch!"

Share this post


Link to post
Share on other sites
Usually, points such as D are generated by clipping the shape to each edge individually, one after another. Search for the Sutherland-Hodgman algorithm for a good starting point.

Btw, use [ source ] and [ /source ] tags for ascii graphics.

Share this post


Link to post
Share on other sites
Sorry abt the previous reply... it got a little messed up... this is what I wanted to convey...

actually what I wanted to know was that if we had a polygon like this




........................./\.V1
......................../**\
......................./****\
....................../******\
..................V1./********\.V21
.....................\********/
......................\******/
.......................\****/
........................\**/
.........................\/ V3


and we had to clip it against a rectangle in such a way that this polygon is at the left bottom corner of the rectangle


.....................-----------------
.....................|^b^^^^^^^^^^^^^|
.....................|^/\^^^^^^^^^^^^|
.....................|/**\^^^^^^^^^^^|
...................a./****\^^^^^^^^^^|
..................../|**** \^c^^^^^^^|
.................../*-------\---------
...................\*d******/
....................\******/
.....................\****/
......................\**/
.......................\/

Thru the polygon clipping algorithm we can obtain the points a, b and c...
but how do we obtain point d?

..................-----------------
..................|^b^^^^^^^^^^^^^|
..................|^/\^^^^^^^^^^^^|
..................|/**\^^^^^^^^^^^|
................a./****\^^^^^^^^^^|
..................|*****\^c^^^^^^^|
..................-------\---------
..................d







"A byte is a large bit to crunch!"

Share this post


Link to post
Share on other sites
That is exactly what my algorithm does. It should have featured a few illustrations.

The purpose of that algorithm is to transform any polygon so that all its vertices are within a given rectangle, without changing any (visible) angles within that rectangle.

Even though my description of it may be fuzzy, it does work and the basic idea is very simple. I''ll be ready to explain if you have questions about it.

Share this post


Link to post
Share on other sites
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!

Now I''m off to look at hockey!


Share this post


Link to post
Share on other sites
CuteBug, there's a very efficient Sutherland-Hodgman clipper in swShader. It does view frustum clipping with homogeneous coordinates but it can easily be used for 2D clipping also.

CWizard, your illustrations are -very- nice. How did you create them? I once wanted to write a tutorial but I stopped because I didn't know how to create such nice looking images.



[edited by - c0d1f1ed on May 3, 2003 4:39:02 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by C0D1F1ED
CWizard, your illustrations are -very- nice. How did you create them? I once wanted to write a tutorial but I stopped because I didn''t know how to create such nice looking images.
I did it the hard way, although Photoshop gave a little help.

If it''s of any interst, you can download the .psd file: gd-pca-ill1.psd.zip

Share this post


Link to post
Share on other sites
quote:
Original post by CuteBug
Well CWizard, thanks a lot.
But will your method work for convex polygons as well?
Yes; any polygon (I think/hope). At least all my test cases have worked.
quote:
And how do we split the vertex into two?
As you can see in the example above, the original polygon has 4 vertices and the clipped has 7. Every vertex that is outside the clip rectangle is splitted and then either moved or removed.

A quick summary of the algorithm:

Have a list/vector of the vertices, and have an index to the current vertex.

Each vertex is tested by 4 "clip regions", which represents one of the clip rectangle''s sides. In my paper and above, these are in order: 1) top, 2) bottom, 3) left, 4) right.

If the vertex is inside all of the "clip regions", and thereby the whole clip rectangle, we proceed to the next point by increasing our index to the current vertex.

Otherwise, we split the vertex into two on the same spot. As optimization trick we can remove the vertex instead, if both neighbor vertices are also outside the same "clip region".

1st "sub-vertex": If the previous vertex is outside the "clip region", or at its edge, remove the 1st sub-vertex. Otherwise we move it. This is simple, because we know either the X- or Y-coordinate of the target position, and solve this easily with the line equation.

2st "sub-vertex": If the next vertex is outside the "clip region", or at its edge, we remove this 2nd sub-vertrex. Otherwise we move it.

There are 3 possibles things that could have happened here:
1) both "sub-vertices" were moved,
2) one of them were move and the other removed, or
3) both removed.
In either case we need to restart the (clip region) testing of the current vertex. The current vertex is for case 1; the 1st sub-vertex, for case 2; the remaining sub-vertex, or for case 3 the next vertex.


Just pick out a paper and draw a clip region and a polygon to clip. Then, follow these steps (the ones in the document rather), and you should see how it all works and why.

Share this post


Link to post
Share on other sites
Ok, I thought I should put up some nice code here, but couldn't figure out a way to get white background for it, and not using [ source ] tags.

Anyway, I made a C++ implementation of this algorithm. It is not optimized and its main purpose is to demonstrate how it works. You, CuteBug, can try to let it operate on one of your polys and see if the result is what you want:

Source, HTML formatted (gd-polyclip-src.cpp.html)
Source, original (gd-polyclip-src.cpp)

DISCLAIMER: Use it at your own risk. I'm not responsible if it causes your computer to blow up or anything.

EDIT: I had misnamed the source file on the server, so it was a 404. Fixed now.

[edited by - CWizard on May 4, 2003 12:43:08 PM]

Share this post


Link to post
Share on other sites
Please let me know how it works. I did never implement it really before, so I''m not sure about that it works flawlessly, although it seems solid. Note that the code I provided may need some tweaking. For example, it will most likely crash if you have two vertices at the exact same position next to eachother, due to a division by zero.

Share this post


Link to post
Share on other sites