Which mouse picking strategy for milions of primitives?

Question

I am rendering models based on milions (up to ten) of triangles using VBOs and I need to detect which of these triangles the user may click on.

I try to read and understand how the "name stack" and the "unique-color" work. I found that the name stack can contain at max only 128 names, while the unique-color can have up to 2^(8+8+8) = 16777216 possible different colors, but sometimes there could be some approximations, so it can get modified..

Which is the best strategy for my case?

Ray picking with an appropriate bounding volume hierarchy perhaps? — Bart, Mar 01 '12 at 13:01
names/colors are really slow ... i wouldnt recommend in any purpose. just do what Bart said. — Rookie, Mar 01 '12 at 19:06

score 9 · Accepted Answer · edited Aug 20 '18 at 15:58

9

Basically, you have 2 classes of options:

The "unique color way per triangle", which means you attach an id to every triangle, and render out the id's to a seperate render target. It can be 32 bit's (8 for rgb, 8 for a), but you could add a second one for even more ideas. It'll be fiddly to get the id's per triangle, but it's relatively easy to implement. Can be quite detrimental to performance though (fillrate).
Proper ray tracing. You almost certainly want to have an acceleration structure (octree, kd,...), but you probably already have one for frustum culling. One ray really isn't a lot, this method should be very fast.
Hybrid. probably the easiest to implement. Render out the vertex buffer id ("unique color per buffer:), and when you know which vertex buffer was selected", just trace a ray against all the triangles.

In the general case, I would say 2) is the best option. If you want to have something work quickly, go for 3). 1) is probably pretty useless.

edited Aug 20 '18 at 15:58

eyllanesc

235,170
19
170
241

answered Mar 01 '12 at 15:50

El Marcel

1,767
1
10
11

Agreed. Ray tracing with a spacial acceleration structure is the best method. – kevintodisco Mar 02 '12 at 02:12
Given that I am relatively new to OpenGL, I would like to start with something easy (maybe also roughly ^^) to implement, so 1 or 3.. The fact is that I have mainly just one VBO which contains, let's say, 10 milions of triangles and I guess that when you mention "ray against all the triangles" then I am scared that this could be not that feasible with such a big amount of triangles.. Another things, do you have some link to some good tutorial for the ray tracing? And what about reading the depth with one pixel and pass it to gluUnProject to retrieve also the x and y coordinate? – elect Mar 02 '12 at 07:49
@elect, dont use names/colors. if you want to make it simple, use gluUnProject() and take a bunch of triangles from an arbitrary radius from there, and test intersection for each triangle. but i warn you: you might not get the correct x/y position depending on the distance/angle to the model. although, you may need octree for this method anyways. – Rookie Mar 02 '12 at 08:16
I say 1) is pretty useless as it's not trivial (but not too hard either) to render out a unique id for each triangle (without interpolation). If you can do it, by all means go ahead. Also note that I used "ray tracing" incorrectly, you probably want "ray picking". Google bounding volume hierarchy, octree, ray triangle intersection. – El Marcel Mar 06 '12 at 02:08

score 6 · Answer 2 · edited Jul 31 '12 at 12:07

If your GPU card has OpenGL 4.2, you may use the function imageStore() in GLSL to mark the triangle Id in an image. In my case, I need to detect all triangles behind a predefined window on the screen. Picking (choosing rendered triangles on a window) works similarly. The selection runs in real-time for me.

The maximum size of an image (or texture) should >= 8192x8192 = 64 M. So it can be used up to 64 M primitives (and even more if we use 2, 3 images).

Saving all trianges Id behind the screen could be done with this fragment shader:

uniform  uimage2D id_image;

void main() 
{
    color_f = vec4(0)
    ivec2 p;
    p.x = gl_PrimitiveID % 2048;
    p.y = gl_PrimitiveID / 2048;
    imageStore(id_image, p, uvec4(255));
}

To save all trianges Id rendered on the screen: first, we precompute a depth buffer, then use a slightly different fragment shader:

uniform  uimage2D id_image;

**layout(early_fragment_tests) in;** //the shader does not run for fragment > depth

void main() 
{
    color_f = vec4(0)
    ivec2 p;
    p.x = gl_PrimitiveID % 2048;
    p.y = gl_PrimitiveID / 2048;
    imageStore(id_image, p, uvec4(255));
}

Right now I am working on OpenGL 2. But I am likely to change in a close future. +1 for your interesting post — elect, Jul 31 '12 at 13:02

Which mouse picking strategy for milions of primitives?

2 Answers2