Picking in 3D space

Picking in 2D is a one-liner: the mouse is inside the rectangle or it is not. In 3D the mouse is a pixel on an image, and the image is only a projection of the scene. Which object sits under that pixel is written down nowhere. You can't ask the picture, you have to look in the scene itself.

The demo has seven objects on a floor: cubes, boxes and spheres. Move the mouse over them: the object you hit gets an orange outline, and the panel on the right shows its name, the distance t and the hit point in world coordinates. A click selects it. Dragging the background (or the right mouse button) orbits the camera, the wheel zooms. The box on the right shows the same scene from above, with the camera, its field of view and the ray that currently sits under the mouse.

Everything is drawn in software with my own 4x4 matrices, and the triangles go out through SDL_RenderGeometry.

From pixel to ray

A pixel gives you a line: everything that falls through that pixel as seen from the camera. You only get a point once you add a depth. So you calculate backwards. Pixel x and y become NDC coordinates between -1 and 1 (y flips on the way, pixels count downwards, NDC counts upwards), plus a depth: -1 is the near plane, 1 the far plane. Then you multiply by the inverse of projection times view and divide by w:

const float nx = (px - vp.x) / vp.w * 2.0F - 1.0F;
const float ny = 1.0F - (py - vp.y) / vp.h * 2.0F;
const Vec4 c = invViewProj * Vec4{nx, ny, ndcZ, 1.0F};
return {c.x / c.w, c.y / c.w, c.z / c.w};

Two points are enough, one with depth -1 and one with depth 1. Both lie on the ray, their difference is the direction. For the origin I take the camera position, which makes t a real distance in the world later:

const Vec3 nearPoint = unproject(invViewProj, vp, px, py, -1.0F);
const Vec3 farPoint = unproject(invViewProj, vp, px, py, 1.0F);
return Ray{eye, normalize(farPoint - nearPoint)};

A test checks this as a round trip: a world point goes through project to pixel plus depth and back through unproject, and the original point has to come out. The tolerance is 0.002, which is all a float gives you with a far plane at 100. On top of that two cases I worked out by hand beforehand: the ray through the middle of the viewport has to point exactly along the view direction, and with a 90 degree field of view the ray through the top left corner points along (-1, 1, -1), normalized.

Ray against sphere and box

For the sphere you put origin + t * dir into the sphere equation and get a quadratic in t. A negative discriminant means the ray misses. Otherwise there are two solutions, entry and exit. If even the exit is behind the origin, the sphere is behind the camera:

const Vec3 oc = ray.origin - center;
const float a = dot(ray.dir, ray.dir);
const float halfB = dot(oc, ray.dir);
const float c = dot(oc, oc) - radius * radius;
const float disc = halfB * halfB - a * c;
if (disc < 0.0F) return std::nullopt;
const float root = std::sqrt(disc);
const float far = (-halfB + root) / a;
if (far < 0.0F) return std::nullopt;
return std::max((-halfB - root) / a, 0.0F);

For the box I use the slab method. An axis-aligned box is the intersection of three slabs, one per axis. For each axis you work out at which t the ray enters and leaves that slab. The box is hit when the three intervals overlap, meaning the largest entry is not behind the smallest exit:

for (int i = 0; i < 3; ++i) {
    if (std::fabs(d[i]) < 1e-8F) {
        if (o[i] < mn[i] || o[i] > mx[i]) return std::nullopt;
        continue;
    }
    float t1 = (mn[i] - o[i]) / d[i];
    float t2 = (mx[i] - o[i]) / d[i];
    if (t1 > t2) std::swap(t1, t2);
    tMin = std::max(tMin, t1);
    tMax = std::min(tMax, t2);
    if (tMin > tMax) return std::nullopt;
}
return tMin;

tMin starts at 0. That cuts off everything behind the origin, and a ray that starts inside the box gets t = 0. That is my own convention, other implementations return the exit point there.

The nearest hit wins

Every object returns a t or nothing, the smallest one wins. The floor is a plane at y = 0 and enters as one more candidate:

for (std::size_t i = 0; i < objects.size(); ++i) {
    const auto t = intersect(ray, objects[i]);
    if (t && (!best || *t < best->t)) best = Pick{static_cast<int>(i), false, *t};
}
const auto floorT = rayPlane(ray, {0, 0, 0}, {0, 1, 0});
if (floorT && (!best || *floorT < best->t)) best = Pick{-1, true, *floorT};

The test puts the far sphere first in the list on purpose, so a "first hit wins" bug shows up. The spheres are hit mathematically, not the 320 triangles you see. In the middle of a face the triangles sit 1.5 to 2 percent below the true sphere surface. At the edge of a sphere the ray therefore hits a little outside the drawn outline, and you won't notice.

Pitfalls

The y axis flips between pixel and NDC. Forget the flip and the mouse picks at the top whatever lies at the bottom.

When the ray runs parallel to an axis, that direction component is 0 and the division blows up. The case is handled up front: if the origin lies inside that slab the axis is ignored, otherwise it is a miss. The edge case, origin exactly on the slab boundary, counts as inside and has its own test.

The direction needs length 1, otherwise t is no longer a distance. pixelToRay normalizes it, the tests assume it.

And then there is drawing, which has nothing to do with picking. I sort the objects by the distance of their center and draw back to front. That only works because nothing intersects (a test checks that), overlapping objects would show errors. Lines that reach behind the camera would land mirrored on the screen, so the grid and the floor get cut at the near plane, in clipNear.

The code is in the repo under picking-3d. All demos of the series are collected in the project Game Dev Snippets.