Citation: Dr. Dobbs Journal, Jan 1990 v15 n1 p16(13) --------------------------------------------------------------------------- Title: Real-time animation: presenting a sprite driver for EGA. (enhanced graphics adapter) (technical) Authors: James, Rahner --------------------------------------------------------------------------- Subjects: Programming Instruction; Tutorial; Animation; Color; Computer Graphics; Real-Time Systems; Program Development Techniques; New Technique Reference #: A8156528 =========================================================================== Abstract: A sprite-based driver is developed for smooth, non-flickering, real-time animation on an enhanced graphics adapter (EGA). Good animation requires coordinate movement of image objects anywhere on a screen, motion of object components independent of coordinate movement, smooth transitions between and complete image frames, regular image transitions without jerky movements, and image consistency for a relative degree of realism. The new technique involves the creation of a set of pixels, a sprite, that constitute an object, removing and storing a section of the background in the shape of the sprite, and placing the sprite in the cutout section. An OR-routine enables the sprites to have internal holes. The sprite driver consists of four routines: EGA sprite drivers, sprite circle handler, display of sprite file on an EGA screen, and a make file. =========================================================================== Full Text COPYRIGHT M&T Publishing 1990 Real-Time Animation As a child, I could not differentiate between Bugs Bunny and Walter Cronkite. This is not to say that the man America most trusted had dental problems, but that the child did not have the experience to see the cartoon for what it was -- a stream of individually drawn pictures. Skilled professional help was required to deal with the trauma caused by the revealed truth. Even after the psychological defects were converted to scars, I had to wait until I could create two-dimensional life for myself. The Time Has Come Animation is achieved by showing a series of incrementally changing images. Depending on the duration of time that a single image is shown and the time it takes to switch to the next image increment, the viewer's visual persistence smooths out the image's transition. Anyone with a compiler and a graphics library can put a series of images on a computer display. But in order to create smooth, non-flickering, real-time animation, a fair amount of thought is necessary. To support reasonable animation, the algorithm must conform to the following rules: Coordinate Movement -- The routines must allow individual objects to be moved around on the screen and placed on any pixel boundary. Independent Motion -- Each object in the image should be able to show a chain of sequences independent of its coordinate movement. Smooth Transitions -- The transition between image frames should have no intermediate stages. This means that the viewer should see only complete images, not images that are half the first image and half the second image. These half-and-half images are perceived as a flicker and are distracting. Regular Transitions -- All image transitions should occur at regular intervals. If this does not happen, the sequence will appear to jerk as if shown on an old projector. Sprites -- If an object has a hole, any objects that are behind it should show through. Poorly done animation will not allow the viewer to see through a gap in an object. Realistic Objects -- There is a difference between what is shown on the screen and what is perceived by the observer. Up to a point, jagged lines will be smoothed, imperfect colors accepted, and stairstep corners rounded. This point, the point of realism, is subjective and entirely dependent on the target audience. Below this point, other unrelated flaws can be magnified; above this point, the overall perception of the product is enhanced. The elements of this list are all mutable by targeted hardware limitations. Accurate shading may be difficult on an AT-class machine. Absolute realism for anything but the simplest geometric shapes is impossible on CGA or EGA. The finished product's design constraints may adjust the significance of one element over the others. These are Rahner rules -- they may be burnt, bent, or beatified. Zippy Tries His Hand at CGA Animation When I first saw reasonable animated images on a CGA adapter, I was intrigued. It was a simple CGA sprite demo -- several helicopters flying aimlessly around the display. Because the demo allowed the helicopters to start only on a byte boundary (four pixels per byte) and did not allow them to exit smoothly from the side of the screen, I decided to try my hand at writing the ultimate animation driver for CGA. After a lazy Sunday's work, the driver was finished. Given CGA's limitations (four colors and 320 X 200 resolution), ultimate is probably too strong a word. It was about the same as tying the ultimate shoelace or throwing the ultimate dirt clod. Anticlimactic would be the correct word for polite company. Because the initial attempt was an unplanned, seat-of-the-pants, I've-got-Fritos-diet-Coke-and-plenty-of-time effort, my trial and error path would best illustrate some animation rudiments. The first attempt was to whip a series of changing pictures past the monitor. This involved copying virtual screens, which I had prearranged, onto the CGA video RAM. This had the interesting effect of flickering the screen with seemingly random images caught in a blizzard. The flicker and snowstorm were due to not waiting for the vertical retrace before displaying the next image. What is vertical retrace? A good question, because it is important later. The CRT monitor etches its pictures in the orbitals of fluorescent compounds with a single beam of electrons. This beam sweeps horizontally back and forth across the screen. In either direction -- back or forth -- the beam has to turn off, otherwise it looks funny. The off direction is called the horizontal retrace. The beam winds its way down the screen in this back and forth manner. When it reaches the bottom, it turns off and returns to the top of the screen: This off time is called the "vertical retrace." On the standard EGA setup, this vertical retrace occurs 60 times a second. The standard CGA adapter has a bit that indicates when the horizontal refresh is occurring and another to show when the vertical refresh is occurring. It was a simple task to change the program so that it waited for the vertical retrace before blasting out the next virtual screen. -- I saw a series of pictures endlessly circling, but without snow or flicker. Next I noticed that most of the screen was stationary and only a small fraction of the image moved at any one time. In fact, most of the things that did move were sets of pixels that did not reposition themselves with respect to one another, only with respect to the rest of the picture. After much deliberation (and lunch), I named these sets "sprites." Later I found that these sets had been noticed by others before and they had used my name for them. Rather than risking a protracted legal battle, I swallowed my pride and have allowed the others to take the credit. The basic concept behind the sprite is simple. Cut a rectangular section out of the screen and store it. Then take the set of pixels that comprise the sprite and replace the cutout section with them. Armed with my "new" creation, I reduced the series of virtual screens to a simple background and a few sprites. The background was displayed first, then the sprites were moved into position before the finish of the vertical retrace. Now I had the same cinematograph that I had before, but the program was more efficient and the storage requirements were reduced. Before I got bored with this endless video cycle, I noticed that when my sprites went in front of something, the background was completely covered, even in places that I should have been able to see through. This meant another change. Instead of just storing the background, I masked off the solid areas of the sprite body. Instead of replacing the cutout, I ORed the sprite onto the masked background, then replaced the cutout around the finished product. This allowed me to have "holes" in the sprites, for increased realism. With the inclusion of holes in the sprites, I had my ultimate CGA sprite routine. All the little fishes were swimming around in my video aquarium without the need for food. I was satisfied and went to bed. You may be asking, "What does this have to do with EGA?" You may be getting sleepy and ready to close the magazine. You may just be hunting for good prices on software. Well, to the shopping sportsman, there are no good prices in this article; to the somnolent peruser, good night; and to the inquisitor in the back with his hand up, Everything! The EGA and I In its 640 X 350-pixel color graphics mode, an EGA adapter with 256K of RAM is set up as four planes of 28,000 bytes each. It also has two pages, one that is being viewed on the monitor and one that is in the ether. Both pages can be addressed directly by the CPU. The first page starts at memory address A000:0000h and the second page starts at A000:8000h. Each byte of EGA memory represents eight pixels with the most significant bit (MSB) being shown as the leftmost pixel. A byte or bit of any combination of the planes may be addressed depending on how the EGA registers have been set. Superficially, there seemed to be little difference between a sprite driver for the CGA and EGA adapters. It seemed to be just another block of RAM that I needed to jam out bytes. Following that line of thought, the first code translation from CGA was conceptually simple. The sprites were placed on the visual page, a plane at a time. When I looked at the result for the first time, I found myself almost back to square one. No matter how efficiently I wrote the driver, there was a constant flicker. I ran to the bookstore, hoping for a tome of enlightenment. My hope was dashed by a limited selection. But a quick reread of the IBM EGA Technical Reference manual provided me with the answers: The EGA adapter can generate an interrupt and the visual page can be switched during the vertical retrace. Writing a Bit Map to EGA Memory The EGA adapter has a fair number of features. All the features and the way the board reacts to CPU memory manipulations are determined by the configuration registers. Most of the registers are set up in pairs. The first register accepts an index value that determines the functionality of the second register. The major register pairs that we need to concern ourselves with are the Sequencer registers and the Graphics 1 & 2 Address registers. Another register that is important for this discussion is Input Status Register One. The Sequencer register is located at 3C4h with its index register at 3C5h. It has five indexed registers: Reset (0), Clocking Mode (1), Map Mask (2), Character Map Select (3), and Memory Mode (4). To access an indexed register, the index's number is output to the Sequencer register followed by the value for that index output to the index port. For example, if you want to place a 5 in the Clocking Mode index register, which is index number 1, the assembly code in Example 1 would do. Because all the register pairs are one right after the other, this code segment could be replaced by that in Example 2. This replacement is usually valid, except when slow ports cause timing difficulties. The important Sequencer index register, with respect to our driver, is the Map Mask Register (index 2). This register enables planes so that the CPU can write to them. Setting bit 0 enables plane 0, bit 1 enables plane 1, and so on. Because there are only four planes, the four MSBs are not used and are ignored. If you wanted to write the same information to multiple planes, multiple bits could be set. No easy assumptions can be made about the sprite data, so we can't really take advantage of this feature. The Graphics 1 & 2 register set deals with colors, pixel masks, and the Boolean graphic operations the EGA can perform. This register is configured the same as the Sequencer register, with nine indexed registers: Set/Reset (0), Enable Set/Reset (1), Color Compare (2), Data Rotate (3), Read Map Select (4), Mode Register (5), Miscellaneous (6), Color Don't Care (7), and Bit Mask (8). The index registers of concern are the Data Rotate register and the Read Map Select register. The Data Rotate register has two controls. Bits 0-2 represent the Rotate Count. The Rotate Count is a binary encoded number that represents the bit positions to shift any data written to a video plane. Because all our data will be unshifted at the hardware level, this value should be 0. Bits 3-4 represent the Function Select. The Function Select indicates which Boolean-type operation is desired for pixels written to display memory. Table 1 shows the available functions. To diverge for a moment, a definition for "latched data" is in order. No matter how it appears, the video memory on the EGA adapter is never directly connected to the PC bus. When the registers are set properly, the program addresses the video memory in exactly the same manner it would any other portion of main memory. The memory can be accessed as a byte or a word, but those accesses are processed through the EGA's circuitry. The circuitry performs some gyrations on the data, then passes it on. In order to properly swing the binary song, that gyrating EGA circuitry latches the byte or word in its internal read/write buffer. A read of EGA memory will put that byte of pixels in the latch, which can then be operated on by some future operation. Because each plane has a seaprate latch buffer, if all four planes have been enabled, 32 bits at a time can be latched (read), operated on, and then rewritten to EGA memory with a single 8086 instruction. Give me an inch and I'll take a while, diverging on to the 8086 instructions. When dealing with this aspect of the EGA adapter, a close look at how some 8086 instructions actually work would be in order. Let's start with the instruction: OR [DI], AL When the 8086 sees this instruction, it loads the value pointed at by the register DI into the 8086 internal register, ORs the value in register AL onto that internal register, then writes the result back out to the location pointed to by DI. If DI happened to point to EGA memory, this would latch up a number of pixels, add in pixels, then write the latch data back out to video memory--all in a single instruction. If an additional EGA function, such as a bit rotate, were added to the previous example, some interesting and possibly useful results could be achieved. I don't use this in my routine, but, by jingo, it's just too nifty to be ignored! The last register of importance is Input Status Register One. It has a few informative bits, but we will be concerned with only the Vertical Retrace bit (3). As the name implies, this bit is set to 1 when the display is in a vertical retrace time. As I stated before, this was the time to write to the video memory with the CGA adapter. It has approximately the same value with the EGA adapter, but not exactly. When Blazing Fast Is Not Fast Enough to Start a Fire When I converted my CGA animation routines to work with the EGA, there was an unexpected problem. I found that no matter how fast I blasted my sprites out to video memory, the raster line (another name for that beam of electrons described earlier) would catch up to where I was writing pixels. When the raster caught up, the screen would flicker annoyingly. Having to deal with four planes and EGA's higher resolution just took too much time. I made my code the most efficient assembly routines I could. I made assumptions about the data I was displaying in order to cut corners. I got a 25-MHz 386 system. Nothing worked. I felt like a laundry soap commercial. I went back to the EGA Technical Reference manual. Almost immediately the answer, written by the IBM ancients, made me question what I had been thinking about in the first place. The standard EGA has 256K of RAM -- enough for two pages of display memory. I would write to one page, wait for the next vertical retrace, then swap pages. I rewrote everything. Planning ahead, I continued reading the Technical Reference manual. The EGA can generate an interrupt request 2. If the driver could just swap pages whenever the video went into vertical retrace, then I wouldn't have to waste time polling. I rewrote it, again. Animation Structures To become animated objects, sprites must have four basic degrees of freedom: Coordinate Motion, Self-relative Motion, Rotation, and Perceived Distance. Coordinate Motion is simply the movement from one point on the screen to another. Self-relative Motion is the movement that the sprite could make without moving to a new coordinate location. Rotation is rotation of the sprite around some center point in its body. Perceived Distance is basically sizing the sprite according to its apparent distance from the viewer. The increment resolution of each degree of freedom is independent of the others. A sprite picture of a person may be pumping its arm up and down a pixel at a time and traversing the screen five pixels at time. Given a monitor/graphics adapter combination that refreshed the screen an infinite number of times, the smaller the movement increment, the more realistic its action would be. Because the standard EGA board refereshes the screenat 60 Hz (60 times a second), the movement increment should be judged relative to the apparent velocity of the sprite, the display resolution, and the level of the art. Because I can draw only crude stick figures, my resolution granularity can be boulder-size. Two of the four degrees of freedom (Rotation and Perceived Distance) should not be a function of a sprite driver. A good, general-purpose rotation algorithm requires fairly heavy calculations. These calculations are burdensome enough to detract from the real-time nature of the animation driver. Although Perceived Distance does not need as much time from the CPU, it should be done at a higher level than the driver. Perceived Distance requires the sprite to be resized larger as it gets closer to the viewer and smaller as it gets farther away. As the size of the sprite approaches the minimum resolution of the monitor, details disappear. No algorithm can make perfect decisions about which features of an object are important to the visual integrity of that object. Self-relative Motion deals with the movement of each of the individual pixels of the sprite with respect to each other, but not straying outside the boundary of the sprite. To illustrate Self-relative Motion without any other component, I have included a sprite of a flame. Each of the pixel groups that represent small flamelets rises to the top of the fire. The pixel groups that represent the edges of the flame billow in the updraft caused by the heated air. In my routine, the effect of the motion is created by a linked list of sprite frames. In the example, each successive frame shows the flame in the next point of time (without regard to mathematical proofs, in animation there is a quantum of time). Because motion in most biological or mechanical systems is cyclical, I join the terminal points of this linked list into a sprite circle. Each sprite can proceed through a cycle of self-relative motions whose complexity is determined by the circumference of the sprite circle. Coordinate Motion involves moving the sprite circle from one point to another on the screen at some regular velocity. The sprite velocity is determined by the number of pixels that the sprite circle will move divided by the number of times per second the visual image will be change. Say we make a sprite representation of a five-meter-long car that is drawn 32 pixels in length. To move that car from the right side of the screen to the center at an apparent velocity of 20 km/hour, the sprite would have to move to the left 176 pixels per second if everything is kept to scale. If our visual page changes come at 20 per second, the sprite would have to be moved nine pixels to the left for every page change. How the Routines Work The sprite routines are broken down into two parts. The portion that deals with the EGA ports, memory and interrupt service is written in 8086 assembly language. Listing One (page 82) shows the EGA sprite drivers and Listing Two (page 88), the sprite circle handler. The higher-level sprite circle and list managers are written in Microsoft C. Listing Three (page 92), SPRITES.C, displays a sprite file on an EGA screen, and Listing Four (page 93) is the make file. Some assumptions were made about the nature of the sprites and the background. The sprite driver is written for sprites of any dimension, but the driver is optimized for a sprite that is 32 bits across. In my application, it was assumed that the observer could pan or tilt the viewing perspective. Because the perspective can be changing in smooth real time, the background is not a set quantity--it is being regenerated in every visual frame. Additionally, because the 8086 family drops at least eight clock ticks every time it makes a JMP or CALL, the code favors execution speed (that is, very few jumps, calls, or loops) over program size. The basic algorithm is simple. Before any operations can be performed, the sprite driver needs to be installed using the function EGA_INSTALL(). This preps the adapter, initializes some variables, and installs the interrupt vector. The first sprite of a sprite circle is inserted into the linked list of circles by calling the function INSERT_SPRITE (START_X, START_Y, END_X, END_Y, SPEED_X, SPEED_Y, DEPTH, SPRITE CIRCLE); where START X and START Y are the starting X, Y coordinates of the sprite, END X and END Y are the ending X, Y coordinates of the sprite, SPEED X and SPEED_Y are the amounts that the X and Y coordinates will change per visual frame, DEPTH is the perceived distance from the observer, and SPRITE_CIRCLE is a pointer to the first entry of the sprite circle. Additional sprites can be added to the circumference of a sprite circle with the function ADD_SPRITE. Once all the sprite circles have been figured out and inserted into the sprite list, call DO_SPRITE_LIST() whenever it is appropriate. DO_SPRITE_LIST() figures out the new sprite positions and places them on the nonvisual page. When it has placed all the sprites, it sets the flag DO PAGE_ FLIP, clears DONE_PAGE_ FLIP, and returns. The main program body is then free to do anything with the sprite structures. At some time in the future, the EGA's vertical interrupts and the interrupt service routine decides whether to swap pages or not. If it does swap the pages, it clears DO_PAGE_FLIP and sets DONE_PAGE_FLIP. Although the routines are not completely reentrant, they are fairly immune to interrupts; they can be called from other interrupt service routines such as the timer tick or a mouse driver. With regard to visual timing, movies project 24 frames per second on the silver screen. To decrease the cost of animation, some cartoon manufacturers will keep the same picture on the screen for more than one frame. The interrupt service routine has a counter that can be used to allow it to skip any number of vertical retraces between page changes. If your CPU is slow or the main body of your program needs more time to do its work, altering the skip count has the effect of smoothing out the movement of the sprites. To counteract the slowing effect that increasing the skip count would have, you must increase the velocity of any coordinate motion proportionately. Finishing Thoughts So much can be written about real-time animation that a conclusion at any point leaves us feeling a lot was left out. The scope of this article does not allow me to explore all the avenues with the depth they deserve. Maybe you can use the routines that have been provided with this article as learning aids to go beyond what has been written. Animation is a form for the presentation of ideas. Seminars, product demonstrations, and computer modeling programs can all be enhanced by the addition of animation graphics. Of course, the most obvious use only enhances what I have always said: The only useful thing someone can do with a computer is play a game on it. Rahner is an independent consultant living near Sacrament, Calif. He can be reached by phone at 916-722-1939 or through CompuServe at 71450, 757. ===========================================================================