Picking Techniques

General Discussions
#1

I’m really interested to know what is the “best” approach and then what are people actually using in real world projects (as they may not be the same) for picking

I have been looking at different ways to implement picking in my game engine.

Based on my research so far i have found the following techniques:

  1. Color Picking.
    This basically involves quietly re-drawing your entire scene but using a different color for every artifact. Then use the GL pixel at approach to determine the color at X,Y. This color will only match one of your objects… (assuming you managed to keep them all unique colors)

A decent approach but it eats up noticeable FPS cycles.

  1. True ray casting
    Calculate the normal and plane for each model and then determine the closest intersecting point.

Ok this sounds nice an generic … but the math on this still escapes me… Especially for my models that have lots of angles and faces… So unless im missing a trick on this approach it sounds good but hard to implement.

  1. Camera depth picking
    I tripped over this one… as it didnt seem like a popular approach but i found the strategy to be interesting. Using Opengl change the perspective to “zoom” really tightly into where the mouse is. Next call glRenderMode(GL11.GL_Render) and you get the count of artifacts draw to the screen. The closest one is your winner.

  2. GL pick list
    You assign a name to each model and then ask OpenGl to tell you what you clicked on… which sounds great! only this feature appears to be dead in current releases…

So what are people actually using??

For my purposes im most interested in 3D applications

thanks!
j.

[edited] - corrected typo… grr typos…
[edited +1] - added type 4 OpenGL Pick List

#2

The thing is ray casting gets trivial when you include collision detection into your game, something probably every game has. Most of the time your physics-engine will handle this for you.

#3

Interesting. I do have a physics engine currently in my game and I already have raycasting working with it. But this implementation is limited to models that the physics engine knows about.

If i had a raycasting technique that worked more generically then it would cover models outside the physics engine also.

Based on your comments i may be overkilling my solution then?

#4

Option #2 is definitely the way to go I believe: give each object in your scene a bounding volume (axis-aligned box or sphere are simplest), determining ray-volume intersection is relatively trivial, and there are plenty of tutorials out there on this approach.

One of the advantages of this is that you can re-use the same functionality for picking, collision detection (as Danny02 mentions) and frustum culling if you need them.

For the others options:

#1 and #3 are a bit clunky IMHO and I doubt are used in any ‘real’ projects or games.

#4 just plain sucks :wink:

  • stride
#5

Thanks for the input stride.

Unfortunately I find lots of posts saying doing 2) is the best approach. Some say its really hard. Some say its super easy. And I have yet to find one that actually gets into the details of how this is done in laymen terms.
Most that claim to do so have links to “examples” which at this point all seem to be broken links. (very frustrating)
Even searching the Game Mechanics section of this forum has lead to little more than confusion (and more broken links) on my part.

The concept is simple enough. Simplify the collision detection by making a box or sphere around your model to act as a boundary. (this is a theoretical entity and never drawn to the screen) then test if a line from unproject mouse click x,y,0 to unprojected x,y,max_ray_distance intersects the the bounding shape.

Now add in rotation and transformation and things seem to be more complex… (not to mention im still not clear on the equation to support the simple case)

So I guess I’m really looking for a real world example of “option 2) ray tracing”. Anyone go one?

#6

Agreed that searching is mighty frustrating, the quality of some of the ‘guides’ out there is questionable (when they still exist!) so I bookmark any good ones I find. Will dig out some links when I’m back on my own machine at home and maybe some code if appropriate.

EDIT: Actually just remembered a good one, I based my implementation on this tutorial, explains the maths if you need it and provides some pretty pictures :slight_smile:

http://antongerdelan.net/opengl/raycasting.html

Note this is just pure 3D, i.e. maths, as opposed to OpenGL. It assumes you’re using custom model-view-projection matrices rather than the ‘old’ style of getting GLUT or something to do it for you.

#7

Thanks for the link. I will study it and let you know how i make out.

#8

Use a physic engine and call it a day.

#9

a physics engine seems like overkill, if all i want to do is build a pretty 3D menu …

#10

This is what I use in my engine: http://pastebin.com/6KQvTTj1

It should work if you split the components in your menu into triangles.

#11

So, this is 3D ray picking correct? You could implement this to work with face picking? If so, you just saved me from having to figure out a lot of math!

#12

I don’t see why it shouldn’t work for you, so yes. :wink:

This video demonstrates it in my engine.

#13

Hi Simn,

You would you be willing to share your Vector3 class. Im trying to read through and understand all of the code and it looks like some of the math is in it.

“Vector3().computeNormal(v1, v2, v3);”

thanks
j.

#14

Here you go: http://pastebin.com/aNfTxe9h :wink:

#15

It’s always handy to sketch what you want to do rather than how you think you want to do it. Chances are you don’t need to be able to pick.

#16

Hi Roquen,

I appreciate the input…

My game is a 3D one. I have built the engine from scratch.
One of the features i need to support in my game is the user clicking on 3D objects and being able to determine what they clicked on and sometimes what part of a model they clicked on specifically.

For this raycasting / picking seemed to be the answer. If there is another technique you think would be simpler I would welcome the suggestion.

thanks
J.

#17

Ok…that’s quite different from a 3D menu system. Back to my original answer: use a physic engine and call it a day.

#18

If you dead against a physics engine, or like me didn’t want to waste time with one for just picking. I found that ray tracing with bounding spheres worked awesome. I was picking things on objects too. I used a hierarchy of such spheres for that. I would group them a bit with bounding spheres as well if there are lots of objects on the screen. Note that its very easy to check if a ray intersects a sphere. For odd shapes i use more than one sphere.

Not sure about pixel perfect however. My models have quite a lot of triangles if up close.

#19

Update

So i have some working code for ray picking with Pixel perfect accuracy !
ok perhaps that was overkill but its easy enough to scale back.

Right now i have test code and a test scene for testing the feature.

Would there be value in me sharing this with a code post and video for the community ?

j.

#20

Oh definetly! Even if I don’t use it(I’ll look at it), I’m sure others would benefit from it greatly.