3d Animation

 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.
 Topic:     Graphics Software
            Programming Instruction
            Three-Dimensional Graphics
            Source Code.
 Feature:   illustration

 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

 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).


 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 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 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

 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

 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

 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.

 [BACK] Back

Discuss this article in the forums

Date this article was posted to GameDev.net: 7/16/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
Michael Abrash's Articles

© 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
Comments? Questions? Feedback? Click here!