Introduction
For really small projects, brute-force collision detection approach looping through all the rigid bodies may work without any problems; however, when the number of the objects in the scene increases, the performance of the approach decreases quickly. That’s why it’s important to use space partitioning approaches to make the collision detection process faster.
Space partitioning approaches partition the scene and create a smaller set of objects in the scene for collision detection test. The main approaches are bounding volume hierarchies (BVH), k-d trees, BSP trees, and Quad/Octrees. However, each approach does not work perfectly in any scenarios. They work better in some certain situations and decision of the space partitioning should be made depending on the game or the application in general.
BVH create a hierarchy based on object bounding boxes and this might be costly for the scene that includes objects moving all around during the frames since it requires reconstruction of the hierarchy for each frame.
BSP trees are good for indoor games (such as Quake) and collision detection between the level geometry and the game level.
For large opens spaces having lots of objects moving around, quad/octrees and uniform grids are good options. Uniform grid especially easier to build and easier to handle especially for tile-based games or the games everything in the scene is always moving.
Uniform Grid Insertion
The grid insertion is easy. It only depends on objectPosition / cellSize, where the cell size is a constant value ideally same or larger than the objects that will be inserted to the grid.
However, this basic insertion approach does not handle the objects that cover more than one grid cell. For handling this situation:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// This code inserts a single rigid body into multiple grids if necessary int startRow = std::max(0, (int)(obj->getBBoxUp().y / mCellSize)); int startCol = std::max(0, (int)(obj->getBBoxUp().x / mCellSize)); int endRow = std::min((int)mGrids.size() - 1, (int)(obj->getBBoxDown().y / mCellSize)); int endCol = std::min((int)mGrids[0].size() - 1, (int)(obj->getBBoxDown().x / mCellSize)); // Insert into the grids for (int row = startRow; row <= endRow; row++) { for (int col = startCol; col <= endCol; col++) { mGrids[row][col].push_back(obj); } } |
Here, getBBoxUp() returns the position of the upper-left corner of the object’s bounding volume and getBBoxDown() returns the position of the lower-right corner of the object’s bounding volume.
Collision Test
After the grid cells are filled with the objects, now you can loop through the grid cells and check the collisions for only the objects in the same cell. Additionally, if there are only some special objects to check collision detection, you can skip all other grid cells and only consider very few of them based on the cells these special objects cover (check insertion section above).
The code below considers all the objects in the grids:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
// Keep id's of the collided objects } In this way, we can prevent multiple collision of // the same objects involving more than one grid cell for (int row = 0; row < mGrids.size(); row++) // For each row of the grid { for (int col = 0; col < mGrids[row].size(); col++) // For each column of the grid { if (mGrids[row][col].size() > 1) // If there is more than one object in the current cell of the grid { for (int rbI = 0; rbI < mGrids[row][col].size(); rbI++) // Check collision for the objects { for (int rbII = rbI + 1; rbII < mGrids[row][col].size(); rbII++) { if (mGrids[row][col].at(rbI)->checkCollision(mGrids[row][col].at(rbII))) { if (!IdHandler::checkIds(mGrids[row][col].at(rbI)->getId(), mGrids[row][col].at(rbII)->getId())) { // COLLISION IS HAPPENING mGrids[row][col].at(rbI)->setCollided(); mGrids[row][col].at(rbII)->setCollided(); mGrids[row][col].at(rbI)->collide(mGrids[row][col].at(rbII)->getBodyType()); mGrids[row][col].at(rbII)->collide(mGrids[row][col].at(rbI)->getBodyType()); } } } } } } } IdHandler::refresh(); |
Here, I assume that my objects are directly bounding volumes. But, for a real mesh, you need to run more detail collision detection algorithm in the final if statement before mark the objects collided.