15

最初に2Dで開始し（後で3Dに拡張します）、（3Dで）ボルツマン分布への収束をシミュレートし、分布が2Dでどのように進化するかを確認するために、多くの粒子衝突をシミュレートする小さなプログラムを作成したいと思います。 。

私はまだプログラミングを始めていないので、コードサンプルを求めないでください。それは私が始めるのに役立つはずのかなり一般的な質問です。この問題の背後にある物理学には問題はありません。かなり良い速度分布を実現するには、少なくとも200〜500個の粒子をシミュレートする必要があるという事実です。そして、それをリアルタイムでやりたいと思います。

ここで、タイムステップごとに、最初にすべてのパーティクルの位置を更新し、次に衝突をチェックして、新しい速度ベクトルを更新します。ただし、すべてのパーティクルが他のすべてのパーティクルと衝突するかどうかを確認する必要があるため、これには多くのチェックが含まれます。私はこの投稿が多かれ少なかれ同じ問題であることに気づき、そこで使用されたアプローチも私が考えることができる唯一のものでした。ただし、衝突チェックが多すぎるため、リアルタイムではうまく機能しないのではないかと思います。

だから今：このアプローチがパフォーマンス的にうまくいくとしても（たとえば40fps）、不必要な衝突チェックを回避する方法を誰かが考えることができますか？

私自身のアイデアは、ボード（または3D：スペース）を少なくとも粒子の直径の寸法を持つ正方形（立方体）に分割し、2つの粒子の中心が隣接する正方形内にある場合にのみ衝突をチェックする方法を実装することでしたグリッド内...

粒子の量をできるだけ増やしながら、リアルタイムの計算/シミュレーションを続けたいので、もっと多くのアイデアを聞いてうれしいです。

編集：すべての衝突は純粋に弾性衝突であり、他の力が粒子に作用することはありません。私が実装する最初の状況は、ランダムな開始位置と速度を選択するためにユーザーが選択したいくつかの変数によって決定されます。

Edit2：ここで粒子衝突のシミュレーションに関する優れた非常に役立つ論文を見つけました。うまくいけば、それはより深いことに興味を持っている何人かの人々を助けるかもしれません。

4

6 に答える 6

9

考えてみれば、平面上を移動する粒子は、実際には3次元がである3Dシステムであり、x時間y（t）です。

「タイムステップ」がからt0に移行するとしt1ます。パーティクルごとに、現在のパーティクルの位置、速度、および方向P0(x0, y0, t0)にP1(x1, y1, t1)基づいてからに至る3Dラインセグメントを作成します。

3D空間を3Dグリッドに分割し、各3D線分を交差するセルにリンクします。

ここで、各グリッドセルをチェックする必要があります。0または1セグメントにリンクされている場合は、それ以上チェックする必要はありません（チェック済みとしてマークします）。2つ以上のセグメントが含まれている場合は、それらの間の衝突をチェックする必要があります。3D衝突点を計算しPt、2つのセグメントを短縮してこの点で終了し（そして、交差しなくなったセルへのリンクを削除し）、2つの新しいセグメントを作成します。パーティクルの新しい方向/速度に従って、から新しく計算されたポイントに移動しますPt。P1これらの新しい線分をグリッドに追加し、セルにチェックマークを付けます。グリッドに線分を追加すると、交差したすべてのセルがチェックされていない状態になります。

グリッドにチェックされていないセルがなくなったら、タイムステップを解決しました。

編集

  • 3D粒子の場合、上記のソリューションを4Dに適合させます。
  • この場合、八分木は3D空間分割グリッドの優れた形式です。これは、チェック済み/未チェックのステータスを「バブルアップ」して、注意が必要なセルをすばやく見つけることができるためです。
于 2012-10-24T09:45:16.620 に答える
7

空間分割の良い高レベルの例は、ポンのゲームについて考え、ボールとパドルの間の衝突を検出することです。

パドルが画面の左上隅にあり、ボールが画面の左下隅の近くにあるとします...

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

