Хороший способ справиться со столкновениями между системами масса-пружина
Я программирую приложение для моделирования на C ++, в котором несколько структур масс-пружин будут двигаться и сталкиваться, и в настоящее время я борюсь с частью обнаружения и реагирования на столкновения. Эти структуры могут или не могут быть замкнуты (это может быть «шар» или просто цепочка масс и пружин), поэтому (я думаю) невозможно использовать «классический» подход, когда мы проверяем две перекрывающиеся фигуры.
Кроме того, столкновения являются действительно важной частью этого моделирования, и мне нужно, чтобы они были максимально точными, как с точки зрения обнаружения, так и с точки зрения реагирования (реальное время здесь не является ограничением). Я хочу быть в состоянии узнать силы, приложенные к каждому Узлу (массам), насколько это возможно.
В данный момент я обнаруживаю столкновения между узлами и пружинами на каждом временном шаге, и обнаружение, кажется, работает. Я могу вычислить время столкновения между одним узлом и пружиной и, таким образом, найти точное положение столкновения. Тем не менее, я не уверен, является ли это правильным подходом к этой проблеме, и после многих исследований я не могу найти способ заставить все работать должным образом, главным образом в аспекте реагирования столкновений.
Поэтому мне бы очень хотелось услышать о любой технике, алгоритме или библиотеке, которая кажется хорошо подходящей для такого рода коллизий, или о любой идее, которая может вам понадобиться, чтобы это сработало. Действительно, любая помощь будет принята с благодарностью.
Решение
Если вы можете выполнить следующие условия:
0) All collisions are locally binary - that is to say
collisions only occur for pairs of particles, not triples etc,
1) you can predict the future time for a collision between
objects i and j from knowledge of their dynamics (assuming that no other
collision occurs first)
2) you know how to process the physics/dynamicseac of the collision
тогда вы должны быть в состоянии сделать следующее:
Пусть Tpq будет предсказанным временем для столкновения между частицами p и q, а Vp (Vq) будет структурой, содержащей локальную динамику каждой частицы p (q) (то есть ее скорость, положение, пружинные постоянные, что угодно)
Для n частиц …
Initialise by calculating all Tpq (p,q in 1..n)
Store the n^2 values of Tpq in a Priority Queue (PQ)
repeat
extract first Tpq from the PQ
Advance the time to Tpq
process the collision (i.e. update Vp and Vq according to your dynamics)
remove all Tpi, and Tiq (i in 1..n) from the PQ
// these will be invalid now as the changes in Vp, Vq means the
// previously calculated collision of p and q with any other particle
// i might occur sooner, later or not at all
recalculate new Tpi and Tiq (i in 1..n) and insert in the PQ
until done
Существует начальная стоимость установки o (n ^ 2), но цикл повторения должен быть O (nlogn) — стоимость удаления и замены 2n-1 недействительных коллизий. Это довольно эффективно для умеренного количества частиц (до сотен). Преимущество заключается в том, что вам нужно обрабатывать вещи только во время столкновения, а не для одинаково разнесенных временных шагов. Это делает вещи особенно эффективными для малонаселенной симуляции.
Другие решения
Я думаю, что подход октри лучше всего с вашей проблемой. Октри делит виртуальное пространство на несколько рекурсивных листьев дерева и позволяет вычислять возможные столкновения между наиболее вероятными узлами.
Вот краткое введение: http://www.flipcode.com/archives/Introduction_To_Octrees.shtml 🙂