Picking

I've been porting muRay over to Processing recently and have been stuck in the camera code. Every raytracer has methods to generate rays from the camera into space. In backwards raytracing, the algorithm starts with a pixel in world space and casts it into the scene to determine intersections and incident light. I was going to trash this code because Processing has a built in transformation matrix based camera, but realized that this method can be used for object selection, or picking.

Explanation

Given a click on the screen, the getRay() method in the camera will return the ray that passes from the camera origin into the scene through the image plane. By intersecting this ray with the scene, we can find the nearest object to the camera along the click ray — the object the user clicked.

//get the direction vector from the origin through the
//screen point that the user clicked
Tuple3f direction = cam.getRay(mouseX,mouseY);
  
//prepare the picking ray
Ray pick = new Ray(cam.pos, direction);
 
//intersect the camera ray with the scene
accel.findNearest(pick);

This is a rapid and efficient method of picking, but it carries significant overhead (you have to include a whole raytracer) and only works in the context of static scenes with heirarchically maintained triangles, unless you're not using an acceleration strucure, in which case it would be ridiculously slow. Another popular method that eschews these problems is rendering the scene offscreen and assigning a unique color to each triangle. Matching the color at the selected point will yield the appropriate triangle. This is especially effective in languages with pointers because the triangle color can be equal to the memory address of the intersectable object (or struct if we're talking C).

Another simple method is to project all selectable object centroids from world space into screen space using Processing's screen commands. Then calculate the distance from the object's item to the mouse cursor. The minimum distance will be the closest item. In this technique, one can use squared distances to save a sqrt() calculation because you are simply trying to find the minimal distance. This technique has the distinct advantage that the user does not actually have to hit the object. They merely have to be near it. Additionally, this will work with any object that supports a distance function: points, lines, spheres, etc.