3D Collision Mesh（更高效的碰撞计算）

Question

在您将其标记为重复之前。我希望它知道是的，有些问题的标题措辞相似......但是，我已经通读过它们并且它们有很大的不同。

我最近完成了一个完整的系统，用于检测从最不复杂到最复杂的 3d 网格的任何地方的碰撞。问题是它在我的引擎中的游戏体验非常低效且代价高昂。作为旁注，我完全编造了这段代码，没有参考，只是为了看看我是否可以自己处理这样的碰撞。抱歉，现在一团糟。话不多说，下面是重要的代码。

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);
}

}

这个 class 只是一个实体，它也有一个碰撞网格...和碰撞检测。为了了解这里发生的事情，您需要更多的洞察力。

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);
            }
        }
    }
}

}

这是给可碰撞实体的碰撞网格，它由单独的网格点组成，这些网格点也存储在那里的连接。这是 class:

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;
        }
    }
}

}

在我看来，网状连接确实会扼杀游戏的帧率。当 objects 像 2 个盒子一样简单时启用碰撞从 120 帧上限下降到通常大约 3是。非常感谢任何帮助。

我知道这样的问题通常不会被很好地接受，许多来这里的人都会寻找一个最小的和完整的例子......但是真的没有什么可以做的比实际小。

Answer 1

建议：

detectImpact不少于6个嵌套循环。难怪性能会受到影响。是否可以减少嵌套数量？如果没有，您是否可以至少对那些周期中考虑的数据进行预处理？（例如，不要考虑所有顶点，而只考虑边界框内的顶点重叠；并希望边界框交点不包含这些顶点中的大部分 - 如果它们是您的碰撞检测在对象变得如此 "intertwined").
detectImpact 最内圈为for (int i = 1; i < points.size(); i++)形式。 size() 是否在循环中发生变化？如果不是，调用通用接口的（虚拟）方法有什么意义？建议：创建一个本地变量来存储 size 并使用它。更好的是，尝试使用 foreach / for-in 形式，它有一个 better performance than the "iterating by index" （是的，我注意到最内层的循环从 1 开始，只需跳过循环内的第一步）。由于这是最内层的循环，每一位都很重要。
由于您的网格 vertices/edges/faces 一旦构建就很少修改，请考虑使用数组而不是列表。是的，拥有自调节容器的灵活性很好，但是...世上没有免费的午餐，性能就是您为此付出的代价。
也许您可以改进网格化对象的生命周期有两个不同的阶段：构建（当您将 vertices/edges 添加到网格时 - 自我调整集合在这里派上用场）和 "frozen/post-build-stage"（当您使用数组而不是容器时).您将获得灵活性和性能，并且您将从 "code complexity" 帐户支付。

3D Collision Mesh（更高效的碰撞计算）

3D Collision Mesh (more efficient collision calculation)

java

3d

mesh

collision-detection