Эффективный способ моделирования многих столкновений частиц?

Ответ 1

Если вы думаете об этом, частицы, движущиеся по плану, действительно представляют собой трехмерную систему, где три измерения: x, y и время (t).

Скажем, что "временной шаг" идет от t0 до t1. Для каждой частицы вы создаете 3D-сегмент, идущий от P0(x0, y0, t0) до P1(x1, y1, t1) на основе текущего положения, скорости и направления частиц.

Разделите 3D-пространство в 3D-сетке и привяжите каждый сегмент 3D-линии к ячейкам, которые он пересекает.

Теперь необходимо проверить каждую ячейку сетки. Если он связан с 0 или 1 сегментами, он не нуждается в дополнительной проверке (отметьте его как отмечено). Если он содержит 2 или более сегментов, вам необходимо проверить наличие конфликтов между ними: вычислить точку 3D-столкновения Pt, сократить два сегмента до конца в этот момент (и удалить ссылку на ячейки, которые они больше не пересекают), создать два новых сегмента, идущих от Pt до вновь вычисленных P1 точек в соответствии с новым направлением/скоростью частиц. Добавьте эти новые сегменты линии в сетку и отметьте ячейку, как отмечено. Добавление сегмента линии в сетку превращает все скрещенные ячейки в непроверенное состояние.

Если в вашей сетке больше нет отмеченных ячеек, вы решили свой временной шаг.

ИЗМЕНИТЬ

• Для 3D-частиц адаптируйте выше решение к 4D.
• Octrees - это приятная форма сетки разбиения 3D-пространств в этом случае, так как вы можете "выкручивать" проверенный/неконтролируемый статус, чтобы быстро находить ячейки, требующие внимания.

Ответ 2

Хорошим примером пространственного разделения является представление об игре понга и обнаружение столкновений между мячом и веслом.

Скажем, что весло находится в верхнем левом углу экрана, а мяч находится в левом нижнем углу экрана...

--------------------
|▌                 |
|                  |
|                  |
|     ○            |
--------------------

Не нужно проверять наличие столкновений каждый раз, когда мяч перемещается. Вместо этого разделите игровое поле на два справа вниз. Является ли мяч в левой части поля? (простой алгоритм прямоугольного прямоугольника)

  Left       Right
         |
---------|----------
|▌       |         |
|        |         |
|        |         |
|     ○  |         |
---------|----------
         |

Если да, разделите левую сторону снова, на этот раз по горизонтали, чтобы мы имели верхний левый и нижний левый раздел.

   Left       Right
          |
 ---------|----------
 |▌       |         |
 |        |         |
-----------         |
 |        |         |
 |     ○  |         |
 ---------|----------
          |

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

Вы можете продолжить разделение пространства на меньшие и меньшие куски, пока объект не будет разделен на два раздела. Это основной принцип BSP (метод, впервые примененный в ранних 3D-играх, таких как Quake). В Интернете существует целая куча теории пространственного разбиения в 2 и 3 измерениях.

http://en.wikipedia.org/wiki/Space_partitioning

В двух измерениях вы часто используете BSP или quadtree. В трех измерениях вы часто используете октет. Однако основной принцип остается тем же.

Ответ 3

Вы можете думать по линии "делить и побеждать". Идея состоит в том, чтобы идентифицировать ортогональные параметры, не влияя друг на друга. например можно думать о компоненте расщепления импульса вдоль оси 2 в случае 2D (3 оси в 3D) и вычислять столкновение/положение независимо. Другим способом идентификации таких параметров может быть группировка частиц, которые движутся перпендикулярно друг другу. Поэтому, даже если они влияют, чистый импульс вдоль этих линий не изменяется.

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

Ответ 4

Скажем, что в момент времени t для каждой частицы вы:

P   position
V   speed

