3D Graphics Picking - What is the best approach for this scenario

Question

I am working on a project which allows users to pick 3d objects in a scene and I was wondering what everyone thought would be the best way to approach this particular scenario.

Basically we have a scene with at least 100 objects (they are low-poly but made from at least ~12-15 triangles) and up to about 1000-2000 objects.

Not all the objects will be "pickable" at all times because some objects will occlude others so "pickable" objects probably land in the range between 800-1500 (depending on the complexity of the scene).

When an object is "picked" we want it to be highlighted in some way so this means rendering it differently, this is trivial but we want picking to be done not only on single clicks but also drags - which means we want to run the picking algorithm a lot in a short space of time. Ideally the user would see objects highlighted while they were still in a "drag" operation - (meaning the picking should probably be done asynchronously as to not lag the main rendering?).

I have tried simple ray trace picking but this is obviously quite slow as we loop through all triangles in the scene to find the object.

I have also tried GPU-based picking - rendering the scene using a pixelbuffer that gives a unique color to each object but with the dragging operation this means multiple renders and GPU-to-CPU data transfer which doesn't have great performance.

Are there any other possibilities I could explore to try and get the performance and functionality I want?

Thanks for your time.

Answer 1

I have used an Octree before for this sort of thing and it seemed to be my best option. Every object can be placed in the corresponding node and tested through the usual Octree protocol. The real benefits come from offsetting the ray cast to the end of a spatial node when the current node is empty. This will surely give you significant gains over brute-forcing it.

The following link should give you a base with Octree's and how it is set up: Introduction to Octrees

While the link is only giving you a base, the use of the Octree is simply for reducing necessary checks, so judging by your question, you seem to already have the knowledge required to perform the actual picking.