Pixel perfect click/pick by key-colouring

What it says on the tin: a place to discuss proposed new features.
Post Reply
User avatar
fantasian
Halfling
Posts: 81
Joined: Fri May 29, 2009 8:47 am
Location: Selanic, Greece
x 2
Contact:

Pixel perfect click/pick by key-colouring

Post by fantasian »

Hello. I thought this would be a usual topic but found nothing relevant in the forums :

I saw elsewhere people suggesting that for pixel-perfect 3d object picking (mouse clicking), ray-casting per-triangle is the best way. What I had in mind was key-colouring (or color-keying :) ).

The scene is drawn in an off-screen buffer. Every separate clickable entity is drawn with its own flat distinct color, with no texturing, lighting, anti-aliasing or complex shaders. For speed purposes, the buffer could only be a small area around the position of the mouse cursor (3x3 or even 1x1 area :shock: ). If this isn't possible, maybe it could just be a scaled-down version of the screen (say 640x480).

So, when there is a mouse click, it's co-ordinates are translated to the off-screen buffer and by checking the color beneath it, we know instantaneously which object is right below the cursor with pixel-perfect accuracy.

How efficient is this method? How fast would it be to draw a complex scene with this dead-simple rendering every frame, alongside normal rendering?

Kind regards,

Bill Kotsias
Software Engineer & Games Programmer
Online Portfolio : http://bkotsias.net46.net/
Forthcoming game : http://kyballgame.com/
User avatar
SomeFusion
Gremlin
Posts: 191
Joined: Sun Dec 01, 2002 12:38 am
x 3

Re: Pixel perfect click/pick by key-colouring

Post by SomeFusion »

Hi,

I use this technique in my Lockenwickler editor. Even for large scenes I have not noticed any lag when executing a pick with my Geforce 8800 GTS.
You can find the code in the python-ogre wiki. Porting this to C++ is probably straight forward.

http://wiki.python-ogre.org/index.php/C ... ion_Buffer
Summoning Wars is an open source role-playing game, featuring both a single-player and a multiplayer mode for about 2 to 8 players.
http://www.sumwars.org
User avatar
FrameFever
Platinum Sponsor
Platinum Sponsor
Posts: 414
Joined: Fri Apr 27, 2007 10:05 am

Re: Pixel perfect click/pick by key-colouring

Post by FrameFever »

how big(width/height) is the selection buffer?
Do you render allways in the selection buffer, or only when selection is activated?
User avatar
SomeFusion
Gremlin
Posts: 191
Joined: Sun Dec 01, 2002 12:38 am
x 3

Re: Pixel perfect click/pick by key-colouring

Post by SomeFusion »

I render only when a click occurs. It renders at the same size as the render window is. Rendering always would be a waste of cycles :).
There's even allot of python code which is executed when a click occurs but there is no noticeable lag when clicking.
Summoning Wars is an open source role-playing game, featuring both a single-player and a multiplayer mode for about 2 to 8 players.
http://www.sumwars.org
User avatar
FrameFever
Platinum Sponsor
Platinum Sponsor
Posts: 414
Joined: Fri Apr 27, 2007 10:05 am

Re: Pixel perfect click/pick by key-colouring

Post by FrameFever »

So not usable when you want to react on a mouseMove event. Or what do you think?

Can you also select multiple elemts, which are behind each other?
User avatar
SomeFusion
Gremlin
Posts: 191
Joined: Sun Dec 01, 2002 12:38 am
x 3

Re: Pixel perfect click/pick by key-colouring

Post by SomeFusion »

I don't know if its fast enough to do every frame. It depends on how big your scene is. But I could imagine it would be a little slow.

This could possibly be implemented. But then you will have to render the scene multiple times, skipping the rendering of items that are selected already.
Summoning Wars is an open source role-playing game, featuring both a single-player and a multiplayer mode for about 2 to 8 players.
http://www.sumwars.org
User avatar
sinbad
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 19269
Joined: Sun Oct 06, 2002 11:19 pm
Location: Guernsey, Channel Islands
x 66
Contact:

Re: Pixel perfect click/pick by key-colouring

Post by sinbad »

I've already implemented exactly this technique in previous (non open-source) projects using Ogre - it's called a 'selection buffer'. Since it's mostly used with editors for picking, the overhead of generating the selection buffer isn't that big a deal, but I wouldn't want to do it every frame; I'd do it on-demand.

It's really project-specific too - in editors for example you often deal with layers or 'locked' objects which mean you might not want to be able to select everything that is usually rendered. Similarly you want to treat skyboxes and other effects differently sometimes, and group rendered objects that use different materials in Ogre into one object for selection purposes.

The general approach I take is to tag all my Renderable instances (via visitRenderables() usually) with an Any containing a pointer to 'context object' which is project-specific. This allows me to do the grouping / layering / locking of selection criteria. Then, before I update the selection buffer I register a MaterialManager::Listener (and I unregister it after the update). I then set the viewport on the selection buffer to use a material scheme like 'Selection' - which incidentally I don't implement on any of my materials. I then call update() on the selection buffer.

As the scene gets pushed on to the render queue, my listener's handleSchemeNotFound method gets called, beacuse it doesn't know how to handle the 'Selection' scheme. In that implementation, I assign a material Technique which renders the object in a solid colour; what colour this is depends on the context object attached in the Any of the Renderable. Usually, I just generate unique colours as I discover new context objects in the frame, and as I discover them, I add them to a map which indexes the colour back to the context.

After the render, I can read back the content of the texture (note, this creates a pipeline stall if you do it straight away after the selection buffer update, so there will be a slight delay), then use the map I have to convert that colour into a context object I already discovered. Hey presto, pixel-perfect selection.

About the selection of objects that are behind each other, this is very tricky. You could do it by excluding objects that are already selected, but that means you can't click on the same object twice which is counter-intuitive. The only way to really do it is to use the separate channels of the selection buffer - say red for selected objects, green/blue/alpha for unselected objects. Then on the second click you could choose to prefer the green/blue/alpha result first over the red result if you wanted to toggle between objects (but it would only work for two). But you have to be careful about colour precision.
User avatar
SomeFusion
Gremlin
Posts: 191
Joined: Sun Dec 01, 2002 12:38 am
x 3

Re: Pixel perfect click/pick by key-colouring

Post by SomeFusion »

A cheap trick would also be assigning completely transparent material to the already selected objects when handleSchemeNotFound is called.
Summoning Wars is an open source role-playing game, featuring both a single-player and a multiplayer mode for about 2 to 8 players.
http://www.sumwars.org
ShadeOgre
Gremlin
Posts: 158
Joined: Mon Mar 10, 2008 10:55 pm
Location: Budapest, Hungary
x 1

Re: Pixel perfect click/pick by key-colouring

Post by ShadeOgre »

What about plus 1 step: set a stencil filter around the cursor to minimize the drawing after? Maybe this could allow the mouse-move/selection-every-frame feature.
Post Reply