How does 3D collision / object detection work?

Question

I always wondered this question. In a game like GTA , where there are 10,000,000 objects, how does the game find out as soon as you get into the health pack?

There can be an event listener for each object? Is iteration not good too? I'm just wondering how this is actually done.

Answer 1

There is not a single answer, but large worlds are often divided in space, using something along the lines of quadtree or kd-tree , which gives the search time to find the nearest neighbors below linear time (fractional power or in the worst case O (N ^ (2 / 3)) for a 3D game). These methods are often called BSPs for binary partitioning.

As for collision detection, each object also has a limited volume grid associated with it (many polygons forming a convex hull). These highly simplified grids (sometimes only a cube) are not drawn, but are used to detect collisions. The most primitive method is to create a plane perpendicular to the line connecting the midpoints of each object with a plane crossing the line at the midpoint of the line. If the object bounding volume has points on both sides of this plane, this is a collision (you only need to check one of the two bounding volumes on the plane). Another method is the advanced GJK algorithm. If you want the tutorial to go through, check out OpenGL NeHe Productions Lesson # 30 .

Incidentally, bounding volumes can also be used for other optimizations, such as so-called occlusal queries. This is the process of determining which objects are behind other objects (occluders), and therefore they do not need to be processed / visualized. Bounding volumes can also be used to reject a truncated cone, which is the process of determining which objects are outside the prospective scope of the view (too close, too far, or outside the field of view) and therefore need not be visualized.

---

As Kilotan noted, using a bounding volume can generate false positives when occlusion is detected and simply does not work at all for some types of objects, such as toroids (for example, looking at a hole in a donut). The presence of objects like these is correctly closed, this is a whole different thread when choosing a portal.

Answer 2

Quadtrees and Octrees , another quadrant , are popular ways of using space markup to achieve this. A later example shows a 97% reduction in cross-collision cross-lookup processing.

Answer 3

A common technique in the engines of game physics is the sweeping and trimming method. This is explained in David Baraf SIGGRAPH's notes (see Chapter "Restricted Traffic"). Havok definitely uses this, I think this is an option in Bullet, but I'm not sure about PhysX.

The idea is that you can look at the AABB overlaps (frames bounding the axis) on each axis; if the AABB projection of two objects overlaps on all three axes, then the AABB must overlap. You can check each axis relatively quickly by sorting the start and end points of the AABB; There is a lot of temporal consistency between frames, since usually most objects do not move very fast, so the sorting does not change much.

Once sweep-and-prune finds a match between the AABB, you can perform a more detailed scan of objects, for example. sphere against the box. If a detailed check detects a collision, you can resolve the collision using force and / or trigger a game event or play a sound effect.

Answer 4

Right. Usually for each object there is no event listener. Often there is a non-skeleton tree structure in your memory that mimics your game map. Imagine a subway / underground map. This strucutre memory is a collection of things in the game. You are a player, monsters and items that you can get, or items that can erupt and harm you. As the player moves around the game, the player object pointer moves in the game / map memory structure.

see How should I know that my game entities are aware of the things around them?

Answer 5

You can use many optimizations. Firstly, any object (for example, with index i, for example) is limited by a cube with the central coordinates CXi , CYi and size Si Secondly, collision detection works with estimates:

a) Find all pairs of cubes i, j with the condition: Abs(CXi-CXj)<(Si+Sj) AND Abs(CYi-CYj)<(Si+Sj)

b) Now we only work with pairs received in a). We calculate the distances between them more accurately, something like Sqrt(Sqr(CXi-CXj)+Sqr(CYi-CYj)) , objects that are currently represented as sets of several numbers of simple shapes - cubes, spheres, cones, - and we use geometry formulas to verify these intersections of shapes.

c) Objects from b) with detected intersections are treated as collisions with physics calculations, etc.

Answer 6

I would like to recommend Christer Erickson's solid book on real-time collision detection. It presents the basics of collision detection, as well as links to modern research.

Real-time Collision Detection (Morgan Kaufmann Series in Interactive 3D Technology)