RealTime 3D
Volume Number:   8

Issue Number:   1

Column Tag:   C Workshop

RealTime 3D Animation
Using simple vector calculations to draw objects that move and spin in a 3D environment
By Lincoln Lydick, Littleton, Colorado
Note: Source code files accompanying article are located on MacTech CDROM or source code disks.
Ever felt that realtime 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 “fisheye” 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 realtime 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.) AddisonWesley 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. AddisonWesley 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 090.*/
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 kMaxObjects1).*/
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);
}