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

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 distance = Math.sqrt(dx * dx + dy * dy);

// 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

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:

And some more:

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

Good luck!

• I though about this method (not knowing the name), but I felt like it would be too performance intensive. I am actually programming my own "game-engine" in Java instead of using a actual game engine like unity or cryengine, etc. It's also exclusive 2 dimensional Nov 23, 2014 at 23:00
• Thats how we did it years ago on slower machines. The key is to only do it if the bounding volumes first overlap Nov 23, 2014 at 23:37
• This seems feasible for my application, especially if I have a "combined intersection method". First, I'll use the bounding box collision to find the overlap and then perform the per pixel collision operation. That shouldn't be too intensive. Nov 24, 2014 at 2:20