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.
Once it has this information, the algorithm has enough data to split up the original rectangle. This will give us this situation:
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:
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:
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:
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:
There are more steps after this, but you can see where I’m going. The data structure we’ve created looks like this:
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.