Picking; linking x y screen coordinates to scene components

What it says on the tin: a place to discuss proposed new features.
User avatar
nullsquared
Old One
Posts: 3245
Joined: Tue Apr 24, 2007 8:23 pm
Location: NY, NY, USA

Post by nullsquared » Mon Oct 20, 2008 3:09 am

Jabberwocky wrote:
nullsquared wrote:What about the other 90% of things that are not entities?
Good point. Although entities would probably cover most of the things a person would care about picking. Maybe IDs could intelligently be assigned to non-entities too.
Lots of edge cases. Take this, for example: an entity is covered by a user-drawn primitive (in immediate mode OpenGL, for example). Obviously, you shouldn't be able to 'pick' that entity since it'd be occluded. But unless you mimic the scene perfectly in this 'picking RTT', then you'll be able to pick occluded entities.

Also - storing the entity is nice an all, but what if you want the exact hit point? Then you'd need an MRT, one RT for the entity ID and the other RT for the hit point/distance.
nullsquared wrote:Besides - rendering the full scene to an RTT
Maybe the user could choose an RTT size, trading some efficiency for precision.
Then what's the point of using this method in the first place? I though the whole point was 'pixel-perfect' picking.
nullsquared wrote:changing colours per-object
Wouldn't this be similar to rendering the depth buffer to a texture, with a simple shader that writes an entity identifier rather than a colour?
No, because you need to change the colour per-entity. This is different from changing the material per-entity for a depth render since there is only a single depth material that needs to be used.
nullsquared wrote:then reading pixels back
Dunno if this helps, but usually you'd only need to read 1 pixel back, unless you're supporting some kind of drag-selection.
AFAIK, you'd need to pull the whole texture off the GPU even for that single pixel.
nullsquared wrote:and attempting to decode them
How exactly do you think decoding the output is going to be expensive?
Alright, that wasn't a great point :roll:
nullsquared wrote:well, let's say it won't be any faster than the already slow brute-force triangle iterating method.
Not sure if I agree.
See my statements above.
0 x

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Mon Oct 20, 2008 3:51 am

nullsquared wrote:Lots of edge cases. Take this, for example: an entity is covered by a user-drawn primitive (in immediate mode OpenGL, for example). Obviously, you shouldn't be able to 'pick' that entity since it'd be occluded. But unless you mimic the scene perfectly in this 'picking RTT', then you'll be able to pick occluded entities.
Two thoughts:
- seems like a pretty obscure edge case that wouldn't affect the majority of users who aren't using user drawn primitives.
- it can probably be solved by drawing the primitive into the picking RTT, if needed. Adds some complexity, but doesn't seem insurmountable.
nullsquared wrote:
Also - storing the entity is nice an all, but what if you want the exact hit point? Then you'd need an MRT, one RT for the entity ID and the other RT for the hit point/distance.
Then what's the point of using this method in the first place? I though the whole point was 'pixel-perfect' picking.
Yes, pixel-perfect picking is part of the point, but not the only one. There's also the "I want an easy way to pick objects without a physics engine" feature request.

Even with a smaller RTT, this still be more accurate than physics detection. Depending on the application, it may not matter if we lose a pixel or two of accuracy by using a smaller RTT. It would be a good option for the programmer to have, don't you think?
nullsquared wrote:
Wouldn't this be similar to rendering the depth buffer to a texture, with a simple shader that writes an entity identifier rather than a colour?
No, because you need to change the colour per-entity. This is different from changing the material per-entity for a depth render since there is only a single depth material that needs to be used.
Maybe I'm wrong, but couldn't you do this with a single material and shader, with an ID parameter set by the object?
nullsquared wrote: AFAIK, you'd need to pull the whole texture off the GPU even for that single pixel.
If this is really slow, and there's no workaround to ask for a single pixel, I agree this could be a serious problem. That seems like the logical starting point to see whether this technique is viable.
0 x
Image

User avatar
jacobb
Greenskin
Posts: 127
Joined: Tue Feb 14, 2006 1:34 am
Location: Orlando, FL

Post by jacobb » Mon Oct 20, 2008 3:57 am

My feeling is that picking is very application specific, with pixel perfect picking probably being unecessary for 99% of most applications. If this was really necessary to enough ogre users, and could only be implemented efficiently by being part of ogre's core, then maybe. I highly doubt this is the case, but I've been wrong before. ;)

