Pixel Perfect Collision Detection using Color Blending

cocos2d for iPhone » Programming » cocos2d support (graphics engine)

Pixel Perfect Collision Detection using Color Blending

(167 posts) (46 voices)

Started 1 year ago by Dani
Latest reply from Dragyn

Tags:

12…6 Next »

Dani
Member
Hello everybody.

I would like to implement a function to detect collisions between 2 sprites at pixel level. There is a good solution I've used before in ActionScript 3, but I need help to integrate it with cocos2d framework.

Original AS2 solution: http://gskinner.com/blog/archives/2005/08/flash_8_shape_b.html

Improved AS3 solution: http://troygilbert.com/2007/06/pixel-perfect-collision-detection-in-actionscript3/

Now look at this image:

Look at the third case: the method consist on drawing the first sprite in RED, the second in WHITE (with DIFFERENCE blending mode), and look if there is CYAN in the mix. We only draw the data inside the intersection, not the whole sprites.

The steps:
1. Check for bounding box collision.
2. Get the intersect rect.
3. Create a bitmap object with the size of the intersection.
4. Draw the sprite A in RED (taking into account scaling, rotation, etc) into the bitmap object.
5. Draw the Sprite B in WHITE with DIFFERENCE blending (taking into account scaling, rotation, etc) into the same bitmap object.
6. Look if there is CYAN color in the bitmap object.
I don't know how and where to draw the intersection data for both objects (steps 3, 4 and 5). Any ideas?

This is how the function could look:
```
-(BOOL) isCollisionBetweenSpriteA:(CCSprite*)spr1 spriteB:(CCSprite*)spr2 pixelPerfect:(BOOL)pp
{
    BOOL isCollision = NO;
    CGRect intersection = CGRectIntersection([spr1 boundingBox], [spr2 boundingBox]);

    if (!CGRectIsEmpty(intersection))
    {
        // If we're not checking for pixel perfect collisions, return true
        if (!pp) {return YES;}

        // 1) Draw the Sprite 1 intersection content in RED color into a bitmap object (must check if it's rotated, scaled, etc)

        // 2) Draw the Sprite 2 intersection content in WHITE color using DIFFERENCE blending option into the same bitmap object

        // 3) Check if there is CYAN color in the mix (WHITE difference blended on RED makes CYAN)
    }

    return isCollision;
}
```
Please, any help and ideas to solve this will be very much appreciated. And maybe this function is a good feature for the cocos2d-iphone Extensions.

Regards.
Posted 1 year ago #
Angry Panda
Member

You could use a physics engine, will be a lot easier.

Posted 1 year ago #
Dani
Member

Uuumm, in fact this method is easier to use than Box2D, but hard to implement to me. It works very well for bullet collisions, because bullets are small and the intersection is small (tested on an old AS3 shooter game).

With this function you don't need worlds, shapes, etc. Only 2 sprites, call the function and it's done.

Any ideas on how to draw the intersection data?

Posted 1 year ago #
Birkemose
Administrator

"Easier" is a relative term in this case.

If you have a bounding box collision, you would probably render the two textures to a off screen surface, using an OpenGL filter that only rendered overlapping pixels.

The tricky part would be to detect if anything was rendered.

Posted 1 year ago #
Dani
Member

If you have a bounding box collision, you would probably render the two textures to a off screen surface, using an OpenGL filter that only rendered overlapping pixels.

What's an "off screen surface" in cocos2d or Objective-C? Is there any class that allows to make that? Could you give me some more clues and links to documentation about this subject?

The first step I need to solve is drawing the sprite texture data into a "bitmap object", but I don't know what classes to use for that, and I don't know how to take into account the sprite rotation and scale.

Thanks in advance.

Posted 1 year ago #
MichaelB
Member

CCRenderTexture and its getUIImageAsDataFromBuffer:kCCImageFormatRawData should help get you #1 and #2.

You'd need to handle drawing the sprites in the right relative position, rotation, scale compared to the overlapping area. You could make one full-size for sprite A so you're not creating them every time; but you'd only need to check the overlap pixels in your step #3.

