# Pixel Perfect Collision problems

This topic is 3309 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

Hi all! I'm working on a 2D-engine using SDL. It's going pretty well, except i don't get my pixel-perfect collision detection to work properly. I know that pixel-perfect collision are expensive, and I won't use it for every collision. I still want it to work though. First I do a simple boundingbox-collision test. If there is a collision, I jump to checkPixelPerfectCollision(). I have the theory straight I think, but the problem seems to be (at least I think) that when I try to get the color value of a certain pixel, it gives me a completely false RGB-value. I guess my algorithm for getting the pixel is wrong. Here's the code anyway... please help me :'< bool CEntity::checkPixelPerfectCollision(CEntity* obj) { SDL_Rect A; A.x = m_X; A.y = m_Y; A.w = m_Width; A.h = m_Height; SDL_Rect B; B.x = obj->getX(); B.y = obj->getY(); B.w = obj->getWidth(); B.h = obj->getHeight(); SDL_Rect AB; if(A.x > B.x) { AB.x = A.x; AB.w = (B.x + B.w) - A.x; } else { AB.x = B.x; AB.w = (A.x + A.w) - B.x; } if(A.y > B.y) { AB.y = A.y; AB.h = (B.y + B.h) - A.y; } else { AB.y = B.y; AB.h = (A.y + A.h) - B.y; } int numberOfPixels = AB.w * AB.h; SDL_Surface* tmpA; SDL_Surface* tmpB; tmpA = SDL_CreateRGBSurface(SDL_HWSURFACE, AB.w, AB.h, 32, 0, 0, 0, 0); tmpB = SDL_CreateRGBSurface(SDL_HWSURFACE, AB.w, AB.h, 32, 0, 0, 0, 0); SDL_SetColorKey(tmpA, SDL_SRCCOLORKEY, SDL_MapRGB(tmpA->format, 255, 0, 255)); SDL_SetColorKey(tmpB, SDL_SRCCOLORKEY, SDL_MapRGB(tmpB->format, 255, 0, 255)); SDL_BlitSurface(m_Sprite->getBitmap(), &AB, tmpA, NULL); SDL_BlitSurface(obj->getSprite()->getBitmap(), &AB, tmpB, NULL); Uint32* transparent = (Uint32*)SDL_MapRGB(tmpA->format, 255, 0, 255); Uint8 r = 0; Uint8 g = 0; Uint8 b = 0; Uint8 r1 = 0; Uint8 g1 = 0; Uint8 b1 = 0; for(int y = 1; y < numberOfPixels; y++) { for(int x = 1; x < numberOfPixels; x++) { //Uint32* pixelA = (Uint32*)(tmpA->pixels + y * tmpA->pitch + x * 2); Uint32* pixelB = (Uint32*)(tmpB->pixels + y * tmpB->pitch + x * 2); Uint32* pixelA = (Uint32*)(tmpA->pixels + y * tmpA->pitch + x * 2); SDL_GetRGB(*pixelA, SDL_GetVideoInfo()->vfmt, &r, &g, &b); SDL_GetRGB(*pixelB, SDL_GetVideoInfo()->vfmt, &r1, &g1, &b1); Uint32 *pxA = (Uint32*)SDL_MapRGB(tmpA->format, r, g, b); Uint32 *pxB = (Uint32*)SDL_MapRGB(tmpB->format, r1, g1, b1); if(pxA != transparent && pxB != transparent) { return true; } else { return false; } } } }

##### Share on other sites
Well, for starters, your pixel collision detection code does not take into account the relative position between the two sprites.

##### Share on other sites
Ok, and what is that supposed to mean?

##### Share on other sites
Well, take a look at those lines:
SDL_BlitSurface(m_Sprite->getBitmap(), &AB, tmpA, NULL);
SDL_BlitSurface(obj->getSprite()->getBitmap(), &AB, tmpB, NULL);

You draw both sprites at the same position on tmpA and tmpB. You do your calculations as if both sprites' x and y positions are the same - and usually they aren't.

You should do something like this:
SDL_Rect relativeA;
relativeA.x=A.x-AB.x;
relativeA.y=A.y-AB.y;
SDL_Rect relativeB;
relativeB.x=B.x-AB.x;
relativeB.y=B.y-AB.y;
SDL_BlitSurface(m_Sprite->getBitmap(), &relativeA, tmpA, NULL);
SDL_BlitSurface(obj->getSprite()->getBitmap(), &relativeB, tmpB, NULL);

You can use the rects A and B instead of making new ones, but I gave them new names to make it easier to understand.

##### Share on other sites
Am I supposed to this in the chain of if:s when setting the AB-values, or after?
I don't really think I understand the idea.

##### Share on other sites
You do this after the chain of ifs, when the values of AB are already set.

Take a look at this picture:

The right part of the picture is the screen. The green area is the collision are between the bounding boxes of the two sprites, and is represented by AB. You calculate the relative position of A from the AB(notice that in this case, relativeA.x and relativeA.y are negative, because A is located up and left from AB). After that, you draw A to tmpA - the left part of the picture. You draw it at relativeA, so only the section of A that is colliding with B will be drawn to tmpA, and it will be draw at the correct location.

You do the same thing with B, and you'll have two SDL_Surfaces that represent the colliding sections of tmpA and tmpB. You know what to do from here...

##### Share on other sites
Allright! I think I understand now why to use these variables.
My other problem is that I allways get a junk value from SDL_GetRGB().
I want r, g and b to take the corresponding values of the currently selected pixel. But i always end up with something like (200, 59, 91). Odd.
Wouldn't it be nice if SDL stored each single pixel as a struct, holding x, y, and SDL_Color. :(

##### Share on other sites
You should pass the surface format to SDL_GetRGB:
Uint32* pixelA = (Uint32*)(tmpA->pixels + y * tmpA->pitch + x * 2);SDL_GetRGB(*pixelA, tmpA->format, &r, &g, &b);

Or you could use the getpixel/setpixel functions from the SDL documentation.

It is possible to do this without allocating additional surfaces.

##### Share on other sites
IMO, pixel perfect collision detection is more trouble than it's worth. Generating a few polygons for each object is easy to code, is much faster to execute, gives you much more information (penetration depth, collision normal) from which to perform collision response, and is almost as accurate.

##### Share on other sites
"IMO, pixel perfect collision detection is more trouble than it's worth. Generating a few polygons for each object is easy to code, is much faster to execute, gives you much more information (penetration depth, collision normal) from which to perform collision response, and is almost as accurate."

Yes, well thanks for the input, but as I mentioned in OP it is not a matter of saving processor-speed. I just want to learn how to make pixel perfect collision testing, because I think that it would be a nice thing to know.

##### Share on other sites
Edit: sry for doublepost

##### Share on other sites
Ok so I've changed a bit in my code. It now looks like this:

bool CEntity::checkPixelPerfectCollision(CEntity* obj)
{
SDL_Rect A;
A.x = m_X;
A.y = m_Y;
A.w = m_Width;
A.h = m_Height;

SDL_Rect B;
B.x = obj->getX();
B.y = obj->getY();
B.w = obj->getWidth();
B.h = obj->getHeight();

SDL_Rect AB;

SDL_Rect relativeA;
SDL_Rect relativeB;

if(A.x > B.x) {
AB.x = A.x;
AB.w = (B.x + B.w) - A.x;
} else {
AB.x = B.x;
AB.w = (A.x + A.w) - B.x;
}
if(A.y > B.y) {
AB.y = A.y;
AB.h = (B.y + B.h) - A.y;
} else {
AB.y = B.y;
AB.h = (A.y + A.h) - B.y;
}

relativeA.w = relativeB.w = AB.w;
relativeA.h = relativeB.h = AB.h;

relativeA.x = A.x - AB.x;
relativeA.y = A.y - AB.y;
relativeB.x = B.x - AB.x;
relativeB.y = B.y - AB.y;

SDL_Surface* tmpA = SDL_CreateRGBSurface(SDL_HWSURFACE, AB.w, AB.h, 32, 0, 0, 0, 0);
SDL_Surface* tmpB = SDL_CreateRGBSurface(SDL_HWSURFACE, AB.w, AB.h, 32, 0, 0, 0, 0);

SDL_SetColorKey(tmpA, SDL_SRCCOLORKEY, SDL_MapRGB(tmpA->format, 255, 0, 255));
SDL_SetColorKey(tmpB, SDL_SRCCOLORKEY, SDL_MapRGB(tmpB->format, 255, 0, 255));

SDL_BlitSurface(m_Sprite->getBitmap(), &relativeA, tmpA, NULL);
SDL_BlitSurface(obj->getSprite()->getBitmap(), &relativeB, tmpB, NULL);

SDL_BlitSurface(tmpA, &relativeA, SDL_GetVideoSurface(), NULL);

Uint8 r1 = 0;
Uint8 g1 = 0;
Uint8 b1 = 0;

Uint8 r = 0;
Uint8 g = 0;
Uint8 b = 0;

for(int y = 0; y < AB.h + 1; y++) {
for(int x = 1; x < AB.w + 1; x++) {
Uint32 pixelA = CSpriteManager::getSingelton()->getPixel(tmpA, x, y);
Uint32 pixelB = CSpriteManager::getSingelton()->getPixel(tmpB, x, y);

SDL_GetRGB(pixelA, tmpA->format, &r, &g, &b);
SDL_GetRGB(pixelB, tmpB->format, &r1, &g1, &b1);

Uint32 pxA = SDL_MapRGB(tmpA->format, r, g, b);
Uint32 pxB = SDL_MapRGB(tmpB->format, r1, g1, b1);

if(pxA == tmpA->format->colorkey && pxB == tmpB->format->colorkey) {
SDL_FreeSurface(tmpA);
SDL_FreeSurface(tmpB);
return true;
}
if(x == AB.w) {
x = 0;
}
}
}
SDL_FreeSurface(tmpA);
SDL_FreeSurface(tmpB);
return false;
}

============================================================

I really can't see where this goes wrong. While debugging it turns out that getPixel(SDL_Surface* surf, int x, int y) return either '0' or '65535'. This is wrong. Or is it? Taking a closer look at the variables, it turns out that the Uint32 returned from getPixel, with the value 65535, contains three other values. p[0] = 255, p[1] = 255, p[2] = 0.
Coincidence? I think not!
That happens to be the color of the entity i am testing collision with. Well. Great! So that works. But why in fucks name do I get p[0] = 0, p[1] = 0, p[2]= 0, when testing my "playerEntity"?
Allright, It LOOKS like there is black background surrounding "playerEntity", but that is because colorkey has rendered the original cyan-colored background transparent.
Help me. Where is my problem?

##### Share on other sites
This is some code that I used when I cared about pixel perfect collision. This code is from before 2005 and I am updating/cleaning it now without testing, but the basics should be the same.

The one important thing to mention was that I modified the getpixel function to return a transparent pixel if the co-ordinates weren't inside the surface. Quite a hack, but do take into account the origin of this code - one of my first adventures in C++.

The code will likely segfault horribly on the getpixel provided by the SDL documentation wiki.
struct Point{	int x, y;};Uint32 transparent_pixel( const SDL_Surface *surface ){	return surface->format->colorkey;}bool pixel_perfect_collision(const Point &p1, SDL_Surface *one, const Point &p2, SDL_Surface *two){	Point start1, start2, end;	// x direction:	if( p1.x < p2.x )	{		start1.x = p2.x - p1.x;		start2.x = 0;		end.x = std::min( two->w, start1.x + one->w );	}	else	{		start1.x = 0;		start2.x = p1.x - p2.x;		end.x = std::min( one->w, start1.x + two->w );	}	// y direction:	if( p1.y < p2.y )	{		start1.y = p2.y - p1.y;		start2.y = 0;		end.y = std::min( two->h, start1.y + one->h );	}	else	{		start1.y = 0;		start2.y = p1.y - p2.y;		end.y = std::min( one->h, start1.y + two->h );	}	Uint32 transparent1 = transparent_pixel( one );	Uint32 transparent2 = transparent_pixel( two );	if( SDL_MUSTLOCK(one) )	{		SDL_LockSurface(one);	}	if( SDL_MUSTLOCK(two) )	{		SDL_LockSurface(two);	}	bool colliding = false;	for( int x = 0; x < end.x && !colliding;  ++x )	{		for( int y = 0; y < end.y && !colliding ; ++y )		{			if( getpixel( one, x + start1.x, y + start1.y ) != transparent1 && 				getpixel( two, x + start2.x, y + start2.y ) != transparent2 )			{				colliding = true;			}		}	}	if( SDL_MUSTLOCK(one) )	{		SDL_UnlockSurface(one);	}	if( SDL_MUSTLOCK(two) )	{		SDL_UnlockSurface(two);	}	return colliding;}