OSDev.org

The method I am using to draw windows currently is unacceptably slow.

What I do is, for each point(x,y), search the window tree and find out which windows contain the pixel, and decide which window is at the front and display that pixel.

Now, I am thinking something like the Painter Algorithm used in Computer Graphics. That is, I'll keep track of the depth of each window, and the redraw function will sort the window by its depth and draw each of them in order.

Any suggestions or alternative approach?
Thanks!

It sounds good. I'd suggest to use linked lists, one pointer pair for parent/child relations, and one for depth.

What can make it faster, you shouldn't walk the tree for every pixel, instead calculate intersections of windows first, then blit a box at once, starting from the deepest window.

Yeah i m drawing the deepest window to the shallowest now. It speeds up by 100 times!

However, if I close or move some window, all other windows would have to be redrawn. It looks like refreshing in Windows XP/7.
Is there any way to fix this?

------------------------------------------------------------------------------------------------------------
Edit:
I come up with a possible solution.
Maybe, instead of writing to the video memory directly.
I can have another temporary buffer that stores the pixels of all the windows, and when a window close, this temporary is the one that will get updated.
Then, I'll compare the video memory and this temporary buffer and only redraw the pixels in video memory that are different from those in the temp buffer.

Hi,
I advise against reading video memory, because it may be slow.Instead, create a cache of it. Let's say you want to write a big buffer in the video, quickly compare the buffer to the cache ( using SSE ).
For parts which differs, copy them to the cache first ( using SSE ) and copy them to the video memory ( using rep movsb I guess ?)

Instead of drawing pixels more than once, I'd divide the screen in areas , and for each area, maintain a list of visible objects, sorted by depth . It is what you do, except you have only one area ( the whole screen)

Have fun!

What you need is called double- or even triplebuffering.

Thanks for your advice! very good ideas!

Thanks! it sounds like what i m doing now, i'll look it up

ilixi project has fairly readable code regarding this kind of stuff...

http://www.ilixi.org/

look in ilixi/compositor

The window management and additional code for how to deal with events of subwindows are in that directory

Thanks!

I've implemented the double buffering and draw windows sorted by depth. Window creation and close is reasonably fast. Moving a window is still very slow.
I am going to implement the technique you mentioned above(divide screen)

how does this look ?



I think this kind of make sure no CPU time is wasted on drawing useless pixels right?
More suggestions?

You don't have to continuously redraw the entire window while it's being dragged across the screen. Just draw and move a hollow rectangle of the same shape as the window. When moving is done (e.g. nothing's moved for about a second), do the proper redraw.

I agree, that is the way Window does it (when low visuals mode is enabled).
You can also use that method for scaling because you don't need to draw the entire window per mouse event.

Sounds good , but the first one gives better visual aid i guess.

At Symbian/UIQ we used to call a bunch of rectangles a 'region'. We had utility functions for subtracting and intersecting rectangles and regions.

Each window had an opaque and a semi-transparent region (either of which could be empty).

To repaint the screen, we started with a region that represented the dirty area.

We then visited the windows front to back. As we passed windows with semi-transparent regions we put them on a 'draw later' stack. As we passed windows with opaque regions we computed the intersection of that opaque region with the dirty region. We then drew this overlap. We then went in back-to-front order through the semi-transparent windows on the 'draw later stack' drawing them if their semi-transparent regions intersected the overlap, subtracting it as we went. Finally we subtracted the overlap from the dirty region before continuing the window walk deeper if there were outstanding dirty region left.

In the old days we used to wake up every window's app and tell it to repaint as we went, and this actually worked well enough even on low-end phones because most phone-apps are full-screen anyway. However, as scenes got much more complicated and semi-transparency arrived we started retaining the draw-commands that each window generated so we could replay them inside the window-server without waking up the client. We had simple limits on how many draw commands we retained and would wake up the client app if completely necessary.

We also supported bitmapped windows, both those drawn by the client directly and those we 'backed' as another way of 'retaining' the drawing (particularly for "transition effects").

It's probably about time I post in this thread... I worked on Compiz many years ago, spent some time at Apple working on the window server in OS X, and have written two different compositing window managers of my own. Hopefully this isn't too much a rambling mess.

I'll spare you the usual history-of-window-drawing explanation and jump straight to "how we do it now". Every modern windowing system employs a compositor - be it Windows's DWM, OS X's WindowServer, Wayland, iOS's WindowServer (which is based on the OS X one), or Android's SurfaceFlinger. It seems you get the general idea of compositing: Store a representation of the window contents within the server so you don't need to ask the clients to redraw. There are many ways to do this, but all of these examples just store bitmaps, usually in GPU memory. Obviously, GPU memory is a tall order for a hobby OS, so you'll likely just want to use plain old RAM. OS X's WindowServer used to work this way in its early days - it actually took several years for it to be moved over to the GPU. You can also store draw calls and re-run them, but that could be more expensive in runtime than it's worth in potential space savings (and RAM is cheap). These "surface-based" systems all present a canvas/surface/texture/bitmap/whatever-term-you-want-to-use to the client, the client does whatever it wants to render into it, informs the server it is ready, usually there's some copying so the client can go back to drawing again (though not always, sometimes the server and client will share the same surface; this can lead to tearing and a few other artifacts), and the server will redraw affected areas of the screen. There's a lot of things compositing is really good with, like rendering semi-transparent windows over other windows that are constantly changing. Since these compositors employ GPUs, they're very similar to video game rendering engines and you can think of windows as big rectangular textured meshes rendered back to front to ensure that semi-transparency stacks up correctly. But video games render the whole visible scene on each frame, and that's obviously not a good idea for a general UI that's unlikely to be changing much. This is where "dirty" or "damaged" regions come into play. Whenever a window updates its texture, it informs the server of where those updates occurred. This can be a whole window or just a small subset of it (your blinking terminal cursor shouldn't signal the server to update the whole terminal, for example). Dirty regions are summed together, probably with an efficient region merging algorithm (jojo's guide covers this pretty well), and then only those regions are rendered and copied to the framebuffer.

As a practical example, I'll explain how the process works for my own compositor. As I don't particularly care about tearing, I use a single surface for each window, rather than having server and client copies. Surfaces are 32-bit ARGB regions with stride==width, which are allocated by the server and made available to clients through a simple shared memory functionality in my kernel. A port of my compositor to Sortix used normal Unix shared memory. An ideal implementation would use GPU memory, but we don't have any GPU drivers, so that's not likely to happen any time soon. The clients can use whatever they want to draw onto that surface (and most of them just set pixel values manually; some use Cairo, some use software Mesa, a few use SDL), and then send a message to the server to inform it that a region has been updated. Because the client and server share the single surface, the server may render updates made within a window before the client has informed the server of them, so most clients employ client-side double buffering (they render into their own buffer and then copy it to the shared surface) to avoid drawing things that should not be displayed on screen (such as layers behind a button or something). The server itself uses Cairo for all of its rendering. My first implementation of a compositor was written from scratch, and I wanted to simplify and speed up my second iteration by employing an existing rendering library. To perform dirty region clipping, we use Cairo's built-in support for clipping. Because Cairo can clip to arbitrary shapes, it actually has two clip modes and which one gets used depends on the sort of clip regions you provide. We always use pixel-aligned rectangular clips to ensure that we stick to the fast clipping mode (the other mode is the slow one used for those arbitrarily-shaped and semi-transparent clips). From there, we render all of the windows from bottom to top into a temporary buffer. Cairo's rendering backend ensures we're not actually doing anything expensive with the windows that don't fall into the clip region. We then copy, using the same clip regions, from the temporary buffer to the actual framebuffer.