2D Polygon intersection testing - Printable Version +- iDevGames Forums (http://www.idevgames.com/forums) +-- Forum: Development Zone (/forum-3.html) +--- Forum: Game Programming Fundamentals (/forum-7.html) +--- Thread: 2D Polygon intersection testing (/thread-3993.html) 2D Polygon intersection testing - unknown - Aug 15, 2006 08:21 AM I have two polygons composed of a number of triangles each and I need to write code that will test if they are intersecting at any time. Ill calculate an AABB (axis aligned bounding box) for each and test if they intersect first of all, but after that im not sure what to do. I could test for each triangle against each other triangle but I'd like to know if there's a better method than this before programming it, because this function will be called several times per frame if a collision is likley. thanks in advance.. 2D Polygon intersection testing - ThemsAllTook - Aug 15, 2006 09:26 AM If your polygons have a huge number of triangles, you might be able to space partition them. If they don't, I wouldn't worry about it and just test against every triangle. Calling a function "several times per frame" generally isn't a concern unless that function is astronomically slow... or if by "several" you mean "several thousand". 2D Polygon intersection testing - Skorche - Aug 15, 2006 10:42 AM Break it into convex polygons and do a SAT test. If you don't need a collision point or normal and your geometry is rigid, this is really easy and relatively fast. 2D Polygon intersection testing - unknown - Aug 15, 2006 11:02 AM ThemsAllTook Wrote:If your polygons have a huge number of triangles, you might be able to space partition them. If they don't, I wouldn't worry about it and just test against every triangle. Calling a function "several times per frame" generally isn't a concern unless that function is astronomically slow... or if by "several" you mean "several thousand". The reason I worry about using triangle/triangle checks is my code looks like this: Code: ```    int TriangleIntersectsTriangle(CVector A, CVector B, CVector C, CVector D, CVector E, CVector F) {         if(BPPointInTriangle(A, D, E, F))             return 1;         if(BPPointInTriangle(B, D, E, F))             return 1;         if(BPPointInTriangle(C, D, E, F))             return 1;         if(BPPointInTriangle(D, A, B, C))             return 1;         if(BPPointInTriangle(E, A, B, C))             return 1;         if(BPPointInTriangle(F, A, B, C))             return 1;                  if(LineSegmentsIntersect(A, B, D, E))             return 1;         if(LineSegmentsIntersect(A, B, E, F))             return 1;         if(LineSegmentsIntersect(A, B, F, D))             return 1;                  if(LineSegmentsIntersect(B, C, D, E))             return 1;         if(LineSegmentsIntersect(B, C, E, F))             return 1;         if(LineSegmentsIntersect(B, C, F, D))             return 1;                  if(LineSegmentsIntersect(C, A, D, E))             return 1;         if(LineSegmentsIntersect(C, A, E, F))             return 1;         if(LineSegmentsIntersect(C, A, F, D))             return 1;                  return 0;     }``` which is a large amount of computation, especially if that function is being called for each triangle 5/6 times a frame to do a binary search to find the time or collision accurately. Skorche Wrote:Break it into convex polygons and do a SAT test. If you don't need a collision point or normal and your geometry is rigid, this is really easy and relatively fast. My geometry is rigid, but I do need to find the point of collision as well as the normal, what does SAT stand for? I will look it up and see if I can apply it, if not hopefully triangle checks will not be too slow. 2D Polygon intersection testing - Skorche - Aug 15, 2006 11:36 AM SAT = Seperating Axis Theorem http://www.harveycartel.org/metanet/tutorials/tutorialA.html You 'could' get the collision point and normal even if you are splitting a concave poly, it just wouldn't be as simple. The collision test would still be a lot simpler though. Probably faster too. 2D Polygon intersection testing - TomorrowPlusX - Aug 15, 2006 11:48 AM I don't know if you're married to implementing it yourself, but ODE's trimesh collider is pretty damn quick. Not hard to use, either. 2D Polygon intersection testing - unknown - Aug 15, 2006 04:17 PM Thanks for the link, it wouldn't be hard to turn my triangulated polygon into a series of convex polygons so ill remember SAT in case the triangle check proves to be too slow. Im trying to implement this from scratch so im going to avoid using somthing like ODE. Thanks for your advice everyone.