Sign in to follow this  
Odiee

Decision about implementing ray picking.

Recommended Posts

I'm currently in doubt about how to implement picking in my application. Considering I have many meshes on the screen, (say like 20-30) In witch way should I implement picking one of that objects. Should I iterate through the scene, testing one by one? In witch case, if selected object is the last, it would mean that I would do 29 unnecessary operations. In case I have 300 objects on the scene, that wouldn't be very efficient in a matter of time passed. The other way I was thinking is , to make objects "alive" so each of them can test it self that was it "him" that was selected. But this would also not be very efficient in a term of processor power (considering all objects would test them selves in the same time). Maybe I could do seperate object that would implement queue for scene objects to give them selves and queue object would one by one, in order that the objects are given, test each one. I'm puzzled here. Dos someone has some experience on this subject to recommend how this is done on commercial games, like war3 or starcraft?

Share this post


Link to post
Share on other sites

I can't tell you how picking is done in commercial games exactly, but there are some optimizations which should be pretty common. First of all, you'll only need to consider objects that are visible on the screen, so you can take advantage of view frustum culling to drastically cut down the number of objects you need to test. Since view frustum culling is a good idea for rendering too, you essentially get two optimizatons for the price (overhead cost) of one.

To perform the actual picking, it's also a good idea to intersect the ray against rough bounding volumes that are cheap to test first, like bounding spheres. This will most likely cut down the number of complex intersection tests (ray-mesh for example) down to only a few for most scenes. If checking bounding spheres still requires too much time, a further optimization would be to use a spatial partitioning technique like an octree to cut down the number of tests even further. But between the view frustum culling and using bounding spheres, I never had any performance issues with picking myself.

Hope this helps :)

Share this post


Link to post
Share on other sites
Moved to 'Game Programming' as this has little direct relevance to DirectX.

remigius' answer is pretty much all you need. The key in my experience is the heirarchical testing - test simple bounding primitives (or bounding primitives around bounding primitives - e.g. a tree structure) to quickly reject objects that can't possibly be a valid result. Ray-sphere tests are good for this job.

Ultimately this is just another search algorithm, so the various 'classic' algorithms can at least give you some inspiration on how to solve this efficiently. Organising your objects as a heirarchy of bounding boxes is not too dissimilar to a binary search for example...

hth
Jack

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