How to apply pixel perfect collision to rotated sprites?

Question

I'm having difficulty of knowing how to approach or how to tackle this problem. I've looked at some tutorials but they are meant for programmers that already know what they're doing. I followed a video on how to perform a form of pixel collision that applies to regular bounding boxes, where if the bounding boxes collide it checks if any non-transparent pixel in both intersecting boxes are overlapping. If they do, then a boolean will return a true value. Where and how could I start to implement the changing of the bounding box's axis in a rotating object to compliment the texture's appreance? I wouldn't prefer being pointed to an external tutorial because most of the ones I've read assumes the programmer knows everything the writer is talking about.

I've also looked at some source code that perfectly demonstrates what I'm looking for, but it seems I need a very in depth explanation to make any use of reading code as well.

Are you sure you really need pixel perfect collision detection? Almost every game you've ever played uses simple bounding shapes. It's easier to implement and provides better performance. — craftworkgames
I don't need pixel perfect collision, but my understanding was that it's the most accurate? I haven't looked at exactly how to do other types of 2d collision, but concept behind pixel collision in the video I watched seemed straightforward, I just went straight away into putting that in my game. My main concern is just making collision look real and to not hit any transparent pixels, and in which case it was solved for any sprites not being rotated. — Advent
Usually putting tight bounding shapes is enough. Most players won't even notice the difference. You can use circles, rectangles or polygons and even combine them into other more complex shapes. Have a look at code and webs physics editor for an idea how this might work — craftworkgames
This comes up alot in the XNA forums. The very name pixel perfect collision or per-pixel collision seems to suggest to new developers that it is something they must do to have a half-decent game where in actual fact bounding boxes are more than sufficient as others have mentioned above. BB are considerably faster and if you really require more precision, use nested bounding boxes. — MickyD

Unknown Unknown · Accepted Answer · 2015-07-24T21:32:17

First off, I don't really recommend doing this, as it's gonna be either computing- or resource-intensive (or both).

That said, one idea is to still do your aforementioned AABB method of straight-up pixel on pixel. This requires you to maintain your own pixel data in memory to only be used for collision, as opposed to relying strictly on the texture's data.

To be more specific, using this method you will have to generate what is essentially an "image", or 2 dimensional matrix of some kind, one that represents/follows your rotated image's pixels. But you will not be storing color information in it, as you would with a normal image. Instead, each "pixel" or entry in the structure shall be collision data: "block" or "not block". You could easily use a bitmask to represent this, with 1 meaning "block" and 0 meaning "not block", and you'd need one bit per pixel. (NOTE: Usually you don't need more than just a boolean "on" & "off" for this, but it's possible you may want different types of collision per pixel; if so, bitmasks won't work, instead encode whatever you need per pixel, regardless the overall idea remains the same)

Generating a bitmask (or other such structure) for your sprite will enable you to just use the AABB method; all you'd have to do is use the generated bitmask instead of the texture data directly, and everything else is the same as before. But how do we generate this? That's the true difficulty of this method, because you generating your own image is basically replicating the work of your graphics card when you tell it to do rotations.

You would essentially "draw" out the rotated image yourself. This could be done by stepping through your base texture image data pixel by pixel, and applying a rotational transformation matrix to each pixel to get it to the correct destination in your bitmask/buffer. Once you have the correct destination, you then would test the image data for "block" or "not block" (using transparency as you mentioned) and write a 1 or 0 there accordingly.

While you're generating, you should also keep track of local minima and maxima; that is, how far left, right, up, and down your rotated image goes, just to give it an actual true AABB to live inside for quick checks (i.e. "Do I even need to check per-pixel collision?")

To be fully accurate, you will probably need to know which interpolation/rounding algorithm you're using (bilinear, nearest neighbor, etc.), which can get ugly. Graphics systems often do very complicated things, so taking ALL of this into account just for collision is pretty extreme. At the end of the day, even applying this method, it may not truly be "pixel perfect" as far as "perfectly synchronized with the rendered image output", unless you really go far in replicating exactly what XNA / DirectX is doing.

Finally, when does this generation occur? The answer is every time anything rotates! Otherwise you'll be checking stale data. Obviously you could just keep one buffer per sprite and just keep changing that, to not hog so much memory. But this does mean potentially once per frame if you're rotating consistently. Which means multiple times per frame if multiple sprites are all rotating a lot. Might not be the most computationally friendly.

How to apply pixel perfect collision to rotated sprites?

1 Answers