# Detailed and fast 2D collision detection

This topic is 4360 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm working on a scripted sprite-based 2D engine in C++, and I've gotten to the point where I really need to start improving the performance. Currently I can't handle more than about 40-50 sprites onscreen before performance takes a nosedive (on a 1.43GHz Mac Mini with 512MB RAM; I want this game to be runnable on less). I discovered that one of the major performance hits I'm taking is with my collision detection; I'm using bounding polygons instead of bounding boxes because I want to be able to do detailed collision reactions (e.g. labelling one side of a sprite as damaging and another side as not, or obtaining the surface normal of a sprite for bouncing). Of course I perform a bounding box check as well before going into the bounding polygon check, and I'm using a quadtree to cull out my list of sprites. If I just ditch the bounding-polygon collision, then I roughly triple the maximum onscreen sprites before slowdown occurs. But I don't want to do that. Does anyone have any recommendations or guides for faster collision detection algorithms that aren't as ham-handed as bounding boxes?

##### Share on other sites
How often do your sprites touch each other,
if too much you could try programming AI so sprites give each other some personal space, for example if you use any sort of weighted AI make it so even though than can keep going until they hit the other sprites bounding polygon they prefer to stay out of the bounding box and thereby reducing the number of time you need to run the algorithm

EDIT:
if its mainly for hit detection of bullet like projectiles you could also make sprites cheat and when hitting the player decide where exactly they hit through a random number insted of full bounding polygon hit detection
im not exactly sure how your game works but the bounding polygon test shouldnt need to be used very offten if you program it right

##### Share on other sites
An interesting approach, but not one that ultimately will be much use for me. The engine I'm working on is as fully general as I can make it, which means that I can't anticipate what sorts of games will be made with it (heck, I hacked together a slideshow with it once). I am working on adding a "class" field so I can have an option such that sprites of the same class don't collide (e.g. if you're making a space shmup, chances are you don't care if two enemy sprites are touching each other). However, that's a workaround at best.

I should have specified earlier - the current bounding polygon algorithms I'm using are entirely self-developed without any reference to external materials (except for a lot of paper and pencil to work out the use cases and simple algebra). In other words, it's not what you would call optimized. So if you know of a guide to fast bounding polygon collision detection, that'd be helpful too.

