Best way for perfect pixel collision detection?

hellhound_01 104 Oct 31, 2012 at 11:00

Actually I try to implement a pixel perfect collision (PPC) detection for 2D sprites. For “normal” sprites anything is working perfectly. But how should I handle scaled and rotated sprites?

PPC is expensive, so I try to find an optimized solution to perform PPC. What is the best way I should go? Should I read the actual pixel data from pixel buffer and compare those or should I approximate the scaled values against the origin image data?

Actually I use this approximation attempt to check point based collisions,
but this works not realy good with scaled sprites:

bool brSprite::intersect(float x, float y)
    // first check if bounding rect collides with point positions
    bool collision = this->contains(x, y);
    // perform pixel perfect collision if required
    if(collision && m_usePPC)
      /* Substract actual rectangle position from point position value to
       reduce intersection point to image dimensions in range: [0,width]
       and [0,height].
       Please take note that we also have to regard the region x,y
       position values to determine correct image position in atlas
       textures and a scaling of the sprite.
        int pos_x = (int)((x - m_x)+m_region.getX()/m_scale.m_fX);
        int pos_y = (int)((y - m_y)+m_region.getY()/m_scale.m_fY);
        if(pos_x<m_width && pos_y<m_height){

            // define alpha compareable
            int alpha = 0;
                alpha = (255 * m_ppcTolerance)/100;

            // perform pixel perfect collision check
            brColor color = m_region.getImage()->getPixelColor(pos_x,pos_y);
                collision = true;
        collision = false;
    return collision;

Any Ideas?

5 Replies

Please log in or register to post a reply.

Stainless 151 Oct 31, 2012 at 12:15

An alternative to pixel perfect collision detection is using collision polygons.

In your editor, you create a polygon that closely fits the image.

It’s not perfect, but it’s a lot less complex and a lot quicker.

hellhound_01 104 Oct 31, 2012 at 12:21

Stainless you are right, this is an option. But I’ve to use PPC …

TheNut 179 Oct 31, 2012 at 13:40

In my UI system, I just compute the inverse transformation on the point and check against the image buffer. These checks are being performed every time the cursor position updates, so it’s quite frequent and I find the performance impact negligible. Tested on my netbook, it’s like a percentage or two of CPU usage with several dozen UI elements on the screen. The benefits of using matrix multiplication is that it covers all grounds (translation, rotation, scale, sheer), and simplifies my code to just an arithmetic operation on the point and inverse transformation matrix. With a UI, demands are much greater because you have to test all objects in front, which can require deep traversals and many tests. With game objects, I would take advantage of spatial partioning to reduce the number of tests. In my particular case, I’m not sure there would be benefits for doing two types of tests. A high level box check and then a low-level pixel check. In both cases, I need to transform the input point, so the hard work has already been done. Performing a point in box check is redundant in my case because my image object already performs boundary checks on accessors. So, naturally I would just request the alpha value at that particular (x,y), do the test, and move on.

hellhound_01 104 Nov 01, 2012 at 06:09

Hmm, sounds good. Nice idea using object transformation matrix operations.
I’ve to check this out.

alphadog 101 Nov 07, 2012 at 16:51

Why mustyou use PPC?

Between PPC and bounding boxes, as Stainless says, you can use more complex geometric shapes. I like techniques that use convex hulls.