{ End Bracket }
Dirty Rectangles.
Jon Schwartz
Our Kid’s Programming Language (KPL), a programming environment designed for kids, is a Windows® Forms-based application built in C# atop the Microsoft® .NET Framework. To capture and hold attention, KPL emphasizes graphics and game programming, including drawing, use of 2D graphical sprites, and simple 3D graphical programming. Everything KPL offers is a simplifying abstraction built atop the .NET Framework or DirectX®.
Frames Per Second is the usual metric for graphics performance: the number of screen refreshes that happen each second. The human eye and brain can’t distinguish more than 30 or so frames in a second, so this is a common target for graphics performance. At that speed or higher, movement and animation will appear smooth; at less than that speed, we may perceive choppiness.
KPL’s graphics performance was acceptable in its first iteration, which was "pure" .NET, but there certainly was room for improvement. Experimentation and optimization led us to an approach which provides well-performing graphics from nearly pure managed code. The keys to this are optimizing the video display step, using a dirty rectangle scheme, and leveraging the performance of BitBlt. BitBlt is a classic native code method for high-performance manipulation of video memory. Nearly everything else in KPL’s graphics subsystem is .NET Framework 2.0 managed code.
A background buffer is used for the base layer, a bitmap on which the fixed elements of the graphical display are stamped, including any background image or background color. A working bitmap buffer is used at refresh time to prepare the image which will be sent to the video device. A sprites collection is used for managing, moving, and displaying graphical objects. Finally, a dirty rectangle collection is key for optimizing display performance.
What is a dirty rectangle? Consider the typical user interface, and the very quick speed at which a computer refreshes that interface. Even when we are interacting with the app with a mouse or keystroke, between one refresh and the next, typically only a small portion of the video display has changed. Optimum performance is reached if we only redraw those regions of the video display which actually have changed. Dirty rectangles define those regions.
The key to our optimization is how we handle each screen refresh, which is an algorithm of three high-level steps. First, our dirty rectangle collection is iterated, and BitBlt is used to copy those rectangles from the background buffer to the working buffer. Next, our sprites collection (z-order sorted) is iterated and the intersection of any sprite with a dirty rectangle is drawn onto the working buffer. Finally, our dirty rectangle collection is iterated one final time, and BitBlt copies those rectangles from our working display buffer directly to the video device memory.
There are various examples and algorithms available for managing a dirty rectangles collection. Algorithmic idealists might use a technique in which two overlapping dirty rectangles are subdivided into the minimal set of three distinct rectangles such that none of the resulting rectangles overlap each other (see Figure 1). We implemented this based on an IRectangleManager interface, which allowed us to easily test the performance of different rectangle management schemes by implementing custom interfaces. We found that our own best performance results from a simple union of overlapping rectangles (see Figure 2). Different applications will have different performance requirements and results based on their own manipulation of the video display.
Figure 2
Figure 1** **
While our approach adds a layer atop .NET-based code, it does provide KPL’s best graphics performance thanks primarily to the use of the highly efficient BitBlt in each place where we copy blocks of video display memory. Using a native API isn’t for beginners, certainly, but on the other hand, Managed DirectX itself is a wrapper around many native API calls.
It is also possible to combine BitBlt performance with uses of existing Control.Invalidate overloads which allow specification of invalidation regions. The control’s OnPaint handler will then receive only the specific region to be redrawn. This is one of the iterations we implemented on the path to our current approach. Forcing a Control.Refresh can make this approach more deterministic, but ultimately didn’t offer as much control as we wanted.
Our final approach also offers better performance for us—but the improvement is small compared to the improvement over our initial unoptimized implementation. You can see the advantages of approaching optimization in an iterative and modular fashion: iteration continues until the desired performance is achieved, within the actual requirements and architecture and usage of the application being implemented.
Jon Schwartz is a founder of consulting and software development company Morrison Schwartz. He can be reached at jon.schwartz@morrisonschwartz.com. His company’s latest product, Kid’s Programming Language, is available on the Web as a freeware download.