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 Collidable flag set and is assigned a surface_base property with the Collision option enabled (by default), 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.

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.

See Also

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.

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.

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.

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).

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.

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.

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.

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.

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.

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.

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.

See the following example illustrating several aspects of collision detection:

• Enabling Selective Surface-Based Collision.