Обнаружение столкновений

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: В Unigine реализовано два типа коллизий в зависимости от типов сталкивающихся объектов:

• 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 - Shape : между двумя объектами с назначенными физическими свойствами (например, имеющими body и хотя бы одну shape , оба должны быть включены ). В этом случае обнаруживаются точки контакта между формами.
• 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. Столкновение Shape - Surface : между объектом с назначенными физическими свойствами и нефизическим объектом (т. е. без физического представления). Если поверхность имеет флаг Collision set, она также может пассивно участвовать в физическом взаимодействии и предотвращать прохождение физического объекта. В этом случае вычисляются точки контакта между формой и многоугольниками поверхности.

Примечание

Масштабирование сеток, участвующих в обнаружении столкновений, не поддерживается.

In order for an object to participate in collision detection (i.e. be a collider), it must be added to a specific BSP-tree representing the physics scene. Collision detection is automatically enabled for an object if it has a body assigned or at least one of its surfaces has the Collision flag set. The algorithm of enabling/disabling collision detection is illustrated below. Для того, чтобы объект участвовал в обнаружении столкновений (т.е. был collider), он должен быть добавлен в конкретное BSP-дерево, представляющее физическую сцену. Обнаружение столкновений автоматически включается для объекта, если ему назначено body или хотя бы одна из его поверхностей имеет установленный флаг Collision. Алгоритм включения / отключения обнаружения столкновений проиллюстрирован ниже.

Algorithm of enabling/disabling collision detection. Алгоритм включения / отключения обнаружения столкновений.

See AlsoСмотрите также#

The whole process is divided into the following stages and phases: Весь процесс разделен на следующие этапы и фазы:

1. Collision Detection - during this phase we find all collisions with all contact points and collect all necessary information. Обнаружение столкновений - на этом этапе мы обнаруживаем все столкновения со всеми точками контакта и собираем всю необходимую информацию.

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. Реакция на столкновение - это результат столкновения (например, два шара отскакивают друг от друга). Без ответа не было бы разницы между столкновением и пересечением двух объектов. Трение , восстановление и другие параметры учитываются при расчете реакции на столкновение.

3. Callbacks Execution - custom user-defined actions to be performed on certain physics-related events. Выполнение callback-функций - настраиваемые пользователем действия, выполняемые в отношении определенных событий, связанных с физикой.

Phases: (a) - collision detection, (b) - collision response Фазы: (а) - обнаружение столкновения, (б) - ответ на столкновение

Detecting CollisionsОбнаружение столкновений#

Checking all pairs of objects for collision is too time consuming, especially if the scene is large. 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. Проверка всех пар объектов на столкновение занимает слишком много времени, особенно если сцена большая. Прежде чем выполнять более точные и дорогостоящие вычисления, мы можем отфильтровать пары объектов, которые расположены слишком далеко для столкновения. Таким образом, все объекты, имеющие физические тела, находятся в пределах Физического расстояния с использованием дерева сцены.

Примечание

Non-colliding dummy bodies are skipped and not simulated unless they interact with other bodies via joints. Не сталкивающиеся фиктивные тела пропускаются и не моделируются, если они не взаимодействуют с другими телами через сочленения (joints).

Actually, there are no broad and narrow phases per se, so on the next step all collisions (shape-shape and shape-surface) along with contact points are found for all colliding bodies, i.e., if they are intersecting or have the distance between them less than the value of penetration tolerance. Contact points are represented by their coordinates, normals, depth of shapes penetration, relative velocity (between two bodies), relative friction and restitution. So, here we collect all the data that is required to resolve collisions later. На самом деле нет широкой и узкой фаз как таковой , поэтому на следующем шаге все столкновения ( shape-shape и shape-surface ) вместе с точками контакта находятся для всех сталкивающихся тел, т. е. если они пересекаются или расстояние между ними меньше значения допуска проникновения . Точки контакта представлены их координатами, нормалями, глубиной проникновения форм, относительной скоростью (между двумя телами), относительным трением и восстановлением. Итак, здесь мы собираем все данные, которые потребуются для разрешения конфликтов позже.

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, all contacting bodies as well as the ones having joints that connect them are combined in a island. В моделировании ограниченной физики одни объекты влияют на движение других, а другие - нет. Таким образом, эти объекты могут быть сгруппированы в острова , которые представляют собой автономные группы тел, которые могут влиять на движение друг друга в группе посредством сил / импульсов связи, но не влияют на объекты, принадлежащие другим. острова. Таким образом, все контактирующие тела, а также те, которые имеют соединения, соединяющие их, объединяются в остров.

Objects grouped into islands Объекты сгруппированы в острова

In case Deterministic mode of physics simulation is enabled bodies, shapes, and joints are sorted inside islands to ensur that contacts are solved in the predefined order and visualization of physics in the world is repetitive (on one computer). Если включен режим моделирования физики Stable , тела (body), формы (shape) и сочленения (joints) сортируются внутри островов, чтобы гарантировать, что контакты решаются в предопределенном порядке, а визуализация физики в мире повторяется (на один компьютер).

