Basic 3D collision detection issue

Question

I am trying to implement basic collision detection for a voxel-based 3D Java game I am working on. I am trying to implement the algorithm from this site: https://sites.google.com/site/letsmakeavoxelengine/home/collision-detection, but I can't seem to get it right. My question is, what does he mean by 'transform the player position to voxel space'. Should I round off the coordinates of the player to the nearest block, so that the voxel the player is in is the one where the center of the player is in? In my game the player is currently one voxel-sized cube.

The guy on that website writes that he only needs to check one voxel for collisions. But if I only check the voxel the center of the player is in, then the center of the player needs to intersect stuff before he collides with them. It's not supposed to be like that right? If the center of the player is in an inactive voxel, but a part of the player cube is intersecting an active voxel, which voxel should I check then?

I realise this text is pretty confusing but I hope you can understand my question. Here is my CollisionHandler class if you feel like looking at some code: (It doesn't really follow the algorithm from the site above yet because of the problems I've been having. It kind of only cares about collisions along the x-axis as of now)

public class CollisionHandler {
private static final float COLLISION_TOLERANCE = 0.4f;
private boolean xCol, yCol, zCol = false;

public void handleCollisions(ChunkManager chunkManager,
        FPCameraController player, float delta) {

    Vector3D playerPos = player.getPosition();
    Vector3D collision = findCollisionVector(player, chunkManager);

    if (collidesWithWorld()) {
        if (!(player.isFalling() && isGrounded(playerPos, chunkManager))) {
            player.setCollisionVector(collision);
            player.translateX(-playerPos.subtract(playerPos.round()).getX());
        }else{
            //123456
        }
    } else {
        if (player.isFalling()) {
            if (isGrounded(playerPos, chunkManager)) {
                float overlap = getYOverlap(player, chunkManager);
                player.translateY(overlap);
                player.setYSpeed(0);
                player.setIsFalling(false);
            } else {
                player.applyGravity(delta);
            }
        } else {
            if (!isGrounded(playerPos, chunkManager)) {
                player.setIsFalling(true);
                player.applyGravity(delta);
            }
        }

    }
}

private boolean collidesWithWorld() {
    return xCol || yCol || zCol;
}

/*
 * Returns a collision vector. Dot with velocity and then subtract it from
 * the player velocity.
 */
private Vector3D findCollisionVector(FPCameraController player,
        ChunkManager chunkManager) {

    Vector3D playerPos = player.getPosition();
    Vector3D distance = playerPos.subtract(playerPos.floor()).abs();

    Vector3D collisions = new Vector3D(1, 1, 1);
    float xDirection = (getCollisionDirection(distance.getX()));
    // float yDirection = (getCollisionDirection(distance.getY()));
    // float zDirection = (getCollisionDirection(distance.getZ()));

    try {
        Vector3D collision = getCollisionNormal(chunkManager, playerPos,
                xDirection, 'x');

        if (collision != null) {
            collisions = collision;
            xCol = true;
        } else {
            xCol = false;
        }

        // collision = getCollisionNormal(chunkManager, playerPos,
        // yDirection,
        // 'y');
        // if (collision != null) {
        // collisions.cross(collision);
        // yCol = true;
        // } else {
        // yCol = false;
        // }
        //
        // collision = getCollisionNormal(chunkManager, playerPos,
        // zDirection,
        // 'z');
        // if (collision != null) {
        // collisions.cross(collision);
        // zCol = true;
        // } else {
        // zCol = false;
        // }
    } catch (OutsideOfWorldException e) {
        e.printStackTrace();
    }

    return collisions;
}

/*
 * Returns the normal of the colliding block, given the axis and
 * direction.
 */
private static Vector3D getCollisionNormal(ChunkManager chunkManager,
        Vector3D playerPos, float direction, char axis)
        throws OutsideOfWorldException {
    Block b;
    Vector3D blockPos;
    if (direction != 0) {
        Vector3D dirVector;
        if (axis == 'x') {
            dirVector = new Vector3D(direction, 0, 0);
        } else if (axis == 'y') {
            dirVector = new Vector3D(0, direction, 0);
        } else if (axis == 'z') {
            dirVector = new Vector3D(0, 0, direction);
        } else {
            return null;
        }
        blockPos = playerPos.add(dirVector);

        b = chunkManager.getBlock(blockPos);

        if (b.isActive()) {

            return Plane3D.getBlockNormal(blockPos, direction, axis);
        }
    }
    return null;
}

private static float getCollisionDirection(float distance) {
    if (distance > COLLISION_TOLERANCE) {
        return 1;
    } else if (distance < COLLISION_TOLERANCE) {
        return -1;
    }
    return 0;
}

private static boolean isGrounded(Vector3D playerPosition,
        ChunkManager chunkManager) {
    try {
        return chunkManager.getBlock(
                playerPosition.add(new Vector3D(0, -1, 0))).isActive();
    } catch (OutsideOfWorldException e) {
        e.printStackTrace();
    }
    return true;
}

private static float getYOverlap(FPCameraController player,
        ChunkManager chunkManager) {
    Vector3D playerPosition = player.getPosition();
    Vector3D blockPosition = player.getLowestBlockPos();
    Block collisionBlock = null;

    try {
        collisionBlock = chunkManager.getBlock(blockPosition);

        // +" "+blockPosition);

        if (collisionBlock.isActive()) {
            float distance = playerPosition.subtract(blockPosition).getY();

            distance += player.getHeight();

            return -distance;

        }
    } catch (OutsideOfWorldException e) {
        e.printStackTrace();
    }

    return 0;
}
}

