Search code examples
algorithmopenglraytracing

Best algorithm for ray picking through a lot of spheres

In my OpenGL application I have a lot of spheres (more than 100.000) and I'm willing to implement an efficient ray-picking algorithm.

My approach so far was the naive one:

Calculate the ray (in object space) corresponding to the mouse pointer and then intersect each sphere that I have with the ray. While this approach may be fast enough for my application (the actual rendering of the spheres can become slower than picking them with a ray...), I was wondering which are the best approaches out there for this kind of situation.

I'm especially concerned with the fact that those sphere may have an arbitrary radius, and I don't know how to take this into account in a space partitioning structure such as an octree.

Do you have any suggestion?

I'll add some more details:

The application in question is a molecular viewer where the atoms are represented as spheres such as in this picture:

enter image description here

Spheres can overlap partially or completely. The scene can be dynamic (you can do a molecular simulation), but you usually don't want to pick anything during the animation.

Ideally, I would like to find a solution that can also be extended to cylinders in future.

Solution

  • interesting question!

    Ray vs Sphere collision test is one of the most simple and that it why spheres are often used in determining PVS (Potentially Visible Set).

    Basically you enclose spheres with larger spheres. First you test ray collision with huge sphere and if it fails you can be sure that any other sphere inside this big volume is also not colliding with the ray. If the ray collides then just move inside the volume and test the next sphere in the group... That hierarchy will save a lot of computation time.

    From O(N) (testing every sphere), you can reach O(Log N) (like in binary tree, or quad/oct tree).

    One problem is when your hierarchy is dynamic, then you will have to rebuild spheres. You can rebuild the whole tree - O(n Log n) probably, or be smart and rebuild only moving parts of the hierarchy. If K spheres are moving then the time to rebuilt can be reduced to around O(K Log N) (for instance remove particular sphere and then insert again)

    here is link to tutorial about picking and a wiki about bounding spheres