1
\$\begingroup\$

I implemented color picking recently and I would like to use it as kind of highlight when mouse is over an object but I am concerned about performance. Color picking requires whole frame to be drawn, loosing effectively up to half of performance (MouseMove can happen nearly every frame).
Also, when mouse moves it is very likely to be nearly above previous point - is there any way how to use this fact to improve performance of 3D picking? Or is my best chance to use some other technique of 3D picking or approximation of results?
tl;dr If I wanted to do "realtime" 3D picking - on MouseMove, what is the best technique for doing so performance-wise?

EDIT: the exact numbers are even worse, when rendering 1m triangles render time increase from 1.5ms to 2-6ms and in spikes up to 15ms.

\$\endgroup\$
  • 1
    \$\begingroup\$ Well, a more common way of doing 3D picking is with object/line intersection tests. This is very fast if you use some form of space partitioning in the scene. I have provided some pseudo-code for that in the past. If you would like to test it, here it is: stackoverflow.com/a/23645092/1198654 \$\endgroup\$ – glampert Jul 28 '14 at 22:28
  • \$\begingroup\$ @glampert thanks, I will definitely have a look. Glm has unproject function but I am not sure what it returns? I would expect ray equation, not a simple vector. Also, can it be modified to select multiple(=all) objects within on-screen rectangle (that is quite important for me)? \$\endgroup\$ – wondra Jul 28 '14 at 22:40
  • \$\begingroup\$ Unproject (when called twice) will produce a line that goes from the camera location to infinity. See this for a detailed explanation. Normally you then test this line agains scene objects. To limit it to a 2D area of the screen you would have to do some math and change the projection matrix. To limit to only the 3D objects in view, then you need some form of space partitioning. \$\endgroup\$ – glampert Jul 28 '14 at 22:49
  • \$\begingroup\$ I see, but I got one more question: why do I need to pass ModelView matrix, not plain View matrix? Or is it just another name? (and where should I get it, since camera doesnt have model matrix) \$\endgroup\$ – wondra Jul 29 '14 at 10:26
  • \$\begingroup\$ Normally, you will pass just the camera's view matrix. If you where to add the transform of an object, making it a model-view matrix, then the resulting points would be in that object's space. This is not very practical though since you usually want to test the resulting line against several objects. So yes, passing just the view matrix is fine. \$\endgroup\$ – glampert Jul 29 '14 at 18:52
2
\$\begingroup\$

Considerations:

A. Do the color-frame less frequently, for example at 10 fps (every 6th frame if you run at 60fps). Small lag won't be that noticeable;

B. Render color-frame at lower resolution, e.g. 1/4, if you don't need pixel-perfect precision;

C. Render only one pixel that you need below the cursor. I'm not confident with the math, but surely there's a way to setup a view/projection matrix to take a tiny portion from the full view/projection matrix. If done right, frustum culling will reduce a lot too - meaning less overhead of unpickable objects ever getting sent to render at all;

D. Make sure you strip off any unnecessary parts and computations, alike non-pickable objects;

E. Forget about color-picking and switch over to Ray-Object intersection technique.

\$\endgroup\$
  • \$\begingroup\$ Regarding the option C. , how can one implement it? Is there noticable performance improvement? (you know, clipping etc. is still performed, isnt it?) \$\endgroup\$ – wondra Jul 30 '14 at 12:35
  • \$\begingroup\$ I'm not confident with the math, but surely there's a way to setup a view/projection matrix to take a 1px portion from the full view/projection matrix. If done right, frustum culling will reduce a lot too - meaning less overhead of unpickable objects ever getting sent to render at all. \$\endgroup\$ – Kromster Jul 31 '14 at 6:10
2
\$\begingroup\$

You need to, as comments indicated, project a ray from the camera's world location and using the unprojection of your camera look vector.

For multi-object selection, you will basically use two of these rays to generate a pyramid shape and do object collision detection against that. One corner would be the initial ray when the user first clicks, the opposite corner would be the current ray from where the mouse is dragged, and you can derive the other two.

I definitely wouldn't do the color technique. The actual rendering of the colors is trivial and not at all a performance concern. However, stalling the GPU so you that you can read back the results onto the CPU is a huge performance concern that you want to avoid. Doing it (somewhat) right at least requires a lot more coordination on the CPU, such as drawing the color buffer at the beginning of your frame and then not trying to read it back until the end of the frame (or next frame), giving the GPU as much time as possible to finish the color render. There's also a lot of shenanigans to play with the texture allocation to make sure it's in fast-to-read GPU memory well before you try to read it. Really, though, just don't do the color picking technique.

\$\endgroup\$
0
\$\begingroup\$

I'd echo Sean and avoid the rendering solution and use ray intersection. That said, you can generally get fast enough results without sophisticated spatial partitioning if you can quickly limit a pick to, say, tens of thousands of triangles to test against and not millions.

It's worth remembering that you only need to do one pick on a mouse over, not collect a billion samples worth of ray intersections as with the cast of a raytracer using path tracing. So you can generally get away without using a BVH, octree, or K-D tree, for example, or at least not ones that have to go all the way to storing things at the triangle level, if all you need is picking.

So a lot of times you can get away with a "good enough" solution, like just start off checking to see if a ray hits any one of your object's AABBs (or an object's "part", like a robot's arm), and if so, just test for ray/tri intersection with each of the triangles in that object. That can usually be "good enough" without building and constantly updating a much more elaborate data structure unless you have need for one for other purposes (collision detection, e.g.).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.