deragon@CADMAN.NYU.EDU (John Deragon) (12/16/89)
Hi, I was wondering how the current applications like MacDraw, MacDraft...etc etc do the line selection. For example in MacDraw you click on the line and it becomes selected? How does it do this? What is it testing on mouseDown? Thanks.. john.
trebor@biar.UUCP (Robert J Woodhead) (12/17/89)
deragon@CADMAN.NYU.EDU (John Deragon) writes: > I was wondering how the current applications like >MacDraw, MacDraft...etc etc do the line selection. For example in >MacDraw you click on the line and it becomes selected? How does it >do this? What is it testing on mouseDown? I don't know how THEY do it, but at first thought, the way I would do it is as follows: 1) Note that every object has an associated rectangle that contains it. 2) When a mouseDown occurs, we can check the position against the rectangles for the objects, in order of the object's frontness. 3) If this matches, we then go into a special checking routine, one for each object type, that does any special checks needed to determine if there is really a hit. The most obvious optimization is to note that objects not in display cannot be clicked on; thus anytime we scroll the window, generate a list of all the objects that intersect it (easy to do since we have to find them to display them) - then on clicks we only have to search this subset. -- Robert J Woodhead, Biar Games, Inc. !uunet!biar!trebor | trebor@biar.UUCP Announcing TEMPORAL EXPRESS. For only $999,999.95 (per page), your message will be carefully stored, then sent back in time as soon as technologically possible. TEMEX - when it absolutely, postively has to be there yesterday!
jackiw@cs.swarthmore.edu (Nick Jackiw) (12/17/89)
deragon@CADMAN.NYU.EDU (John Deragon) writes: > I was wondering how the current applications like > MacDraw, MacDraft...etc etc do the line selection. For example in > MacDraw you click on the line and it becomes selected? How does it > do this? What is it testing on mouseDown? Presumably you store you objects in some sort of list. Rather than check if each line is some pixel-distance close to the mouseDown (which can get very expensive, if you have lots of lines in your list), it's good to implement some sort of preprocessing. In my object-manipulating program, each object has a HitZone:Rect field, which is simply the minimal bounding box of that object. So for any line segment between X1,Y1 and X2,Y2, SetRect(HitZone, min(X1,X2),min(Y1,Y2),max(X1,X2),max(y1,y2)). Then, once you've got the mouseDown, run through the list. If mousePt is in HitZone, then there's possibly a hit on this line. At this point, you'll have to do some more cumbersome math. As you may recall from school, the distance between is hairy. Rather than rederive it all for you, I'll give you one--that seems to me pretty computationally efficient--free. Given: point P(p,q) / line L through 2 pts (x1,y1), (x2,y2) Test: is the distance D from P to L less than k units? Let dX=(x2-x1) dY=(y2-y1) dP=p-x1 dQ=q-y1 D=abs(dQ*dX-dP*dY)/sqrt(dX*dX+dY*dY) But sqrts and real divides are extremely costly, therefore continue So D<k (k>0) iff |dQdX-dPdY|^2<k^2(dX^2+dY^2) which is true iff ((dQdX-dPdY)^2-k^2(dX^2+dY^2)<0. The cool thing about this is that the whole right term (k^23(dxdx+dYdY)) is constant for each line. That means you can work it out just once, when the line is drawn, and then when you're paging through the list of objects, you'll only have to compute the left term and compare it to the stored term. Of course, be sure to recalculate the stored term if you reorient the line. Also note that this treats the line as a geometric line (extending to infinity in both directions), so it will register false hits if your line is only a ray or a segment. Fortunately, if you FIRST decide whether the line could possibly be hit by checking if the mouseDown was in the HitZone, then you'll clip out all possible hits except those on the segment. (My program is a geometry program which uses segs, rays, and lines; so I needed this flexibility. Somebody else may be able to derive a quicker way to check if you're limited to segments.) Hope this helps. -Nick -- _ _|\____ Nick Jackiw | Visual Geometry Project | Math Department / /_/ O> \ ------------+-------------------------+ Swarthmore College | O> | 215-328-8225| jackiw@cs.swarthmore.edu| Swarthmore PA 19081 \_Guernica_/ ------------+-------------------------+ USA
jmunkki@kampi.hut.fi (Juri Munkki) (12/17/89)
In article <8912160053.AA00720@cadman.nyu.edu> deragon@CADMAN.NYU.EDU (John Deragon) writes: > I was wondering how the current applications like >MacDraw, MacDraft...etc etc do the line selection. For example in >MacDraw you click on the line and it becomes selected? How does it >do this? What is it testing on mouseDown? I think I read that MacDraw uses QuickDraw to do this. You need a grafport with a single pixel (or many pixels, if your pointer should not be with single pixel resolution). Then draw all objects with a black penpat. Check the pixel after every object and stop when it is black. The last object you drew was hit. You have to draw the objects from front to back. I also recommend that you create a "select next object" menu item that resumes the last selection check. You also have to set up the grafport so that the single pixel (or group of pixels) have the coordinates of the mousedown. I wrote a very simple Bezier curve program and used my own window as the checking grafport. This causes a pixel to blink and you have to update that pixel after this routine, so I recommend that you use an offscreen bitmap. Offscreen bitmaps have the benefit that you can just a look at the bitmap contents without having to call GetPixel. This algorithm is surprisingly fast. I guess QuickDraw clips so well that discards most objects without even considering them. Most of the overhead probably still comes from trap dispatches. _._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._._ | Juri Munkki jmunkki@hut.fi jmunkki@fingate.bitnet I Want Ne | | Helsinki University of Technology Computing Centre My Own XT | ^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^~^
jb@aries5.uucp (James Bruyn) (12/18/89)
In article <981@biar.UUCP> trebor@biar.UUCP (Robert J Woodhead) writes: >deragon@CADMAN.NYU.EDU (John Deragon) writes: > >> I was wondering how the current applications like >>MacDraw, MacDraft...etc etc do the line selection. For example in >>MacDraw you click on the line and it becomes selected? How does it >>do this? What is it testing on mouseDown? > >I don't know how THEY do it, but at first thought, the way I would do >it is as follows: > >1) Note that every object has an associated rectangle that contains >it. > That was my immediate thought to - gee how simple. But then I realized that a line could be on a diagonal, and the enclosing rectangle would then be quite large. So I think a more reasonable way would be to define a region around the line with some room for slop. i.e. assuming the line goes from lower left to upper right. (left.h-3,left.v-3;, right.h+3, right.h-3; right.h+3, right.v+3; left.h+3, left.v+3; left.h+3, left.v-3) and then checking whether the mouse in local coordinates is within the region. Jim Bruyn Computer Systems Group University of Waterloo.
trebor@biar.UUCP (Robert J Woodhead) (12/18/89)
jb@aries5.uucp (James Bruyn) writes: >That was my immediate thought to - gee how simple. But then I realized >that a line could be on a diagonal, and the enclosing rectangle would >then be quite large. So I think a more reasonable way would be >to define a region around the line with some room for slop. i.e. Jim, what do you think a Region is? It is a structured grouping of rectangles. Such a region is going to be seriously huge and slow to check. Sure, you are going to check the line rect often in the case of diagonals? So what? Given the start and end point it is a simple calculation to determine how "close" the click is to the line. Given: Cx,Cy Click X and Y Sx,Sy Line start X and Y Ex,Ey Line end X and Y Lx,Ly Points on Line near Cx,Cy (vertically or horizontally) Slope used in expressing line parametrically (This uses floating point math for simplicity but can be done using fake fixed point very quickly) Note : assumes Sx<>Ex and Sy<>Ey, eg: diagonal line Note : off the top of my head, don't flame for stupid screwups! Slope := (Ex-Sx) / (Ey-Sy); { slope of the line } Ly := Sy + ((Cy-Sy)*Slope); Slope := (Ey-Sy) / (Ex-Sx); { slope expressed other way } Lx := Sx + ((Cx-Sx)*Slope); if (abs(Lx-Cx)<CRITERIA) or (abs(Ly-Cy)<CRITERIA) then begin { hit code } end; In this case the points Cx,Ly and Lx,Cy are the two points on the line between Sx,Sy and Ex,Ey that are reached by travelling vertically (up or down) or horizontally from Cx,Cy. Since you want to be at most a couple of dots away anyway, this is a good enough approximation. -- Robert J Woodhead, Biar Games, Inc. !uunet!biar!trebor | trebor@biar.UUCP Announcing TEMPORAL EXPRESS. For only $999,999.95 (per page), your message will be carefully stored, then sent back in time as soon as technologically possible. TEMEX - when it absolutely, postively has to be there yesterday!
jackiw@cs.swarthmore.edu (Nick Jackiw) (12/19/89)
jb@aries5.UUCP (James Bruyn) writes: > In article <981@biar.UUCP> trebor@biar.UUCP (Robert J Woodhead) writes: > >deragon@CADMAN.NYU.EDU (John Deragon) writes: > That was my immediate thought to - gee how simple. But then I realized > that a line could be on a diagonal, and the enclosing rectangle would > then be quite large. So I think a more reasonable way would be > to define a region around the line with some room for slop. i.e. > assuming the line goes from lower left to upper right. > (left.h-3,left.v-3;, > right.h+3, right.h-3; > right.h+3, right.v+3; > left.h+3, left.v+3; > left.h+3, left.v-3) > and then checking whether the mouse in local coordinates is within the > region. Regions are essentially stored as composite rectangles, in a somewhat compressed format. (MacTutor once documented their internal structure.) Diagonal lines are composed of a number of rectangles proportional to the degree to which the slope of the line reaches 1 (in which each pixel requires a separate rectangle). A quick check reveals that a rgn containing the area defined by MoveTo(0,0) / LineTo(150,0) is 10 bytes--one rectangle because the line is horizontal--but the size of MoveTo(0,0) / LineTo(150,150) is 1212 bytes--over 1K of memory. This is a short line; longer lines take more space. Obviously, this is computationally dreadful... if your heap space is tight, you could even cause a scramble during selection, which will lead to miserable performance. I maintain that the most computationally efficient method is to check the bounding rectangle (which, I agree, gets progressive less useful the closer to slope=1 your line is), and--if the mouse point lies within it-- to calculate the distance between the point and the line in a mathematical fashion rather than in some Quickdraw-related one. I posted here three days ago a solution which required three integer multiplies and one integer subtraction per line to tell if a point was within some constant distance from a line. This is less overhead than *one* dispatch through the trap-table. Check your archives for the derivation. -Nick -- +-------------------+-jackiw@cs.swarthmore.edu / !rutgers!bpa!swatsun!jackiw-+ | nicholas jackiw | jackiw%campus.swarthmore.edu@swarthmr.bitnet | +-------------------+-VGP/MathDept/Swarthmore College, Swarthmore, PA 19081--+ "Ah...I've got this CHRONIC pain." _True Believer_
billkatt@mondo.engin.umich.edu (billkatt) (12/19/89)
In article <L7GB0A2@cs.swarthmore.edu> jackiw@cs.swarthmore.edu (Nick Jackiw) writes: >jb@aries5.UUCP (James Bruyn) writes: >> In article <981@biar.UUCP> trebor@biar.UUCP (Robert J Woodhead) writes: >> >deragon@CADMAN.NYU.EDU (John Deragon) writes: >> That was my immediate thought to - gee how simple. But then I realized >> that a line could be on a diagonal, and the enclosing rectangle would >> then be quite large. So I think a more reasonable way would be >> to define a region around the line with some room for slop. i.e. >> assuming the line goes from lower left to upper right. >> (left.h-3,left.v-3;, >> right.h+3, right.h-3; >> right.h+3, right.v+3; >> left.h+3, left.v+3; >> left.h+3, left.v-3) >> and then checking whether the mouse in local coordinates is within the >> region. > >Regions are essentially stored as composite rectangles, in a >somewhat compressed format. (MacTutor once documented their internal >structure.) Diagonal lines are composed of a number of rectangles >proportional to the degree to which the slope of the line reaches >1 (in which each pixel requires a separate rectangle). A quick check >reveals that a rgn containing the area defined by > > MoveTo(0,0) / LineTo(150,0) > >is 10 bytes--one rectangle because the line is horizontal--but the size of > > MoveTo(0,0) / LineTo(150,150) > >is 1212 bytes--over 1K of memory. This is a short line; longer lines take >more space. Obviously, this is computationally dreadful... if your heap >space is tight, you could even cause a scramble during selection, which >will lead to miserable performance. > Just because the data structure is large doesn't mean the useage is "computationally dreadful". It does gobble memory, but to check whether a point is inside or outside a region requires at max, x+y+1 bytes examined (where x and y are the distance from the top and left of the bounding box. This is excluding the initial point in rect check. This is cheap for most things, since it doesn't involve any multiplication or division. And I sincerely doubt you would get a heap scramble on just indexing through a list. You see, the regions are stored ahead of time, you don't make them every time you need to check. If you don't make any new data structures while indexing through, you aren't going to get a scramble. -Steve
lsr@Apple.COM (Larry Rosenstein) (12/19/89)
In article <1989Dec17.104221.23095@santra.uucp> jmunkki@kampi.hut.fi (Juri Munkki) writes: > grafport with a single pixel (or many pixels, if your pointer should > not be with single pixel resolution). Then draw all objects with a > black penpat. > > You have to draw the objects from front to back. I also recommend that You can draw the shapes back to front (the way you would draw them on the screen) and select the last one that touched the pixel. The advantage of this algorithm is that is works for any shape regardless of how complex it is. If you need to compute the distance to the shape then you need a different formula for lines, ovals, etc. > This algorithm is surprisingly fast. I guess QuickDraw clips so well I implemented this in a MacApp graphics building block, and it works very well. Larry Rosenstein, Apple Computer, Inc. Object Specialist Internet: lsr@Apple.com UUCP: {nsc, sun}!apple!lsr AppleLink: Rosenstein1
d88-jwa@nada.kth.se (Jon Watte) (12/20/89)
>Just because the data structure is large doesn't mean the useage is >"computationally dreadful". It does gobble memory, but to check whether a Do you think one kilobyte is OK for one line ? I am, besides a mac programmer, also a graphic designer. I would have to yurn off all INITS, find a small drawing program and run without MF just to make a business card ! And that's on a 5meg SE/30... The "First check box, then calculate distance" approach is, indeed, the most effective method for this, with the quickdraw method (open an offscreen port with a portRect the size of the "click area", and then draw the objects and check for blackity) a close second. Happy hacking ! h+@nada.kth.se -- -- Stay alert ! - Trust noone ! - Keep your laser handy ! --- h+@nada.kth.se == h+@proxxi.se == Jon Watte longer .sig available on request