# Collision Detection

The body movement without constraints and obstacles rarely happens in real life, the same is true for a virtual world. To correctly describe the situation when the body meets an obstacle the collision detection is used.

Collision detection algorithms, regardless of their implementation, usually operate with invisible simplified shapes that approximate the meshes of colliding objects. Such approximations are called colliders (or collision shapes). There are several types of colliders, which can be combined: boxes, spheres, cylinders, capsules, convex hulls.

There are two types of collisions implemented in Unigine depending on the types of colliding objects:

• Shape - Shape collision: between two objects with physical properties assigned (i.e. having a body and at least one shape, both must be enabled). In this case contact points between the shapes are found.
• Shape - Surface collision: between an object with physical properties assigned and a non-physical object (i.e. without physical representation). If the surface has the Collision flag set, it can also passively participate in physical interaction and prevent the physical object from going through. In this case, contact points between the shape and surface polygons are computed.

Notice
Scaling of meshes that participate in the collision detection is not supported.
In order for an object to participate in collision detection, it must be added to a specific BSP-tree representing the physics scene. The algorithm of enabling/disabling collision detection is illustrated below.

Algorithm of enabling/disabling collision detection.
Notice
• Disabling physics simulation globally does not turn off Collision detection.
• In case if an object has a body and a shape assigned and enabled, the collision detection algorithms will use only shape's parameters, while the parameters of its surfaces will be ignored.

## Process Pipeline#

The whole process is divided into the following stages and phases:

1. Collision detection
• Broad phase detection is a computationally low cost operation that quickly answers the question: Which objects have a strong possibility of colliding?
• Narrow phase is a computationally intense mesh on mesh collision detection, and thus cannot be performed on every pair of objects each frame. It answers the question: What part of object A collided with object B?
2. Collision response

It is the result of collision (e.g. two balls bounce off of each other). Without the response there would be no difference between collision and intersection of two objects. Friction, restitution and other parameters are taken into account in calculation of collision response.

Collision detection phases: (a) - broad phase, (b) - narrow phase, (c) - collision response

Checking all pairs of objects for collision is too time consuming, especially if the scene is large. That is why potentially colliding objects are found based on fast and rough tests. The broad phase increases collision detection efficiency and decreases computational load using certain optimization approaches (space partitioning, islands, freezing etc.).

Before doing more precise and costly calculations, we can filter out pairs of objects that are positioned too far to collide. Thus, all objects that have physical bodies are found within the Physical distance using the scene tree.

Notice
Non-colliding dummy bodies are skipped and not simulated unless they interact with other bodies through joints.

In a constrained physics simulation some objects influence the motion of others, while others don’t. Thus, these objects can be grouped into islands, which are self-contained groups of bodies that can influence the motion of each other in the group through constraint forces/impulses, but do not affect objects belonging to other islands. So, if bodies intersect with their bounding volumes, or there are joints connecting them, such bodies are combined in a island.

Objects grouped into islands

Unigine physics is deterministic. Bodies, shapes and joints are sorted inside islands. This ensures that contacts will always be solved in the predefined order and visualization of physics in the world is fully repetitive (the same for all computers).

## Narrow Phase#

After the broad phase we have a set of pairs of rigid bodies that are potentially colliding. Thus, for each pair, given the shape, position and orientation of both bodies, we need to find out if they are, in fact, colliding; if they are intersecting or if their distance falls under a small value of penetration tolerance. We also need to know contact points between the colliding bodies, since this information is necessary to resolve the collisions later.

Collisions are found for bodies inside each island: shape-shape and shape-surface. The found contact points are represented by their coordinates, normals, depth of shapes penetration, relative velocity (between two bodies), relative friction and restitution. At this stage we collect all the data that is required to calculate objects iteration.

## Collision Response#

