Я видел картину теплового движения молекул на розетке. Мне это показалось очень интересным, поэтому на той неделе я построил простой физический движок для полного упругого столкновения двухмерных сфер.

До написания движка я смутно знал, что большинство физических движков, кажется, в каждом кадре позволяют каждому объекту немного двигаться вперед, а затем выполняют обработку столкновений, когда два объекта перекрываются. Но я мало что знаю об этом наборе теорий, и мне всегда очень трудно это делать, и я боюсь, что, когда столкновение очень сложное (например, есть много объектов, сталкивающихся друг с другом), будут проблемы, поэтому я решил следовать другой очень очевидной идее написать двигатель.

Двигатель

Поскольку мне нужно только смоделировать столкновения мяча с мячом и мяча со стеной, я на самом деле создал только один тип объекта — двумерный мяч. Вектор положения каждого шара является функцией времени:

r (t)= p + v ∗t

Таким образом, легко найти время столкновения двух шаров, решив уравнение

|r1( t ) −r2( t ) | =2R

Таким образом, когда двигатель работает, он фактически записывает время следующего столкновения. Если текущее время меньше времени следующего события столкновения, то игнорируем его, просто вычисляем положение каждой точки по функции, а потом рисуем картинку.

Когда текущее время превышает время следующего события столкновения, необходимо пересчитать новую функцию объекта после столкновения r’( t )r’(t), а затем снова вычислить время следующего столкновения, если оно до текущего времени, то продолжить обновление пока время следующего столкновения не превысит текущее время.

Для абсолютно упругого столкновения в Википедии можно найти следующую формулу:

Таким образом, двигатель по-прежнему очень прост.

События столкновений при техническом обслуживании

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

O(N²)

Наиболее распространенный метод заключается в вычислении событий столкновения между двумя объектами после того, как произошло столкновение, а затем в качестве времени следующего столкновения используется последнее событие столкновения. Это то, что я сделал в начале, сложность O(N²), что очень неоптимистично, в основном поддерживает плавную анимацию только в 400 точек.

O(NK)

После этого я подумал о том, как его оптимизировать. Фактически, после столкновения следующее событие столкновения каждой точки не изменится, потому что возникновение этого столкновения изменит только функцию двух объектов, которые сталкиваются на этот раз. Если мы запишем следующее событие столкновения для каждой точки, то после того, как произойдет столкновение, следующим событием столкновения будут только те объекты, которые происходят с текущим сталкивающимся объектом, и их следующее событие столкновения будет недействительным и его нужно будет пересчитать.

Таким образом, мы узнаем, что следующее событие столкновения — это объект, который сталкивается с текущим объектом столкновения, предполагая, что существует K, затем пересчитываем это K. Со следующим столкновением все в порядке (конечно, два текущих столкновения также учитываются).

Сложность этого составляет O(NK). Хотя, когда K= O(N), алгоритм по-прежнему O(N²). Но я провел некоторую статистику, K ≈ 0,01N, так что фактическая производительность все равно очень хорошая.

O (N log N)

Следуя изложенной выше идее, легко подумать, что если очередь событий столкновения каждой точки поддерживается, то после того, как произойдет столкновение, необходимо пересчитать только очередь столкновений двух сталкивающихся объектов, а количество пересчета столкновения событие определяется как O(NK), сводится к O(N).

В частности, это когда происходит xи yколлизия:

  1. В очереди событий столкновения всех точек отметьте время столкновения с xи ycollision как ∞+∞
  2. Пересчитать всю очередь событий столкновения для xsumy
  3. Очистите очередь событий столкновения для всех точек, чтобы найти событие столкновения с ближайшим временем столкновения в качестве следующего события столкновения.

Так как же реализована эта очередь коллизий? Естественно, это куча. Простая куча может реализовать эту операцию.

По статистике этот метод вычисляет на 65% меньше коллизий, чем описанный выше метод при тех же условиях.

Лучший путь?

Печальная новость заключается в том, что, хотя третий вышеприведенный метод выглядит очень мощным, на самом деле он отстает больше, чем второй метод. Основная причина может заключаться в том, что, когда количество точек невелико, например, 1000 точек, дополнительное время, которое приходит, рассчитывается больше, чем уменьшенные события столкновения.

Я чувствую, что должны быть какие-то более тонкие способы, такие как разделение экрана, и тогда следующее столкновение не произойдет в блоке, который находится далеко, поэтому его нужно только пересчитать локально.

Однако я действительно не знаю конкретного метода. Может быть, это дыра, которую нужно заполнить позже?

Визуализация

Единственный известный мне метод визуализации — HTML5 Canvas. Я думаю, что сотрудничать с JavaScript довольно удобно. Вначале я работал непосредственно на холсте. Позже я нашел библиотеку, специально используемую для управления холстом, поддерживающую WebGL, а также предоставляющую холст в качестве резервной копии, и с ней было легко работать, поэтому позже я переключился на эту библиотеку. К сожалению, текущим узким местом по-прежнему является расчет событий столкновения, поэтому улучшение производительности не является очевидным.pixi.js

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

Код со вторым методом расчета столкновений.

Код с использованием кучи.