   collision
  I created this function to detect collision (pixel by pixel)bool Sprite::Collision(const Sprite &spr1, const Sprite &spr2){// storage for the pointsPointStorage spr1Points, spr2Points;spr1Points.reserve(spr1.w() * spr1.h() / 4);spr2Points.reserve(spr2.w() * spr2.h() / 4);// add pointsconst unsigned SPR1_SIZE = AddPixelPoints(spr1, spr1Points);const unsigned SPR2_SIZE = AddPixelPoints(spr2, spr2Points);// if the bounding boxes collideif( Rect::Collision(spr1.rect(), spr2.rect()) ){PointStorage *small = SPR1_SIZE < SPR2_SIZE ? &spr1Points : &spr2Points,*big = SPR1_SIZE < SPR2_SIZE ? &spr2Points : &spr1Points;// use the small vector to iterate for increased performancefor(PointStorage::iterator iter = small->begin(); iter < small->end(); ++iter)if( std::find(big->begin(), big->end(), *iter) != big->end() )return true;}return false;}unsigned Sprite::AddPixelPoints(const Sprite &spr, PointStorage &storage){// this function inserts the points of the pixels of the sprite// to storage. If a colorkey is set, it skips transparent pixels// is a colorkey used?bool usesColorKey = spr.GetAlphaKey().ColorKeyOn();Uint32 key;// if colorkey is used, retrieve itif( usesColorKey ) key = spr.GetKey();for(unsigned i = 0; i < spr.w(); ++i){for(unsigned j = 0; j < spr.h(); ++j)// if a colorkey is usedif( usesColorKey ){// skip the colorkey pixelsif( spr.GetPixel(i,j) != key )storage.push_back( Point(spr.x() + i, spr.y() + j) );}else{// if a colorkey isn't used, add all pixelsstorage.push_back( Point(spr.x() + i, spr.y() + j) );}}return storage.size();}I first check if the collision boxes collide if( Rect::Collision(spr1.rect(), spr2.rect()) ) so that I won't do unnecessary calculations.The problems start when the above line returns true; there is a huge performace drop. I used the small and big pointers to use the small vector to iterate to make things a bit faster but it's still very slow! Any advice to fix that?(The vectors are created every time the function is called, but I didn't see any performance regarding that. It's the damn loop that slows it down.)   
  I've never implemented a per-pixel collision detection system myself, but I think you're probably taking the wrong approach here. The algorithm you're using now is probably going to be on the slow side no matter what (due to the memory allocations, copying of data, and/or nested loops).First of all, are you sure you need pixel-perfect collision detection? Geometric algorithms are typically faster, and usually return more useful results.If you do want to stick with the pixel-perfect approach, I would do some Googling, as I'm pretty sure there are some decent articles on the topic floating around on the internet.Since I havent done it myself I'm probably not the best person to offer advice, but I'll go ahead and offer a couple of ideas.The first thing to keep in mind is that you need only be concerned with the area of overlap between the two bounding rectangles. In many cases (such as if one of the objects is small, or if the objects are slow-moving) the area of overlap will be fairly small.Once you have the rectangular area of overlap, iterate over all of the 'pixel cells' in the rectangle. For each cell, check to see if the corresponding pixel from each sprite is non-transparent (i.e. a color other than the color key). If so, you have a hit.Implemented correctly, this should eliminate all copying and dynamic memory allocations, and reduce the number of loop iterations to the number of 'pixel cells' in the area of overlap.Again, there may be better approaches (which you might find by Googling), but this is what first comes to mind.   ;  I assume you don't have sprite rotations or scaling there and the sprite positions are always at integer coordinates so that if the two sprites overlap, then their pixel coordinates always match exactly?Indeed your code is quite inefficient... Doing a broadphase rect-rect test is great, but after that not so much.. You compute a vector/list/set of the pixels of both sprites that are occupied - this is not really the best data structure to use. If you really insist on doing it like this, at least the AddPixelPoints should be moved to a precomputation phase instead of computing it each time the Collision routine is called.If your sprites aren't that big, just precompute a boolean 2D matrix of per-pixel occupancy data and use that matrix to do the check (or in a simple case of yours like that, just read the original sprite color array for this data). That already is far more efficient than performing this copy at each iteration.Then there are lots of ways to optimize the check. First off, you can compute which parts of the sprite bounding rectangles overlap, and only check that are per-pixel. The outside sections can be ignored.Another (instruction-set level) optimization is to pack the bit matrix into a an array of 32-bit (or 64-bit if in 64 bit mode) values, and use the binary & operation to check 32 or 64 pixels at once.Yet another optimization is to precompute mip pyramids of this per-pixel data. This can be used as an early in/out check for the collisions.If the pixels don't align between the sprites, then I suggest going the route of computing the intersecting polygon of the two rotated/scaled overlapping bounding rectangles, then backprojecting that onto the original sprite local coordinate systems, rasterizing those and finally checking for per-pixel collision matches.Hope that helps.   ;Quote:Original post by clbAnother (instruction-set level) optimization is to pack the bit matrix into a an array of 32-bit (or 64-bit if in 64 bit mode) values, and use the binary & operation to check 32 or 64 pixels at once.How can I do that?   ;Quote:Original post by sheep19Quote:Original post by clbAnother (instruction-set level) optimization is to pack the bit matrix into a an array of 32-bit (or 64-bit if in 64 bit mode) values, and use the binary & operation to check 32 or 64 pixels at once.How can I do that?I'm not sure how the above method would work, given that the pixel layouts aren't guaranteed to be aligned in any particular way, but maybe clb can offer some clarification on that.In any case, to begin with at least, reducing the test to a single iteration over the cells of the overlap area will be the most important optimization to make. I'd try to get that implemented and working correctly, and then worry about further optimization only if it proves to be necessary.   ;Quote:Original post by sheep19Quote:Original post by clbAnother (instruction-set level) optimization is to pack the bit matrix into a an array of 32-bit (or 64-bit if in 64 bit mode) values, and use the binary & operation to check 32 or 64 pixels at once.How can I do that?Exactly as mentioned. 1) For each pixel, compute whether it is passable or solid, and give it an 1/0 boolean value.2) Pack these booleans tightly into an u32 (unsigned long on most compilers in 32-bit mode) array. That means that in the array, one element contains the values for 32 horizontally adjacent pixels (pad the lines with zeroes at the end so that the widths are divisible by 32 for easier checking).3) In collision check time, compute the bounding rectangle of which parts of the sprites may potentially overlap.4) For this potential collision area, determine which indices of the bit mask array correspond to those pixels.5) There's a slight catch: The sprite distances in x -dimension are most probably not divisible by 32, so when checking, you need to adjust for that by performing shift operations in the array elements to match up the individual corresponding bits.6) Loop through these elements in the array, shifting the bits inside each element to match and perform a binary AND (& -operator) on these elements. You'll end up checking 32 pixels in one cycle.The math is not difficult, but probably needs a little pen&paper to figure out where to look up the correct pixels in the mask array, and what is the proper shift amount in each case. I'll note again that this approach works only if the sprites always align per-pixel (no scaling, rotation, or subpixel translation).If you need pixel perfect collision detection in any of these cases, you'll need to be transforming individual pixels from one sprite space to another and check where they overlap.   ;Quote:Original post by jykQuote:Original post by sheep19Quote:Original post by clbAnother (instruction-set level) optimization is to pack the bit matrix into a an array of 32-bit (or 64-bit if in 64 bit mode) values, and use the binary & operation to check 32 or 64 pixels at once.How can I do that?I'm not sure how the above method would work, given that the pixel layouts aren't guaranteed to be aligned in any particular way, but maybe clb can offer some clarification on that.Yeah exactly.. To work over this you do two things:1) Pad the mask widths to multiples of 32 (or 64, or whatever the word size is), so that you can quickly compute the index of the array that starts each scanline.2) When doing the check, perform shift ops depending on sprite x coordinate to align the data. I'll draw a crappy image using a word size of 8 to show the idea:sprite1 x=19sprite2 x=24difference=5 => shift amount=5aligned mask arrays (numbers correspond to elem indices).mask1: 000000001111111122222222mask2: 000000001111111122222222break-up on word size, 8 bits:mask1: 00000 00011111 11122222 222mask2:  00000000 11111111 22222222further break-up for binary AND ops:mask1: 00000 000 11111 111 22222 222mask2:  000 00000 111 11111 222 22222label: ab   cd   ef   gBinary ops performed:a: no check needed.b: mask1[0] & (mask2[0] >> 5)c: mask1[1] & (mask2[0] << 3)d: mask1[1] & (mask2[1] >> 5)e: mask1[2] & (mask2[1] << 3)f: mask1[2] & (mask2[2] >> 5)g: no check needed.If my ascii is any readable, I think you can see the pattern forming. If any of those AND operations return nonzero, there was a collision at one of the pixels that were checked. Note that the shifts need to be "unsigned", so that no sign-extending occurs when right-shifting (work on unsigned data types to have this on X86), and the shift op can't be cylindrical (which it isn't on X86 platform).This kind of method for collision detection used to be the standard trick in old DOS days.. I remember spending lots of time reverse engineering the Star Control 2 .SHP data files to figure out how they stored the bit masks for various ships. To support rotations, they went as far as to precompute these bit masks for each of the 16 rotations of the ship, as well as each of the three possible scales on which they were drawn. A nice hack was to clear these collision masks all to zero to make your ship unhittable. Oh those were the days.. *sob*   ;  Though you can make it really nice with that trick explained in above posts, just know that you don't need it. If you think it's hard or just don't want to, checking one pixel at a time will still be very fast.What makes your code slow now is possibly partly because you use dynamic arrays re-allocated every time, but I think even that is only a very small fraction of the time taken. My guess at what really breaks it is your actual check loop, where you have a std::find inside the for-loop. Say there are 100 pixels in 'big', and 100 in 'small', then for 100 iterations you will do a search through 100 pixels for a match. This is 10,000 iterations for a naive search, though if you have a sorting container it might be optimized, but still probably slow.You need to get rid of that double-loop algorithm. Something like the following:// Loop over every pixel in sprite 1for(y1=0; y1 < height1; y1++) { for(x1=0; x1 < width1; x1++) {    // Get world-position of the x1,y1 pixel in sprite 1  int x = x1 + sprite1Position.x;  int y = y1 + sprite1Position.y;    // Get what pixel this corresponds to in sprite 2  int x2 = x - sprite2Position.x;  int y2 = y - sprite2Position.y;    // Check if it is inside sprite 2  if(x2 >= 0 && y2 >= 0 && x2 < width2 && y2 < height2) { // Check so that it's a solid pixel in both sprites, and not a transparent one   if(sprite1.pixels(x1, y1) != key && sprite2.pixels(x2, y2) != key) {    Collision();   }  } }};  I'm not good at bits so I'll do something simpler:That's what I do now:#include "Min_Sprite.h"using namespace Min;// return true if the sprites collidebool Sprite::Collision(const Sprite &spr1, const Sprite &spr2){// storage for the pointsstorageType storage;spr1.w() * spr1.h() > spr2.w() * spr2.h() ? AddPixelPoints(spr1, storage) : AddPixelPoints(spr2, storage);// if the bounding boxes collideif( Rect::Collision(spr1.rect(), spr2.rect()) ){for(unsigned i = 0; i < unsigned(spr1.w() * spr1.h()); ++i){unsigned row1, row2, column1, column2;GetPixelPosition(spr1, i, row1, column1);GetPixelPosition(spr2, i, row2, column2);if(PointInRect(Point(spr2.x() + row2, spr2.y() + column2), spr2.rect()) )if(spr1.GetPixel(row1, column1) != spr1.GetKey()&& spr2.GetPixel(row2, column2) != spr2.GetKey() )return true;}}return false;}unsigned Sprite::AddPixelPoints(const Sprite &spr, storageType &storage){// this function inserts the points of the pixels of the sprite// to storage. If a colorkey is set, it skips transparent pixels// is a colorkey used?bool usesColorKey = spr.GetAlphaKey().ColorKeyOn();Uint32 key;// if colorkey is used, retrieve itif( usesColorKey ) key = spr.GetKey();// reserve spacestorage.reserve( spr.w() * spr.h() );for(unsigned i = 0; i < unsigned(spr.w() * spr.h()); ++i){unsigned row, column;GetPixelPosition(spr, i, row, column);if( usesColorKey ){// if this is a solid pixelif( spr.GetPixel(row, column) != key )storage.push_back(true);elsestorage.push_back(false);}elsestorage.push_back(true);}return storage.size();}void Sprite::GetPixelPosition(const Sprite &spr, const unsigned i, unsigned &row, unsigned &column){row = i / spr.w();column = i / spr.h();}It's faster than it was, but it's not accurate...(The image at the left because semi-transparent when there's a collision)(They collide!!)[Edited by - sheep19 on April 12, 2009 6:53:38 AM];  Why doesn't this work?bool Sprite::ComparePixels(const Point &pixel1, const Point &pixel2, const Sprite &spr1, const Sprite &spr2){return /*******/}error C2678: binary '==' : no operator found which takes a left-hand operand of type 'const Min::Point' (or there is no acceptable conversion)1>   c:\data. mina\c++\include\Min_Point.h(16): could be 'bool Min::Point::operator ==(const Min::Point &)'1>   while trying to match the argument list '(const Min::Point, const Min::Point)'Point does define the == operator.// Point : represents a 2D point#ifndef MIN_POINT_H#define MIN_POINT_H#include "SDL/SDL.h"namespace Min{struct Point{public:// constructorsPoint(Sint16 _x = 0, Sint16 _y = 0) : x(_x), y(_y) {}bool operator == (const Point &p) {return (x == p.x && y == p.y);}bool operator < (const Point &p) {return (x * y < p.x * p.y);}// value returned when 2 Points don't collidestatic const Sint16 NPOS = static_cast <Sint16> (-32768);Sint16 x, y;};}#endif