ボールが動くたびに衝突をチェックする必要はありません。代わりに、競技場を真ん中で2つに分割します。ボールはフィールドの左側にありますか？（長方形アルゴリズム内の単純な点）

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

答えが「はい」の場合は、左側をもう一度分割します。今回は水平に分割して、左上と左下のパーティションを作成します。

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

このボールは画面の左上隅にあるパドルと同じですか？そうでない場合は、衝突をチェックする必要はありません！同じパーティションに存在するオブジェクトのみが、相互の衝突をテストする必要があります。長方形チェック内で一連の単純な（そして安価な）ポイントを実行することにより、より高価な形状/ジオメトリの衝突チェックを実行する必要がなくなります。

オブジェクトが2つのパーティションにまたがるまで、スペースをますます小さなチャンクに分割し続けることができます。これがBSP（Quakeのような初期の3Dゲームで開拓された技術）の背後にある基本原則です。Webには、2次元および3次元での空間分割に関する理論がたくさんあります。

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

2次元では、多くの場合、BSPまたはクワッドツリーを使用します。3次元では、多くの場合、八分木を使用します。ただし、基本的な原則は同じままです。

于 2012-10-24T10:04:33.013 に答える
1

あなたは「分割統治」の線に沿って考えることができます。アイデアは、互いに影響を与えずに直交パラメータを識別することです。たとえば、2D（3Dでは3軸）の場合は2軸に沿って運動量成分を分割することを考え、衝突/位置を個別に計算できます。このようなパラメータを特定する別の方法は、互いに垂直に移動している粒子をグループ化することです。したがって、それらが影響を与えたとしても、それらの線に沿った正味の勢いは変わりません。

私は上記があなたの質問に完全に答えていないことに同意します、しかしそれはあなたがここで役に立つと思うかもしれない基本的な考えを伝えます。

于 2012-10-24T09:51:54.097 に答える
1

時間tで、各粒子について、次のようになります。

P   position
V   speed

粒子A（i）とA（j）の間の情報のN *（N-1）/2配列（i <j）。完全なN*（N-1）グリッドの代わりに、対称性を使用して上三角行列を評価します。

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

これは、粒子jに関して、粒子jの距離がdx、dy、dzの3つの成分で構成されていることを意味します。デルタビーは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's 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で衝突が発生しています。

次に、これが発生した場所を正確に計算します。つまり、衝突の正確なd'tを計算します。これは、古い距離の2乗D2（dx * dx + dy * dy + dz * dz）と新しいDNから実行できます。

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

（時間dtで距離SQRT（D2）-SQRT（DN）をカバーする速度で、SQRT（D2）からDまでの距離を短縮するために必要な時間）。これにより、パーティクルiの参照フレームから見たパーティクルjが「オーバーシュート」していないという仮説が立てられます。

これはより多額の計算ですが、衝突が発生した場合にのみ必要になります。

d'tとd"t= dt-d'tがわかれば、dx * d't / dtなどを使用してPiとPjの位置計算を繰り返し、粒子iとjの正確な位置Pを瞬時に取得できます。衝突の;あなたは速度を更新し、それから残りのd "tのためにそれを統合し、時間dtの終わりに位置を取得します。

ここで停止した場合、このメソッドは3粒子の衝突が発生した場合に機能しなくなり、2粒子の衝突のみを処理することに注意してください。

したがって、計算を実行する代わりに、パーティクル（i、j）のd'tで衝突が発生したことをマークし、実行の最後に、衝突が発生した最小のd'tとその間のd'tを保存します。

つまり、粒子25と110をチェックし、0.7dtで衝突を見つけたとします。次に、0.3dtで110と139の間に衝突が見つかります。0.3dtより前の衝突はありません。

衝突更新フェーズに入り、110と139を「衝突」させ、それらの位置と速度を更新します。次に、（i、110）と（i、139）ごとに2 *（N-2）の計算を繰り返します。

おそらくまだ粒子25との衝突がありますが、現在は0.5 dtであり、おそらく、0.9dtで139から80の間の衝突があることがわかります。0.5 dtが新しい最小値であるため、25から110の間で衝突計算を繰り返し、衝突ごとにアルゴリズムでわずかな「速度低下」が発生することを繰り返します。