Here is another relevant method:

    public static Vector3D getBlockNormal(Vector3D blockPos, float direction,
        char axis) {
    float offset = Block.BLOCK_RENDER_SIZE / 2f;

    Vector3D pointA = null;
    Vector3D pointB = null;
    Vector3D pointC = null;

    Vector3D a = blockPos.round();

    a = a.addScalar(Block.BLOCK_RENDER_SIZE / 2f);
    float factor = -direction;
    if (axis == 'x') {
        pointA = a.add(new Vector3D(factor * offset, -offset, -offset));
        pointB = a.add(new Vector3D(factor * offset, offset, -offset));
        pointC = a.add(new Vector3D(factor * offset, -offset, offset));
    } else if (axis == 'y') {
        pointA = a.add(new Vector3D(-offset, factor * offset, offset));
        pointB = a.add(new Vector3D(offset, factor * offset, offset));
        pointC = a.add(new Vector3D(offset, factor * offset, -offset));
    } else if (axis == 'z') {
        pointA = a.add(new Vector3D(-offset, -offset, factor * offset));
        pointB = a.add(new Vector3D(offset, -offset, factor * offset));
        pointC = a.add(new Vector3D(offset, offset, factor * offset));
    } else {
        return null;
    }

    Vector3D v = new Vector3D(pointB.getX() - pointA.getX(), pointB.getY()
            - pointA.getY(), pointB.getZ() - pointA.getZ()).normalize();
    Vector3D w = new Vector3D(pointC.getX() - pointA.getX(), pointC.getY()
            - pointA.getY(), pointC.getZ() - pointA.getZ()).normalize();
    Vector3D normal = v.cross(w).scale(-1);

    return normal.scale(factor);

}

Answer 1

Its your design decision how to handle collisions, go with what you feel is most natural (elaboration follows):

The single voxel closest to the players position is the base from which you can derive more sophisticated methods easily by just making the collision detection take the voxel to check. You can then easily extend it to check multiple adjacent voxels to give the player the size you intend him to have.

For example you could treat the player as a cylinder, and check all voxels beneath the circle the cylinder covers. If you detect (for example) a single voxel of lava beneath the circle, you may apply lava damage (whatever ground properties your game works with).

Another problem you need to experiment with is elevation. Do you take the highest, the lowest or some kind of average of the covered voxels to determine the elevention where the player currently is (or when flying at which height he collides with the ground)?.

There are is no single recipe to get it "to feel right". You will need to experiment a little to find what you feel is "natural" for your game's intended physics model.

If your physics allow for fast movement, you may need to extend the collision checks to check the entire shape covered by an object between two game steps to avoid strange phenomena like bullets passing through obstacles. Because technically they could travel so fast that they will never have a position within the obstacle, although their movement vector clearly intersects the obstacle.

So "transform the player coordinates to voxel space" can mean anything, its not defining the method in detail. For initial testing your "round off to nearest block" is probably good enough, for the final game you probably need to apply some of the concepts outlined above to make its physics "feel right".