I'd done something similar in the past--for a little speed improvement in your step #3, I did a checkerboard pattern, so only looking at 1/2 the pixels that way to keep that step faster.

Posted 1 year ago #
Birkemose
Administrator
Look up CCRenderTexture.

Basically it is just like rendering to the screen. Rotation and everything works. The basic syntax is
```
[ myRenderTexture begin ];
// set up any OpenGL stuff you like
[ myCCNode1 visit ]; // renders a CCNode
[ myCCNode2 visit ]; // renders another CCNode
[ myRenderTexture end ];
```
A this point you have a CCRenderTexture in memory, with myCCNode1 and myCCNode2 rendered upon it, just as if it was the screen. You can save the texture, or of cause render it to the screen. ( or in your case, check for collision )
Posted 1 year ago #
Birkemose
Administrator

As MichaelB says, the problem is not the render, but to access the pixels afterwards. Rendering the overlapping areas would be very very fast, but reading the pixels is slow.

I also think first option would be to copy them to a buffer, and then examine them in peace and quiet from the OpenGL pipeline.
Another idea would be to apply some sort of filter on the render result. I would not be surprised if you could apply a OpenGL filter that ex counted the sum of white. If collisions was rendered as white ( the rest black ), anything above 0.00f would be a collision.
And that would be fast. Very fast.

Posted 1 year ago #
indy2005
Member

Hi,

If you use a physics engine, you get the benefit of still detecting a collision when objects move so fast they pass over each other in one time step. You don't get that with this method.

Posted 1 year ago #
araker
Moderator
@indy, even chipmunk doesn't have that feature, it all depends whether or not you have that kind of fast moving objects.

@Dani
I would create a render texture with the size of the screen, render the sprites completely and only check for collision in the intersection part. This is faster than creating a new render texture with different dimensions for every collision.

Getting the color values needs to be done with glReadPixels, which is a expensive operation. To minimize the cost of it, I would recommend the following structure. It's best to execute this a the begin or at the end of a frame.
```
//create a clear sprite
CCSprite *clearSprite = [[CCSprite alloc] init];
[clearSprite setColor:(ccColor3b) {0,0,0}];
[clearSprite setTextureRect:CGRectMake(0.f,0.f,screen.width,screen.height)];
[clearSprite setAnchorPoint:ccp(0.f,0.f)];

ccColor4B color;

[rt beginWithClear:0.0f g:0.0f b:0.0f a:1.0f];
[node1 visit];
[node2 visit];

//get color values of intersection area
//glReadPixels uses a different coordinate system where (0,0) is top left instead of bottom left.

ccColor4B *buffer = malloc(sizeof(ccColor4B)*width*height);
glReadPixels(x,y,widthOfIntersection,heightOfIntersection,GL_RGBA,GL_UNSIGNED_BYTE, buffer);
//read out buffer

//finished, clear buffer again for next collision
//this is faster than using glClearColor
[clearSprite visit];

//draw next nodes

[rt end];
[clearSprite release];
```
More examples of glReadPixels can be found in -getUIImageFromBuffer and -getUIImageAsDataFromBuffer methods of the render texture.

Too bad there's nothing in OpenGL 1.1 that can act as a filter to get the result quickly, glReadPixels is the only option.
Posted 1 year ago #
Dani
Member
@indy2005: I didn't had the pass over problem using this in AS3. Also, physics engines are good for physic based games. An old arcade shooter like 19XX didn't need a physics engine, only a pixel perfect collision detection function. I think that a good 2D video game framework should provide a built in collision detection function for both bounding box and pixel perfect based options independent from a whole physics engine, and cocos2d doesn't provide the built in pixel perfect option. It's my opinion.

This method works well, and it's easier to use for a non physics game (where you don't need friction, density, shapes and all that stuff). For now, to use physics engines is my last option. I think it's interesting to make this pixel perfect method work and test it to make a comparison.

