11.3 - Selecting Objects¶

A “Selection” Algorithm¶

When a user clicks on a specific location in a rendered image, we would like to identify the object that was rendered at that location. If you think about it, the solution is simple: for every pixel in a rendered image don’t store the color of an object – instead store a unique identifier for that object. When the user clicks on a pixel, return the unique identifier stored for that pixel. Of course we don’t want the user to see these unique identifiers, so we render a scene twice, the first time with the unique identifiers, and the second time with correct colors. The user never sees the rendered image that contains the identifiers because we never display it to the canvas window. This algorithm requires two shader programs. A “selection_program* produces a rendering of the identifiers, and a “visible_program” produces the rendering that is displayed to the user.

Let’s assume that we want to know which object is at the mouse location (mouse_x, mouse_y). The algorithm, in pseudocode, follows these steps:

1. gl.useProgram(selection_program)
2. Clear the color buffer and the z-buffer.
3. Render the scene.
4. Read the pixel at location (mouse_x,mouse_y) from the color buffer which identifies the object.
5. gl.useProgram(visible_program)
6. Clear the color buffer and the z-buffer.
7. Render the scene.
8. The contents of the color buffer becomes visible in the canvas window because the JavaScript code terminates its execution. (See the discussion on double-buffering in lesson 11.1.)

There are several technical issues we need to discuss before we look at a complete implementation of this algorithm.

• How can you read a value out of the color buffer at a particular location?
• How can you store a unique object identifier as a color value in a color buffer?
• How can you render a model using two different shader programs?

Read From the Color Buffer¶

After a rendering operation you can access the resulting color buffer using the gl.readPixels() function. This allows you to read a rectangular section of the image into a 1D array of color component values. OpenGL supports a variety of image formats, but WebGL 1.0 only supports one image format: 8 bits per component with 4 components per pixel (RGBA). To retrieve a rectangular section of the color buffer that has dimensions width by height starting at the lower-left corner (x,y), you would use this command:

pixels = new Uint8Array(width*height*4); // RGBA values for each pixel
gl.readPixels(x, y, width, height, gl.RGBA, gl.UNSIGNED_BYTE, pixels);

The pixel data is stored in row-major order in the 1D array.

We only need to get a single pixel value from the color buffer, so our command is,

pixels = new Uint8Array(4); // A single RGBA value
gl.readPixels(mouse_x, mouse_y, 1, 1, gl.RGBA, gl.UNSIGNED_BYTE, pixels);

However, the coordinate system for the canvas window and the color buffer are not the same. The canvas window has its Y axis starting at the top-left corner and going down the screen. The color buffer‘s image coordinate system has its Y axis starting at the bottom-left corner and going up the image. We need to invert the value of mouse_y based on the height of the color buffer. Take a second to prove to yourself that this equation does the right thing:

mouse_y = image_height - mouse_y;

Finally, note that pixels is an array of UNSIGNED_BYTEs, not floats. Each component is an 8-bit unsigned integer in the range 0 to 255.

Storing Identifiers as Colors¶

Without lose of generality, we can assume that object identifiers are integers. We need to store a integer ID into a color buffer that is defined by floating point color values. In a fragment shader you set a fragment’s color to a vec4 value like this,

gl_FragColor = vec4(red, green, blue, alpha);

where each component value is a floating point value in the range 0.0 to 1.0. However, a color buffer does not store floating point values; it stores integer values to a limited precision. We can get the number of bits used for individual values in a color buffer using these JavaScript calls:

red_bits   = gl.getParameter(gl.RED_BITS);
green_bits = gl.getParameter(gl.GREEN_BITS);
blue_bits  = gl.getParameter(gl.BLUE_BITS);
alpha_bits = gl.getParameter(gl.ALPHA_BITS);
total_bits = red_bits + green_bits + blue_bits + alpha_bits;

