PDA

View Full Version : picking algorithm like silo selection


fasteez
05-13-2005, 09:57 PM
hy,
actually studying computer science, ive to develop a curve modelisation tool.
As id like to make it easy to use, im looking for a way to selection control points easily.
for the moment i can do classic picking "like" in maya or max.

i mean , on each mouse click , i get informations from opengl pipeline that helps me to select what under the mouse if i want.. but this is only an "after-click" thing... id like to be able to highlight the nearest point under my mouse pointer to help user to visualize better.

If its not clear, id like to understand how silo do their selection.. i was really knocked out on my feets because it works even for a complex model in the scene.
the main fact is i cant figure how to make this so interactive ... do they call opengl GL_SELECT mode each time the mouse moves or is their a "tricky" algorithm behind this.

if someone knows anything about things that can help , id be really glad that he gave it here.

thanks in advance , steez.

LetterRip
05-14-2005, 05:51 PM
Don't know how silo does it, but I required a similar algorithm when I developed sculpt mesh.

What I did was

1) divide the screen into bins.
2) find each verts screen coordinates and hash it into a bin
For edges and faces, you place the face and edge in each bin that one of the edges or faces verts is in. You also will need to check if the edge or face cross any additional bins and place them in those bins as well. (You can also hash the face center and the edge center, which is useful if you want to do free selection and the type of selection is based on what element type is nearest)
3) now as the mouse moves hash it to a bin (better is to have a bounding cube that is the size of your bins and hash the four corners to bins). Then check the each of the bins for the nearest element either based on element type, or just radius if you have free selection type.

LetterRip

fasteez
05-14-2005, 08:52 PM
okay
thanks for answering;
so if i get it right ; your bins are like some kind of screen space partitionning then instead of finding the closer element ( vertex, edge , face or whatever ) inside the total scene elements, you just search inside the bin under the mouse.
i thought about that but it seemed to me that projecting each vertex into 2D coordinates would be too expensive as you need to re"sort" the whole scene each time the point of view moves and unfortunately i cant take advantages of the fact that opengl already does the calculation to render the scene :(.
thx twice
steez

LetterRip
05-14-2005, 09:15 PM
on 100,000 verts it takes about two seconds with python, with that much geometry on screen the verts appear solid mass. If you are using c or c++ you could probably expect at least a 10 fold, and probably 100 fold speedup.

LetterRip

fasteez
05-14-2005, 09:34 PM
great, thats a m....fkin advice.
im doing this in java , its may not be as fast ( even if i think that for pure data manipulation its quite as fast, but i can guess wrong ) but i would never use a such amount of vertices, its a small studies project, i think ill never have to manage more than um lets say 1000 control points ( that would be a large total of complex curves )
can you tell me how you make your bins, i mean , do you make a sort of linear grid of a 2D space of do you use non uniform space partitioning in order to make the bins elements count quite average in each bin.

thx

ps : this reminds me of octree or quadtree .. whatever ;)

LetterRip
05-15-2005, 12:04 AM
Hi,

you can look at the code directly,

http://wiki.blender.org/pub/Blenderdev/SculpMesh/sculpt_mesh_tablet23.zip

do you make a sort of linear grid of a 2D space of do you use non uniform space partitioning in order to make the bins elements count quite average in each bin.

yep it is a 2d linear grid, since I'm using a brush for sculpting I basically used the maximum brush size as the bin size for simplicity, also the bins are small enough that going smaller or doing tricks to give equal points per bin doesn't gain me anything.

Yep similar in concept to octrees etc, I'm self taught so learned the structures after I created my own.

LetterRip

fasteez
05-15-2005, 10:40 AM
cool, ive some reading tonight ;)
thanks

CGTalk Moderation
05-15-2005, 10:40 AM
This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.