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?


Try taking a look at KD trees; I use them in my engine for (amongst other things) preparing scenes for raytracing, and they are quite good at nearest neighbour searches for fairly large data sets (especially in conjunction with other structures like octrees if your dataset is massive). 'TinyRT' is a decent header libary which could get you started.

| improve this answer | |
  • \$\begingroup\$ Indeed k-d trees could be useful but I haven't yet found an implementation that deals with lines as well as points. I will take a look at TinyRT to get an idea, thanks. \$\endgroup\$ – kagelos Jul 28 '15 at 6:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.