OSDev.org

Hello!

I was wondering what the best implementation of a simple window manager would be? In my current approach, the current graphics mode (either VGA or VESA) is represented as a Screen struct, which contains some info about the graphics mode as well as some resources. Screen has a root Window struct which has a mutable array of subwindows, and each Window has a View, which, in turn, has a subviews field. Each refresh, starting from the screen's root window, we traverse the entire hierarchy and draw from the bottom up. We write to a double buffer memcpy'd to the LFB.

Each Window, View, Screen etc has a needs_refresh flag, which gets set whenever a function like add_subview or set_background_color is called. Then, when we're traversing the hierarchy to draw each frame, if an element doesn't have needs_refresh set, we quit early and don't bother re-writing to the double buffer.

I have a PS/2 mouse driver and can't figure out a much more efficient way to check which window to give a click to besides traversing the entire hierarchy and returning the highest window that overlaps with the coordinates.

How are you tracking the z-order of the windows? Does your window structure have a "z position" field?

A simple approach would be to sort the array of windows so that the top window is at the start of the array, the next window down is next in the array, and so on. In other words, when a window is brought to the top, its structure is moved to the start of the array (you might want to implement the array as a linked list for efficiency). This way, you can start at the beginning of the array and work your way through, returning on the first window containing the click. When you refresh the screen, you start at the end of the array and draw each window in turn (your linked list will need to be a double-linked list - with links going in both directions).

You'll also want to think about the controls inside the windows - remember that in a modern GUI windows aren't just an array of pixels but contain a collection of controls, some of which may contain further controls, and which should each receive their own events. You mentioned views and subviews - when you find the window that was clicked, are you then iterating through the views and subviews inside the window to find which one the click was in, and then passing the subview's identifier to the window when it receives the click event?

+1 for the sorted array list as the z-index.

I would just add that id consider the control elements inside a window to be part of the widget toolkit, which will also decide on which control element gets clicked etc, and not the window manager. MDI windows might be sub-views though?

Things get simpler if you start by implementing text-mode windows.

Then you can concentrate in things more fundamental than basic drawing, although it would always be necessary to calculate hidden regions, the coordinates of window controls, and those of mouse clicks.


Also start by worrying to update only the currently focused window and actively changing areas in other background windows. No matter if you get lost at the beginning when selecting something else outside the current window. In this way you can concentrate first in implementing stable windows with stable controls and locating them in memory, as well as simply selecting other windows by keeping their coordinates in memory and responding if you click that screen area.

Later, you can start implementing the update of background regions and windows in a more efficient way, having solved the base screen update services in a clean way.

Along with the other good comments made here, you will need to capture mouse movement and send events to each control.

First you send the mouse (and key) events to the root, allowing it to send these events to each window until one window acknowledges the event. Before acknowledging the event, the window sends the event to each of its controls, waiting for one of these controls to acknowledge the event, sending to the current focus first.

Other events should be global. For example, MOUSE_ENTER and MOUSE_LEAVE. These events are created when the mouse cursor enters and then leaves a control. Functions such as mouse cursor change and button highlight are reasons for these two events.

You should also maintain a "focus" within each window. A control that has the current focus should be maintained across windows so that when a window is brought to the top (activated), the control within the window regains the focus, unless of course you click on another control, which in the process, brings that window to the top.

In my current work, I call each item an object. An object has the same base structure with the type of object added to it so that I may control it. However, all of the base functions can operate on any object using this base object structure.

Here is an example of my current work:
http://www.fysnet.net/temp/vol6_gui.png
from
http://www.fysnet.net/osdesign_book_series.htm

Hi,

codyd51 wrote:Each refresh, starting from the screen's root window, we traverse the entire hierarchy and draw from the bottom up.

This means that if there's 20 windows that overlap, you write to the same area of the buffer 20 times. For the simple case (flat rectangles parallel with screen) it's easy to avoid this by drawing from top to bottom.

Imagine you have an "updateRectangle()" that draws a source rectangle (a window) in a destination rectangle in the buffer. Initially the source rectangle is the top window and the destination rectangle is the entire screen. Use the edges of the source rectangle to split the destination rectangle into (a maximum of) 5 smaller rectangles: center, top, bottom, left and right. Copy the source rectangle into the center sub-rectangle.

For the top, bottom, left and right sub-rectangles (if they exist); use recursion (and the next window in Z order) to update them. If there isn't any more windows; use the desktop/background image as the source rectangle.

In this way, you only ever write to each pixel in the buffer once. Of course this method can't handle "less simple" cases (any transparency, and any windows that aren't rectangular). However, if some windows are opaque and some are transparent it's easy enough to modify this to handle transparency (if the source rectangle is transparent, use recursion to update the entire rectangle first, then draw the center sub-rectangle after).

Next; with one buffer for each window there's a synchronisation problem - you can be refreshing the screen while an application is in the middle of updating its window, and this can cause ugly "tearing" effects. To avoid that you need 2 buffers for each window - a "current buffer" that the application can't touch (that's displayed if/when you refresh the screen), and a "working buffer" that the application draws into. When the application is finished drawing something in the "working buffer", it tells you to replace the "current buffer" with the "working buffer" (and that's when you set the "needs refresh" flag for the application's "current buffer").

Next; limit the number of times you update the screen. For example; if the top window tells you to refresh the screen but the screen has been refreshed in the last 1/120th of a second, set a time delay for "1/120th of a second since screen refreshed last" and refresh the screen when the time delay expires. This means that if the top window is trying to refresh the screen 12345 times per second you only update the screen (a maximum of) 120 times per second. Windows that are in the background are less important; so for the second from top window use "1/60th of a second" for the time delay, for the third from top window use "1/30th of a second" for the time delay, and for anything further in the background use "1/15th of a second" as the time delay. Because the "further in the background" windows are likely to be obscured, and because the user is less likely to care about them, the user probably won't notice this (and won't mind if they do notice). Because the monitor can only display (e.g.) 60 frame per second this can avoid a large amount of pointless refreshes.


Cheers,

Brendan

Brendan wrote:Imagine you have an "updateRectangle()" that draws a source rectangle (a window) in a destination rectangle in the buffer. Initially the source rectangle is the top window and the destination rectangle is the entire screen. Use the edges of the source rectangle to split the destination rectangle into (a maximum of) 5 smaller rectangles: center, top, bottom, left and right. Copy the source rectangle into the center sub-rectangle.

For the top, bottom, left and right sub-rectangles (if they exist); use recursion (and the next window in Z order) to update them. If there isn't any more windows; use the desktop/background image as the source rectangle.

That sounds quite efficient. I was thinking of maintaining a bitmap of which areas had already been drawn, filling it in with the outline of each window as it is drawn, and skipping any windows which are entirely covered by a "drawn" area. This has the advantage of being able to handle non-rectangular windows quite well.

You'll probably also need to buffer the contents of each window somewhere else, so that you can use this as the source image when preparing the frame buffer. It isn't always going to be possible to request that a window or a control inside a window draws only part of itself, so you need some way for the window to draw itself entirely and then copy just the required part into the frame buffer (or the buffer in which you are preparing the frame buffer, most likely).