opengl - Best algorithm for ray picking through a lot of spheres -

in opengl application have lot of spheres (more 100.000) , i'm willing implement efficient ray-picking algorithm.

my approach far naive one:

calculate ray (in object space) corresponding mouse pointer , intersect each sphere have ray. while approach may fast enough application (the actual rendering of spheres can become slower picking them ray...), wondering best approaches out there kind of situation.

i'm concerned fact sphere may have arbitrary radius, , don't know how take account in space partitioning structure such octree.

do have suggestion?

i'll add more details:

the application in question molecular viewer atoms represented spheres such in picture:

spheres can overlap partially or completely. scene can dynamic (you can molecular simulation), don't want pick during animation.

ideally, find solution can extended cylinders in future.

interesting question!

ray vs sphere collision test 1 of simple , why spheres used in determining pvs (potentially visible set).

basically enclose spheres larger spheres. first test ray collision huge sphere , if fails can sure other sphere inside big volume not colliding ray. if ray collides move inside volume , test next sphere in group... hierarchy save lot of computation time.

from o(n) (testing every sphere), can reach o(log n) (like in binary tree, or quad/oct tree).

one problem when hierarchy dynamic, have rebuild spheres. can rebuild whole tree - o(n log n) probably, or smart , rebuild moving parts of hierarchy. if k spheres moving time rebuilt can reduced around o(k log n) (for instance remove particular sphere , insert again)

here link tutorial about picking , a wiki bounding spheres