I for one admire Sinbad's "do one thing and do it well" design decision for ogre. I would hate to see that ruined just to try and force an inefficient solution to a problem that isn't ogres to begin with.

cheers:)
0 x
find / -name base -exec chown -R us {} ';'
Check the API | Read the Manual | Browse the Wiki

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Mon Oct 20, 2008 4:32 am

jacobb wrote:My feeling is that picking is very application specific, with pixel perfect picking probably being unecessary for 99% of most applications.
The question "what graphical object is displayed at screen position x,y" doesn't seem that application specific to me.

I agree that many apps won't need pixel perfect picking. But it's a nice bonus for those that do want it. Still, many/most applications do need picking of some kind.
0 x
Image

User avatar
jacobb
Greenskin
Posts: 127
Joined: Tue Feb 14, 2006 1:34 am
Location: Orlando, FL

Post by jacobb » Mon Oct 20, 2008 4:54 am

I do agree picking is needed in many applications. The question is if a renderer should provide that functionality or not. If the picking is based on triangle intersection, then I believe that's really just outside the scope of ogre. As far as renderer based approach, pixel perfect or otherwise, then it obviously has to involve ogre in some way. The question then becomes whether it can be done efficiently, if it should be part of the core ogre, or if ogre should only provide necessary facilities to roll your own solution(which it may already).

I would kind of favor the latter. Use existing ogre facilities to roll your own solution, adding to the core only if necessary to provide missing functinality to do so. Since I don't think it's within ogre's scope to do triangle or pixel based picking efficiently, and if it can't be done efficiently/cleanly, it probably shouldn't be forced in at all.

my 2 pennies :)
0 x
find / -name base -exec chown -R us {} ';'
Check the API | Read the Manual | Browse the Wiki

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Mon Oct 20, 2008 5:32 am

I agree with all of that.

I would only support pixel-based picking being added to the ogre core if we found a decent implementation that didn't add any extra overhead when not being used.
0 x
Image

User avatar
Klaim
Old One
Posts: 2565
Joined: Sun Sep 11, 2005 1:04 am
Location: Paris, France
Contact:

Post by Klaim » Mon Oct 20, 2008 9:15 pm

