2D Polygon intersection testing
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..
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!
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".
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.
Post: #4ThemsAllTook 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!
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.
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.
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.
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.
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 | |
| Ray-Triangle Intersection | mikey | 2 | 3,568 |
Aug 15, 2010 05:11 AM Last Post: mikey |
|
| Triangle Intersection Tests | merrill541 | 1 | 2,516 |
Feb 6, 2009 12:13 PM Last Post: scgames |
|
| Box to Plane Intersection With Quaternions | KiroNeem | 6 | 4,116 |
Jun 25, 2006 05:44 PM Last Post: KiroNeem |
|
| OBB Intersection volume | hangt5 | 0 | 2,761 |
Aug 5, 2005 04:22 PM Last Post: hangt5 |
|
| Sides of intersection | KiroNeem | 4 | 3,027 |
Apr 18, 2005 07:54 PM Last Post: KiroNeem |
|