graphics - ボール同士の衝突 - 検出と処理

Question

スタックオーバーフローコミュニティの助けを借りて、かなり基本的でありながら楽しい物理シミュレーターを作成しました。

alt text

マウスをクリックしてドラッグすると、ボールが発射されます。それは跳ね返り、最終的に「床」で止まります。

追加したい次の大きな機能は、ボールとボールの衝突です。ボールの動きは、x と y の速度ベクトルに分割されます。重力 (ステップごとに y ベクトルの小さな減少) があり、摩擦 (壁との衝突ごとに両方のベクトルの小さな減少) があります。ボールは正直、驚くほどリアルに動きます。

私の質問には2つの部分があると思います：

ボール同士の衝突を検出する最良の方法は何ですか?
各ボールを反復処理し、半径が重複しているかどうかを確認するために他のすべてのボールをチェックする O(n^2) ループがありますか?
ボール同士の衝突を処理するには、どの方程式を使用すればよいですか? 物理学 101
2 つのボールの速度 x/y ベクトルにどのように影響しますか? 2 つのボールが飛び出した結果の方向は? これを各ボールにどのように適用しますか?

alt text

「壁」の衝突検出とその結果のベクトルの変更の処理は簡単でしたが、ボールとボールの衝突ではさらに複雑になります。壁の場合、適切な x または y ベクトルの負の値を取るだけで、正しい方向に進むことができました。ボールに関しては、そうではないと思います。

いくつかの簡単な説明：簡単にするために、今のところ完全に弾性的な衝突で問題ありません。また、すべてのボールは現在同じ質量ですが、将来変更する可能性があります。

編集：私が有用だと思ったリソース

ベクトルを使用した 2D ボールの物理学: Trigonometry.pdf を使用しない 2 次元の衝突
2D ボールの衝突検出の例:衝突検出の追加

成功！

ボールの衝突検出と応答がうまく機能しています。

関連コード:

衝突検出:

for (int i = 0; i < ballCount; i++)  
{  
    for (int j = i + 1; j < ballCount; j++)  
    {  
        if (balls[i].colliding(balls[j]))  
        {
            balls[i].resolveCollision(balls[j]);
        }
    }
}

これにより、すべてのボール間の衝突がチェックされますが、冗長なチェックはスキップされます (ボール 1 がボール 2 と衝突するかどうかをチェックする必要がある場合は、ボール 2 がボール 1 と衝突するかどうかをチェックする必要はありません。また、それ自体との衝突のチェックもスキップします)。）。

次に、私のボールクラスには、collliding() メソッドと resolveCollision() メソッドがあります。

public boolean colliding(Ball ball)
{
    float xd = position.getX() - ball.position.getX();
    float yd = position.getY() - ball.position.getY();

    float sumRadius = getRadius() + ball.getRadius();
    float sqrRadius = sumRadius * sumRadius;

    float distSqr = (xd * xd) + (yd * yd);

    if (distSqr <= sqrRadius)
    {
        return true;
    }

    return false;
}

public void resolveCollision(Ball ball)
{
    // get the mtd
    Vector2d delta = (position.subtract(ball.position));
    float d = delta.getLength();
    // minimum translation distance to push balls apart after intersecting
    Vector2d mtd = delta.multiply(((getRadius() + ball.getRadius())-d)/d); 


    // resolve intersection --
    // inverse mass quantities
    float im1 = 1 / getMass(); 
    float im2 = 1 / ball.getMass();

    // push-pull them apart based off their mass
    position = position.add(mtd.multiply(im1 / (im1 + im2)));
    ball.position = ball.position.subtract(mtd.multiply(im2 / (im1 + im2)));

    // impact speed
    Vector2d v = (this.velocity.subtract(ball.velocity));
    float vn = v.dot(mtd.normalize());

    // sphere intersecting but moving away from each other already
    if (vn > 0.0f) return;

    // collision impulse
    float i = (-(1.0f + Constants.restitution) * vn) / (im1 + im2);
    Vector2d impulse = mtd.normalize().multiply(i);

    // change in momentum
    this.velocity = this.velocity.add(impulse.multiply(im1));
    ball.velocity = ball.velocity.subtract(impulse.multiply(im2));

}

ソースコード:ボールトゥボールコライダーの完全なソース。

