Что такое столкновение? — При ошибке возобновить далее

From Mario bouncing off a Goomba to two cars bumping into each other in a racing
game, dealing with collisions is such an integral part of most video games that
we often take it for granted.

In this series of blog posts, I want to show you what actually goes on behind the
scenes in a physics simulation like the one above.
While we’re going to look at this through the lens video games, this post is
really about the actual math and physics of collisions.
Video games are just a nice way to contextualize these concepts and help make
things a little less abstract.

Let’s set our expectations and define a few terms.

Rigid bodies

The specific kind of physics simulation we are going to cover is called
rigid body physics. А rigid body тело, которое не деформируется под действием сил. Это идеализированная модель, поскольку в реальном мире не существует настоящих твердых тел; все деформируется на молекулярном уровне, даже если эта деформация не видна невооруженным глазом.

For most physics simulations, trying to simulate this level of detail is not
only extremely difficult (if not flat out impossible) and computationally
expensive, it’s also unnecessary.
As long as our bodies behave realistically, we’re allowed to simplify as much
as we want.
Rigid bodies are one such simplification.

This might sound a little abstract at the moment but will hopefully start to
make sense as we work through our examples.

Collision detection vs. collision resolution

In a video game engine, dealing with collisions can be broken down into two
distinct phases: collision detection и collision resolution.

Collision detection is about determining which bodies in our scene are
colliding.
This usually involves a bunch of geometry to check if two shapes are
intersecting or overlapping.
Depending on how many objects there are in our scene, this can be quite
computationally expensive and is usually heavily optimized.
The result of this step is then used in the collision resolution step.

Collision resolution is the process of figuring out what needs to happen to
two colliding bodies based on things like their current movement directions,
speeds, materials, and many other things.

In this series of blog posts, we’re only looking at the collision resolution
фаза, где происходит вся интересная физика.

Ok, enough preamble. Let’s get started!

Let’s start out by trying to define the problem we’re trying to solve.

Most games run in a big loop. In order to make things move on the screen, the
game engine needs to continually calculate the positions of the various objects
in the scene.
So on each iteration of the game loop, the position of each of object
gets updated a tiny amount based on its current velocity.

Velocity is a vector quantity, meaning it has both a magnitude and a direction.
We can represent an object’s current velocity with an arrow where the length of
the arrow represents the object’s current speed and the direction the arrow
is pointing its travel direction.

In the demonstration below, you can change the box’s
velocity перетаскивая arrow вокруг. Если вы когда-нибудь потеряетесь в космосе, вы всегда можете сбросить симуляцию с помощью кнопки

кнопка.

Velocity describes the change in position объекта за определенный интервал времени $Дельта т$. В физике такое изменение положения называется displacement и обычно обозначается $вещь{с}$

Whenever you see a little arrow over a variable like this $vec{s}$

In order to find an object’s new position, we first calculate the displacement
based on the object’s current velocity.

Where $Delta t$ is the time that has passed since the last iteration
of our game loop.
So if our game loop runs 60 times per second, then $Delta t$ would
be $frac{1}{60}$

We do this for every object in our scene and lo’ and behold. Things are moving!

What happens if the new positions of two objects would cause their geometries to
overlap?

The scene below shows two objects and their current
velocities в определенном кадре нашего игрового цикла.

Let’s think about what would happen if we didn’t do anything special and simply
continued with the next iteration of our game loop.

In this case, the physics engine would update each objects’ positions as usual
based on its current velocity. Это приведет к тому, что объекты будут проникать друг в друга и в конечном итоге проходить друг через друга.

You can see this happening in the demonstration below by dragging the
slider чтобы прогрессировать время.

This situation, where continuing to update the objects’ positions would cause
the objects to penetrate, is called a collision.

Part of a physics engine’s job is to resolve столкновения между объектами.

Conceptually, this is actually quite simple.
The goal of collision resolution is to change each object’s velocity so that
as the simulation progresses the objects will no longer penetrate each other.

We can define two equations for the respective post-collision velocities of our
bodies.

Where $vec{v}_{a, i}$

If we want our collision behavior to look realistic, we have to ensure that
whatever values we pick for $Delta vec{v}_{a}$

To start, let’s try defining what a collision is a little more rigorously.

Take a look at the scene below.
This scene shows two bodies on a specific frame of our game.
We can see that the bodies are touching, but are they colliding?

In the last section we learned that two bodies are said to be colliding if
continuing to move them along their current velocities would cause them to
penetrate each other.
So, with the information we’ve been given, can we actually determine if the
scene above depicts a collision or not?

We can’t!
All we know is that the bodies are touching.
We haven’t been given any information about their velocities.

To see why this matters, take a look at the demonstration below.

You can change the velocities of the bodies by dragging the
arrows вокруг. Индикатор сообщает вам, приведет ли текущая конфигурация к
столкновение
или нет столкновения. Вы можете проверить результат, проиграв симуляцию.

We can see that depending on the velocities of the bodies, the same scene can
either represent a collision or not.

Towards a definition

In order for two bodies to be colliding, two conditions have to be met:

1. The bodies’ geometries have to be touching or overlapping
2. The bodies are still moving towards the collision

Let’s assume that point 1 is true for now and focus on point 2, instead.
What does it mean for two bodies to be moving “towards the collision”?
This seems like a pretty circular definition.

Instead of asking what it means to move towards the collision, let’s ask what it
means to move away от столкновения. Фактически, давайте на мгновение полностью проигнорируем столкновения. Что значит отойти от surface?

The image below shows a box sitting on the floor.
What direction would you have to move the box in order to move it away from the
floor?

At first glance, this seems like a silly question.
Obviously, we’d have to move the box up.

However, there are an infinite number of directions that we could move the box!
As long as we are moving it generally вверх, увеличиваем расстояние между коробкой и полом.

Notice that while the box was moved the exact same distance in each
direction—that is, the length of the arrows То же самое — некоторые ящики явно находятся дальше от пола, чем другие.

So, are some of these directions more “up” than others?
Is there a direction that is most “вверх”?

To explore this idea, let’s play a little game.

Surface normals

You are given a box sitting on the floor.
Your goal is to move the box so that its distance to the floor is as close as
possible to the total distance the box was moved.
It doesn’t matter how far you move the box, just that these two distances are
as close to each other as possible.

To make things a little more challenging, the angle of inclination of the floor
is going to change every time you reset the game.

I know, I know, Game of the Year material right here.
But hopefully you were able to figure out that the direction that maximizes the
distance between the box and the floor is the direction that is perpendicular
на пол, что не обязательно прямо вверх!

This direction is called the normal directionчасто называемый просто normal поверхности. Нормальное направление поверхности всегда перпендикулярно поверхности. Это направление, которое указывает directly away с поверхности.

Normal directions are represented with a normalized vector; то есть вектор длиной $1$. Вектор с длиной $1$ также называется unit vector. Чтобы было понятно, что вектор нормализован, мы часто добавляем небольшую шляпку поверх переменной, вот так: $hat{n}$

If our surface is perfectly straight, the normal direction is the same
everywhere on the surface.
However, if the surface is curved, the normal direction will be different for
each point on the surface.
The easiest way to demonstrate this is with a circle.
If we stick with the idea that the normal direction points directly away from
a surface, then the normal direction for any point on the circle’s circumference
is the direction from the center of the circle to that point.

More generally, the normal направление точки на поверхности перпендикулярно tangent поверхности в этой точке.

We saw earlier that it isn’t necessary to move the box directly в нормальном направлении, чтобы отодвинуть его от пола.

What all these directions have in common, is that they all generally point in
the same direction as the surface normal.
We say that these directions have some component in the normal direction. Давайте подробнее рассмотрим, что именно это означает.

The dot product

To calculate how much of one vector is pointing in the same direction as another
vector, we can use the dot product из двух векторов. В нашем примере два вектора — это направление, в котором мы перемещаем прямоугольник, и нормаль к поверхности. Скалярное произведение между двумя векторами $вещь{а}$

The dot product can be defined either algebraically or geometrically.

Algebraically, the dot product is defined as the sum of the products of the
corresponding components of the two vectors.
For two-dimensional vectors such as the ones we’re dealing with, we can write
this as:

Note that the result of the dot product is a scalarа не другой вектор.

While this is fairly straight-forward to calculate, it’s not exactly obvious
what this scalar represents. К счастью, существует также геометрическая интерпретация скалярного произведения, которую можно хорошо визуализировать.

Say we have two vectors a и b у которых есть некоторый угол θ между ними.

Next, starting from the tip of a давайте проведем линию, перпендикулярную b соединяющий два вектора.

The length from the base of b до точки пересечения перпендикуляра b называется
scalar projection s из a
на b.

Imagine a light that’s perfectly perpendicular to b сияющий a. Скалярная проекция – это длина тени, a
набрасывается на b.

Since we now have a right triangle, trigonometry tells us that the length of
this projection является произведением длины
a (гипотенуза) и косинус угла между двумя векторами.

To be precise, it’s the absolute value скалярной проекции, которая дает нам длину тени, поскольку вскоре мы увидим, что скалярная проекция также может быть отрицательной.

This is equivalent to the dot product of a и единичный вектор $hat{b}$ в направлении
b.

Well hold on, that’s a bit of a bait and switch!
Why are we suddenly talking about the unit vector in the direction of
b? Это не то, что мы хотели найти! Как нам получить скалярное произведение между a и
b сам?

By definition, $hat{b}$

Therefore, multiplying both sides of by
$| vec{b} |$

In English, the dot product of two vectors is the length of the scalar
projection of one vector onto the other, multiplied by the length of the vector
we’re projecting onto.

