Journal: Dr. Dobb's Journal Jan 1992 v17 n1 p121(7) ----------------------------------------------------------------------------- Title: 3-D animation. (Graphics Programming)(column) (Tutorial) Author: Abrash, Michael. AttFile: Program: GP-JAN92.ASC Page flips & polygon fills in C. Abstract: Tips and techniques for programming three-dimensional animation routines are presented. 3-D animation can be performed on the 80x86 architecture using a combination of drawing pipelines, projection, translation and rotation algorithms. Objects are built out of polygons that represent a surface; the polygon must be transformed from world space into view space, and the projection of the Z axis must follow a particular ratio in view space to accurately represent world space. Translation is the process of adding X, Y and Z offsets to a coordinate to move it through world space and actually requires nothing more than an addition for each axis. Rotation circularly moves coordinates around the origin in order to turn objects to the desired attitude before translating them into world space. A simple example program that displays and moves a polygon in 3-D space is included; source code and notes are provided. ----------------------------------------------------------------------------- Descriptors.. Topic: Graphics Software Programming Instruction Tutorial Animation Three-Dimensional Graphics Source Code. Feature: illustration chart graph program. ----------------------------------------------------------------------------- Full Text: When first I started programming micros, more than 11 years ago now, there wasn't much money in it, or visibility, or anything you could call a promising career. Sometimes, it was a way to accomplish things that would never have gotten done otherwise because minicomputer time cost too much; other times, it paid the rent; mostly, though, it was just for fun. Given free computer time for the first time in my life, I went wild, writing versions of all sorts of software I had seen on mainframes, in arcades, wherever. It was a wonderful way to learn how computers work: trial and error in an environment where nobody minded the errors, with no meter ticking. Many sorts of software demanded no particular skills other than a quick mind and a willingness to experiment: Space Invaders, for instance, or full-screen operating system shells. Others, such as compilers, required a good deal of formal knowledge. Still others required not only knowledge but also more horsepower than I had available. The latter I filed away on my ever-growing wish list, and then forgot about for a while. Three-dimensional animation was the most alluring of the areas I passed over long ago. The information needed to do rotation, projection, rendering, and the like was neither so well developed nor widely so available then as it is now, although, in truth, it seemed more intimidating than it ultimately proved to be. Even had I possessed the knowledge, though, it seems unlikely that I could have coaxed satisfactory 3-D animation out of a 4-MHz Z80 system with 160x72 monochrome graphics. In those days, 3-D was pretty much limited to outrageously expensive terminals attached to minis or mainframes. Times change, and they seem to do so much faster in computer technology than in other parts of the universe. A 486 is capable of decent 3-D animation, owing to its integrated math coprocessor; not in the class of, say, an i860, but pretty good nonetheless. A 386 is less satisfactory, though; the 387 is no match for the 486's coprocessor, and most 386 systems lack coprocessors. However, all is not lost;32-bit registers and built-in integer multiply and divide hardware make it possible to do some very interesting 3-D animation on a 386 with fixed-point arithmetic. Actually, it's possible to do a surprising amount of 3-D animation in real mode, and even on lesser 80x86 processors; in fact, the code in this article will perform real-time 3-D animation (admittedly very simple, but nonetheless real-time and 3-D) on a 286 without a 287, even though the code is written in real-mode C and uses floating-point arithmetic. In short, the potential for 3-D animation on the 80x86 family may be quite a bit greater than you think. This month, we kick off an exploration of some of the sorts of 3-D animation that can be performed on the 80x86 family. Mind you, I'm talking about arbitrary 3-D animation, with all calculations and drawing performed on-the-fly; generating frames ahead of time and playing them back is an excellent technique, but I'm interested in seeing how far we can push purely real-time animation. Granted, we're not going to make it to the level of Terminator 2, but we should have some fun nonetheless. The initial columns may seem pretty basic to those of you experienced with 3-D programming, and, at the same time, 3-D neophytes will inevitably be distressed at the amount of material I skip or skim over. That can't be helped, but at least there'll working code, the references mentioned later, and some explanation; that should be enough to start you on your way with 3-D. Animating in three dimensions is a complex task, so this will be an ongoing topic, with later columns building on previous ones; even this firt 3-D column will rely on polygon fill and page-flip code from earlier columns. From time to time I'll skip to other topics, but I'll return to 3-D animation on a regular basis, because, to my mind, it's one of the most exciting things that can be done with a computer--and because, with today's hardware, it can be done. References on 3-D Drawing There are several good sources for information about 3-D graphics. Foley and van Dam's Computer Graphics: Principles and Practice (Second Edition, Addison-Wesley, 1990) provides a lengthy discussion of the topic and a great many references for further study. Unfortunately, this book is heavy going at times; a more approchable discussion is provided in Principles of Interactive Computer Graphics, by Newman and Sproull (McGraw-Hill, 1979). Although the latter book lacks the last decade's worth of graphics developments, it nonetheless provides a good overview of basic 3-D techniques, including many of the approaches likely to work well in real time on a PC. A source that you may or may not find useful is the series of six books on C graphics by Lee Adams, as exemplified by High-Performance CAD Graphics in C (Windcrest/Tab, 1986). (I don't know if all six books discuss 3-D graphics, but the four I've seen do.) To be honest, this book has a number of problems, including: relatively little theory and explanation; incomplete and sometimes erroneous discussions of graphics hardware, use of nothing but global variables, with cryptic names like "array3" and "B21;" and--well, you get the idea. On the other hand, the book at least touches on a great many aspects of 3-D drawing, and there's a lot of C code to back that up. A number of people have spoken warmly to me of Adam's books as their introduction to 3-D graphics. I wouldn't recommend these books as your only 3-D references, but if you're just starting out, you might want to look at one and see if it helps you bridge the gap between the theory and implementation of 3-D graphics. The 3-D Drawing Pipeline Each 3-D object that we'll handle will be built out of polygons that represent the surface of the object. Figure 1 shows the stages a polygon goes through enroute to being drawn on the screen. (For the present, we'll avoid complications such as clipping, lighting, and shading.) First, the polygon is transformed from object space, the coordinate system the object is defined in, to world space, the coordinate system of the 3-D universe. Transformation may involve rotating, scaling, and moving the polygon. Fortunately, applying the desired transformation to each of the polygon vertices in an object is equivalent to transforming the polygon; in other words, transformation of a polygon is fully defined by transformation of its vertices, so it is not necessary to transform every point in a polygon, just the vertices. Likewise, transformation of all the polygon vertices in an object fully transforms the object. Once the polygon is in world space, it must again be transformed, this time into view space, the space defined such that the viewpoint is at (0,0,0), looking down the Z axis, with the Y axis straight up and the X axis off to the right. Once in view space, the polygon can be perspective-projected to the screen, with the projected X and Y coordinates of the vertices finally being used to draw the polygon. That's really all there is to basic 3-D drawing: transformation from object space to world space to view space to the screen. Next, we'll look at the mechanics of transformation. One note: I'll use a purely right-handed convention for coordinate systems. Right-handed means that if you hold your right hand with your fingers curled and the thumb sticking out, the thumb points along the Z axis and the fingers point in the direction of rotation from the X axis to the Y axis, as shown in Figure 2. Rotations about an axis are counter-clockwise, as viewed looking down an axis toward the origin. The handedness of a coordinate system is just a convention, and left-handed would do equally well; however, right-handed is generally used for object and world space. Sometimes, the handedness is flipped for view space, so that increasing Z equals increasing distance from the viewer along the line of sight, but I have chosen not to do that here, to avoid confusion. Therefore, Z decreases as distance along the line of sight increases; a view space coordinate of (0,0-1000) is directly ahead, twice as far away as a coordinate of (0,0-500). Projection Working backward from the final image, we want to take the vertices of a polygon, as transformed into view space, and project them to 2-D coordinates on the screen, which, for projection purposes, is assumed to be centered on and perpendicular to the Z axis in view space, at some distance from the screen. We're after visual realism, so we'll want to do a perspective projection, in order that farther objects look smaller than nearer objects, and so that the field of view will widen with distance. This is done by scaling the X and Y coordinates of each point proportionately to the Z distance of the point from the viewer, a simple matter of similar triangles, as shown in Figure 3. It doesn't really matter how far down the Z axis the screen is assumed to be; what matters is the ratio of the distance of the screen from the viewpoint to the width of the screen. This ratio defines the rate of divergence of the viewing pyramid--the full field of view--and is used for performing all perspective projections. Once perspective projection has been performed, all that remains before calling the polygon filler is to convert the projected X and Y coordinates to integers, appropriately clipped and adjusted as necessary to center the origin on the screen or otherwise map the image into a window, if desired. Translation Translation means adding X, Y, and Z offsets to a coordinate in order to move it linearly through space. Translation is as simple as it seems; it requires nothing more than an addition for each axis. Translation is, for example, used to move objects from object space, in which the center of the object is typically the origin (0,0,0), into world space, where the object may be located anywhere. Rotation Rotation is the process of circularly moving coordinates around the origin. For our present purposes, it's necessary only to rotate objects about their centers in object space, so as to turn them to the desired attitude before translating them into world space. Rotation of a point about an axis is accomplished by transforming it according to the formulas shown in Figure 4. These formulas map into the more generally useful matrix-multiplication forms also shown in Figure 4. Matrix representation is more useful for two reasons: First, it is possible to concatenate multiple rotations into a single matrix by multiplying them together in the desired order; that single matrix can then be used to perform the rotations more efficiently. Second, 3x3 rotation matrices can become the upper-left-hand portions of 4x4 matrices that also perform translation (and scaling as well, but we won't need scaling in the near future), as shown in Figure 5. A 4x4 matrix of this sort utilizes homogeneous coordinates; that's a topic way beyond this column, but, basically, homogeneous coordinates allow you to handle both rotations and translations with 4x4 matrices, thereby allowing the same code to work with either, and making it possible to concatenate a long series of rotations and translations into a single matrix that performs the same transformation as the sequence of rotations and transformations. There's much more to be said about transformations and the supporting matrix math, but, in the interests of getting to working code this month, I'll leave that to be discussed as the need arises. A Simple 3-D Example At this point, we know enough to be able to put together a simple 3-D animation example. The example will do nothing more complicated than display a single polygon as it sits in 3-D space, rotating around the Y axis. To make things a little more interesting, we'll let the user move the polygon around in space with the arrow keys, and with the "A" (away), and "T" (toward) keys. The sample program requires two sorts of functionality: the ability to transform and project the polygon from object space onto the screen (3-D functionality), and the ability to draw the projected polygon (complete with clipping) and handle the other details of animation (2-D functionality). Happily (and not coincidentally), we put together a nice 2-D animation framework back in the July, August, and September columns, so we don't much have to worry about non 3-D details. Basically, we'll use mode X (320x240, 256 colors, as dicussed in the above-mentioned columns), and we'll flip between two display pages, drawing to one while the other is displayed. One new 2-D element that we need is the ability to clip polygons; while we could avoid this for the moment by restricting the range of motion of the polygon so that it stays fully on the screen, certainly in the long run we'll want to be able to handle partially or fully clipped polygons. Listing One (page 140) is the low-level code for a mode X polygon filler that supports clipping. (The high-level polygon fill code is mode independent, and is the same as in the February and March columns, as noted further on.) The clipping is implemented at the low level, by trimming the Y extent of the scan line list up front, then clipping the X coordinates of each scan line in turn. This is not a particularly fast approach to clipping--ideally, the polygon would be clipped before it was scanned into a line list, avoiding potentially wasted scanning and eliminating the line-by-line X clipping--but it's much simpler, and, as we shall see, polygon filling performance is the least of our worries at the moment. The other 2-D element we need is some way to erase the polygon at its old location before it's moved and redrawn. We'll do that by remembering the bounding rectangle of the polygon each time it's drawn, then erasing by clearing that area with a rectangle fill. With the 2-D side of the picture well under control, we're ready to concentrate on the good stuff. Listings Two through Five are the sample 3-D animation program. Listing Two (page 140) provides matrix multiplication functions in a straightforward fashion. Listing Three (page 140) transforms, projects, and draws polygons. Listing Four (page 142) is the general header file for the program, and Listing Five (page 143) is the main animation program. Other modules required are: Listings One and Six from July (mode X mode set, rectangle fill); Listing Six from September (page 146); Listing Four from March (polygon edge scan); and the FillConvexPolygon() function from Listing One from February. To simplify matters, the archive file 3D-1.ARC, with all required modules and a make file, will be made available as part of the listings from this issue wherever DDJ code is posted. Notes on the 3-D Animation Example The sample program transforms the polygon's vertices from object space to world space to view space to the screen, as described earlier. In this case, world space and view space are congruent--we're looking right down the negative Z axis of world space--so the transformation matrix from world to view is the identity matrix; you might want to experiment with changing this matrix to change the viewpoint. The sample program uses 4x4 homogeneous coordinate matrices to perform transformations, as described above. Floating-point arithmetic is used for all 3-D calculations. Setting the translation from object space to world space is a simple matter of changing the appropriate entry in the fourth column of the object-to-world transformation matrix. Setting the rotation around the Y axis is almost as simple, requiring only the setting of the four matrix entries that control the Y rotation to the sines and cosines of the desired rotation. However, rotations involving more than one axis require multiple rotation matrices, one for each axis rotated around; those matrices are then concatenated together to produce the object-to-world transformation. This area is trickier than it might initially appear to be; more in the near future. The maximum translation along the Z axis is limited to -40; this keeps the polygon from extending past the viewpoint to positive Z coordinates. This would wreak havoc with the projection and 2-D clipping, and would require 3-D clipping, which is far more complicated than 2-D. We'll get to 3-D clipping someday, but, for now, it's much simpler just to limit all vertices to negative Z coordinates. The polygon does get mighty close to the viewpoint, though; run the program and use the "T" key to move the polygon as close as possible--the near vertex swinging past provides a striking sense of perspective. The performance of Listing Five is, perhaps, surprisingly good, clocking in at 16 frames per second on a 20-MHz 386 with a VGA of average speed and no 387, although there is, of course, only one polygon being drawn, rather than the hundreds or thousands we'd ultimately like. What's far more interesting is where the execution time goes. Even though the program is working with only one polygon, 73 percent of the time goes for transformation and projection. An additional 7 percent is spent waiting to flip the screen. Only 20 percent of the total time is spent in all other activity--and only 2 percent is spent actually drawing polygons. Clearly, we'll want to tackle transformation and projection first when we look to speed things up. (Note, however, that a math coprocessor would considerably decrease the time taken by floating-point calculations.) In Listing Three, when the extent of the bounding rectangle is calculated for later erasure purposes, that extent is clipped to the screen. This is due to the lack of clipping in the rectangle fill code from July; the problem would more appropriately be addressed by putting clipping into the fill code, but, unfortunately, I lack the space to do that here. Finally, observe the jaggies crawling along the edges of the polygon as it rotates. This is temporal aliasing at its finest! It'll be a while before we address antialiasing, real-time antialiasing being decidedly nontrivial, but this should give you an idea of why antialiasing is so desirable. Coming Up Next time, we'll assign fronts and backs to polygons, and start drawing only those that are facing the viewer. That will enable us to handle convex polyhedrons, such as tetrahedrons and cubes. We'll also look at interactively controllable rotation, and at more complex rotations than the simple rotation around the Y axis that we did this month. If there's room, we'll try moving the viewpoint, and perhaps we'll even use fixed-point arithmetic to speed things up. If not, patience; we'll get to all that and more (shading, hidden surfaces, maybe even a little rendering and antialiasing) soon.