Collision detection uses certain optimization approaches to decrease computational load and improve efficiency (e.g., space partitioning, islands, freezing etc.). При обнаружении столкновений используются определенные подходы к оптимизации для уменьшения вычислительной нагрузки и повышения эффективности (например, разделение пространства, острова, замораживание и т. д.).

Collision ResponseОтвет на столкновение#

So, we've got 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. Итак, у нас есть вся необходимая информация о столкновениях, теперь нужно что-то сделать с этой информацией, чтобы обеспечить реалистичную реакцию. Реакция на столкновение означает моделирование изменений в движении двух твердых тел после столкновения. При столкновении кинетические свойства двух тел мгновенно меняются. Обычно тела отскакивают друг от друга, скользят или устанавливаются в статический контакт, в зависимости от их упругости и конфигурации столкновения. Unigine использует модель импульсной реакции . Во время столкновения первое тело применяет импульс столкновения ко второму в точке контакта, равной по величине, но противоположной по направлению импульсу, приложенному вторым телом, в соответствии с ньютоновским принципом действия и противодействия.

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. На этом этапе все найденные контакты кэшируются вместе с контактами из предыдущего кадра - для обеспечения правильного взаимодействия. На основе собранных данных о точках контакта Unigine вычисляет импульс, который форма получает от столкновения. Контактные точки решаются в псевдослучайном порядке для достижения стабильности и воспроизводимости моделирования.

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. Сочленения решаются в процессе расчета реакции контакта. Вычисляются импульсы, которые сочленения дают прикрепленным к ним телам: как в соответствии с текущим состоянием сочленения тела должны реагировать, чтобы сочленение оставалось неповрежденным (т.е. на основе их массы, линейной и угловой скорости, изменять направление движения и ориентацию ), и как этот ответ влияет на сочленение (сочленение может быть сломано слишком сильным импульсом). Сочленения также решаются в псевдослучайном порядке.

Примечание

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 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)The maximum value of 1 represents highly elastic collisions (a rubber ball bouncing off a wall)
  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)Restitution - степень относительной кинетической энергии, остающейся после столкновения. Это зависит от упругости материалов сталкивающихся тел.
  • The minimum value of 0 indicates inelastic collisions (a piece of soft clay hitting the floor) Минимальное значение 0 указывает на неупругие столкновения (удары кусочка мягкой глины об пол).
  • The maximum value of 1 represents highly elastic collisions (a rubber ball bouncing off a wall) Максимальное значение 1 соответствует высоко упругому столкновению (резиновый мяч, отскакивающий от стены).
• 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. Friction - сила, препятствующая относительному движению двух соприкасающихся поверхностей. Чем выше значение, тем меньше тенденция к скольжению тела.

Примечание

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. В случае, если объект содержит поверхность и форму, как с заданным восстановлением, так и с трением, должны использоваться только параметры формы.

Callbacks ExecutionВыполнение обратных вызовов#

After the simulation stage all physics callbacks are called. These callbacks are mainly used for creation, destruction or modification of other objects, such operations can only be performed in the main thread. После этапа моделирования вызываются все обратные вызовы физики. Эти обратные вызовы в основном используются для создания, уничтожения или изменения других объектов, такие операции могут выполняться только в основном потоке.

Примечание

Physics callbacks are called in the main thread. Обратные вызовы физики вызываются в основном потоке.

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. Что касается способа учета шкалы времени, используются два основных подхода к поиску точек контакта в случае столкновения. Оба этих подхода реализованы в 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.
  Примечание

  Continuous collision detection is available for sphere and capsule shapes only.Continuous collision detection is available for sphere and capsule shapes only.
  Continuous collision detection is available for sphere and capsule shapes only. Непрерывное обнаружение столкновений не сталкивается с этой проблемой, поскольку движущееся тело выдавливается по своей траектории (между двумя соседними кадрами). В случаях, когда что-то попадает в этот объем и обнаруживается столкновение, тело отправляется назад во времени, чтобы скорректировать реакцию на столкновение.
  Примечание

  Continuous collision detection is available for sphere and capsule shapes only. Непрерывное обнаружение столкновений доступно только для фигур сфера и капсула .

Discrete (a) and continuous (b) collision detection Дискретное (a) и непрерывное (b) обнаружение столкновений

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. Динамический , когда два тела, хотя бы одно из которых движется, сталкиваются. В этом случае мы должны рассчитать мгновенное изменение скоростей для обоих сталкивающихся объектов.

Static (left) and dynamic (right) contacts Статические (слева) и динамические (справа) контакты

See the following example illustrating several aspects of collision detection: См. следующий пример, иллюстрирующий несколько аспектов обнаружения столкновений:

• Enabling Selective Surface-Based Collision. Включение выборочного столкновения на поверхности .