Author Topic: Bounding Spheres: Collision Detection  (Read 1880 times)

Michael Lobko-Lobanovsky

  • Administrator
  • *****
  • Posts: 903
Bounding Spheres: Collision Detection
« on: March 09, 2016, 05:54:35 am »
Game engines use bounding spheres to detect physical collisions among dynamic objects in the scene.

Bounding spheres are the simplest primitive shapes suitable for only very rough estimation if two or more moving objects can potentially collide. The bounding sphere carries information about only one of the object's extreme points, the one that's the most distant from the object's virtual "center of mass". However, the object's "center of mass" may generally not coincide with its "center of rotation" or "center of symmetry". In fact, the object's outline may generally not correspond to a sphere at all, in which case a more elaborate primitive shape should preferably be chosen for more exact, yet simple and fast enough, collision detection. The other shapes suitable for use in collision detection systems are axis-aligned bounding boxes (a.k.a. AABB's) that store information about the object's minima and maxima on all the three spatial axes, disk-capped cylinders, and hemisphere-capped cylinders (a.k.a. capsules).

General strategy of fast and precise collision detection presupposes the following steps:

1. First check if two or more objects of interest can potentially collide using their bounding spheres, which in this case would touch or intersect one another. This test is the fastest to perform because it checks only one, the most extreme, point of an object.

2. If test #1 above fails, drop the whole subject: the objects cannot collide in principle.

3. If test #1 above passes, then proceed to check if the objects' AABBs touch or intersect one another as well. This implies checking all the six sides of every bounding box against all the sides of other bounding boxes and is therefore much more computationally intensive than the bounding sphere test, yet not so much intensive as it would've been if we were to check all the tris or verts of the real colliding objects.

4. If the bounding boxes (or cylinders, or capsules) don't intersect, test no more: the objects aren't colliding.

5. If they do, either signal and process the objects' collision or proceed to test the objects' vertices and/or polygons one by one for the most exact collision detection possible. This is however rarely done these days because there are usually too many modern scene objects to poll and too many verts and tris in each of them to test.

Since neither ObjReader nor Objector features a collision detection system (they aren't true game rendering engines, after all), I won't discuss it in any further detail beyond what's been already said just to illustrate yet one more potential use of bounding spheres that are calculated and stored in the mesh structures of ObjReader/Objector model loaders.

(to be continued)
Mike
(3.6GHz Intel Core i5 Quad w/ 16GB RAM, nVidia GTX 1060Ti w/ 6GB VRAM, Windows 7 Ultimate Sp1)