##### Share on other sites
Can you tell us a little about your algorithm and what sort of intersection information it returns? Also, are these polygons always convex? (I'm guessing they are since you describe them as 'bounding polygons'.) In any case, I'm guessing that switching to another algorithm (such as a carefully optimized SAT implementation) would solve your problem.

##### Share on other sites
I don’t know much about bounding polygon algorithms but most fps I have seen have several bounding boxes that are connected to the skeleton of the model, also not sure how that’s handled and if its generated automatically or not. But you should be able to have fairly good collision/hit detection on most models with a dozen or so simple geometric shapes like boxes, cylinders and spheres but you may need to make the user of you engine manually define them though I think some programs that can do that already exist (milkshape?)

##### Share on other sites
Quote:
 Original post by jykCan you tell us a little about your algorithm and what sort of intersection information it returns? Also, are these polygons always convex? (I'm guessing they are since you describe them as 'bounding polygons'.) In any case, I'm guessing that switching to another algorithm (such as a carefully optimized SAT implementation) would solve your problem.
Sure, more information makes it easier to get help. :) The algorithm actually doesn't require convex polygons right now. It basically just takes two polygons - one with velocity vector v and one at rest. The endpoints of the moving polygon's lines are projected backwards along v to generate two more lines. Each line is then tested for intersection with the at-rest polygon. If an intersection exists, then the component c of v that must be subtracted from the line's position to get it to not intersect is calculated. After all is said and done, the line with the largest c is the one that had the first collision; the surface normal of the line it collided with, c, and the line's "color" are returned (the color of a line classifies its in-game effects, e.g. on fire, safe to walk on, poisonous, powerup, and so on).

Edit: the direction of the surface normal is determined by the velocity vector - surface normals always "oppose" the velocity of the line.

I'll need to research SAT; I'm not familiar with how it works. It could well be that my best bet is to decompose the polygons I start with into convex polygons and do faster piecewise detections instead of one big test.

And Kaze - this is a 2D engine, not 3D. For 2D, the only really fast collisions are bounding box to bounding box, with bounding sphere as a reasonably close second. Neither are sufficient to my needs.

##### Share on other sites
Quote:
 Original post by DerakonThe algorithm actually doesn't require convex polygons right now. It basically just takes two polygons - one with velocity vector v and one at rest. The endpoints of the moving polygon's lines are projected backwards along v to generate two more lines. Each line is then tested for intersection with the at-rest polygon. If an intersection exists, then the component c of v that must be subtracted from the line's position to get it to not intersect is calculated. After all is said and done, the line with the largest c is the one that had the first collision; the surface normal of the line it collided with, c, and the line's "color" are returned (the color of a line classifies its in-game effects, e.g. on fire, safe to walk on, poisonous, powerup, and so on).
I see (although I'm not sure why you say the line endpoints of the moving polygon are projected backwards along v - wouldn't you want to project them forwards, in the direction of motion?). It seems though that this method could miss collisions. Imagine an axis-aligned box heading straight towards a considerably smaller axis-aligned box; it could be that the boxes do collide during the timestep, but none of the vertices of the first box ever intersect the smaller box. Perhaps I'm misunderstanding your method though.

In any case, the SAT is a good solution and can be made to be quite efficient, but in general it is resricted to convex objects. You could decompose your objects into convex sub-objects, or you could just treat the objects as collections of line segments and perform the SAT test between these segments. This is just an idea - I've never actually tried this approach, so I can't say from experience how well it would work.

##### Share on other sites
Quote:
Original post by jyk
Quote:
 Original post by DerakonThe algorithm actually doesn't require convex polygons right now. It basically just takes two polygons - one with velocity vector v and one at rest. The endpoints of the moving polygon's lines are projected backwards along v to generate two more lines. Each line is then tested for intersection with the at-rest polygon. If an intersection exists, then the component c of v that must be subtracted from the line's position to get it to not intersect is calculated. After all is said and done, the line with the largest c is the one that had the first collision; the surface normal of the line it collided with, c, and the line's "color" are returned (the color of a line classifies its in-game effects, e.g. on fire, safe to walk on, poisonous, powerup, and so on).
I see (although I'm not sure why you say the line endpoints of the moving polygon are projected backwards along v - wouldn't you want to project them forwards, in the direction of motion?). It seems though that this method could miss collisions. Imagine an axis-aligned box heading straight towards a considerably smaller axis-aligned box; it could be that the boxes do collide during the timestep, but none of the vertices of the first box ever intersect the smaller box. Perhaps I'm misunderstanding your method though.
Whether you project forwards or backwards makes little difference; it's just a matter of when you do the collision detection - before or after you try to move the polygon? If before, then you project forwards; if after, then you project backwards.

As far as your example, you're correct that the large box wouldn't collide with the small box. However, the small box would collide with the large box; when I have to collide an object at rest with a moving object, I change my frame of reference so that the first object is moving and the second is at rest. This is a bit hackish but it covers the case you pointed out, and others besides.

I'll look into SAT and see how hard it would be to decompose a potentially concave polygon into a set of convex polygons. Thanks for the recommendation.

##### Share on other sites
Quote:
 Original post by DerakonAs far as your example, you're correct that the large box wouldn't collide with the small box. However, the small box would collide with the large box;...
I think that's part of your problem. Consider 5 objects in a node,
4+3+2+1 = 10 tests when a specific object-object test is done only once;
5*4 = 20 tests when a specific object-object test is done from each perspective.

Once an object is tested against another, they generally should not be tested against each other again(unless there is some cost in figuring out if two objects have been tested).

Quote:
 ...I'll look into SAT

What's SAT?

##### Share on other sites
Quote:
Quote:
 Original post by DerakonAs far as your example, you're correct that the large box wouldn't collide with the small box. However, the small box would collide with the large box;...
I think that's part of your problem. Consider 5 objects in a node,
4+3+2+1 = 10 tests when a specific object-object test is done only once;
5*4 = 20 tests when a specific object-object test is done from each perspective.

Once an object is tested against another, they generally should not be tested against each other again(unless there is some cost in figuring out if two objects have been tested).

Quote:
 ...I'll look into SAT

What's SAT?

Separating Axis Theorem

and Swept SAT, with added test for moving polygons.

##### Share on other sites
I've read through the SAT tutorial by the makers of N, and while it's useful, it's very N-centric; the examples given are for axis-aligned boxes, circles, and inverse circles, as opposed to, say, arbitrary polygons. I'm fairly certain I understand how I can make use of SAT anyway, but I want to be certain I have this right (after all, improperly-implemented collision detection is deadly and very hard to track down). Say I have a collection of convex polygons A that I'm using to compose an arbitrarily-shaped bounding polygon, and I want to determine if that polygon collides with another such collection B. I can iterate over every polygon p1 in A and compare it with every polygon p2 in B. Would this about do it?
for each polygon p1 in A{bool intersect = falsefor each line l1 in p1{  for each polygon p2 in B  {  for each line l2 in p2  {    if (infinite extension of l1 intersects with l2)    {      intersect = true      determine offset vector    }  }  }}if (intersect = true)  A and B do intersect}return largest offset vector
Where by "infinite extension" I mean the line that the line segment lies on (in other words, the axis of separation for that edge of the polygon). The offset vector is a vector based on the velocity vector of A, which must be added to A's position to keep it from intersecting with B (a similar one for B based on its own velocity can be calculated at the same time, thus keeping me from having to compare A-B and B-A).

Obviously this process becomes faster if I can guarantee that A and B are convex because the number of component polygons is 1; at worst (for M edges in A and N in B) this process involves N*M/4 intersection tests (since a sawtooth bounding polygon consists of N / 2 triangles), with good odds of short-circuiting the entire process (short-circuits occur if one polygon in A does not intersect with any polygons in B).

Edit: cleaned up the code a touch to make it more clear.

##### Share on other sites
You test convex polygons one by one, yes, but I think you misunderstood the SAT.

for each edge e1 in p1    Vector axis = perpendicular vecor of e1    proj1 = projection of p1 on axis    proj2 = projection of p2 on axis    if (proj1 do not overlap proj2)         return object_dont_intersect;end forfor each edge e2 in p2    Vector axis = perpendicular vecor of e2    proj1 = projection of p1 on axis    proj2 = projection of p2 on axis    if (proj1 do not overlap proj2)         return object_dont_intersect;end for............return objects_intersected;

[Edited by - oliii on January 10, 2006 6:31:23 AM]

##### Share on other sites
Ahh, thank you. That does make sense. Now I'm just faced with the problem of figuring out how to quickly project arbitrary polygons onto arbitrarily-oriented lines. Can't see how I can do that in less than O(N) time (N = number of vertices of the polygon). At least I can pre-calculate the projections of each polygon onto its own separating axes. Memory is cheap.

Thanks for all the assistance!

##### Share on other sites
Quote:
 Original post by DerakonNow I'm just faced with the problem of figuring out how to quickly project arbitrary polygons onto arbitrarily-oriented lines. Can't see how I can do that in less than O(N) time (N = number of vertices of the polygon). At least I can pre-calculate the projections of each polygon onto its own separating axes. Memory is cheap.
If you're still looking for a speed up, this can be further optimized. As you noted, the projection of the polygon onto its own edge normals can be precalculated and simply offset by the projection of the polygon position at run time. For the other polygon you obviously have to do an arbitrary projection, but that can be accelerated as well. Two methods you might look into for this are 'hill climbing' and 'DK (Dobkin-Kirkpatrick) hierarchy'. Although in general I'd think these would be overkill for 2d, if you have a high number of complex objects composed of multiple convex polygons, it might be worth it. You also cache 'witnesses' (in this case, the axis that separated the objects) to further speed up the rejection test. And, of course you can do circle or boolean swept circle tests first to early out.

I don't know how dense the object distribution in your simulation is, but it seems that with all this in place, under normal circumstances the full SAT test would only end up being performed a few times per frame, which should not be a bottleneck.

##### Share on other sites

This topic is 4360 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.