Sign in to follow this  
  • entries
    8
  • comments
    35
  • views
    16187

PPP - Pixel Perfect Picking for Vertex and Face Selection

Sign in to follow this  
Buckeye

3230 views

Disclaimer

Credit for the concept of Pixel Perfect Picking in D3D11 belongs to gamedev member unbird, a wizard with shaders. However, since I'm basically lazy, I coined the acronym PPP, and adapted the idea to my needs.

N.B., some of the implementations below require SM5.

The PPP Approach

The idea is to pick objects (in my editor that's vertices and faces) with a mouse-click by writing mesh and vertex/face information to a texture during the rendering process; sample a single pixel of the texture at the mouse position; and interpret the components as data, rather than color, providing the needed information. If you need to know what object is under the mouse position, and you're rendering the scene anyway, get the information from the rendering process itself in a single pass.

When the user clicks the mouse to select something (or, actually, any time you want to know what's under the mouse position):

1. Clear and set a second render target view.
2. Set appropriate buffer data and shaders to both render to the primary render target and output the needed information to that second texture (mesh id's, vertex or face id's, etc.) HLSL provides the convenience of SV_VertexID and SV_PrimitiveID which can be passed through.
3. Render the scene, writing the color to SV_Target0 and the data to SV_Target1.
4. Use CopySubresourceRegion to get just the single pixel from the second texture at the mouse position.
5. Examine the pixel to see what (if anything) lies under the mouse position.

It's a Different Approach to an Old Concept

Picking objects by rendering them can be done in OpenGL. I haven't done it in ages, but, IIRC, OGL has the option to set the render mode to GL_SELECTION. You then get a list of object hits in the view volume by rendering. PPP works similarly but tests for an object hit at the pixel under the mouse-click position in a single pass.


The Need for a Picking Algorithm

A feature I wanted to incorporate in my mesh editor for picking or selecting vertices and faces is the option to limit selection to only visible vertices or faces. That is, "visible" in the sense of "appearing in the current view." It's one of the options Blender implements and I use it frequently when editing meshes. In general, it's more natural when selecting vertices or faces with a mouse-click to expect that the selection will include only the verts/faces I can see onscreen. Before I was mindful of the option in Blender, I would click a face or vertex and later find that hidden vertices or faces (verts or faces at a greater depth than the intended selection) were also selected. Editing what I assumed was only affecting the verts/faces I could see, was, in fact, altering stuff I hadn't intended.

A common method for picking verts/faces with a mouse-click is to do a raycast into the scene from the mouse position, search through verts/faces for hits, and select the object with the smallest hit distance. That picking algorithm can be extended to a list of hits with depth information (hit distance) if desired. That algorithm can be made more efficient with broad-phase culling (choose your favorite method), but still requires setting up the raycast and searching through data to find hits.

However, as with the OpenGL GL_SELECTION method, the very act of rendering does that depth testing (if depth testing is enabled). In particular, if the scene is being rendered anyway, why not use the rendering process to get the needed information, and skip the raycasting process altogether?

For my particular needs in a mesh editor, I have two picking/selection algorithms available - one using geometry shader stream-out to generate a list of visible objects for box selection; the other using the PPP method for mouse picking.

In addition, to give the user a reasonable target for clicking, I display the vertices as billboarded colored quads (say 3x3 or 4x4 pixels), with color indicating whether the vert is currently selected or not, with depth testing disabled so the full quad overdraws adjacent geometry. To do that with depth testing disabled requires culling using a depth map (I use a method similar to shadow mapping) to determine whether the quad is visible and should be rendered, or is not visible and should be discarded. That can be done in the pixel shader, or in a geometry shader. I do it in a geometry shader which can also be used, as mentioned, with stream-out to generate a list of visible objects. Maybe more on that in a later blog entry.
Sign in to follow this  


11 Comments


Recommended Comments

I use a similar approach in my game. One tip is to sample a larger region (eg 3x3 or 5x5) of pixels and introduce a weight to rate each pixel. Then sum up all rating of pixels refering the same data (vertex/surface) and select the highest rated surface instead of the one which is directly at the mouse position.

 

The reasaon, or my experience, is, that if you have really small objects (thin or mostly covered vertices), it is really hard (and frustrating) to hit the right pixel. With a weighted sum you are able to pick them more easily, especially if you have a neutral background which could not be selected at all.

Share this comment


Link to comment

Thanks for the credit :-)

 

We discussed a couple of approaches. One I haven't tried is using a UAV in the pixel shader.

 

@Ashaman73: Nice idea. You say you use it in-game. Any performance problems in this regard ? 

Share this comment


Link to comment

Thanks for the credit :-)

 