Before moving on, take a second to think about the following questions.
You can click on them to reveal the answers.

I mentioned earlier that the scalar projection, and therefore the dot product,
can also be negative.
A lot of the time, we’re actually more interested in the sign скалярного произведения, а не его фактического значения.

The demonstration below shows the dot product между
two vectors так же хорошо как
angle между ними. Вы можете контролировать angle между векторами с
slider ниже. Угол нормализуется и всегда находится в диапазоне от 0° до 180°.

Pay attention to the sign принадлежащий dot product как вы меняете angle. Можете ли вы сказать, в чем angles тот
dot product отрицательный или положительный? А как насчет того, когда оно равно нулю? Подумайте о том, как, глядя на знак dot product
может помочь нам определить, указывают ли два вектора в одном направлении или нет.

If the angle between the vectors is acute (меньше, чем $90^{circ}$), скалярное произведение positive. Положительное скалярное произведение указывает на то, что векторы обычно указывают в одном направлении.

If the angle is obtuse (больше чем $90^{circ}$), скалярное произведение negative. Отрицательное скалярное произведение указывает на то, что векторы обычно направлены в противоположные стороны.

If the angle is exactly $90^{circ}$скалярное произведение zero.

Tying it all together

We started out by asking what it means for two bodies to be moving towards
столкновение. Чтобы ответить на этот вопрос, мы сделали небольшое отступление и рассмотрели, что значит отойти от surface.

Using the dot product, we can now answer the second question.
As long as the velocity vector of the body has some component in the normal
direction of the surface normal, i.e. the dot product between these vectors is
positive, the body is moving away с поверхности.

Even so, it might not be immediately obvious how this helps us answer the
original question.
Let’s look at our two boxes again.

This situation differs from the previous example of the box and the floor in two
ways:

1. We have two velocity vectors вместо одного, по одному на каждую коробку. Какой из них мы используем?
2. There is no “surface”, is there? What is our surface normal?

To answer the first question, instead of using the individual velocities of the
boxes, we use their relative velocity. Как следует из названия, относительная скорость сообщает нам скорости тел относительно друг друга. Относительная скорость — это векторная разность между отдельными скоростями. В этой статье я буду обозначать относительную скорость тел $а$

и $б$ как $vec{v}_{ab}$

Geometrically, the relative velocity $vec{v}_{ab}$

All other things being equal, two cars hitting each other head-on at
$50 frac{text{km}}{text{h}}$

What about the second question?
What’s our surface and its corresponding normal?
What we’re looking for is called the collision normal. К сожалению, способ расчета нормали столкновения зависит от формы (или геометрии) сталкивающихся тел, поэтому я не могу просто показать вам одну формулу.

What we’re dealing with is called a vertex-edge collision. При этом типе столкновения точка (или вершина) одного тела сталкивается со стороной (или краем) другого тела. Мы поговорим больше о нормалях столкновения, когда рассмотрим силы, действующие во время столкновения. А пока вам придется поверить мне на слово, что при столкновении вершины с ребром нормаль столкновения перпендикулярна ребру.

In our example, the collision normal выглядит так:

If we label our bodies a и bпо соглашению, нормаль столкновения указывает на тело a. Довольно произвольно, какое тело называется a или b до тех пор, пока мы последовательны во всех наших расчетах.

Based on what we learned about surface normals earlier, the
collision normal сообщает нам направление, которое указывает прямо от поверхности столкновения.

We can now calculate the dot product between the relative velocity of the bodies
$vec{v}_{ab}$

We’ll call this value the relative normal velocity. Это составляющая относительной скорости в направлении нормали столкновения. На данный момент нас интересует только знак относительной нормальной скорости, но позже мы увидим, что он играет важную роль в расчете сил, действующих во время столкновения.

Using our understanding of the dot product, we can say that

• if the relative normal velocity is positiveтела уже расходятся
• if the relative normal velocity is negativeтела все еще врезаются друг в друга

The demonstration below combines all concepts we’ve learned so far.
As before, you can change the velocities ящиков, перетаскивая стрелки. В правом верхнем углу показано collision normal и
relative velocity тел.

You can see that as soon as the angle between the
relative velocity и
collision normal меньше или равно
$90^{circ}$— и, следовательно, скалярное произведение положительно — тела больше не сталкиваются.

So, finally, we can formally define what a collision is:

Neat!

If you made it to this point, pat yourself on the back!
We now have a formal definition of what a collision is, as well as the set of
equations we’re ultimate trying to solve when resolving collisions
(see ).
Not bad at all!

In the next post, we’ll dive into the actual physics behind collisions.
If you enjoyed this article, you’ll love the next part!

This is all I have for you today.
Thank you so much for reading and I hope I’ll see you again for the next post.

If you want to discuss this article, feel free to either reach out to me on
Twitter или напишите мне по электронной почте
[email protected].