PDA

View Full Version : Selection Mode is slooooow!



redarrow
04-02-2005, 01:39 AM
Hi,

I'm using selection mode in a 3d designer app I'm working on,
It's extremely slow I need to be able to individuly select from hundereds of vertices.
Selection mode just doesn't seem to be good enough.
Are there any "smarter" ways of selecting stuff?
Or can I speed selection mode up someway?

One more point: It works fine and quick if I just pick a single point (even among thousands) the real
problem comes when I drag a selection rectangle - the bigger it is the longer it takes.

Thanks

redarrow
04-02-2005, 01:42 AM
How on earth did that happen?
I only posted once and now there are two copies????

LarsMiddendorf
04-02-2005, 01:57 AM
Selection is very slow when using Vertex Buffers.

RigidBody
04-02-2005, 02:12 AM
use gluProject to get the window coordinates wx/wy for each vertex. define a selection rectangle (x_left, y_bottom)->(x_right, y_top) and select vertex if


x_left <= wx <= x_right
y_bottom <= wy <= y_topnote that in opengl (wx,wy) = (0,0) is the bottom left of the window, but in some window systems the top left.

knackered
04-02-2005, 02:35 AM
You could software transform every vertex, yes...if you were mad.
Alternatively, you could transform the selection rectangle into world space to give you a selection 3d box made out of 6 planes and test every vertex against those 6 planes. This would be an order of magnitude more efficient than RigidBody's suggestion. More efficient=faster+scaleable.

RigidBody
04-02-2005, 05:00 AM
well, using gluProject is the simplest idea that comes to my mind. easy to realize, just a for-loop and there you are. and for only some thousand vertices there should be no performance problem.

that 6-plane-thing sounds interesting, but i think to get it work i would have to think too much :D by the way, if you do it like that you should use only 4 planes (not 6), because your selection volume would go into infinity in two directions.

knackered
04-02-2005, 09:53 AM
No it wouldn't, it would go from the near plane to the far plane in world space. You have to test with all 6 planes as you're doing an inside-test with a volume suspended in world space.
This is ultra simple stuff...you can even use gluUnproject if you want. There's nothing wrong with doing some thinking, it's what separates us from the animals.

RigidBody
04-02-2005, 10:04 AM
ok. using the clipping planes limits the selected points to the visible ones. which maybe wanted, or not.

by the way: animals think, too. not so fast, not so deeply, but they do. some even use tools.

what separates us from animals is the ability to laugh (said peter ustinov) or maybe the ability to play (said someone else).

in my personal opinion we are not much different from animals. but that is a religious thing.

redarrow
04-02-2005, 10:15 AM
Thanks all,

I'll do some thinking ;-)
and I'll give the 6 plane thing a try - I tend to agree with RigidBody that it's a lot of hard thinking.
But I need (want) the best performance, so I guess I gotta do it.
Maybe my collie dog can help me? ;-)

RigidBody
04-02-2005, 10:44 AM
yeah, give your dog a try. maybe it's worth it- think of lassie...

anyway, i don't think selection is simple stuff, because there are many possibilities of what you want to select. the best solution can depend on:

* do you want to select a point that is part of a polygon or the polygon itself?

* do you want to select the entity (node/polygon) that is close (in z-direction) to the viewer? do you want to avoid selecting a node that is occluded by another polygon?

* do you want the entity close to the pointer or many entities contained in a picking rectangle?

after some years of hick-hack i found an optimal solution for selecting a polygon: draw the whole scene in the back buffer(without light, without swapping, depth test enabled), giving each polygon a unique color. in 24-bit color mode you can draw 16.7 million polygons with each in a different color. read the color buffer at the pointer position and by the color you find the polygon which you clicked on.

maybe it helps if you give more information about the program you want to make and its purpose.

knackered
04-02-2005, 12:24 PM
That solution isn't scaleable, and has a one frame latency.
When dealing with extremely large datasets, you typically want selection to be quicker than rendering (the render time for a 16 million poly model is going to be noticeable when selecting using a geforce6800, let alone a RivaTNT). So it's typically not a scaleable approach, especially seeing as though selection is usually only useful in a designer environment, so typically dealing with hi LODs for the majority of the time (most designer software only re-renders when regions of the screen get dirty, remember).
But calculating the 6 planes of the selection volume is trivial, then testing vertices against this volume is trivial and fast (a dot product for each plane, each time eliminating a huge percentage of vertices from further testing).
I just can't get my head round the idea that a bit of basic linear algebra is overkill for this situation. As I say, use glUnproject to give you the selection rectangle points in world space, stick them into the plane equation and iterate over your vertices...it's easy.