Collision detection

As collision detection or collision detection (English Collision Detection) is understood in two or three dimensional space in the computational geometry recognition of touching or overlapping of two or more geometric ( rigid or deformable ) objects. A collision detection or collision response follows the collision handling, thereby causing a reaction to the collision is started.

Collision detection methods are used, for example in image generation of animated films, in physical simulations, computer games, for path planning in robotics or in Haptics. We distinguish methods for exact and approximate solving collision responses.

Collision detection in rigid body simulation

In the rigid-body simulation (English Rigid Body Simulation) can be used different algorithms for the detection of a collision, the following situations are treated differently:

• Collision of simple geometrical body,
• Collision of two convex polyhedra (eg V -Clip algorithm)
• N collision- convex polyhedron (eg, I- Collide algorithm)
• Collision of non-convex polyhedra (eg RAPID )
• Collision complex geometric body.

In some cases, it is worthwhile to decompose non-convex polyhedra into convex and in turn to use the algorithms for finding collisions between convex polyhedra. In scenarios where large amounts or very complex geometric figures are, collision detection needs to be divided into two phases:

• In the " broad phase " (English Broad phase) is used to check which objects can overlap at all. This is done with the help of bounding volumes, which enclose the geometric objects (such as hitboxes, OBBs, AABBs or k- DOPs ). It is important that a bounding volume has a simple geometric configuration ( for example, spheres, cubes ), and is located as closely as possible to the geometric figure to be wrapped around complex. In addition, spatial, hierarchical data structures ( engl. BV -trees ) can be created from the bounding volumes in order to quickly get into areas where collisions can occur. As soon as two bounding volumes intersect, phase two is active.

• In the "near phase " (English Narrow phase) the complex body will be reviewed within the bounding volumes for possible intersections. An exact collision detection can result in very high computational complexity, so has to be introduced in a large number of objects in an efficient approximate algorithms. The detection of a collision triggers the collision response.

To further reduce the required computing power during the simulation, calculating the bounding volumes and creating the hierarchical data structure in a pre-processing phase (English preprocessing ) can be laid.

Collision detection in simulation of deformable bodies

The simulation of deformable bodies is frequently divided into collision between two disjoint bodies and self- collision. The self-collision takes, for example, in the simulation of textiles or hair almost half the computing power to complete and is therefore very compute- intensive. In some deformable bodies, however, may not self-collision. Fluids are not considered as deformable objects and must be considered separately in a collision with a rigid or deformable object.

For deformable objects using hierarchical data structures can take a lot of computing power to complete. Therefore often non-hierarchical data structures are used.

Spatial dimension

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

• Computational Geometry