2010-09-08

Redrawing with Damaged Rects

The Problem: Bad APIs and Suboptimal Redrawing

The existing gadget redrawing system in Woopsi sucks. It’s inefficient and makes the API ugly.

For example, here is a completely bare-bones startup method that will get Woopsi into a usable (but empty) state:

void SomeApp::startup() {
    enableDrawing();
    redraw();
}

The two function calls in the startup() method ensure that the Woopsi instance is visible. When an instance of the Woopsi class is created, its redraw system is disabled. This allows the initial set of gadgets to be added without them appearing on-screen one at a time. Once the initial state has been set up, drawing can be enabled, and the initial state can be drawn.

You might notice that these two lines of code aren’t required in any other UI framework you’ve used. Neither winforms, AWT, Swing, GTK, KDE or anything else requires that you manually enable redrawing and redraw the display once you’ve finished adding UI components to your application.

The reason for this is the way that Woopsi handles redrawing. In Woopsi, each gadget is responsible for redrawing itself. All gadgets know which portions of themselves are visible, and they also know when their appearance has been changed. When a gadget is created it knows that it must redraw itself, and does so. Likewise, when a gadget moves, or is resized, or is clicked, it will redraw itself. So, when we add gadgets to Woopsi, they will draw themselves to the screen one at a time instead of the entire screen being drawn in a single operation. This piecemeal redraw looks odd and wastes CPU time, so drawing is initially disabled. Users must re-enable drawing themselves when the UI is ready.

The problem of wasted CPU cycles is more onerous in other situations. Consider the TextBox gadget. This redraws itself every time its text is changed. If we run the following code, the textbox will redraw four times:

textbox->appendText('t');
textbox->appendText('e');
textbox->appendText('x');
textbox->appendText('t');

The textbox redraws every time a character is added to its text. If we were to add one hundred characters, the textbox would redraw one hundred times. Now suppose that the textbox fills the entire bottom DS screen. Changing the text in the textbox changes roughly 8x8, or 64 pixels, per update. That means we’ve changed 6,400 pixels. However, we’ve redrawn every pixel on the screen one hundred times. We’ve redrawn 256x192, or 49,152 pixels, per update. We’ve redrawn 4,195,200 pixels when we only needed to redraw at most 6,400. 99.87% of the redrawing was just wasted CPU time.

Woopsi offers a workaround in the form of the enableDrawing() and disableDrawing() methods of the Gadget class:

textbox->disableDrawing();
textbox->appendText('t');
textbox->appendText('e');
textbox->appendText('x');
textbox->enableDrawing();
textbox->appendText('t');

However, this is a nasty hack. It requires that the developer knows enough about Woopsi’s internals to be able to predict when it will redraw and when it is safe to prevent the automated redraws from running. In the above code, it isn’t particularly obvious why drawing is re-enabled before the last character is added (so that the final append triggers a redraw) and it isn’t something that developers should need to care about.

The Competition: What Everyone Else Does

In the majority of other UI kits, redrawing is handled by tracking damaged rectangles. These are areas of the screen that have been modified and therefore need redrawing. In these systems, instead of our textbox redrawing itself, it would notify an object responsible for tracking these damaged rectangles that its visible areas had changed. The tracking object would store any of those rectangles that it hadn’t been previously notified of in a list. At frequent intervals (every VBL, say) the tracker would order the gadget hierarchy to redraw all of the damaged rectangles in its list. Using this system, the textbox would only be drawn once no matter how many times it was changed.

Justifying Woopsi’s Behaviour: DMA and Bad Code

Woopsi doesn’t use a damaged rectangle system for two reasons. Firstly, it makes extensive use of the DS’ DMA hardware to copy areas of the framebuffer around. It is especially important to the scrolling system that everything on-screen is up-to-date. If redrawing was postponed until a later time it is likely that the scrolling system would be working with out-of-date 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 horribly complicated because, well, the code itself is horrible.

Potential Benefits of Changing Woopsi

But what if Woopsi could use the damaged rectangle system for redrawing? How would that affect the API and the framework? It would instantly obsolete about a dozen of the most complicated methods, and it would make a bare-bones Woopsi setup function look like this:

void SomeApp::startup() { }

Adding one hundred characters to a textbox would require a single redraw without any extra developer effort. Even actions such as moving gadgets would be more efficient - they are currently entirely erased from one location and redrawn at another, even if they move by just one pixel. A damaged rectangle system would reduce the number of rendered pixels in such a situation by almost 50% because there wouldn’t be an erasing step.

Fixing the Rectangle Splitter

The existing code used to split up rectangles into intersecting and non-intersecting sub-rectangles is 207 lines long. At times, it has nested if statements and for loops nearly a dozen deep.

(I’d originally intended to add the code in here, except my current WordPress theme breaks the “more” tag, making the post far too long for the front page of the blog. Additionally, trying to force the code into a smaller div by adding a “style” attribute breaks the syntax highlighter and causes angle brackets to be interpreted as HTML tags. I really need to get a new theme that’s less cluttered and easier to read, but nothing I’ve found so far fits.)

Anything nested that deeply is in dire need of refactoring. I looked at it the other day and realised that the entire algorithm was vastly overengineered. A far more efficient approach presented itself to me and I set about rewriting it. The replacement method is 74 lines long and contains just 4 if statements with no nesting at all.

The new method is a massive improvement over the original code. It is considerably smaller and easier to understand, it is faster and best of all, it produces the optimal result each time.

In all situations where there is an intersection, the original code produced (2n-1) rectangles, where n is the optimum number of rectangles. The larger the number of rectangles produced by this method, the more clipping the renderer will have to do later, so having a function that always produces the optimal result is a very good thing.

Switching to Damaged Rectangles

With the rectangle splitting routine rewritten and moved into the Rect class, where it should have been from the start, switching to a damaged rectangle-based rendering system starts to become feasible. The last problem to solve is the issue of scrolling. The scroll routines must be working with the latest bitmap data, which means rendering cannot be deferred.

I don’t know how much thought I’ve put into into solving this during the course of Woopsi’s development, but I’d never managed to hit on a solution until a couple of days ago. The answer is painfully obvious once you know it: make any functions that use the scrolling abilities of Woopsi flush any pending damaged rectangle redraws before they start. That way, the screen will be up-to-date before any scrolling is done.

Simple, obvious.

The upshot of all this is that Woopsi’s rendering engine is now based on damaged rectangles. Instead of the TextBox calling redraw() when its text changes, it now calls markRectsDirty(). It sends its list of visible rectangles to a new DisplayManager class (I might change the name of that class at some point), which works out which parts of the damaged rectangles it knows about (and discards them) and which are new (and remembers them). Once every VBL the DisplayManager redraws the display.

Redrawing is achieved by splitting the damaged rectangles into intersections with the gadgets. The DisplayManager performs a depth-first walk of the gadget tree in order to redraw in front-to-back order. Any rectangles that are redrawn are removed from the damaged rects list. Once that list is empty, the redraw method ends.

What has changed?

So, what has changed? There’s no need to call enableDrawing() or redraw() in the startup() method, for a start. In fact, both enableDrawing() and disableDrawing() no longer exist. The redraw() method has gone too, as well as the following:

  • Gadget::erase()
  • Gadget::eraseGadget()
  • Gadget::redrawDirty()
  • Gadget::drawChildren()
  • Gadget::redrawDirtyChildren()
  • Woopsi::eraseRect()

As previously mentioned, these were some of the cludgiest, most unpleasant functions in the system. I’m glad to have chucked them out.

There’s always a Catch

Unfortunately, the hack that the DimmedScreen class exploited no longer works. That class has had to be deleted.