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.

thanks in advance..

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Moderator
Posts: 1,560
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".
Quote this message in a reply
Sage
Posts: 1,482
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.
Quote this message in a reply
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!
Quote this message in a reply
Sage
Posts: 1,482
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.
Quote this message in a reply
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.
Quote this message in a reply
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.

Thanks for your advice everyone.

Sir, e^iπ + 1 = 0, hence God exists; reply!
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Ray-Triangle Intersection mikey 2 4,231 Aug 15, 2010 05:11 AM
Last Post: mikey
  Triangle Intersection Tests merrill541 1 2,903 Feb 6, 2009 12:13 PM
Last Post: scgames
  Closest Point on Polygon Boundry unknown 3 5,871 Sep 2, 2006 03:46 PM
Last Post: memon
  Box to Plane Intersection With Quaternions KiroNeem 6 5,048 Jun 25, 2006 05:44 PM
Last Post: KiroNeem
  OBB Intersection volume hangt5 0 3,139 Aug 5, 2005 04:22 PM
Last Post: hangt5