picking

Hi,

I'm considering a switch to OpenGL from Direct3D.

I'm using a shader approach to picking and I'm wondering whether something similar would be possible in OpenGL using Jogl?

I have dedicated the geometry shader for picking. It's possible to remove and insert this shader into the graphics pipeline. It's also possible to make the pipeline stop at this shader so nothing appears on screen. In the application there are two modes. One for drawing without the geometry shader and one for picking with the geometry shader present.

All objects that are drawn in a frame enter the geometry shader in the form of a sequence of triangles. In the shader a unigue integer is available as an identifier for each object. Id's are assigned by the application. Also the origin and direction of the pick ray is available in the geometry shader. For each triangle that arrives the shader checks whether it intersects with the pick ray. If it does, the distance from the pick ray origin to the intersection point with the triangle, and the object id is sent back to the application via a pipeline feature called stream output. The application then checks all hit candidates and selects the closest one to the pick point. The object id tells which object was picked.


[code]
struct StreamRecord { // stream output data
        int objectID : OBJECT_ID;
        float distance : DISTANCE;
};

// geometry shader writes to stream output if triangle intersects with pick ray
[maxvertexcount(1)]
void GS_pickShader(triangle CommonVertexStruct input[3], inout PointStream<StreamRecord> output) {
        int id = input[0].objectID;
        if (id >= 0) { // only consider non-negative object id:s
                float d = ray_triangle_intersection(pickOrigin, pickDirection, input[0].posW, input[1].posW, input[2].posW);
                if (d > ZERO) { // pick candidate
                        StreamRecord r = {id, d};
                        output.Append(r); // to stream output
                }
        }
}
[/code]

As a summary the application does this,

1. Insert and remove the pick shader (switches between draw and pick mode).
2. Calculate the pick ray and assign id's to objects.
3. Send pick ray and objects with id's to the pipeline.
4. Select the picked object among the candidates that are reported back from the pick shader.

The pick shader does this,

1. Determine whether the pick ray intersects with arriving triangles.
2. Report hits back to the application.

This approach turns out to be very fast because most calculations are done on the GPU. It's as fast as drawing one frame if not faster since no actual drawing is done in pick mode. The approach is also very general since every object with a surface is triangulated anyway as part of the drawing process so the triangles are for free in this sense. And no complex extra data structure must be maintained by the application other than what's kept for drawing anyway. In fact it's as close to a free lunch as it gets!

Hi

As you seem to have only triangulated surfaces, why not using software picking? It can be a lot faster than drawing one frame especially when you have only triangles. The use of build-in OpenGL picking is discouraged, color picking doesn't work if some colors of the palette are emulated (especially on some low end laptops).

If you still want to use a geometry shader, you can disable the rasterization by enabling GL_RASTERIZER_DISCARD but as triangles are treated in parallel, I'm not sure you can't early stop when you have found an intersection. Maybe Sven or Dominik could give you a more accurate answer.

Thank you gouessej,

I don't quite understand what you mean by software picking? You mean picking that takes place in data structures held by the application rather than on the GPU?

Sure I could do that but I find this approach better because it's much more general and simpler. It's just drawing as usual (although nothing appears on screen in pick mode). It works with any triangulated surface including when the triangulation is performed by the GPU. For example I draw lots of spheres but I only send position and radius (and some extras) for each sphere to the GPU. The actual triangulation takes place in a Hull shader on the GPU, so the application doesn't even know of any triangulated spheres (or cones, or cylinders, or circles or squares or any other easily parametrized geometric shape).

So certainly I'm hoping the same approach can be used with OpenGL. I guess I could find out by starting porting but it's always nice to know in advance what to expect. That's why I'm asking.

If you can do that in Direct3D, you can do that in OpenGL but I'm not sure this is a really efficient approach. Software picking means picking implemented in software, without OpenGL. When you only have triangles, it's quite simple to implement.

Thanks,

Yes, the grapewine has it that OpenGL and Direct3D are feature equivalent, but the devil's in the details. I was wondering if anyone experienced in working with OpenGL shaders see any immediate problems with my approach. For example is there something similar to a Geometry shader which allows me to get hold of triangulated data? And can I output (pick) data back to the application from that shader?

I know it's simple to intersect a ray with a triangle and that's why I'm doing exactly that :). But as I said in my previous reply, most of the triangles are created on the GPU. I'm using Hull shaders to triangulate easily parametrizable shapes such as spheres and cones. These triangles are not available to the "software" running on the CPU.

This contributes to the efficiency of this approach. When you draw say a sphere you essentially just pass a position and a radius to the GPU, not lots of triangles. It's very easy on the bandwidth. And furthermore you don't duplicate effort. You don't need an extra "software" copy on the CPU of functionality you've distributed to the GPU. Once you've embraced shaders you need to get rid of fixed-pipeline thinking. The shaders are part of the "software".

Just an example. To draw 1.4 million spheres (using adaptive triangulation so spheres appear round regardless of distance to the observer) takes 0.1 seconds on my computer. That's fast enought to pan, scroll and zoom them smoothly. To pick any sphere takes 0.025 seconds.

ul wrote

Thanks,

Yes, the grapewine has it that OpenGL and Direct3D are feature equivalent, but the devil's in the details. I was wondering if anyone experienced in working with OpenGL shaders see any immediate problems with my approach. For example is there something similar to a Geometry shader which allows me to get hold of triangulated data? And can I output (pick) data back to the application from that shader?

I don't have experience in doing these advanced things so I can't give you specific pointers but as far as I know, yes, you certainly can do this. What you are looking for are probably tessellation shaders and transform feedback. There is a thing called geometry shaders in OpenGL that was introduced before tessellation shaders but aren't targeted to specific tessellation hardware so might not perform as good.

http://www.opengl.org/wiki/Tessellation_Shader

But I guess I can see goussejs point, the usual approach is to keep the model of the world separate from the graphical presentation. Picking, physics simulation et c. are probably best done in the world model rather than picking against the graphical presentation. Still, use cases might be different so whatever works :)
I guess another thing that might be of interest is OpenCL, picking against a lot of spheres could probably be handled rather efficiently by compute shaders.

https://www.khronos.org/opencl/resources

Thank you jmaasing for your input.

I agree my approach may be categorized as low-level picking. But on the other hand if you do it high-level you basically take on to implement the ray-tracing approach to graphics. And that's no cakewalk. I found it better to tap into the triangulation based graphics you find in the majority of graphics cards today.

Regarding the use of compute shaders, the advantage with my approach is that you don't need to treat lots of special cases, like picking spheres. picking cones, picking this or picking that. It works on any surface as long as it's triangulated and that's the beauty of it. If you can draw it you can pick it. In 3D graphics the triangle is a primitive data type like say a floating point number. Both are independent of what you draw or calculate respectively.

Well, I'm willing to motivate my choise but my immediate wish is to get an indication as to whether my approach is feasible in OpenGL. And so far so good, no one has said it's difficult or impossible. :)

ul wrote

But on the other hand if you do it high-level you basically take on to implement the ray-tracing approach to graphics. And that's no cakewalk. I found it better to tap into the triangulation based graphics you find in the majority of graphics cards today.

Regarding the use of compute shaders, the advantage with my approach is that you don't need to treat lots of special cases, like picking spheres. picking cones, picking this or picking that. It works on any surface as long as it's triangulated and that's the beauty of it. If you can draw it you can pick it. In 3D graphics the triangle is a primitive data type like say a floating point number. Both are independent of what you draw or calculate respectively.

It's not specific to your approach. Some engines manage only triangles and when they deal with picking, they don't have special cases to treat. Moreover, don't expect a huge speedup when performing the equivalent of the intersection test between a ray and a triangle on the GPU. If you need to use this result on the CPU, you'll have to transfer it. When I use software picking in Ardor3D, there are several intermediary steps that allow to skip heavy computation when there is obviously no chance of picking something, it uses bounding volumes before testing on the mesh. If your mesh doesn't change, you don't even have to recompute its bounding volume.

There is an example using GL_TRANSFORM_FEEDBACK_BUFFER here:
http://github.prideout.net/modern-opengl-prezo/

I like this one because the author takes care of discarding the rasterization.

Edit.: Your approach is less flexible but maybe it fits better into your particular needs. For example, it is nice if you don't have any hierarchical mesh data.

Well, I called it "my" approach because I'm using it, not because I invented it. :)

And my main concern isn't the relative merits of my approach but whether it's portable to OpenGL. Picking as fast as drawing a frame, that's fast enougth for me.

Still I'm quite surprised by the generality, simplicity and efficiency of my approach. Why not enter 1.4 million spheres in Ardor3D allowing for pan, scroll and zoom of all spheres in unison. Can you draw the whole scene in 0.1 seconds and pick a sphere in 0.025? My expectation based on experience with the so called "software" approach is that you won't even be able to hold a scene of that size, and if you do that everything will come to a grinding halt when you try to perform operations on it.

You claim my approach is "less flexible" but compared with what? And why wouldn't it work on hierarchical meshes? On the contrary I'd say. The more decomposed the mesh, the better my approach.

