   3D Picking - need help
  Hi all,I have a list of 4 million unique points. Each point is rotated by a quaternion on all three axes, then scaled by some random distance. My issues is trying to identify the correct point when I mouse click on it. I'm not sure if a ray point intersection will do the trick since I'd have to test against all 4 million points (or at least the ones with the same x,y as the ray).Is there a better way to do picking other than ray intersection?   
Quote:Original post by ou8her2Hi all,I have a list of 4 million unique points. Each point is rotated by a quaternion on all three axes, then scaled by some random distance. My issues is trying to identify the correct point when I mouse click on it. I'm not sure if a ray point intersection will do the trick since I'd have to test against all 4 million points (or at least the ones with the same x,y as the ray).Is there a better way to do picking other than ray intersection?Rather than using a picking ray, I'd recommend using a picking volume (which is basically a frustum corresponding to a rectangular area in screen space). Point-ray intersection isn't very well-defined, and using a volume should make the process of picking a point onscreen a bit more user-friendly.A picking volume may of course pick up more than one point at a time; in that case, you can select the point that is closest to the ray going through the center of the volume.For that many points, you will most likely need to use a spatial hierarchy of some sort. Four million is a lot of points, and I won't presume to tell you what spatial partitioning scheme would be optimal for your particular case, but a fairly obvious choice might be to use an octree. (Note that whether and how often the points move is another factor that needs to be taken into consideration when choosing a partitioning scheme.)   