Optimization of per-pixel collision

Question

I'm been developing my own physics engine for a school project and recently I encountered a problem: Per pixel collisions on big sprites make my FPS drop A LOT.

Here's my pixel collision code. Before entering the following code I'm using Intersects() to see if their bounding boxes collided.

private bool PerPixelCollision(IObject a, IObject b)
{

    Color[] bitsA = new Color[a.Texture.Width * a.Texture.Height];
    a.Texture.GetData(bitsA);
    Color[] bitsB = new Color[b.Texture.Width * b.Texture.Height];
    b.Texture.GetData(bitsB);

    // Calculate the intersecting rectangle
    int x1 = Math.Max(a.Bounds.X, b.Bounds.X);
    int x2 = Math.Min(a.Bounds.X + a.Bounds.Width, b.Bounds.X + b.Bounds.Width);

    int y1 = Math.Max(a.Bounds.Y, b.Bounds.Y);
    int y2 = Math.Min(a.Bounds.Y + a.Bounds.Height, b.Bounds.Y + b.Bounds.Height);

    Color c;
    Color d;
    // For each single pixel in the intersecting rectangle
    for (int y = y1; y < y2; ++y)
    {
        for (int x = x1; x < x2; ++x)
        {
            // Get the color from each texture
            c = bitsA[(x - a.Bounds.X) + (y - a.Bounds.Y) * a.Texture.Width];
            d = bitsB[(x - b.Bounds.X) + (y - b.Bounds.Y) * b.Texture.Width];

            if (c.A != 0 && d.A != 0) // If both colors are not transparent (the alpha channel is not 0), then there is a collision
            {
                return true;
            }
        }
    }
    // If no collision occurred by now, we're clear.
    return false;
}

In the example I'm using to test I'm dropping 4 sprites in another sprite that represents the floor (736x79). When I change the sprite that represents the floor to a bigger sprite (3600x270) the FPS drops. I know the problem is in the pixel collision because I'm using a profiler.

Does anyone have any idea on how to optimize the collision?

P.S.: Sorry if I wasn't clear enough about my problem. My english is not so good.

EDIT: The first problem was solved by using the solution provided by @pinckerman but I found another one related to pixel collision detection. When a sprite collide with a the transparent part of a texture, we get the part that intersected and check all the pixels of that part. The problem is: When the transparent part is big enough to cover the whole sprite, I check the whole texture of that sprite (currently using 50x50 textures which is 2500 pixels). Is there any way to not check the whole texture?

Thanks

I'm no expert, but I don't think you should do per pixel collision checks on something like a floor. If you want terrain collision do some kind of polygon collision check. Or if the floor is just flat do a rectangle or even a line intersection check. Sorry but I can't help you with optimizing your algorithm. — Jens Vossnack
don't use this. this is perormace killer. use line, box, circle, polygon collision. or all together in combination, but not pixel collision. it's just waste of resources. — Davor Mlinaric
I feel it necessary to add my voice to the throng and point out that you're always going to run into performance issues doing this kind of collision detection. Calling GetData() on a texture stalls the rendering pipeline, which prevents the GPU and CPU from working together at maximum efficiency. In most cases it's going to be better to use geometric collision detection--though of course, there's nothing wrong with this sort of thing as a learning exercise. See this article for more information. — Cole Campbell

pinckerman pinckerman · Accepted Answer · 2013-09-16T15:54:44

I'm pretty sure that your FPS drop so much because you're doing

Color[] bitsA = new Color[a.Texture.Width * a.Texture.Height];
a.Texture.GetData(bitsA);
Color[] bitsB = new Color[b.Texture.Width * b.Texture.Height];
b.Texture.GetData(bitsB);

at the beginning of your method.
I suppose you call your PerPixelCollision every Update loop and creating and coping millions of values every game cycle it's not a very efficient thing to do.

A big sprite creates a huge Color[] array: the bigger are your arrays, the slower will be this method.

EDIT:

For your second problem, I think that, if you don't know beforehand where is the transparent area of your "big" texture, you have to check the whole sprite anyway.
If your sprite it's not too big that's not a big waste of performance.

PS: I see that you get the intersecting Rectangle on your own, maybe you could find useful this method.

Optimization of per-pixel collision

1 Answers