12.3 - Selecting Objects¶

Interactive applications and games allow users to select objects from a 3D rendered scene. There are two commonly used algorithms:

Cast a ray starting at the camera, (0,0,0), going into the scene through the location of the user mouse click. Then intersect the ray with every triangle in the scene and remember the closest one. The model associated with the selected triangle is the user selection.
Render the scene twice. On the first rendering, use a unique color with no lighting calculations to render each object in the scene. Read the color of the pixel at the location of the user mouse click. The unique color identifies the selected object. Then immediately clear the draw buffers and re-render the scene normally. The user never sees the first rendering, only the second one.

The second algorithm is easier to implement and is explained in detail in this lesson.

A “Selection” Algorithm¶

The following assumptions are made about a scene:

The scene is composed of multiple models which can be accessed from an array.
A unique identifier for each model is its array index.

The scene is rendered twice. The shader program used for the first rendering puts a unique identifier into every pixel rendered for each unique model. Let’s call this shader program selection_program. The second rendering creates the image seen by the user. Let’s call this shader program visible_program. Here are the steps to the selection algorithm, assuming that the user has clicked on the canvas location (mouse_x, mouse_y).

gl.useProgram(selection_program)
Clear the color buffer and the depth buffer.
Render the scene.
Read the color of the pixel at location (mouse_x,mouse_y) from the color buffer.
Use the color to identify the selected object.
gl.useProgram(visible_program)
Clear the color buffer and the depth buffer.
Render the scene.
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 8.1.)

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

How can values be retrieved from the color buffer after a rendering is finished?
How can a unique identifier be converted into a color value suitable for use in a fragment shader?
How can a color value retrieved from a color buffer be converted into a unique identifier?
How can a model be rendered using two different shader programs?

Reading Pixels 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. 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.

The selection algorithm only needs the color of one pixel from the color buffer. Therefore, the command is,

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

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. The value of mouse_y can be converted to the color buffer’s coordinate system by subtracting it from the buffer’s height:

mouse_y = buffer_height - mouse_y;

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.

Converting an Integer Identifier to a Color¶

Caveat

From the previous discussion we know that a WebGL 1.0 color buffer always uses 32 bits (8 bits per component) to represent a color. However, this might not be true for future WebGL versions. The following discussion assumes that the number of bits per component value can vary.

Setting a color in the color buffer requires four floating point values in the range [0.0, 1.0] like this:

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

The color component values are represented as floating point percentages to make their values hardware independent. However, at the hardware level, the color component values are stored as integers to a precision defined by the underlying hardware. The number of bits used for individual component values in a color buffer can be queried 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;

The diagram to the right shows a conceptual representation of a color value in bit format. If an integer identifier is conceptualized in the same format then the integer can be divided into four parts and each part converted to a floating point percentage. Dividing the integer into four parts can be efficiently performed using bit-wise shift, >>, and and, & operations, as shown in the following code:

let red_max   = Math.pow(2,red_bits) - 1;
let green_max = Math.pow(2,green_bits) - 1;
let blue_max  = Math.pow(2,blue_bits) - 1;
let alpha_max = Math.pow(2,alpha_bits) - 1;

let red_shift   = green_bits + blue_bits + alpha_bits;
let green_shift = blue_bits + alpha_bits;
let blue_shift  = alpha_bits;

/** ---------------------------------------------------------------------
 * Given an integer identifier, convert it to an RGBA color value.
 * @param id {number} an integer identifier
 * @returns {Float32Array} A array containing four floats.
 */
