Journal: Dr. Dobb's Journal Feb 1993 v18 n2 p127(6) ------------------------------------------------------------------------- Title: More dirty (dirtier?) rectangles. (animation programming) (Column) (Graphics Programming) (Tutorial) Author: Abrash, Michael Attached: Program: GP-FEB93.ASC Source code listing. Abstract: Dirty-rectangle animation is a method of animation programming that results in good visual quality without the video hardware and memory necessary for page flipping. The dirty-rectangle method can add further advantages with the use of low-level drawing routines written in assembly language to increase performance. Masking an object before drawing it allows pixels to penetrate only through holes in the mask. Masked images, which are sometimes called sprites, make animation more realistic. Drawing masked images can be slow, but speed can be increased with the use of assembly language. Another good animation programming technique is internal animation, where the images themselves instead of their positions are changed. Other recommended techniques are discussed. ------------------------------------------------------------------------- Full Text: Programming is, by and large, a linear process. One statement or instruction follows another, in predictable sequences, with tiny building blocks strung together to make a custom state machine. As programmers, we grow adept at this sort of idealized linear thinking, which is, of course, A Good Thing. Still, it's important to keep in mind there's a large chunk of the human mind that doesn't work in a linear fashion. I've written elsewhere about the virtues of nonlinear/right-brian/lateral/what-have-you thinking in solving tough programming problems, such as debugging or optimization, but it bears repeating. The mind can be an awesome pattern-matching and extrapolation tool, if you let it. For example, the other day I was grinding my way through a particularly difficult bit of debugging. The code had been written by someone else, and, to my mind, there's nothing worse than debugging someone eles's code; there's always the nasty feeling that you don't quite know what's going on. The overall operation of this code wouldn't come clear in my head, no matter how long I started at it, leaving me with a rising sense of frustration and a determination not to quite until I got this bug. In the midst of this, a coworker poked his head through the door and told me he had somthing I had to listen to. Reluctantly, I went to his office, whereupon he played a tape of what is surely one of the most bizarre 911 calls in history. No doubt some of you have heard this tape, which I will briefly described as involving a deer destroying the interior of a car and bitting a man in the neck. Perhaps you found it funny, perhaps not--but as for me, it hit me exactly right. I started laughing helplessly, tears rolling down my face. When I went back to work--presto!--the pieces of the debugging puzzle had come together in my head, and the work went quickly and easily. Obviously, my mind needed a break from linear, left-brain, push-it-out thinking, so it could do the sort of integrating work it does so well--but that it's rarely willing to do under conscious control. It was exactly this sort of thinking I had in mind when I titled my book Zen of Assembly Language. (Although I must admit that few people seem to have gotten the connection, and I've had to field a lot of questions about whether I'm a Zen disciple. I'm not--more of a Dave Barry disciple. If you don't know who Dave Barry is, you should; he's good for your right brain.) Give your mind a break once in a while, and I'll bet you'll find you're more productive. We're strange thinking machines, but we're the best ones yet invented, and it's worth learning how to tap our full potential. And with that, it's back to dirty-rectangle animation. Dirty-rectangle Animation, Continued Last month, we got our feet wet with dirty-rectangle animation. This technique is an alternative to page flipping that's capable of producing animation of very high visual quality, without any help at all from video hardware, and without the need for any extra, nondisplayed video memory. This makes dirty-rectangle animation more widely usable than page flipping, because many adapters don't support page flipping. Dirty-rectangle animation also tends to be simpler to implement than page flipping, because there's only one bitmap to keep track of. A final advantage of dirty-rectangle animation is that it's potentially somewhat faster than page flipping, because display-memory accesses can theoretically be reduced to exactly one access for each pixel that changes from one frame to the next. The speed advantage of dirty-rectangle animation was entirely theoretical last month, because the implementation was completely in C, and because no attempt was made to minimize display-memory accesses. The visual quality of last month's animation was also less than ideal, for reasons we'll explore shortly. The code in Listings One (page 142) and Two (page 144) addresses the shortcomings of last month's code. Listing Two implements the low-level drawing routines in assembly language, which boosts performance a good deal. For maximum performance, it would be worthwhile to convert mor of Listing One into assembler, so a call isn't required for each animated image, and overall performance could be improved by streamlining the C code, but Listing Two goes a long way toward boosting animation speed. This program now supports snappy animation of 15 images (as opposed to 10 last month), and the images are two pixels wider this month. That level of performance is all the more impressive considering that this month I've converted the code from using rectangular images to using masked images. Masked Images Masked images are rendered by drawing an object's pixels through a mask; pixels are actually drawn only where the mask specifies that drawing is allowed. This makes it possible to draw nonrectangular objects that don't improperly interfere with each other when they overlap. Masked images also make it possible to have transparent areas (windows) within objects. Masked images produce far more realistic animation than do rectangular images, and therefore are more desirable. Unfortunately, masked images are also considerably slower to draw; however, a good assembly language implementation can go a long way toward making masked images draw rapidly enough, as illustrated by this month's code. (Masked images are also known as "sprites;" some video hardware supports sprites directly, but on the IBM PC it's necessary to handle sprites in software.) Masked images make it possible to render scenes so a given image convincingly appears to be in front of or behind other images; that is, so images are displayed in z-order (by distance). By consistently drawing images that are supposed to be farther away before drawing nearer images, the nearer images will appear in front of the other images, and because masked images draw only precisely the correct pixels (as opposed to blank pixels in the bounding rectangle), there's no interference between overlapping images to destroy the illusion. Internal Animation I've added another feature essential to producing convincing animation: internal animation, the process of changing the appearance of a given object over time, as distinguished from changing the location of a given object. Internal animation makes images look active and alive. I've implemented the simplest possible form of internal animation in Listing One--alternation between two images--but even this level of internal animation greatly improves the feel of the overall animation. You could easily increase the number of images cycled through, simply by increasing Internal-AnimateMax for a given entity. You could also implement more complex image-selection logic to proudce more interesting and less predictable internal-animation effects, such as jumping, ducking, running, and the like. Dirty-rectangle Management As mentioned above, dirty-rectangle animation makes it possible to access display memory a minimum number of times. Last month's code didn't do any of that; instead, it copied every dirty rectangle to the screen, regardless of overlap between rectangles. This month's code goes to the other extreme, taking great pains never to draw overlapped portions of rectangles more than once. This is accomplished by checking for overlap whenever a rectangle is to be added to the dirty list. When overlap with an existing rectangle is detected, the new rectangle is reduced to between zero and four nonoverlapping rectangles. Those rectangles are then again considered for addition to the dirty list, and may again be reduced, if additional overlap is detected. A good deal of code is required to generate a fully nonoverlapped dirty list. Is it worth it? It certainly can be, but in Listing One, it probably isn't. For one thing, you'd need bigger, heavily overlapped objects for this approach to pay off big. Besides, this program is mostly in C, and spends a lot of time doing things other than actually accessing dispaly memory. It also takes a fair amount of time just to generate the nonoverlapped list; the overhead of all the looping, intersecting, and calling required to generate the list eats up a lot of the benefits of accessing display memory less often. Nonetheless, fully nonoverlapped drawing can be useful under the right circumstances, and I've implemented it in Listing One so you'll have something to refer to should you decide to try this route. There are a couple of additional techniques you might try if you want to wring maximum performance out of dirty-rectangle animation. You could try coalescing rectangles as you generate the dirty-rectangle list. That is, you could detect pairs of rectangles that can be joined together into larger rectangles, so that fewer, larger rectangles would have to be copied. This would boost the efficiency of the low-level copying code, albeit at the cost of some cycles in the dirty-list management code. You might also try taking advantage of the natural coherence of animated graphics screens. In particular, because the rectangle used to erase an image at its old location often overlaps the rectangle within which the image resides at its new location, you could simply directly generate the two or three nonoverlapped rectangles required to copy both the erase rectangle and the new-image rectangle for any single moving image. The calculation of these rectangles could be very efficient, given that you know in advance the direction of motion of your images. Handling this particular overlap case would eliminate most overlapped drawing, at a minimal cost; you might then decide to ignore overlapped drawing between different images, which tends to be both less common and more expensive to identify and handle. Drawing Order and Visual Quality A final note on dirty-rectangle animation concerns the quality of the displayed screen image. Last month, we simply stuffed dirty rectangles in a list in the order they became dirty, and then copied all of the rectangles in that same order. Unfortunately, this caused all of the erase rectangles to be copied first, followed by all of the rectangles of the images at their new locations. Consequently, there was a significant delay between the appearance of the erase rectangle for a given image and the appearance of the new rectangle. A byproduct was the fact that a partially complete--part old, part new--image was visible long enough to be noticed. In short, although the pixels ended up correct, they were in an intermediate, incorrect state for a sufficient period of time to make the animation look wrong. This violated a fundamental rule of animation: No pixel should ever be perceptible in an incorrect state. To correct the problem, this month I've sorted the dirty rectangles by Y coordinate, and secondarily by X coordinate. This means the screen updates from the top down, and from left to right, so the several nonoverlapping rectangles copied to draw a given image should be drawn nearly simultaneously. Run last month's code and then this month's; you'll see quite a difference in appearance. Avoid the trap of thinking animation is merely a matter of drawing the right pixels, one after another. Animation is the art of drawing the right pixels at the right times so the eye and brain see what you want them to see. Animation is a lot more challenging than merely cranking out pixels, and it sure as heck isn't a purely linear process. Until We Meet Again It's been two years since my first graphics column for DDJ. In that time, I've learned a great deal about graphics, partly from my research for the column, but mostly from those of you around the world. For instance, I got two letters from the Ukraine last week. (One was accompanied by a manuscript--in Russian. Two important tips: Send your manuscripts to the DDJ editorial offices, not to me, and write them in English.) You are a remarkably inquisitive and sharing lot, and it's hard to imagine how I could have enjoyed writing this column any more than I have. Unfortunately, this will be my last column, for now at least. Other responsibilities and challenges beckon, and I've covered much of what I set out to share two years ago (six years ago, if you count my graphics columns in the late Programmer's Journal). I hope the world is a little better because of the interchange of ideas, information, and even a bit of humor that went on in this space. I know I'm richer for having written and corresponded with many of you. I'm not vanishing off the face of the Earth, of course; we'll meet in these pages again. Until then, thanks for your support and sharing. In particular, thanks for your support of the Careware effort; you've helped change many lives for the better. I'd also like to thank the DDJ staff, especially Monica Berg and Tami Zemel, for their unfailing support and good humor. Au revoir. -------------------------------------------------------------------------