Selection in 3D Graphics Environments
Christine Albert and Lindsey Press

The ray picking approach involves a series of transformations when a 3D object is rendered. As was referenced in earlier weeks, the pipeline begins with object space and transforms to world space, camera space, and lastly viewport space. The inverse pipeline transformations make traveling through the pipeline in reverse possible, which is crucial to this ray picking approach implemented. Once the scene has been rendered and appears on-screen, a ray is shot into the scene with the origin at the mouse position. Following this, inverse transformations are applied to travel back to object space and test for intersection between the ray and each object. The pipeline is then followed back to viewport space where any cube that intersects with the ray will appear highlighted red.

The steps involved in implementing the ray picking approach are as follows:

Step 1: Ray Class

The following code was added to implement a ray class: class Ray
{
public:
     Ray() {
          origin = vec3(0.0f, 0.0f, 0.0f);
          dir = vec3(0.0f, 0.0f, 0.0f);
     }
     vec3 origin;
     vec3 dir;
};

The purpose of this class is to create a ray that has two components, origin and direction. Both of these componenets are designated as vectors, and are initialized to 0. This allows for the instantiation of a ray later in the code for in the ray pick method, which requires a ray to be created and ultimately tested for intersectionality with a given object in the graphics scene.


Step 2: Intersect Method


Some of the key aspects of the intersect method code are highlighted below. The overall purpose of this method is to accept paramaters for a cube and a ray and return a boolean result indicating whether or not the ray intersects the cube.

GLboolean Intersect(Cube c, Ray r, GLfloat & tmin)
{
     GLfloat tmax, tymin, tymax, tzmin, tzmax;
     GLfloat size = 2.0f;

     vec3 v1 = -vec3(size / 2.0, size / 2.0, size / 2.0);
     vec3 v2 = vec3(size / 2.0, size / 2.0, size / 2.0);


The above section of code lays out the heading and variables for this method. As previously mentioned, the two especially noteworthy parameters are the cube and ray that the method accepts. Various variables are included to perform calculations that determine whether or not the ray intersects, and the two vectors v1 and v2 are adjusted for the presumed cube size of 2x2x2, thus why the size for the x, y, and z coordinates is divided by 2 for both vectors, the only difference being that v1 is negative and v2 is positive.
The remainder of the method includes if/else statements that first test the values of the x and y direction of the ray, setting values for tmax and tmin once it is determined whether the direction of these components is positive or negative. The firist set of if/else statements assigns the tmin and tmax values, which are based on the xdirectional component of the ray. Following this, tymin and tymax are assigned values based on the y directional component of the ray. The calculation for all of these assignments is similar, and the x or y value of the ray's origin is subtracted from either v1 or v2's x or y component, depending on which specific component of the vector was initially being tested. This value is then divided by the x or y directional component of the ray, which again will match the component initially being tested. The next section of the if/else statements tests wether tmin is greater than tymax or if tmax is less than tymin, and if either of these is true the method returns false as it is known that the ray does not intersect. If this is not the case, tymin is assigned to time if tmin is less than tymin, and tymax is assigned to tmax if tmax is greater than tymax. This functions to use the larger value for the minimum component, and the smaller value for the maximum component. The z direction of the ray is then tested, and txmin and tzmax are set according to whether or not this component is greater than or equal to zero. The values for these variables involves subtracting the z component of the ray's origin from the z component of v1 or v2, and that value is divided by the z directional component of the ray. At this point, it is tested to determine whether tmin is greater than tmax or if tmax is less than tzmin; if either of these conditions is true, the method will return false as this case also signifies that the ray does not intersect. Otherwise, the method returns true and signifies that the ray has been found to intersect.


Step 3: Ray Pick Method


Portions of code will be included below to highlight some of the key features of this method. The overall function of this method is to find and print the amount of time it takes to perform selection in the graphics scene using the ray picking method. This method takes a window, button, action, and mods as its parameters and instantiates a ray, using various vector variables to ultimately allow for the return of the time it takes to test for the intersection of a ray with an object in the graphics scene. One of the key aspects of this method is that when the left mouse button is clicked on the graphics scene, the glfw timer begins and clickedindex is set to -1 to start the process. A viewport vector is assigned, and the y position is determined. The following code segment appears next in the sequence described:

for (int i = 0; i < NUMCUBES; i++)
{
     mat4 model = cubes[i].model;      robj.origin = unPorject(vec3(xpos, ypos, 0.0), camera*model, projection, viewport);
     robj.dir = unProject(vec3(xpos, ypos, 1.0), camera*model, projection, viewport);
     robj.dir = normalize(robj.dir - robj.rigin);

     GLboolean hit = Intersect(cubes[i], robj, zcube);
     if (hit && zcube < zmin)
     {
          zmin = zcube; clickedindex = i;
     }
}

This for loop tests for intersection using rays and runs for the number of cubes in the scene. The orign value of the ray robj is set using the unProject method, which converts a point in screen space to a point in world space, such as discussed in earlier posts involving matricies and inverse transformations. The directional component of the ray robj is then set using the same method, and following this is normalized to allow for its implementation in the intersect method. The call to the interset method tests using the cube of the given iteration, the value of the ray robj that has been converted to world space and normalized, and is tested with 'zcube', or the z component of the cube in question. If it is determined that hit is true, meaning there is intersection, and if zcube is less than zmin, zmin is set to zcube and the clickedindex is set to the current iteration of the the loop to remember the minimum z value and which iteration of cube it occurred.

After this for loop has finished running, the end time variable is assigned by getting the time of the timer that was running and the method prints the total time taken to test for selection using the ray picking method in milliseconds.


Step 4: Update Main Method


The final key changes to the code are made in the AppMain segment of code. Where before there was a call for the program to use the ColorPick method, discussed in the previous post, a different call is added and shown below:

glfwSetMouseButtonCallback(gWindow, RayPick);

This is the change necessary to implement the ray picking approach instead of the color picking approach. The remainder of the main function remains the same, and while the window is open the scene is continually updated with changes to the graphics scene and continually re-rendered, but clicks to select now use the RayPick method in place of the ColorPick method. The time taken for the ray pick method to execute and select an object, or alternatively to determine that no object is present and there is no intersection, is printed and appears on screen when the program is run. This allows for the collection of data to determine which of the two methods, ray picking or color picking, is more efficient with regards to time.

Resources:

http://www.ntu.edu.sg/home/ehchua/programming/opengl/cg_basicstheory.html