Object under mouse?

Question

My little game engine basically has a 3D array Cubes[x][y][z] (its actually a big 1D array but I'v done some overloading). I know which cube in X Y Z that the player is standing on. The player will be able to shoot a cube to destroy it which is why I need to figure out how to find the Cube that the mouse is under. I found some OpenGL documentation on picking, but this method was slow. Since my cubes are organized and I know which cube the player is on, and the camera's angle in X and Y (camera does not rotate on Z), and that the mouse is always at screenwidth / 2, screenheight / 2 I'm sure theres a faster way than the gl picking technique.

Here is how the camera is set up:

void CCubeGame::SetCameraMatrix()
{

    glMatrixMode(GL_MODELVIEW);
    glLoadIdentity();

    glRotatef(Camera.rotx,1,0,0);
    glRotatef(Camera.roty,0,1,0);
    glRotatef(Camera.rotz,0,0,1);

    glTranslatef(-Camera.x , -Camera.y,-Camera.z );
}

void CCubeGame::MouseMove(int x, int y)
{
    if(!isTrapped)
        return;

    int diffx = x-lastMouse.x; 
    int diffy = y-lastMouse.y; 

    lastMouse.x = x; 
    lastMouse.y = y;
    Camera.rotx += (float) diffy * 0.2; 
    Camera.roty += (float) diffx * 0.2; 
    if(Camera.rotx > 90)
    {
        Camera.rotx = 90;
    }

    if(Camera.rotx < -90)
    {
        Camera.rotx = -90;
    }

    if(isTrapped)
    if (fabs(ScreenDimensions.x/2 - x) > 1 || fabs(ScreenDimensions.y/2 - y) > 1) {
        resetPointer();
    }

}

Vertex3f CCubeGame::MoveCamera( int direction, float amount )
{
    float xrotrad, yrotrad;
    Vertex3f result(0,0,0);

    switch(direction)
    {
    case CAM_FORWARD:
        yrotrad = (Camera.roty / 180 * 3.141592654f);
        xrotrad = (Camera.rotx / 180 * 3.141592654f);

        result.x = float(sin(yrotrad)) * amount;
        result.z = -(float(cos(yrotrad)) * amount);
        result.y = 0;
        //Camera.y -= float(sin(xrotrad)) * amount;
        break;
    case CAM_BACKWARD:
        yrotrad = (Camera.roty / 180 * 3.141592654f);
        xrotrad = (Camera.rotx / 180 * 3.141592654f);
        result.x = -(float(sin(yrotrad)) * amount);
        result.z = float(cos(yrotrad)) * amount;
        result.y = 0;

        //Camera.y += float(sin(xrotrad)) * amount;
        break;
    case CAM_RIGHT:
        yrotrad = (Camera.roty / 180 * 3.141592654f);
        result.x = float(cos(yrotrad)) * amount;
        result.z += float(sin(yrotrad)) * amount;
        result.y = 0;
        break;
    case CAM_LEFT:
        yrotrad = (Camera.roty / 180 * 3.141592654f);
        result.x = -(float(cos(yrotrad)) * amount);
        result.z = -(float(sin(yrotrad)) * amount);
        result.y = 0;
        break;
    default:
        break;
    }

    Camera.x += result.x;
    Camera.y += result.y;
    Camera.z += result.z;

    return result;

}

Thanks

Answer 1

If you can't rotate in Z, then you can only shoot a cube at the same Z height that the gun is at. This makes things a lot simpler because you can sort your cubes by Z and throw away any that are too high or too low (this will take log(N) time in the number of cubes if they can be at fractional heights; if they're all the same height and all at the same height as each other, you just index into that portion of the array).

Now you need to draw a line from the gun through the grid and find out which cube it hits first. The way to do this is with a vector along the line of the gun:

v = (cos(angle), sin(angle))

and find each boundary where that line crosses an integer in either X or Y. If we are at

(x0,y0)

to start with and travel in direction v then we will hit (assuming cos(angle) > 0)

ceil(x0), ceil(x0+1), ...

at times

(ceil(x0)-x0)/cos(angle), (ceil(x1)-x1)/cos(angle), ...

and similarly for y0 and sin(angle). Now you just walk down the list of times--which will take you into a new square--and the first time you encounter a cube, you hit it.

If the cube array is not gigantic, this whole thing should take only a few microseconds on a decent processor (maybe a few hundred or so on an embedded processor).