function createColor(id) {
  var red, green, blue, alpha;

  red   = ((id >> red_shift)   & red_max)   / red_max;
  green = ((id >> green_shift) & green_max) / green_max;
  blue  = ((id >> blue_shift)  & blue_max)  / blue_max;
  alpha = ((id                 & alpha_max) / alpha_max;

  return new Float32Array([ red, green, blue, alpha ]);
};

Converting a Color to an Integer Identifier¶

When a color is retrieved from the color buffer using gl.readPixels(), the value is an array of four integers. To convert the four integers into a single integer identifier, the values are shifted and added like this:

let red_max   = Math.pow(2,red_bits) - 1;
let green_max = Math.pow(2,green_bits) - 1;
let blue_max  = Math.pow(2,blue_bits) - 1;
let alpha_max = Math.pow(2,alpha_bits) - 1;

let red_shift   = green_bits + blue_bits + alpha_bits;
let green_shift = blue_bits + alpha_bits;
let blue_shift  = alpha_bits;

/** ---------------------------------------------------------------------
 * Given a RGBA color value from a color buffer, calculate and return
 * a single integer.
 * @param red   {number} component in the range [0,red_max  ]
 * @param green {number} component in the range [0,green_max]
 * @param blue  {number} component in the range [0,blue_max ]
 * @param alpha {number} component in the range [0,alpha_max]
 * @returns {number} An integer identifier.
 */
function getID(red, green, blue, alpha) {
  // Shift each component to its bit position in the final integer
  return ( (red   << red_shift)
         + (green << green_shift)
         + (blue  << blue_shift)
         + alpha );
};

A JavaScript Conversion Class¶

The two functions, createColor() and getID() can be combined into a single JavaScript class to avoid recalculating the configuration values each time they are needed. In addition, the continual creation of new objects, such as creating a new color object for each call to createColor(), should be avoided to minimize garbage collection. Please study the details of the following JavaScript class.

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

  let self = this;

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

  let red_max   = Math.pow(2,red_bits) - 1;
  let green_max = Math.pow(2,green_bits) - 1;
  let blue_max  = Math.pow(2,blue_bits) - 1;
  let alpha_max = Math.pow(2,alpha_bits) - 1;

  let red_shift   = green_bits + blue_bits + alpha_bits;
  let green_shift = blue_bits + alpha_bits;
  let blue_shift  = alpha_bits;

  let color = new Float32Array(4);

  /** ---------------------------------------------------------------------
   * Given an integer identifier, convert it to an RGBA color value.
   * @param id {number} an integer identifier
   * @returns {Float32Array} A array containing four floats.
   */
  self.createColor = function (id) {

    color[0] = ((id >> red_shift)   & red_max)   / red_max;
    color[1] = ((id >> green_shift) & green_max) / green_max;
    color[2] = ((id >> blue_shift)  & blue_max)  / blue_max;
    color[3] = ( id                 & alpha_max) / alpha_max;

    return color;
  };

  /** ---------------------------------------------------------------------
   * Given a RGBA color value from a color buffer, calculate and return
   * a single integer.
   * @param red   {number} component in the range [0,red_max  ]
   * @param green {number} component in the range [0,green_max]
   * @param blue  {number} component in the range [0,blue_max ]
   * @param alpha {number} component in the range [0,alpha_max]
   * @returns {number} An integer identifier.
   */
  self.getID = function (red, green, blue, alpha) {
    // Shift each component to its bit position in the final integer
    return ( (red   << red_shift)
           + (green << green_shift)
           + (blue  << blue_shift)
           + alpha );
  };

};

Rendering a Model with Different Shader Programs¶

For the WebGL program below, the scene is created by rendering one model of a cube at different positions, different scales, and different colors. The cube model is defined by a single set of vertex object buffers that are created by a call to ModelArraysGPU(). That is:

gpuModel = new ModelArraysGPU(gl, models["cube2"], out);

Two separate shader programs are created using these statements:

select_program = download.createProgram(gl,
                   vshaders_dictionary["uniform_color"],
                   fshaders_dictionary["uniform_color"]);
visible_program = download.createProgram(gl,
                    vshaders_dictionary["uniform_color_with_lighting"],
                    fshaders_dictionary["uniform_color_with_lighting"]);

The select_program sets every fragment that composes a rendered model to the same color. For selection, this is a color that represents a unique identifier. The visible_program performs lighting calculations when it renders a model and therefore every fragment is potentially a different color.

Two separate classes use these different shader programs to render the cube model. These are created with these calls:

select_cube = new RenderUniformColor(gl, select_program, gpuModel, download.out);
cube = new RenderUniformColorWithLighting(gl, visible_program, gpuModel, download.out);

