2007-09-25

Splitting Rectangles

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.

Duh.

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:

Splitting Rectangles

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:

Woopsi Demo V0.17

Woopsi 0.17 Screenshot

Comments

Jeff on 2007-09-26 at 00:10 said:

Looks like you are hammering along nicely.

One thing about your picture of rectangles - have you coped with the pathological cases?

a) one rectangle completely inside the other b) two rectangles not overlapping except at a common point. c) two rectangles sharing an edge

The latter tends to confuse most clipping algorithms - as I recall, John Carmack had lots to say on the topic, which started out with “left edges are inclusive, right edges are exclusive” and proceeded into areas I confess to knowing nothing about.

The optimising tip of the day would be to do with determining whether a point lies in a rectangle. If you reduce it to a single dimension (ie, does x fall within these two values (x1,x2), and you are playing with integers, then (x1-x)^(x-x2) has its top bit set if the value is outside the range and clear if inside. Much quicker than (xx2) which requires that you know that x1

ant on 2007-09-26 at 08:47 said:

Yep, the rectangle code handles overlaps at the edges. Trying to track down that particular bug caused me some effort, but fixing it (once I worked out what was going on) was easy. As I deal with the two dimensions separately when working out where the rectangles are, getting edge overlaps working gives me single point overlap detection for free.

Your code for checking if a point lies between two others looks good - I’ll have to work that in at some stage! How do you come up with all of these crazy shortcuts?

Jeff on 2007-09-26 at 10:45 said:

That particular one came out of a discussion in the office when we were discussing how you tell if 2,3 or more dimensional vectors were “to the left of one another” - trying to do a polygon fill or some such.

Anyway, whilst the math shouldn’t hold when you collapse it to one dimension (according to the purists, you can’t have a cross-product in a one-dimensional matrix), it produces the desired result. In the real world, of course, you can’t just check the top bit, you need to check if the result is

ant.simianzombie.com » Redrawing with Damaged Rects on 2010-09-08 at 13:52 said:

[…] data. The second reason is the complexity of the rectangle splitting algorithm discussed here and here. Trying to get the code that splits up rectangles to do anything slightly different would be […]