Real-Time 3D Animation

Using simple vector calculations to draw objects that move and spin in a 3-D environment

By Lincoln Lydick, Littleton, Colorado

Ever felt that real-time 3d animation was meant only for the “computer gods” to create? That mere mortal programmers are destined only to marvel at the feats of greatness? That finding example code on how to accomplish some of these tricks is impossible? Well it turns out not to be difficult at all. This example uses simple vector calculations to draw 6 objects which move and spin in a 3 dimensional environment. The viewer is also free to move, look at, and even follow any of the objects. To optimize the calculations, we’ll do all of this without SANE. This may sound difficult, but stick with me - it’s very simple

The Plan

In order to draw cubes and pyramids (henceforth called objects), we’ll use a single pipeline that translates, rotates and projects each in perspective. But first we need to develop a plan. Our plan will be a Cartesian coordinate system where all objects (including the viewer) will occupy an x, y, & z position. The objects themselves will be further defined by vertices and each vertex is also defined by an x, y, & z coordinate. For instance, cubes will be defined by eight vertices and pyramids by five - with lines drawn between.

Figure 1: Vertex assignment

Changing any value of a vertex represents movement within space. Therefore we can move the viewer or an object by simply changing an x, y, or z. If either the viewer or an object is required to move in the direction of some angle, then we provide a variable called velocity and apply these simple vector equations:

[EQ.1]  Xnew = Xold + sin(angle) * velocity
[EQ.2]  Ynew = Yold + cos(angle) * velocity

Translation

Objects will first be translated (moved) relative to the viewer’s position. This is required because rotation calculations (coming up next) require points to be rotated around a principal axis. Therefore, since the viewer may not be at the origin (Figure 2), we must move the object the same amount we would need to move the viewer to be at the origin (Figure 3). Note: I adopt the convention where the x and y axis are parallel to the plane, and the z axis depicts altitude.

So to perform this “relative” translation, we just subtract the components of the two points:

[EQ.3]  Xnew = Xold - ViewerX
[EQ.4]  Ynew = Yold - ViewerY
[EQ.5]  Znew = ViewerZ - Zold

Now this is all well and good, but what if the viewer is looking at the object? Wouldn’t the object then be directly in front of the viewer - and subsequently drawn at the center of the window? Yes, and this leads us to

Figure 2: Before & Figure 3: After Translation

Rotation

Since we’re providing the viewer with the ability to “look around”, we need to rotate each object by the viewer’s angle. This rotation will occur around the Z axis and is accomplished by applying these calculations to each vertex:

[EQ.6]  Xnew = Xold * cos(angle) - Yold * sin(angle)
[EQ.7]  Ynew = Xold * sin(angle) + Yold * cos(angle)

Figure 4: Before & Figure 5: After Rotation

Figure 4 shows the viewer looking at the object by some angle. Rotating the object by that angle indeed moves it centered on the y axis (Figure 5) and will be drawn centered in the window. Of course if the viewer and the object are at different heights, (it could be above or below us), we might not see it at all - but we’ll deal with that later.

Now if an object is allowed to rotate itself (i.e., spin), then we use the same calculations, although the angle will be unique to the object and not the viewers. Note, this rotation must occur with the object at the origin, and before it is translated relative to the viewer or rotated by the viewer’s angle. Therefore, we’ll first build the object around the origin, spin it, move it to its correct location, then translate and rotate as shown earlier. This may sound costly (and it is a little) but we’ll compute the net movement once and add it in one quick swoop.

Perspective Drawing

After translation and rotation, the final step is to plot each vertex on the window and connect them with lines. This requires describing a 3d scene on a 2d medium (the screen) and is accomplished by perspective projection. Therefore to plot a 3d point, we’ll use the following calculations:

[EQ.8]  H = X * kProjDistance / Y + origin.h
[EQ.9]  V = Z * kProjDistance / Y + origin.v

where origin.h and origin.v are the center of the window. Note: y must not be negative or zero - if it is, let it equal 1 before using the formula. kProjDistance is a constant that describes the distance of the conceptual projection plane from the viewer (see below).

Figure 6: Object being projected onto a projection plane.

This plane is the “window” to which all points get plotted. Points outside this plane are not visible. Experiment with this constant and you’ll notice smaller values (like 100) create a “fish-eye” lens effect. This is due, in part, to the ability of the projection plane to display more than we would normally see. A value between 400 to 500 approximates a 60 degree cone of vision.

Optimizations

1. All of our calculations are ultimately manipulated into integer values (in order to draw to a window) so calculations involving extended variables (decimal accuracy) are not required. However, we do need to find the sine and cosine of angles, which are fractional values, and requires the use of SANE. But SANE is notoriously slow and further requires all angles to be specified by radians - yuk! Our solution to this dilemma is simple, and very accurate: a Sine Table.

What we’ll do is calculate 91 values of sine (angles 0 to 90) once at initialization, multiply each by 1000, and save them in an indexed array of integers (multiplying by 1000 converts them into rounded integer values which are quite suitable). Finally, when we need to multiply by sine or cosine, we just remember to divide the answer back by 1000. If we desire finer rotations, we can break the angles down into minutes (which is provided by the constant kMinutes) having no effect on execution speed. Note: the cosine of an angle is found from the inverse index of the sine index (see procedure GetTrigValues()).

2. Due to object symmetry (and the fact we only rotate on one axis), redundant calculations can be avoided for the top plane of cubes. By calculating only the vertices of the base, we’ll be able to assign them to the top directly (except for the z component) - see the code.

3. Matrices might be employed but the concept of matrix multiplication tends to confuse an otherwise simple explanation, and is well covered in previous MacTutor articles (see references).

4. Finally, avoiding all traps entirely (esp. _LineTo, _CopyBits and _FillRect) and writing the bottleneck routines in assembly. This was done in the assembly version (except for _LineTo).

The Code

The interface code and error checking are minimal - in the interest of clarity. The only surprise might be the offscreen bit map: since double buffering (_CopyBits) is explored in many other articles, I decided to add the bit map.

After initialization, we check the mouse position to see if the viewer has moved. This is done by conceptually dividing the window into a grid and subtracting a couple of points. Once the velocity and angle of the viewer are determined, the sine and cosine values are also calculated. We also check the keyboard to see if either the “q” key or “w” key might be pressed (“q” = move up, “w” = move down). Armed with these values, we start translating and rotating all the points. If an object can spin, it is first built around the origin and rotated. Once all the rotations are complete and the vertices are found, we decide if the object is visible; if it’s not, we skip it and go on to the next. Otherwise, we connect the dots with lines. This continues until all the points and lines are drawn - then we transfer the bit image to the window and start the process all over (or until the mouse button is pressed - then we quit).

Of course more objects can be easily added (or even joined to create a single complex object) but at the expense of the frame rate. Frame rate refers to how many times the screen can be erased and redrawn per second (fps) and is always a major obstacle for real time simulations (usually sacrificing detail for faster animation). This example runs at 30 fps when written in assembly on a Macintosh II. This was clocked when looking at all the objects - and over 108 fps when looking away. This discrepancy is due to the line drawing, since all of the other calculations take place regardless of whether we see the objects or not. Therefore, speeds averaging 60+ fps (instead of 30) might be obtained if we wrote our own line drawing routines as well! Of course this C version runs somewhat slower but for the purpose of this article is much easier to understand.

One final thing worth mentioning - our lines are not mathematically clipped to the window (where the endpoint is recalculated to the intersection of the line and window). This will present a problem if we calculate an end greater than 32767 or less than -32767 (the maximum allowed by QuickDraw). Our solution is to not draw the object if it is too close.

The Future

If interest is shown, perhaps we’ll discuss a technique for real-time hidden line removal. There are a couple of methods that could be incorporated into this example. We might also look at adding rotations around the other two axis and linking them to the same control. This could be the first step to developing a flight simulator. Who knows, terrain mapping using octree intersections, other aircraft and airports, sound... the skies the limit (pun intended). Have fun.

References

Foley, vanDam, Feiner, Hughes. Computer Graphics, (2nd ed.) Addison-Wesley Publishing Company. Good (but very general) explanation of geometrical transformations, rotations and perspective generation using matrix algebra. Also includes line clipping, hidden line removal, solid modeling, etc

Burger & Gillies. Interactive Computer Graphics. Addison-Wesley Publishing Company. Very similar to above and less expensive.