この基本的な物理シミュレーターを改善する方法について誰か提案があれば教えてください! まだ追加していないことの 1 つは、ボールがよりリアルに転がるように角運動量です。他の提案はありますか？コメントを残す！

score 122 · Accepted Answer

2 つのボールが衝突するかどうかを検出するには、中心間の距離が半径の 2 倍未満かどうかを確認します。ボール間の完全な弾性衝突を行うには、衝突の方向にある速度の成分だけを気にする必要があります。もう一方のコンポーネント (衝突の接線) は、両方のボールで同じままです。1 つのボールから別のボールへの方向を指す単位ベクトルを作成し、ボールの速度ベクトルで内積をとることによって、衝突コンポーネントを取得できます。次に、これらのコンポーネントを 1D の完全弾性衝突方程式に組み込むことができます。

ウィキペディアには、プロセス全体のかなり良い要約があります。任意の質量のボールの場合、新しい速度は次の式を使用して計算できます (ここで、v1 と v2 は衝突後の速度であり、u1、u2 は衝突前の速度です)。

$v_{1} = \frac{u_{1}(m_{1}-m_{2})+2m_{2}u_{2}}{m_{1}+m_{2}}$

$v_{2} = \frac{u_{2}(m_{2}-m_{1})+2m_{1}u_{1}}{m_{1}+m_{2}}$

ボールの質量が同じ場合、速度は単純に入れ替わります。似たようなことをする私が書いたコードを次に示します。

void Simulation::collide(Storage::Iterator a, Storage::Iterator b)
{
    // Check whether there actually was a collision
    if (a == b)
        return;

    Vector collision = a.position() - b.position();
    double distance = collision.length();
    if (distance == 0.0) {              // hack to avoid div by zero
        collision = Vector(1.0, 0.0);
        distance = 1.0;
    }
    if (distance > 1.0)
        return;

    // Get the components of the velocity vectors which are parallel to the collision.
    // The perpendicular component remains the same for both fish
    collision = collision / distance;
    double aci = a.velocity().dot(collision);
    double bci = b.velocity().dot(collision);

    // Solve for the new velocities using the 1-dimensional elastic collision equations.
    // Turns out it's really simple when the masses are the same.
    double acf = bci;
    double bcf = aci;

    // Replace the collision velocity components with the new ones
    a.velocity() += (acf - aci) * collision;
    b.velocity() += (bcf - bci) * collision;
}

効率に関しては、Ryan Fox が正しく、領域をセクションに分割してから、各セクション内で衝突検出を行うことを検討する必要があります。ボールはセクションの境界で他のボールと衝突する可能性があるため、コードがさらに複雑になる可能性があることに注意してください。ただし、数百個のボールが得られるまでは、効率はおそらく問題になりません。ボーナスポイントとして、各セクションを異なるコアで実行したり、各セクション内で衝突の処理を分割したりできます。

score 50 · Accepted Answer

さて、何年も前に、あなたがここで紹介したようなプログラムを作成しました。
隠れた問題が 1 つあります (視点によっては、多くの場合もあります)。

ボールの速度が速すぎると、衝突を逃す可能性があります。

また、ほぼ 100% の場合、新しい速度は間違っています。まあ、速度ではなく位置です。新しい速度を正しい場所で正確に計算する必要があります。それ以外の場合は、前の離散ステップから利用可能な小さな「エラー」量でボールをシフトするだけです。

解決策は明らかです。タイムステップを分割して、最初に正しい場所にシフトし、次に衝突し、残りの時間をシフトする必要があります。

score 20 · Accepted Answer

この問題を解決するには、領域分割を使用する必要があります。

Binary Space Partitioning と Quadtreesについて読む

score 13 · Accepted Answer

画面を領域に分割し、領域内の衝突のみをチェックするという Ryan Fox の提案の明確化として...

たとえば、プレイエリアを四角形のグリッドに分割し (辺ごとに 1 単位の長さであると任意に言います)、各グリッドの四角形内での衝突をチェックします。

それは絶対に正しい解決策です。唯一の問題は (別のポスターが指摘したように)、境界を越えた衝突が問題になることです。

これに対する解決策は、最初のグリッドに対して 0.5 単位の垂直方向および水平方向のオフセットで 2 番目のグリッドをオーバーレイすることです。

