2D collision detection

Member
Posts: 260
Joined: 2005.05
Post: #1
I didn't find a thread about 2D collisions when searching. (Some related though, like one about sprite-background test.)

I need some good way to detect collisions in my 2D game engine (OpenGL based). I know a few ways, but I might be missing some.

Of course I first need a high level layer, like an axis-aligned BSP tree, quad tree or other sorting. 1D sorting is an old favourite of mine in that respect, very easy and quite enough speedup. I have that already.

A bounding sphere is always a winner as broad phase, but only that. Easy. But then we have the narrow phase.

I found one related thread here:

http://www.gamedev.net/community/forums/..._id=277591

In the old days, I used AABBs. This was good as long as sprites did not rotate or scale. But of course they must be able to do that.

I have one similar solution: a convex polygon. I can check for polygon-polygon collisions fairly easy, and transform all points in each polygon with the transformation of the sprite. And I get the intersection as a polygon as a result, too, which can be useful for collision handling (since it encloses the point of impact and also gives the amount of overlap).

What I don't like with it is that it complicates the creation of sprites. I must provide that polygon for every sprite face. If it is just my old AAB, it now turns into an OBB, and that works, but for many sprites that AABB is a too crude approximation.

Sometimes, you want to test on pixel level. The thread above suggest occlusion queries. I do understand what occlusion queries do, but not quite how to apply it efficiently to collision detection.

Maybe I could use my polygon approach, and generate a bounding polygon as the convex hull of pixels with non-zero alpha. It would be OK for some cases.

But you don't always want pixelwise tests, don't always want to hit on any overlap. Mant of my old games are pseudo-3D, so sprites really should be tested for a "bottom plate" area. But then I am back to the manually designed polygon.

That's a few ideas. Am I missing something obvious? What are others using?
Quote this message in a reply
Moderator
Posts: 3,579
Joined: 2003.06
Post: #2
I pretty much have taken the same route as you. Normally I still use AABBs and circles for just about everything, but if I happen to have a situation with a major odd-shape which requires finer collision detection, I'll drop down to polygonal collision detection. But like I said, I rarely bother with that nowadays, and instead prefer circles and AABBs. I'll even go so far as to use multiple AABBs. Like you said, polygonal works great and it's fine and all, but it is a pain to specify bounding coordinates for each sprite.

I used per-pixel collision detection way back in the old days when the graphics were done in software. I can't recall ever trying it using OpenGL. I don't really need it right now, but I can think of a few situations where it might be handy. If you happen to come up with a good workable solution, I'd love to hear about it!
Quote this message in a reply
Member
Posts: 260
Joined: 2005.05
Post: #3
AnotherJake Wrote:I pretty much have taken the same route as you. Normally I still use AABBs and circles for just about everything, but if I happen to have a situation with a major odd-shape which requires finer collision detection, I'll drop down to polygonal collision detection. But like I said, I rarely bother with that nowadays, and instead prefer circles and AABBs. I'll even go so far as to use multiple AABBs. Like you said, polygonal works great and it's fine and all, but it is a pain to specify bounding coordinates for each sprite.

I used per-pixel collision detection way back in the old days when the graphics were done in software. I can't recall ever trying it using OpenGL. I don't really need it right now, but I can think of a few situations where it might be handy. If you happen to come up with a good workable solution, I'd love to hear about it!
Sounds good to me. Polygons feel right, I can default at the same old boxes without loss of generality. But supporting non-convex polygons will be a pain, if I need that. I guess my answer then is to support multiple polygons per sprite.

I wouldn't mind a pixelwise check option, but it is not very easy to do. I can think of a few ways, but they would be costly.
Quote this message in a reply
Member
Posts: 194
Joined: 2009.02
Post: #4
Ingemar Wrote:I wouldn't mind a pixelwise check option, but it is not very easy to do. I can think of a few ways, but they would be costly.

I'm not sure if this is what you had in mind but for testing pixel collisions in opengl I usually call something similar to the below function for a collection of points detailing the the object. I do this only after some preliminary bounding tests. Alpha channels are of course required.



Code:
BOOL texel_transparency(NSPoint p, texture_type texture)
{
      int w = texture.width;
      int h = texture.height;
      int x = p.x;
      int y = p.y;
    
      unsigned char *pixels = texture.image_data;
      unsigned char alpha = pixels[4*(y*w + x) + 3];
    
      if (alpha == 0)
        return FALSE;
    else
        return TRUE;
}
Quote this message in a reply
Member
Posts: 260
Joined: 2005.05
Post: #5
NelsonMandella Wrote:I'm not sure if this is what you had in mind but for testing pixel collisions in opengl I usually call something similar to the below function for a collection of points detailing the the object. I do this only after some preliminary bounding tests. Alpha channels are of course required.
Testing a single pixel is not a problem. Testing an entire shape (the mask/alpha of an image) against another is the hard part. You have to do it with any transformation you allow (translation, rotation, scaling). Doing that on the CPU is pretty costly.

Testing a "collection of points", then we are at the polygon representation again. It is pretty nice I think. The only problem is non-convex polygons.
Quote this message in a reply
Post Reply 

Possibly Related Threads...
Thread: Author Replies: Views: Last Post
  Optimize the collision detection alaslipknot 1 2,805 May 12, 2013 08:02 PM
Last Post: SethWillits
  Collision detection tutorial ThemsAllTook 7 22,835 Nov 5, 2011 05:20 PM
Last Post: SethWillits
  Help with Collision Detection..(i'm almost there) carmine 1 4,695 Jun 29, 2011 12:33 PM
Last Post: ThemsAllTook
  Time Delta, collision detection mk12 19 15,650 Sep 8, 2010 06:40 PM
Last Post: AnotherJake
  Collision detection for pinball game johncmurphy 0 4,806 Sep 6, 2009 02:46 PM
Last Post: johncmurphy