3D碰撞網格（更有效的碰撞計算）

Question

在您將其標記爲重複之前。我希望它知道，是的，有一些問題的措辭相同的標題......但是，我已經通讀了他們，他們是完全不同的。

我最近完成了一個完整的系統，用於檢測從最小到最複雜的三維網格的任何地方的碰撞。問題在於它在我的引擎中的遊戲體驗效率非常低且非常昂貴。作爲一個方面說明，我已經完全編寫了這個代碼，沒有參考，只是爲了看看我是否可以自己處理這樣的碰撞。對不起，這是一團糟。所以，不要緊張，這裏是重要的代碼。

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. 由於網格的頂點/邊/面很少會在構建時修改，因此可以考慮使用數組而不是列表。是的，擁有自我調節容器的靈活性很好，但是......沒有免費的午餐這樣的事情，而且性能就是你爲之付出的錢包。也許你可以細化一下網格對象的生命週期，使其具有兩個不同的階段：構造（當你向網格添加頂點/邊緣 - 自我調整的集合在這裏得心應手）和「凍結/後期構建階段」（當你使用數組而不是容器時）。您將獲得靈活性和性能，並且您將從「代碼複雜性」帳戶中支付費用。