Picking

From DmWiki

The idea behind picking is being able to click on a point inside your client area and select an object that appears at that position. In order to find out which objects appear at a given screen location, you have to cast a ray through 3D space. The ray starts at the camera location and "goes through" the pixel that was clicked on, then continues on through the scene.

After you have your ray, the next step is to check if the ray is hitting an object. Now most objects' vertices are in local coordinates, so you can't really test a ray that's in world space with those vertices. What you'll have to do is transform the ray into local coordinates (which is a straightforward process, as you will see in a minute).

The following is what you'll need:

1. The projection matrix, so that you can transform the pixel from screen space into a ray in eye space
2. The world-to-eye matrix (view matrix) so that you can transform the ray from eye space to world space
3. The local-to-world matrix of each object, so that you can transform the ray from world to local coordinates

First, you can construct the ray in eye space:

Point2D p = GetMouseClickPoint();

Vector RayPos = (0, 0, 0, 1);
Vector RayDir;
RayDir.x =  (2 * p.x / Screen.Width - 1) / ProjMatrix[0][0];
RayDir.y = -(2 * p.y / Screen.Height - 1) / ProjMatrix[1][1];
RayDir.z = 1;
RayDir.w = 0;

If you are using OpenGL, you should set RayDir.z = -1 instead.

The next step is to take this ray, which is in eye space, and transform it into world space. To do this, you use the inverse of the world-to-eye matrix (see vectors and matrices).

InvViewMatrix = InverseOf( ViewMatrix );
RayPos = InvViewMatrix * RayPos;
RayDir = InvViewMatrix * RayDir;

Finally, for each object that you want to test against the ray, you use the inverse of the local-to-world matrix to transform the ray into that object's local coordinate system.

for (each object) {
    InvLocalToWorldMatrix = InverseOf( LocalToWorldMatrix );
    Vector localRayPos = InvLocalToWorldMatrix * RayPos;
    Vector localRayDir = InvLocalToWorldMatrix * RayDir;
    TestRayAgainstObject(RayPos, RayDir);
}

To test a ray against an object, see ray-triangle intersection. Note that if you have more than a few dozen triangles in your scene, you probably do not want to test the ray against all of them! This could be very slow. Instead, use bounding volumes, a BSP tree, an octree, or some other system to reduce the number of triangles you actually have to check.