Algorithms for Image Shapes

Newbie & Debugging Questions
#1

I’m exploring the idea of converting images into bounding shapes, using a transparency color (or alpha for png’s), as a method for doing pixel perfect collision.

Of course, this can quickly turn into a CPU taxing problem. I could just hit every pixel, and add all non-transparent ones to a polygon. But, that’s far too many points, and it’s just a slow process to go through every pixel in an image.

Another though would be to check every pixel, but only add the bordering pixels to create an outline. This reduces the point count, but is still checking every pixel.

A third thought was scanning until I found the first non-transparent pixel, as this would definitely be on an edge, and then only checking pixels around it for other border pixels, And just making my way around the image. I could use a scalar to reduce the number of points actually added.

Finally, my question is if this is an accepted approach to pixel perfect collision. Or, do people generally just use the pixel colors directly to check for overlap?

#2

What I did about 10 years ago was to upload all image data as a single color in an 8 bit array with with the first and second elements as width and height.

Then at runtime scan all overlapping pixels (scans only the overlapping bounding boxes and not the whole box) by “clipping” one sprite to the other. Fast enough on a 486DX 66mhz but that’s DOS and I did it in x86 ASM.

Here’s a more recent version (still old) using inline x86 ASM.

http://rel.phatcode.net/index.php?action=contents&item=FJ-RX

Try “replay” mode to see an auto-game.

#3

If you want something faster than a full scan of the bounding box, it seems to me that the best way to do it is likely to be runlength-encoding the alpha channel as a pre-processing step. If your shapes are convex then you only need to store 3 numbers per row, and the overlap check would be two comparisons.

#4

I don’t fully understand the question, and may be clueless as to what you are asking, but when you write: “Or, do people generally just use the pixel colors directly to check for overlap?” it gets me wondering, why make colors serve two purposes? Will you be putting constraints on future graphics decisions if the color data is being used for collision checking?

A second array, representing each pixel location of the screen is not that large. Fill it with bytes that are pointers to the objects occupying the space, instead of colors. I did this on a kind of loony experiment where I had about 500 threads going, each at its own sleep loop, and all the objects checking against this representation for collisions. It worked. The “interesting” concurrency issues can be avoided by moving all objects in turn rather than having them in independent loops, which should make it even more performant.

It is a little cumbersome to set up, but it scales linearly :o as you add more objects for collision checking. A crazy idea perhaps, but I’d like to go back to it and explore some more, look for possible optimizations.

#5

Found this.
http://www.gamedev.net/topic/632646-simplifying-dynamic-2d-bounding/#post_id_5053404

I had reposted the source since it’s not visible.

#6

The thought on using the pixel colors for the actual collision checking was just a query about the more excepted method of achieving pixel perfect collision. Doing some research, there isn’t all that much information on the topic, and there really isn’t a consensus on an accepted method for it.

To me, using the pixels to test for overlap doesn’t seem efficient at all. That’s why I’m opting for building a polygon to represent the non-transparent pixels of the image. Though, scanning through every single pixel and adding all non-transparent pixels to the polygon is also very cumbersome. So, if I can develop a method of collecting just the bordering pixels of the image, or something like that, maybe this would be efficient enough to be practical. Maybe adding an options for an offset, so that it only gets every other border pixel, or so.

SHC’s link seems to be something like what I’m looking for. I’ll mess with that and see if it proves useful.

#7

Just thought I’d update this with my findings:

I was able to write a method that created a shape from the outline of an image. Here are a couple screen shots:

The method to create this has a parameter for “precision”, which basically just means it only adds a point to the polygon once every x number of pixel hits. So, for a precision of 2, every second border pixel is added to the polygon. There is also a parameter for the value of the alpha to check against.
For this image the time to create the shape was:

Image size: 384x384
Precision Time (in ms)

1           87
2           66
4           55
8           42
16         33

These are all on separate run times, so there is no optimization between each. The image above uses a precision of 2. One part of my algorithm that I know plays a big part in the creation time is converting the image to an array of Pix (inner class). I do this for convenience, so I’m sure by just accessing the image pixels directly, that time can be lowered more.

A couple limitations I haven’t fixed:
If there is an edge of the non-transparent pixels on any border of the whole image, an out of bounds exception occurs.

It doesn’t account for transparent pixels within the non-transparent pixels.

So, anyway, that’s what I’ve found that I think will suite my needs. I’m sure there is still a better way to do this, but I’m satisfied. Here is the pastebin link http://pastebin.com/Wvatq5Bk. It is in the form of a singleton class. When you create a shape, you also pass in a name, so that you can access the shape again without having to re-create it. It’s done this way for personal need. Also, this was done using the Slick2D Image, Shape, and Polygon classes. I’m sure converting it to Java2D would require minimal changes. Further more, it’s written to quit the program if the user tries to use an image that isn’t a png.
Feel free to use the code, abuse it, criticize, or whatever. Hopefully this helps someone.

Update: Redid method to cut out all the code duplication, and fixed typo indicated by SHC.

#8

Found one typo in code.


private class Pix
{
    public int r;
    public int g;
    public int b;
    public int a;
 
    public boolean checked;
 
    public Pix(Color c)
    {
        r = c.getRed();
-       g = c.getBlue();
+       g = c.getGreen();
        b = c.getBlue();
        a = c.getAlpha();
        checked = false;
    }
}
#9

Oh man. Thanks for that. Haha. The color fields in Pix are for another version of this method that uses a specific color as the transparent color, which I haven’t implemented yet, so I haven’t used those fields to realize it was typed wrong.

#10

for all interested take a look at this particle trimmer
http://www.humus.name/index.php?page=Cool&ID=8