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.
-----------------------------------------------------------------------------
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.
[BACK] Back
Discuss this article in the forums
See Also: © 1999-2011 Gamedev.net. All rights reserved. Terms of Use Privacy Policy
|