To convert a floating point value in the range [0.0, 1.0] to a limited precision integer, we can scale it by the allowed precision and then round it to the closest integer. Let f be a floating point value we want to map to the integer range [0,n-1], where n is a power of 2. For example, the range [0,15], where n = 16 = 2⁴. This operation requires this simple equation,

var i = Math.round(f * (n-1));

Bit arrangement for a single integer value

We would like to use a series of integers to represent a single larger integer. The diagram on the right shows a conceptual layout of the color components. To calculate a single integer value we need to scale (or shift) each value to its correct position in the larger integer, where the scale factors are powers of 2. The number of bits to the right of each value gives us the required scale factor. The final result is a function that can convert a color value composed of 4 unsigned integers into a single integer identifier:

/** ---------------------------------------------------------------------
 * Given a RGBA color value from a color buffer, where each component
 * value is an integer in the range [0,numBits-1].
 * @param r Number Red   component in the range [0,numBits-1]
 * @param g Number Green component in the range [0,numBits-1]
 * @param b Number Blue  component in the range [0,numBits-1]
 * @param a Number Alpha component in the range [0,numBits-1]
 * @returns Number An integer identifier.
 */
self.getID = function (r,g,b,a) {
  // Shift each component to its bit position in the integer
  return ( r * Math.pow(2, green_bits+blue_bits+alpha_bits)
         + g * Math.pow(2, blue_bits+alpha_bits)
         + b * Math.pow(2, alpha_bits)
         + a );
};

Now let’s do the reverse. Given an integer ID, convert it into a RGBA color. The individual color component values, (r,g,b,a), can be calculated by dividing by powers of 2 to move them to the least significant bits and then removing the fractional part using the floor function. Before the next value is calculated we remove the value of the first part from the original ID.

self.createColor = function (id) {
  var r, g, b, a;

  r = Math.floor(id / Math.pow(2,green_bits+blue_bits+alpha_bits));
  id = id - (r * Math.pow(2,green_bits+blue_bits+alpha_bits));

  g = Math.floor(id / Math.pow(2,blue_bits+alpha_bits));
  id = id - (g * Math.pow(2,blue_bits+alpha_bits));

  b = Math.floor(id / Math.pow(2,alpha_bits));
  id = id - (b * Math.pow(2,alpha_bits));

  a = id;

  return new Float32Array([ r/(Math.pow(2,red_bits)-1),
                            g/(Math.pow(2,green_bits)-1),
                            b/(Math.pow(2,blue_bits)-1),
                            a/(Math.pow(2,alpha_bits)-1) ] );
};

These two functions, createColor() and getID() are non-trivial and we should avoid recalculating the powers of 2 over and over again. Putting these functions into an JavaScript “class” would make a lot of sense. Below is a JavaScript class definition that pre-calculated the needed scale and shift factors to simplify the calculations.

/** =======================================================================
 *
 * @param gl WebGLRenderingContext
 * @constructor
 */