Martin, Jeffrey J. “Line Art Rotation.” MacTutor Vol.6 No.5. Explains some of the concepts presented here, plus rotations around 2 axis, matrix multiplication, and illustrates why we avoid SANE in the event loop.

Listing

/*---------------------------
#
#Program: Tutor3D™
#
#Copyright © 1991 Lincoln Lydick
#All Rights Reserved.
#
#
Include these libraries (for THINK C):
 MacTraps
 SANE

Note:   
 The procedures “RotateObject()” and “Point2Screen()”
 significantly slow this program because THINK C creates a
 JSR to some extra glue code in order to multiply and divide
 long words. Therefore both procs are written in assembly,
 however the C equivalent is provided in comments above.
 Simply replace the asm {} statement with the C code if you
 prefer.

---------------------------*/

#include  “SANE.h”
#include“ColorToolbox.h”

#define kMaxObjects6 /*num. objects*/
#define kMinutes 4 /*minutes per deqree*/
#define kProjDistance450  /*distance to proj. plane*/
#define kWidth   500 /*width of window*/
#define kHeight  280 /*height of window*/
#define kMoveUpKey 0x100000 /*’q’ key = move up*/
#define kMoveDnKey 0x200000 /*’w’ key = move down*/
#define kOriginH (kWidth/2) /*center of window */
#define kOriginV (kHeight/2)/*ditto*/
#define kMapRowBytes (((kWidth+15)/16)*2)

/* Define macros so MoveTo() & LineTo() accept Points.*/
#define QuickMoveTo(pt) asm{move.l pt, gOffPort.pnLoc}
#define QuickLineTo(pt) asm{move.l pt, -(sp)}asm {_LineTo}

enum  ObjectType {cube, pyramid};
typedef struct {shortx, y, z;
} Point3D;/*struct for a 3 dimensional point.*/

typedef struct {
 Point3Dpt3D;
 short  angle, sine, cosine;
} ViewerInfo;  /*struct for viewer’s position.*/

typedef struct { 
 enum   ObjectType objType;
 Point3Dpt3D;
 short  angle, halfWidth, height;
 Booleanrotates, moves;
} ObjectInfo;    /*struct for an object.*/

ViewerInfogViewer;
Point3D gDelta;
Point   gMouse, gVertex[8];
WindowPtr gWindow;
BitMap  gBitMap;
GrafPortgOffPort;
Rect    gVisRect, gWindowRect;
ObjectInfogObject[kMaxObjects];
short   gVelocity, gSineTable[(90*kMinutes)+1];
KeyMap  gKeys;

/****************************************************/
/* 
/* Assign parameters to a new object (a cube or pyramid).
/* 
/****************************************************/
static void NewObject(short index, enum ObjectType theType, short width, 
short height,
 Boolean rotates, Boolean moves, short positionX, short positionY, short 
positionZ)
{
 register ObjectInfo *obj;
 
 obj = &gObject[index];
 obj->angle = 0;
 obj->objType = theType;
 obj->halfWidth = width/2;
 obj->height = height;
 obj->rotates = rotates;
 obj->moves = moves;
 obj->pt3D.x = positionX;
 obj->pt3D.y = positionY;
 obj->pt3D.z = positionZ;
}

