Clever Geek Handbook

アルゴリズムと実装による衝突処理

こんにちは、Habr！



最近、衝突処理に関する記事を見ました。 そして、最も重要なことはありませんでした-アルゴリズムと実装。 このギャップを埋めて、衝突を見つけて処理する方法を考えてみましょう。 実装はJavaで行われます。

この記事には多くのコードがあることを警告します。









理論のビット



このアルゴリズムは、分割軸の定理に基づいています。 3Dの場合、これは分割面です。

定義は次のようになります。2つの凸形の図形の間に平面があり（2Dラインの場合）、それに対して図形が反対側にある場合、そのような図形は交差しません。



分割面をチェックできるかどうかの結果：分割面を取り、それに垂直に構築する場合、結果の平面上の図形の投影も抑制されません。



分離面を見つける（または、図形が交差するかどうかを見つけない）ために、側面の法線を収集し、それらに垂直を構築する必要があります。 これらの垂線は、モデルの投影を構築する必要がある平面の法線になります。 この場合、平面の座標を知る必要はありません。それらはすべて中心を通過すると仮定します。 以下の図は、いずれかの当事者の検証を示しています。









緑色は、チェックされている図の通常の側面を示します。 赤は分割面です。 投影を構築する必要がある青い面。 ご覧のように、青い面の法線を使用すると、テストする側面の法線に垂直になります。



これで、各平面にモデルの2つの投影ができました。 投影が交差しない少なくとも1つの平面を見つける必要があります。 これを行うには、2Dの場合にのみ同じ定理を適用できます（実装の詳細）。 見つかった場合、モデルは交差しません。 したがって、見つからない場合は交差します。



アルゴリズム



理論に基づいて、次の作業のアルゴリズムをコンパイルできます。







次に、各プレーンで個別に作業します。







投影交差検証アルゴリズム：



投影のすべての側面を収集し、それらを使用して作業します。







実装



次に、交差点の検出と処理の完全な実装を分析します。



小さな余談：

レイアウトされたコードを短くせず（悪魔は詳細にあります）、コメントを追加するだけです。興味のあるメソッドは投稿しませんが、 GitHubのリポジトリに簡単に見つけることができます。クラスへのリンクも残します。



アルゴリズムに従って、すべてのプレーンを検索することから始めます。 法線を知っていると仮定します（モデルファイルからそれらをロードしました）。

同一のプレーンを取り除くことは非常に重要であり、アルゴリズムはコストの点で非常に複雑であり、最適化は適切です。 この場合、それはまったくなく、チェックされるプレーンの数の減少はその速度に大きく影響します。

ゲーム内の物理モデルには、平行六面体のみを使用し、複雑な形状は使用しません。 その結果、最悪の場合、6つのプレーンをチェックします。



始める前に、以下で使用するインターフェースを検討する必要があります。 

public interface ICollidable { //   . //       ,     . float getRadius(); Vector3 getPosition(); ArrayList<Vector2> getConvexHull(Plane plane); //     (   ) ArrayList<Vector3> getNormals(); void normalizeLocation(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     