Jabberwocky> I though about a similar technique to do this (but only raw thinking as i'm not sure i need it myself). Can't it be done (at least to see the perfs) as a plugin?
It looks like we already have public access to everything needed to try it, don't we?
0 x

User avatar
nullsquared
Old One
Posts: 3245
Joined: Tue Apr 24, 2007 8:23 pm
Location: NY, NY, USA

Post by nullsquared » Mon Oct 20, 2008 9:52 pm

Jabberwocky wrote:
nullsquared wrote:Lots of edge cases. Take this, for example: an entity is covered by a user-drawn primitive (in immediate mode OpenGL, for example). Obviously, you shouldn't be able to 'pick' that entity since it'd be occluded. But unless you mimic the scene perfectly in this 'picking RTT', then you'll be able to pick occluded entities.
Two thoughts:
- seems like a pretty obscure edge case that wouldn't affect the majority of users who aren't using user drawn primitives.
- it can probably be solved by drawing the primitive into the picking RTT, if needed. Adds some complexity, but doesn't seem insurmountable.
Not just user drawn stuff, but things like mirrors, terrains, portals, water, etc. Render a full scene just to pick? Can't be faster.
0 x

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Tue Oct 21, 2008 5:51 am

nullsquared wrote: Not just user drawn stuff, but things like mirrors, terrains, portals, water, etc. Render a full scene just to pick? Can't be faster.
A terrain could be drawn with an id just like an entity.
Same with water.
Same with a mirror (I think).

Anything which uses a material to draw something (which is almost everything) can be changed to output an ID.

And the worst case scenario about anything weird that somehow can't output an ID instead of a pixel colour is that you wouldn't be able to pick that object. Which may be acceptable for a few strange and uncommon edge cases.

I don't understand the technology behind portals, but obviously it's highly advanced stuff that requires a lot of custom code, so it may not be unreasonable that getting portals to work with the "picking" code would require custom code, too. Since unmodified Ogre core doesn't support portals, I don't feel that any picking code would need to, either.

----------

Let's say your app is rendering at 60 FPS.
Are you saying we can't afford to render 1 frame every time the user pushes the mouse button to pick something from the Scene? And quite possibly, it would be a far cheaper render, since we can cut out any expensive shaders, and everything would be a single pass.

-----------

Anyway, I think you've raised some fair points. Especially your concerns over retrieving the texture data from the render target. And I don't mean to dismiss your edge-case concerns, I'm sure some edge cases would complicate things.

What I should be doing at this point is shutting up and implementing graphics-based mouse picking to see if I'm right or wrong. And quite possibly I'm wrong, because you never really know until you try something. But since I don't need it in my game, I'm unfortunately all talk and no action. :(
Last edited by Jabberwocky on Tue Oct 21, 2008 6:03 am, edited 4 times in total.
0 x
Image

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Tue Oct 21, 2008 5:52 am

Klaim wrote:Jabberwocky> I though about a similar technique to do this (but only raw thinking as i'm not sure i need it myself). Can't it be done (at least to see the perfs) as a plugin?
It looks like we already have public access to everything needed to try it, don't we?
Sure, wherever it fits best.
0 x
Image

beaugard
OGRE Contributor
OGRE Contributor
Posts: 265
Joined: Sun Mar 25, 2007 1:48 pm

Post by beaugard » Tue Oct 21, 2008 8:57 am

Sure, wherever it fits best.
hm. isn't this exactly what I proposed way earlier - make it a custom scene manager or something, but keep it out of the core!

I am sure it would be highly appreciated.
0 x

User avatar
nullsquared
Old One
Posts: 3245
Joined: Tue Apr 24, 2007 8:23 pm
Location: NY, NY, USA

Post by nullsquared » Tue Oct 21, 2008 8:29 pm

Jabberwocky wrote:
nullsquared wrote: Not just user drawn stuff, but things like mirrors, terrains, portals, water, etc. Render a full scene just to pick? Can't be faster.
A terrain could be drawn with an id just like an entity.
Same with water.
Same with a mirror (I think).

Anything which uses a material to draw something (which is almost everything) can be changed to output an ID.
You're completely missing the point.

1) This will be slow - you'll need to rerender the whole scene just to pick something.

2) How do you differentiate? Given a certain ID/pixel colour, how do you know what it is? You can't just go (Ogre::Entity*)id, because it might not be an entity.

3) How do you gather hit point distance/position info?
And the worst case scenario about anything weird that somehow can't output an ID instead of a pixel colour is that you wouldn't be able to pick that object. Which may be acceptable for a few strange and uncommon edge cases.
Again, how do you know it's not pickable. Does '0x313fad34' sound like 'pickable entity' or 'non-pickable terrain' to you?
I don't understand the technology behind portals, but obviously it's highly advanced stuff that requires a lot of custom code, so it may not be unreasonable that getting portals to work with the "picking" code would require custom code, too. Since unmodified Ogre core doesn't support portals, I don't feel that any picking code would need to, either.
Just a stupid example I decided to throw out :lol:. Just for the record, you don't need to modify the Ogre core.
Let's say your app is rendering at 60 FPS.
Are you saying we can't afford to render 1 frame every time the user pushes the mouse button to pick something from the Scene? And quite possibly, it would be a far cheaper render, since we can cut out any expensive shaders, and everything would be a single pass.
Again, not just rendering. Ever notice that taking a screenshot takes a good second or two? Or at least 1/2 a second and if not maybe 1/4 a second? Same thing here. Obviously you're not going to write to a harddrive, but you need to read the render texture's contents on the CPU.
0 x

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Wed Oct 22, 2008 2:56 am

nullsquared wrote: You're completely missing the point.
It seems like we've intelligently talked over lots of issues, and it has overall been an enlightening thread. Is this how you discuss things with people in real life? If you're so frustrated, you probably shouldn't keep posting. Or maybe I'm just touchy. ;)
nullsquared wrote: 1) This will be slow - you'll need to rerender the whole scene just to pick something.
Yep. I think we're both starting to sound like broken records on this point. Obviously we have different opinions on whether this is a good idea or not. Fair enough.
nullsquared wrote: 2) How do you differentiate? Given a certain ID/pixel colour, how do you know what it is? You can't just go (Ogre::Entity*)id, because it might not be an entity.
Excellent point.
Ideally the ID would be provided by the user somehow. Often games/applications will already have some identifier for scene objects with an efficient lookup. It would be nice to allow reuse of that.
nullsquared wrote: 3) How do you gather hit point distance/position info?
You don't.
Not all tools are built to handle all tasks.

When talking about hit position / distance / normal, etc, you're definitely moving further down the "I need a physics engine" road.
nullsquared wrote: Again, how do you know it's not pickable. Does '0x313fad34' sound like 'pickable entity' or 'non-pickable terrain' to you?
Not sure if I completely understand your point here. Ideally anything which is non-pickable would output some kind of "Nothing" ID, like 0.
nullsquared wrote: Just a stupid example I decided to throw out :lol:. Just for the record, you don't need to modify the Ogre core.
Interesting. Go Ogre! :)
Again, not just rendering. Ever notice that taking a screenshot takes a good second or two? Or at least 1/2 a second and if not maybe 1/4 a second? Same thing here. Obviously you're not going to write to a harddrive, but you need to read the render texture's contents on the CPU.
Yep. I still agree this is one of your strongest points. I'm kinda feeling like we're at the point where somebody'd just have to try it. As you sort of implied, reading a pixel (or more) from the GPU is going to be a different story than compressing and writing a jpg to disk. Making guesses about one based on the other isn't very useful.
0 x
Image

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Wed Oct 22, 2008 3:08 am

I wonder if it's possible to do some math and somehow just render a subset of the screen. Perhaps even the single pixel location the user has clicked on. Or subsection in case of an RTS-style rectangle select. That would speed things up a lot.

Just a thought. Might be crazy.
0 x
Image

CABAListic
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 2903
Joined: Thu Jan 18, 2007 2:48 pm
Contact:

Post by CABAListic » Wed Oct 22, 2008 8:21 am

I'm not convinced that the slowness of the process is actually much of an issue. Since we're talking about mouse-picking by a user mostly, and users can only click ever so often, we're talking about something that would need to run once in a second, not every frame.
Furthermore, the application usually knows some things for the scenario, specifically it should know which entities are pickable in the first place. So, only render what actually makes sense. And, finally, there is a good chance you don't need pixel-*perfect* picking since the mouse is kind of a rough device, so rendering on a 512x512 texture or even lower might suffice.

So, what I would propose is a helper class for this particular problem. You set it up with the primary camera, it creates an internal render target, and then it does nothing. Once the user actually clicks something, you propagate the helper class with further info (entities that are clickable, perhaps prefiltered by a ray scene query on the bounding boxes), mapping entities to IDs, and the class renders exactly these entities and could perhaps even make use of the cached frustum culling by the camera (?). Really, the additional rendering is not much of a problem, it doesn't occur often, it's a relatively small target and it uses primitive shaders compared to what a full scene might use, plus it only renders a preselected number of entities. Only problem might be reading back the texture, but that would be a matter for profiling, not discussing about. As is so often stated, a programmer is particularly bad at guessing what takes noticable time and what doesn't ;)

I think the point here is: Don't try to make the process too clever - specifically do rely on the application to deliver necessary information.
0 x

User avatar
xadhoom
Minaton
Posts: 973
Joined: Fri Dec 28, 2007 4:35 pm
Location: Germany

Post by xadhoom » Wed Oct 22, 2008 8:35 am

Fyi

http://www.ogre3d.org/phpBB2/viewtopic.php?t=45267

It just uses Raycasting in a moderate scene...
0 x

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Wed Oct 22, 2008 8:56 am

Some nice implementation thoughts, CABAListic.

I was thinking about only rendering pickable entities too. But then you might miss rendering a non-pickable entity that is in front of a pickable entity, allowing you to pick something through a wall for example.

Other than that, great ideas.
0 x
Image

CABAListic
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 2903
Joined: Thu Jan 18, 2007 2:48 pm
Contact:

Post by CABAListic » Wed Oct 22, 2008 12:25 pm

Okay, yeah, you're right. How's the saying go? For every problem, there is a solution which is clean, elegant, easy - and wrong ;)
So, maybe I'll go with triangle-level raycasting rather than pixel-perfect queries for our project.
0 x

User avatar
Jabberwocky
OGRE Moderator
OGRE Moderator
Posts: 2819
Joined: Mon Mar 05, 2007 11:17 pm
Location: Canada
Contact:

Post by Jabberwocky » Wed Oct 22, 2008 12:34 pm

Well, just because that one optimization doesn't work doesn't mean we should trash the whole idea.

Depending on the poly-count of my scene (and some other factors) I'd still certainly be considering this approach over raycasting.
0 x
Image

