Finding object under mouse

Question

I'm developing a game that basically has its entire terrain made out of AABB boxes. I know the verticies, minimum, and maximum of each box. I also set up my camera like this:

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

What I'm trying to do is basically find the cube the mouse is on. I thought about giving the mouse position a forward directional vector and simply iterating through until the 'mouse bullet' hits something. However this envolves interating through all objects several times. Is there a way I could do it by only iterating through all the objects once?

Thanks

Answer 1

This is called Ray Tracing (oops, my mistake, it's actually Ray Casting). Every Physics engine has this functionality. You can look at one of the simplest - ODE, or it's derivative - Bullet. They are open-source so you can take out what you don't need. They both have a handy math library that handles all oftenly needed matrix and vertex operations. They all have demos on how to do exactly this task.

Answer 2

This is usually referred to as 'picking' This here looks like a good gl based link

If that is tldr, then a basic algorithm you could use

1. sort objects by z (or keep them sorted by z, or depth buffer tricks etc)
2. iterate and do a bounds test, stopping when you hit the first one.

Answer 3

There's a lot of information on hit testing in OpenGL over in the OpenGL FAQ

Answer 4

I suggest you consider looking at this issue from a bigger perspective.

The boxes are just points at a lower resolution. The trick is to reduce the resolution of the mouse to figure out which box it is on.

You may have to perform a 2d to 3d conversion (or vice versa). In most games, the mouse lives in a 2d coordinate world. The stuff "under" the mouse is a 2d projection of a 3d universe.

Answer 5

You want to use a 3D picking algorithm. The idea is that you draw a ray from the user's position in the virtual world in the direction of the click. This blog post explains very clearly how to implement such an algorithm. Essentially your screen coordinates need to be transformed from the screen space to the virtual world space. There's a website that has a very good description about the various transformations involved and I can't post the link due to my rank. Search for book of hook's mouse picking algorithm [I do not own the site and I haven't authored the document].

Once you get a ray in the desired direction, you need to perform tests for intersection with the geometries in the real world. Since you have AABB boxes entirely, you can use simple vector equations to check which geometry intersects the ray. I would say that approximating your boxes as a sphere would make life very easy since there is a very simple sphere-ray intersection test. So, your ray would be described by what you obtain from the first step (the ray drawn in the first step) and then you would need to use an intersection test. If you're ok with using spheres, the center of the sphere would be the point you draw your box and the diameter would be the width of your box.

Good Luck!