The narrow phase extracts all necessary information about collisions, now something has to be done with this information to provide realistic reaction. Collision response stands for simulation of the changes in the motion of two solid bodies after collision. On collision, the kinetic properties of two bodies change instantaneously. Typically the bodies rebound away from each other, slide, or settle into a static contact, depending on their elasticity and the configuration of the collision. Unigine uses an impulse-based reaction model. During the collision, the first body applies a collision impulse to the second one at a contact point equal in magnitude but opposite in direction to the impulse applied by the second body, as per the Newtonian principle of action and reaction.

Collision response

At this stage all found contacts are cached together with contacts from the previous frame — to ensure proper interaction. On the basis of gathered contact points data, Unigine computes the impulse a shape gets by collision. Contact points are solved in a pseudo-random order to achieve simulation stability and reproducibility.

Joints are solved in the process of contact response calculation. The impulses that joints give the bodies attached to them are computed: how according to the current state of the joint, the bodies should respond to keep the joint unbroken (i.e. based on their masses, linear and angular velocities, change their movement direction and orientation), and how that response affects the joint (a joint can be broken by a too large impulse). Joints are also solved in the pseudo-random order.

Notice
Within one physics iteration, joints can be solved several times. High number of joint iterations increases the precision of calculations, as well as computational load.

The results of contact and joint solving are accumulated and applied to bodies. The coordinates of the bodies change according to their new linear and angular velocities.

There are two material parameters taken into account in the process of collison response calculation, which can be set for a shape and for a surface as well:

• Restitution - the degree of relative kinetic energy retained after a collision. It depends on the elasticity of the materials of colliding bodies.
• The minimum value of 0 indicates inelastic collisions (a piece of soft clay hitting the floor)
• The maximum value of 1 represents highly elastic collisions (a rubber ball bouncing off a wall)
• Friction - the force that impedes the relative motion of two surfaces in contact. The higher the value, the less tendency the body has to slide.

Notice
In case if an object contains a surface and a shape, both with specified restitution and friction, only the shape's parameters are to be used.

## Discrete and Continuous Collision Detection#

Regarding the way the time scale is considered, two basic approaches to finding contact points in case of collision are used. Both of these approaches are implemented in Unigine.

• Discrete collision detection is performed in certain intervals of time and each frame is treated separately from others. In general, discretization improves performance. However, when a project framerate is already low, a small fast-moving object is likely to teleport from one point to another instead of moving there smoothly and collision will not be detected.
• Continuous collision detection does not suffer this problem as the moving body is extruded along its trajectory (between two adjacent frames). In cases when something gets into this volume and a collision is detected, the body is taken back in time to correct the collision reaction.
Notice
Continuous collision detection is available for sphere and capsule shapes only.

Discrete (a) and continuous (b) collision detection

The primary advantage of discrete detection is that it tends to be much faster and simpler for objects with complex shape or large size. Continuous collision detection requires mathematical descriptions of all objects and their motions and the solving systems of equations, which can be difficult, slow, or even impossible in many circumstances.

To make collision detection flexible and selective, and to reduce calculation costs, the mechanism of bit masking is used. For example, we have an object, which does not participate in interactions with others, but we want it to lie on the ground. Matching the collision bit masks of this object and the ground (at least one bit in the masks should match) provides the necessary effect. One object can participate in several collision checks as only one bit in the mask is required to match for a pair of objects.

All scene objects, if not configured, are created with the default collision mask i.e. everything collides with everything. This may reduce performance in case if the number of objects in the world is large. The best practice here would be to establish what should collide with what.

## Static and Dynamic Contacts#

Basically there are two types of contacts:

• Static, when the body rests on another body. In this case, bodies are considered "frozen" until an external force affects them. This makes it possible to avoid unnecessary calculations.
• Dynamic, when two bodies, at least one of which is moving, collide. In this case, we have to calculate instantaneous change of velocities for both colliding objects.

Static (left) and dynamic (right) contacts

## Collision Examples#

See the following example illustrating several aspects of collision detection:

Last update: 2019-11-28