I said that splitting up the rectangles of overlapping windows would be complicated, and I was right. I came up with a fantastic solution to the problem last night and added a post about it here, but I realised afterwards that all I was doing was a pointless two-dimensional binary search, and at the end all I got was information I already possessed - the height, width and co-ordinates of the two original rectangles.
Looking at it as a problem with two separate dimensions gave me the solution, though. It’s actually a really simple problem that I was over-analysing.
First of all, let’s go over the problem again. We have two rectangles, A and B. A overlaps rectangle B. We’re trying to determine which areas of A overlap B, so that we can redraw just that region (this algorithm is used to wipe windows from the display - A is being erased from the screen). Ultimately, then, we’re trying to subtract the overlap of B from A. If we succeed in removing the overlapped area, we’d be left with an irregular polygon, which is of no use to us - rectangles are far easier to deal with. So, we need to divide A up into the smallest number of sub-rectangles that we can - this will allow us to just discard the non-overlapping regions (which will be all but one of the sub-rectangles).
Thinking in two separate dimensions is the key to the problem. Here’s a picture of the situation:
Rectangle A is the “Erased gadget”. Rectangle B is the “Current gadget”. Across the top and on the left are the two-dimensional representations of where the rectangles start and end. We can obtain this information from the two windows.
Starting from the left side of the “Erased Gadget”, we identify point 1 (the left-hand edge of the “Erased Gadget”), then point 2 (which will either be the start of the current gadget or, as in this case, the end of the current gadget), then point 3 (either the end of the current gadget or the end of the erased gadget). We may have a point 4 if the current Gadget is entirely covered by the erased gadget. We know the X location of each point, and thus we know the distances between them. We can also identify which pair of points contains the overlap.
We perform the same routine on the Y axis. This will give us a set of points that describes every rectangle on the display. In the image shown below, we have a rectangle from X1, Y1 to X2, Y2 (this is the rectangle immediately above the overlap). We have a rectangle from X2, Y1 to X3, Y2, a rectangle from X1, Y2 to X2, Y3 that contains the overlap, and so on. This gives us 6 rectangles; not the best solution (the optimum is 4 rectangles), but we’ve hardly done any processing and we’ve managed to chop the rectangle up. If we wanted, we could merge some of the rectangles together (by checking if they have the same vertical or horizontal properties, and that they are contiguous), but at the moment it seems that the current system is fast enough. To tie this into the rest of the algorithm described a couple of posts ago, we re-draw the overlapped region of the current gadget, remove the erased gadget’s rectangle from the rectangle vector, feed the new rectangles into it, and continue passing the vector down through the gadget hierarchy. Once we’re out of rectangles to split we know we’ve successfully redrawn all of the invalid parts of the display and thus erased the gadget we wanted to remove.
All of this is now integrated into Woopsi, and for the simple demos in the system at the moment it is pretty damned quick. I don’t know how it’ll cope with complicated displays, but I’m sure there’s plenty of scope for optimisation in the future. Here’s a list of things that have changed:
- Fixed width/height inaccuracies (I wasn’t quite converting from (x1,y1) (x2,y2) to (x,y) (width,height) properly)
- Tidied up border drawing again (related to the width/height thing)
- Added intelligent gadget erasing
- Screen/window borders are now gadgets (so they automatically get redrawn as necessary when they become visible)
- Almost all gadgets now have a draw function that clips to a supplied rectangle’s dimensions
- Swapped the dull black rectangle in the SuperBitmap demo for a picture of many Marios (shows off the concept a bit better)
- The Pong demo now uses the SuperBitmap class as its canvas
The last change reflects a decision I’ve made regarding drawing to windows. I’ve decided that it won’t be possible (using the supplied classes and functions) to draw directly to a window; instead, programmers will add a SuperBitmap gadget to the window (just a case of calling window.addSuperBitmap(x, y, width, height, bitmapWidth, bitmapHeight) and draw to that. They can then call the draw() command on the SuperBitmap object to draw the entire canvas to the window. There are several advantages to this:
- Unlike the standard window canvas, the contents of a SuperBitmap gadget is stored in RAM and will be preserved even if the window is not visible - the standard canvas is wiped when the window is redrawn
- Once the new drawing code is in place (see below), the SuperBitmap will automatically use the optimal drawing routines; if I tried to support drawing to a window, each drawing function would need to implement its own optimised, clipped routine. Far too much hard work, and probably really slow
- Writing drawing functions for the SuperBitmap gadget is easier than writing them for windows, as I’m just writing straight to memory instead of converting from screen space to window space and back again.
Here’s a couple of things I need to remember to do:
- The TextViewer gadget’s redraw routine doesn’t have clipping implemented yet
- The TextWriter class’ clipping routines could be more intelligent
- I need to write a gadget drawing system that will only draw the visible portions of gadgets (I think I described the routine in my last post) - I can probably adapt the erasing code to do this. O nce this is in place, the Pong demo won’t overlap other windows any more.
Here’s a link to another demo: