PDA

View Full Version : Selection / Picking in OpenGL 3.2



Kip Warner
12-12-2009, 07:31 PM
The Red Book (GL 3.0 / 3.1) states that all of the selection / picking routines discussed in chapter 13 are deprecated. That's fine, but it doesn't explain what they are superseded by. Can someone point me in the right direction for how we are expected to perform picking in OpenGL >= 3.1?

Aleksandar
12-13-2009, 04:26 AM
It is a very interesting question!
There are other posts on this forum discussing that topic, but none of them gives a satisfying answer.

Until you develop some efficient method of your own, I suggest you to switch to GL 3.2 Compatibility mode, and you'll have all deprecated functionality along with the core.

By the way, I have recently tested GL 3.2 Core against GL 1.5 on the same driver (geforce 190.89) and the speed gain is about 5%. The scene is very complex and there are tens of thousands VBOs, and special traversal algorithm. So, GL 3.2 Core is faster, but application is not only drawing, and switching to new model does not mean a speed boost for sure.

Ilian Dinev
12-13-2009, 05:03 AM
What happened to colour-tagging :) ?

Aleksandar
12-13-2009, 05:22 AM
Not good enough! :)

Disadvantages of color-tagging:

1. Drawing has to be reorganized with lighting and texturing and fogging and EVERYTHING ELSE switched off.

2. No hierarchical organization. This is the most important issue! In the "standard" way of picking I know, for example, that I have picked a window, belongs to the particular building, reside in particular terrain block. It cannot be achieved (or to be more precise, not easily) by coloring.

I can quote other disadvantages if those are not enough, but ... I think they are. ;)

Jan
12-13-2009, 05:23 AM
The problem is that picking is horribly slow on most drivers, because it is done in software. That means, you shouldn't use it, AT ALL, no matter what version of GL you are using.

The best way to replace it, is to use color-picking or however it is called. Basically you give every object a unique ID and then render it with the ID packed into its color. Then you read the color from the framebuffer (glReadPixels) and thus have the object ID at the pixels position.

Of course you need to implement all that yourself via shaders etc.


Jan.

Ilian Dinev
12-13-2009, 05:52 AM
32-bit or 64-bit values: instead of colors, you put pointers; a fbo without MSAA/CSAA. What fogging, lighting? You code one shader to write the group, and one shader to write the triangleIDX. First you draw the groups with shader_1, until you find the precise one; then you draw that group with shader_2 to find the triangleIDX. With a shader_3 and rgba32f fbo you could also output up to 16 or 32 float varyings that the VBO provides.
Right?

zeoverlord
12-13-2009, 05:57 AM
Not good enough! :)

Disadvantages of color-tagging:

1. Drawing has to be reorganized with lighting and texturing and fogging and EVERYTHING ELSE switched off.

Actually since in 3.0 you always have to supply your own shaders to render, this is a moot point, just insert a basic color pass trough shader and your good for the entire pass.




2. No hierarchical organization. This is the most important issue! In the "standard" way of picking I know, for example, that I have picked a window, belongs to the particular building, reside in particular terrain block. It cannot be achieved (or to be more precise, not easily) by coloring.

Well you do have 4294967296 different colors to choose from and using a simple lookup table or even encode it in the color itself will fix that




I can quote other disadvantages if those are not enough, but ... I think they are. ;)
the largest one is that it requires glReadPixels that has the effect of stalling the CPU, though there are ways around this.
Another one is that your using rendering resources as opposed to if you where using a ray tracing method instead, though that problem can be minimized.
However i would like to see a extension or two to make this easier, basically something like occlusion testing that gives you a list of the closest few fragments rendered on a certain position and a integer/object ID rendering buffer (that is if no such thing exists, haven't checked)

Aleksandar
12-13-2009, 06:46 AM
The problem is that picking is horribly slow on most drivers, because it is done in software... Then you read the color from the framebuffer (glReadPixels) and thus have the object ID at the pixels position.
Reading from the framebuffer is also slow. I have never experienced a performance issue, because picking can happen once per few seconds.


32-bit or 64-bit values: instead of colors, you put pointers
Yes, it can be useful, but you need a hierarchy in RAM and efficient algorithm to traverse that structure to find appropriate part of the hierarchy. If I have tens of thousands terrain blocks with tens of buildings, each with tens of windows, I need to traverse that tree to find appropriate. How if I only have a pointer to the window?

Having a just coloring shader is OK! I agree with that. But if I have to support a fixed functionality too, it can be more complicated. Nevertheless, I agree that disabling everything except colors is not difficult at all with shaders.


Well you do have 4294967296 different colors to choose from and using a simple lookup table or even encode it in the color itself will fix that
The number of values that can be represented is not an issue. But, as you have already mentioned, you need additional structure to map it (if they are not IDs or pointers), and the problem of hierarchy stays.

pjcozzi
12-13-2009, 07:27 AM
An alternative to color picking is to use the depth buffer. First, shrink the view frustum so it just fits around the picked pixel(s). Make sure you render the scene with view frustum culling for best performance. Before you render an object clear the depth buffer and after you render an object read the depth buffer. If it wrote depth, the object was picked. If multiple objects were picked, you can sort them based on depth.

Assuming your objects write depth, this algorithm doesn't require any changes to your rendering code. Although, as an optimization you will probably want to change your rendering code. For example, I usually trim multi-pass algorithms down to a single pass when rendering an object for picking.

I wrote a blog about this algorithm a while back: Picking using the Depth Buffer (http://blogs.agi.com/insight3d/index.php/2008/03/05/picking-using-the-depth-buffer/).

With all this said, I still really like the simplicity and speed of color picking. I'm surprised no one has mentioned ray casting yet.

Regards,
Patrick

Jan
12-13-2009, 07:42 AM
"Reading from the framebuffer is also slow. I have never experienced a performance issue, because picking can happen once per few seconds."

You have never done picking on a scene with millions of triangles, have you? I tell you it is HORRIBLY slow in a detailed scene, when it has to go through a software-renderer (taking SECONDS). The read-back from an FBO is nothing compared to that. Of course this method is supposed to be done in editors and such, where you really want to pick pixel-precise, and a minor lag is no problem, but people get pretty cranky, when they have to wait 2-3 seconds every time they (accidentally) click somewhere.

On small scenes this is not an issue, but then simply doing a brute force raycast on every triangle wouldn't be a problem either...

Jan.

Aleksandar
12-13-2009, 08:15 AM
You have never done picking on a scene with millions of triangles, have you? I tell you it is HORRIBLY slow in a detailed scene, when it has to go through a software-renderer (taking SECONDS).
I did! And, because I haven't noticed such delay, I doubt that it is done in software. I'll measure tomorrow how many triangles are drawn and what is the frame rate, but I'm sure that is is far less than a second with more than a million triangles.

Jan
12-13-2009, 10:14 AM
Well, then you are lucky to have a GPU/driver that might do it in hardware. Maybe some vendor has actually improved his implementation of the feedback mode recently, but i know of several programs that use that mode and have big performance problems (in university every student is told that feedback mode would be great and thus all those newbies go ahead using it and when their apps start getting more complex they begin crying about bad performance in feedback mode).

But i have used it several years ago myself and had the same issues myself.

Basically it's the same story again and again: Use a difficult to support feature (feedback buffer, display lists, accumulation buffer, several old extensions, ...) and you are dependent on the IHV how well your app runs. Often you will become dependent on ONE IHV (usually nVidia) because they support it well and others don't. Sometimes you even become dependent on a certain OS.

I like independence, portability and having future-proof code (or at least code that is not PROBABLY going to break some time soon). That is why i don't use the feedback-buffer, even if it might work on MY machine.

I agree that it is difficult to implement the exact same thing that the feedback buffer provides via shaders, but usually people only use a subset of its features anyway (closest object selection). In that case color-picking is a really good replacement that can be implemented without much problems in short time.

Jan.

Aleksandar
12-13-2009, 11:00 AM
Thank you Jan for a very comprehensive overview.

I couldn't wait until tomorrow, so I carried out some experiments at home... and the results are:

================================================== ============
Experiment 1.

- Rendering time - 31.25ms
- Picking time - 85.716ms
__________________________
Picking time is about 2.75x longer than a regular frame time.
Memory utilization is on the edge, and application didn't perform normally.

================================================== ============
Experiment 2.

- Rendering time - 7.5ms
- Picking time - 19.169ms
__________________________
Picking time is about 2.56x longer than a regular frame time.
Application executes normally with frame-rate greater than 100fps.
================================================== ============
Experiment 3.

- Rendering time - 14.327ms
- Picking time - 34ms
__________________________
Picking time is about 2.37x longer than a regular frame time.
================================================== ============
Testing machine:
GX600 laptop
CPU - Intel C2D T8100 @ 2.1GHz,
GPU - NVidia GF 8600M GT with 512 DDR2 RAM
Driver: 190.89
OS: Vista 32bit
================================================== ============
Conclusion: In all previous experiments picking takes about 2.3 to 2.75 times longer time than a regular frame. So, it is not considerably slower. And, of course, I didn't try to select a single triangle, but a whole object consists of many triangles, and hierarchically embedded into other objects. Nevertheless, there are many hundreds of objects (even more than a thousand for the first test).

dukey
12-13-2009, 11:27 AM
Colour picking is the best way I know. But if anti-aliasing is enabled in the driver it might unleash armageddon.

Jan
12-13-2009, 11:57 AM
That looks indeed as if nVidia has implemented feedback mode properly now. Maybe it has become easier to do so with modern hardware. Thanks for the information!

Still, keep in mind that it might be a problem on other vendors hardware. Though it reminds me of the accumulation buffer. It has never been supported in hardware for years, until float-buffers came around, suddenly it was no problem to use them. Though at that time their usefulness had been superseded anyway.

Jan.

Kip Warner
12-13-2009, 01:40 PM
Thank you everyone for your feedback. Very valuable.

Aleksandar
12-14-2009, 03:50 AM
Just a short addendum to previous test results...

Processing hit-records, probably, can be time-consuming if there are lots of records. The picking time in previous tests does not include hit-records processing time. So, I have extended tests and dump number of hit-records and parsing time. My hit-record buffer contained from 4 to 24 hit-records and processing time is about 3uS (3*10-6s). As we can see it is negligible compared to everything else.

I'm sorry for this addendum, but I had to complete my test-conditions if any one try to compare his/her results with mine. I'll be glad to see the efficiency testing on other (non-nvidia) hardware.

zeoverlord
12-15-2009, 04:37 AM
You know 2.3 to 2.75 times longer still isn't that good, try and implement color picking, it would be interesting to see how these things scale in comparison.