During rendering, the appropriate object is used to render a cube. The rendering function’s parameter, select_mode, is used to pick the correct rendering function. (Note that JavaScript allows for default parameter values. Since the parameter select_mode is set to false in the function heading, a call to render() is equivalent to render(false)).

Error Warning

GLSL variables of type uniform can only be initialized for the active shader program. Calling any version of gl.uniform[1234]f[v] for a variable that is not part of the active shader program will generate WebGL errors.

Experiments¶

Experiment with the following WebGL program and then modify the code as described below. (Use right button mouse clicks to select a model.)

Show: Code Canvas Run Info

select_scene.js

/**
 * select_render.js, By Wayne Brown, Spring 2018
 */

/**
 * The MIT License (MIT)
 *
 * Copyright (c) 2015 C. Wayne Brown
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.

* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */

"use strict";

/** -----------------------------------------------------------------------
 * Create a WebGL 3D scene, store its state, and render its models.
 *
 * @param id The id of the webglinteractive directive
 * @param download An instance of the SceneDownload class
 * @param vshaders_dictionary A dictionary of vertex shaders.
 * @param fshaders_dictionary A dictionary of fragment shaders.
 * @param models A dictionary of models.
 * @constructor
 */
window.SelectScene = function (id, download, vshaders_dictionary,
                               fshaders_dictionary, models) {

// Private variables
  let self = this;
  let out = download.out;

let gl = null;
  let select_program = null;
  let visible_program = null;
  let cube = null;
  let select_cube = null;
  let gpuModel;
  let number_cubes = 30;
  let all_cubes = new Array(number_cubes);

let matrix = new GlMatrix4x4();
  let transform = matrix.create();
  let camera_model_transform = matrix.create();
  let projection = matrix.createPerspective(45.0, 1.0, 0.1, 100.0);
  let camera = matrix.create();
  let scale_matrix = matrix.create();
  let translate_matrix = matrix.create();
  let rotate_x_matrix = matrix.create();
  let rotate_y_matrix = matrix.create();

// Public variables that will possibly be used or changed by event handlers.
  self.canvas = null;
  self.angle_x = 0.0;
  self.angle_y = 0.0;
  self.animate_active = true;

// Light model
  let P4 = new GlPoint4();
  let V = new GlVector3();
  self.light_position = P4.create(10, 10, 10, 1);
  self.light_color = V.create(1, 1, 1); // white light
  self.shininess = 30;
  self.ambient_color = V.create(0.2, 0.2, 0.2); // low level white light

let convert = null;
  let pixel = new window.Uint8Array(4); // A single RGBA value
  let selected_object_id = -1;
  let red = [1.0, 0.0, 0.0, 1.0];

//-----------------------------------------------------------------------
  self.render = function (select_mode = false) {
    let size, position, color, x_radians, y_radians, scale;

// Clear the entire canvas window background with the clear color
    gl.clear(gl.COLOR_BUFFER_BIT | gl.DEPTH_BUFFER_BIT);

// Rotate the models about the origin
    matrix.rotate(rotate_x_matrix, self.angle_x, 1.0, 0.0, 0.0);
    matrix.rotate(rotate_y_matrix, self.angle_y, 0.0, 1.0, 0.0);

if (! select_mode) {
      //  - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
      // Set the location of the light source
      gl.useProgram(visible_program);
      gl.uniform3f(visible_program.u_Light_position, self.light_position[0],
          self.light_position[1],
          self.light_position[2]);
      gl.uniform3fv(visible_program.u_Light_color, self.light_color);
      gl.uniform3fv(visible_program.u_Ambient_color, self.ambient_color);
      gl.uniform1f(visible_program.u_Shininess, self.shininess);
    }

// Draw a set of spheres with different locations, sizes, and colors.
    for (let j = 0; j < number_cubes; j += 1) {
      size     = all_cubes[j].size;
      position = all_cubes[j].position;
      color    = all_cubes[j].color;

matrix.scale(scale_matrix, size, size, size);
      matrix.translate(translate_matrix, position[0], position[1], position[2]);

// Combine the transforms into a single transformation
      matrix.multiplySeries(camera_model_transform, camera,
                            rotate_x_matrix, rotate_y_matrix,
                            translate_matrix, scale_matrix);
      matrix.multiplySeries(transform, projection, camera_model_transform);

if (select_mode) {
        // Render a single cube using its array index converted into a color.
        select_cube.render(transform, convert.createColor(j));
      } else {
        // Render a single cube. Make it red if it is the selected object.
        if (j === selected_object_id) { color = red; }
        cube.render(transform, camera_model_transform, color);
      }
    }
  };

//-----------------------------------------------------------------------
  /**
   * Given the location of a mouse click, get the object that is rendered
   * at that location.
   * @param mouse_x Number The x-component of the mouse's location.
   * @param mouse_y Number The y-component of the mouse's location.
   */
  self.select = function (mouse_x, mouse_y) {

// Render the scene to put each object's ID number into the color buffer.
    self.render(true);

// Convert the canvas coordinate system into an image coordinate system.
    mouse_y = self.canvas.clientHeight - mouse_y;

// Get the color value from the rendered color buffer.
    gl.readPixels(mouse_x, mouse_y, 1, 1, gl.RGBA, gl.UNSIGNED_BYTE, pixel);

// Convert the RGBA color array into a single integer
    selected_object_id = convert.getID(pixel[0], pixel[1], pixel[2], pixel[3]);

// Debugging
    out.displayInfo("Pixel = " + pixel);
    out.displayInfo("ID = " + selected_object_id);

// Now render the scene for the user's view.
    self.render(false);
  };

//-----------------------------------------------------------------------
  self.delete = function () {

// Clean up shader programs
    gl.deleteShader(select_program.vShader);
    gl.deleteShader(select_program.fShader);
    gl.deleteProgram(select_program);

gl.deleteShader(visible_program.vShader);
    gl.deleteShader(visible_program.fShader);
    gl.deleteProgram(visible_program);

// Delete each model's VOB
    cube.delete(gl);
    select_cube.delete(gl);

events.removeAllEventHandlers();

// Disable any animation
    self.animate_active = false;
  };

//-----------------------------------------------------------------------
  // Object constructor. One-time initialization of the scene.

// Get the rendering context for the canvas
  self.canvas = download.getCanvas(id + "_canvas");
  if (self.canvas) {
    gl = download.getWebglContext(self.canvas);
  }
  if (!gl) {
    return;
  }

// Make the cursor be a pointer in the canvas window.
  $(self.canvas).css("cursor", "pointer");
  $('#' + id + '_animate').prop('checked', self.animate_active);

// Set up the rendering programs
  select_program = download.createProgram(gl, vshaders_dictionary["uniform_color"],
                                              fshaders_dictionary["uniform_color"]);
  visible_program = download.createProgram(gl, vshaders_dictionary["uniform_color_with_lighting"],
                                               fshaders_dictionary["uniform_color_with_lighting"]);

gl.enable(gl.DEPTH_TEST);

gl.clearColor(0.98, 0.98, 0.98, 1.0);

matrix.lookAt(camera, 0.0, 0.0, 20.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0);

// Create Vertex Object Buffers for the models
  gpuModel = new ModelArraysGPU(gl, models["cube2"], out);
  select_cube = new RenderUniformColor(gl, select_program, gpuModel, download.out);
  cube = new RenderUniformColorWithLighting(gl, visible_program, gpuModel, download.out);

// Create a set of random positions, colors, and sizes for a group of cubes.
  let position_x, position_y, position_z;
  for (let j = 0; j < number_cubes; j += 1) {
    position_x = Math.random() * 10 - 5.0;
    position_y = Math.random() * 10 - 5.0;
    position_z = Math.random() * 10 - 5.0;
    all_cubes[j] = { position: [position_x, position_y, position_z],
                     size: Math.random() + 0.2,
                     color: new Float32Array([0.0, Math.random(), Math.random(), 1.0])
                   };
  }

// Set up callbacks for user and timer events
  let events;
  events = new SelectEvents(id, self);
  events.animate();

// Create an object to convert between integer identifiers and colors.
  convert = new ColorToID(gl);
};

