Просчет столкновений

Допустим, есть биллиардный стол с шариками. У каждого шарика есть его положение,и вектор скорости. В цикле меняем положение шариков по векторам скоростей - получаем движение. Для обработки столкновений момент столкновения определяем по расстоянию от центров 2 шариков - если оно меньше диаметра шарика, значит, столкнулись.
Пока шарики движутся медленно, все прекрасно - катаются, сталкиваются. Но! Теперь увеличим их скорость так, чтобы длина вектора скорости оказалась больше диаметра шарика. В результате возможна такая ситуация - в одной итерации цикла быстро движущийся шарик находится перед другим, а в следующей - уже за ним, то есть шарики пролетели друг через друга!
Так вот, хотелось бы знать - существует ли способ правильно просчитать момент столкновения на больших скоростях?
Увеличить частоту итераций, разумеется, не выход, так как до бесконечности ее увеличить нельзя.
Можно проводить линию из точек положения шарика между текущей и предыдущей итерациями и проверять, находится ли на ней другой шарик. Но это годится, только если этот второй шарик неподвижен. Если же он тоже быстро движется, причем под углом к направлению первого, ничего не определить.
Возможно, неверен сам способ задания шариков и их движения - но тогда как их задавать правильно?

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

Раз у тебя пример с биллиардом - http://pascal.sources.ru/cgi-bin/forum/YaBB.cgi?board=algorithm;action=display;num=1042787730;start=0 - там был пример реализации, шарики друг сквозь друга не пролетали:)

Цитата Sulako, 24.03.03, 03:57:43

...
Увеличить частоту итераций, разумеется, не выход, так как до бесконечности ее увеличить нельзя.
...

Законы физики еще ни кому не удавалось нарушить.
Хочешь увеличивать скорость - увеличивай количество иттераций.
На счет бесконечности - это перегиб, скорость шаров до бесконечности тоже
поднять не удасться.

Должно быть:

<br>V_max*dt << R<br>

и точка.

В твоих руках разве что только есть возможность динамически отслеживать V_max и, соответственно, регулировать шаг по времени, например, по формуле

<br>procedure КоррекцияШагаПоВремениdt();<br>begin<br>  dt := 0.01*R / V_max;<br>  if dt > 0.01*base_time_interval then dt := 0.01*base_time_interval;<br>end;<br>

Тогда самый простой вариант "одного шага" по времени на интервал = base_time_interval будет таким

<br>t := 0;<br>while t < base_time_interval do begin<br>  НахождениеМаксимальнойСкорости();<br>  КоррекцияШагаПоВремениdt();  <br>  ДвижениеШаровНаВремя(dt);<br>  t := t + dt;<br>end;<br>

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

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

Цитата wormball, 25.03.03, 16:25:12

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

То есть ты предлагаешь решить задачу многих тел аналитически?

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

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

сложность по любому o(n²)

2S.Yu.Gubanov

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

Нельзя здесь проводить итерации по времени - можно пролететь.
Надо искать наиближайшее по времени столкновение, перебирая все возможные пресечения "движущийся шар - любой другой шар".  Удобно делать это, переходя в Систему Отсчета этого движущегося шара. Тогда для нахождения пересечения надо просто найти(если есть) точки пересечения 2 прямых и окружности (или сферы? ), пересчитать время, через которое будет столкновение (если будет) и так перебрать все остальные шары для одного движушегося шара. Затем взять следующий движушийся и т.д. Найти минимальное время до удара, пересчитать новые скорости и координаты и делать следующую итерацию.


З.Ы. Про бортики не забудь!!! ;D

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

Не за что. Честно говоря, меня заинтересовало, каков реализм твоего бильярда? Собираешся ли ты учитывать вращение шаров и, если да, то как? Ведь, ИМХО, это очень сложно...

Да биллиард только для примера, меня вообще интересовал сам принцип обработки на больших скоростях...
просто на моем биллиарде это было заметно...ну да вот оно - http://sulako-v.narod.ru/games/pool.htm Шарики залезают друг в друга, и приходится их отпихивать обратно...теперь попробую сделать по новому принципу...
Вращение делать я не собирался... реалистичное сделать и правда очень трудно, но для игры, по-моему, можно было бы просто делать поправку при движении на вращение...ну и передавать вращение при столкновениях...