Image Collision Detection Recommendations

Newbie & Debugging Questions
#1

I currently have a working implementation of image collision detection for .pngs with alpha and making sure their non-alpha pixels collide. It is very slow however.

This is the example I originally learned from. I’ve got various versions of this for my code. Partial collision and 100% collision. 100% collision takes longer as it requires going though every pixel to ensure total collision.

This is done at loading a new game. Detecting collision between 1000ish+ images ranging from 10x10-300x300 takes upwards of 40 seconds. If I turn off collision, the load time drops to a few seconds.

Can anyone suggest a faster way to detect collision between images contents? Or is this actually a decent speed? I’d expect we can do better.

#2

As a very general idea which may not apply here, could you do something like:-

  1. Take a blank image/byte array thingie that’s big enough to hold both images at their relative positions
  2. Copy the pixel bits of the first image into a new array grid, making transparent pixels as zero and and anything else is collideable.
  3. AND (as in not OR/XOR etc…) the bits of the second image into the same grid.
  4. See if any of the bits in the new array are != 0.

Just a thought really. I don’t how fast doing the above would be, but I’m hoping there are functions that can handle whole areas of a byte array without having to do each pixel manually.

#3

Yea, if the functions you mention at the end exist, that seems like a viable strategy. If those functions don’t exist, it seems like the load would be the same since we have to deal with each pixel then.

I think OpenGL might have something I could use (some form of buffer object), but that would come again to why I am here. I’m looking myself, but if someone knows of a way to do this with OpenGL, I’d greatly appreciate such guidance.

#4

I am assuming that each your images have a location. Try partitioning your space into sections and only do collision to entities within the same sections. Use the bound of image to determine which sections to play entities in.

#5

The present method operates in stages. 1) Test the bounds of the two image rectangles in coordinate space. If passes, 2) scan through each relevant pixel of the relevant pixel subsets. If no conditions are violated, return happy.

No irrelevant pixels are tested presently. Some sort of operation like what SteveSmith said is all I can think would work here. I don’t have that sorted yet tho.

#6

FWIW, I ended up using multithreading on the chunks of image collision tests. This made the time acceptable. 8)

#7

I bet there’s a way to do this on a GPU super-fast :slight_smile:

Cas :slight_smile:

#8

One method that might be more efficient if your images don’t change, they’re just rotated and translated, is to make a polygon out of the image outline. Maybe make lines between border pixels. I think that there are libraries that do this, but I can’t remember their name. JTS can then simplify the polygon by turning Collinear points into one straight line, then just do an intersection test of these lines in the polygon against other polygons’ lines.

#9

The polygons idea sounds very good. Probably the kind of answer I should be doing. These are all static images. If I had something to make these into polys, I could keep those poly files or that information and just use that.

I’m looking into it, but if you have or remember any further information, it’s well appreciated.

Edit - I haven’t gotten to look into this fully, but this looks cool.

#10

Here are some good alternatives:

Back when I tried to do this only Potrace seemed decent:
http://potrace.sourceforge.net/

But these days even Inkscape has an option to do vectorising of bitmaps.

This java library looks promising, but I haven’t tried it:
https://github.com/jankovicsandras/imagetracerjava7