2. Broadphase

Интро

Итак у нас есть алгоритмы, которые позволяют определить коллизии между объектами. Проблема появится тогда, когда объектов становится очень много, тк количество проверок будет расти квадратично числу объектов.

И из-за такого быстрого увеличения сложности в простом скетче уже происходят тормоза.

Решение столкновения шариков

1. Дано:

  • Массы сфер: $m_1$ и $m_2$
  • Скорости сфер до столкновения: $\vec{v_1}$ и $\vec{v_2}$
  • Радиусы сфер: $r_1$ и $r_2$
  • Коэффициент упругости $e$, где $e = 1$ для абсолютно упругого столкновения и $e < 1$ для частично упругого.
  • Положение центров сфер до удара: $\vec{r_1}$ и $\vec{r_2}$

2. Расчёт нормальной составляющей скорости:

Сначала находим нормальный вектор столкновения, который направлен вдоль линии, соединяющей центры двух сфер:

\begin{equation} \hat{n} = \frac{\vec{r_2} - \vec{r_1}}{|\vec{r_2} - \vec{r_1}|} \end{equation}

Касательный вектор $\hat{t}$ будет перпендикулярен $\hat{n}$, но для нас важна только нормальная составляющая при упругом столкновении.

3. Проекция скоростей на нормальный вектор:

Теперь проектируем скорости сфер на нормальный вектор:

\begin{equation} \begin{split} &v_{1n} = \vec{v_1} \cdot \hat{n} \ &v_{2n} = \vec{v_2} \cdot \hat{n} \end{split} \end{equation}

Эти проекции — скорости сфер вдоль линии столкновения.

4. Закон сохранения импульса:

При упругом столкновении сохраняется и импульс, и кинетическая энергия. Для нормальных составляющих скоростей:

\begin{equation} m_1 v_{1n} + m_2 v_{2n} = m_1 v’{1n} + m_2 v’{2n} \end{equation}

где $v’{1n}$ и $v’{2n}$ — нормальные компоненты скоростей после удара.

5. Закон коэффициента упругости:

Коэффициент упругости $e$ описывает, насколько изменится относительная скорость сфер после удара по сравнению с до удара:

\begin{equation} e = \frac{v’{2n} - v’{1n}}{v_{1n} - v_{2n}} \end{equation}

Для абсолютно упругого удара, где $e = 1$, это становится:

\begin{equation} v’{2n} - v’{1n} = v_{1n} - v_{2n} \end{equation}

6. Решение системы уравнений:

Теперь у нас есть два уравнения:

  1. $m_1 v_{1n} + m_2 v_{2n} = m_1 v’{1n} + m_2 v’{2n}$
  2. $v’{2n} - v’{1n} = v_{1n} - v_{2n}$

Решив их, получаем нормальные компоненты скоростей после удара:

\begin{equation} \begin{split} &v’{1n} = \frac{(m_1 - e m_2) v{1n} + (1 + e) m_2 v_{2n}}{m_1 + m_2} \ &v’{2n} = \frac{(m_2 - e m_1) v{2n} + (1 + e) m_1 v_{1n}}{m_1 + m_2} \end{split} \end{equation}

7. Скорости после удара:

После того как мы нашли нормальные составляющие скоростей $v’{1n}$ и $v’{2n}$, можем вычислить итоговые скорости сфер:

\begin{equation} \begin{split} &\vec{v’1} = \vec{v_1} + (v’{1n} - v_{1n}) \hat{n} \ &\vec{v’2} = \vec{v_2} + (v’{2n} - v_{2n}) \hat{n} \end{split} \end{equation}

Теперь у нас есть итоговые скорости сфер после столкновения.

Здесь я делаю неполностью упругое столкновение и релаксирую позиции объектов, так чтобы они не пересекались. У меня на тысячи объектов фпс уже падает до 10.

Для того чтобы уменьшить количество проверок, придумали разные алгоритмы о которых расскажу дальше.