PDA

View Full Version : realtime mouse picking



akuda
06-10-2006, 10:51 AM
Hi,

I'm trying to make a basic game in OGL, and currently working on an input system.

How to impement a mouse picking? I found some tutorials about object nameing, implemented that too, but I don't know how to get the output data (determine what was cliked on, during a frame).

I'm using SDL, so I can determine the X,Y in pixels.

soconne
06-10-2006, 05:41 PM
Here's a tutorial I wrote over at the Game Programming Wiki. It should suit what you're looking for.
Game Wiki (http://gpwiki.org/index.php/OpenGL_Selection_Using_Unique_Color_IDs)

akuda
06-11-2006, 03:47 AM
That is very helpful.

But now, which of the methods is better (faster, more realtime)?
The "Selection Buffer" method, or the "uniqe colors"?

soconne
06-11-2006, 07:13 PM
Well in my opinion, using unique colorIDs is much more flexible and doesn't require any opengl object creation, like the selection buffers. Plus no extra rendering pass is required, not really anyway.

ebray99
06-11-2006, 07:15 PM
Actually, in most professional titles I've worked on, we've done triangle picking by the following method:

1.) calculate ray into the scene, starting from the eye's position, and moving into the screen (you can calculate this using your field of view).

2.) determine which objects your ray hits and store them in an array or tree, ordered front to back.

3.) for each object (front to back), iterate through all triangles to determine points of intersection.

4.) Take the closest triangle you've intersected with.

5.) If you need additional data, such as texture coordinates, etc, simply calculate it for that triangle.

This will give you a very general picking system, and won't force you to render your scene for every ray you want to shoot into the scene. Also, you can use simplified geometry for this if you only need per-object intersection (for instance, the convex hulls generally used with physics).

- Kevin B