и массив N * (N-1)/2 информации между частицами A (i) и A (j), где я < J; вы используете симметрию для оценки верхней треугольной матрицы вместо полной сетки N * (N-1).

    MAT[i][j] = { dx, dy, dz, sx, sy, sz }. 

что означает, что в отношении частицы j частица j имеет расстояние, состоящее из трех компонентов dx, dy и dz; и delta-vee, умноженное на dt, которое равно sx, sy, sz.

Чтобы перейти к мгновенному t + dt, вы предварительно обновите позиции всех частиц на основе их скорости

px[i] += dx[i]  // px,py,pz make up vector P; dx,dy,dz is vector V premultiplied by dt
py[i] += dy[i]  // Which means that we could use "particle 0" as a fixed origin
pz[i] += dz[i]  // except you can't collide with the origin, since it virtual

Затем вы проверяете весь массив N * (N-1)/2 и предварительно вычисляете новое относительное расстояние между каждой парой частиц.

dx1 = dx + sx
dy1 = dy + sy
dz1 = dz + sz
DN  = dx1*dx1+dy1*dy1+dz1*dz1  # This is the new distance

Если DN < D ^ 2 с диаметром D частицы, у вас было столкновение в dt только что.

Затем вы точно вычисляете, где это произошло, т.е. вы вычисляете точное столкновение, которое вы можете сделать из старого квадрата D2 (dx * dx + dy * dy + dz * dz) и нового DN: это

d't = [(SQRT(D2)-D)/(SQRT(D2)-SQRT(DN))]*dt

(Время, необходимое для уменьшения расстояния от SQRT (D2) до D со скоростью, которая покрывает расстояние SQRT (D2) -SQRT (DN) за время dt). Это делает гипотезу, что частица j, замеченная из кадра refrence частицы i, не "перевыполнилась" .

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

Зная dt и d "t = dt-dt, вы можете повторить расчет положения на Pi и Pj, используя dx * d't/dt и т.д. и получить точное положение P частиц я и j в момент столкновения, вы обновляете скорости, затем интегрируете их для оставшихся d" t и получаете позиции в конце времени dt.

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

Итак, вместо того, чтобы выполнять вычисления, мы просто отмечаем, что столкновение произошло при d't для частиц (i, j), и в конце прогона мы сохраняем минимум d t, в котором произошло столкновение, и между кем.

I.e, скажем, мы проверяем частицы 25 и 110 и находим столкновение при 0,7 dt; то мы обнаруживаем столкновение между 110 и 139 при 0,3 дт. Нет столкновений раньше 0,3 dt.

Мы вводим фазу обновления столкновений и "сталкиваемся" с 110 и 139 и обновляем их положение и скорость. Затем повторите вычисления 2 * (N-2) для каждого (i, 110) и (i, 139).

Мы обнаружим, что, вероятно, все еще существует столкновение с частицей 25, но теперь на 0,5 дт, а может быть, скажем, между 139 и 80 при 0,9 дт. 0.5 dt - новый минимум, поэтому мы повторяем расчет столкновения между 25 и 110 и повторяем, испытывая небольшое "замедление" в алгоритме для каждого столкновения.

Таким образом, единственным риском может быть только "призрачные столкновения", т.е. частица находится в D > диаметре от мишени в момент времени t-dt и находится на D > диаметре с другой стороны в момент времени t.

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

Таким образом, верно, что алгоритм значительно замедляется вблизи столкновения, но он значительно ускоряется, когда столкновения вряд ли. Если минимальное расстояние (которое мы вычисляем практически без затрат во время цикла) между двумя частицами, таково, что самая быстрая частица (которую мы также обнаруживаем практически без затрат) не может покрыть ее менее чем за пятьдесят dts, что 4900 % увеличивается там.

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

Этот метод имеет то преимущество, что O (N ^ 2) - он масштабируется с числом частиц - вместо того, чтобы быть O (M ^ 3) - масштабированием с объемом используемого пространства.

