Sign in to follow this  
Langecrew

drag mouse to draw box, select objects within...free select???

Recommended Posts

Hi again! I'm rendering some point clouds, and I want the user to be able to use the mouse to drag a box around some points. Then, in the code, I would use selection to figure out which points were in the box the user drew. In many programs, like Microsoft Paint, there is an option to draw a box to select parts of the image underneath, but there is also an option to allow the user to draw a selection region of any size and shape...I think its called Free Selection or something. Selecting primitives under a box is easy, but what would be a good way to approach the idea of a "Free Select" function? I wager it would work OK if I limit the user to drawing points to create a "Free Select" region. After the user creates 2+ verticies for the free select region, a line loop would be drawn between them all, connecting the beginning and end of the free select line. After the user is done cutting things up I could make a polygon out of the verticies the user has created, and then cut that polygon into triangles, and then run my selection routine on each small triangle I could simply define the selection viewport to be one of these triangles and then select the items inside like normal. Will this work? is there a better way to approach that problem? Thanks, have a great day! -Langecrew-

Share this post


Link to post
Share on other sites
The method you suggest might work fine. You'll run across problems though if the user tries to make a concave shape with the selection; concave polygons don't split into triangles very well and you'll need additional logic to detect and deal with that kind of situation. You could prevent the user from creating a concave shape by detecting if the angle between vectors ever becomes more than 180 degrees. Then you could prevent a new point from being dragged further than 180 degrees, or invalidate the selection. Both of these have problems: locking a new point can lead to situations where the user can't complete a selection box, and invalidating a selection could mean the user would be constantly accidentally invalidating selections.

A better, more bullet-proof way might be to allow the user to draw any shape of selection box they want (just follow the mouse as Paint does), then project your 3D points to 2D screen coordinates and test to see if they're inside the selection volume the user drew. I believe this is the method used by Paint and other art programs, as well as 3D content creation tools like blender (but I could be wrong :). It eliminates having to cut the volume into polygons, and it keeps everything in 2D, so you can build a lookup table.

The best way (ie. works for all situations but is a bit complicated) would be this:
  • When the user finishes drawing their selection box, you'll have a list of 2D points where the user's mouse went.
  • Connect the end point to the start point (you must fill in the points between the start and end; you'll need to use Bresenham's line algorithm for this), then find the two points with the lowest and highest Y values. This will give you the top and bottom extents of the selection box.
  • For each line of screen pixels between the lowest and highest Y values:

    • Collect all of the points which occur on that line (have the same Y value as that line).
    • Sort them so that they go from lowest X value to highest X value.
    • The pixels between points 1 and 2 are "in" the selection box, the pixels between points 2 and 3 are "out", the pixels between points 3 and 4 are "in", and so on.
    • There are two special cases:

      • Two points are next to each other, and
      • There are an odd number of points on a line.

      Both of these have relatively simple solutions, but I don't have time to explain how to get around these at the moment. You can figure it out easily enough with a piece of graph paper, anyway [smile]
    • Record, for each line of pixels, the regions of pixels which are "in" the selection box, eg.

      struct InRegion
      {
          int startX;
          int endX;
      };


  • You now have a lookup table (perhaps an std::map like this - std::map< int, std::vector<InRegion> > - where the int is screen-line Y position). To find out if one of your 3D points is inside the selection box:

    • Unproject the 3D point to a 2D screen coordinate (using gluProject, for example)
    • Convert from float values to ints (the fast way - int ix = static_cast<int>( fx + 0.5f ))
    • Use the Y coord to find the screen line the 2D coord is on, and hence the potential InRegions
    • Test if it's X value is inside any of the InRegions
Like I say, a bit complicated, might be overkill for your project, but it works every time, and it should be pretty quick.

Wow, that was way more than I was planning to write, and a stack of edits on top. Hope it's helpful [grin]

[Edited by - iNsAn1tY on March 8, 2007 11:43:49 AM]

Share this post


Link to post
Share on other sites
Helpful? Oh man, that was great!

That definitely sounds like a better solution than what I was thinking of. I'll give it a shot, and if I run into any issues, I'll post back!



Thanks, and have a great day!
-Langecrew-

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this