iDevGames Forums
2D collision detection - Printable Version

+- iDevGames Forums (http://www.idevgames.com/forums)
+-- Forum: Development Zone (/forum-3.html)
+--- Forum: Game Programming Fundamentals (/forum-7.html)
+--- Thread: 2D collision detection (/thread-1575.html)



2D collision detection - Ingemar - Mar 21, 2009 03:16 PM

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/topic.asp?topic_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?


2D collision detection - AnotherJake - Mar 22, 2009 11:43 AM

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!


2D collision detection - Ingemar - Mar 22, 2009 12:33 PM

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.


2D collision detection - NelsonMandella - Mar 25, 2009 07:04 PM

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;
}



2D collision detection - Ingemar - Mar 26, 2009 12:22 AM

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.