Pie Menus for X10 "uwm" Window Manager - June 1986

My second implementation of pie menus (source code), written in June of 1986, was an extension to the X10 "uwm" window manager.

I refactored "uwm" and integrated it into Mitch Bradley's Sun Forth system, to implement a Forth programmable window manager with pie menus called "pietest" (source code). I reprogramming the window manager's main loop in Forth, to perform an empirical comparison of pie menus with linear menus.

Later, I wrote this generic pie menu layout and tracking code written in C. It's free (as in speech) software that may be used as a basis to implement pie menus on other systems. It supports pie menus with any number of items. Each item can be of any positive angular width, as long as all the item widths add up to 360 degrees. Each item records the quadrant and slope of its leading edge. A leading edge is a ray going out from the menu center in the direction given by an item's (quadrant,slope) pair. The area of a pie menu item is the wedge between its leading edge, and the leading edge of the next menu item.

The generic pie menu tracking code is optimized to minimize floating point division and avoid calling atan2 during mouse tracking. But now most computers are much faster and have floating point hardware, so the optimizations are no longer necessary to keep up with the mouse (but they still might be useful on low end computers and small embedded devices).

Date: Fri, 20 Jun 86 19:16:38 EDT
From: Don Hopkins <don@brillig.umd.edu>
To: topaz!unipress!mg@seismo.css.gov
Cc: don@brillig.umd.edu
Subject: [sfbc!jab@lll-crg.arpa: Re: does anybody know what the following are...]

I fixed gralm. It's regrinding the host tables now. Theta menus are now running under the X uwm window manager! Shortly I can send you a tar file. What I want to do now is make it so that you can specify that a menu be pull-down or theta, with a variable you can set in your .uwmrc file controling the type of unspecified menus. I added a variable called menutheta that you can specify in your .uwmrc file that controls the size of the menu. Also, at this point, it does trig, i.e. t = atan2(x, y), whenever you move the mouse, normalizing it such that 0 <= t < 1, and multiplying by the number of items to get the item number. I will fix this by dividing the menu into 4 quadrants, and calculating the boundries in terms of quadrant and slope in that quadrant upon initializing the menu. Each item will have a quadrant and slope field for one of its edges, and when you move the mouse, you just figure out its quadrant and slope by looking at the signs of x and y, and dividing. Then you look through the linked list of selections for the one it falls in. This eliminates all the trig except for setting up the menu. What I have already runs quite well on a sun-2, and roars on a Sun-3. I've set up some useful menus and tried them out and they're very easy to use. Next step is making it smart about not overlapping item names.

-Don

Date: Thu, 17 Jul 86 20:13:14 EDT
From: Don Hopkins <don@brillig.umd.edu>
To: unipress!mg@topaz.rutgers.edu, mark@brillig.umd.edu, don@brillig.umd.edu
Subject: theta menus

The way to specify both the position of the middle of the 0th selection around the circle, and the radius of the menu, is to supply as input to the create_menu function an x and y offset from the center of the menu where the 0th item is to be centered. i.e.:

x=0,y=-40, 2 selections => radius of 40, 0th item is down, 1st is up, Yes/No menu.
x=-30, y=0, 2 selections => radius of 30, 0th iten is left, 1st is right, 0/1 menu.
x=20, y=20, 4 selections => radius of sqr(20^2+20^2) = 28.28, 0th item is NE, X shaped menu.
x=50, y=0, 12 selections => radius of 50, 0th item is up, clock face menu.

-Don

Date: Fri, 18 Jul 86 10:23:33 EDT
From: Don Hopkins <don@brillig.umd.edu>
To: mark@brillig.umd.edu, don@brillig.umd.edu
Subject: theta menus

I've modified the yacc code that parses the uwm init files to recognize the parameter for the initial menu selection position. It is an optional pair of numbers enclosed by angled brackets, i.e., <30,0>, that comes after the optional color specification. If you don't give it, it puts the initial item straight up, at the default radius. (Which you can specify in your .uwmrc file if you like)

menu = "menu name" (color1:color2:color3:color4) <x,y> {
"item name" : (color5:color6) :" action"
...
}

For example:

menu = "Bit" <0,-30> {
0: !"echo 0"
1: !"echo 1"
}

menu = "Direction" (red,blue,green,yellow) <40,0> {
Right: !"echo Right"
Left: !"echo Left"
}

menu = "Cross" <30,30> {
NE: !"echo up right"
SE: !"echo down right"
SW: !"echo down left"
NW: !"echo up left"
}

-Don

Date: Thu, 18 Sep 86 05:02:47 EDT
From: Don Hopkins <don@brillig.umd.edu>
Cc: don@brillig.umd.edu, unipress!mg@topaz.rutgers.edu
Subject: Pie menu ideas, and the punch line ...

I changed uwm so that it does not warp the mouse to the center of the menu when it puts it up. I had originaly done this because I wanted to always start in the middle of the menu, but what I really want is for the selection to be based on the angle of the movement from mouse down to mouse up, not from menu display to mouse up. The response it now a lot better (i.e. the movement between mouse down and menu display is not ignored), and you get effective "mouse ahead". I have to bog down a Sun and see how well it performs then. That was when the warping version was lusing. It also makes for more reasonable behavior near the edges of the screen, due to an X bug in mouse warping I have have not been able to track down. Currently, if you invoke a menu where part might fall off the screen, it is moved so that it all fits onto the screen. This moves the center of the menu away from where the mouse down event was. The mouse was being warped to the middle, but as soon as you moved, it mysteriously warped back to where it was at the mouse down event. Without warping, it starts out with the selection in the direction of the mouse down event from the new menu center highlighted. This is better than what is WAS doing, but still not optimal. Do you think the menu shouldn't be forced to be completely on the screen? Should mouse tracking during menu selection allow the mouse to leave the screen? Or should it warp the mouse to new_menu_center + (mouse_down_location - current_mouse_location)? (Assuming the warp drive is operational.)

Menus can be displayed as labeled icons around the menu name label in the center, which may have arrows, spears, wedges, or other embelishments around it. For entries that invoke a submenu, the icon for the entry could be an scaled down image of the menu that it invokes (possibly with less detail) so that you can know by looking at the first menu what the next stroke should be. Alternativly, just the name of the submenu and maybe an icon could be displayed, but when tracking the mouse, selections that are menus would be highlighted by drawing the mini-menu. This might look less cluttered. When a submenu is selected, its mini-menu would zoom to normal size, and the parent menu could either vanish or stay underneath.

A menu that would work well in miniature form as a submenu:

                        ______
                        |    |
                        |    |
                        |    |
        ______          |    |
        |    |          |    |
        |    |          | 60 |
        |    |          |    |          ______
        |    |          |    |          |__6_|
        | 48 |          |    |
        |    |          |____|
        |    |
        |____|       Window Height
        ______
        |    |                          ______
        |    |          ______          |    |
        |    |          |    |          |_12_|
        | 36 |          |    |
        |    |          | 24 |
        |____|          |____|

You could choose from a set of 6 commonly used window sizes, with each being in a unique direction, or you could choose any intermediate value in between, by not constraining the choices to 6 sizes.

One thing that should be explored is the philosophy of convenient directions. What does it mean for a direction to be convenient? Easy to remember is convenient, but are there directions that are easier to specify with a mouse, touchpad, joystick, trackball, lightpen, footmouse, or whatever? Under what circumstances does a direction's convenience differ?

A selection's position relative to other selections is an important factor. A selections could be placed opposite of one that complements it, and 90 (or whatever) degrees away from ones that are orthogonal to it. What other ways are there to make selection directions easy to remember are there?

I think the following menu demonstrates this philosophy:

                           Any Height
           Any Size                         Next Size

    Any Width              Window Size          Common Width

        Previous Size                      Common Size
                          Common Height

A graphical representation could show a small version of each submenu, as well as the text label. The Common menus might have pointers showing the direction of each icon, while the Any menus would have the icons but not the arrows.

There could be another menu to choose a window size from a window's size ring (like an emacs kill ring: a circular array with one "current item" (displayed at the top of course)), and a way add and delete sizes. i.e. a size ring menu, where you choose a verb (select, replace, add, delete, next, previous, etc), and then (if appropriate) a noun (by selecting one of the sizes depicted in a menu). With the current item at the top, operations on the current item would always be the same sequence of strokes. This could be applied to rings of whatever you want.

Another similarly arranged set of menus could let you scale windows without changing the number of lines or columns. (i.e. change the font size.)

I am going to write the mouse tracking code next, and feed it some fake mouse actions as a test, and print out a "movie" of what would happen. Maybe I can cut them out and staple them together to make a flip-em cartoon.

To make mouse tracking much more efficient, when the mouse angle changes, the current then the neighboring selections should be compared against the new angle. No reason to start from the top of the list of selections each and every mouse movement. I'm thinking about efficient ways to do a fast binary search by first looking at sector numbers, and then at slopes when you've homed in. But if x% of the cases of mouse movement leave you in the same sector, y% in a neighbor, and z% somewhere else, and (pardon the ad hoc notation) x < y <<<<<<<<< z , is it worth the extra effort? The solution should work for degenerate cases (two, one, or even zero items) to be truly elegant.

Another thing to think about is how to represent the angle more efficiently. Instead of quad = {0,1,2,3} and 0 <= slope < infinity, how about quad = {0, 1}, and -infinity < slope < infinity ...? I don't think you could not describe straight up and down (or wherever) though. Is there a clever way to encode that? Or is it really worthwhile?

What do you think about confering with James Gosling about making pie menus fit into SunDew? Also, is there any news on the Sun Users Group meeting? I think it would be quite benificial to attend.

Simple Simon popped a Pie Men-u up on the screen.
With direction-al selection, all was peachy keen!

-Don