snap-to-point in CAD applications
Author
Hi all!
can anyone help me with implementation of a snap function as is seen in various CAD programs?
Suppose you have a list of geometrical primitives like points, lines and planes in 3D space. You then transform them to a plane and display them on screen. Now, when the user is moving the mouse cursor around, I would like to highlight and snap to the primitive nearest to the cursor.
How do you sort the primitives to find the nearest one as fast as possible?
Could you please point me in the right direction?
Many thanks.
The best way I could think of would be to use a quadtree to sort the screen, focusing on the mouse pointer. The general theory, in case you don't know, goes like this:
You divide the screen into four sections. You can then check which area of the screen is in, thereby eliminating a full 75% of the screen area to check. Then you continually divide this portion of the screen into smaller quadrants, until you have isolated the mouse pointer and just a few points. Usually the screen is divided once, then second on the quadrant, and once more for three total divisions - more than enough to shrink the area of collisions to check, but not so much that it would give you a performance hit. Then once you've got it narrowed down, you can check for the nearest point to snap to. And vavoom, you've got your snap.
For more information on Quadtrees, check out this Gamedev article:
http://www.gamedev.net/reference/programming/features/quadtrees/
There are, of course, other methods - this one just springs readily to mind.
You divide the screen into four sections. You can then check which area of the screen is in, thereby eliminating a full 75% of the screen area to check. Then you continually divide this portion of the screen into smaller quadrants, until you have isolated the mouse pointer and just a few points. Usually the screen is divided once, then second on the quadrant, and once more for three total divisions - more than enough to shrink the area of collisions to check, but not so much that it would give you a performance hit. Then once you've got it narrowed down, you can check for the nearest point to snap to. And vavoom, you've got your snap.
For more information on Quadtrees, check out this Gamedev article:
http://www.gamedev.net/reference/programming/features/quadtrees/
There are, of course, other methods - this one just springs readily to mind.
a quadtree might be more trouble than its worth
seeing as how this is for a user interface thing, which is only active while theyre moving the mouse, not every loop
what I did when i needed a snap-to-grid feature in my mesh editor was to simply loop thru every coordinate in my grid ( a 64*64 square or something), and take a dot product of the ray from each vert to the mouse selection ray, then just keep a track of the one with the biggest dot product value
performance cost was not noticable at all
of course that is a incredibly dumb way of doing it, since my grid was planar... and eventually i replaced it with the exact intersection math, but only as an exercise, it wasnt needed at all....
seeing as how this is for a user interface thing, which is only active while theyre moving the mouse, not every loop
what I did when i needed a snap-to-grid feature in my mesh editor was to simply loop thru every coordinate in my grid ( a 64*64 square or something), and take a dot product of the ray from each vert to the mouse selection ray, then just keep a track of the one with the biggest dot product value
performance cost was not noticable at all
of course that is a incredibly dumb way of doing it, since my grid was planar... and eventually i replaced it with the exact intersection math, but only as an exercise, it wasnt needed at all....
Author
Thank you very much for your replies. Since I already have an algorithm that linearly searches through all primitives to find the closest one, I will try the quadtree approach.
Thanks once again for the advice.
Thanks once again for the advice.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement