Error while calculating normal vectors for SAT collision in 3d.

By | August 5, 2018
Questions:

I’ve been working on implementing SAT collision in my 3d game engine using LWJGL following this tutorial for 2d SAT collision.

Since the tutorial is for 2d and I’m trying to do 3d collision, I needed to change the code a bit to fit my needs, and have failed to do so successfully.

Here is the class SAT:

public class SAT {

public static IntersectionData collision(Box box1, Box box2){

    float overlap = Float.MAX_VALUE;
    Vector3f smallest = null;

    Vector3f[] box1Vertices = box1.getExtents();
    Vector3f[] box2Vertices = box2.getExtents();
    Vector3f[] box1Axes = getAxes(box1Vertices);
    Vector3f[] box2Axes = getAxes(box2Vertices);

    for (Vector3f axis:box1Axes){
        Projection p1 = Projection.project(box1Vertices, axis);
        Projection p2 = Projection.project(box2Vertices, axis);
        if (!p1.overlap(p2))
            return new IntersectionData(false, p1.getDistance(p2));
        else {
            float o = p1.getOverlap(p2);
            if (o < overlap){
                overlap = o;
                smallest = axis;
            }
        }
    }

    for (Vector3f axis:box2Axes){
        Projection p1 = Projection.project(box1Vertices, axis);
        Projection p2 = Projection.project(box2Vertices, axis);
        if (!p1.overlap(p2))
            return new IntersectionData(false, p1.getDistance(p2));
        else {
            float o = p1.getOverlap(p2);
            if (o < overlap){
                overlap = o;
                smallest = axis;
            }
        }
    }
    MTV mtv = new MTV(smallest, overlap);

    return new IntersectionData(true, mtv.getOverlap());
}

private static Vector3f[] getAxes(Vector3f[] vertices){ // FIXME
    Vector3f[] axes = new Vector3f[vertices.length];
    for (int i = 0; i < vertices.length; i++){
        Vector3f p1 = vertices[i];
        Vector3f p2 = vertices[i + 1 == vertices.length ? 0 : i + 1];
        Vector3f p3 = vertices[i + 2 >= vertices.length ? 1 : i + 1];
        Vector3f edge1 = Vector3f.sub(p2, p1, null);
        Vector3f edge2 = Vector3f.sub(p3, p1, null);
        Vector3f normal1 = Vector3f.cross(edge1, edge2, null);
        normal1.normalise();
        axes[i] = normal1;
    }
    return axes;
}
}

It makes use in other classes I’ve created which I can assure you work perfectly (Those were there before I started implementing SAT and I’ve used them several times), the Vector3f class that is built-in in LWJGL and in the following classes:

Projection:

class Projection {

private float min;
private float max;

private Projection(float min, float max) {
    this.min = min;
    this.max = max;
}

float getOverlap(Projection projection){
    if (overlap(projection))
        return Math.min(max, projection.max) - Math.max(min, projection.min);
    return 0;
}

float getDistance(Projection projection){
    if (overlap(projection))
        return getOverlap(projection);
    else
        return Math.max(min, projection.min) - Math.max(max, projection.max);
}

boolean overlap(Projection projection){
    return max > projection.min || projection.max > min;
}

static Projection project(Vector3f[] vertices, Vector3f axis){
    float min = Vector3f.dot(axis, vertices[0]);
    float max = min;

    for (Vector3f vertex:vertices){
        float p = Vector3f.dot(axis, vertex);
        if (p < min)
            min = p;
        else if (p > max)
            max = p;
    }

    return new Projection(min, max);
}
}

MTV:

class MTV {
private Vector3f axis;
private float overlap;

MTV(Vector3f axis, float overlap) {
    this.axis = axis;
    this.overlap = overlap;
}

public Vector3f getAxis() {
    return axis;
}

float getOverlap() {
    return overlap;
}
}

Note: The class IntersectionData is just a class that stores if two objects collide and the distance between the to objects, it is already in use in other parts of the engine and is fully functioning.

For some reason, collision won’t detect properly and objects pass right through each other, and I suspect the source of the problem is the way the normal vector is calculated, because when I run the simulation (the engine), I get an IllegalStateException: Zero length vector exception at the line normal1.normalise();.

Can someone please help me find the problem?

Answers:

Leave a Reply

Your email address will not be published. Required fields are marked *