I load a piece of a town in the suburbs of Paris with Ardor3D, the meshes are less complicated than a real artwork manually created by a computer artist but more than a scene with 1.4 million spheres and the picking is necessary to be able to use the guns of course. As it is interactive, the frame rate must be acceptable and it's obviously drawn in less than 0.1 seconds (even on an ATI Radeon 9250 Pro bought in 2004) especially when mesh instancing is enabled (this technique is used in the Ardor3D-based game "Caromble" too). An extremely naive implementation of software picking would give poor results, I don't deny that but this is not the case in several engines that use software picking including Ardor3D. It depends on your needs but in my case, I need to perform picking faster than drawing. Picking as fast as drawing is enough for you, I see the difference.

If you only perform a typical ray / triangle intersection test on each triangle of the meshes on the GPU or on the CPU, you won't take advantage of the hierarchy unlike what several engines do. If you just move the intersection test from the CPU to the GPU, where is the plus value? Yes it's doable in OpenGL with a tessellation shader (don't forget to send patches instead of triangles as explained here), the transform feedback buffer and preferably by discarding the rasterization but you might have to write several versions of the same shader and you'll need a fallback solution for the graphics cards with no support of this kind of shader (TES and TCS are only available in OpenGL 4 ~= Direct3D 11). It seems useful if you can use the result of the intersection test in the shaders. On my view, implementing picking on shaders requires much more plumbing especially when some computations are still done on the CPU outside shaders.

Edit.: You can even get the primitive id in the GLSL shader, maybe it could be useful for you.

He he gouessej, I didn't expect my question would end me up in a discussion about the merits of my approach, but okay! :)

In my view you're stuck in the old thinking where you have the "software" running on the CPU controlling a fixed graphics pipeline implemented in hardware.

But the trend is that the graphics hardware is becoming a general processing unit able of massive parallelism. This is what shaders and OpenGL of late and OpenCL is all about. This means that the CPU "software" of yesteryear is getting distributed and more and more is dedicated to the GPU. Hence my approach.

Now if Ardor3D is supposed to be general it cannot rely on a specific structure of the graphics data to be efficient. It should also be able to efficiently pick in the structure-free 3D scene I was talking about, namely 1.4 million spheres. I can draw that in 0.1 seconds and that's a sufficient frame rate for my application because I draw on demand only. I don't have continuous frame production, I redraw when necessary only.

But lets lower the stakes. Lets say you have 170.000 spheres only. I draw them in 10 milliseconds and pick them in 4 milliseconds. That's a frame rate that would be very acceptable also in a continuous frame rate situation.

How does Ardor3D perform in this situation? I'm curious because you claim the "software" approach is so efficient but can you back that up with actual performance data?

I'm not stuck in an old thinking, I just say that shader based picking is only worth in a fully shader based architecture. Moving an operation into a shader doesn't drive it magically faster. JMonkeyEngine 3 has a fully shader based renderer and it does NOT use shaders for the picking as far as I know. You admit it yourself, you talk about parallelism, shaders and OpenCL are better for algorithm that can be parallelized, it doesn't mean that just moving the execution of an algorithm is enough to benefit of parallelism. However, you basically move a ray intersection test into a shader, how can you expect a speedup from that?

Ardor3D and my game are open source, feel free to check your claims by running your picking on the WaveFront OBJ file I generated from an OpenStreetMap file:
http://svn.code.sf.net/p/tuer/code/pre_beta/obj/planet_2.413_48.853_f55ff5ae.osm.obj

A non naive software picking used with some complementary checks to avoid heavy computations can be efficient, the same in shaders too, I just think that you would spend a lot of time in implementing the same thing in shaders and it wouldn't be more efficient. Do you know at least one engine performing frustum culling and intersection tests with bounding volumes in shaders?

Ardor3D is quite flexible, you can even use a render delegate with some raw JOGL code in it, it doesn't prevent you from doing whatever you want with JOGL but I know that tons of developers prefer reinventing the wheel in worse. Each time I enter a new job I find a new "private" scenegraph with some poorly implemented algorithms (with a very few exceptions) :s

gouessej wrote

I'm not stuck in an old thinking, I just say that shader based picking is only worth in a fully shader based architecture. Moving an operation into a shader doesn't drive it magically faster. JMonkeyEngine 3 has a fully shader based renderer and it does NOT use shaders for the picking as far as I know.

I'm pretty sure jMonkeyEngine uses BIH-tree for scene graph picking (http://en.wikipedia.org/wiki/Bounding_interval_hierarchy) or if you use Bullet physics you usually do ray casts in that engine (http://bulletphysics.org/wordpress/).

Each time I enter a new job I find a new "private" scenegraph with some poorly implemented algorithms (with a very few exceptions) :s

Nothing wrong with writing a poorly implemented scene graph, I've done it many times

To the OP, we are derailing this topic because the original question (i.e. is it possible in OpenGL) is I think answered with yes. The thing is there are a lot of engines available with OpenGL based graphics and there is a lot to learn by comparing how they do things. If what you learn is best-practice or old-set-ways-of-thinking is up for debate.

The engines I know use ray casts to do picking. I think the reason is that ray casts are so useful for all sorts of things that they all have pretty optimized ray casts, and then picking is just another application of a really fast ray cast.

jmaasing wrote

I'm pretty sure jMonkeyEngine uses BIH-tree for scene graph picking (http://en.wikipedia.org/wiki/Bounding_interval_hierarchy) or if you use Bullet physics you usually do ray casts in that engine (http://bulletphysics.org/wordpress/).

Yes, you're probably right, Ardor3D and JMonkeyEngine use both bounding volumes first before performing some checks on each triangle.

jmaasing wrote

The engines I know use ray casts to do picking. I think the reason is that ray casts are so useful for all sorts of things that they all have pretty optimized ray casts, and then picking is just another application of a really fast ray cast.

I agree with you and the OP is free to share his findings with us, it will be useful when the move of the implementation of several algorithms into shaders is viable (it's ok for me, it's the future, I don't deny it).

Dear gouessej and jmaasing,

My approach is simple; If you can draw it you can pick it. And it's fast enougth; Picking is never slower than drawing and usually about ten times faster.

You claim that doing things on the GPU cannot be faster than doing it on the CPU. Of course it can! That's why we've had dedicated graphics hardware for a long time and that's why these cards are now being opened up to make their massive parallelism available for general computing.

So with all due respect, if you want to claim superiority of your oldfashioned hierarchical "software" approach of yesteryear the burden of proof is on you. Good luck.

I've understood that you prefer to discuss your pet ideas but my interest in this really is just the OpenGL porting issue. Thanks.

ul wrote

You claim that doing things on the GPU cannot be faster than doing it on the CPU. Of course it can! That's why we've had dedicated graphics hardware for a long time and that's why these cards are now being opened up to make their massive parallelism available for general computing.

For a so rudimentary operation (a ray triangle intersection test), I'm not sure it is really faster when done in a shader but if you succeed to split the job correctly to really benefit of parallelism, why not?

ul wrote

So with all due respect, if you want to claim superiority of your oldfashioned hierarchical "software" approach of yesteryear the burden of proof is on you. I'm not going to waste any time with this lost cause. Good luck.

I don't understand your claim. Bounding volumes and hierarchical methods have nothing to do with the "software" approach. I remind you that hierarchical occlusion culling and geometry shaders can be used to compute shadow volumes:
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch11.html
This example uses a binary bounding-volume hierarchy (BVH) of axis-aligned bounding boxes (AABBs). Moreover, occlusion culling, backface culling and frustum culling (with BVH) can be used with deferred shading:
http://gamedev.stackexchange.com/a/66284
How is it old fashioned?

ul wrote

I've understood that you prefer to discuss your pet ideas but my interest in this really is just the OpenGL porting issue. Thanks.

But some people here gave you some pieces of information about the way you could implement that:
- tessellation shaders
- transform feedback
- discard rasterization
- maybe use the primitive id

Actually, it is possible to get a speedup by implementing the picking in shaders but this algorithm is more complicated than the one ul suggests:
http://www.hindawi.com/journals/ijcgt/2009/730894/

Edit.: This is a bad example of picking in GLSL shaders:
http://www.opengl-tutorial.org/miscellaneous/clicking-on-objects/picking-with-an-opengl-hack/

Well dear gouessej,

In this thread you promote your own favorite scenegraph called Ardor3D, but in another thread you claim the JavaFX scenegraph is bad.

The purpose of both is to hide OpenGL but why do you consider your scenegraph good and the other bad?

It looks kind of wobbly to me.

Hi ul

Actually, I'm responsible for engine support (for the JogAmp Foundation), I have to maintain the JogAmp backends of some major engines / frameworks / libraries with the help of some people (Harvey for Java3D, Xerxes for LibGDX, some occasional contributors for JMonkeyEngine) including Ardor3D, JMonkeyEngine, Xith3D, Java3D and LibGDX. I don't "promote" a particular scenegraph but:
- LibGDX JogAmp backend urgently needs to be updated and fixed. I advise developers to use it mainly for 2D games, it's more reliable, complete and actively maintained than Slick2D and JGame
- Xith3D seems to be no longer actively developed but still maintained. As it looks like Java3D which is very actively maintained, I advise developers looking for a Java3D-like scenegraph to use Java3D instead of Xith3D
- JMonkeyEngine 3 has a very large community, tons of features, lots of tutorials and a big documentation, it is very modern, it has a nice integrated game development environment based on Netbeans Platform but it is a bit less reliable than Ardor3D and it is mainly designed for games, not for visualization applications with multiple windows. I advise developers to use it mainly for 3D games if and only if they are ready to spend some time in rewriting some of its shaders and in fixing some of its bugs (like me for one year when I used JMonkeyEngine 2)
- Ardor3D has a tiny community, lots of examples but a few tutorials and a small documentation, it has fewer features than JMonkeyEngine but it is very reliable and it is designed with support of multiple windows in mind. I advise developers to use it for visualization applications and for 3D games except if they really need build-in physics and some advanced features that are supported by JMonkeyEngine 3
- Java3D is actively maintained but no new feature will be implemented. It has some design flaws preventing us from making it evolve without breaking the public API. On the long term, I advise developers to switch to Ardor3D or JMonkeyEngine, especially if they want to benefit of NEWT.

Do you see that it is a lot more complicated than "you promote your own favorite scenegraph"? JavaFX 3D API seems to be extremely poor, very rudimentary and it has the same design flaws than the previous versions of Java3D, i.e it uses distinct renderers depending on the platform which is a nightmare to maintain and which doesn't allow to obtain consistent performance across platforms. JavaFX 3D API is so poor that even Oracle is aware of the need of improving the interoperability between JavaFX and native APIs to ease the use of other scenegraphs based on JogAmp with JavaFX, 2 Oracle employees made a presentation about OpenGL and JavaFX at Java One a few months ago, see the bug report about JavaFX JOGL interoperability for more information about that. There is currently no public and reliable mean of forcing JavaFX not to use Direct3D yet which can cause some conflicts with OpenGL (and then JOGL), this is the main reason why I don't advise JavaFX 3D API.

Ardor3D and JavaFX 3D API are 2 very different scenegraphs, they have nothing in common except the fact that they are mainly written in Java. Ardor3D doesn't completely hide OpenGL, you can write custom render delegates in pure JOGL, you can use Ardor3D with WWJ, it is very flexible. As you can see above, each scenegraph has its pros and its cons, there is no obvious choice. Some knowledge of OpenGL (or at least an understanding of the basic principles of 3D visualization) is still very useful when using a Java based scenegraph. JavaFX 3D API is only interesting for extremely simple projects in which you don't need any OpenGL based third party API, when you just need to display a few meshes with a few lights. What is still wobbly now? As all Java based scenegraphs are different and as I have a strong experience in using most of them, it is logical that I make some distinctions between them, isn't it? A scenegraph is a layer above low level and middle level APIs, I know no very elaborated 3D Java softwares using no scenegraph, in the worst case some developers prefer using their homemade ones, sometimes they don't even consider it as a scenegraph, it is intended in being a kind of encapsulation, it shouldn't prevent you from writing raw JOGL code when you want and Ardor3D is flexible enough to allow that (but at your own risk if you put the OpenGL state machine in a bad state).

Please don't accuse me of promoting anything. I have nothing to sell, I'm a volunteer and maintaining scenegraphs is very time consuming. I spent hours in looking for an example of an efficient picking shader because my aim wasn't to prove you that I was right but rather to deeply understand the current limits of this approach (and the papers I found were interesting anyway). The truth is more interesting for me and finally, both of us were right and wrong at the same time.

On 01/11/2014 01:00 PM, gouessej [via jogamp] wrote:
> Please don't accuse me of promoting anything. I have nothing to sell, I'm a
> volunteer and maintaining scenegraphs is very time consuming.

.. indeed - Julien simply lists methods
for 'picking' without being picky :)

This is what it is all about and you can choose whats best for you.

All the information is available across the web
under the section 'general computer graphics'
and now I just feel like feeding the trolls :)

Otherwise it for sure has merits to discuss picking method
(as Julien did).

Thank you Julien for your very detailed answer and elaborating.

Sometimes I am just afraid that the original poster has not earned it.
Shows again how much love there is.

+++

TL;DR

Don't assume evil forces are driving us when you don't understand.
Simply assume the best is given to you.

:)

+++

~Sven