akuda
06-12-2006, 04:39 AM
hmm, but it still looks like, you have to calculate a lot. Color picking (if only I can determine a color even if it's covered by a texture (it is a question :) ) ) sounds fastest.

And, if I would have to iterate through all triangles, doesn't the OGL do the same, in GL_SELECTION mode?

Anyway, is any of this option fast enought for realtime applications, like games?

knackered
06-12-2006, 05:40 AM
obviously, rendering your entire scene (even a small frustums worth), then reading back a pixel from the framebuffer, is going to be slower than using your scene hiearchy for a fast bounds intersection check, followed by a a ray-triangle test against the lowest LOD version of the object.
You'll get away with the colour-coding method only if your viewpoint is going to be static while the user is picking, otherwise with anything but a simple scene you're going to have quite a judder in your frame rate when the user clicks.
Saying that, there have been circumstances in the past where I couldn't afford to keep the scene geometry in system memory too, so I had to use the colour-coding method.
Is this an advanced topic?

PS. GL_SELECTION is generally not accelerated on consumer boards, so really, really don't use it.

RigidBody
06-12-2006, 07:12 AM
Color picking (if only I can determine a color even if it's covered by a texture (it is a question :) ) ) sounds fastest.[/QB]if you choose that option, you would have to redraw your scene without light, without textures, without anything that could affect the color that you assigned to a particular triangle.

concerning the performance- if your game is at 30 fps and you loose one frame for selection it should not be a problem. drawing the scene for selection will take less time since you do not need to draw skyboxes or anything else that you don't want to be selected. anyway, just try it.

akuda
06-12-2006, 09:03 AM
I think, that during 1 frame everythinh is static, so mi idea was to render every frame twice: simplified for color picking (invisible for user) and the full-detail view. When a new frame is ready, I collect all the mouse events during last frame, process events (basing on simplified version), and then swap buffers.

Someone can say that in a moment the n'th frame is visible, it's already inactual, because it takes state made by mouse events made in n-2'th frame (when events are collected, the n-1 frame is ready) but I can't imagine how to afford that.

Overmind
06-12-2006, 11:05 AM
The problem with this method is that you still need a readback of data to the CPU, and this kills performance because it flushes the pipeline.

If you're really looking for the fastest algorithm, you should propably use what ebray99 proposed. It's more efficient than color picking in all but the most exotic cases.

And you're going to need the general mechanism sooner or later, because at some point you'll want to pick from another origin that's not at the camera (tracking projectiles, ...).

But if you're just looking for something easy to implement, go for color picking. It's not that bad for simple scenes...

AlexN
06-12-2006, 01:16 PM
With color picking you should ensure that antialiasing isn't going to be enabled. Doing it in the framebuffer could cause problems because people frequently force AA to be enabled through the driver, and this will mess up your color IDs.

akuda
06-13-2006, 11:50 AM
Aw, right...

Is there any way to prevent it?

akuda
06-13-2006, 11:59 AM
"Doing it in the framebuffer" - can I write in other buffer to prevent any AA modifications, even if they're forced to framebuffer by drivers?

What buffers are actually modified by AA forcing?

AlexN
06-13-2006, 12:23 PM
You can use FBO or pbuffer and it should work most of the time. Just like picking with opengl's selection mechanism, you are only rendering inside a small subset of your scene centered around the cursor, so you can get away with a low resolution render target. This is of course going to require that the user's driver support whichever method you choose (pbuffers are in older drivers), and also there is the possibility that the newer ATI cards might be capable of forcing AA even for off screen buffers...

akuda
06-13-2006, 01:10 PM
This is not what I was thinking about - I need a full frame (full window size) to handle all (more than one) mouse events during a frame.

Argh! So, the only way to make a *working* selectiom mechanism, is to implement it (geometricaly) myself?

How do I check all the triangles in a model, if they're in VBO? Should I have a copy of them in memory, just for iterating? No, it doesn't make sense.

This sounds really slow - i need to make (mouse events number)*(triangles in every visible model) checks, and after that, find the best match for each event... That's how professionals are doing this?

Is there any way to determine, is or is not the "force AA in this buffer" mechanism enabled?

ebray99
06-13-2006, 01:30 PM
Okay, I can't ethically let this kind of misguided information propogate.

Lets look at how these algorithms are similar and how they differ.

- For both algorithms you must traverse the scene.

- In one algorithm, you send triangles to the graphics card to be rendered. In the other, you iterate through your triangles and perform a triangle-ray intersection test.

- In the color coded algorithm, you must read from your framebuffer.

- In the color coded algorithm, you must assign objects ids, and then search for the object whose ID you hit.

I guarantee you that the triangle intersection method will not only cause you to write less code, it will also end up being faster in the end. Not to mention it's far more useful as it would allow you to cast arbitrary rays into your scene for collision purposes (as opposed to just offering you one purpose only).

Honestly, I look at this thread and simply see the refusal to learn the math required to write the code needed to calculate your ray and perform the triangle intersection test. (Don't get me wrong, I do think there are novel applications for the color coded algorithm, but these are few and far between).


How do I check all the triangles in a model, if they're in VBO? Should I have a copy of them in memory, just for iterating? No, it doesn't make sense. Yes, you should. Chances are, you'll need them for more than just mouse picking.

- Kevin B

akuda
06-13-2006, 01:49 PM
Ok, so how to do the itersection test? My idea was:

Get a vector parallel to screen's normal vector, with a beginning in a mouse event point (the x and y coords).
This vector shows the line of intersection.

Then, check if that line intersects a single triangle, by:
1. find an itersection point with a triangle's plane
2. check whether the point lies inside the triangle,
using area test condition (4 triangle areas), or with scalar products (not sure in translation) (like in Cormen's book).

Yes, I know math basics. But as a programmer and mathematic (no, really) I prefer to choose easiest method. And this looks like long-code, low-performance and easy-to-bug method. But if you say it's the only one working, I'll do it.

Ok, so now, I'm asking You, is there any code-trick that makes it easier than I said?
And, should I represent the vector as a float[3] or is there a simplier method?

ebray99
06-13-2006, 01:57 PM
Here is a link to a tutorial on the algorithm I've described.

http://www.devmaster.net/wiki/Picking

Note that the page says "Note that if you have more than a few dozen triangles in your scene, you probably do not want to test the ray against all of them! This could be very slow." Really, you can get away with thousands of triangles at interactive rates. Computers are fast =).

- Kevin B

akuda
06-13-2006, 01:58 PM
Aw, and there's another obstacle - all models are in the memory as set of triangles in a local point of reference. So, for every vector (or line), I would have to transform it, like the GPU does, when translation and rotation functions are called. This means, that I would have to make all transformation calculations twice (because when mouse events are processed, the scene is not being rendered).

Another option would be to (after rendering) save (for every model) it's MODELVIEW matrix, to make the calculations possible...

Aw... this sound like a few days long coding for a single student programmer...

ebray99
06-13-2006, 02:03 PM
You should store the object-to-world matrix with each model. When you are performing your pick, simply transform your ray from world space into object space (you can do this by using the inverse of the object-to-world matrix).

- Kevin B

akuda
06-13-2006, 02:04 PM
Is it something about clipping? Sorry, I didn't get to it yet. For now, for me it looks like I would have to check all the triangles are drawn, from objects that handles a mouse events (about 99%).

akuda
06-13-2006, 02:15 PM
You know what? Now it sounds that (using VBO), the "natural" OGL's pickin mechanism would be faster.

knackered
06-13-2006, 03:22 PM
he's all yours, kevin.

ebray99
06-13-2006, 11:00 PM
Akuda... I'm going to give you some of the best advice that I can give you. This the advice one of my mentors gave me when I first got into the game industry...

look it up on google. =)

- Kevin B

Overmind
06-14-2006, 08:22 AM
And this looks like long-code, low-performance and easy-to-bug method. But if you say it's the only one working, I'll do it.Noone said it's the only one working. But performance is actually exactly the other way round as you see it. OGL's picking has most likely the lowest performance, followed by color picking.

Doing it yourself has the best performance, because you have more chance to optimize.

Think about it that way: If you really test the ray with each triangle, you'll do about the same amount of work as GL picking, so GL picking is at least not significantly faster than the manual way.

In addition to that you can do your intersection test against a LOD hierarchy, so you do only O(log N) test instead of O(N) tests, so you're WAY faster.

grisha
06-15-2006, 01:50 AM
About color-picking - no need to render scene into whole vieport, you can create 1*1 pixel FBO just for picking and draw your scene into it with modified projection matrix.

akuda
06-15-2006, 07:33 AM
grisha - Yes, but it would handle only one event for frame.

About O(log N) - what type of tree you mean?

ZbuffeR
06-15-2006, 10:06 AM
Originally posted by akuda:
About O(log N) - what type of tree you mean? Octree, quadtree ... whatever suits your geometry.

akuda
06-17-2006, 04:17 AM
Hmm, about those trees, should the be built each frame, or built once, and actualize after a camera movement?

I hadly can imagine, how this should work.

akuda
06-17-2006, 05:51 AM
any tutorials?

Overmind
06-21-2006, 06:25 AM
The trees make only sense if they are build only once, not each frame. If you have moving objects, the best approach is to make a static tree for immobile objects and associate the moving objects with a tree node dynamically (that is, find the new node where the object should go after it moved every frame, but leave the rest of the tree as it is).