@MichaelB and @Birkemose: thanks for your help, very useful; I added some lines inside the function:
```
-(BOOL) isCollisionBetweenSpriteA:(CCSprite*)spr1 spriteB:(CCSprite*)spr2 pixelPerfect:(BOOL)pp
{
    BOOL isCollision = NO;
    CGRect intersection = CGRectIntersection([spr1 boundingBox], [spr2 boundingBox]);

    if (!CGRectIsEmpty(intersection))
    {
        // If we're not checking for pixel perfect collisions, return true
        if (!pp) {return YES;}

        NSLog(@"Intersection: x=%f y=%f",intersection.origin.x,intersection.origin.y);

        [_rt beginWithClear:0 g:0 b:0 a:0];
        [spr1 visit];
        [spr2 visit];
        [_rt end];

        // 1) Draw the Sprite 1 intersection content in RED color into a bitmap object (must check if it's rotated, scaled, etc)

        // 2) Draw the Sprite 2 intersection content in WHITE color using DIFFERENCE blending option into the same bitmap object

        // 3) Check if there is CYAN color in the mix (WHITE difference blended on RED makes CYAN)
    }

    return isCollision;
}
```
Now we got the two sprites rendered in _rt (it's a CCRenderTexture object) with rotation and scale, but I don't know what gl function to use to draw the first sprite in RED and the second in WHITE with DIFFERENCE blending.

Any suggestions?

EDIT: @araker, I just saw your reply, I'm going to read it :D
Posted 1 year ago #
araker
Moderator

Regarding the color part, try to use glColorMask before visiting the sprite and use (for instance) red for one sprite and green for the other. Then check in the intersection if red and green have a value > 0.

Posted 1 year ago #

Dani
Member

@araker: Thanks for your sample code, very helpful; I have modified the function, and it's detecting collisions, but it fails in some cases. I think I'm not looping and reading the buffer in the correct way.

This is what's happening in the simulator:

And this is the current function:

-(BOOL) isCollisionBetweenSpriteA:(CCSprite*)spr1 spriteB:(CCSprite*)spr2 pixelPerfect:(BOOL)pp
{
    BOOL isCollision = NO;
    CGRect intersection = CGRectIntersection([spr1 boundingBox], [spr2 boundingBox]);

    if (!CGRectIsEmpty(intersection))
    {
        // If we're not checking for pixel perfect collisions, return true

        if (!pp) {return YES;}

        // Draw the sprites in RED and GREEN into the RenderTexture

        [_rt beginWithClear:0 g:0 b:0 a:1];
        glColorMask(1, 0, 0, 1);
        [spr1 visit];
        glColorMask(0, 0, 0, 1);
        [spr2 visit];
        glColorMask(1, 1, 1, 1);
        [_rt end];

        // Get color values of intersection area
        // glReadPixels uses a different coordinate system where (0,0) is top left instead of bottom left.

        CGSize winSize = [[CCDirector sharedDirector] winSize];
        unsigned int numPixels = intersection.size.width * intersection.size.height;
        ccColor4B *buffer = malloc(sizeof(ccColor4B)*numPixels);
        glReadPixels(intersection.origin.x, winSize.height-intersection.origin.y, intersection.size.width, intersection.size.height, GL_RGBA, GL_UNSIGNED_BYTE, buffer);

        // Read buffer and look for pixels with RED and GREEN

        unsigned int step = 2;
        for(unsigned int i=0; i<numPixels; i+=step)
        {
            ccColor4B color = buffer[i];
            if (color.r > 0 && color.g > 0)
            {
                isCollision = YES;
                break;
            }
        }

        // Free buffer memory
        free(buffer);
    }

    return isCollision;
}

The sprite 1 renders in RED, and the sprite 2 renders in GREEN, this part works. The mixture gives some colors next to YELLOW, and that's ok too. But I think that the loop for cheking colors is wrong, am I reading the buffer in the correct way?

Thanks in advance.

Posted 1 year ago #

Birkemose
Administrator

What you are trying to do, is hard to test, so an important step would be to visualize it in some way.
Maybe render the result in some way?

Cool jets BTW :)

