Picking Technique Opinions

Hi all,

I’m currently finishing up my project on OpenGL selection/picking techniques. I looked at GL Selection (or native selection as I call it), Color-ID buffering in the backbuffer and Ray-intersection (shooting a ray through a pixel an intersecting it with surfaces.

I measured the speed of these methods under a range of circumstances (random polygons, polygon meshes, flat and hierarchical scenes…) and by far, the ray method was the fastest and most accurate. GL Selection came second, and Color IDs a distance third (I guess it is because you have to redraw the scene)

To round everything off, I woundered if I could get you’re preferences, as OpenGL developers, as to which technique you prefer (or any other methods I haven’t mentioned).

Is GL Selection to cumbersome? Ray Intersection too specialised? Are some methods better for games than modelling apps?

Give me you’re opinions. 3D picking is generally not a well-documented technique, so part of the project’s aim was to implement and evaluate the methods available.

When it’s finished, I’ll be happy to provide the code for anyone who wants it.

If you’re only interested in the 3D position of the picked point, you can always use gluUnproject to retrieve the coordinates.

N.

My €0.02

Generally if in doubt, I would always go for something image-based, as what are you to do if you want to pick an object with alpha masked surfaces? The ID buffer sounds like the most robust solution, maybe the ID buffer could be rendered in one go via multiple render targets?

But if that is not an option, ray tests on the CPU may be the fastest, as they can go in parallel with rendering.

Actually, I gave up with gluUnProject. I could never get it to work. It was easy to just build my own prjection mechanism, but that required me to store each transformation on an object, and it’s inverse through which to project the ray.

And yes, Color Buffering was the most robust method. Far simpler to code and easier to expand. Just want to select points? Simple. Render them in a different color. Polygons? Just give them a unique color and so on. You can’t do that with rays, and GL Selection is just to clumsy. The trade off is a second render, but it’s a minimal cost if you avoid swapping buffers and only render the surfaces that can actually be picked…

… and GL Selection is just to clumsy.

Hold on now.

I’ve been using selection in my editor for years, and I wouldn’t trade it for anything. True, if you’re after sheer speed, you could arguably do better with another method, but for editing, selection is plenty fast enough, and incredibly robust, if setup properly.

I’ve been using GL picking for some months and it’s been reliable and fast. Soon though I want to implement a “hover-over” help type mechanism and I already know that GL picking is way too slow for this if attempted every frame/ every other frame (~400 objects on a GF2). Any suggestions?

Ok, so maybe I was a bit harsh with that comment. But it is a very crude mechanism. Although it does generally work well, it occasionally selects the wrong object in scenes comprised of many overlapping surfaces. As for hierarchies, the only way to handle them is to continually pop ever more names on the namestack, which isn’t efficient and can make the code hard to read - especially when you’re using many classes and the code is split between files.

And of course, there’s the cost in the 2nd render, and the occasionally difficulty in setup up the projection matrix…

But this is what I want to here. From what I’ve read on other boards, GL Selection doesn’t seem to be very popular, especially in games where a consistent framerate is important.

Am I completely wrong here?

I wasn’t aware that this was a contest for the “best method in the universe” award. There is rarely a wonder method for all occasions in any area of graphics. As I said, selection works for me in editing. In other contexts, I use various tracing techniques; it just depends on the situation. I think it is rather foolish to publicly condemn a method simply because it’s unattractive to you in one particular context, or doesn’t appeal to your sense of neatness. And I would hardly call selection “crude”, that’s simply a pretentious boast. I’m sure the creative minds behind selection would love to discuss that one with you, over some hot tea, perhaps.

As for hierarchies, the only way to handle them is to continually pop ever more names on the namestack, which isn’t efficient and can make the code hard to read - especially when you’re using many classes and the code is split between files.

Well, pushing and popping names is part of the process, I agree. However, I’d like to see your benchmarks on pushing and popping the name stack; I seriously doubt if that could even be measured reliably. As for the code being split across files, how is that related to this discussion?

And of course, there’s the cost in the 2nd render, and the occasionally difficulty in setup up the projection matrix…

The cost of the second render can be negligable if you are intelligent about your scene graph traversal. And if you have trouble with the projection matrix, perhaps you should find some good books on linear algebra.

Am I completely wrong here?

Maybe you should try to answer that one for yourself.

edit:

added a smiley face

Color selection is useful, if you want to pick only one (nearest) object - and of course, as mentioned before, alpha masked objects.

The picking mechanism allows to select multiple objects in a row, which is really useful, if it isn’t very clear, which object should be selected (I find it very useful, to be able to select objects behind other objects - especially together with a somewhat intelligent hover/highlighting mechanism - and I feel that OpenGL selection mode is up to the task even for many objects (it’s probably done on the CPU in most cases anyway, so there is no need to implement own ray/polygon intersection code)).

As in many occasions with OpenGL I have the strong feeling that people did actually think before implementing it, when using selection mode.

Yaw!!! Put the claws away, please!

I’m not being pretentious. I’ve studied these three techniques in particular, implemented and tested them against a range of criteria for the last year. The subject doesn’t seem to be well documented (as the sheer number of posts to this board on the topic should justify), when compared to the likes of shading or antialiasing etc. even though to me, user interaction seems to be critically important in graphics.

Technically, it’s actually quite hard to determine the surface projected below a specific screen pixel; hats of to SGI for actually bothering to implement a selection mechanism at all. Larger commercial efforts, likes PHIGS didn’t bother, because of the inherant problems.

There are several techniques, and the objective of this thread was to determine the consensus, among serious OpenGL developers - ie. you - as to which method was most appropriate in the typical case. Of course, they will never be a one-size fits all solution.

I just wanted to enrichen my final report with the views of the very people is was intended to benifit, by providing a serious study and evaluation of the area.

Had I known the response was going to be this hostile, I needn’t have bothered.

I regret that you percieved my comments as hostile - I knew I should have added more smiley faces. I merely meant to point out some flaws I found in your argument. You did ask if you were wrong, didn’t you?

You’re right, selection in gl in not very well documented, and a naive implementation is not going to cut the mustard for any real application. Setting up a robust selection framework is not a trivial enterprise. I suspect that is why the technique is often brushed aside in favor of simple methods that work reasonable well out of the box, e.g,. color id. This was the motivation for my comments; I just don’t think you can fairly characterize the merits of a techique with only a trivial understanding of it.

Anyway, good luck in your picking quest, and may the force be with you.

How can you assume I have ony a trivial understanding of the technique? Thats a little arrogant on you’re part, is it not? I have been studying it and other techniques for my Degree Dissertation for over a year.

I remember now where I got that comment:

“Although the OpenGL selection mechanism (see “Selection” in Chapter 13) is powerful and flexible, it can be cumbersome to use.” OpenGL Programming Guide, p392

NYAH!

I’m a long-time fan of color-ID, but I’d advise only using it if you can amortize the cost over many calls or you can greatly focus and optimize. It’s not a general-purpose win.

You didn’t specify this one way or another, but some people implement color-ID by re-rendering the whole scene to a normal-sized framebuffer ahd then find the X,Y projection of the ray on the resulting image plane (worst case reading the whole image back first). That’s actually somewhat reasonable if you’re testing a very large number of rays at once.

For resolving a scattering of rays with the color-id technique, you might actually decide to render to most of the viewing frustum, but here at least you can pre-mask the pixels that you don’t care about to reduce the fill cost. If you had hardware histogram, this readback would be on the order of a few bytes per ray with such masking.

But for a single ray, you’d want to first cull the scene to a 1 pixel-wide frustum and render to a 1x1 framebuffer only to resolve the z-order (which I understand is essentially what gl picking does, only in software since it’s just one pixel). So for a single ray, I think it can be shown that using the framebuffer for picking will only be faster if the depth complexity is impossibly large. For your project, you might want to determine “how large” for a given CPU/GPU combo.

On occasion, it’s possible to use the color-tag render as the first pass of a more complex shading technique, since colors may get overridden anyway (often, they are used as interpolants, so tough luck there). Difficulties include the wait between the first and subsequent passes, and handling things like alpha surfaces, which you’d make either 100% opaque or transparent for picking purposes (no blending allowed).

There are other techniques, of course. Another method involves maintaining screen-space bboxes for objects and using that to accelerate picking. In one case, a system I worked on rendered only a small set of unique primitives, so the screen-space bounds could be computed algorithmically and very easily for final visibility/pick resolution in 2D projected (even head-centered spherical) space. Lots of options, depending on the design and constraints of the engine.

Hope this helps with some of the options and tradeoffs.

Avi

Thanks for the info! That was really useful!

just in case someone was still curious about using gluUnProject here’s the URL for a quick little tutorial of sorts on how it works:

http://nehe.gamedev.net/data/articles/article.asp?article=13

good for simple quick and dirty get the prototype going programming