How can I implement bounding volume subdivision for my sprite images?

Question

Lately, I have been researching different Collision methods, how to deal with multiple collisions and different types of bounding shapes, circles, rectangles, polygons and ellipsoids. Some common collision methods are the:

'Axis aligned bounding box'

if (rect1.x < rect2.x + rect2.width &&
   rect1.x + rect1.width > rect2.x &&
   rect1.y < rect2.y + rect2.height &&
   rect1.height + rect1.y > rect2.y) {
    // collision detected!
}

'Circle Collision'

double dx = (circle1.x + circle1.radius) - (circle2.x + circle2.radius);
double dy = (circle1.y + circle1.radius) - (circle2.y + circle2.radius);
double distance = Math.sqrt(dx * dx + dy * dy);

if (distance < circle1.radius + circle2.radius) {
    // collision detected!
}

---

The bounding box/shape dilema

For one my projects, I am using images, which are rectangle by nature. However, to simply check for intersections with the images' edges would result in unsatisfactory collision detection. As Gamasutra puts it:

" The experience of playing some of the early flight simulators illustrated how bad collision detection can ruin a game. Flying through a mountain peak and surviving isn’t very realistic. Even some recent games have exhibited collision problems. Many game players have been disappointed by the sight of their favorite heroes or heroines with parts of their bodies inside rigid walls. Even worse, many players have had the experience of being hit by a rocket or bullet that was “not even close” to them. "

From that resource I discovered an interesting method of making bounding boxes or circles which Gamasutra calls subdivision

I am having trouble thinking how to do this subdivision process for my images (as I am working with images) and how to properly implement either subdividing process within my collision reliant app.

For example take mario and a koopa shell. I wouldn't want their transparent space to trigger intersection

Answer 1

Kiro,

Imagine Mario and the Koopa shell surrounded by rectangles. Once you detect that the two rectangles are overlapping, you then need to perform per-pixel intersection testing. There are many ways to do this, all depending on the kind of engine you are using. Essentially you want to compare each pixel in one image against the pixels in the other image.

I found an explanation of one technique here, which seems to encode spans to accelerate it, using SDL2, here: http://lazyfoo.net/SDL_tutorials/lesson18/

And I found these stack overflow ones:

https://stackoverflow.com/questions/173199/can-someone-explain-per-pixel-collision-detection https://stackoverflow.com/questions/20596893/per-pixel-collision-detection

And some more:

http://www.austincc.edu/cchrist1/GAME1343/PerPixelCollision/PerPixelCollision.htm

Good luck!