window.ColorToID = function (gl) {

  var self = this;

  // Get the precision of each color component
  var red_bits   = gl.getParameter(gl.RED_BITS);
  var green_bits = gl.getParameter(gl.GREEN_BITS);
  var blue_bits  = gl.getParameter(gl.BLUE_BITS);
  var alpha_bits = gl.getParameter(gl.ALPHA_BITS);
  var total_bits = red_bits + green_bits + blue_bits + alpha_bits;

  var red_scale   = Math.pow(2, red_bits);
  var green_scale = Math.pow(2, green_bits);
  var blue_scale  = Math.pow(2, blue_bits);
  var alpha_scale = Math.pow(2, alpha_bits);

  var red_shift   = Math.pow(2, green_bits + blue_bits + alpha_bits);
  var green_shift = Math.pow(2, blue_bits + alpha_bits);
  var blue_shift  = Math.pow(2, alpha_bits);

  var color = new Float32Array(4);

  /** ---------------------------------------------------------------------
   * Given a RGBA color value, where each component is in the range [0.0,1.0],
   * create a integer ID.
   * @param r Number Red component in the range [0.0,+1.0]
   * @param g Number Green component in the range [0.0,+1.0]
   * @param b Number Blue component in the range [0.0,+1.0]
   * @param a Number Alpha component in the range [0.0,+1.0]
   * @returns Number An integer ID
   */
  self.createID = function (r, g, b, a) {
    // Change the color component values from the range (0.0, 1.0) to integers
    // in the range (0, 2^bits-1).
    r = Math.round(r * (red_scale   - 1));
    g = Math.round(g * (green_scale - 1));
    b = Math.round(b * (blue_scale  - 1));
    a = Math.round(a * (alpha_scale - 1));

    // Shift each component to its bit position in the integer
    return (r * red_shift + g * green_shift + b * blue_shift + a);
  };

  /** ---------------------------------------------------------------------
   * Given a RGBA color value from a color buffer, where each component
   * value is an integer in the range [0,numBits-1].
   * @param r Number Red   component in the range [0,numBits-1]
   * @param g Number Green component in the range [0,numBits-1]
   * @param b Number Blue  component in the range [0,numBits-1]
   * @param a Number Alpha component in the range [0,numBits-1]
   * @returns Number An integer identifier.
   */
  self.getID = function (r, g, b, a) {
    // Shift each component to its bit position in the integer
    return (r * red_shift + g * green_shift + b * blue_shift + a);
  };

  /** ---------------------------------------------------------------------
   * Given an integer ID, convert it into an RGBA color.
   * @param id
   * @returns Float32Array An RGBA color as a 4-component array of floats.
   */
  self.createColor = function (id) {
    var r, g, b, a;

    r = Math.floor(id / red_shift);
    id = id - (r * red_shift);

    g = Math.floor(id / green_shift);
    id = id - (g * green_shift);

    b = Math.floor(id / blue_shift);
    id = id - (b * blue_shift);

    a = id;

    color[0] = r / (red_scale - 1);
    color[1] = g / (green_scale - 1);
    color[2] = b / (blue_scale - 1);
    color[3] = a / (alpha_scale - 1);

    return color;
  };
};

Rendering with Two Shader Programs¶

Given a model, we would like to render it in different ways using different shader programs. One shader program will render “identifiers” to the color buffer, while the other shader program will render colors to the color buffer. For efficiency you should use the same buffer objects with the same vertex attribute data. However, the rendering initialization will be different for the different shader programs. You can perform the correct initialization by determining which shader program is currently in use by calling the gl.getParameter() function with the parameter gl.CURRENT_PROGRAM. For example:

if (gl.getParameter(gl.CURRENT_PROGRAM) == select_program) {
  // Perform the initialization to render for the "select_program"
  // ...
} else {
  // Perform the initialization to render for the "visible_program"
  // ...
}

This is also useful when you are initializing uniform variables of a shader program because you can only pass data to the active shader program. Trying to send values to a shader program that is not “in use” generates WebGL errors.

Experiment¶

Experiment with the following demo program and then modify the code as described below.

Experiments:

• Study the select function in lines 145-167. Note that it calls the render() function twice, with a different shader program enabled each time.
• Don’t render the scene twice on selection by commenting out lines 165-166. These lines change the shader program and then render. If you don’t render using the “visible_program” shader, you will see the “identifier” rendering which contains the encoded ID’s.
• Uncomment lines 161-162 to display the value of the selected pixel and the identifier value it represents. Try to select various spheres and note the output to the window below the canvas. Note that a “selected pixel’s” color of (229,229,229,255), which translates to an single integer value of 3,857,049,087, is the color of the background and therefore no sphere is selected. The background should be a value that does not translate into a valid ID.
• Note the use of gl.getParameter(gl.CURRENT_PROGRAM) to control which rendering code is executed.
• Note that rendering the scene twice on selection does not seem to effect the frame rate of the animation. What if you increase the number of sphere’s from 30 to 300 in line 49? How about 3000? How about 30000?