Experiment with object selection.

Right-click to select an object. The currently selected object is rendered in red.
Left-click and drag rotates your view.

Animate

Show: Process information Warnings Errors

Open this webgl program in a new tab or window

Experiments:

Study the select function in lines 142-161. Note that it calls the render() function twice.
Don’t render the scene twice on selection by commenting out lines 161. (Disable animation to keep the “selection rendering” visible on the canvas.) The “color” rendered for each cube was created from the cube’s integer identifier (see line 126).
Lines 157-158 display the color of a “clicked-on” pixel and the identifier value it represents. Try to select various cubes and note the output to the console window (or the “Run Info” window below the canvas). Note that a color of (249,249,249,255), which translates to an identifier of -101058049, is the color of the background and therefore no cube is selected. The background color should be a value that does not translate into a valid model identifier.
Note that rendering the scene twice for selection has no effect on the frame rate of the animation. What happens if you increase the number of cubes’s from 30 to 300 in line 54? How about 3000? How about 30000? (Looks kind of like a Borg spaceship from Star Trek – don’t you think?)

Glossary¶

selection algorithm: An algorithm for selecting one model (or geometric primitive) from a large collection of models using a user’s mouse click.
gl.readPixels(): A function in the WebGL API that allows a JavaScript program to access the output image of a rendering.
bitwise shift operators: << and >>: JavaScript operators that shift the bits in a binary value left or right. For example, 00101101 >> 2 results in 00001011.
bitwise logical-and operator: &: A JavaScript operator that performs a logical “and” operation on a bit-by-bit basis. For example, 01001101 & 15 results in 00001101 because 15 in binary is 00001111.

