Как правильно обрабатывать столкновения движущейся окружности и нескольких линий?

#алгоритм #разработка_игр #физика

Есть работающий алгоритм, обрабатывающий столкновения движушейся окружности и линии
(сегмента линии). Столкновения определяются и разрешаются корректно. Но если окружность
"одновременно" касается 2 линий (т. е. очень быстро касается то одной, то другой) -
возникает нереалистичная ситуация. Причем, корректная для каждой пары "окружность-линия".

Окружность "падает" на две, расположенные под углом линии (изображение 1). В момент
контакта со второй линией она начинает двигаться вниз как и должна. Но в определенный
момент останавливается, не касаясь другой линии (изображение 3).
Похоже, разрешение столкновений в этом кадре происходит следующим образом.
Окружность выталкивается в сторону первой линии и контактирует с ней (4). Потом выталкивается
в сторону второй линии (5), контактирует с ней и вторая линия выталкивает ее так же,
но без контакта с первой (6). Кадр завершается, окружность видна на экране в этой позиции.
Потом эта же ситуация повторяется снова и снова и окружность "зависает".
Как можно исправить? Чтобы окружность скатилась в самый низ и уперлась в обе линии?
Если угол достаточно острый - так и происходит (за счет множественного разрешения столкновений
в одном кадре) (7).


    

Ответы

Ответ 1

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

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

 просчитать траекторию
 tau = Min(из событий, которые изменят траекторию)
 while (t < tau)
     осуществлять движение по траектории
     отрисовать кадр для времени t
     t++
 отрисовать кадр для времени tau (иначе может получится визуальный ляп)
 всё сначала


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


Ответ 2

Мне непонятны направления синих стрелoк на рисунках 2, 4, 5 и 6. Это вектора скорости
(или направления движения) круга - тогда они неправильные, или что-то другое?

Точка, в которй будет находиться центр круга в момент касания обеих линий, находится
как пересечение прямых параллельных линиям 1 и 2 и отстoящих от этих линий на расстояние
равное радиусу круга.

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


Ответ 3

Вам надо перейти от обсчёта времени к обсчёту событий.

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

Когда же очередной кадр «перешагнёт» предсказанное событие, надо определить новую
траекторию, получившуюся после этого события, и место следующего столкновения. Может
так случиться, что между двумя соседними кадрами произойдёт больше одного столкновения
(например, окружность с малой массой влетает в острый угол на большой скорости и начинает
очень часто переотражаться). Поэтому определение и обработку событий надо производить
в цикле перед собственно визуализацией текущего кадра, пока кадр по хронометражу вновь
не начнёт отставать от очередного события — это событие и станет следующим.

К слову, в качестве события стоит взять момент пересечения окружностью очередной
прямой в направлении снаружи внутрь. Это позволит окружности немного пролететь по инерции
сквозь прямую, если она до этого имела большой импульс (мы же не можем согнуть прямую
вслед за окружностью, так?).

Иными словами, событийная модель позволяет выполнять рассчёты только при смене траектории
под влиянием внешних сил. Если столкновений мало, то частота пересчёта траектории будет
значительно меньше кадровой частоты (FPS). Если же мы попадаем в плотную группу объектов —
частота обработки событий начинает значительно превышать кадровую. При этом скачки
FPS не влияют на точность физики.

Теперь перейдём к определению траектории после очередного столкновения. Так как при
столкновении окружности придаётся ускорение, то траектория будет представлять собой
кривую вида p = p0tloc + v0tloc + (a2 / 2)tloc, где:


p — точка на траектории в определённый момент времени. Является вектором, то есть
парой координат (x и y).
p0 — точка столкновения, от которой и пошла текущая траектория.
v0, a — скорость и ускорение окружности, получившиеся после его соударения с прямой.
Также являются векторами. Так как событие попадает точно на момент соударения с поверхностью,
нам не надо непрерывно симулировать выталкивание окружности из этой поверхности. Просто
пересчитываем ускорение с учётом направления переотражения и гравитации. И да, стоит
также учитывать упругость (т. е. поглощение энергии), чтобы окружность не скакала постоянно
по сцене. Скорость при этом берём ту, какая была на момент пересечения точки x0.
tloc — относительная временна́я отметка. Считается в секундах виртуального мира,
отсчитывается от момента нахождения в точке x0.


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

И чтобы у нас действительно было скольжение (без событий пересечения), необходимо
перед определением дальнейшей траектории проверять скорость вдоль перпендикуляра к прямой-поверхности.
Если скорость не превышает некий малый порог (так как абсолютного нуля мы никогда не
достигнем), значит при расчёте траектории направляем ускорение в нижнюю часть сцены
вдоль прямой. В противном случае переходим к обработке соударения.

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