Jump to content
  • Advertisement
Sign in to follow this  
Miso

snap-to-point in CAD applications

This topic is 4957 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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....

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!