Megabyte Softworks
C++, OpenGL, Algorithms

Current series: OpenGL 3.3

18.) 3D Picking Pt. 1

Hello guys! Welcome to 18th tutorial from OpenGL 3.3 and beyong series. This one took forever, because I'm first year on Master's degree on Comenius University, and it took me more time then I thought it would. I also work as programmer (at least in time of writing this tutorial, but I probably will for a long time ). And the rest of my spare time was spent by drumming or with my girlfriend - after a day in a school / work, I just had no mana to write a new tutorial and I better chose to chill out . This tutorial was supposed to be about shadows, but I realized that there are several very basic OpenGL techniques and functions, that should be explained first.

Finally it is here and it is about picking. It's only the first part, because there are more picking methods. So go on, read it and learn something new!

Picking

Picking is a method of selecting 3D object in 2D space. So what you basically want by picking is to tell, which object is rendered on the [X, Y] position of screen. And the most common use for this is to select object, which is at the cursor's position. That's what we are gonna do in this tutorial - we'll click on one of our three common objects (SpongeBob, Alien Creature and Thor ) and then we'll tell which one was clicked. In this first part, I'll describe Color picking method.

Color picking

Color picking is the simplest, yet very powerful picking idea. You render your desired objects off-screen, each one with different unique color, and then you just read back color of one pixel - the one that is under the cursor (or generally, on arbitrary [X Y] position), and you can identify the object with that color. That's it - simple as can be.

Or? Well, idea is really simple, but we cannot just take it and use it without using our brains first . Problem is, that if we want everything to go smooth, we must render whole scene twice. This practically results in FPS halved by 2. So we need to think it through a little first. Rendering whole pickable objects (like models with thousands of polygons) is just wasting computational resources. So instead of rendering whole objects, in this tutorial we'll render only bounding boxes of each model - box just enough to cover whole model. So as we load model, we must remember two opposite corners of bounding box. I decided to go for lower-left-front vertex and upper-right-back vertex, as you can see in this image:

So we'll create two variables for bounding box, which will be updated with every vertex we read:

// Bounding box data - two opposite corners of model's bounding box
glm::vec3 vLowerLeftFront = glm::vec3(999999.0f, 999999.0f, -999999.0f),
vUpperRightBack = glm::vec3(-999999.0f, -999999.0f, 999999.0f);

// Vertex
else if(sType == "v")
{
glm::vec3 vNewVertex;
int dim = 0;
while(dim < 3 && ss >> vNewVertex[dim])dim++;
vVertices.push_back(vNewVertex);
// Update lower-left-front corner of BB
vLowerLeftFront.x = min(vLowerLeftFront.x, vNewVertex.x);
vLowerLeftFront.y = min(vLowerLeftFront.y, vNewVertex.y);
vLowerLeftFront.z = max(vLowerLeftFront.z, vNewVertex.z);
// Update upper-right-back corner of BB
vUpperRightBack.x = max(vUpperRightBack.x, vNewVertex.x);
vUpperRightBack.y = max(vUpperRightBack.y, vNewVertex.y);
vUpperRightBack.z = min(vUpperRightBack.z, vNewVertex.z);
iAttrBitField |= 1;
}

Now that we have both opposite corners, it's enough to build whole bounding box. To do it, we'll create 8 box vertices, and we'll create a function that will render bounding box with indexed drawing (introduced to you in Tutorial 5). So we'll create one VBO for box vertices, one VBO for proper indices, and one VAO to store them both:

// Now create bounding box VAO and VBO

glGenVertexArrays(1, &uiBBVAO);
glBindVertexArray(uiBBVAO);

glm::vec3 vBoxVertices[] =
{
// Front wall of bounding box
vLowerLeftFront,
glm::vec3(vUpperRightBack.x, vLowerLeftFront.y, vLowerLeftFront.z),
glm::vec3(vLowerLeftFront.x, vUpperRightBack.y, vLowerLeftFront.z),
glm::vec3(vUpperRightBack.x, vUpperRightBack.y, vLowerLeftFront.z),
// Back wall of bounding box
glm::vec3(vLowerLeftFront.x, vLowerLeftFront.y, vUpperRightBack.z),
glm::vec3(vUpperRightBack.x, vLowerLeftFront.y, vUpperRightBack.z),
glm::vec3(vLowerLeftFront.x, vUpperRightBack.y, vUpperRightBack.z),
vUpperRightBack
};

int iIndices[] =
{
0, 1, 2, 3, 8, // Front wall
4, 5, 6, 7, 8, // Back wall
4, 0, 6, 2, 8, // Left wall
1, 5, 3, 7, 8, // Right wall
2, 3, 6, 7, 8, // Top wall
0, 1, 4, 5     // Bottom wall
};

vboModelBB.CreateVBO();
vboModelBB.BindVBO();

glEnableVertexAttribArray(0);
glVertexAttribPointer(0, 3, GL_FLOAT, GL_FALSE, sizeof(glm::vec3), 0);

vboModelBBIndices.CreateVBO();
vboModelBBIndices.BindVBO(GL_ELEMENT_ARRAY_BUFFER);

All we need to do is to store and enable vertex attribute 0 - position of vertices. We don't really need anything else - no texture coordinates or normals. The vertices of bounding box in my implementation are numbered this way (it really doesn't matter which order you choose, as long as you provide right sequence of vertices later):

If you look closely, you can see, that after every box side definition, there's index 8 in that array. And you probably already know what this means from 5th Tutorial - it's a primitive restart index. Every side of bounding box is rendered using triangle strip with four vertices. And because we have box defined by 8 vertices indexed from 0 to 7, 8 is big enough to be primitive restart index.

When everything is set up, rendering bounding box is just a matter of few lines of code.

void CObjModel::RenderBoundingBox()
{
glBindVertexArray(uiBBVAO);

glEnable(GL_PRIMITIVE_RESTART_INDEX);
glPrimitiveRestartIndex(8);
glDrawElements(GL_TRIANGLE_STRIP, 29, GL_UNSIGNED_INT, 0);
}

Rendering offscreen

I have already taught you how to render things offscreen using framebuffers. They are good for color picking for sure. But for now, we won't use any framebuffer to perform color picking. We'll just render bounding boxes and perform color picking before rendering scene. If user clicks the left mouse button, we render bounding boxes, read pixel color under mouse cursor, and decide which object was picked from it. Then, we clear depth and color buffers again and continue rendering like normal. Because we don't call SwapBuffers function yet, bounding boxes are actually rendered off-screen and we can't see them. That simple:

void RenderScene(LPVOID lpParam)
{
// Typecast lpParam to COpenGLControl pointer
COpenGLControl* oglControl = (COpenGLControl*)lpParam;

glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
// If user presses LMB, render bounding boxes, read back pixel color and convert it to index
if(Keys::Onekey(VK_LBUTTON))
{
RenderBoundingBoxes(oglControl->GetProjectionMatrix(), false);
iSelectedIndex = GetPickedColorIndexUnderMouse();
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
}

spMain.UseProgram();

// Rendering continues normally...

oglControl->SwapBuffers();
}

Framebuffers will be probably used in second part of this tutorial, but for now not. Problem with them is, that we can resize our window, and then we should also resize our framebuffers to make things work. To have picking exact we should have framebuffers with dynamic size (re-initialize it with every WM_SIZE message). But really, more on that in next part. RenderBoundingBoxes function renders bounding box of each object. Important thing to notice is, that this function must perform the very same transformations that are performed to model, so that it is aligned to model properly.

Let's assign IDs to our objects. SpongeBob has ID 0, Alien Creature has ID 1 and Thor has ID 2. We need to render bounding boxes of these 3 objects each with different color. We can take orange, yellow and blue for example and then map recorded value back to ID. But this is really unnecessary, as we can render objects with colors RGB(0, 0, 0), RGB(0, 0, 1) and RGB(0, 0, 2) (and so on...). When we read RGB value back, we can convert it to corresponding index. If we'd have more than 256 colors, we can use green value of RGB (so object with index 256 has RGB (0, 1, 0), 257th object has RGB(0, 1, 1) and so on). This way we can easily colorpick up to 256*256*256 = 16,777,216 different objects, which should be more than enough (if still wouldn't, you can use RGBA to target 2^32 different objects). However, RGB color (255, 255, 255) is default color, that is cleared, so if we read pure white color from the off-screen render, we know that we haven't picked any object.

First thing we need to do is to create a function, that converts RGB value to index. It's easy - we just binary OR all values together, so that first 8 bits are R, next 8 bits are G, and next 8 bits are B value:

int GetIndexByColor(int r, int g, int b)
{
return (r)|(g<<8)|(b<<16);
}

Then we need kind of an inverse function - we provide index, and we get back the desired color, that's sent right to color shader program:

glm::vec4 GetColorByIndex(int index)
{
int r = index&0xFF;
int g = (index>>8)&0xFF;
int b = (index>>16)&0xFF;

return glm::vec4(float(r)/255.0f, float(g)/255.0f, float(b)/255.0f, 1.0f);
}

If you have problems with these binary operations, check Storing data in computers - it's all about bits article of mine, that should help you.

The last thing that's remaining is how to actually read values from framebuffer. This is nothing difficult - OpenGL provides a function glReadPixels, which does this exactly. You can read arbitrary subregion of framebuffer with this function. So all we need is to read one pixel (RGB value), that's under mouse cursor. But beware, we also need to flip Y coordinate of mouse, because mouse coordinates provided by system are inverted, i.e. 0 is at the top of screen, whereas OpenGL has Y coordinate 0 on bottom of viewport. When we read values, we can get index of picked object:

// This is RGB white in our indexing
#define RGB_WHITE (0xFF | (0xFF<<8) | (0xFF<<16))

int GetPickedColorIndexUnderMouse()
{
POINT mp; GetCursorPos(&mp);
// Convert cursor position
ScreenToClient(appMain.hWnd, &mp);
RECT rect; GetClientRect(appMain.hWnd, &rect);
mp.y = rect.bottom-mp.y;
BYTE bArray[4];
glReadPixels(mp.x, mp.y, 1, 1, GL_RGB, GL_UNSIGNED_BYTE, bArray);
int iResult = GetIndexByColor(bArray[0], bArray[1], bArray[2]);
if(iResult == RGB_WHITE)return -1; // Nothing was selected
return iResult;
}

Now we need to render each bounding box with different color, so that we can differentiate objects when reading values back from framebuffer (the bRedBox parameter is used only for rendering red bounding box in the real scene, so that you can see how it looks like):

void RenderBoundingBoxes(glm::mat4* mProj, bool bRedBox)
{
// Use pure color shader program
spColor.UseProgram();
spColor.SetUniform("matrices.projectionMatrix", mProj);

glm::vec4 vRed(1.0f, 0.0f, 0.0f, 1.0f); // Red color

glm::mat4 mView = cCamera.Look();
spColor.SetUniform("matrices.viewMatrix", &mView);

// Render SpongeBob :D

// Do some transformations

spColor.SetUniform("vColor", bRedBox ? vRed : GetColorByIndex(0)); // Set color with index 0
mdlSpongeBob.RenderBoundingBox();

// Render strange creature found on internet as free model :D

// Do some transformations

spColor.SetUniform("vColor", bRedBox ? vRed : GetColorByIndex(1)); // Set color with index 1
mdlAlien.RenderBoundingBox();

// Render Thor

// Do some transformations

spColor.SetUniform("vColor", bRedBox ? vRed : GetColorByIndex(2)); // Set color with index 2
mdlThor.RenderBoundingBox();
}

Result

Traditional screenshot from the tutorial follows:

I hope this tutorial helped you, because 3D picking is a very important thing in creating 3D applications and games. Color picking is very good to use, but it has some limitations. Can you think of some flaws that are in this tutorial? I'll give you a hint - try to go below the floor and then click on Thor (which you can't see from below) - he's selected still! So this idea should be extended. How, you can read in the part 2 of this tutorial. We will also have a look at how to read back the actual 3D value of a point we click onto (unprojection of vertex, this is commonly used in any for example RTS games to move along map).

We have created some new VAOs and VBOs in CObjModel class, so we cannot forget to delete them in DeleteModel function.

I really hope that such an extremely long delay (over 3 months from last tutorial!!! was the last one from me ). If you have additional questions, comment or e-mail me .

Name:

E-mail:
(Optional)
Entry:

Enter the text from image:

Smileys

 U0MWIVJKr (0cj44ti4hu@outlook.com) on 15.12.2015 15:52:31 Wrong specs theres are true as in now up to date 9/27/2012Both bulndes include a basic AC adapter and an HDMI adapter for 1080p gaming. Nintendo claim the Wii U is around 20 times more powerful than its six-year-old Wii console.Nintendo president, Satoru Iwata said the Wii U will have 1GB of system memory and 1GB of game memory for 2GB total, that’s compared to PS3 and 360′s 512MB.The Wii U uses 75 watts of power when operating and 45 watts in power save mode. It measures 46 mm x 172 mm x 268.5 mm in the horizontal position.
 g8yTd0Nw8To8 (p31op209n@outlook.com) on 15.12.2015 15:51:28 never in the history of this pleant did a company called IBM confirm any such thing IDIOT they confirmed a link to it il explain those links so you can stop being a herp derp 45nm process silicon on insulator process IBM EDRAM there are your links to power 7 FOOL the cpu to any level headed sane human being are as follows POWERPC 400 SERIES AT 45NM WITH BROADWAY FIED CORES X 3 WITH CUSTOM EDRAM CATCH 512K X 2 AND A 2MB CATCH TO A SINGLE LETS SAY TURBO CORE the above is also known as COMMON FLAMING SENSE
 zPtfYdhwN7cq (rp8kmebg@hotmail.com) on 11.12.2015 21:17:49 Las especificaciones te9cnicas que ha fdatrlio VGleaks son completamente ciertas, la CPU ahed descrita no debereda tener un tamaf1o superior al del Broadway en cuanto a e1rea, la GPU vendreda a ser como la que describe la patente que he comentado hace unas horas y ademe1s el tamaf1o combinado de la GPU y su eDRAM en cuanta a e1rea no sereda superior al que ocupa el Hollywood de Wii, por faltimo 1GB de memoria DDR3 hoy en deda puede venir en un chip, como los 64MB DDR2 de la MEM2 de Wii. En otras palabras, Nintendo mantendre1 la misma estructura de costes de Wii en Wii U en cuanto al hardware se refiere.
 OIPRIVBlOKt (xx8g6qh2m@mail.com) on 11.12.2015 20:37:22 GPU has got to be based on HD4670,,, its just got to be, the peak texture rloseution and the opengl and shader specs are all totally in line with a spec break down of the HD4670 the wiiU started development in 2008 also the year of the HD4670 the rops are clearly 8 rops,, rayman developer talked of high fillrates AND big high res textures and theres 2 x screens to support that all looks very high texel fillrate to me and HD4670 has 32 texture units its a perfect gpu for amd to tweak and upgrade and die shrink and license to nintendo HD4670 is a 55nm chip shrinking to 45nm to match the cpu is easy or even a 40nm shrink i cannot see the gpu remaining at 55nm if in fact it is a HD4670 that gpu refined and with a big bandwidth edram would be a huge fillrate beast and added fixed funtion to boost overall performance like say hollywood tev and effects for both back ward play and wiiu assistence to shaders etc i got my casino chips on CUSTOM HD 4670 CORE
jaey on 03.03.2013 21:22:20
Hi! I love your tutorials!!!!!!!! I'm just learning opengl for a project and u need to know how helpful your tutorials have been. Like seriously, thank you!!
When will the part 2 of this picking tutorial be out pls?

Soon? Pls? Thanks again! :D
 Michal Bubnar (michalbb1@gmail.com) on 29.04.2013 17:01:40 I released it today. Dat time of response
 Evan on 29.01.2013 20:11:12 These tutorials make me happy. =D
 Biggy Smith on 08.01.2013 03:35:17 I've been working thru your tutorials recently to refresh my opengl skills and I've just started thinking that picking would be useful and I check back here and a picking tutorial appears! Great work, keep it up.
Sebastian on 29.12.2012 21:02:08
Useful. Are you planning create tutorial for point light shadows?
 Michal Bubnar (michalbb1@gmail.com) on 29.12.2012 22:57:54 Yes, shadows will come, not that far from this tutorial. But first I want to go through picking, occlusion queries and such easier things, which just require some basic OpenGL functions, and then I'll go to things like reflections, shadows, caustics etc...