Collision detection (algorithmic geometry)

from Wikipedia, the free encyclopedia

When collision detection or collision detection ( English Collision Detection ) is used in the computational geometry understood two detecting of touching or overlapping or more geometric (rigid or deformable) objects in two- or three-dimensional space. A collision detection is followed by the collision response or collision handling, whereby a reaction to the collision is initiated.

Collision detection methods are used, for example, to generate images for animated films, in physical simulations, in computer games, for path planning in robotics or in haptics . A distinction is made between methods for the exact and approximate solving of collision responses.

Collision detection in the rigid body simulation

In the rigid body dynamics ( English rigid body simulation ) can be used for detection of a collision, the following situations are handled differently different algorithms:

  • Collision of simple geometric bodies,
  • Collision of two convex polyhedra (e.g. using the V-clip algorithm),
  • Collision n convex polyhedra (e.g. by I-collide algorithm),
  • Collision of non-convex polyhedra (e.g. RAPID),
  • Complex geometric bodies collision.

In individual cases it is worthwhile to break down non-convex polyhedra into convex ones and thereby in turn to use the algorithms to find collisions between convex polyhedra. In scenarios with large quantities or very complex geometric figures , the collision detection must be divided into two phases:

  • In the "broad phase" ( English Broad Phase ) it is checked which objects can overlap at all. This is done with the aid of bounding volumes that enclose the geometric objects (e.g. hitboxes , OBBs, AABBs or k-DOPs). It is important that a bounding volume has a simple geometric structure (e.g. spheres, cuboids) and is as close as possible to the complex geometric figure to be enveloped. In addition, spatial, hierarchical data structures ( english BV-trees are created from the bounding volumes) to move as quickly as possible in areas where collisions can occur. As soon as two bounding volumes intersect, phase two becomes active.
  • In the “near phase” ( English Narrow Phase ) the complex bodies within the bounding volumes are checked for possible intersections. Exact collision detection can result in a very high computational effort, which is why efficient approximate algorithms must be used for a large number of objects . The detection of a collision triggers the collision response.

To further reduce the computing power required during the simulation, the calculation of the bounding volumes and creating the hierarchical data structure into a pre-processing phase can ( English Preprocessing ) to be laid.

Collision detection when simulating deformable bodies

The simulation of deformable bodies is often divided into collision between two disjoint bodies and self-collision. The self-collision, for example when simulating textiles or hair, takes up almost half of the computing power and is therefore very computationally intensive. However, with some deformable bodies, self-collision cannot occur. Fluids are not considered deformable objects and must be considered separately in the event of a collision with a rigid or deformable object.

For deformable objects, the use of hierarchical data structures can take up a lot of computing power. That is why non-hierarchical data structures are often used.

Spatial dimension

Computer simulation and animation can run in 2D space or in 3D space. Most of the collision detection methods that have been created for three-dimensional space can be used to solve the two-dimensional problem, but this does not generally have to lead to an equally efficient solution.