Как правильно смоделировать систему N колизий тел, прям абсолютно точно?

Question

[Nimus2000]

Нужна не обычная модель, а прям идеальная. с 100 нюансов, которых сам штук 30 обнаружил.
Так точно, что бы при ударе 1 шара, по 1000 последовательно содеянных шаров, самый последний получил импульс.
Все уравнения и сама модель есть.
Есть 2 вопроса.
На что влияет глубина проникновения объектов коллизий, как ее обрабатывать, создает ли она дополнительный какой-то импульс, меньший или больший,.
Например при врезании шара в бокс, шар проник на расстояние h. Что надо делать

1. Оттолкнуть на h растояние h+radius
   
2. Оттолкнуть на расстояние radius
   
3. Ни чего не делать, сам уйдет(нет, на след итерации если не успел покинуть, то застрянет, так как вектор скорости снова изменит знак. А фиксить дорого
   
4. Оттолкнуть как 1,2 с увеличением скорости или наоборот ее уменьшением
   

Есть один довольно сложный не очевидный вопрос
При расчете кадра, допустим находим N коллизий, во всех них объект будет проникать в другой объект всегда, так как коллизия случилась, следовательно надо раздвинуть, теперь представим, вот мы раздвигаем 2 объекта, и 2-ой объект может проникнуть в 3-ий объект рядом, в итоге все объекты могут сложиться в один при разных параметрах, как такое исключить.

Answer 1

[hint000]

прям идеальная. с 100 нюансов

На что влияет глубина проникновения объектов коллизий, как ее обрабатывать, создает ли она дополнительный какой-то импульс, меньший или больший,.
Например при врезании шара в бокс, шар проник на расстояние h.

Если прям идеально, то не влияет глубина ни на что. Потому что эта глубина - просто результат конечного шага по времени модели. Идеально - вам после проникновения нужно сделать шаг назад во времени до точки прикосновения. Для этого нужно интерполировать из траекторий и скоростей объектов момент времени, когда они соприкоснулись без проникновения. И откатить все вычисления ровно до этого момента (в пределах погрешности интерполяции, конечно; мизерный "недолёт" или "перелёт" просто игнорируем, как будто его нет и как будто имеем точное прикосновение). Таким образом, шаг по времени должен быть изменяемый, а не по фиксированной сетке. Именно такая модель обеспечит правильное условие независимости скоростей, импульсов и т.п. от сетки времени. Но, возможно, вы и так уже это реализовали, поскольку далее встречается слово "раздвинуть".

коллизия случилась, следовательно надо раздвинуть, теперь представим, вот мы раздвигаем 2 объекта, и 2-ой объект может проникнуть в 3-ий объект рядом

А тут нужно после шага назад, иниццированного 1-м и 2-м объектами, проверять их оба на пересечение с 3-м, и если пересечение (проникновение) есть, то дополнительно ещё откатывать назад во времени, и шаг отката опять нужно интерполировать, а не брать фиксированный.
Согласен, когда одновременно очень близко 100 объектов (да даже 10), то довольно сложно будет определить, кто из них с кем столкнётся раньше, проблема на самом деле есть (по центрам масс легко определить очерёдность, а вот зацепы по касательной - неприятная штука).

Для смягчения проблемы можно сделать вот что. Берёте характерные размеры R[i] соседних объектов (условный радиус можно определить и для прямоугольника, этот размер нам потребуется для оценки, а не для точных рассчётов). Берёте текущие расстояния S[i,j] между ними. И по мере их сближения уменьшаете шаг времени обратно произведению логарифмов R[i]*R[j]/S[i,j]. Таким образом вы будете как бы рассматривать замедленную съёмку "взрыва" (массового столкновения), где можно будет точнее поймать факт, что 3-й успел столкнуться со 2-м ещё до того, как столкнулись 1-й и 2-й. Т.е. вы, сравнивая размеры объектов и расстояния между ними, заранее прогнозируете столкновение и готовитесь рассчитать его точнее, уменьшая шаг времени. Это позволит меньше откатывать время назад и меньше путаться в куче взаимодействующих объектов.

Answer 2

[rPman]

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

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

С другой стороны, после столкновения, пересчитывать проверку пересечения придется только для этих двух столкнувшихся объектов, т.е. трудоемкость линейная

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

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

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