How do you determine which object/surface the user's pointing at with lwjgl?

Question

Title pretty much says it all. I'm working on a simple 'lets get used to lwjgl' project involving manipulation of a rubik's cube, and I can't figure out how to tell which side/square the user's pointing at.

Answer 1

You'll want to use 3D picking. Here's some code I use in my game.

First I cast a ray from my camera. I'm using the mouse, but if you're just using where the user is looking, you can just use the center of the window. This is that code from my camera class:

public Ray GetPickRay() {
    int mouseX = Mouse.getX();
    int mouseY = WORLD.Byte56Game.getHeight() - Mouse.getY();

    float windowWidth = WORLD.Byte56Game.getWidth();
    float windowHeight = WORLD.Byte56Game.getHeight();

    //get the mouse position in screenSpace coords
    double screenSpaceX = ((float) mouseX / (windowWidth / 2) - 1.0f) * aspectRatio;
    double screenSpaceY = (1.0f - (float) mouseY / (windowHeight / 2));

    double viewRatio = Math.tan(((float) Math.PI / (180.f/ViewAngle) / 2.00f)) * zoomFactor;

    screenSpaceX = screenSpaceX * viewRatio;
    screenSpaceY = screenSpaceY * viewRatio;

    //Find the far and near camera spaces
    Vector4f cameraSpaceNear = new Vector4f((float) (screenSpaceX * NearPlane), (float) (screenSpaceY * NearPlane), (float) (-NearPlane), 1);
    Vector4f cameraSpaceFar = new Vector4f((float) (screenSpaceX * FarPlane), (float) (screenSpaceY * FarPlane), (float) (-FarPlane), 1);


    //Unproject the 2D window into 3D to see where in 3D we're actually clicking
    Matrix4f tmpView = Matrix4f(view);
    Matrix4f invView = (Matrix4f) tmpView.invert();
    Vector4f worldSpaceNear = new Vector4f();
    Matrix4f.transform(invView, cameraSpaceNear, worldSpaceNear);

    Vector4f worldSpaceFar = new Vector4f();

    Matrix4f.transform(invView, cameraSpaceFar, worldSpaceFar);

    //calculate the ray position and direction
    Vector3f rayPosition = new Vector3f(worldSpaceNear.x, worldSpaceNear.y, worldSpaceNear.z);
    Vector3f rayDirection = new Vector3f(worldSpaceFar.x - worldSpaceNear.x, worldSpaceFar.y - worldSpaceNear.y, worldSpaceFar.z - worldSpaceNear.z);

    rayDirection.normalise();

    return new Ray(rayPosition, rayDirection);
}

Then I follow out the ray until it intersects with an object, you can do this with bounding boxes or something similar, since this is specific to your game, I'll let you handle that. Generally this is done by following the ray out (adding the direction of the ray to it's starting point over and over 'till you bump into something).

Next you want to see which face is being picked, you can do that by iterating over the triangles in your cube to see if the ray intersects them. The following function does that and returns the distance to the picked face, then I just use the intersected face that's closest to the camera (so you're not picking the back face).

public static float RayIntersectsTriangle(Ray R, Vector3f vertex1, Vector3f vertex2, Vector3f vertex3) {
    // Compute vectors along two edges of the triangle.
    Vector3f edge1 = null, edge2 = null;

    edge1 = Vector3f.sub(vertex2, vertex1, edge1);
    edge2 = Vector3f.sub(vertex3, vertex1, edge2);

    // Compute the determinant.
    Vector3f directionCrossEdge2 = null;
    directionCrossEdge2 = Vector3f.cross(R.Direction, edge2, directionCrossEdge2);


    float determinant = Vector3f.dot(directionCrossEdge2, edge1);
    // If the ray and triangle are parallel, there is no collision.
    if (determinant > -.0000001f && determinant < .0000001f) {
        return Float.MAX_VALUE;
    }

    float inverseDeterminant = 1.0f / determinant;

    // Calculate the U parameter of the intersection point.
    Vector3f distanceVector = null;
    distanceVector = Vector3f.sub(R.Position, vertex1, distanceVector);


    float triangleU = Vector3f.dot(directionCrossEdge2, distanceVector);
    triangleU *= inverseDeterminant;

    // Make sure the U is inside the triangle.
    if (triangleU < 0 || triangleU > 1) {
        return Float.MAX_VALUE;
    }

    // Calculate the V parameter of the intersection point.
    Vector3f distanceCrossEdge1 = null;
    distanceCrossEdge1 = Vector3f.cross(distanceVector, edge1, distanceCrossEdge1);


    float triangleV = Vector3f.dot(R.Direction, distanceCrossEdge1);
    triangleV *= inverseDeterminant;

    // Make sure the V is inside the triangle.
    if (triangleV < 0 || triangleU + triangleV > 1) {
        return Float.MAX_VALUE;
    }

    // Get the distance to the face from our ray origin
    float rayDistance = Vector3f.dot(distanceCrossEdge1, edge2);
    rayDistance *= inverseDeterminant;


    // Is the triangle behind us?
    if (rayDistance < 0) {
        rayDistance *= -1;
        return Float.MAX_VALUE;
    }
    return rayDistance;
}

The triangle with the shortest distance is the picked triangle. Also, shameless plug for my game, you should check it out, follow it and vote in the polls I put out occasionally. Thanks! http://byte56.com

Answer 2

The technique you're looking for is called "picking" or "3D picking." There are several ways to do it; one of the more common ones is to transform a 2D point on the screen into eye space by using the inverse of the projection transformation. This will allow you to generate a ray in view space, which you can use to test for collision with the physical representation of your various bits of scene geometry to determine which object the user 'hit.'

You can also use a "picking buffer" (or "selection buffer") which GL has support for. This basically involves writing some unique object identifier into a buffer for every pixel and then simply testing that buffer.

The OpenGL FAQ has brief discussions on both (it focuses more on the selection buffer since that's entirely a GL feature; ray picking is API agnostic except perhaps for extracting the active matrices from the pipeline). Here is a more specific example of the ray picking technique (for iOS, but it should translate easily enough). This site has some source code to some of the OpenGL Red Book examples ported to LWJGL, which include a picking demo.

See also this question on SO.