Megabyte Softworks
C++, OpenGL, Algorithms

Current series: OpenGL 3.3

19.) 3D Picking Pt. 2

Hi guys and welcome to 19th tutorial from OpenGL 3.3 series! This one took me long to create, it’s for my lack of time and even if I have some free time (not much), it’s late in the evening (23:00+ local time), so I really don’t have much mana to create something :D But don’t worry, once in a while the feeling of guilt for not writing tutorials grows so strong, that I just write one against all odds :D This is the case, I hope you enjoy it, it’s not too long nor too difficult.

This tutorial is the continuation of the first tutorial 3D Picking Part1, where we used a bounding box rendered “behind the scenes” to find an object user has clicked on. Problem of this method was that bounding box doesn’t match model very much. So the solution is to either render full model in color mode or use multiple bounding boxes. Either way or another, previous tutorial used color picking for finding what a user has clicked on. This time we will use completely different approach and it’s ray-casting pick.

Ray casting

The key to this tutorial is to find a ray in 3D going from near-plane to far-plane. We click on a point on 2D screen and we need to generate two 3D points - one close to us (one on near-plane) and second deep in the 3D screen (on far-plane). Then we have two points that define a ray. This ray is used to find an intersection with an object on a scene. So basically we need to check which objects our ray intersects. We can check it against whole model (like checking every triangle against the ray), or do it somehow easier, but less exact again. We use an invisible sphere that every object on a scene has to check collision of our ray with. And because sphere is a nice mathematical object and can be expressed with a pretty easy equation, finding collision of a ray and sphere is nothing difficult. So these are two objectives of this tutorial - find a ray in 3D and then find an intersection of this ray with objects on the scene and determine, which object was hit by ray and thus selected.

Finding ray

First objective has to do with projection. I will simplify this and I won’t explain to you how projection matrix exactly works (to be completely honest, I know what it does, I can google it’s equations, but I wouldn’t write a projection matrix to you just from head on request). I’m just gonna remind you what such a projection matrix does. Projection matrix takes a point in eye-space coordinates and PROJECTS it onto 2D screen. So the result of multiplying vector in eye-space coordinates and projection matrix is a point in normalized device coordinates (ranging from -1 to 1), which is then drawn to 2D screen for example. So one way - going from 3D to 2D is easy - we just need to PROJECT point and this operation is injective - every 3D point will map to unique 2D point.

But our task is to do the inverse - we must convert 2D point back to 3D, thus UNPROJECT. However this operation isn’t injective - there is an infinite set of 3D points that project to 2D point. That’s because we’re missing the third coordinate on 2D screen and it’s Z coordinate. This set of 3D points that project to our desired 2D point is exactly the ray we’re looking for! We just need to unproject clicked 2D point on near-plane (Z coordinate is 0.0) and on far plane (Z coordinate is 1.0). This way we get two 3D points and we’re done finding the ray! This picture should help you to understand whic ray we're picking even better:

Now the implementation part - all we need to do is to write an unprojection function. Or do we need to write it? Library glm provides us with such function so there is no need to write our own :D It takes 4 parameters:

• glm::vec3 screenPos - 2D position on screen and depth parameter - it's from 0.0 to 1.0 and determines the depth after projection (we can also get actual Z from depth buffer)
• glm::mat4 modelviewMatrix - modelview matrix currently used
• glm::mat4 projectionMatrix - projection matrix currently used
• glm::vec4 viewport - viewport parameters used for clipping

But still I recommend you to look on its implementation in glm to get an idea how it works, for example I had to code unprojection function myself when I was developing on iPads in C# (just right click on Go To Definition in Visual Studio 2008). So we just need to write a code that gives us a ray from given 2D point (the one under mouse cursor in this case):

void Get3DRayUnderMouse(glm::vec3* v1, glm::vec3* v2)
{
POINT mp; GetCursorPos(&mp);
ScreenToClient(appMain.hWnd, &mp);
RECT rect; GetClientRect(appMain.hWnd, &rect);
mp.y = rect.bottom-mp.y;

glm::vec4 viewport = glm::vec4(0.0f, 0.0f, appMain.oglControl.GetViewportWidth(), appMain.oglControl.GetViewportHeight());

glm::unProject(glm::vec3(float(mp.x), float(mp.y), 0.0f), cCamera.Look(), *appMain.oglControl.GetProjectionMatrix(), viewport);

}

The first part is done, now let’s get to the second part.

Finding collisions

For the sake of this tutorial, we'll approximate all four objects on the scene (there is a new object - a black hole ) with only a simple sphere, that has a position and radius. As it was with bounding boxes, this approximation is far from optimal, but this tutorial just shows you the way how to do things, you can always build upon them to create something better (use more spheres, boxes, or primitives in general to approximate model). How to find collision between a ray and a sphere? Nothing difficult, whole work can be split into two parts:

• 1.) Finding closest point lying on ray to the center of sphere
• 2.) Checking if distance between center of sphere and found point is less than radius of sphere

The first part is obviously more difficult and involves some math to be done. But really not that much. All we need to do is to project center of a sphere to a ray using dot product. This just means, that using dot product you'll get the line equation parameter for a closest point (let's call it t). With this t we can insert it into line equation LINE = A+ t*dir, where dir is normalized direction of line (B-A) and get the closest point. However, notice that ny calculations work with the ray as it was just a line segment, not whole infinite line, so the closest point can also be point vA or point vB:

bool RaySphereCollision(glm::vec3 vSphereCenter, float fSphereRadius, glm::vec3 vA, glm::vec3 vB)
{
// Create the vector from end point vA to center of sphere
glm::vec3 vDirToSphere = vSphereCenter - vA;

// Create a normalized direction vector from end point vA to end point vB
glm::vec3 vLineDir = glm::normalize(vB-vA);

// Find length of line segment
float fLineLength = glm::distance(vA, vB);

// Using the dot product, we project the vDirToSphere onto the vector vLineDir
float t = glm::dot(vDirToSphere, vLineDir);

glm::vec3 vClosestPoint;
// If our projected distance from vA is less than or equal to 0, the closest point is vA
if (t <= 0.0f)
vClosestPoint = vA;
// If our projected distance from vA is greater thatn line length, closest point is vB
else if (t >= fLineLength)
vClosestPoint = vB;
// Otherwise calculate the point on the line using t and return it
else
vClosestPoint = vA+vLineDir*t;

// Now just check if closest point is within radius of sphere
}

And that does the trick! All we need to do now is to use our two function to find a casting ray and collision with sphere approximating object with it!

Result

As always screenshot from the tutorial follows:

Today I showed you how to use ray casting to pick objects in scene. Of course, it's just basics, because it's not very exact, since sphere isn't a great aproximation of an object (but if object is a spherical black hole, then it is totally enough ). Anyway, I hope I enlightened you this approach and you can now build upon it. I also programmed sphere creation by myself, you can have a look in static_geometry.cpp to see how sphere can be generated (it's my own code, I hope you'll understand it, but if not, nothing happens, similar sphere generation codes can be found anywhere on the internet ).

And forgive me really my delays, I'm so unreliable in this . If I hadn't had school and work, it would have been better for sure . I'm also drummer in some local bands here, and I'm planning to post some drum covers on youtube (and then i will provide you links so you can see me . Be patient, next tutorial will be about loading models using Assimp library, so stay tuned !

Name:

E-mail:
(Optional)
Entry:

Enter the text from image:

Smileys

 CWMSgImYa2 (yzbulazc3@hotmail.com) on 15.12.2015 15:52:42 I just now wanted to thank you once again for your aizmang blog you have made here. Its full of useful tips for those who are truly interested in this subject, primarily this very post. You really are all aizmangly sweet and also thoughtful of others and also reading your site posts is a superb delight in my experience. And exactly what a generous present! Jeff and I really have pleasure making use of your suggestions in what we have to do in the near future. Our record is a kilometer long so your tips will definitely be put to beneficial use.
 RmMSIafEb5 (i40zipuzc@mail.com) on 11.12.2015 21:32:03 I needed to send you a bit of note just to thank you very much once again on your buiutafel tactics you have shown here. It's certainly unbelievably open-handed with people like you in giving extensively all that most of us could have offered for sale as an ebook to end up making some cash for themselves, and in particular seeing that you might have done it if you ever wanted. These tips as well served to become easy way to be certain that the rest have similar zeal just as my very own to grasp significantly more concerning this matter. I am certain there are many more fun moments ahead for people who discover your site.
Mystery Keeper (mystkeeper@gmail.com) on 23.06.2013 16:50:07
Why not just use color coded off-screen drawing? Isn't it way more efficient?
 Michal Bubnar (michalbb1@gmail.com) on 23.06.2013 17:27:05 Yea, it's true, it's been explained in previous tutorial, however with rendering only bounding boxes. I just wanted to show another approach. I'm aware that this one is not that useful for this purpose.
 hatfarm (hatfarm@gmail.com) on 26.05.2013 19:09:09 Any advice on picking AABB's in 3d with this method? I tried to implement it myself and I had some serious issues.
Dmitry (dmitry.trok@gmail.com) on 03.05.2013 10:16:14
Michal !
You lessons is weary well, thx. In you next tutorial model will be loaded with bone animation ore not ?)
 Michal Bubnar (michalbb1@gmail.com) on 05.05.2013 19:49:18 Thank you I'm planning to do it, but not right next tutorial. Anyway I'm going to update this 19th tutorial soon, for there is a serious flaw there, I thought I did mention it in article but I didn't so I will update right after I finish and present one project in my school at 7th May, then I will have some time to do it