# Collision detection... again.

• ### Question

• Hi, I'm doing some experimenting and research on pixel-based collision detection. Ofcourse I came across Andy's article on this, using WriteableBitmap. As I was afraid of a performance drain, so I started implementing some optimized variant, based on the same idea.

But with any optimization, you loose something. It doesn't work with images which have a rotationtransform working on it. My guess is, that Andy's algorithmn could still work if you use Writeable bitmap for UIElement and use the rotatetransformed image as input. I have not tested this though.

I also came across an article of Mike Snow, stating in bullet number 4, that he uses polygons to represent collision areas. Does anybody know more about this?

I've used polygon-to-polygon collision before in Avios. I coded this, for actually the reason that I wanted the collision area to rotate along with the player. But in Avios, I created the collision areas manually. Does anybody know about an algorithm, which automatically detects the outline of an image? I've already been studying how to do it myself, but I don't want to reinvent the wheel if I don't have to.

Monday, November 23, 2009 6:50 PM

• Hi,

Convolve this matrix with your binary mask bitmap(could be seen as a matrix), in the result matrix, all positive number are the region edge.

1  1  1
1  -8 1
1  1  1

Thanks,

Thursday, November 26, 2009 2:00 AM

### All replies

• When using pixel perfect collision it's always a good idea to do some other collision detection first. The most efficient collision detection without implementing something like Quadtrees in 2D is Circle collision detection. Determine a collision radius, and then if the sum of the radii is greater than the distance between the centers then the objects collide. One easy optimization on this is that you can compare the square of the sum of the radii to the square of the distance which eliminates an expensive square root operation.

Doing a collision of rectangles isn't much more expensive, so if that is more appropriate for your objects then it's a good option.

Only if the other collision detection returns true is when you would do the per-pixel collision.

Monday, November 23, 2009 9:33 PM
• Hi Bill,

Thanks for responding. What I am not looking for though, is what I call postponing work. I'm actually looking for a way to reduce work.'

I'll give some more explanation.

Meet Ross, he's a terrible guy and lives in a world where people behave badly (so he's not a girl game at the moment):

To the right we have the original image, to the left we have converted the original to a binary bitmask. For those who have worked with Amiga 500 blitter chip, should recognise the idea. Actually, to the left is the binary bitmask, converted back to an image.

In pixel detection for collision, we really are only interested in two types of pixels in the image: transparent and not transparent. We can store this very compact; a unit/UInt32 can contain 32 bits - so 32 ones and zeros. When within vecinity, it is the idea to place two of these masks close to eachother. The good old C programmer will recognize the trick. You use the bit-shift operator "<<" to position the masks of both objects in the horizontal way (using a uling/UInt64), in the vertical way there is no compression. Then you perform the logical and operator "&" on both masks, and if the result of this operation is not 0, then you have a pixel hit. In this method, you reduce work, because you test 32 pixels in only one iteration. Plus that, the "<<" and "&" operators are usually very fast in most languages.

Now like I said. If you store the bitmask compact in unit's/UInt32's, then it doesn't work when you rotate the image, or transform it in any other way. So this method could be good and fast for images without rendertransform.

So I thought, well, I created polygon-to-polygon collision detection in Avios, I can rotate polygons, so let's use that.

Hopefully without infringing an Adobe "Stroke-algorithmn" patent (well, I don't live in the USA, so that's not much of a problem), I tried to detect the borders of this terrible guy called Ross (his name will be "youri" in future, so don't get used to this name):

In the above, to the left we have an outline of Ross, for each pixel which has less than 4 neighbouring pixels. Now if I could transform this outline into a polygon - per frame ofcourse - I could have a very, flexible and fast collision detection method. Ofcourse you see the space between the arm and the head, which would be covered by the polygon. But this isn't a problem. The polygon method is only a little less acurate than the full pixel-to-pixel detection, but this is acceptable.

So, I'm looking for a way to reduce work, by reducing information, and the result may be lesser accurate. My impression was that Mike Snow has made something, to autodetect the collision polygon area.

Tuesday, November 24, 2009 3:55 PM
• Hi,

Convolve this matrix with your binary mask bitmap(could be seen as a matrix), in the result matrix, all positive number are the region edge.

1  1  1
1  -8 1
1  1  1

Thanks,

Thursday, November 26, 2009 2:00 AM
• Hi,

I'm not much of a matrix-hero. Isn't your matrix method just a way to determine border pixels by counting its neighbours? Let's see if I understand it, you declare a pixel a border pixel when it has less than 8 neighbours...

But this is not what I'm looking for. Yes, obviously, my neighbourpixel count from above is not sufficient. I actually did not improve it (yet) because it was late and I realized that my technical challenge would come after that.

The real technical problem starts when you have the border pixels. I would like to convert this to a polygon.

So given a perfect outlined image, with only border pixels, how to convert this to a polygon effectively? I guess no-one has heard of a way to do this, which was really my question. So I'll have to solve it myself. I'm thinking in the direction of the 8-queens on the chessboard algorithm... It is hard stuff, that's for sure.

Tuesday, December 1, 2009 6:44 PM