2

OpenGLでレンダリングされたブルートフォース衝突アルゴリズムを使用して、2つのオブジェクト（それぞれ約10,000個の三角形で構成されている）が衝突するかどうかを確認するプロジェクトがあります。2つのオブジェクトは移動していません。それらをいくつかの位置に変換して、たとえば100個の三角形の衝突などを見つける必要があります。

これまで、これら2つのモデル間の線と平面の交差を実際にチェックするコードを作成しました。すべてをまっすぐにした場合、最初のモデルのすべての三角形のすべてのエッジを、他のモデルの各三角形の各平面でチェックする必要があります。これは実際には、終了するのに数時間かかる3'for'ループを意味します。何かがおかしいのか、コンセプト全体が誤解されているのではないかと思います。

     for (int i=0; i<model1_faces.num; i++) {
    for (int j=0; j<3; j++) {
        x1[j] = model1_vertices[model1_faces[i].v[j]-1].x;
        y1[j] = model1_vertices[model1_faces[i].v[j]-1].y;
        z1[j] = model1_vertices[model1_faces[i].v[j]-1].z;
    }
    A.x = x1[0]; 
    A.y = y1[0]; 
    A.z = z1[0];
    B.x = x1[1];
    B.y = y1[1];
    B.z = z1[1];
    C.x = x1[2];
    C.y = y1[2];
    C.z = z1[2];

    TriangleNormal = findNormalVector((B-A)*(C-A));
    RayDirection = B-A;

    for (int j=0; j<model2_faces.num; j++) {
        PointOnPlane = model2_vertices[model2_faces[j].v[0]-1]; // Any point of the triangle
        system("PAUSE");
        float D1 = (A-PointOnPlane)^(TriangleNormal);   // Distance from A to the plane of j triangle
        float D2 = (B-PointOnPlane)^(TriangleNormal);

        if ((D1*D2) >= 0) continue; // Line AB doesn't cross the triangle
        if (D1==D2) continue;       // Line parallel to the plane

        CollisionVect = A + (RayDirection) * (-D1/(D2-D1));
        Vector temp;
        temp = TriangleNormal*(RayDirection);
        if (temp^(CollisionVect-A) < 0) continue; 
        temp = TriangleNormal*(C-B);
        if (temp^(CollisionVect-B) < 0) continue; 
        temp = TriangleNormal*(A-C);
        if (temp^(CollisionVect-A) < 0) continue;

        // If I reach this point I had a collision //
        cout << "Had collision!!" << endl;

また、上記のこの関数を正確にどこで呼び出すべきか正確にはわかりません。レンダリング機能で、移動しないオブジェクトの衝突をチェックするだけでよいという事実を考慮して、レンダリング中に継続的に実行するか、1回だけ実行するようにしますか？

説明をいただければ幸いです。忙しすぎたり退屈して私のコードを見ることができない場合は、この概念全体をもう少し理解するのを手伝ってください。

4

2 に答える 2

1

すでに提案したように、バウンディングボリュームを使用できます。これらを最大限に活用するために、バウンディングボリュームをオクトリーに配置できます。この場合、ボリュームはボックスです。

最も外側のレベルでは、各バウンディングボリュームにオブジェクト全体が含まれます。したがって、ゼロレベルのバウンディングボリュームを比較することで、2つのオブジェクトが交差するかどうかをテストできます。すべての面が軸に沿って配置されている2つのボックスの交差をテストするのは簡単です。

八分木は、どの面がバウンディングボリュームのどのサブディビジョンに属するかをインデックス付けします。したがって、一部の面はもちろん複数のボリュームに属し、複数回テストされる場合があります。

利点は、ほんの一握りのサブボリュームのみが実際に交差するという事実によって失敗することが保証されているブルートフォーステストの多くを取り除くことができることです。実際の交差テストはまだブルートフォースですが、顔の小さなサブセットで行われます。

于 2013-01-14T22:46:57.167 に答える
0

お気づきのように、ブルートフォース衝突検出はスケーリングされないことがよくあります。:)通常のアプローチは、モデル/形状を含み、交差計算を単純化するバウンディングボリュームを定義することです。バウンディングボリュームは、モデルに応じてすべての形状とサイズで提供されます。それらは球、箱などである可能性があります。

バウンディングボリュームを定義することに加えてupdate、コードのセクションで衝突を検出する必要があります。このセクションでは、しばらくの間通過する可能性が最も高くなりますdelta。そのdelta時間は、オブジェクトが移動する必要がある距離と、その時間枠で衝突が発生したかどうかを判断するために必要になることがよくあります。

于 2013-01-14T22:21:37.400 に答える