# 11.3 - Selecting Objects¶

Interactive applications and games allow users to select objects from a 3D rendered scene. This lesson explains the standard technique for identifying user selected 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:

`gl.useProgram(selection_program)`- Clear the
*color buffer*and the*z-buffer*. - Render the scene.
- Read the pixel at location (mouse_x,mouse_y) from the
*color buffer*which identifies the object. `gl.useProgram(visible_program)`- Clear the
*color buffer*and the*z-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 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_BYTE`s, 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^{4}.
This operation requires this simple equation,

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

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.

- Right-click to select an object. The currently selected object is rendered in red.
- Left-click and drag rotates your view.
- Notice that you can select any visible object from any viewing angle.

Animate

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?