• 15
• 15
• 11
• 9
• 10

# Convex Hull Collision

This topic is 2822 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

How do games like Quake and Doom check for collision against the world? From my knowledge, I know that they store all the planes, as sets of convex hulls for the level, and check for collision against those.

And the same with the level objects, which are again, stored as a convex hull, and thus a set of planes.

But lets say the convex hull is something simple, like a cube, so viewed from the top looks like this,

       |-----------|       |           |       |           |       |           |       |           |       |           |       |-----------|

But in terms of whats stored, ie the planes, its this. Where the planes obviously go to infinity

       |           |       |           |       |           |       |           |       |           |                 P-------|-----------|------------------------       |           |       |           |       |           |       |           |       |           |-------|-----------|------------------------       |           |       |           |       |           |       |           |       |           |       |           |

And so if I was at point P, id be colliding with the cubes planes. But I dont want that to occur. How do they solve this?

Is it as simple as they only consider it a collision if the point is behind ALL the planes?

##### Share on other sites
Your last sentence is correct. Simply put, that is how it works. I'll expand on that a bit.

I'm not a Quake or Doom expert, but they use a BSP (binary space partition) tree to break up the world into regions. A BSP tree recursively divides the world into two halfs, or two halfspaces, via planes. So, if you start with a world that is infinite in all directions, the first planar division will give a world that is infinite on each side but terminating at the plane. Lets say that one side of the plane is "inside" and the other semi-infinite side is "outside." Now, if you create 6 planes, e.g., those bounding a cube, and orient each plane's "inside" and "outside" half appropriately, then it will turn out that the cube portion is "inside" all of the planes and everything outside the cube is "outside" all of the planes. And it is that property, the union of the "inside" vs. "outside" parts of the planes, that BSP collision detection is based on. Basically, as you summarized it in the last sentence you wrote.

Lets look at your illustration, which is 2D. Instead of 6 planes you only have 4. Your point P, it can only be inside the square if it is "inside" all of the 4 planes. But where you have drawn it, it is "inside" 2 planes and "outside" the other 2. Since it isn't inside all 4, it fails the test...it is outside the cube.

That logic to determine inside vs. outside containment works for more complex BSP region shapes as well, e.g, some volume created with more planes than just 6. Without adding complex crossing or winding number logic, it is limited, though, to convex volumes. So any concave volumes would have to be subdivided into convex sub-portions. The process to build the BSP tree takes care of this, so the technique used in Quake and Doom does ensure the BSP tree is made of convex regions.

As for how Quake and Doom deal with level objects, I'm not sure how exactly they do it. It is possible they use convex hulls, but they might use different primitives such as a sphere or collection of spheres (e.g, a bounding sphere gives an approximation to any shape and for collision purposes can be used as a proxy for any visual object in the game). It is quite common, extremely, extremely common and pretty much standard practice, to use primitives in this way. Spheres, cylinders, capsules, boxes. One at a time or in collections or hierarchies. These other primitives might be cheaper to test for containment against the BSP regions than testing a full mesh, triangle-by-triangle. It is pretty trivial to test a single point for containment in a BSP region, but not quite as trivial to test a shape that has volume. If you have a triangle mesh, you could test every vertex in the mesh, but that could be expensive. Testing a sphere against the BSP tree is pretty cheap.

There is an article here on gamedev about collision detection using BSP trees, but it doesn't have any illustrations. I found another that looks like it may be better. Please note that I cannot vouch for it. I have not read it to look for overall quality. But it looks like it may be useful:

Physics in BSP-Trees: Collision Detection