Sign in to follow this  
kindREX

Fast Selection Technique

Recommended Posts

I am currently using back-buffer selection with vertex arrays to select vertices and faces on a 50,000+ quad mesh. It's running a bit slow (maybe because of glReadPixels?), so I was wondering if anyone can suggest an alternate technique or a way that I could speed it up? I am considering trying octrees.

Share this post


Link to post
Share on other sites
do it on the cpu perhaps, i think 50,000 verts aint much to do brute force.
50,000*4 plane -> point checks should be ok (note i assume this is for some modeling app + not a game )

Share this post


Link to post
Share on other sites
Octrees or some other partitioning technique is definitely the way to go.
Use some kind of hierarchical organization for your data like
Model
| -- Face 1
| |-- vertex 1
| |-- vertex 2
| |-- vertex 3
| |-- vertex 4
|
|-- Face 2
..
..

You can have an axis-aligned bounding box or bounding sphere for each node including for each vertex.

Don't use glReadPixels, it is slow.

Share this post


Link to post
Share on other sites
Thanks for the replies! It sounds like if I am going to use selection from a single point that shooting rays with octrees is the way to go. However, this is for a sculpting app that will have circular brushes. The average radius might be about 30 pixels, so that would mean shooting a lot of rays.

It seems like it might be better to project the geometry to the screen and test if it is inside my brush. Any thoughts on whether a vertex shader that basically does gluProject would be better than just doing it on the cpu?

Share this post


Link to post
Share on other sites
Quote:
Original post by kindREX
Thanks for the replies! It sounds like if I am going to use selection from a single point that shooting rays with octrees is the way to go. However, this is for a sculpting app that will have circular brushes. The average radius might be about 30 pixels, so that would mean shooting a lot of rays.

It seems like it might be better to project the geometry to the screen and test if it is inside my brush. Any thoughts on whether a vertex shader that basically does gluProject would be better than just doing it on the cpu?
I can't comment on the shader aspect, but you can use a picking volume rather than a picking ray to correspond with your brush (and to make it easier in general to select vertices).

The fact that the brush is circular does complicate things a bit. Typically a picking volume is associated with a drag-enclosed rectangle, which means that the picking volume is a volume similar to the view frustum. For a circular selection region this would become a cone, which is a little harder to work with (especially with respect to traversing the octree).

As for performing the picking in screen space, it seems you would still want to perform some initial culling in world space; otherwise you'd have to project every visible vertex to screen space, which could be quite expensive.

I'm sure this could be done efficiently though using some combination of the aforementioned methods. For example, you could cull in world space using a rectilinear picking volume, and then perform the narrow phase either in world space using a cone, or in screen space using a circle.

This is all just speculative - there may be better solutions that I'm not aware of or am just not thinking of at the moment.

Share this post


Link to post
Share on other sites

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

Sign in to follow this