Newsgroups: rec.games.programmer,comp.graphics,rec.answers,comp.answers,news.answers
Path: bloombeacon.mit.edu!hookup!swrinde!ihnp4.ucsd.edu!mvb.saic.com!MathWorks.Com!news.duke.edu!newsfeed1.peachnet.edu!paperboy.wellfleet.com!noc.near.net!dasnews.harvard.edu!honeydew.srv.cs.cmu.edu!rochester!rit!iscnewsserver!nick.csh.rit.edu!pat
From: pat@mail.csh.rit.edu
Subject: FAQ: 3D Information for the Programmer
XArchiveInformation: /pub/3dfaq/FAQ.n @ ftp.csh.rit.edu
MessageID: <1994May6.184642.26078@ultb.isc.rit.edu>
FollowupTo: rec.games.programmer
Summary: Still in progress, fillintheblanks...
Originator: pat@nick.csh.rit.edu
Keywords: gameprogramming 3dtransforms faq
Sender: pat@mail.csh.rit.edu
NntpPostingHost: nick.csh.rit.edu
ReplyTo: pat@mail.csh.rit.edu
Organization: Computer Science House @ RIT
XPostingInformation: This article posted automagically, weekly.
Date: Fri, 6 May 1994 18:46:42 GMT
Approved: newsanswersrequest@MIT.Edu
Lines: 537
Xref: bloombeacon.mit.edu rec.games.programmer:16428 comp.graphics:24574 rec.answers:5320 comp.answers:5249 news.answers:19223
Archivename: 3dprogrammerinfo
Version: $Id: .header,v 1.7 1994/03/14 17:36:21 pat Exp $
O O
+ + F A Q + + F A Q + +
%[% X$HOOR$H\[[8@DoooDDDDD8@@[%[% X$HOOR$H\[[8@DoooDDDDD8@@[%[% X$H
[[% $C$OOR$H\%[8DooooDDDD8D@@[[[% $C$OOR$H\%[8DooooDDDD8D@@[[[% $C$
[[% X$HHRR$H@[ 88@@[[% X$HHRR DDDD88@@[[% X$H
[[[ $$$HRR$H@%[@8ooooD 888@[[[[ $$$HRR$H@%[@8o DDDD888@[[[[ $$$
[[[ X$$H / / 88[[[[ X$ / / D888[[[[ X$$
[%[ XC$H \%[@8DDD DD @[[%[ XC $H\%[@ DDDD 88@[[%[ XC$
[[% XC$H \%%@8DD DDDD @[[% XC $H\%% DDDDDD 8@@[[% XC$
[%[ X$$H \%%@88DDD D8 @[%[ X$ $H\%%@8 DDD8 8@@[%[ X$$
[%[ CX$H \%%[88DDD88 D @[%[ CX $H\%%[88D 88D 8@@[%[ CX$
[%[ X$CH \%[[@888D8D8  @[%[ X$ _$H\%[[@888 88 88@[%[ X$C
[%[ XXCH  [@888D888  @@[%[ XX  H\@[[@888 8 88@@[%[ XXC
[%[ XC$$ \ \  88@[%[ XC \ \   8888@[%[ XC$
[%[ XX$HOR$HH@ [@88888 8D8@@[%[ XX$HOR H@[%[@8 @8888D8@@[%[ XX$
[%[ X$CHOR$H\@% @@@@Y 8888@@[%[ X$CHOR$ @%%[Y @8888888@@[%[ X$C
[%[ CX$$OR$HH@%% .d8D88@@[%[ CX$$OR$H .d@@888D88@@[%[ CX$
[[[ X$$HOR$HH@%%[[@@@@88D8D88@[[[ X$$HOR$HH@%%[[@@@@88D8D88@[[[ X$$
[%[ CX$HOR$HH\%[%[@@@@888D88@@[%[ CX$HOR$HH\%[%[@@@@888D88@@[%[ CX$
+ + F A Q + + F A Q + +
Contents:
1) General references for 3d graphics questions.
2) How do I define an object?
3) How do I define space?
4) How do I define position?
5) How do I define orientation?
6) How do I define a velocity?
7) Drawing threedimensional objects on a twodimensional screen.
8) Vector Math  Dot Product and CrossProduct.
9) Matrix Math
10) Collisions.
11) Perspective.
12) ZBuffering & the Painters Algorithm & BSPTrees.
13) Shading.
14) 3space clipping.
15) 3d scanning.
16) Publically available sourcecode.
17) Books on the topics.
18) Other forums.
19) Current Contents of Archive ftp.csh.rit.edu::/pub/3dfaq
Last update:
03Mar94
What's new?
A bit more matrix math.
Added another book to the list
Contents of the Archive I'm keeping on this stuff.
1) General references for 3d graphics questions.
Well, this FAQ is just getting off the ground. Hopefully it will
touch on most of the bases you need to get started for now, and
hopefully it will expand at least as fast as you need it too. But...
regardless, things you'll want to locate for more help are Matrix
Algebra books, Physics books talking about Eulerian motion, and some
books on the Graphics Hardware you want to program for. The code
examples included in this FAQ will most likely be in C with pseudocode
in comments.
One of the most popular references, (and one of my favorites), is:
Computer Graphics: Principles and Practice

Foley, van Dam, Feiner, and Hughes
Addison Wesley  Reading, Massachusetts
(c) 1990. ISBN 0201121107
But, you'll also want to definitely check out the FAQ for
comp.graphics. That FAQ touches mainly on 2D needs, but some 3D
aspects are reviewed there, too.
2) How do I define an object?
There are lots of ways to define objects. One of the most commonly
used is the OFF (Object File Format). The OFF toolkit and a library of
objects are available via anonymous ftp from gatekeeper.dec.com  XXX
???. The format provides easy methods for extensions and a base set of
things you can expect for each object. The toolkit is a bit bulky, but
the file format (in ascii) is easy enough to parse by hand.
The OFF.aoff file contains information about the object. The most
important one there is the location of the surface specification file
(usually object name.geom). This file also contains other attributes

and file names relevant to this object.
The OFF surface specification begins with the number of points, the
number of polygons and the number of segments.
npts nplys nsegs
This line is followed by the floating point coordinates for the points
that make up the object.
x1 y1 z1
x2 y2 z2
x3 y3 z3
.
.
x(npts) y(npts) z(npts)
Then, it gets a bit more complicated. The following lines begin with a
number to indicate the number of vertices in this polygon. That number
is followed by that many numbers, one for each vertex. These are given
in an order specified in the .aoff (usually conterclockwise). So, for
example, a triangle and a pentagon which share a side are shown below.
3 1 3 4
5 2 4 3 6 7
Here is some quick and dirty sample code to read in the .geom file:
struct polygon {
int nvert; /* Number of vertices in this polygon */
int *verts; /* Vertices in this polygon */
};
struct object {
int npts; /* The number of points */
int npolys; /* The number of polygons */
int nsegs; /* The number of segments */
double *point x,*point y,*point z;
  
struct polygon *polys;
};
int
read geom file( char *geom file, struct object *obj )
  
{
FILE *fp;
int i,j;
if (!(fp = fopen(geom file,"r"))) /* Open the .geom file */

return 1;
/* Get header information */
fscanf(fp,"%d %d %d",&obj.npts,&obj.npolys,&obj.nsegs);
/*
** Allocate room for the points.
*/
obj.point x = (double *)malloc(obj.npts*sizeof(double));

obj.point y = (double *)malloc(obj.npts*sizeof(double));

obj.point z = (double *)malloc(obj.npts*sizeof(double));

for (i=0;i triplets, it will
require a fair bit of work on reading them in to turn them into
spherical coordinates. If you're looking to this FAQ for information on
how to define the space your objects will be in, I'd strongly suggest
using rectangular coordinates and some derivative of the OFFformat.
For starters, let me just throw in that while our universe may be
infinite in all directions, that doesn't make for good programming. We
have to limit ourselves to small enough numbers that we can multiply
them together without overflowing them, we can divide them without
crashing our systems, and we can add them without accidentally flipping
a sign bit.
Now, the fun begins. The simplest form of defining the Universe is
to flat out say that the Universe stretches over these coordinates, say
in the bounding box of <65536, 65536, 65536> to <65536, 65536,
65536>. This is often referred to as a Universal Coordinate system or
an Absolute Coordinate system. Then, each object in the Universe will
be centered about some coordinate in that range. This includes your
viewpoint. Several strategies are available for dealing with the edge
of the Universe. One can make the Universe wrap around so that an
object leaving the cube at < X, Y, 65536> will reappear in the Universe
at < X, Y, 65536>. Or, one can make objects bounce or stop at the edge
of the Universe. And, given any approach, one can have the edge of the
Universe be transparent or opaque.
In an Absolute Coordinate system, all objects must be shown from
the position of your viewpoint. This involves lots of interesting math
that we'll get into later. But, in general, an objects position with
respect to you is it's absolute position  your absolute position (with
all kinds of hell breaking loose if you can see past the edge of the
Universe). Then, after this position is calculated, it must be rotated
based on your orientation in the Universe.
Another possibility for defining space is a Relative Coordinate
system or a ViewCentered Coordinate system. In this sort of system,
the Viewpoint is always at coordinates <0,0,0> and everything else in
the Universe is based relatively to this home position. This causes
funky math to come into play when dealing with velocities of objects,
but... it does wonders for not having to deal with the 'edge of the
Universe'. This is the Schroedinger's cat method of the 'edge of the
Universe'.... in the truest sense of out of sight is out of mind. Small
provisions have to be made if objects aren't to wrap around. But... a
Relative Coordinate system can be used to give the illusion of infinite
space on a finite machine. (Yes, even your 486/66DX is finite).
I'll leave spherical coordinates to a later version if people think
they'll be of use...
4) How do I define position?
Position in an Absolute Coordinate system is easy. Each object has
three coordinates. These are often stored in a datatype called a
vector to abstract further the notion that these numbers belong
together.
typedef struct {
long x;
long y;
long z;
} VECT;
Usually, each object in the Universe is defined about its center with
each coordinate on its surface being centered at its own <0,0,0>. This
helps tremendously in rotating the object, and I would highly recommend
this. Then, the object as a whole is given a position in space. When
it comes time to draw this object, its points' coordinates get added on
to its position.
In a Relative Coordinate system, position is also fairly straight
forward. The viewpoint always has position VECT={ 0, 0, 0 };. Other
objects follow the same sort of system that they would in Absolute
Coordinate systems.
5) How do I define orientation?
Orientation can be quite tricky. I interchange some of the terms
here quite often. In 3space, orientation must be defined be twoand
ahalf angles. "Two and a half?" you say. Well, almost everyone uses
three because two just isn't enough, but if you want to be technical,
one of those angles only has to range from 0  180 degrees (0  PI/2
radians).
But, taking that for granted now.... you have to pick an
orientation for your view. I personally prefer to have the Xaxis run
from left to right across the center of my screen. I also like to have
the Yaxis run from the bottom of my screen; and I also like to have the
Zaxis running from me straight into my screen. With some tweaking of
plus and minus signs and a bit of reordering, all of the math herein
can be modified to reflect any orientation of the coordinate system.
Some people prefer to have the Yaxis heading into the screen with the
Zaxis going vertically. It's all a matter of how you want to define
stuff.
Given that you've agreed with me that Z can go into the screen,
what 3angles do you need? (Here's where I stand the biggest chance of
mucking up the terms.) You need roll, pitch, and yaw. (I often mix up
roll and yaw and such... so if you can follow along without getting
locked into my terminology, future FAQ's will correct it.)
Look at your monitor as you're reading this. Now tilt your head so
that your right ear is on your right shoulder. This change in
orientation is roll (or yaw... but I call it roll).
Ok, now sit up straight again. Now bring your chin down to meet
your chest. (Hmmm... LOOK BACK NOW!!!, whew... glad you heard me.)
That motion was pitch.
Ok, now look over your right shoulder keeping your head vertical to
see who's behind you. (LOOK BACK AGAIN!!.) Ok... that was yaw (or
roll, but I call it yaw).
That's the basics. Now, what do I do with them? Well, here's
where a nice book on Matrix Arithmetic will help you out. You have to
use these three angles to make a Transformation matrix. [See the
section on Matrix Math]. Here is a typical method of doing these
transformations: [Note, if you don't have Z going into your screen
you'll have to munge these considerably].
typedef double matrix[4][4];
double sr,sp,sy,cr,cp,cy;
matrix mr, mp, my; /* individual transformations */
matrix s; /* final matrix */
sr = sin( roll ); cr = cos( roll );
sp = sin( pitch ); cp = cos( pitch );
sy = sin( yaw ); cy = cos( yaw );
/* clear all matrixes
** [See the section on Matrix Math]
*/
identity( &mr ); identity( &mp ); identity( &my );
/* prepare roll matrix */
mr[0][0] = mr[1][1] = cr;
mr[1][0] =  (mr[0][1] = sr);
/* prepare pitch matrix */
mp[1][1] = mp[2][2] = cp;
mp[1][2] =  (mp[2][1] = sp);
/* prepare yaw matrix */
my[0][0] = my[2][2] = cy;
my[0][2] =  (my[2][0] = sy);
multiply( &mr, &my, &s );
multiply( &s, &mp, &s );
6) How do I define a velocity?
Sticky question. I'll get to it in the next rev.
7) Drawing threedimensional objects on a twodimensional screen.
Modified from comp.graphics FAQ:
"There are many ways to do this. Some approaches map the
viewing rectangle onto the scene, by shooting rays through
each pixel center and assigning color according to the object
hit by the ray. Other approaches map the scene onto the
viewing rectangle, by drawing each object into the region,
keeping track of which object is in front of which.
The mapping mentioned above is also referred to as a
'projection', and the two most popular projections are
perspective projection and parallel projection. For example,
to do a parallel projection of a scene onto a viewing
rectangle, you can just discard the Z coordinate, and 'clip'
the objects to the viewing rectangle (discard portions that
lie outside the region). To do a perspective projection,
dividing each the x and the y by some multiple or the Zdepth
is the usual approach.
For details on 3D rendering, the Foley, van Dam, Feiner and
Hughes book, reading. Chapter 6 is 'Viewing in 3D', and
chapter 15 is 'VisibleSurface Determination'. For more
information go to chapter 16 for shading, chapter 19 for
clipping, and branch out from there."
8) Vector Math  Dot Product and CrossProduct.
Adding and subtracting vectors is as easy as subtracting their
respective parts:
+ =
 =
Scaling vectors is as simple as multiplying each part by a
constant:
S * =
The DotProduct of two vectors is simply the sum of the products of
their respective parts:
. = A*D + B*E + C*F
Note that this value is not a vector.
The CrossProduct of two vectors is a bit more complex (it is the
determinant of the matrix with the direction vector as the first row,
the first vector as the second row, and the second vector as the third
row):
X =
Note that:
X = 1 * ( X )
and
( X ) . = ( X ) . = 0
More later.
9) Matrix Math
The identity matrix is a square matrix (same number of rows as
columns) with all elements {i,j} given by:
{ 1.0 if i == j
m[i][j] = {
{ 0.0 otherwise
Multiplication of matrices:
if X is a matrix that is m rows and n columns (an mbyn (or mxn) matrix)
and Y is a matrix that is n rows and r columns (nxr), then the product
X * Y ==> m[i][j] = sum{ a=0, a