次に、最初のグリッドの境界を越える (したがって検出されない) 衝突は、2 番目のグリッドのグリッドスクエア内にあります。すでに処理した衝突を追跡している限り (オーバーラップが発生する可能性があるため)、エッジケースの処理について心配する必要はありません。すべての衝突は、グリッドの 1 つのグリッドスクエア内にあります。

score 10 · Accepted Answer

衝突チェックの回数を減らす良い方法は、画面を複数のセクションに分割することです。次に、各ボールを同じセクション内のボールとのみ比較します。

score 8 · Accepted Answer

最適化するためにここで私が見るものの1つ。

距離が半径の合計であるときにボールが当たることには同意しますが、実際にこの距離を計算することはできません。むしろ、それが正方形であると計算し、そのように処理します。その高価な平方根演算の理由はありません。

また、衝突を見つけたら、それ以上残らなくなるまで衝突を評価し続ける必要があります。問題は、最初の問題により、正確な画像を取得する前に解決しなければならない他の問題が発生する可能性があることです。ボールが端でボールに当たった場合はどうなるか考えてみてください。2番目のボールがエッジに当たり、すぐに最初のボールに跳ね返ります。コーナーでボールの山にぶつかると、次のサイクルを繰り返す前に解決しなければならない衝突がかなり発生する可能性があります。

O（n ^ 2）に関しては、次のことを見逃したものを拒否するコストを最小限に抑えることができます。

1）動いていないボールは何も打てません。床に適度な数のボールが置かれている場合、これにより多くのテストを節約できます。（静止したボールに何かが当たったかどうかを確認する必要があることに注意してください。）

2）やりがいのあること：画面をいくつかのゾーンに分割しますが、線はぼやけている必要があります。ゾーンの端にあるボールは、関連するすべての（4つの可能性がある）ゾーンにあるものとしてリストされます。4x4グリッドを使用し、ゾーンをビットとして保存します。2つのボールゾーンのゾーンのANDがゼロを返す場合、テストは終了します。

3）前述したように、平方根は実行しないでください。

score 6 · Accepted Answer

2D での衝突検出と応答に関する情報が記載された優れたページを見つけました。

http://www.metanetsoftware.com/technique.html (web.archive.org)

彼らはそれがどのように行われるかを学術的な観点から説明しようとします。簡単なオブジェクト間の衝突検出から始めて、衝突応答とそれをスケールアップする方法に進みます。

編集：更新されたリンク

score 3 · Accepted Answer

あちこちでほのめかされているように見えますが、最初にバウンディングボックスのオーバーラップを比較するなど、より高速な計算を実行し、最初のテストに合格した場合は半径ベースのオーバーラップを実行することもできます。

加算/差分の計算は、半径のすべての三角関数よりもバウンディングボックスの方がはるかに高速であり、ほとんどの場合、バウンディングボックスのテストで衝突の可能性が排除されます。しかし、その後trigで再テストすると、求めている正確な結果が得られます。

はい、2つのテストですが、全体的に高速になります。

score 3 · Accepted Answer

これを行うには、2 つの簡単な方法があります。ボールの中心からの正確なチェック方法をジェイがカバーしています。

より簡単な方法は、長方形のバウンディングボックスを使用し、ボックスのサイズをボールのサイズの 80% に設定することです。そうすれば、衝突をうまくシミュレートできます。

ボールクラスにメソッドを追加します。

public Rectangle getBoundingRect()
{
   int ballHeight = (int)Ball.Height * 0.80f;
   int ballWidth = (int)Ball.Width * 0.80f;
   int x = Ball.X - ballWidth / 2;
   int y = Ball.Y - ballHeight / 2;

   return new Rectangle(x,y,ballHeight,ballWidth);
}

次に、ループで：

// Checks every ball against every other ball. 
// For best results, split it into quadrants like Ryan suggested. 
// I didn't do that for simplicity here.
for (int i = 0; i < balls.count; i++)
{
    Rectangle r1 = balls[i].getBoundingRect();

    for (int k = 0; k < balls.count; k++)
    {

        if (balls[i] != balls[k])
        {
            Rectangle r2 = balls[k].getBoundingRect();

            if (r1.Intersects(r2))
            {
                 // balls[i] collided with balls[k]
            }
        }
    }
}

score 3 · Accepted Answer

3

これKineticModelは、引用されたアプローチを Java で実装したものです。

于 2011-07-22T19:05:00.207 に答える

graphics - ボール同士の衝突 - 検出と処理

成功！

15 に答える 15

Related

Reference