Every 3D application will have user interaction to some degree. But with the CPUs and GPUs these days, it’s easy to have 100’s or 1000’s of entities per scene, and if you want to do per-triangle selection, It’s very easy to quickly end up with 100 000s into the millions of triangles with in a scene. Take the Standford Dragon mesh as an example. Below is a version of it opened in Iris Viewer which holds 900 000 Vertices which make up 100 000 faces kept in a single mesh.
This is great, even in WebGL, I still get 35 fps on a Macbook air, and that’s without much optimization on the *.OBJ file importer. So you have your scene, you have your meshes, but what if you want to select something?
There’s a few methods:
We could implement a raycast method where we cast a ray from the camera, but then that involves us calculating and setting up bounding shapes for each entity we want to be able to select and then testing against each shape which could quickly get expensive in terms of CPU usage. It’s not really practical for a 100 000 selectable faces. There’s also depreciated method built into OpenGL and is a semi workable solution in C++, but support (and accuracy) for it is subpar and it has a limit on the number of entities in a scene.
Whats needed is a more robust solution that’s applicable too not only OpenGL/WebGL, but any graphics backend? This is where Colour Index Encoding comes in. What it does is assign an index to each selectable item, in the Standford Dragons case, an index for each face.
Below is the same mesh with each face displaying it’s index converted into a colour.
Using this colour, we can back out the index of of the face so that we can handle user input and selection. So how do we do this?
Colour Index Encoding
Index encoding is a method I’ve used more than a few times on different platforms and boils down to encoding the Index of the entity you’re drawing into a colour. This requires the scene to be drawn twice, once with no normals, no lighting, only the encoded colour, and then drawn again normally once with all the textures and lighting and everything. In between the two draw calls, the mouse would read what RGB values are under it and from there the item encoding can be backed out from there.
In terms of encoding the colours, here’s a basic example using a typical RGB colour,
item1 = (1,0,0)
item2 = (2,0,0)
… and so on
and then once the 255th item is reached it would roll over back to 1 in R and then the G value will increment up.
item255 = (255,0,0)
item256 = (1,1,0)
In terms of code, these are the Encode/Decode methods I use:
[code language=”javascript”]
// Set’s the RGB values based on a index value
vxColour.prototype.EncodeColour = function(index) {
this.R = index % 255;
this.G = Math.floor((index/255) % (255));
this.B = Math.floor((index/(255 * 255)) % (255));
this.A = 1;
//Now scale down the values from 0-255 to 0-1
this.R = this.R / 255;
this.G = this.G / 255;
this.B = this.B / 255;
//this.A = this.A / 255;
};
// Set’s the Index value based on the RGBA value
vxColour.prototype.DecodeColour = function(r, g, b, a) {
var index = 0;
index = r + g * 255 + b * 255 * 255;
return index;
};
[/code]
Since a typical RGB Colour is essentially three numbers which each hold a value between 0 to 255, then the total number of possible colours is
255 ^ 3 = 16 581 375
Or a little over 16 and a half million possible combinations, and that’s before we even consider using an Alpha value (which brings the total number to over 4 billion combinations).
Apply this to each entity you wish to draw, whether it’s a per-mesh or per-face.
In Iris Viewer, I set the Selection Colour as a separate array during the Buffer Initialization.
[code language=”javascript”]
// Setup the Vertices Buffer
this.meshVerticesBuffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, this.meshVerticesBuffer);
gl.bufferData(gl.ARRAY_BUFFER, new Float32Array(this.mesh_vertices), gl.STATIC_DRAW);
// Set up the Normal Buffer for the vertices.
this.meshVerticesNormalBuffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, this.meshVerticesNormalBuffer);
gl.bufferData(gl.ARRAY_BUFFER, new Float32Array(this.vert_noramls), gl.STATIC_DRAW);
// Now set up the colors
this.meshVerticesColorBuffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, this.meshVerticesColorBuffer);
gl.bufferData(gl.ARRAY_BUFFER, new Float32Array(this.vert_colours), gl.STATIC_DRAW);
// Setup the Selection Color Buffer
this.meshVerticesSelectionColorBuffer = gl.createBuffer();
gl.bindBuffer(gl.ARRAY_BUFFER, this.meshVerticesSelectionColorBuffer);
gl.bufferData(gl.ARRAY_BUFFER, new Float32Array(this.vert_selcolours), gl.STATIC_DRAW);
[/code]
Double Draw
Now that the selectable entities have been given an index and relating colour. From here the next step is set up the rendering.
As I stated already, the scene needs to be drawn twice. Once with the indexed colour with no shading, and then once with the normal scene with shading and edges etc. The layout of the algorithm is as follows:
- Draw the Scene with the Indexed Colours and no shading.
- Check what is the colour of the pixel at the mouse position.
- Now re-draw the scene with the regular shading, edges, etc.
In Iris I added a seperate method for drawing the Indexed Colour that’s similar to the Draw call called ‘DrawSelPreProc()’.
[code language=”javascript”]
vxMeshPart.prototype.DrawSelPreProc = function(){
// Only Draw if it’s enabled.
if(this.Enabled === true){
// Bind the Buffers
// Bind the Vertices buffer to the shader attribute.
gl.bindBuffer(gl.ARRAY_BUFFER, this.meshVerticesBuffer );
gl.vertexAttribPointer(vertexPositionAttribute, 3, gl.FLOAT, false, 0, 0);
// Bind the Normals buffer to the shader attribute.
gl.bindBuffer(gl.ARRAY_BUFFER, this.meshVerticesNormalBuffer);
gl.vertexAttribPointer(vertexNormalAttribute, 3, gl.FLOAT, false, 0, 0);
// Here is where the Selection Colour is set in the buffers
// Bind the Selection Colour buffer to the shader attribute.
gl.bindBuffer(gl.ARRAY_BUFFER, this.meshVerticesSelectionColorBuffer);
gl.vertexAttribPointer(vertexColorAttribute, 4, gl.FLOAT, false, 0, 0);
// Draw the mesh.
gl.bindBuffer(gl.ELEMENT_ARRAY_BUFFER, this.meshVerticesIndexBuffer);
setMatrixUniforms();
if(this.meshType == MeshType.Solid){
gl.drawElements(gl.TRIANGLES, this.Indices.length, gl.UNSIGNED_SHORT, 0);
}
}
};
[/code]
As an example, I’ll be using the 3D worlds most famous Teapot, the Utah Teapot. Drawn normally, the scene looks like this:
But drawn with the Indexed Colour, it looks like the following:
All of the different shades of red illustrate the index of that face index. For a larger model you begin to see shades of green, and eventually you’ll see colours of blue as seen in the Standford Dragon image above.
Reading Pixels
Now that we’ve rendered the scene using the indexed colour, you can then read the Pixel data at the Mouse Position. For Javascript in WebGL, the code looks like the following. Note we need to correct for the ‘y’ position of the mouse.
[code language=”javascript”]
// Get Selection Information
//*******************************************************************
var pixels = new Uint8Array(4);
gl.readPixels(MouseState.x, gl.drawingBufferHeight – MouseState.y, 1, 1, gl.RGBA, gl.UNSIGNED_BYTE, pixels);
HoverIndex = 0;
HoverIndex = pixels[0] + pixels[1] * 255 + pixels[2] * 255 * 255;
[/code]
From here, we then have the Hover Index, we can now draw the scene regularly, using the Hover Index to highlight the proper entity/face.
Below is the same Utah Teapot scene now with Hovering and Selection implemented using the Indexed Colour method. There’s two faces too note; The Orange shows a previously selected Face while the Blue is a Highlighted face.
In a larger scene with more entities the solution can look like the following:
The Regular Scene of Spheres with 122 880 Faces and and over 1.1 million vertices:
The same Sphere scene with the Colour Encoded Index Scene:
Note the shade of green and yellows indicating a much larger Encoded index.
Conclusion
This is a robust and extendable yet simple solution for selection on almost any 3D Platform. It requires very little extra code when compared to a raycast method and can be used on any platform that allows you to read pixel data.
For other platforms that don’t have an easy way to read pixel data in realtime such as XNA/MonoGame, hovering isn’t possible, but Selecting is still an option as a mouse click is a one-frame event. I’ll be posting a method soon on that!
Until then, you can try different models in Iris by clicking below:
