Tutorials
Articles
OpenGL Demos
Games
OpenGL Misc
MSG Board
About
Donate
Links
Home
Megabyte Softworks
C++, OpenGL, Algorithms




Current series: OpenGL 3.3
(Return to list of OpenGL 3.3 tutorials)

Download (4.07 MB)
4100 downloads. 6 comments
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);

and during loading, we'll update it accordingly:


// 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();

FOR(i, 8)vboModelBB.AddData(&vBoxVertices[i], sizeof(glm::vec3));
vboModelBB.UploadDataToGPU(GL_STATIC_DRAW);

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

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

vboModelBBIndices.AddData(iIndices, sizeof(iIndices));
vboModelBBIndices.UploadDataToGPU(GL_STATIC_DRAW);

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()
{
   if(!bLoaded)return;
   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;
   // Read only RGB value
   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 .



Download (4.07 MB)
4100 downloads. 6 comments
 
Name:

E-mail:
(Optional)
Entry:

Enter the text from image:



Smileys




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...
Jump to page:
1