Posted 1 year ago #
araker
Moderator
Now glReadPixels reads the frame buffer of the screen, not the buffer from the render texture. That's why glReadPixels needs to be called before [rt end];

The color mask is also not completely correct, try
```
[_rt beginWithClear:0 g:0 b:0 a:0]; //no alpha in the rt
        glColorMask(1, 0, 0, 1);
        [spr1 visit];
        glColorMask(0, 1, 0, 1);
        [spr2 visit];
        glColorMask(1, 1, 1, 1);
        [_rt end];
```
One other thing this won't work if both of your sprites have large completely black areas. As long as you use (1,1,0) instead of (0,0,0) for black that won't be a issue. In the article you've linked to they've extracted the alpha channel and put that into a separate color channel, that's the completely foolproof way.
Posted 1 year ago #
Dani
Member
@araker: Ok, I fixed those problems; but I think that the problem is in this piece of code:
```
ccColor4B *buffer = malloc( sizeof(ccColor4B) * numPixels );
        CGSize winSize = [[CCDirector sharedDirector] winSize];
        glReadPixels(x, winSize.height-y, w, h, GL_RGBA, GL_UNSIGNED_BYTE, buffer);

// Read buffer
        unsigned int step = 1;
        for(unsigned int i=0; i<numPixels; i+=step)
        {
            ccColor4B color = buffer[i];

            if (color.r > 0 && color.g > 0)
            {
                NSLog(@"\nCollision at pixel %u",i);
                isCollision = YES;
                break;
            }
        }
```
I don't know how to retrieve ccColor4B objects from the buffer. Please help.

Also I have noticed that cocos2d boundingBox method is not calculating the correct bounding box when the sprites are rotated, look at this screen from the simulator:

At the top there are the sprites. At the bottom there is the CCRenderTexture object visible. The sprites bounding boxes are being calculated using [spr boundingBox] and are drawn in real time, in red and green. The intersection is drawn in blue. The green bounding box should be smaller. Is it a cocos2d bounding box method bug? I'm using the last cocos2d version.
Posted 1 year ago #
malphigian
Member

No bugs of that sort with bounding box, more likely it's transparent pixels in your image. Either crop the image or if youre using a tool like zwotpex you can subtract the offset.

Posted 1 year ago #
itlgames
Key Master

I think it's actually right, it's the bounding box that contains the rotated PNG file, so it's normal is bigger.

Posted 1 year ago #

Dani
Member

@malphigian and @itlgames: You're right, the bounding box is adjusted to the corners of the rotated sprite, that's why it's bigger.

I still need help with this:

ccColor4B *buffer = malloc( sizeof(ccColor4B) * numPixels );
        CGSize winSize = [[CCDirector sharedDirector] winSize];
        glReadPixels(x, winSize.height-y, w, h, GL_RGBA, GL_UNSIGNED_BYTE, buffer);

// Read buffer
        unsigned int step = 1;
        for(unsigned int i=0; i<numPixels; i+=step)
        {
            ccColor4B color = buffer[i];

            if (color.r > 0 && color.g > 0)
            {
                isCollision = YES;
                break;
            }
        }

How do you read the data from the buffer so that the variable color, a ccColor4B, contains the next color of the buffer? Has someone done this before? What's the content of the variable buffer and how do I access it?

Posted 1 year ago #

Dani
Member

Ok, people, it seems that the function is working fine now. I was passing the wrong y parameter to the glReadPixels. Here's is the complete function:

-(BOOL) isCollisionBetweenSpriteA:(CCSprite*)spr1 spriteB:(CCSprite*)spr2 pixelPerfect:(BOOL)pp
{
    BOOL isCollision = NO;
    CGRect intersection = CGRectIntersection([spr1 boundingBox], [spr2 boundingBox]);

    // Look for simple bounding box collision
    if (!CGRectIsEmpty(intersection))
    {
        // If we're not checking for pixel perfect collisions, return true
        if (!pp) {return YES;}

        // Get intersection info
        unsigned int x = intersection.origin.x;
        unsigned int y = intersection.origin.y;
        unsigned int w = intersection.size.width;
        unsigned int h = intersection.size.height;
        unsigned int numPixels = w * h;

        // Draw into the RenderTexture
        [_rt beginWithClear:0 g:0 b:0 a:0];

        // Render both sprites: first one in RED and second one in GREEN
        glColorMask(1, 0, 0, 1);
        [spr1 visit];
        glColorMask(0, 1, 0, 1);
        [spr2 visit];
        glColorMask(1, 1, 1, 1);

// Read pixels
        ccColor4B *buffer = malloc( sizeof(ccColor4B) * numPixels );
        CGSize winSize = [[CCDirector sharedDirector] winSize];
        glReadPixels(x, y, w, h, GL_RGBA, GL_UNSIGNED_BYTE, buffer);

        [_rt end];

        // Read buffer
        unsigned int step = 1;
        for(unsigned int i=0; i<numPixels; i+=step)
        {
            ccColor4B color = buffer[i];

            if (color.r > 0 && color.g > 0)
            {
                isCollision = YES;
                break;
            }
        }

        // Free buffer memory
        free(buffer);
    }

    return isCollision;
}

_rt is a CCRenderTexture class variable. And you can change the variable step for speed up the loop.

Thanks everybody for the help and tips.

Posted 1 year ago #

wilczarz
Member

This code looks awesome, it's so clean :) I will check it out soon, but thanks anyway!

Posted 1 year ago #
coconut
Member

Looks awesome,
however it seems to work if the background is black.

If there is another sprite (various color values) in the background intersection rectangle it reads background's r/g/b values.

Is there a way to have only spr1 and spr2 in _rt?

Posted 1 year ago #
Rani
Member

Maybe render it on a white or transparent background?

Posted 1 year ago #
araker
Moderator

@coconut, what's exactly your problem?

The two sprites are placed in an off-screen buffer where there is no interference from other layers/sprites that are visible on screen. So background sprites shouldn't be a problem.

Posted 1 year ago #
Dani
Member

Hello everybody.

@coconut: I think there is no problem with multiple sprites. As @araker said, only the two sprites for wich you are checking collision are being rendered into the CCRenderTexture.

See the picture below taken from simulator:

There are 3 sprites (top of the screen, one tinted to red to visually represent collisions), but the function only renders the two you are cheking (at the bottom is the CCRenderTexture content, where you check for collision, only two sprites).

Regards.

Posted 1 year ago #
coconut
Member

Sorry for post editing,
my problem is that if there is another sprite (various color values) in the background of intersection rectangle it reads background's r/g/b values.

So, collision detection only works if I have sprites on black background.

Posted 1 year ago #
Dani
Member

@coconut: Here is the sample project: Pixel Perfect Collision Detection Sample Project.

Regards.

Posted 1 year ago #
itlgames
Key Master

@Dani thanks for the sharing, just tried out of curiosity and on a iPod 1G the FSP drops to 5, it's fine on an iPhone 4, I guess the pixel check is pretty CPU intensive for old devices.

Posted 1 year ago #
Questor
Member

@itagames

I don't think it is necessarily the pixel check that is generating the performance hit you are seeing. Rather it is more likely the rendering of the result that is causing the FPS hit. The rendering technique is not optimal since (per the posts above) it was done primarily for debugging/visualization of the collision. I would suggest commenting out the drawing code to see the real performance of the pixel check.

Posted 1 year ago #
itlgames
Key Master

@Qeustor, I did comment the drawing of the render texture, basically I create the texture and don't add to the layer (I just need to retain otherwise will be autoreleased too soon), I also commented all the extra drawing, and makes no difference. Ok I'm not 100% sure is the pixel check, but definitively it's not the rendering of the result.

@Dani by no means I'm trying to sound negative, it's pretty cool this code and nice you shared, but just thought would be nice to point the performance issue.

Posted 1 year ago #

RSS feed for this topic

12…6 Next »

Reply »

You must log in to post.