Self Assessment¶

Q-406: What WebGL command will retrieve values from a color buffer?

gl.readPixels()
Correct.
gl.readColorBuffer()
Incorrect. There is no such function.
gl.getPixelColor()
Incorrect. There is no such function.
gl.atPixel()
Incorrect. There is no such function.

Q-407: When a color is read from a WebGL color buffer, what type of data is returned?

Four unsigned bytes in the range 0 to 255.
Correct.
Four floating point values in the range 0.0 to 1.0.
Incorrect. This is how colors are specified in a fragment shader, but not how they are actually stored in the color buffer.
One unsigned integer in the range 0 to 2³²-1
Incorrect.
Three floating point values, RGB, in the range 0.0 to “max_color”.
Incorrect.

Q-408: The coordinate system used for a canvas is different from the coordinate system used for a color buffer. Which of the following is correct?

canvas: Y axis down, origin in upper-left corner
color buffer: Y axis up, origin in lower-left corner
Correct.
canvas: Y axis up, origin in lower-left corner
color buffer: Y axis down, origin in upper-left corner
Incorrect.
canvas: Y axis up, origin in center
color buffer: Y axis up, origin in lower-left corner
Incorrect.
canvas: Y axis down, origin in center
color buffer: Y axis up, origin in center
Incorrect.

Q-409: If a has the value of 6, what is a << 2. (Six in binary is 110.)

11000 (24)
Correct. It is a left shift by 2 bits.
00110 (6)
Incorrect.
1100 (12)
Incorrect.
11011 (27)
Incorrect.

Q-410: If a has the value of 187, what is a >> 5. (187 in binary is 10111011.)

101 (5)
Correct. It is a right shift by 5 bits.
11011 (27)
Incorrect.
10111 (23)
Incorrect.
1110 (14)
Incorrect.

Q-411: Why are two separate shader programs needed to accomplish a selection? (Select all that apply.)

The shader program that puts a unique identifier into the color buffer must not perform lighting calculations because the lighting calculations would change the ID.
Correct.
The shader program that creates the visible rendering should create a realistic scene.
Correct.
The shader program that puts a unique identifier into the color buffer must ignore the color properties of the model.
Correct.
The shader program that puts a unique identifier into the color buffer must deal with light attenuation.
Incorrect.

Next Section - 12.4 - Transparency