/****************************************************/
/* 
/* Initialize all our globals, build the trig table, set up an
/* offscreen buffer, create a new window, and initialize all
/* the objects to be drawn.
/****************************************************/
static void Initialize(void)
{
 extended angle;
 short  i;

 InitGraf(&thePort);
 InitFonts();
 InitWindows();
 InitMenus();
 TEInit();
 InitDialogs(0L);
 InitCursor();
 FlushEvents(everyEvent, 0);
 SetCursor(*GetCursor(crossCursor));

 if ((*(*GetMainDevice())->gdPMap)->pixelSize > 1)
 ExitToShell();  /*should tell user to switch to B&W.*/

 /*create a table w/ the values of sine from 0-90.*/
 for (i=0, angle=0.0; i<=90*kMinutes; i++, angle+=0.017453292/kMinutes)
 
 gSineTable[i] = sin(angle)*1000;

   /* give the viewer an initial direction and position */
 gViewer.angle = gViewer.sine = gViewer.pt3D.x = gViewer.pt3D.y = 0;
 
 gViewer.cosine = 999;
 gViewer.pt3D.z = 130;

 /*create some objects (0 to kMaxObjects-1).*/
 NewObject(0, cube, 120, 120, false, false, -150, 600, 0);     
 NewObject(1, cube, 300, 300, true, false, -40, 1100, 60);
 NewObject(2, cube, 40, 10, true, true, 0, 500, 0);
 NewObject(3, pyramid, 160, 160, false, false, 200, 700, 0);
 NewObject(4, pyramid, 80, -80, true, false, 200, 700, 240);
 NewObject(5, pyramid, 60, 60, false, false, -40, 1100, 0);

 SetRect(&gBitMap.bounds, 0, 0, kWidth, kHeight);
 SetRect(&gWindowRect, 6, 45, kWidth+6, kHeight+45);
 SetRect(&gVisRect, -150, -150, 650, 450);
 gWindow = NewWindow(0L, &gWindowRect, “\pTutor3D™”, true, 0, (Ptr)-1, 
false, 0);

 /*make an offscreen bitmap and port */
 gBitMap.rowBytes = kMapRowBytes;
 gBitMap.baseAddr = NewPtr(kHeight*kMapRowBytes);
 OpenPort(&gOffPort);
 SetPort(&gOffPort);
 SetPortBits(&gBitMap);
 PenPat(white);
}

/****************************************************/
/* Return the sine and cosine values for an angle.
/****************************************************/
static void GetTrigValues(register short *angle, register short *sine, 
register short *cosine)
{
 if (*angle >= 360*kMinutes)
 *angle -= 360*kMinutes;
 else if (*angle < 0)
 *angle += 360*kMinutes;

 if (*angle <= 90*kMinutes)
 { *sine = gSineTable[*angle];
 *cosine = gSineTable[90*kMinutes - *angle];
 }
 else if (*angle <= 180*kMinutes)
 { *sine = gSineTable[180*kMinutes - *angle];
 *cosine = -gSineTable[*angle - 90*kMinutes];
 }
 else if (*angle <= 270*kMinutes)
 { *sine = -gSineTable[*angle - 180*kMinutes];
 *cosine = -gSineTable[270*kMinutes - *angle];
 }
 else
 { *sine = -gSineTable[360*kMinutes - *angle];
 *cosine = gSineTable[*angle - 270*kMinutes];
}}

/****************************************************/
/* Increment an objects angle and find the sine and cosine
/* values. If the object moves, assign a new x,y position for
/* it as well. Finally, rotate the object’s base around the z
/* axis and translate it to correct position based on delta.
/* 
/* register Point*vertex; short i;
/* 
/* for (i = 0; i < 4; i++)
/* {  vertex = &gVertex[i]; savedH = vertex->h;          
/* vertex->h=((long)savedH*cosine/1000 -
/* (long)vertex->v*sine/1000)+gDelta.x;
/* vertex->v=((long)savedH*sine/1000 +
/* (long)vertex->v*cosine/1000)+gDelta.y;
/* }
/****************************************************/
static void RotateObject(register ObjectInfo       *object)
{
 Point  tempPt;
 short  sine, cosine;

 object->angle += (object->objType == pyramid) ? -8*kMinutes : 2*kMinutes;
 GetTrigValues(&object->angle, &sine, &cosine);
 if (object->moves)
 { object->pt3D.x += sine*20/1000; /*[EQ.1]*/
 object->pt3D.y += cosine*-20/1000;/*[EQ.2]*/
 }

 asm  { moveq    #3, d2   ; loop counter
 lea    gVertex, a0; our array of points
 loop:  move.l   (a0), tempPt ;  ie., tempPt = gVertex[i];
 move.w cosine, d0
 muls   tempPt.h, d0 ;  tempPt.h * cosine
 divs   #1000, d0; divide by 1000
 move.w sine, d1
 muls   tempPt.v, d1 ;  tempPt.v * sine
 divs   #1000, d1; divide by 1000
 sub.w  d1, d0   ; subtract the two
 add.w  gDelta.x, d0 ;  now translate x
 move.w d0, OFFSET(Point, h)(a0);  save new h

 move.w sine, d0
 muls   tempPt.h, d0 ;  tempPt.h * sine
 divs   #1000, d0; divide by 1000
 move.w cosine, d1
 muls   tempPt.v, d1 ;  tempPt.v * cosine
 divs   #1000, d1; divide by 1000
 add.w  d1, d0   ; add em up
 add.w  gDelta.y, d0 ;  now translate y
 move.w d0, OFFSET(Point, v)(a0);  save new v
 addq.l #4, a0   ; next vertex address
 dbra   d2, @loop; loop
 }
}