  private static ArrayList<Plane> getPlanes(ICollidable firstPh, ICollidable secondPh) { ArrayList<Plane> planes = new ArrayList<>(); ArrayList<Vector3> firstNormals = firstPh.getNormals(); ArrayList<Vector3> secondNormals = secondPh.getNormals(); Plane plane = new Plane(); int size = firstNormals.size() + secondNormals.size(); for(int i = 0; i < size; i++) { setPlane(plane, firstNormals, secondNormals, i); if (!planes.contains(plane)) planes.add(new Plane(plane)); } return planes; } private static void setPlane(Plane plane, ArrayList<Vector3> firstNormals, ArrayList<Vector3> secondNormals, int num) { //     (      x, y ) if (num < firstNormals.size()) plane.setFrom(firstNormals.get(num)); else { num -= firstNormals.size(); plane.setFrom(secondNormals.get(num)); } //   . plane.swapZY(); }




Planeクラス、 Vector3のソースコード



そのため、確認する飛行機があります。 これを行うには、各平面にモデルの投影を作成します。 投影が交差しない平面が見つからない場合、モデルの交差が最も少ない平面を見つける必要があります。この交差からベクトルを抽出する必要があります。 これは、モデルが交差しないようにモデルの1つを移動するために必要なベクトルになります。



最初に平面でベクトルを受け取ります。 したがって、X平面とY平面の軸の方向は重要ではありませんが、それでも、ベクトルを3Dに戻す必要があり、役に立つので、それらを保持する必要があります。



モデルの交差の検索を実装するクラス： Collision3D

上記のアルゴリズムを実行するコード： 



  private static CheckResult check(ICollidable firstPh, ICollidable secondPh) { //      ArrayList<Plane> planes = getPlanes(firstPh, secondPh); Collision2D min = null; Plane minPlane = new Plane(); for (Plane plane : planes) { //     . ArrayList<Vector2> resultOne = firstPh.getConvexHull(plane); ArrayList<Vector2> resultTwo = secondPh.getConvexHull(plane); //     . (       "check") Collision2D collision = new Collision2D(resultOne, resultTwo); Vector.release(resultOne); Vector.release(resultTwo); if (!collision.isCollide()) return null; //          if (min == null || collision.getMTVLength() < min.getMTVLength()) { min = collision; minPlane.setFrom(plane); } plane.release(); } return new CheckResult(min, minPlane); }




投影を取得する方法をより詳細に検討してみましょう。 完全な実装は次のとおりです。

実際には、投影自体を見つけることは難しくありませんが、投影自体からは意味がありません。 さらに処理するには、図の側面を正しく見つける必要があります。 それはまた凸状でなければなりません、下の写真はその理由を説明しています。



ヴォグンタイ




凸






最初の図（凹面の図）でわかるように、分離軸を構築できますが、アルゴリズムは図が交差することを計算します。 軸は図の側面に基づいて求められますが、この場合、軸に平行な側面はありません。 2番目の図では、凹面図がMBOをコンパイルしました。 ここで、アルゴリズムは軸を見つけます。 シェルを見つけるために、Grahamのアルゴリズムを実装しました。



以下は、単純な投影-平面に投影された点のセットを見つける機能です。 



  private ArrayList<Vector2> getDistinctProjection(Plane plane) { Vector2 vector = Vector.getInstance(2); //     HashSet         (   ) ArrayList<Vector2> result = new ArrayList<>(); for (Vector3 current : vertices) { plane.getProjection(vector, current); if (!result.contains(vector)) //     { Vector2 copy = Vector.getInstance(2, vector); result.add(copy); } } Vector.release(vector); return result; } //    Plane: public void getProjection(Vector2 result, Vector3 vector) { throwIfReleased(); float x = vector.getX() * xAxis.getX() + vector.getY() * xAxis.getY() + vector.getZ() * xAxis.getZ(); float y = vector.getX() * yAxis.getX() + vector.getY() * yAxis.getY() + vector.getZ() * yAxis.getZ(); result.setFrom(x, y); }




ここで、 MBO構築の実装を見てみましょう。

アクションは4つのステップで説明できます。

  1. プロジェクション検索。
  2. 基準点を選択します。
  3. 参照に対して残りのポイントを並べ替えます。
  4. 余分なポイントを削除します。


MBOについて少し
ウィキペディアによると：

集合Xの凸包はXを含む最小の凸集合です。ここで「最小の集合」とは、集合の埋め込みに関する最小の要素、つまり、この図形を含む他の凸集合に含まれる特定の図形を含む凸集合を意味します。




また、例があります：

たくさんの釘が打ち込まれたボードを想像してください-帽子自体ではありません。 ロープを取り、それにスライディングループ（投げ縄）を結び、ボードに投げてから締めます。 ロープはすべての爪を囲んでいますが、最も外側にあるのは一部のみです。 それが触れる爪は、爪のグループ全体の凸包を構成します[1]。





最小の凸包の構築に関する良い記事。 





  @Override public ArrayList<Vector2> getConvexHull(Plane plane) { //   ArrayList<Vector2> projection = getDistinctProjection(plane); ArrayList<Vector2> convexHull = new ArrayList<>(projection.size()); if (projection.size() < 2) throw new IllegalStateException("projection size less than 2"); //   ,  100%    //      //     ,  . int firstIndex = getFirstPointIndex(projection); Vector2 first = projection.remove(firstIndex); convexHull.add(first); //       Collections.sort(projection, new AngleComparator(first)); //   , ..      . Vector2 second = projection.remove(0); convexHull.add(second); Vector2 prevVector = Vector.getInstance(2); Vector2 currentVector = Vector.getInstance(2); for(Vector2 current : projection) { Vector2 firstPrevPoint = convexHull.get(convexHull.size() - 1); Vector2 secondPrevPoint = convexHull.get(convexHull.size() - 2); //   prevVector.setFrom(firstPrevPoint); prevVector.subtract(secondPrevPoint); //   currentVector.setFrom(current); currentVector.subtract(firstPrevPoint); //         ,     float angle = prevVector.getAngle(currentVector); if (angle >= 180 && angle < 360) convexHull.remove(convexHull.size() - 1); //     convexHull.add(current); } Vector.release(prevVector); Vector.release(currentVector); return convexHull; }


getAngle 
  //     Vector2 public float getAngle(Vector2 other) { throwIfReleased(); float scalar = getScalar(other); float lengthOne = this.getLength(); float lengthTwo = other.getLength(); float angle = (float)Math.toDegrees(Math.acos(scalar / (lengthOne * lengthTwo))); return Angle.correct(getCross(other) > 0 ? angle : 360 - angle); }






MBOに含めるべき最初のポイントは、一番右を選択します。 これらが複数ある場合は、それらの中から一番上のものを選択します。

最初のポイントの選択 
  private static int getFirstPointIndex(ArrayList<Vector2> projection) { Vector2 minVector = null; int minVectorIndex = 0; int size = projection.size(); for (int i = 0; i < size; i++) { Vector2 current = projection.get(i); if (minVector == null) { minVector = current; continue; } int compareX = Float.compare(current.getX(), minVector.getX()); if (compareX < 0) { minVector = current; minVectorIndex = i; } if (compareX == 0) { int compareY = Float.compare(current.getY(), minVector.getY()); if (compareY == 0) throw new IllegalArgumentException("projection has the same points"); if (compareY > 0) { minVector = current; minVectorIndex = i; } } } return minVectorIndex; }






最も混雑した場所は、ポイントを反時計回りに並べ替えることでした。 最初は実装が正しくありませんでしたが、例外的な状況を理解するには多くの時間がかかりました。 何が起きているのかを忘れないように、私は自分でコメントを書きさえしました。



最初のポイントを基準にして、コーナーごとにポイントを並べ替えます。 ポイントの角度が等しい場合は、最初のポイントからの距離に応じて、ポイントの位置に応じてさまざまな方法で-基準の上または下で比較します。 低い場合は、最初の距離が短い方に移動する必要があります。 より高い場合-その逆。









青い点は参照です。 緑は普通の点です。 赤-同じ角度で。 バイパススキームは、上記のソートアルゴリズムを示しています。



また、通常のソートのためにコーナーを正規化することを忘れないでください。コードには例があります。 



  private static class AngleComparator implements Comparator<Vector2> { private Vector2 first; private Vector2 left; private Vector2 right; public AngleComparator(Vector2 first) { this.first = first; left = Vector.getInstance(2); right = Vector.getInstance(2); } @Override public int compare(Vector2 lhs, Vector2 rhs) { //     //     left.setFrom(lhs); left.subtract(first); right.setFrom(rhs); right.subtract(first); //      float firstAngle = Vector2.xAxis.getAngle(left); float secondAngle = Vector2.xAxis.getAngle(right); //      // : 15, 45, 315, 345 () => -45, -15, 15, 45 () if (firstAngle > 90) firstAngle -= 360; if (secondAngle > 90) secondAngle -= 360; //          //              //          . //   ,     //       if (Math.abs(firstAngle - secondAngle) <= Vector.epsilon) { float leftLength = left.getLength(); float rightLength = right.getLength(); //    0,    if (firstAngle >= 0) return Float.compare(rightLength, leftLength); return Float.compare(leftLength, rightLength); } //          return Float.compare(firstAngle, secondAngle); } }




投影検索を理解しました。2つの投影の交差点を見つける方法を理解する必要があります。 ロジックは3Dと同じままです。



さらに、予測のさらなる予測を構築するにつれて、トートロジーをおaびするため、これらの予測を数字と呼びます。



結果の図のすべての側面を調べて、法線を探します。 次に、見つかった法線上に図の投影を作成します。投影が交差しない少なくとも1本の直線が見つかった場合、次に何をしますか。 予想外ですが、この場合、図形（3Dモデルなど）は抑制されません。 :)



ここでの完全なクラス実装： Collision2D 



  private static CheckResult check(ArrayList<Vector2> firstVertices, ArrayList<Vector2> secondVertices) { Vector2 mtv = null; Vector2 normal = Vector.getInstance(2); float minMTVLength = 0.0f; int count = firstVertices.size() + secondVertices.size(); for (int i = 0; i < count; i ++) { setNormal(normal, firstVertices, secondVertices, i); //      . X -   Y - . Vector2 firstProjection = normal.getProjection(firstVertices); Vector2 secondProjection = normal.getProjection(secondVertices); //         ,    ,     . if (firstProjection.getX() < secondProjection.getY() || secondProjection.getX() < firstProjection.getY()) return null; //   .   ,     . if (mtv == null) { mtv = Vector.getInstance(2, normal); minMTVLength = getIntersectionLength(firstProjection, secondProjection); } else { float mtvLength = getIntersectionLength(firstProjection, secondProjection); if (Math.abs(mtvLength) < Math.abs(minMTVLength)) { mtv = Vector.getInstance(2, normal); minMTVLength = mtvLength; } } } return new CheckResult(mtv, minMTVLength); } //    Vector2 public Vector2 getProjection(ArrayList<Vector2> vertices) { Vector2 result = null; for (Vector2 current : vertices) { float projection = getScalar(current); if (result == null) result = new Vector2(projection, projection); // x - max if (projection > result.getX()) result.setX(projection); // y - min if (projection < result.getY()) result.setY(projection); } return result; }


getIntersectionLength、setNormal 
  private static float getIntersectionLength(Vector2 firstProjection, Vector2 secondProjection) { return (secondProjection.getY() - firstProjection.getX() > 0) ? secondProjection.getY() - firstProjection.getX() : firstProjection.getY() - secondProjection.getX(); } private static void setNormal(Vector2 normal, ArrayList<Vector2> vertices, int num) { Vector2 firstPoint = vertices.get(num); Vector2 secondPoint = vertices.get(num + 1 == vertices.size() ? 0 : num + 1); Vector2 edge = secondPoint.getSubtract(firstPoint); normal.setX(-edge.getY()); normal.setY(edge.getX()); normal.normalize(); }






上記の方法ではすぐに、最小の交差ベクトルを探します。図と交差しない場合は、必要ありません。 そして、それらが交差する場合、3Dに変換する必要があります。これにより、モデルを互いに離すことができます。 これは、以下の方法を使用して実行できます。 



  private static Vector3 getMTV(CheckResult result) { Vector2 mtv2 = result.collision.getMTV(); Vector3 mtv3 = new Vector3(mtv2.getX(), mtv2.getY(), 0); Vector3 planeX = result.plane.xAxis(); Vector3 planeY = result.plane.yAxis(); Vector3 planeZ = result.plane.zAxis(); float[] matrix = new float[16]; matrix[0] = planeX.getX(); matrix[1] = planeX.getY(); matrix[2] = planeX.getZ(); matrix[4] = planeY.getX(); matrix[5] = planeY.getY(); matrix[6] = planeY.getZ(); matrix[8] = planeZ.getX(); matrix[9] = planeZ.getY(); matrix[10] = planeZ.getZ(); matrix[15] = 1.0f; Matrix.multiplyMV(mtv3.getRaw(), 0, matrix, 0, mtv3.getRaw(), 0); mtv3.normalize(); return mtv3; }




基本的にはこれですべてです。3Dモデルの交差を判断するには、上記のすべてで十分です。



アルゴリズムの応用



書く代わりに、2つのオブジェクトの交差をチェックするのに時間がかかることを書きます。 すでに述べたように、私は複雑な衝突モデルを使用しません。 また、モデルの周囲に記述された球体の半径を計算するなど、いくつかの最適化を適用します。球体の交差は比較がはるかに簡単です。 球体が交差する同じオブジェクトの場合、交差点の詳細な検索が並行して実行されます 。



ゲームのソースはこちらです： github.com/Nirklav/Tanks



UPD ：アルゴリズムの実装を更新し、平面への投影の形で余分なステップを削除しました。現在では、法線の投影がすぐに検索されます。


More articles:


All Articles