We discussed a couple of approaches. One I haven't tried is using a UAV in the pixel shader.

 

@Ashaman73: Nice idea. You say you use it in-game. Any performance problems in this regard ? 

The issue with reading back the pixels is always to stall the GPU, therefor I read it back when swapping the buffers. The information is stored in the alpha channel (you got only 256 values, but with the right distribution of ids close to the mouse position you will not really need more ids). I can't look into my code now, but I'm sure, that I read the alpha value back from the front buffer to avoid stalling the GPU which writes to the back buffer. Thought this works only for double buffering and could introduce lag when pre-rendering multiple buffers. Eventually the better way would be to write the pixels to a small PBO and use double buffers, fenches  and asyncronously DMA to get it into CPU memory. But I don't have any notable performance impacts with my approach, so I leave if there for now.

Share this comment


Link to comment

I use a similar approach in my game. One tip is to sample a larger region (eg 3x3 or 5x5) of pixels and introduce a weight to rate each pixel. Then sum up all rating of pixels refering the same data (vertex/surface) and select the highest rated surface instead of the one which is directly at the mouse position.

 

The reason, or my experience, is, that if you have really small objects (thin or mostly covered vertices), it is really hard (and frustrating) to hit the right pixel. With a weighted sum you are able to pick them more easily, especially if you have a neutral background which could not be selected at all.

 

It's an advantage programming an editor (slow, always waiting for user input) vs. a game - as mentioned above, I draw a 4x4 pixel quad (a decent size target area**) for each vertex, with depth testing disabled for the quad drawing, so the quad is never covered (except by another vertex). That eliminates the need to sample more than the pixel at the mouse position.

 

** For  me, anyway. My eyes are getting old and I may have to add in a user option to set the quad size to a larger value!

Re: "neutral background" - see below for the advantages of using a second render target - i.e., it's cleared to a known "background" value that's easily identified. wink.png
 

 

The information is stored in the alpha channel (you got only 256 values, but with the right distribution of ids close to the mouse position you will not really need more ids).

Actually, for a mesh editor, I need to be able to uniquely identify 1000s of vertex & face ids, as any vertex/face may be onscreen at any one time. ohmy.png

"Pick a vertex ... or die"

 

[sharedmedia=gallery:images:6350]
 

Using a second render target texture to store the information has a couple advantages- 1) clearing it to (e.g.) (0,0,0,0) before the render provides just a single "no hit" value to worry about, and 2) provides 4 channels for storing data. That's plenty of room to identity which mesh and which vertex or face is under the mouse!

 

