Triangle_Polygon intersection test
Author
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
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 :)
Author
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 :)
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 :)
Quote:Original post by jimgeageaInstead 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).
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 :)
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?]
Author
Quote:Original post by jykQuote:Original post by jimgeageaInstead 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).
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 :)
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.
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).
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).
Author
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..
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
