Source: link
Pixel collision
If you need to perform a perfect detection, you can do pixel-level detection. It is important to keep in mind, as you will see, that this type of procedure, although effective, is extremely costly in terms of processing. Based on the pixels in which the overlap is detected, you can tell which side of a rectangle the collision occurred.
The main point to begin defining a pixel collision detection function (or method) is to understand that bitmaps images are stored as repeating whole numbers along the bitmap. Each color is associated with a number. In general, the transparent color is associated with the number 0 (zero).
To optimize the process, we first define whether there is a collision between the object's surrounding polygons (assuming rectangles). In case there is no collision between the surrounding polygons, it is impossible to collide between objects. On the other hand, if there is a collision between the surrounding polygons then there is the possibility that there was a collision between objects.
Notice that in the first case our work is finished. In the second case, we have to define what was the collision area (which in the case of surrounding rectangles gives us a new rectangle). We will call this overlapping rectangle rectangle. It is the area where the two rectangles of objects overlapped.
Now what we have to do is to traverse this area of the overlapping rectangle in the two images (pixel by pixel) and determine if in both images there is a same pixel of the overlapping rectangle where the two images have a non-transparent color. If both object images have non-transparent pixels in the same position within the overlapping rectangle then there was actually collision.
The pseudo-code below shows this procedure:
/*retorna 0 se não houve colisão, ou 1 se houve colisão*/
int Função ColisaoPorPixel(objeto1, objeto2)
{
//Define os pontos corners dos objetos
left1 = objeto1.x;
left2 = objeto2.x;
right1 = objeto1.x + object1.largura;
right2 = objeto2.x + object2.largura;
top1 = objeto1.y;
top2 = objeto2.y;
bottom1 = objeto1.y + object1.altura;
bottom2 = objeto2.y + object2.altura;
/*Teste de rejeição para colisão de polígonos circundantes*/
if (bottom1 < top2) returna(0);
if (top1 > bottom2) returna(0);
if (right1 < left2) returna(0);
if (left1 > right2) returna(0);
/*Se chegamos aqui é porque pode haver colisão, descubra o retângulo de sobreposição*/
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;
// Agora situa as áreas de comparação nos dois objetos
i = ((over_top – objeto1.y) * objeto1.largura) + over_left;
pixel1 = objeto1.frames[objeto1.curr_frame] + i;
j = ((over_top - objeto2.y) * objeto2.largura) + over_left;
pixel2 = objeto2.frames[objeto2.curr_frame] + j;
/* Agora começa a varrer todos o retângulo de sobreposição, testando se o correspondente pixel de
cada bitmap de cada objeto,para ver se ambos são
diferentes de zero
*/
for (i=0; i < over_height; i++)
{
for (j=0; j < over_width; j++)
{
if (objeto1[pixel1].cor > 0) && (objeto2[pixel2].cor > 0)
{
//houve colisão
return(1);
}
pixel1++;
pixel2++;
}
pixel1 += (objeto1.largura - over_width);
pixel2 += (objeto2.largura - over_width);
}
/* Pior caso do algoritmo! Varremos o retângulo de sobreposição e não encontramos nenhuma colisão*/
return(0);
};
As stated above, it is important to understand that this algorithm, while completely effective, is very costly. For many objects moving on the screen at the same time, for which you have to test collision, this procedure can simply make your game get almost so slow.
Considering the shape of the objects, their sizes and how realistic the game needs to be. We can think of ways to combine the collision detection techniques learned to form a treatment that although it is more complex, since dealing with several cases, can also be quite efficient: the hierarchical collision detection.
