3D衝突メッシュ（より効率的な衝突計算）

Question

これを重複としてマークする前に、はい、同様の言葉で書かれたタイトルでいくつかの質問がありますが、私はそれらを読んできましたが、それらは大きく異なります。

私は、最近では、最も小さいものから最も複雑な3次元メッシュまで、どこからでも衝突を検出するための完全なシステムを完成させました。問題は、私のエンジンでゲームプレイの経験が非常に非効率で非常にコストがかかるということです。副次的なこととして、私は完全にこのコードを作りました、参照はありません、私はこのような衝突を私自身で扱うことができるかどうかを見ています。混乱のために申し訳ありません。だからこそ、重要なコードがあります。

package nope; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

import org.lwjgl.util.vector.Vector3f; 

import net.aionstudios.nightfall.entities.Entity; 
import net.aionstudios.nightfall.renderEngine.model.TexturedModel; 

public class ColliderEntity extends Entity { 

private List<CollisionMesh> entityBounds = new ArrayList<CollisionMesh>(); 
private boolean alertCollisions = false; 

public ColliderEntity(TexturedModel model, Vector3f position, float rotX, float rotY, float rotZ, float scale, BoundingBox entityBounds) { 
    super(model, position, rotX, rotY, rotZ, scale); 
    this.entityBounds.add(entityBounds); 
} 

public List<ColliderEntity> detectImpact(List<ColliderEntity> colliders){ 
    List<ColliderEntity> colE = new ArrayList<ColliderEntity>(); 
    colE.clear(); 
    for (ColliderEntity ce : colliders) { 
     if(ce != this) { 
      Vector3f boundsOffsets = new Vector3f(difference(this.getPosition().x, ce.getPosition().x), difference(this.getPosition().y, ce.getPosition().y), difference(this.getPosition().z, ce.getPosition().z)); 
      boolean xCollide = false; 
      boolean yCollide = false; 
      boolean zCollide = false; 
      for (CollisionMesh b1 : this.getEntityBounds()){ 
       for(MeshPoint mp : b1.getPoints()){ 
        List<Vector3f> points = mp.getConnectionsAndPoint(); 
        for (CollisionMesh b2 : ce.getEntityBounds()) { 
         for(MeshPoint mp2 : b2.getPoints()){ 
          List<Vector3f> points2 = mp2.getConnectionsAndPoint(); 
          for (Vector3f pt : points2){ 
           pt = new Vector3f(pt.x-boundsOffsets.x, pt.y-boundsOffsets.y, pt.z-boundsOffsets.z); 
           for (int i = 1; i < points.size(); i++){ 
            if(!xCollide || !yCollide || !zCollide){ 
             if(points.get(i-1).x > pt.x && pt.x > points.get(i).x) { 
              xCollide = true; 
             } 
             if(points.get(i-1).y > pt.y && pt.y > points.get(i).y) { 
              yCollide = true; 
             } 
             if(points.get(i-1).z > pt.z && pt.z > points.get(i).z) { 
              zCollide = true; 
             } 
            } 
           } 
          } 
          if(!!xCollide || !yCollide || !zCollide){ 
           for (Vector3f pts : points){ 
            pts = new Vector3f(pts.x-boundsOffsets.x, pts.y-boundsOffsets.y, pts.z-boundsOffsets.z); 
            for (int i = 1; i < points2.size(); i++){ 
             if(!xCollide || !yCollide || !zCollide){ 
              if(points2.get(i-1).x > pts.x && pts.x > points2.get(i).x) { 
               xCollide = true; 
              } 
              if(points2.get(i-1).y > pts.y && pts.y > points2.get(i).y) { 
               yCollide = true; 
              } 
              if(points2.get(i-1).z > pts.z && pts.z > points2.get(i).z) { 
               zCollide = true; 
              } 
             } 
            } 
           } 
          } 
          if(xCollide && yCollide && zCollide){ 
           colE.add(ce); 
           if(alertCollisions) { 
            System.out.println("Collision on Entity "+this.toString()+" at: "+this.getPosition().x+" "+this.getPosition().y+" "+this.getPosition().z+" with Entity "+ce.toString()+" at: "+ce.getPosition().x+" "+ce.getPosition().y+" "+ce.getPosition().z); 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
    return colE; 
} 

private float difference(float x, float x1){ 
    float dx = x - x1; 

    return (float) Math.sqrt(dx * dx); 
} 

public boolean isAlertCollisions() { 
    return alertCollisions; 
} 

public void setAlertCollisions(boolean alertCollisions) { 
    this.alertCollisions = alertCollisions; 
} 

public List<CollisionMesh> getEntityBounds() { 
    return entityBounds; 
} 

public void addEntityBounds(BoundingBox b){ 
    this.entityBounds.add(b); 
} 

public void removeEntityBounds(BoundingBox b){ 
    this.entityBounds.remove(entityBounds); 
} 

} 

このクラスは、衝突メッシュを持つ単なるエンティティです...そして、衝撃の検出。ここで何が起こっているのかを理解するには、より多くの洞察が必要です。

package nope; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

import org.lwjgl.util.vector.Vector3f; 

public class CollisionMesh { 

private List<MeshPoint> points = new ArrayList<MeshPoint>(); 

public CollisionMesh(MeshPoint[] points){ 
    for(MeshPoint p : points){ 
     this.points.add(p); 
    } 
} 

public List<MeshPoint> getPoints() { 
    return points; 
} 

public void addMeshPoint(MeshPoint point){ 
    for (MeshPoint p : points){ 
     if(point == p){ 
      return; 
     } 
    } 
    points.add(point); 
} 

public void removeMeshPoint(MeshPoint point){ 
    for(MeshPoint p : points){ 
     if(p == point){ 
      points.remove(point); 
      return; 
     } 
    } 
    cleanupMeshPoints(); 
} 

public void cleanupMeshPoints(){ 
    for(MeshPoint p : points){ 
     for(Vector3f pi : p.getConnections()){ 
      boolean connected = false; 
      for(MeshPoint p2 : points){ 
       if(p2.getPoint() == pi){ 
        connected = true; 
       } 
      } 
      if(!connected){ 
       p.getConnections().remove(pi); 
      } 
     } 
    } 
} 

} 

これは、それがまた、そこに接続を格納し、個々のメッシュ点で構成され、衝突可能実体に与えられた衝突メッシュです。実際にゲームのフレームレートを殺して、私が何を考え、

package nope; 

import java.util.ArrayList; 
import java.util.Arrays; 
import java.util.List; 

import org.lwjgl.util.vector.Vector3f; 

public class MeshPoint { 

private Vector3f point; 
private List<Vector3f> connections = new ArrayList<Vector3f>(); 

public MeshPoint(Vector3f point, Vector3f[] connections){ 
    this.point = point; 
    for(Vector3f connection : connections){ 
     this.connections.add(connection); 
    } 
} 

public Vector3f getPoint() { 
    return point; 
} 

public void setPoint(Vector3f point) { 
    this.point = point; 
} 

public List<Vector3f> getConnections() { 
    return connections; 
} 

public List<Vector3f> getConnectionsAndPoint() { 
    List<Vector3f> cp = connections; 
    cp.add(this.point); 
    return cp; 
} 

public void addConnection(Vector3f connection){ 
    for (Vector3f c : connections){ 
     if(c.x == connection.x && c.y == connection.y && c.z == connection.z){ 
      return; 
     } 
    } 
    connections.add(connection); 
} 

public void removeConnection(Vector3f connection){ 
    for (Vector3f c : connections){ 
     if(c.x == connection.x && c.y == connection.y && c.z == connection.z){ 
      connections.remove(connection); 
      return; 
     } 
    } 
} 

} 

メッシュ接続は、次のとおりです。ここでは、そのクラスです。 2つのボックスのような単純なオブジェクトが有効になっている場合、120のフレームキャップから通常は約3に落ちます。私はいくつかの問題を特定することができますが、私はこのコードを現在よりも複雑にする方法はないと思います。どんな助けも大歓迎です。

私はこのような質問は一般的に受け入れられず、ここに来る多くの人々が最小限の完全な例を探していることを知っています...しかし、これを小さくするためには本当に何もしませんでしたそれよりも。

Answer 1

提案：

1. detectImpact 6つのネストされたサイクルを下回りません。パフォーマンスが低下するのは不思議ではありません。入れ子の数を減らすことは可能ですか？そうでない場合、少なくともそのサイクルで考慮されるデータを前提条件とすることができますか？ （例えば、すべての頂点を考慮しないで、バウンディングボックスの重なり内にあるものだけを考慮してください。そして、境界ボックスの交差点がではなくにこれらの頂点の大部分が含まれていることを期待してください。以前の段階で、オブジェクトが「絡み合って」絡む前に）。

2. detectImpact最も内側のサイクルはfor (int i = 1; i < points.size(); i++)の形式です。サイクル中にsize()が変化しますか？そうでない場合は、ジェネリックインターフェイスの（仮想）メソッドを呼び出すポイントは何ですか？提案：sizeを格納するローカル変数を作成して使用します。より良いことに、foreach/for-inフォームを使用しようとすると、better performance than the "iterating by index"があります（内側のサイクルは1から始まり、サイクル内の最初のステップをスキップするだけです）。これは最も内側のループなので、すべてのビットがカウントされます。

3. メッシュの頂点/辺/面が構築された後に変更することはめったにないので、リストの代わりに配列を使うことを検討してください。はい、それは自己調整のコンテナの柔軟性を持つことはいいですが、...無料のランチのようなものはありませんし、パフォーマンスはあなたがそれを支払っている財布です。
   メッシュオブジェクトのライフサイクルを2段階に分けて調整することができます。メッシュに頂点やエッジを追加すると、自己調整コレクションが便利になります）、「フリーズ/ポストビルドステージ」（コンテナではなく配列を使用する場合）。柔軟性とパフォーマンスの両方を得ることができます。そして、あなたは "コードの複雑さ"の勘定から支払うつもりです。