このように実装された場合、現在の唯一のリスクは「ゴースト衝突」のリスクです。つまり、粒子は時間t-dtでターゲットからD>直径にあり、時間tで反対側のD>直径にあります。

これを回避するには、dtを選択する必要があります。これにより、特定のdtで粒子が自身の直径の半分を超えて移動することはありません。実際には、最速のパーティクルの速度に基づいて適応型dtを使用する場合があります。ゴースト視線衝突はまだ可能です。さらなる改良は、任意の2つの粒子間の最も近い距離に基づいてdtを減らすことです。

このように、衝突の近くでアルゴリズムがかなり遅くなるのは事実ですが、衝突が起こりそうにないときは非常に速くなります。2つの粒子間の最小距離（ループ中にほとんどコストをかけずに計算）が、最速の粒子（これもほとんどコストをかけずに見つける）が50 dts未満でカバーできない場合、それは4900です。すぐそこに％速度が上がります。

とにかく、衝突のない一般的なケースでは、5つの合計（実際には配列のインデックス付けのために34のようになります）、3つの積、およびすべてのパーティクルカップルに対していくつかの割り当てを行いました。粒子の更新自体を考慮に入れるために（k、k）のカップルを含めると、これまでのところコストの適切な概算が得られます。

この方法には、O（M ^ 3）ではなく、粒子の数に応じてスケーリングされるO（N ^ 2）であるという利点があります。

最新のプロセッサ上のCプログラムは、数万のオーダーの多数の粒子をリアルタイムで管理できると期待しています。

PS：これは実際にはNicolas Repiquetのアプローチと非常によく似ており、複数の衝突の4D付近で速度を落とす必要があります。

于 2012-10-24T10:24:37.587 に答える
1

2つのパーティクル間（またはパーティクルと壁の間）の衝突が発生するまで、統合は簡単です。ここでのアプローチは、最初の衝突の時間を計算し、それまで統合してから、2番目の衝突の時間を計算するというようになります。th粒子が最初の壁にぶつかるのにかかるtw[i]時間として定義しましょう。i球の直径を考慮する必要がありますが、計算は非常に簡単です。

tc[i,j]2つの粒子間の衝突時間の計算にはもう少し時間がかかり、それらの距離の時間の研究から得られiます。jd

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

が、粒子の直径（または、粒子を異なるものにしたい場合は、粒子の2つの半径の合計）であるようtな正の値が存在するかどうかを調べます。ここで、RHSでの合計の最初の項について考えてみましょう。d^2=D^2D

Δ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ここで、表示される新しい用語は、座標の2つの粒子の運動の法則を定義します。

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])の速度の3つの成分とします。i他の3つの座標についても同じことを行い、合計すると、の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すべての要素を減算します。twtc

-番目のパーティクルの壁との弾性衝突の場合は、iそのパーティクルの速度を反転し、1つおきにのみ再計算しtw[i]ます。tc[i,k]k

2つのパーティクル間の衝突の場合、再計算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)。次に、2つのタイムステップ間の積分はO(n)であり、壁にぶつかったり衝突したりするには、O(n)再計算が必要です。しかし、本当に重要なのは、衝突間の平均時間が。でどのようにスケーリングするかnです。そして、これに対する統計物理学のどこかに答えがあるはずです:-)

時間に対してプロパティをプロットする場合は、さらに中間のタイムステップを追加することを忘れないでください。

于 2012-10-24T22:29:17.970 に答える
0

1 /（距離の2乗）に比例して、粒子間の反発力を定義できます。各反復で、粒子ペア間のすべての力を計算し、各粒子に作用するすべての力を追加し、粒子の加速度を計算し、次に粒子の速度を計算し、最後に粒子の新しい位置を計算します。衝突はこのように自然に処理されます。しかし、粒子と壁の間の相互作用を処理することは別の問題であり、別の方法で処理する必要があります。

于 2019-04-30T20:01:36.023 に答える