[解決済み】ボールとボールの衝突の検出と処理

質問

Stack Overflowコミュニティの助けを借りて、かなり基本的な、しかし楽しい物理シミュレータを書きました。

マウスをクリックしてドラッグすると、ボールが発射されます。 ボールはバウンドして、最終的には床の上に止まります。

次に入れたい大きな機能は、ボールとボールの衝突です。 ボールの動きは、xとyの速度ベクトルに分解されます。 重力（ステップごとにyベクトルを小さくする）、摩擦（壁と衝突するたびに両方のベクトルを小さくする）があります。ボールは素直に、驚くほどリアルに動き回ります。

私の質問は2つに分かれると思います。

1. ボールとボールの衝突を検出するのに最適な方法は何ですか？
   
   各ボールを反復して、他のすべてのボールの半径が重なるかどうかをチェックする O(n^2) ループを用意すればよいのでしょうか。
2. ボールとボールの衝突を処理するには、どのような方程式を使用すればよいですか？物理学入門
   
   2つのボールの速度x/yベクトルにはどのような影響があるのでしょうか？ その結果、2つのボールが向かう方向はどうなるのでしょうか？ これを各ボールに適用するにはどうすればよいのでしょうか？

壁とボールの衝突判定とその結果のベクトル変更は簡単でしたが、ボールとボールの衝突はもっと複雑なようです。 壁については、適切な x または y ベクトルのマイナスを取るだけで、正しい方向に進みました。 しかし、ボールの場合はそうはいきません。

また、今はすべてのボールの質量が同じですが、将来的には変更するかもしれません。

編集：私が見つけた有用なリソース

ベクトルを使った2Dボール物理学。 三角法なしの2次元衝突.pdf

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と衝突するかどうかはチェックする必要がありません。 また、自分自身との衝突のチェックも省略します）。

そして、ボールクラスにはcolliding()メソッドと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));

}

ソースコード ボールとボールのコライダーの完全なソースです。

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

解決方法は？

2つのボールが衝突するかどうかを検出するには、中心間の距離が半径の2倍より小さいかどうかをチェックすればよい。完全な弾性衝突をさせるには、速度のうち衝突する方向の成分だけを気にすればよい。もう一方の成分（衝突の接線方向）は、どちらのボールも同じままである。衝突成分は、一方のボールから他方のボールへの方向を指す単位ベクトルを作成し、ボールの速度ベクトルとの内積を取ることで得られます。この成分を1次元完全弾性衝突方程式に代入します。

ウィキペディアには、かなり良い 全体の流れの要約 . どのような質量の球でも、新しい速度は方程式を使って計算できます（ここで、v1 と v2 は衝突後の速度、u1 と u2 は衝突前の速度です）。

ボールの質量が同じであれば、単純に速度を入れ替えるだけです。以下は、私が書いた似たようなことをするコードです。

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 の言うとおり、領域をセクションに分割し、各セクションで衝突判定を行うことを検討すべきです。ただし、ボールはセクションの境界で他のボールと衝突する可能性があるため、コードが非常に複雑になる可能性があることに注意してください。しかし、数百個のボールがあるうちは、効率は問題ないでしょう。ボーナスポイントとして、各セクションを別のコアで実行したり、各セクションで衝突の処理を分担したりすることもできます。