/****************************************************/
/* Rotate a point around z axis and find it’s location in 2d
/* space using 2pt perspective.
/*
/* saved = pt->h;/*saved is defined as a short.*/
/* pt->h = (long)saved*gViewer.cosine/1000 -
/* (long)pt->v*gViewer.sine/1000;  /*[EQ.6]*/
/* pt->v = (long)saved*gViewer.sine/1000 +
/* (long)pt->v*gViewer.cosine/1000;/*[EQ.7]*/
/* /*[EQ.8 & 9]*/
/* if ((saved = pt->v) <= 0)saved = 1;/*never <= 0*/
/* pt->h = (long)pt->h*kProjDistance/saved+kOriginH;
/* pt->v = (long)gDelta.z*kProjDistance/saved+kOriginV;
/****************************************************/
static void Point2Screen(register Point *pt)
{asm  { 
 move.w gViewer.cosine, d0; [EQ.6]
 muls   OFFSET(Point, h)(pt), d0;  pt.h * cosine
 divs   #1000, d0; divide by 1000
 move.w gViewer.sine, d1
 muls   OFFSET(Point, v)(pt), d1;  pt.v * sine
 divs   #1000, d1; divide by 1000
 sub.w  d1, d0   ; subtract, yields horizontal
 move.w gViewer.sine, d1  ; [EQ.7]
 muls   OFFSET(Point, h)(pt), d1;  pt.h * sine
 divs   #1000, d1; divide by 1000
 move.w gViewer.cosine, d2
 muls   OFFSET(Point, v)(pt), d2;  pt.v * cosine
 divs   #1000, d2; divide by 1000
 add.w  d2, d1   ; add, yields vertical
 bgt    @project ; if (vertical<=0) 
 moveq  #1, d1   ; then vertical=1

project:muls#kProjDistance, d0;  [EQ.8]. horiz*kProjDist
 divs   d1, d0   ; divide by the vertical
 addi.w #kOriginH, d0;  add origin.h
 move.w d0, OFFSET(Point, h)(pt);  save the new hor
 move.w #kProjDistance, d0; [EQ.9]
 muls   gDelta.z, d0 ;  height * kProjDistance
 divs   d1, d0   ; divide by the vertical
 addi.w #kOriginV, d0;  add origin.v
 move.w d0, OFFSET(Point, v)(pt);  save the new vert
 }
}

