2D Polygon intersection testing
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..
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!
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".
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.
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!
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.
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.
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.
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.
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!
Possibly Related Threads...
Thread:  Author  Replies:  Views:  Last Post  
RayTriangle Intersection  mikey  2  6,272 
Aug 15, 2010 05:11 AM Last Post: mikey 

Triangle Intersection Tests  merrill541  1  4,143 
Feb 6, 2009 12:13 PM Last Post: scgames 

Closest Point on Polygon Boundry  unknown  3  8,548 
Sep 2, 2006 03:46 PM Last Post: memon 

Box to Plane Intersection With Quaternions  KiroNeem  6  8,497 
Jun 25, 2006 05:44 PM Last Post: KiroNeem 

OBB Intersection volume  hangt5  0  4,238 
Aug 5, 2005 04:22 PM Last Post: hangt5 