## 2D Polygon intersection testing

Sage
Posts: 1,403
Joined: 2005.07
Post: #1
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.

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Moderator
Posts: 1,563
Joined: 2003.10
Post: #2
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".
Sage
Posts: 1,487
Joined: 2002.09
Post: #3
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.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Sage
Posts: 1,403
Joined: 2005.07
Post: #4
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.

Sir, e^iÏ€ + 1 = 0, hence God exists; reply!
Sage
Posts: 1,487
Joined: 2002.09
Post: #5
SAT = Seperating Axis Theorem

http://www.harveycartel.org/metanet/tuto...rialA.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.

Scott Lembcke - Howling Moon Software
Author of Chipmunk Physics - A fast and simple rigid body physics library in C.
Sage
Posts: 1,199
Joined: 2004.10
Post: #6
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.
Sage
Posts: 1,403
Joined: 2005.07
Post: #7
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.