Source: http://www.sirmacstronger.eti.br/jogos2d/conceitos2.htm
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 can 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, it is possible to know on 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 integer numbers that repeat along the bit map. 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 was a collision between the surrounding polygons of the object (assuming rectangles). If there is no collision between the surrounding polygons, there is no collision between the 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 the objects.
Note that in the first case our work is finished. In the second case, we have to define what was the area of collision (which in the case of surrounding rectangles gives us a new rectangle). We will call this rectangle an overlap rectangle. It is the area where the two rectangles of the objects overlapped.
Now what we should do is to traverse this area of the overlapping rectangle in the two images (pixel by pixel) and determine whether in both images there is a single pixel of the overlapping rectangle where the two images have non-transparent color. If both images of objects present non-transparent pixels in the same position within the overlapping rectangle then there was in fact 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, although 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 as caught up as 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 more complex, as treating multiple cases, can also be quite efficient: the hierarchical collision detection.
Useful link: https://www.youtube.com/watch?v=yge4GBkQsvw
– Marcelo Bezerra bovino
I had already seen this video, but the case, was what I explained above, I need to distinguish the sides that are colliding :)
– Dannark