Depending on the needs of the game, using multiple render targets (up to 4) could be used to great advantage. As unbird mentions, using a UAV (which I haven't tried, either) adds even greater flexibility!

Share this comment


Link to comment

When I model with blender, I use very often proximity instead of direct selection for eg. edges. Increasing the size of the vertices to make it easier to select them directly (what about hi-resolution monitors?), makes the visibilty of different vertices more difficult.

I would recomment to download blender and analyse the picking behavior, it is quite matured.

Share this comment


Link to comment

When I model with blender, I use very often proximity instead of direct selection for eg. edges. Increasing the size of the vertices to make it easier to select them directly (what about hi-resolution monitors?), makes the visibilty of different vertices more difficult.

I would recomment to download blender and analyse the picking behavior, it is quite matured.

 

 

I'm not sure how increasing the displayed vert size would affect visibility of other verts. If you mean that one vert quad may overdraw another vert quad, the situations when that might occur: 1) two or more verts are lined up closely along the camera direction, in which case the model can be rotated to provide more separation; 2) two or more verts are in very close proximity in the mesh itself, in which case zooming in provides more visual separation. In those cases, providing visual separation by rotating or zooming is likely the best approach, as the very idea for picking (versus box selection) is to support the user in selecting a single vertex. If two verts are visually close on the screen, and the user clicks at a position exactly between them, the program (and not the user) determines which vert gets selected. A pixel perfect approach works for both the user and the program - either a vert close to the mouse position is selected, or it's not.

 

Particularly in the case of hi-res displays, making things easier and predictable for the user (me) is the priority.

 

With regard to Blender, as I mentioned in a previous blog entry:

 

I still have a ways to go to be really proficient in D3D11 ... N.B., Blender can (probably) do everything I need, but I love creating my own tools ...

The reason I'm programming a mesh editor isn't to duplicate Blender, or even to discover how Blender does it. I'm using a mesh editor as a vehicle to force myself to explore and learn more about D3D11, and have fun doing it. Using Blender for cut-and-paste, or dissecting and rewriting someone elses code? [shudder] Nah!

 

It may be a subtle difference, but the idea is not "How can I do that?" but "How can I do that?"

Share this comment


Link to comment

 

The reason I'm programming a mesh editor isn't to duplicate Blender, or even to discover how Blender does it.

I know that you don't want to use or reproduce blender. Blender was just an example for me, which I know and which visualizes what I mean. Maya, max etc. would do too. Nevertheless, refusing a design before analying it, because someone else already used it, is not the best way.

 

Form follows function, not antipathy :-P

Share this comment


Link to comment

 

 

The reason I'm programming a mesh editor isn't to duplicate Blender, or even to discover how Blender does it.

I know that you don't want to use or reproduce blender. Blender was just an example for me, which I know and which visualizes what I mean. Maya, max etc. would do too. Nevertheless, refusing a design before analying it, because someone else already used it, is not the best way.

 

Form follows function, not antipathy :-P

 

 

 

Your quotation of my statement missed the two statements which followed - I'm exploring D3D11, and I want to have fun doing it. wink.png

 

It's my understanding that Blender uses the OpenGL API. If that's correct, then first learning OpenGL in order to analyze how Blender's design uses OGL tools and capabilities, and determining from that analysis how the same thing, or similar, can be done in D3D11, doesn't support my immediate goal to explore D3D11, and (more importantly) wouldn't be enjoyable to me right now. biggrin.png

 

I'm not making the claim that learning OGL and its capabilities, or how other well-written apps take advantage of that API, wouldn't be educational. There are more than enough this-API-versus-that-API posts on gamedev! blink.png  I'm just on another path. That's not antipathy, it's a decision to see what D3D11 can do, rather than OGL.

 

With regard to form following function, that's exactly my approach - perhaps you missed A Program's User is the Customer. The function I'm trying to implement is making it easy and reliable for me to pick a vertex.

Share this comment


Link to comment
That's an interesting approach to mouse picking. I was a bit dismissive when I first started reading, but you make some good points that justify it.

Share this comment


Link to comment

Thanks. Much appreciated. As mentioned, my primary goal was to avoid the "standard" picking algorithm (unproject the mouse point, cull and test all objects of interest). I haven't profiled it to see if it's faster. But particularly for skinned meshes where every vertex is multiplied by multiple matrices every frame (whether picking is in progress or not), part of the picking calculation is done on the GPU. However, time is also taken to clear and set the second "pick" texture. The nice part is that a single pixel can be tested to determine if there's a "hit" at the mouse position. The "standard" algorithm still requires testing for a hit on each vertex (and there may be 1000s). Even with a good culling process, there's a lot of CPU-side work doing all that matrix multiplication.

 

However, the PPP approach has limitations for vertex picking for meshes with multiple vertices at the same location (as many meshes do). That is, the "pick" texture only stores data for the last vertex rendered at the location. As a result, in the case of multiple vertices at a single pixel, the pick texture only provides the info that some vertex was hit. Further testing is needed to determine how many vertices were hit.

 

If no vertices are hit, all's well and the program continues. However, if some vertex was hit, I run a geometry shader for one frame which does the picking and streams out the picked vertex data. Maybe another blog entry on that end of things.

 

The PPP process may work even better for selecting faces. For triangle rendering, if the pick texture is populated with instance ids, a single click yields the picked face without any further calculations. The only significant cost is clearing and setting the pick texture. As you're probably quite aware, picking a face in an animated skinned mesh on the CPU side is horrendous.

Share this comment


Link to comment

@Ashaman73: Your mention of weighting each pixel position is just the right thing to do for picking edges. I'll soon be adding a blog entry describing an implementation for edge-picking - with credit to you for an excellent way to do picking of objects in the proximity of the pick position.

 

As is not unusual, unbird saw the value in your algorithm immediately. I'm a bit slower, but I, too, see the utility in your suggestion. Thank you for the comment!

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now