2008-05-06

Splitting Rectangles vs BSP Trees

Back when I started work on Woopsi in September, one of the first problems I had to solve was how to work out which parts of which gadgets were visible. That’s the secret to a good windowing system - make sure you only draw the parts of each gadget that are actually visible, and don’t waste CPU time drawing things that will get overdrawn later.

My solution to this was to write an algorithm that would take two rectangular surfaces, work out which parts of the first rectangle were overlapped by parts of the second, and finally spit out a pair of vectors that contained an array of the overlapped rectangles and the visible rectangles. Based on the timestamps of the blog posts in question, it took about three days to go from basic idea (which took a week or so to develop) to implementation, and the code has been tweaked considerably since then.

I bring this up because I was thinking of optimising the routine last night. My only real idea for this up until now was somehow to merge adjacent rectangles back together if they share common dimensions along one edge. The routine to do this would probably be just as complicated as the routine to split them up in the first place, so I haven’t bothered really looking into it.

Anyway, I came up with the idea that perhaps the merging routine could be simplified if I worked in a tree-like structure instead of just flat vectors. Every time a gadget is split up, the original rectangle is kept in memory (instead of being discarded) and the split up components are set as children of the original rectangle. Something of a revelation later and I realise that I finally understand BSP trees. Not only that, I’ve just re-invented them.

The splitting algorithm currently works like this. Imagine we want a screen to redraw itself. It creates two vectors, one that will store overlapped (and thus invisible) regions, and one that will store non-overlapped (visible) regions. It inserts its own rectangular region into the non-overlapped vector and sends both to its top-most child.

The top-most child works out where the “split points” of each rectangle in the non-overlapped vector are based on its own boundaries. In this example, in which we’re splitting the screen’s rectangle, the split points are illustrated by the red markers. The algorithm has to examine each dimension separately.

Woopsi Splitting Rects 1

Once it has this information, the algorithm has enough data to split up the original rectangle. This will give us this situation:

Woopsi Splitting Step 2

Splitting continues until we run out of child gadgets to split against or the non-overlapped vector is empty. We eventually get to this situation:

Woopsi Splitting Step 3

This shows the final stage, in which everything has been split. (Actually, I think it would be considerably more complicated than this, but you get the idea.) This works, but it’s not the best way to do it, which brings us back to BSP trees. A BSP tree, or a “binary space partitioning tree”, is a data structure that models a complex polygon as a set of primitives by recursively splitting it into increasingly simpler shapes. In the world of Woopsi, what that means is instead of trying to explode rectangles into 9 smaller rectangles in one go, we divide them in two, then in two again, and in two again, storing each new rectangle as a child of the original rectangle, until we produce a more manageable shape.

Here’s how the split routine looks if we model it with a BSP tree instead. First of all, we work out where to split the screen’s rectangle by looking at the top-most child. Same idea as before, really, but we just divide the rectangle into two at the left edge of the child window:

Woopsi BSP Tree Step 1

These two new rectangles become the left and right children of the original rectangle, which gives us a tiny binary tree. We recurse into the left-hand child trying to split again, working our way down the child list until we hit something that overlaps this rectangle. Eventually we reach this:

Woopsi BSP Tree Step 2

At this point there are no more children to recurse through, so we exit the recursion stack and start on the right-hand child of the original rectangle:

Woopsi BSP Tree Step 3

There are more steps after this, but you can see where I’m going. The data structure we’ve created looks like this:

Woopsi BSP Tree Model

The advantage of this approach is huge:

  • We split less, so we don’t need to merge rectangles as it’s already done for us
  • The algorithm is considerably simpler than the original
  • It uses less memory
  • In theory, it’s faster
  • Gadgets no longer need to maintain vectors of cached visible rectangles
  • The layout of the display can be managed centrally
  • Gadget erasing code should be less cumbersome
  • Since splits are done in a strict top-down method, clipping to parents is automatically thrown in for free (this is currently bolted on)

I’ve got an implementation of the BSP drawing system done. It’s just over 200 lines of code for a tidy stand-alone class, compared with over 200 lines of code just for the “splitRectangles()” function embedded in the Gadget class in the current system. The only problem I’ve got is that the current system is so entrenched in the code it’s going to be a real pain to extract it. On the positive side, none of the current code should be affected, since this stuff is all hidden away deep in Woopsi’s guts.

I’m planning to get a very stripped-down version of Woopsi running in SDL, make the changes, get it running on the DS and then see if swapping to BSP trees really does make any difference.

Comments

Jeff on 2008-05-07 at 00:09 said:

A well presented explanation. One question in my mind, I had this feeling (and its only that, I don’t really know BSP enough) was that the splitting tended to alternate horizontal, vertical, whereas you appear to have continued to do vertical slicing till nothing remained.

It seems like their might be some benefit in weighting the two sides, rather than always choosing the left as your start point. If someone has moved a window to the left, its probably to make the things on the right visible, which implies more splitting will be required on that side.

For example, if you had sliced horizontally to start with, the screen title bar would have remained a single rectangle for a lot longer. In general terms and catering specifically to the proportions of the DS screen, it probably makes more sense to begin splitting horizontally.

Or something like that. Anyway, I look forward to seeing it in action…

ant on 2008-05-07 at 07:46 said:

I’d need to read up on the “official” way to use BSP trees to be certain of the exact details. The algorithm I’m currently using is very simple so there’s probably room for optimisation if I can prove to myself that it will work.

The routine tries to split vertically, then tries to split horizontally (think of it as an in-order tree walking routine), but there might be some benefit in making it choose which to do first based on the screen layout. Weighing up the screen and choosing to split one side instead of another probably wouldn’t help, as both sides will eventually be split anyway.

Jeff on 2008-05-07 at 08:50 said:

I think if you did horizontal first, then vertical, you’d save the screen titles, window titles, etc since you have pretty much always several sub-gadgets at the top of each screen/window which share a common bottom y value.

Of course, gadgets with vertical scroll bars would be a pain - perhaps you want to ask the gadget which it prefers as a hint.

ant on 2008-05-07 at 13:41 said:

Asking the gadgets would require people who make their own gadgets to have more knowledge about the clipping/drawing system than they really should need. I wonder if it’s possible just to favour horizontal splits for gadgets wider than they are tall, and vertical splits for gadgets that are taller than they are wide? I think that would cater for the majority of situations without any difficult calculations.

Jeff on 2008-05-07 at 23:50 said:

I’m not so sure that it matters. If there’s a virtual method that answers ‘vertical first’ for Screen and Window, and ‘horizontal first’ for Gadget, then you’d get better performance surely? And those that know can tune performance even more if they want to put in the effort, but don’t have to if they don’t want to.

I think the distinction I’m drawing is between Screen/Window which know that they contain a horizontal slice at the top (and perhaps List which knows it has a vertical slice at the scrollbar). Sure, within a Screen are a number of randomly placed Windows which might better slice vertical than horizontal (though its going to depend on human placement and/or aesthetics).

Basing is on aspect ratio (width/height) was something else I was thinking about, and that might be a good default position for Gadget to take. Screen would automatically work as well, though thats by accident - the presence of the title bar is not a function of the aspect ration.

ant.simianzombie.com » Blog Archive » Keyboard Bug on 2008-10-12 at 19:52 said:

[…] do still have the BSP tree code I mentioned a while back. I’d like to get that plugged in at some […]

ant.simianzombie.com » Woopsi Optimisations and Fixes on 2009-10-07 at 12:12 said:

[...] is to try and either optimise it (by making the rect splitting smarter) or replace it with the BSP tree code I came up with – oops – a year ago. I’ve fixed a raft of bugs in that code, but [...]

ant.simianzombie.com » Redrawing with Damaged Rects on 2010-09-08 at 13:57 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 […]