   Per-Pixel Collision Detection - Unsolved
  I have posted a post here before about this it was orignally for an invalid pointer. I managed to fix that so that it detected collision. How ever I have noticed something about this system.When I changed the paddel of my pong game so that it has a empty center where the ball should pass though due to there being the correct alpha value. It still manages to hit that area. Therefore I have posted the code below to see if you guys can help me figure out why. I think it might be the way im extracting the alpha values into a array of bytes, I am however unsure. I would be very greatful if you could help me figure out why.I used this resource for most of my collision detection code. I also have wondered perhaps if this article is purely related to rectangular detection, and can not detect more irregular shaped (a bent rectangle perhaps). If thats the case what type of collision detection am I looking for?Also, this uses the HGE library for those who don't know./***************************************************************************************** CSprite.h****************************************************************************************/#ifndef __CSPRITE_H__#define __CSPRITE_H__class CSprite{public:// constructorsCSprite();CSprite(HTEXTURE tex, float x, float y, float w, float h);// destructor~CSprite();// Check collision.bool spriteCollide(CSprite *sprite);// load texture.void loadTexture(HGE* hge, const char* fileName,float x, float y, float w, float h);// Cleanup texturesvoid cleanup(HGE *hge);// Basic inline functions that are used to return values.inline void setXY(float x, float y) { xPosition = x; yPosition = y; }inline float getX() { return xPosition; }inline float getY() { return yPosition; }inline float getWidth() { return (float)width; }inline float getHeight() { return (float)height; }inline hgeSprite *getSprite() { return currentSprite; }inline unsigned char* getAlpha() { return alpha; }private:intheight;intwidth;floatxPosition;floatyPosition;// Holds the sprite textureHTEXTUREspriteTexture;// Holds the sprite objecthgeSprite*currentSprite;// Used to hold the alpha values of the textureunsigned char*alpha;};#endif/***************************************************************************************** CSprite.cpp****************************************************************************************/#include "MainIncludes.h"#include "CSprite.h"CSprite::CSprite(): spriteTexture(NULL){}// Overloaded constructor.CSprite::CSprite(HTEXTURE tex, float x, float y, float w, float h){currentSprite = new hgeSprite(tex, x, y, w, h);}CSprite::~CSprite(){// deletes the sprite.if(currentSprite){delete currentSprite;}// Deletes the pointer alphaif(alpha){delete alpha;}}// Cleans up the texture.void CSprite::cleanup(HGE *hge){if(spriteTexture != NULL){hge->Texture_Free(spriteTexture);spriteTexture = NULL;}}// Loads a texture and creates the sprite.void CSprite::loadTexture(HGE* hge, const char *filename,  float x, float y, float w, float h){// load the texture.spriteTexture = hge->Texture_Load(filename);if(!spriteTexture){char errorMsg[256];sprintf(errorMsg,"%s",filename);MessageBox(NULL, errorMsg, "Error", MB_OK | MB_ICONERROR | MB_SYSTEMMODAL);hge->System_Shutdown();hge->Release();}// make the spritecurrentSprite = new hgeSprite(spriteTexture, x, y, w, h);height = (int)h;width = (int)w;// Create an array for alpha values.alpha=new unsigned char[size_t(w*h)];// Lock the texture.unsigned char *point = (unsigned char*)hge->Texture_Lock(spriteTexture, true, (int)x, (int)y, (int)w, (int)h);int f = 0;// Get the alpha values for the texture.for(int i=0; i<w*h; i+=3){alpha[f] = (unsigned char)point;point++;f++;}hge->Texture_Unlock(spriteTexture);point = NULL;}// Check for per pixel sprite collision, between// this sprite and the sprite sent via paramater.bool CSprite::spriteCollide(CSprite *sprite){float left1=0.0f, left2=0.0f, over_left=0.0f;float right1=0.0f, right2=0.0f, over_right=0.0f;float top1=0.0f, top2=0.0f, over_top=0.0f;float bottom1=0.0f, bottom2=0.0f, over_bottom=0.0f;float over_width=0.0f, over_height=0.0f;int i=0, j=0;unsigned char *pixel1, *pixel2;left1 = this->getX();left2 = sprite->getX();right1 = this->getX() + this->getWidth();right2 = sprite->getX() + sprite->getWidth();top1 = this->getY();top2 = sprite->getY();bottom1 = this->getY() + this->getHeight();bottom2 = sprite->getY() + sprite->getHeight();// Trivial rejections:if (bottom1 < top2){return false;}if (top1 > bottom2){return false;}if (right1 < left2){return false;}if (left1 > right2){return false;}// Ok, compute the rectangle of overlap:if (bottom1 > bottom2) over_bottom = bottom2;else over_bottom = bottom1; if (top1 < top2) over_top = top2;else over_top = top1;if (right1 > right2) over_right = right2;else over_right = right1;if (left1 < left2) over_left = left2;else over_left = left1;over_width = over_right - over_left;over_height = over_bottom - over_top;// Now compute starting offsets into both objects' bitmaps:i = (int)((over_top - this->getY()) * this->getWidth()) + over_left;pixel1 = alpha + (unsigned char)i;j = (int)((over_top - sprite->getY()) * sprite->getWidth()) + over_left;pixel2 = sprite->getAlpha() + (unsigned char)j;  // Now start scanning the whole rectangle of overlap,// checking the corresponding pixel of each object's// bitmap to see if they're both non-zero:for (i=0; i < over_height; i++) {for (j=0; j < over_width; j++) {if ((*pixel1 > 0) && (*pixel2 > 0)) return true;pixel1++;pixel2++;}pixel1 += unsigned char(this->getWidth() - over_width);pixel2 += unsigned char(sprite->getWidth() - over_width);}// Worst case!  We scanned through the whole darn rectangle of overlap // and couldn't find a single colliding pixel!return false;}EDIT:I don't believe it matters, but I am using PNG files with a transparent background when loading textures for sprites.[Edited by - DevLiquidKnight on May 28, 2006 11:49:53 AM]
  Hmm, it looks okay at a glance. Have you checked to make sure your alpha values are correct? ... you could try drawing only the alpha value in your render section to find out.   ;  1> Make the anomolous situation reproduceable.  (ie, ball is in the gap inside a paddle).2> Step through the collision code.3> Find out which bit of logic is saying "we have collided".4> Hit your head and say "this is obvious" -- or come back with that bit of information.;Quote:Original post by NotAYakk1> Make the anomolous situation reproduceable.  (ie, ball is in the gap inside a paddle).2> Step through the collision code.3> Find out which bit of logic is saying "we have collided".4> Hit your head and say "this is obvious" -- or come back with that bit of information.I've already done that when it collides with the object the reasons it says it has collided is very obvious if you read the code I posted. The pixel data being scanned obviously is above 0. When infact nearly the entire paddel is transparent. The data inside the debugger that the pixels use is as follows:+ pixel2 0x0b4da844 "Ú´z?Oþ>Üø¿>¼?àA{½Š˜¿...... etc unsigned char *+ pixel1 0x0b4d943b "ÀÌØäðü? ,8DP\ht€Œ˜¤°¼ÈÔàìø(4@LXdp|ˆ" ¬¸ÄÐÜèô"unsigned char *;  What are you using to generate your images? I noticed that GIMP sometimes (at least for me) saves colors slightly off of their intended value, or the color picking tool doesn't always do quite what you told it to do.I had a problem similar to yours, in which pixels had an alpha value of 1/255 instead of 0/255.  It definitely caused me a lot of frustration; I thought the problem was in my image loading code or my algorithm in general.I didn't look too closely at your code - I thought I would just alert you of this potential problem before you spent any more time in your code.;  Another supposition: if you base your alpha color to 0, make sure it really equals to 0. Maybe your pad isn't completely transparent, but have an alpha value like 1 or 2, which is barely noticeable for the human eye.   ;  I've already considered extralongpants, and PERECil suggestions. For the record I am using adobe photoshop to generate the images. That being said I have considered what you have proposed.I have tried by increasing the 0 in the check for pixel collision to for instance 10, instead of 0. This should in theory make it so that if such small alpha values were off slightly. It still would ignore the pixels as being un transparent. I get the same result this way as well.There was also the possibility seeing as how HGE library works that it could automatically pad my images dimensions. I am not sure if it does this by resizing them, as a result I took that into account already as well.   ;  Your code contained a couple of mistakes plus quite a lot of questionable design decisions.  Some of the changes here are personal preferences I made just because it was easier for me to write the code that way.  Unless otherwise noted you should feel free to change it back to your conventions.  I've had to make some assumptions where the HGE documentation is underspecified.  It hasn't been tested, so there are probably lots of errors.// Texture.h#if !defined(PROJECT_PREFIX_TEXTURE)#define PROJECT_PREFIX_TEXTURE#include <cstddef>#include <string>#include <boost/shared_ptr.hpp>// hge includesclass Texture{public:Texture(HGE * hge, std::string const & filename);HTEXTURE handle() const;std::size_t height() const;HGE * hge() const;std::size_t width() const;private:static void deleteTexture(HGE * hge, HTEXTURE * textureHandle);HGE * hge_;boost::shared_ptr< HTEXTURE > texture_;};#endif// Texture.cpp#include "Texture.h"#include <boost/bind.hpp>#include <boost/function.hpp>Texture::Texture(HGE * hge, std::string const & filename):hge_(hge){assert(hge);assert(!filename.empty());HTEXTURE textureHandle = hge->Texture_Load(filename.c_str());boost::function< void (HTEXTURE *) > deleter = boost::bind(&Texture::deleteTexture, hge_, _1);if (textureHandle){texture_.reset(new HTEXTURE(textureHandle), deleter);}else{throw std::runtime_error("Failed loading texture");}}HTEXTURE Texture::handle() const{return *texture_;}std::size_t Texture::height() const{return hge_->Texture_GetHeight(*texture_);}HGE * Texture::hge() const{return hge_;}std::size_t Texture::width() const{return hge_->Texture_GetWidth(*texture_);}void Texture::deleteTexture(HGE * hge, HTEXTURE * textureHandle){assert(hge);assert(textureHandle);assert(*textureHandle);hge->Texture_Free(*textureHandle);delete textureHandle;}// TextureData.h#if !defined(PROJECT_PREFIX_TEXTURE_DATA)#define PROJECT_PREFIX_TEXTURE_DATA#include "Texture.h"// hge includesclass TextureData{public:TextureData(Texture const & texture);~TextureData();unsigned char operator[](std::size_t index) const;private:// Explicitly disable copying - you could write these if// you wanted - but I don't need them for this exampleTextureData(TextureData const & textureData);TextureData & operator=(TextureData const & textureData);HGE * hge_;Texture const & texture_;unsigned char * data_;};#endif// TextureData.cpp#include "TextureData.h"TextureData::TextureData(Texture const & texture):hge_(texture.hge()),texture_(texture),data_(reinterpret_cast< unsigned char * >(hge_->Texture_Lock(texture.handle(), true))){// Error checkingif (!data_){throw std::runtime_error("Failed locking texture");}}TextureData::~TextureData(){hge_->Texture_Unlock(texture_.handle());}unsigned char TextureData::operator[](std::size_t index) const{assert(index < (texture_.width() * texture_.height()));return data_[index];}/***************************************************************************************** CSprite.h****************************************************************************************/// Underhanded names - names containing a double underscore or starting with an// underscore followed by a capital letter are reserved in the C++ standard for// standard library and compiler writers only.  You are neither.  Don't use// underhanded names.#if !defined(PROJECT_PREFIX_SPRITE)#define PROJECT_PREFIX_SPRITE#include <vector>#include "Texture.h"class Sprite{public:// The empty constuctor leaves a sprite in an unusable state.  Use RAII -// Resource Acquisition Is Initializatior, or, in other words, the constructor// acquires all resources.// The constructor which takes a HTEXTURE is dangerous with the new design// because it is not clear who owns the HTEXTURE.  Instead we will modify// it to use the Texture class, since the Texture class always owns its// resource// constructors//Sprite();Sprite(Texture const & tex, float x, float y, float w, float h);// If you need one of: destructor, copy-constructor and/or copy-assignment// operator, you usually need all three.  In this case I've removed the// destructor because I will be adjusting the class design.  For the record,// if I hadn't have adjusted the design to remove dynamically allocated// resources I would have added the following function prototypes://    Sprite(Sprite const & csprite);//    Sprite & operator=(Sprite const & csprite);// destructor - removed//~Sprite();// You will never want to test for a collision between a sprite and nothing// (i.e. passing NULL to this member function).  Therefore using a pointer// adds an additional source of error - NULL could be passed and therefore must// be checked for.  I have adjusted the parameter to be passed by reference// since a reference cannot be NULL.  I have also added two const qualifiers to// make this function const correct// Check collision.bool spriteCollide(Sprite const & sprite) const;// In C++ std::string is preferable to const char * because it allows either to// be passed without requiring the caller to do anything special.  That said,// this should probably be moved to the constructor since a sprite without a// texture makes little sense.  However, since we already have a constructor// which takes a Texture object and the Texture object can be constructed from// an HGE pointer and a filename the existing constructor already does all this// load texture. - removed//void loadTexture(HGE* hge, std::string const & fileName,//float x, float y, float w, float h);// For the same reasons given above for loadTexture this should probably be// moved to the destructor.  Fortunately the work can be done automatically,// which saves having to actually write the destructor// Cleanup textures - removed//void cleanup(HGE *hge);// Getters/Setters like these are often a code smell.  Make the class// encapsulate behaviour, not state.  I.e. provide move, draw, etc. member// functions.  I don't have enough information about your program to make// sensible adjustments, so I've just made them compilable, not safe// Basic inline functions that are used to return values.inline void setXY(float x, float y) { xPosition = x; yPosition = y; }inline float getX() const { return xPosition; }inline float getY() const { return yPosition; }inline float getWidth() const { return (float)width; }inline float getHeight() const { return (float)height; }inline hgeSprite const * getSprite() const { return &currentSprite; }inline unsigned char const * getAlpha() const { assert(!alpha.empty());return &alpha[0]; }private:intheight;intwidth;floatxPosition;floatyPosition;// I've replaced the HTEXTURE with my Texture class, which handles deallocation// automatically// Holds the sprite texture - removedTexture spriteTexture;// The redesign means we can hold currentSprite by value rather than by pointer// Holds the sprite objecthgeSprite currentSprite;// This would be better as a <tt>std::vector</tt>.// Used to hold the alpha values of the texturestd::vector< unsigned char > alpha;};#endif/***************************************************************************************** CSprite.cpp****************************************************************************************/#include "MainIncludes.h"#include "CSprite.h"// We got rid of this//CSprite::CSprite()//: spriteTexture(NULL)//{//}// Prefer to use the initialization list to initialize objects.// currentSprite is now an object, not a pointer// Assign to all members in the initialization list// We've merged this with the old loadTexture member function// Overloaded constructor.Sprite::Sprite(Texture const & tex, float x, float y, float w, float h):height(h),width(w),xPosition(x),yPosition(y),spriteTexture(tex),currentSprite(tex.handle(), x, y, w, h),alpha(spriteTexture.width() * spriteTexture.height()){//currentSprite = new hgeSprite(tex, x, y, w, h);//}// We removed this// Note that there is never a need to do an if (pointer) test before deleting// deleteing a null pointer is perfectly valid and does nothing.// Also alpha should have been deleted with delete[], not delete, since it was// allocated with new[], not new.  A moot point with the redesign though.//CSprite::~CSprite()//{// deletes the sprite.//if(currentSprite)//{//delete currentSprite;//}// Deletes the pointer alpha//if(alpha)//{//delete alpha;//}//}// We removed this too// Cleans up the texture.//void CSprite::cleanup(HGE *hge)//{//if(spriteTexture != NULL)//{//hge->Texture_Free(spriteTexture);//spriteTexture = NULL;//}//}// This we changed into a constructor// Loads a texture and creates the sprite.//void CSprite::loadTexture(HGE* hge, const char *filename,//  float x, float y, float w, float h)//{// load the texture.//spriteTexture = hge->Texture_Load(filename);//if(!spriteTexture)//{//char errorMsg[256];//sprintf(errorMsg,"%s",filename);//MessageBox(NULL, errorMsg, "Error", MB_OK | MB_ICONERROR | MB_SYSTEMMODAL);//hge->System_Shutdown();//hge->Release();//}// make the sprite//currentSprite = new hgeSprite(spriteTexture, x, y, w, h);//height = (int)h;//width = (int)w;// Create an array for alpha values.//alpha=new unsigned char[size_t(w*h)];// Use RAII wrappers whenever something needs to be acquired and later released// Lock the texture.TextureData point(spriteTexture);//int f = 0;// use unsigned types for unsigned quantities// Get the alpha values for the texture.for (std::size_t i = 0; i < alpha.size(); ++i){// This was an error - you need to dereference or index into point,// not just cast it//alpha[f] = (unsigned char)point;alpha = point[(i * 4) + 3];}// No need to explicitly unlock since we're using RAII//hge->Texture_Unlock(spriteTexture);// This was redundant and potentially dangerous.  The variable is about to// cease to exist - it shouldn't matter what value it has//point = NULL;}// Check for per pixel sprite collision, between// this sprite and the sprite sent via paramater.bool Sprite::spriteCollide(Sprite const & sprite) const{float left1=0.0f, left2=0.0f, over_left=0.0f;float right1=0.0f, right2=0.0f, over_right=0.0f;float top1=0.0f, top2=0.0f, over_top=0.0f;float bottom1=0.0f, bottom2=0.0f, over_bottom=0.0f;float over_width=0.0f, over_height=0.0f;int i=0, j=0;unsigned char const *pixel1, *pixel2;// little point in calling functions when we have access// to the variables directlyleft1 = xPosition;left2 = sprite.getX();right1 = xPosition + width;right2 = sprite.getX() + sprite.getWidth();top1 = yPosition;top2 = sprite.getY();bottom1 = yPosition + height;bottom2 = sprite.getY() + sprite.getHeight();// Trivial rejections:if (bottom1 < top2){return false;}if (top1 > bottom2){return false;}if (right1 < left2){return false;}if (left1 > right2){return false;}// Ok, compute the rectangle of overlap:if (bottom1 > bottom2) over_bottom = bottom2;else over_bottom = bottom1; if (top1 < top2) over_top = top2;else over_top = top1;if (right1 > right2) over_right = right2;else over_right = right1;if (left1 < left2) over_left = left2;else over_left = left1;over_width = over_right - over_left;over_height = over_bottom - over_top;// Now compute starting offsets into both objects' bitmaps:i = (int)((over_top - yPosition) * width) + over_left;// Made compilable, not necessarily correctpixel1 = &alpha;j = (int)((over_top - sprite.getY()) * sprite.getWidth()) + over_left;pixel2 = sprite.getAlpha() + (unsigned char)j;  // Now start scanning the whole rectangle of overlap,// checking the corresponding pixel of each object's// bitmap to see if they're both non-zero:for (i=0; i < over_height; i++) {for (j=0; j < over_width; j++) {if ((*pixel1 > 0) && (*pixel2 > 0)) return true;pixel1++;pixel2++;}pixel1 += unsigned char(width - over_width);pixel2 += unsigned char(sprite.getWidth() - over_width);}// Worst case!  We scanned through the whole darn rectangle of overlap // and couldn't find a single colliding pixel!return false;}After cleaning that up I didn't have much time to look through your collision detection function.  Hopefully this will get you closer to getting it working though.  If I'd had known more about your project and had more time would have organised things a little differently - abstracting the HGE pointer away better for one.Σnigma   ;  I was attempting to tell you how to debug the problem, and possibly come back with better information for us to work out your problem.Do you have access to a debugger that can step through your code?  If so, to debug the problem, you want to arrange a test case where you will get an incorrect "collision", and examine the state of your program at the moment where the collision occurred.Which two pixels are reported as colliding?  You can even report this using printf-debugging.Now, for an educated guess asto why your program is broken:unsigned char *point = (unsigned char*)hge->Texture_Lock(spriteTexture, true, (int)x, (int)y, (int)w, (int)h);int f = 0;// Get the alpha values for the texture.for(int i=0; i<w*h; i+=3){alpha[f] = (unsigned char)point;point++;f++;}hge->Texture_Unlock(spriteTexture);point = NULL;The variable alpha has no resemblance to a copy of the alpha channel of your texture.This code is wrong in many many ways.  Take your debugger and step through this code, and I believe it won't make any sense.Good day.;Quote:Original post by NotAYakkI was attempting to tell you how to debug the problem, and possibly come back with better information for us to work out your problem.Do you have access to a debugger that can step through your code?  If so, to debug the problem, you want to arrange a test case where you will get an incorrect "collision", and examine the state of your program at the moment where the collision occurred.Which two pixels are reported as colliding?  You can even report this using printf-debugging.Now, for an educated guess asto why your program is broken:unsigned char *point = (unsigned char*)hge->Texture_Lock(spriteTexture, true, (int)x, (int)y, (int)w, (int)h);int f = 0;// Get the alpha values for the texture.for(int i=0; i<w*h; i+=3){alpha[f] = (unsigned char)point;point++;f++;}hge->Texture_Unlock(spriteTexture);point = NULL;The variable alpha has no resemblance to a copy of the alpha channel of your texture.This code is wrong in many many ways.  Take your debugger and step through this code, and I believe it won't make any sense.Good day.Your right there is a lot wrong with it, since I have posted this thread. I have actually changed it around a bit. Now instead of just iterating by one with the pointer which is an obvious mistake. I now iterate 3 times.I've also tried a few various other things. It still doesn't seem to work. [sad]I've been looking through Enigmas code as well, but seeing as I don't use boost as much as he apparently does. It is a bit obscure and kind of difficult to work with, I am going to try and perhaps transfer some of his ideas to my code though.The reason the design of this code is not too much of a big deal is because its just a simple game of pong, I am merely experimenting with this form of collision. For learning purposes obviously.The new code looks something like this:/***************************************************************************************** CSprite.h****************************************************************************************/#ifndef __CSPRITE_H__#define __CSPRITE_H__class CSprite{public:// constructorsCSprite();CSprite(HTEXTURE tex, float x, float y, float w, float h);// destructor~CSprite();// Check collision.bool spriteCollide(CSprite *sprite);// load texture.void loadTexture(HGE* hge, const char* fileName,float x, float y, float w, float h);// Cleanup texturesvoid cleanup(HGE *hge);// Basic inline functions that are used to return values.inline void setXY(float x, float y) { xPosition = x; yPosition = y; }inline float getX() { return xPosition; }inline float getY() { return yPosition; }inline float getWidth() { return (float)width; }inline float getHeight() { return (float)height; }inline hgeSprite *getSprite() { return currentSprite; }inline unsigned char* getAlpha() { return alpha; }private:intheight;intwidth;floatxPosition;floatyPosition;// Holds the sprite textureHTEXTUREspriteTexture;// Holds the sprite objecthgeSprite*currentSprite;// Used to hold the alpha values of the textureunsigned char*alpha;};#endif/***************************************************************************************** CSprite.cpp****************************************************************************************/#include "MainIncludes.h"#include "CSprite.h"CSprite::CSprite(): spriteTexture(NULL){}// Overloaded constructor.CSprite::CSprite(HTEXTURE tex, float x, float y, float w, float h){currentSprite = new hgeSprite(tex, x, y, w, h);}CSprite::~CSprite(){// deletes the sprite.if(currentSprite){delete currentSprite;}// Deletes the pointer alphaif(alpha){delete alpha;}}// Cleans up the texture.void CSprite::cleanup(HGE *hge){if(spriteTexture != NULL){hge->Texture_Free(spriteTexture);spriteTexture = NULL;}}// Loads a texture and creates the sprite.void CSprite::loadTexture(HGE* hge, const char *filename,  float x, float y, float w, float h){// load the texture.spriteTexture = hge->Texture_Load(filename);if(!spriteTexture){char errorMsg[256];sprintf(errorMsg,"%s",filename);MessageBox(NULL, errorMsg, "Error", MB_OK | MB_ICONERROR | MB_SYSTEMMODAL);hge->System_Shutdown();hge->Release();}// make the spritecurrentSprite = new hgeSprite(spriteTexture, x, y, w, h);height = (int)h;width = (int)w;// Create an array for alpha values.alpha=new unsigned char[size_t(w*h)];// Lock the texture.DWORD *point = hge->Texture_Lock(spriteTexture, true, (int)x, (int)y, (int)w, (int)h);int f = 0;for(int i=0; i<w*h; i+=3){point++;point++;point++;alpha[f] = (unsigned char)point;f++;}hge->Texture_Unlock(spriteTexture);point = NULL;}// Check for per pixel sprite collision, between// this sprite and the sprite sent via paramater.bool CSprite::spriteCollide(CSprite *sprite){float left1=0.0f, left2=0.0f, over_left=0.0f;float right1=0.0f, right2=0.0f, over_right=0.0f;float top1=0.0f, top2=0.0f, over_top=0.0f;float bottom1=0.0f, bottom2=0.0f, over_bottom=0.0f;float over_width=0.0f, over_height=0.0f;int i=0, j=0;unsigned char *pixel1=NULL, *pixel2=NULL;left1 = this->getX();left2 = sprite->getX();right1 = this->getX() + this->getWidth();right2 = sprite->getX() + sprite->getWidth();top1 = this->getY();top2 = sprite->getY();bottom1 = this->getY() + this->getHeight();bottom2 = sprite->getY() + sprite->getHeight();// Trivial rejections:if (bottom1 < top2){return false;}if (top1 > bottom2){return false;}if (right1 < left2){return false;}if (left1 > right2){return false;}// Ok, compute the rectangle of overlap:if (bottom1 > bottom2) over_bottom = bottom2;else over_bottom = bottom1; if (top1 < top2) over_top = top2;else over_top = top1;if (right1 > right2) over_right = right2;else over_right = right1;if (left1 < left2) over_left = left2;else over_left = left1;over_width = over_right - over_left;over_height = over_bottom - over_top;// Now compute starting offsets into both objects' bitmaps:i = (int)((over_top - this->getY()) * this->getWidth()) + over_left;unsigned char* alpha1= alpha;for(int v=i; v>0; v--){alpha1++;}pixel1 = alpha1;j = (int)((over_top - sprite->getY()) * sprite->getWidth()) + over_left;unsigned char *alpha2 = sprite->getAlpha();for(int d=j; d>0; d--){alpha2++;}pixel2 = alpha2;  // Now start scanning the whole rectangle of overlap,// checking the corresponding pixel of each object's// bitmap to see if they're both non-zero:for (i=0; i < over_height; i++) {for (j=0; j < over_width; j++) {if ((*pixel1 > 10) && (*pixel2 > 10)) return true;pixel1++;pixel2++;}pixel1 += unsigned char(this->getWidth() - over_width);pixel2 += unsigned char(sprite->getWidth() - over_width);}// Worst case!  We scanned through the whole darn rectangle of overlap // and couldn't find a single colliding pixel!return false;}