Eliminating Divides During Pie Menu Tracking - September 1987

Date: Mon, 14 Sep 87 03:03:46 EST
From: Don Hopkins <don@brillig.umd.edu>
To: weiser.pa@xerox.com
Cc: don@brillig.umd.edu
Subject: Eliminating divides during pie menu tracking

Vaughn Pratt suggested an improvement to my quadrant-slope algorythm for pie menu tracking, which eliminates the division done every time the mouse moves during cursor tracking. You can eliminate the divide used to calculate the cursor slope, by multiplying both sides of the slope comparison by the denominator of the cursor slope. i.e. as before, do the divisions to calculate the slopes of the slice edges when laying out the menu. But when tracking the cursor, and comparing its slope with the slice edge slopes, instead of dividing to get the cursor slope, and comparing it with the slice edge slopes, you compare the numerator of the cursor slope with the denominator of the cursor slope times the slice edge slope.

I put the modification into uwm, and it works fine! I want to fix the NeWS pie menus to use this scheme, because they're using atan2 now, and they seem to feel "heavy" when things are going on. Anyway, atan2 loses if you want to have different sized wedges.

-Don

From: don@brillig.umd.edu
To: pratt%aster@sun.com
Date: Fri, 11 Sep 87 04:00:48 EST
Subject: Eliminating divides in quadrant-slope comparisons

I made the change that you suggested to my pie menu cursor tracking algorithm -- it's working just great, and saving zillions of divisions!

Here is a description of the algorithm, on a much more convenient medium than Two Guys from Italy napkins:

When tracking the cursor in a pie menu, every time the cursor moves, a check is made to see if it has moved into a different slice of the menu. This is done by comparing the angles of the slice edges with the angle from the menu center to the cursor. Instead of representing the angles as degrees or radians, and using atan2 to get the cursor angle during tracking, an angle is encoded as a quadrant and a slope. The quadrant and slope are defined such that as the angle around the circle increases, the quadrant and (always positive) slope increase.

The quadrant and slope may be defined thusly:

            Y
          ^
  s=-x/y  |  s=y/x
          |
  quad 1  |  quad 0
 x<=0,y>0 | x>0,y>=0   X
----------+---------->
  quad 2  |  quad 3
 x<0,y<=0 | x>=0,y<0
          |
 s=-y/-x  |  s=x/-y
          |

(However, in my X pie menu implementation, from which I removed the division, everything's upside down and inside out, due to the screen coordinate system. I'll get it right when I put quadrant-slope tracking into NeWS pie menus.)

The case of x=0,y=0 is never encountered, because the center of the menu (inside a certain radius, or a square if you want to be quick&tacky) is an inactive region, which makes no selection from the menu. The case of no selection is the first things tested for.

Another thing I still need to teach it to do is to check against the edges of the current slice first, then the neighboring slices, and finally the rest of the slices. That will handle most cases with only a few comparisons.

As you suggested, I eliminate the divide that was used to calculate the cursor slope, by multiplying both sides of the slope comparison by the denominator of the cursor slope. i.e. as before, I do cos, sin, and division to calculate the slopes of the slice edges when laying out the menu, but when tracking the cursor, and comparing its slope with the slice edge slopes, instead of dividing the (x,y) cursor offset to get the cursor slope, I now compare the numerator of the cursor slope with the denominator of the cursor slope times the slice edge slope. i.e.:

        numerator / denominator < slice.leftedge.slope

is the same as

        numerator < denominator * slice.leftedge.slope

(Given numerator >= 0, denominator > 0)

Thanks a lot for the suggestion! I don't remember the name of the chap with the beard who was visiting from England, but if you think he'd be interested, you can forward him this.

-Don

Date: Fri, 11 Sep 87 10:16:09 PDT
From: coraki!pratt@Sun.COM (Vaughan Pratt)
To: Don Hopkins <don@brillig.umd.edu>
Subject: Re: Eliminating divides in quadrant-slope comparisons

Great, glad it worked out. I forwarded your message to Mike Pitteway (the visiting Pommie).