Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I have written some code to preform 3D picking that for some reason dosn't work entirely correct! (Im using LWJGL just so you know.)

I posted this at stackoverflow at first but after researching some more in to my problem i found this neat site and tought that you guys might be more qualified to answer this question.

This is how the code looks like:

if(Mouse.getEventButton() == 1) {
  if (!Mouse.getEventButtonState()) {
    Camera.get().generateViewMatrix();

    float screenSpaceX = ((Mouse.getX()/800f/2f)-1.0f)*Camera.get().getAspectRatio();
    float screenSpaceY = 1.0f-(2*((600-Mouse.getY())/600f));
    float displacementRate = (float)Math.tan(Camera.get().getFovy()/2);

    screenSpaceX *= displacementRate;
    screenSpaceY *= displacementRate;

    Vector4f cameraSpaceNear = new Vector4f((float) (screenSpaceX * Camera.get().getNear()), (float) (screenSpaceY * Camera.get().getNear()), (float) (-Camera.get().getNear()), 1);
    Vector4f cameraSpaceFar = new Vector4f((float) (screenSpaceX * Camera.get().getFar()), (float) (screenSpaceY * Camera.get().getFar()), (float) (-Camera.get().getFar()), 1);

    Matrix4f tmpView = new Matrix4f();
    Camera.get().getViewMatrix().transpose(tmpView);
    Matrix4f invertedViewMatrix = (Matrix4f)tmpView.invert();

    Vector4f worldSpaceNear = new Vector4f();
    Matrix4f.transform(invertedViewMatrix, cameraSpaceNear, worldSpaceNear);

    Vector4f worldSpaceFar = new Vector4f();
    Matrix4f.transform(invertedViewMatrix, cameraSpaceFar, worldSpaceFar);


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

    Ray clickRay = new Ray(rayPosition, rayDirection);

    Vector tMin = new Vector(), tMax = new Vector(), tempPoint;
    float largestEnteringValue, smallestExitingValue, temp, closestEnteringValue = Camera.get().getFar()+0.1f;
    Drawable closestDrawableHit = null;
    for(Drawable d : this.worldModel.getDrawableThings()) {
        // Calcualte AABB for each object... needs to be moved later...
        firstVertex = true;
        for(Surface surface : d.getSurfaces()) {
            for(Vertex v : surface.getVertices()) {
                worldPosition.x = (v.x+d.getPosition().x)*d.getScale().x;
                worldPosition.y = (v.y+d.getPosition().y)*d.getScale().y;
                worldPosition.z = (v.z+d.getPosition().z)*d.getScale().z;
                worldPosition = worldPosition.rotate(d.getRotation());
                if (firstVertex) {
                    maxX = worldPosition.x; maxY = worldPosition.y; maxZ = worldPosition.z;
                    minX = worldPosition.x; minY = worldPosition.y; minZ = worldPosition.z;
                    firstVertex = false;
                } else {
                    if (worldPosition.x > maxX) {
                        maxX = worldPosition.x;
                    }
                    if (worldPosition.x < minX) {
                        minX = worldPosition.x;
                    }
                    if (worldPosition.y > maxY) {
                        maxY = worldPosition.y;
                    }
                    if (worldPosition.y < minY) {
                        minY = worldPosition.y;
                    }
                    if (worldPosition.z > maxZ) {
                        maxZ = worldPosition.z;
                    }
                    if (worldPosition.z < minZ) {
                        minZ = worldPosition.z;
                    }
                }
            }
        }

        // ray/slabs intersection test...


        // clickRay.getOrigin().x + clickRay.getDirection().x * f = minX
        // clickRay.getOrigin().x - minX = -clickRay.getDirection().x * f
        // clickRay.getOrigin().x/-clickRay.getDirection().x - minX/-clickRay.getDirection().x = f
        // -clickRay.getOrigin().x/clickRay.getDirection().x + minX/clickRay.getDirection().x = f


        largestEnteringValue = -clickRay.getOrigin().x/clickRay.getDirection().x + minX/clickRay.getDirection().x;
        temp = -clickRay.getOrigin().y/clickRay.getDirection().y + minY/clickRay.getDirection().y;
        if(largestEnteringValue < temp) {
            largestEnteringValue = temp;
        }
        temp = -clickRay.getOrigin().z/clickRay.getDirection().z + minZ/clickRay.getDirection().z;
        if(largestEnteringValue < temp) {
            largestEnteringValue = temp;
        }

        smallestExitingValue = -clickRay.getOrigin().x/clickRay.getDirection().x + maxX/clickRay.getDirection().x;
        temp = -clickRay.getOrigin().y/clickRay.getDirection().y + maxY/clickRay.getDirection().y;
        if(smallestExitingValue > temp) {
            smallestExitingValue = temp;
        }
        temp = -clickRay.getOrigin().z/clickRay.getDirection().z + maxZ/clickRay.getDirection().z;
        if(smallestExitingValue < temp) {
            smallestExitingValue = temp;
        }


            if(largestEnteringValue > smallestExitingValue) {
                //System.out.println("Miss!");
            } else {
                if (largestEnteringValue < closestEnteringValue) {
                    closestEnteringValue = largestEnteringValue;
                    closestDrawableHit = d;
                }
            }

    }
    if(closestDrawableHit != null) {
        System.out.println("Hit at: (" + clickRay.setDistance(closestEnteringValue).x + ", " + clickRay.getCurrentPosition().y + ", " + clickRay.getCurrentPosition().z);
        this.worldModel.removeDrawableThing(closestDrawableHit);    
    }
  }
}

