3D Collision Mesh (more efficient collision calculation)

Question

Before you go marking this as a duplicate. I would like it know that yes, there are some questions with similarly worded titles... However, I've read through them and they are vastly different.

I have recently completed a complete system for detecting collision of anywhere from the least to the most complex 3d meshes. The problem being that it is massively inefficient and very costly to gameplay experience in my engine. As a side note, I have completely made up this code, no reference, just to see if I could handle collision like this on my own. Sorry for the mess it is. So without further ado, here is the important code.

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

}

this class is just an entity that also has a collision mesh... And the impact detection. In order to understand what's going on here you'll need some more insight.

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

}

this is the collision mesh given to a collidable entity, it is made up of individual mesh points that also store there connections. Here is that 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;
        }
    }
}

}

the mesh connections are, what I think, is really killing the game's framerate. Which when objects as simple as 2 boxes have collisions enabled drops from the frame cap of 120 to usually about 3. While I am able to identify several problems I can think of no way to make this code less complicated than it currently is. Any help is much appreciated.

I know a question like this wouldn't typically be well received, and many people who come here will be looking for a minimal and complete example... But there really wasn't anything to be done to make this smaller than it is.

Answer 1

Suggestions:

1. detectImpact no less than 6 nested cycles. No wonder the performance is going to suffer. Is it possible to reduce the number of nesting? If not, can you at least precondition your data considered in those cycles? (e.g. don't consider all the vertices but only those inside a bounding-box overlap; and hope that the bounding box intersection will not contain most of these vertices - if they are your collision detection didn't do a proper job at previous stages, before the objects became so "intertwined").

2. detectImpact the inner-most cycle is under the form of for (int i = 1; i < points.size(); i++). Does the size() change during the cycle? If not, what is the point of calling a (virtual) method of a generic interface? Suggestion: create a local var to store the size and use it. Better still, try to use the foreach / for-in form, it has a better performance than the "iterating by index" (yes, I noted that inner-most cycle starts at 1, just skip the first step inside the cycle). As this is the inner-most loop, every bit counts.

3. As the vertices/edges/faces of your mesh are seldom going to modify once constructed, consider using arrays instead of lists. Yes, it's nice to have the flexibility of self-adjusting containers, but... there ain't such a thing like a free lunch and the performance is the wallet you are paying for it.
   Perhaps you could refine a bit the lifecycle of your meshed objects to have two distinct stages: construction (when you add vertices/edges to the mesh - self-adjusting collection come handy here) and "frozen/post-build-stage" (when you use arrays rather than containers). You'll get both the flexibility and performance, and you are going to pay from the "code complexity" account.