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. 由于网格的顶点/边/面很少会在构建时修改，因此可以考虑使用数组而不是列表。是的，拥有自我调节容器的灵活性很好，但是......没有免费的午餐这样的事情，而且性能就是你为之付出的钱包。也许你可以细化一下网格对象的生命周期，使其具有两个不同的阶段：构造（当你向网格添加顶点/边缘 - 自我调整的集合在这里得心应手）和“冻结/后期构建阶段”（当你使用数组而不是容器时）。您将获得灵活性和性能，并且您将从“代码复杂性”帐户中支付费用。