CABAListic
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 2903
Joined: Thu Jan 18, 2007 2:48 pm
Contact:

Post by CABAListic » Wed Oct 22, 2008 1:52 pm

Certainly. You could still use the renderables that the camera frustum culling has left, have the user assign IDs to some and render any else with an ID of 0. But in that case, the rendering gets a lot more expensive since you're basically rerendering the scene, just with a simpler pixel shader. Of course, it's likely still absolutely reasonable since, as stated, you'd only render a single frame whenever you need to pick.
0 x

Vectrex
Ogre Magi
Posts: 1266
Joined: Tue Aug 12, 2003 1:53 am
Location: Melbourne, Australia
Contact:

Post by Vectrex » Wed Oct 22, 2008 3:15 pm

http://www.ogre3d.org/phpBB2/viewtopic. ... highlight=

just tried the demo and it seems to work rather nicely for picking
0 x

User avatar
TheSpaceMan
Gremlin
Posts: 151
Joined: Tue Jan 23, 2007 3:44 am
Contact:

Post by TheSpaceMan » Wed Oct 22, 2008 4:57 pm

I'm not sure if this was mentioned before or the technique being used.

I was condering doing some line picking by makeing a shader that render each entity with a id color, think something simular was mentioned here. And from that retrive the actual object, the thing i don't know is how to actualy return a working, correct integer from the shader to a texture for the actual look up.

Sorry for disturbing.
0 x
Using:
Ogre3D v1.4.9,
OIS,
Physx v2.8.1,
Personal Physx<->Ogre3D Bindings,
FMOD.
Goal: Current day Retro Engine.
Keywords: Dynamic Terrain, Lowpoly, Engine, Nostalgia
Visit my Blog: http://spacedev.wordpress.com

User avatar
Nauk
Gnoll
Posts: 647
Joined: Thu May 11, 2006 9:12 pm
Location: Bavaria
Contact:

Post by Nauk » Wed Oct 22, 2008 8:12 pm

Vectrex wrote:http://www.ogre3d.org/phpBB2/viewtopic. ... highlight=

just tried the demo and it seems to work rather nicely for picking
Thanks for testing it and the feedback, I have been using it since 8 months or so now in Artifex and it works pretty reliable and without performance issues. The only quirk I found so far is that sometimes small foiliage meshes (grass / flowers) consisting of 2 crossed quads and placed directly on the terrain only respond to the pick from certain angles, but it seems to me that the rayquery is unable to detect them on bounding box level in the first place. Right now we are working on it, but if any of you has interest and an idea what could be causing it, I would greatly appreciate it :)
0 x

gmueckl
Halfling
Posts: 44
Joined: Wed Aug 06, 2003 2:22 pm

Post by gmueckl » Thu Oct 23, 2008 9:06 pm

Just trying to stir things up here for the sake of discussion (feel free to ignore this):

Have you considered using mechanisms provided by the underlying rendering interface for picking? OpenGL provides selection buffers exactly for pixel-perfect picking. This is exactly what you've been talking about when reading back from the render target except that with selection buffers this is taken care of by the driver itself. There is much room for the driver for cutting the rendering pipeline short when using that interface as it only outputs the list of names, no further spatial information. I'm not 100% certain, but I think D3D has a similar interface (there's a D3D picking demo in the SDK after all). Why not add support for that in Ogre?
0 x

User avatar
bisco
OGRE Contributor
OGRE Contributor
Posts: 235
Joined: Wed Nov 03, 2004 5:01 pm
Location: London, United Kingdom

Re: Picking; linking x y screen coordinates to scene components

Post by bisco » Sun Mar 22, 2009 3:27 pm

gmueckl wrote:Just trying to stir things up here for the sake of discussion (feel free to ignore this):
Have you considered using mechanisms provided by the underlying rendering interface for picking? OpenGL provides selection buffers exactly for pixel-perfect picking. This is exactly what you've been talking about when reading back from the render target except that with selection buffers this is taken care of by the driver itself. There is much room for the driver for cutting the rendering pipeline short when using that interface as it only outputs the list of names, no further spatial information. I'm not 100% certain, but I think D3D has a similar interface (there's a D3D picking demo in the SDK after all). Why not add support for that in Ogre?
FYI, there is a tutorial on this page about selection mode in OpenGL:
http://www.lighthouse3d.com/opengl/picking/
0 x

Post Reply