/****************************************************/
/* For all of our cubes and pyramids, index thru each -
/* calculate sizes, translate, rotate, check for visibility,
/* and finally draw them.
/****************************************************/
static void DrawObjects(void)
{
 register ObjectInfo *obj;
 short  i;

 for (i = 0; i < kMaxObjects; i++)
 { obj = &gObject[i];
 gDelta.x = obj->pt3D.x - gViewer.pt3D.x; /*[EQ.3]*/
 gDelta.y = obj->pt3D.y - gViewer.pt3D.y; /*[EQ.4]*/
 gDelta.z = gViewer.pt3D.z - obj->pt3D.z ; /*[EQ.5]*/

 if (obj->rotates) /*does this one rotate?*/
 { gVertex[0].h=gVertex[0].v=gVertex[1].v=gVertex[3].h = -obj->halfWidth;
 gVertex[1].h=gVertex[2].h=gVertex[2].v=gVertex[3].v = obj->halfWidth;
 RotateObject(obj);
 }
 else   /*translate*/
 { gVertex[0].h = gVertex[3].h = -obj->halfWidth + gDelta.x;
 gVertex[0].v = gVertex[1].v = -obj->halfWidth + gDelta.y;
 gVertex[1].h = gVertex[2].h = obj->halfWidth + gDelta.x;
 gVertex[2].v = gVertex[3].v = obj->halfWidth + gDelta.y;
 }

 if (obj->objType == pyramid) /* a pyramid?*/
 { gVertex[4].h = gDelta.x; /*assign apex*/
 gVertex[4].v = gDelta.y;
 }
 else
 { gVertex[4] = gVertex[0]; /*top of cube.*/
 gVertex[5] = gVertex[1];
 gVertex[6] = gVertex[2];
 gVertex[7] = gVertex[3];
 }

 Point2Screen(&gVertex[0]); /*rotate & plot base*/
 Point2Screen(&gVertex[1]);
 Point2Screen(&gVertex[2]);
 Point2Screen(&gVertex[3]);
 gDelta.z -= obj->height;
 Point2Screen(&gVertex[4]);

 if (! PtInRect(gVertex[4], &gVisRect)) /* visible?*/
 continue;

 QuickMoveTo(gVertex[0]);
 QuickLineTo(gVertex[1]);
 QuickLineTo(gVertex[2]);
 QuickLineTo(gVertex[3]);
 QuickLineTo(gVertex[0]);
 QuickLineTo(gVertex[4]);

 if (obj->objType == pyramid)
 { QuickLineTo(gVertex[1]); /*Finish pyramid.*/
 QuickMoveTo(gVertex[2]);
 QuickLineTo(gVertex[4]);
 QuickLineTo(gVertex[3]);
 } else {
 Point2Screen(&gVertex[5]); /*Finish cube.*/
 Point2Screen(&gVertex[6]);
 Point2Screen(&gVertex[7]);
 QuickLineTo(gVertex[5]);
 QuickLineTo(gVertex[6]);
 QuickLineTo(gVertex[7]);
 QuickLineTo(gVertex[4]);
 QuickMoveTo(gVertex[1]);
 QuickLineTo(gVertex[5]);
 QuickMoveTo(gVertex[2]);
 QuickLineTo(gVertex[6]);
 QuickMoveTo(gVertex[3]);
 QuickLineTo(gVertex[7]);
}} }

/****************************************************/
/* Check mouse position (velocity is vertical movement,
/* rotation is horiz.), calculate the sine and cosine values of
/* the angle, and update the viewer’s position. Finally, check
/* the keyboard to see if we should move up or down.
/****************************************************/
static void GetViewerPosition(void)
{
 GetMouse(&gMouse);
 if (! PtInRect(gMouse, &gWindowRect))
 return;
 gVelocity = -(gMouse.v-(kOriginV+45))/5;
 gViewer.angle += (gMouse.h-(kOriginH+6))/14;
 GetTrigValues(&gViewer.angle, &gViewer.sine, &gViewer.cosine);

 gViewer.pt3D.x += gViewer.sine*gVelocity/1000; /*[EQ.1]*/
 gViewer.pt3D.y += gViewer.cosine*gVelocity/1000; /*[EQ.2]*/

 GetKeys(&gKeys);
 if (gKeys.Key[0] == kMoveUpKey)
 gViewer.pt3D.z += 5;
 if (gKeys.Key[0] == kMoveDnKey)
 gViewer.pt3D.z -= 5;
}

/****************************************************/
/* Draw a simple crosshair at the center of the window.
/****************************************************/
static void DrawCrossHair(void)
{
 QuickMoveTo(#0x008200fa);/*ie., MoveTo(250, 130)*/
 QuickLineTo(#0x009600fa);/*ie., LineTo(250, 150)*/
 QuickMoveTo(#0x008c00f0);/*ie., MoveTo(240, 140)*/
 QuickLineTo(#0x008c0104);/*ie., LineTo(260, 140)*/
}

/****************************************************/
/* Main event loop - initialize & cycle until the mouse
/* button is pressed.
/****************************************************/
void main(void)
{
 Initialize();
 while (! Button())
 { FillRect(&gBitMap.bounds, black);
 GetViewerPosition();
 DrawObjects();  /*main pipeline*/
 DrawCrossHair();
 CopyBits(&gBitMap, &gWindow->portBits, &gBitMap.bounds, &gBitMap.bounds, 
0, 0L);
 }
 FlushEvents(mDownMask+keyDownMask, 0);
}