Can someone explain per-pixel collision detection?

Question

Can someone explain the pros and cons of it and any math involved with it?

Answer 1

For 2D: You do not need any math for this problem, you need only a custom bitblit-routine. You will blit collision candidates into a hidden surface by painting their collisionmasks onto this surface and checking, if the pixels you just want to draw are (pixel != 0) . Then you will have a collision. Of course, you should precheck by bounding rectangles if an collision can occur.

For 3D: You will need math(a lot)!

basically you will check each surface of your actor against each surface of your enemy. This will be done by calculating a plane-ray intersection. There is a lot of optimization possible here, but it depends on your 3d representation. This is also no Per-Pixel-Collision, but Per-Vertex-Collision

Answer 2

I will start by answering the pros and cons of per-pixel collision detection, and then consider the mathematical aspects later.

Per-pixel collision detection, also known as pixel-perfect collision detection, and maybe more precisely image-based collision detection, is finding collisions between collision objects that are represented as images. This spatial method stands in contrast to more geometric methods, where polygons and other geometric shapes are used to represent the collision objects.

For 2D, there are generally 3 different options:

• Image-based
• Simple geometric shapes (axis-aligned bounding boxes, circles)
• Complex geometric shapes (convex polygons, convave polygons, ellipses, etc.)

Image-based collision detection is precise and easy to use and understand. In regards to games that uses images for drawing, using image-based collision detection means that whenever the sprites on the screen overlap, they also overlap in the collision detection system. They are also useful for games where deformable collision objects are needed, such as for destructible terrain seen games such as Worms 2D, since there is generally little pre-computation involved. Their main drawback is that they are very inefficient compared to the other methods, especially when rotating and scaling the collision objects.

Simple geometric shapes are both simple to work with and very efficient. If high precision is not needed, or the collision objects fit well with simple geometric shapes (for instance, if your collision objects are balls, circles is a perfect fit, sometimes even better than images). Their main drawback is their precision. For high precision where the basics shapes don't fit, you either have to combine the simple shapes into more complex shapes, or you have to use more general and complex shapes. In either case, you end up in the third method.

Complex geometric shapes can be somewhat precise and relatively efficient or inefficient, depending on the complexity of the used shape(s) to represent a collision object. An important drawback is the ease of use. When the collision objects does not fit with the available geometric shapes, either the precision will have to suffer, or multiple, possibly different shapes will have to be used to represent it, which takes time. Furthermore, some of the shapes are complex and not easy to create, unless you can generate them from an image automatically. One important advantage is that rotation and scaling is generally efficient and easy, especially compared to image-based collision detection.

Image-based collision detection is generally seen as a bad solution, because it is frequently inefficient, especially when using rotation and scaling. However, since it is so flexible, precise and easy to use, I decided to implement a library that seeks to solve the issue of efficiency. The result is PoxelColl, which uses automatically precomputed convex hulls to speed up the image-based collision detection. This gives ease of use, flexibility, precision and efficiency, and supports rotation and scaling. The main drawbacks is that it isn't efficient in all cases compared to the pure geometric solutions, and it uses pre-computation is required, meaning it isn't very inefficient for deformable collision objects.

For 3D, the options and advantages are somewhat similar:

• Volume-based
• Simple geometric shapes (axis-aligned bounding boxes, circles)
• Complex geometric shapes (convex polygons, convave polygons, ellipses, etc.)

It should be noted that Peter Parker's answer is wrong for 3D; pixels (picture elements) in 2D correspond to voxels (volume elements) in 3D.

Some important differences are that the spatial method is much rarer for 3D than it is for 2D. One possible reason is that because 3D adds an extra dimension, the spatial solution becomes even less efficient, while the simple geometric solutions are still efficient. And in games, collision detection is generally an online operation, requiring some level of efficiency, making efficiency important. Volumes are therefore more often used in non-game applications where collisions do not need to be determined online.

For examples of collision detection with volume-based collision detection, see for instance Volumetric collision detection for deformable objects, where their use of volumes instead of geometric shapes means that they can handle deformable collision objects with arbitrarily shaped, closed surfaces.

As for the second question, the math involved in image-based collisions can range from simple to complex. The simple case is basically using axis-aligned bounding boxes for the images, finding their intersection, and then only check the images in the intersection. More complex solutions include the library I mentioned before, where convex polygon intersection is required. And for the 3D case, solutions range from simple to very complex.

Answer 3

It's more accurate than vertexes (or hit-boxes etc). I'm assuming you're talking about 2d here (3d would be box-model vs vertex). Per-pixel would allow you to have detailed sprites which small things (missiles, say) would collide with more realistically.

It's more math and slower than the conventional method, which would be to draw a box (or some other easily math shape like a circle) and say 'this is the actor, anything in here is he'. It is however, more accurate.

Answer 4

When talking pros and cons you also have to consider collision response. What do you want to do when a collision is detected? If you're detecting an object hitting another object where the result is one or both of the objects being destroyed, then per-pixel collision detection is good and accurate. If you want the object to react in some other way, i.e. sliding against a wall, bouncing, etc... then you may want to work with some type of bounding rectangle/circle/oval which will make the collision response seem smoother and more consistent, with less chance of getting stuck.

Answer 5

The pros have already been mentioned: It’s pixel-perfect and fair, there are no false positives nor false negatives. The main disadvantage is that it’s expensive to compute, but if You do a simple bounding box check first, this should not be a big problem. In the age of OpenGL and DirectX there is one more problem: The sprite data are usually textures, which means they are in the VRAM and You cannot check the pixel values easily Yourself. In OpenGL You can use the glReadPixels function to get the intersected portion of two sprites back to RAM and check the collision, or You can use the occlusion query. The occlusion query approach should have better performance, as You are not moving data back from GPU, but occlusion queries are not supported everywhere (ie. they are not supported in OpenGL ES, somebody please correct me if I am wrong).

Answer 6

Per-pixel collision detection is a relic from the past, when graphics were simple and 2D hardware included free collision checking between sprites and backgrounds, because even basic distance calculations were computationally expensive. While todays 2d graphics are more complex, per-pixel collision checks are rarely used, especially because object visible shape and collision shape are usually different. Circles or boxes are sufficient for most cases. Also, since opengl-based graphics hardware can't do collision checks anymore, you have to write additional rendering code, using CPU for the sole purpose of collision checking, while keeping additional bitmap data in system memory, since graphics memory cannot be accessed directly.

Answer 7

taking about OpenGL and the texture-case: you could precalculate a bit matrix for the image and test if two pixels are overlapping.