Sign in to follow this  

Triangle_Polygon intersection test

This topic is 3669 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

Hi all, i need some fast way to detect no_intersection between 2 coplanar triangle and convex polygon. what tests can be done? and i was thinking about having a bounding circle around the polygon, maybe that would save me some time and tests.. i am stuck, and i need this to go on with my project. any ideas plz? THanks for the help

Share this post


Link to post
Share on other sites
I'm certainly no authority on the subject, but I believe that an SAT test would work well here. You can search the forums or the web for more information. The basic idea is to find an axis that separates the two polygons. If one exists, then they can't possibly intersect. I believe this test also has the advantage of being able to early-out once an axis is detected. There might be ways to optimize the test if one of the polygons is always a triangle, but again someone with more background in collision detection and SAT would have to step in here :)

Share this post


Link to post
Share on other sites
the thing is that i dont really need it to be accurate,

i'll give some insights to what i am doing, maybe it would be easier...

i am doing a coplanar triangle-polygon intersection test, so that test will check the line segments of the triangle and polygon for intersection,
in case of intersection, then we have intersection, if not, then there is no intersection...


what i wanted is, instead of having to run this segment-segment test, i only want to run it when there is a big chance that they intersect..

so i wanted some tests (cheap ones) to direclty return NO_Intersection so i can skip the test...

i hope i am making some sense :)

Share this post


Link to post
Share on other sites
Quote:
Original post by jimgeagea
the thing is that i dont really need it to be accurate,

i'll give some insights to what i am doing, maybe it would be easier...

i am doing a coplanar triangle-polygon intersection test, so that test will check the line segments of the triangle and polygon for intersection,
in case of intersection, then we have intersection, if not, then there is no intersection...


what i wanted is, instead of having to run this segment-segment test, i only want to run it when there is a big chance that they intersect..

so i wanted some tests (cheap ones) to direclty return NO_Intersection so i can skip the test...

i hope i am making some sense :)
Instead of using segment-segment tests for the narrow phase, use the SAT, as suggested by Zipster. It will be faster, more robust, and more accurate (in that performing the intersection test in terms of polygon edges will miss certain cases).

As for an early out, I would think that a circle-circle test would suffice (other options include AABBs and OBBs).

If there are many objects involved you may need a broad phase as well, but that's a different topic.

[Edit: You mention co-planar polygons, but you haven't specified whether this is 2D or 3D. What is this for exactly?]

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Original post by jimgeagea
the thing is that i dont really need it to be accurate,

i'll give some insights to what i am doing, maybe it would be easier...

i am doing a coplanar triangle-polygon intersection test, so that test will check the line segments of the triangle and polygon for intersection,
in case of intersection, then we have intersection, if not, then there is no intersection...


what i wanted is, instead of having to run this segment-segment test, i only want to run it when there is a big chance that they intersect..

so i wanted some tests (cheap ones) to direclty return NO_Intersection so i can skip the test...

i hope i am making some sense :)
Instead of using segment-segment tests for the narrow phase, use the SAT, as suggested by Zipster. It will be faster, more robust, and more accurate (in that performing the intersection test in terms of polygon edges will miss certain cases).

As for an early out, I would think that a circle-circle test would suffice (other options include AABBs and OBBs).

If there are many objects involved you may need a broad phase as well, but that's a different topic.


SAT wouldnt help me, because i want to find where the triangle-polygon intersect... and in order to get those points of intersection, i couldn't think of something other than linesegment/linesegment test..


since we are talking about an early out, i was thinking more about circle - triangle test... but it would be more expensive than circle-circle test right?

PS: the triangle-polygon are in 3D but coplanar.

Share this post


Link to post
Share on other sites
I think it would still be helpful if you were to describe what you're trying to do. Is it a secret? :-D

The SAT can return information about penetration for intersecting objects, or time of intersection and contact manifold for moving objects. If this is for a purpose other than collision detection and response, polygon clipping may be what you're looking for (which is still a little different than a simple series of segment-segment tests).

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
I think it would still be helpful if you were to describe what you're trying to do. Is it a secret? :-D

The SAT can return information about penetration for intersecting objects, or time of intersection and contact manifold for moving objects. If this is for a purpose other than collision detection and response, polygon clipping may be what you're looking for (which is still a little different than a simple series of segment-segment tests).


it is not really a secret, lol
but i wanted to know where exactly the polygon and triangle intersect..

Share this post


Link to post
Share on other sites

This topic is 3669 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this