I am developing a CAD-like application where the user can draw (digitize) new geometries (points, polylines & polygons). While digitizing, I want the user to be able to (optionally) snap the points of the new shape onto points or lines of existing geometries. I have already written the snapping algorithm that computes a ray from the mouse position and finds a line segment between the ray and the closest geometry (point or line segment). My scene is totally static but may contain too many shapes, which makes brute force searching inefficient.
What would be a good way to index the existing geometries so that I could quickly filter most of them out and consider a smaller set (the ones roughly within distance X) in my snapping algorithm?
I was thinking of doing something similar to what OpenGL (I am using DirectX 9 in my app) provides with the GL_SELECT option, i.e. render my geometries on a bitmap, each one coded with a different color. However I am a bit worried since I will have to use a second device with a hidden window to achieve this.
Is there a 3D space partitioning data structure that I can use, which can efficiently compute the nearest neighbour to a ray?