Я ожидаю, что программа C на современном процессоре сможет управлять в реальном времени несколькими частицами порядка десятков тысяч.

P.S.: на самом деле это очень похоже на подход Николаса Репикета, в том числе необходимость замедления в 4D близости от нескольких столкновений.

Ответ 5

До тех пор, пока не произойдет столкновение двух частиц (или между частицей и стеной), интеграция тривиальна. Подход здесь состоит в том, чтобы вычислить время первого столкновения, интегрировать до тех пор, затем вычислить время второго столкновения и так далее. Определим tw[i] как время, в течение которого i -ная частица попадает в первую стену. Это довольно легко вычислить, хотя вы должны учитывать диаметр сферы.

Расчет времени tc[i,j] столкновения между двумя частицами i и j занимает немного больше времени и следует из исследования во времени их расстояния d:

d^2=Δx(t)^2+Δy(t)^2+Δz(t)^2

Исследуем, если существует t положительный такой, что d^2=D^2, будучи d диаметром частиц (или суммой двух радиусов частиц, если вы хотите, чтобы они были разными). Теперь рассмотрим первый член суммы в RHS,

Δx(t)^2=(x[i](t)-x[j](t))^2=

Δx(t)^2=(x[i](t0)-x[j](t0)+(u[i]-u[j])t)^2=

Δx(t)^2=(x[i](t0)-x[j](t0))^2+2(x[i](t0)-x[j](t0))(u[i]-u[j])t + (u[i]-u[j])^2t^2

где новые члены, определяющие закон движения двух частиц для координаты x,

x[i](t)=x[i](t0)+u[i]t

x[j](t)=x[j](t0)+u[j]t

и t0 - время начальной конфигурации. Пусть тогда (u[i],v[i],w[i]) - три компоненты скоростей i -й частицы. Выполняя то же самое для остальных трех координат и суммируя, мы получим уравнение полинома 2-го порядка в t,

at^2+2bt+c=0,

где

a=(u[i]-u[j])^2+(v[i]-v[j])^2+(w[i]-w[j])^2

b=(x[i](t0)-x[j](t0))(u[i]-u[j]) + (y[i](t0)-y[j](t0))(v[i]-v[j]) + (z[i](t0)-z[j](t0))(w[i]-w[j])

c=(x[i](t0)-x[j](t0))^2 + (y[i](t0)-y[j](t0))^2 + (z[i](t0)-z[j](t0))^2-D^2

Теперь есть много критериев для оценки существования реального решения и т.д. Вы можете оценить это позже, если хотите его оптимизировать. В любом случае вы получаете tc[i,j], и если он является сложным или отрицательным, вы устанавливаете его на плюс бесконечность. Чтобы ускорить работу, помните, что tc[i,j] является симметричным, и вы также хотите установить tc[i,i] в бесконечность для удобства.

Затем вы берете минимум tmin массива tw и матрицы tc и интегрируете по времени для времени tmin.

Теперь вы вычитаете tmin ко всем элементам tw и tc.

В случае упругого столкновения со стенкой i -ной частицы вы просто переворачиваете скорость этой частицы и пересчитываете только tw[i] и tc[i,k] для всех других k.

В случае столкновения двух частиц вы пересчитываете tw[i],tw[j] и tc[i,k],tc[j,k] для всех остальных k. Оценка упругого столкновения в 3D не является тривиальной, возможно, вы можете использовать эту

http://www.atmos.illinois.edu/courses/atmos100/userdocs/3Dcollisions.html

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

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

Ответ 6

Вы можете определить силу отталкивания между частицами, пропорциональную 1/(квадрат расстояния). На каждой итерации вычисляют все силы между парами частиц, складывают все силы, действующие на каждую частицу, вычисляют ускорение частицы, затем скорость частицы и, наконец, новое положение частицы. Таким образом, столкновения будут обрабатываться естественным образом. Но взаимодействие с частицами и стенами является еще одной проблемой и должно решаться по-другому.