Finding border pixels of a image with transparent surrounding (for collision detection)

Question

I'm programming a game and I want to collide images with transparent borders (sprites) against a circle.

It's easy to know if the circle is overlapping the image by checking collision with the pixels which are not transparent.

The problem I have is to know the normal angle in order to make a bounce.

I would need a library (Java) or algorithm that given an image it would return an array with the pixels that are at the border of the image so i can find the slope between two points of the surface.

Is there any library/algorithm/code snippet i can learn from?

Answer 1

Here's a simple approach:

Create a mask from the original image where all transparent pixels are 0 and all non-transparent pixels are 1

Then, perform a simple edge detection on your mask by subtracting each pixel (x,y), which will be 0 or 1, from pixel (x+1,y+1) and taking the absolute value.

This will give you a 1 for pixels on the edge of the image and a 0 everywhere else.

Note: this method is essentially equivalent to treating the image as a 2d function and calculating its gradient. The edges are steep parts of the intensity surface (which correspond to large gradient values). Here's some more information on gradient-based edge detection.

---

Here's an example image:

First mask all the non-transparent pixels:

Then shift the image down and over one pixel and subtract it from itself.

This creates the image below. Now simply read out the matrix indices with value 1.

That's your array of edge pixels.

Note: if your images contain interior transparent pixels, this technique will also find interior edges, which may or may not be a problem for you...

Answer 2

This is what I'v implemented over the time: (detectionStrength is best 10)

public static List<Pixel> getEdges(Image image, int detectionStrength) {

    boolean[][] opaque = new boolean[image.getWidth(null)][image
            .getHeight(null)];
    LinkedList<Pixel> edges = new LinkedList<Pixel>();
    int rgb;

    /*
     * convert to BufferedImage to get individual pixel colors
     */
    BufferedImage bufferedImage;
    if (image instanceof BufferedImage)
        bufferedImage = (BufferedImage) image;
    else {
        bufferedImage = new BufferedImage(image.getWidth(null),
                image.getHeight(null), BufferedImage.TYPE_INT_ARGB);
        bufferedImage.createGraphics().drawImage(image, 0, 0, null);
    }

    for (int i = 0; i < opaque.length; i++) {
        for (int j = 0; j < opaque[i].length; j++) {
            rgb = bufferedImage.getRGB(i, j);
            opaque[i][j] = (rgb >> 24 & 0xFF) > detectionStrength; // transparency
        }
    }

    /*
     * If a pixel is opaque, but is surrounded, with at least one
     * transparent pixel, it is considered an edge.
     */
    for (int x = 0; x < opaque.length; x++) {
        for (int y = 0; y < opaque[x].length; y++) {
            if ((x == 0) || (x == opaque.length - 1) || (y == 0)
                    || (y == opaque[x].length - 1)) { // border pixel
                if (opaque[x][y]) // if opaque, it is automatically an edge,
                                    // no matter its surrounding...
                    edges.add(new Pixel(x, y, new Color(bufferedImage
                            .getRGB(x, y))));

            } else { // not a border pixel
                if (opaque[x][y]
                        && (!opaque[x - 1][y - 1] || !opaque[x][y - 1]
                                || !opaque[x + 1][y - 1]
                                || !opaque[x - 1][y] || !opaque[x + 1][y]
                                || !opaque[x - 1][y + 1]
                                || !opaque[x][y + 1] || !opaque[x + 1][y + 1]))
                    edges.add(new Pixel(x, y, new Color(bufferedImage
                            .getRGB(x, y))));
            }
        }
    }

    return edges;
}

And the Pixel class (just a very simple extension of Point) :

public class Pixel extends Point implements Cloneable {

    private static final long serialVersionUID = -9053911985748552077L;

    public Color color;

    public Pixel(int x, int y, Color c) {
        super(x, y);
        color = c;
    }

    public Pixel(Pixel other) {
        super(other.x, other.y);
        color = other.color;
    }

    public Color getColor() {
        return color;
    }

    public void setColor(Color newColor) {
        color = newColor;
    }

    public int hashCode() {
        final int prime = 31;
        int result = super.hashCode();
        result = prime * result + ((color == null) ? 0 : color.hashCode());
        return result;
    }

    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (!super.equals(obj))
            return false;
        if (!(obj instanceof Pixel))
            return false;
        Pixel other = (Pixel) obj;
        if (color == null) {
            if (other.color != null)
                return false;
        } else if (!color.equals(other.color))
            return false;
        return true;
    }

    public Object clone() {
        return new Pixel(x, y, color);
    }

    public String toString() {
        return "Pixel [color=" + color + ", x=" + x + ", y=" + y + "]";
    }
}

The image created with the algorithm, will be: