Jump to content
  • Advertisement

Archived

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

CuteBug

Polygon Clipping Algorithm

This topic is 5523 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Can anyone suggest me the method to clip a polygon of n vertices against a rectangular boundary... Thx in advance "A byte is a large bit to crunch!"

Share this post


Link to post
Share on other sites
Advertisement
Haha! I actually had to think up an algorithm for doing that, and wrote an article about it (for my own reference while implementing it).

Unedited, unreviewed: Polygon Clipping Algorithm (Word document)

Comments are appricieated, if it relates to what you want.


Share this post


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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!