I just don't understand what's wrong, the ray are shooting and i do hit stuff that gets removed but the result of the ray are verry strange it sometimes removes the thing im clicking at, sometimes it removes things thats not even close to what im clicking at, and sometimes it removes nothing at all.

Edit:

Okay so i have continued searching for errors and by debugging the ray (by painting smal dots where it travles) i can now se that there is something oviously wrong with the ray that im sending out... it has its origin near the world center (nearer or further away depending on where on the screen im clicking) and always shots to the same position no matter where I direct my camera...

My initial toughts is that there might be some error in the way i calculate my viewMatrix (since it's not possible to get the viewmatrix from the gluLookAt method in lwjgl; I have to build it my self and I guess thats where the problem is at)...

Edit2:

This is how i calculate it currently:

private double[][] viewMatrixDouble = {{0,0,0,0}, {0,0,0,0}, {0,0,0,0}, {0,0,0,1}};

public Vector getCameraDirectionVector() {
    Vector actualEye = this.getActualEyePosition();
    return new Vector(lookAt.x-actualEye.x, lookAt.y-actualEye.y, lookAt.z-actualEye.z);
}

public Vector getActualEyePosition() {
    return eye.rotate(this.getRotation());
}

public void generateViewMatrix() {

    Vector cameraDirectionVector = getCameraDirectionVector().normalize();
    Vector side = Vector.cross(cameraDirectionVector, this.upVector).normalize();
    Vector up = Vector.cross(side, cameraDirectionVector);

    viewMatrixDouble[0][0] = side.x;                    viewMatrixDouble[0][1] = up.x;                  viewMatrixDouble[0][2] = -cameraDirectionVector.x;                 
    viewMatrixDouble[1][0] = side.y;                    viewMatrixDouble[1][1] = up.y;                  viewMatrixDouble[1][2] = -cameraDirectionVector.y;                 
    viewMatrixDouble[2][0] = side.z;                    viewMatrixDouble[2][1] = up.z;                  viewMatrixDouble[2][2] = -cameraDirectionVector.z;                 


    /*
    Vector actualEyePosition = this.getActualEyePosition();
    Vector zaxis = new Vector(this.lookAt.x - actualEyePosition.x, this.lookAt.y - actualEyePosition.y, this.lookAt.z - actualEyePosition.z).normalize();
    Vector xaxis = Vector.cross(upVector, zaxis).normalize();
    Vector yaxis = Vector.cross(zaxis, xaxis);
    viewMatrixDouble[0][0] = xaxis.x;                   viewMatrixDouble[0][1] = yaxis.x;                   viewMatrixDouble[0][2] = zaxis.x;                  
    viewMatrixDouble[1][0] = xaxis.y;                   viewMatrixDouble[1][1] = yaxis.y;                   viewMatrixDouble[1][2] = zaxis.y;                  
    viewMatrixDouble[2][0] = xaxis.z;                   viewMatrixDouble[2][1] = yaxis.z;                   viewMatrixDouble[2][2] = zaxis.z;                  
    viewMatrixDouble[3][0] = -Vector.dot(xaxis, actualEyePosition); viewMatrixDouble[3][1] =-Vector.dot(yaxis, actualEyePosition);  viewMatrixDouble[3][2] = -Vector.dot(zaxis, actualEyePosition);
    */
    viewMatrix = new Matrix4f();
    viewMatrix.load(getViewMatrixAsFloatBuffer());
}

Would be verry greatfull if anyone could verify if this is wrong or right, and if it's wrong; supply me with the right way of doing it... I have read alot of threads and documentations about this but i can't seam to wrapp my head around it...

Edit3:

Okay with the help of Byte56 (thanks alot for the help) i have now concluded that it's not the viewMatrix that is the problem... I still get the same messedup result; anyone that think that they can find the error in my code, i certenly can't, have bean working on this for 3 days now :(

share|improve this question

3 Answers 3

I wrote an answer on this before for picking within a 3D game, using LWJGL. You should see if the answer here is useful to you.

And as for your camera's view matrix, you can generate it with something like the following code:

Matrix4f CreateView(Vector3f position, Vector3f direction, Vector3f up) {
    Vector3f rightVector = new Vector3f();
    Vector3f.cross(up, direction, rightVector);
    rightVector = (Vector3f) rightVector.normalize();
    Matrix4f result = new Matrix4f();
    result.m00 = rightVector.x;
    result.m10 = rightVector.y;
    result.m20 = rightVector.z;
    result.m30 = -(Vector3f.dot(rightVector, position));

    result.m01 = up.x;
    result.m11 = up.y;
    result.m21 = up.z;
    result.m31 = -(Vector3f.dot(up, position));

    result.m02 = direction.x;
    result.m12 = direction.y;
    result.m22 = direction.z;
    result.m32 = -(Vector3f.dot(direction, position));

    return result;
}

Where the up vector and direction vector are both normalized.

This looks like you're doing the same thing. I'd take a look your code here:

viewMatrix.load(getViewMatrixAsFloatBuffer());

Make sure it's doing what you think it should be. I put my matrix into a float buffer like so:

public static FloatBuffer MatrixToFloatBuffer(Matrix4f matrix) {
    FloatBuffer fb = BufferUtils.createFloatBuffer(16);
    int i = 0;
    fb.put(i++, matrix.m00);
    fb.put(i++, matrix.m01);
    fb.put(i++, matrix.m02);
    fb.put(i++, matrix.m03);
    fb.put(i++, matrix.m10);
    fb.put(i++, matrix.m11);
    fb.put(i++, matrix.m12);
    fb.put(i++, matrix.m13);
    fb.put(i++, matrix.m20);
    fb.put(i++, matrix.m21);
    fb.put(i++, matrix.m22);
    fb.put(i++, matrix.m23);
    fb.put(i++, matrix.m30);
    fb.put(i++, matrix.m31);
    fb.put(i++, matrix.m32);
    fb.put(i++, matrix.m33);
    return fb;
}

So after generating my view matrix, I can load it like so:

glLoadMatrix(WorldCamera.MatrixToFloatBuffer(WORLD.Camera.view));

Also check your "up" and "side" vectors to ensure they are correct.

share|improve this answer
    
Hi Byte56, thanks for the reply! I have indeed taken a close look at that code and i think that if you take a closer look on the top part of my code you will see that alot of it is practicly identical. It helped me alot, thanks! Tough my current problem seams to lie somewhere else, may i ask you how your calculations for your view matrix looks like? –  Wirde Jan 3 '12 at 23:59
    
Ah great, glad I've helped at least a little already! I will post the calculations for the view matrix. Also, remember to vote up the other LWJGL answer if it was useful ;) –  Byte56 Jan 4 '12 at 0:15
    
Would definetly do it if i could :/ I'm new to gamedev so i can't vote up yet. But i will select your answer as accepted if it solves my problem :) –  Wirde Jan 4 '12 at 0:34
    
Do you think i can send you my code so you can test the program an se if you know what the problem is? You seam to be verry knowledgeable in the 3d-picking area, and you have already proven verry helpfull! I would be eternaly grateful ^^ –  Wirde Jan 4 '12 at 1:02
    
Actually this is the perfect opportunity for you to build up your debugging skills. Set break points, draw lines in game to represent your different vectors, do the math on paper to ensure you've done it correctly in your program. If you have to, use the debugger to step through your code line by line from when you click the mouse until it returns an clicked object. I'd rob you of all those valuable lessons if I just looked at your code! –  Byte56 Jan 4 '12 at 1:36
up vote 0 down vote accepted

Okay so i finaly managed to solve this with the help of @Byte56 and a friend of mine.

Here is the result, it's is a litle bit buggy but it works reasonably well :D

It also contains my algorithm for Ray / AABB intersection test, tought it might help someone that are doing this in the future...

while(Mouse.next()) {
if(Mouse.getEventButton() == 1) {
    if (!Mouse.getEventButtonState()) {
    Camera.get().generateViewMatrix();

    float screenSpaceX = ((2*Mouse.getX()/800f)-1.0f)*Camera.get().getAspectRatio();
    float screenSpaceY = ((2*Mouse.getY()/600f)-1.0f);
    float displacementRate = (float)Math.tan(Math.toRadians(Camera.get().getFovy()/2));

    screenSpaceX *= displacementRate;
    screenSpaceY *= displacementRate;

    Vector4f cameraSpaceNear = new Vector4f((float) (screenSpaceX * Camera.get().getNear()), (float) (screenSpaceY * Camera.get().getNear()), (float) (-Camera.get().getNear()), 1);
    Vector4f cameraSpaceFar = new Vector4f((float) (screenSpaceX * Camera.get().getFar()), (float) (screenSpaceY * Camera.get().getFar()), (float) (-Camera.get().getFar()), 1);

    Matrix4f tmpView = new Matrix4f().load(Camera.get().getViewMatrix());

    Matrix4f invertedViewMatrix = (Matrix4f)tmpView.invert();

    Vector4f worldSpaceNear = new Vector4f();
                    Matrix4f.transform(invertedViewMatrix, cameraSpaceNear, worldSpaceNear);

    Vector4f worldSpaceFar = new Vector4f();
    Matrix4f.transform(invertedViewMatrix, cameraSpaceFar, worldSpaceFar);


    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 = new Vector(rayDirection).rotateX(-Camera.get().getRotation().x).rotateY(-Camera.get().getRotation().y).rotateZ(-Camera.get().getRotation().z).to3f();

    rayDirection.normalise();

    rayPosition.z = -rayPosition.z;
    // TODO: origin is a little bit off.... probably has to do with the Camera.get().getActualEyePosition....
    Ray clickRay = new Ray(rayPosition, rayDirection);

    /* Debugg to se where the rays shoot from/at: */                        
    /*
    this.worldModel.addDrawableThing(new StageObject("smallGrassPlate", new Vector(clickRay.getOrigin().x, clickRay.getOrigin().y,clickRay.getOrigin().z), new Vector(), new Vector(0.3f, 0.3f, 0.3f)));    
                    for(float f = Camera.get().getNear(); f < Camera.get().getFar(); f += 1f) {
                        this.worldModel.addDrawableThing(new StageObject("cube", new Vector(clickRay.setDistance(f).x, clickRay.getCurrentPosition().y,clickRay.getCurrentPosition().z), new Vector(), new Vector(0.3f, 0.3f, 0.3f)));
                    }
    */                      
    float largestEnteringValue, smallestExitingValue, temp1, temp2, closestEnteringValue = Camera.get().getFar()+0.1f;
    Drawable closestDrawableHit = null;

    for(Drawable d : this.worldModel.getDrawableThings()) {
        // Calcualte AABB for each object... needs to be moved later...
        firstVertex = true;
        for(Surface surface : d.getSurfaces()) {
            for(Vertex v : surface.getVertices()) {
                worldPosition.x = (v.x+d.getPosition().x)*d.getScale().x;
                worldPosition.y = (v.y+d.getPosition().y)*d.getScale().y;
                worldPosition.z = (v.z+d.getPosition().z)*d.getScale().z;
                worldPosition = worldPosition.rotate(d.getRotation());
                if (firstVertex) {
                    maxX = worldPosition.x; maxY = worldPosition.y; maxZ = worldPosition.z;
                    minX = worldPosition.x; minY = worldPosition.y; minZ = worldPosition.z;
                    firstVertex = false;
                } else {
                    if (worldPosition.x > maxX) {
                        maxX = worldPosition.x;
                    }
                    if (worldPosition.x < minX) {
                        minX = worldPosition.x;
                    }
                    if (worldPosition.y > maxY) {
                        maxY = worldPosition.y;
                    }
                    if (worldPosition.y < minY) {
                        minY = worldPosition.y;
                    }
                    if (worldPosition.z > maxZ) {
                        maxZ = worldPosition.z;
                    }
                    if (worldPosition.z < minZ) {
                        minZ = worldPosition.z;
                    }
                }
            }
        }

        // ray/slabs intersection test...


        // clickRay.getOrigin().x + clickRay.getDirection().x * f = minX
        // clickRay.getOrigin().x - minX = -clickRay.getDirection().x * f
        // clickRay.getOrigin().x/-clickRay.getDirection().x - minX/-clickRay.getDirection().x = f
        // -clickRay.getOrigin().x/clickRay.getDirection().x + minX/clickRay.getDirection().x = f
        // (minX - clickRay.getOrigin.x) / clickRay.getDirection().x = f

        // TODO: Fix something better here...
        if (clickRay.getDirection().x == 0 || clickRay.getDirection().y == 0) {
            System.out.println("Nu stötte vi på 0 i division!");
            System.exit(1);
        }
        temp1 = (minX - clickRay.getOrigin().x)/clickRay.getDirection().x;
        temp2 = (maxX - clickRay.getOrigin().x)/clickRay.getDirection().x;

        if (temp2 > temp1) {
            largestEnteringValue = temp1;
            smallestExitingValue = temp2;
        } else {
            largestEnteringValue = temp2;
            smallestExitingValue = temp1;
        }

        temp1 = (minY - clickRay.getOrigin().y)/clickRay.getDirection().y;
        temp2 = (maxY - clickRay.getOrigin().y)/clickRay.getDirection().y;
        if (temp2 > temp1) {
            if (largestEnteringValue < temp1 ) {
                largestEnteringValue = temp1;
            }
            if (smallestExitingValue > temp2) {
                smallestExitingValue = temp2;
            }
        } else {
            if (largestEnteringValue < temp2 ) {
                largestEnteringValue = temp2;
            }
            if (smallestExitingValue > temp1) {
                smallestExitingValue = temp1;
            }                       
        }

        temp1 = (minZ - clickRay.getOrigin().z)/clickRay.getDirection().z;
        temp2 = (maxZ - clickRay.getOrigin().z)/clickRay.getDirection().z;
        if (temp2 > temp1) {
            if (largestEnteringValue < temp1 ) {
                largestEnteringValue = temp1;
            }
            if (smallestExitingValue > temp2) {
                smallestExitingValue = temp2;
            }
        } else {
            if (largestEnteringValue < temp2 ) {
                largestEnteringValue = temp2;
            }
            if (smallestExitingValue > temp1) {
                smallestExitingValue = temp1;
            }                       
        }

        if(largestEnteringValue <= smallestExitingValue) {
            if (largestEnteringValue < closestEnteringValue) {
                closestEnteringValue = largestEnteringValue;
                closestDrawableHit = d;
            }
        }

    }
    if(closestDrawableHit != null) {
        this.worldModel.removeDrawableThing(closestDrawableHit);    
    }
}
}

And this code is in my camera class for generating view matrix:

public Vector getActualEyePosition() {
    Vector rotatedEye = eye.clone();
    rotatedEye.x -= lookAt.x*2;
    rotatedEye.y -= lookAt.y*2;
    rotatedEye.z -= lookAt.z*2;
    rotatedEye = rotatedEye.rotate(this.getRotation());
    return new Vector(-rotatedEye.x, -rotatedEye.y, rotatedEye.z);
}

public void generateViewMatrix() {
    Vector actualEye = this.getActualEyePosition();
    Vector3f forward;
    Vector3f side = new Vector3f();
    Vector3f up;
    forward = new Vector3f(lookAt.x - eye.x, lookAt.y - eye.y, lookAt.z - eye.z);

    up = upVector.to3f();

    forward.normalise();

    /* Side = forward x up */
    Vector3f.cross(forward, up, side);
    side.normalise();

    /* Recompute up as: up = side x forward */
    Vector3f.cross(side, forward, up);

    viewMatrix.m00 = side.x;
    viewMatrix.m10 = side.y;
    viewMatrix.m20 = side.z;
    viewMatrix.m30 = -(Vector3f.dot(side, actualEye.to3f()));

    viewMatrix.m01 = up.x;
    viewMatrix.m11 = up.y;
    viewMatrix.m21 = up.z;
    viewMatrix.m31 = -(Vector3f.dot(up, actualEye.to3f()));

    viewMatrix.m02 = -forward.x;
    viewMatrix.m12 = -forward.y;
    viewMatrix.m22 = -forward.z;
    viewMatrix.m32 = -(Vector3f.dot(forward, actualEye.to3f()));
}

I want to point out that there are 2 types of vectors here the first is my own "Vector" and the other one is lwjgls "Vector3f".

Hope this helps any one thats having the same problems as I had and that it dosn't take them 5 days to fix this :D

share|improve this answer

I recently attempted to implement picking, and this thread was invaluable in getting things to work. One problem that I ran into though is that I don't think that the accepted answer generates the right view matrix in all cases. Let me suggest an alternative for obtaining it, which is much simpler and more likely to be right - it just pulls the matrix straight out of OpenGL.

Unfortunately the code is written in Scala so you may have to tweak it a little bit to get it to work in Java, but there should only be minor differences.

  def storeViewMat() = {
    viewMatrix = new Matrix4f()
    var buf: FloatBuffer = BufferUtils.createFloatBuffer(16 * 4)

    // Get your current model view matrix from OpenGL.
    glGetFloat(GL_MODELVIEW_MATRIX, buf)

    // rewind the buffer
    buf.rewind()

    viewMatrix.m00 = buf.get(0)
    viewMatrix.m01 = buf.get(1)
    viewMatrix.m02 = buf.get(2)
    viewMatrix.m03 = buf.get(3)

    viewMatrix.m10 = buf.get(4)
    viewMatrix.m11 = buf.get(5)
    viewMatrix.m12 = buf.get(6)
    viewMatrix.m13 = buf.get(7)

    viewMatrix.m20 = buf.get(8)
    viewMatrix.m21 = buf.get(9)
    viewMatrix.m22 = buf.get(10)
    viewMatrix.m23 = buf.get(11)

    viewMatrix.m30 = buf.get(12)
    viewMatrix.m31 = buf.get(13)
    viewMatrix.m32 = buf.get(14)
    viewMatrix.m33 = buf.get(15)
  }

This code will store the view matrix inside a Matrix4f named viewMatrix. I hope this helps anyone who comes across this thread in the future!

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.