Copy Link
Add to Bookmark
Report
Intro to 3D Graphics Programming (Volume 1)
=------------------------------[Intro to 3D Graphics Programming]--[Kiwidog]-=
_____Greetings
Hello everyone,
As my first code article since joining the Hornet crew, I've decided to
write an introduction into 3D graphics coding. Trixter informed me that
DemoNews has never had a 3D article, so it seemed like a good idea. :-)
This will not be just one article - far from it. In fact, it will take
quite a few articles to cover all the information I want to cover (after
finding out about space limitations on article size I'm allowed to write,
I've had to chop up the series into smaller pieces). But expect a minimum
ten or so articles coming your way...
This is the full version of the DemoNews 114 article, which means you've
got the supplement file (that's good, because it has example source, too :)
The source included is the same example, but in three different files,
depending on what language and compiler you use.
WC_EX1.C - Watcom C version (32-bit DOS extended)
BC_EX1.C - Borland C version
TP_EX1.PAS - Turbo Pascal version
This series will assume you've never done 3D graphics (or "Vectors" as
the scene likes to call it) before. I'm going to try this on a very basic
level, and if you're already familiar with the essentials, you might want
to hit PgDn a few times. Eventually, I'll write about more complicated 3D
issues in later articles. But let's take it one step at a time...
_____What You Need To Know First
I'm assuming you have a knowledge of basic algebra, i.e. early high school
level math. If you've had some Trigonometry already, that will help out,
but I'll try to cover the basics of what you need from that as well. But,
more important than any one particular requirement, you have to like math,
or at least a willingness to like it.
MATH IS ONLY BORING IF YOU DON'T HAVE A USE FOR IT.
Basically, 3D coding is not really about programming... it's almost entirely
about math. The amount of time you spend thinking about what you're doing
is generally a lot longer than the time you actually spend pounding the keys
writing the code.
If you don't think you like math, and you're a coder, chances are you
probably _DO_ like math and just don't know it. :-) I'm serious... a lot
of times when you hate a subject in school, you don't really hate it, you
just think you hate it because you hate the way it's taught. Once you get
down to finding a purpose for all that "useless" knowledge.... it becomes
a heck of a lot of fun. So if you like math, and you like coding graphics,
you've come to the right place. If you like coding graphics but don't like
math... give it a chance; you may find out something new about yourself. :-)
_____What You Don't Need to Know First
Okay, generally speaking, the chain of math courses taught in high school
and college (or their European equivalents, which I can't really speak for
but I can take a guess) goes something like this:
1. Algebra 2. Geometry 3. Analytical Algebra 4. Trigonometry
5. Pre-Calculus 6. Calculus 7. Linear Algebra 8. Vector Geometry
9. Multivariable Calculus 10. Differential Equations 11. Even more
complicated issues that I haven't gotten to yet...
You need to know up to #3 to make use of any of this. #4 would be helpful,
although I'll cover a few things here in the beginning to get you going,
if you've never taken Trig before.
Pre-Calc and Calc aren't directly needed for this series, although you'll
find it useful later on in life when you want to make really cool movements
for your vectors. And if you know through #7, life is a breeze; you can
forget most of this beginning crap. :) Anything after that I'm not going to
cover by itself, but you'll find it helpful if you know it, as you try more
innovative ideas with your vector code. But still, it's not necessary at
all for the little I'm going to be able to teach you. :)
_____What Will Be Covered In This Series
Whew, it's a whopper. Here's the series layout as I'm planning it so far.
As you can tell, the first couple articles are for the _very_ beginners,
like the kind who know how to code, but have never even touched anything
with 3D before. After the first few, it'll get more interesting though,
so bear with me (if you have some 3D experience already, you can forget
reading the first few articles; they won't do you any good).
1. Basic Trig functions, 3D Coordinate to 2D Screen Projection.
2. 2D and 3D Rotations & Other Transformations.
3. Dot and Cross Products, Backface Removal and Lightsourcing.
4. Polygon Fills - Flat and Lambert
5. Polygon Fills - Gouraud and Phong
6. Polygon Fills - Affine Texture Mapping
7. Polygon Fills - Perspective Texture Mapping, Perspective Correction
8. Spherical and Cylindrical Coordinates
9. Polygon Fills - Bump Mapping
10. BSP Trees and Spacial Partitioning
11. Polygon Fills - Reflection Mapping
12. Alternative Camera Positioning and Motion
13. Path Management, Linear and Bezier Curve Movement
14. Basic Inverse Kinematics
15. (Unknown - I'm not sure how much further I can take it without risking
losing the few tricks I have up my sleeve for my future :)
It's quite likely that the later articles will be split into separate
articles as well (I doubt I can fit both Gouraud and Phong, for example,
into one article). So the numbers are probably going to get higher and
higher. It will probably be around the time of NAID or afterward that
the series ends.
Get ready for a crash course in 3D... :-)
_____Section One - Basic Trigonometric Functions
Okay, If you've taken Trig before, skip this section. If you haven't,
you're probably thinking that this long title doesn't sound too friendly.
Don't worry, it sounds a whole lot worse than it is.
The main principles of Trigonometry come from the first part of the name,
"Trigon", which pretty much means a triangle. Everything in Trig is based
on a few functions which deal with triangles. There are six of these
functions...
Sine, Cosine, Tangent, Secant, Cosecant, and Cotangent
Abbreviated: Sin, Cos, Tan, Sec, Csc, and Cot.
... but in fact, they all boil down to the first two, Sine and Cosine.
Now I assume you're all familiar with functions, like [f(x) = 2x] and so
forth (BTW I'll enclose functions in [] on occasion throughout this doc).
Well the Trig functions are all functions using angles, for example
[f(x) = sin(x)] or even [f(x) = 2 sin(x) - 5 cos(x)], and so on.
In these cases, x is an angle, either in degrees or radians. I'm going
to stick with degrees for this explanation, since radians are too complex
for me to discuss right now.
Okay, so now you're thinking, "Great... Sine and Cosine are functions using
angles. But what do they _DO_?" Well, here's the rundown.
Get out a piece of paper. Go ahead, I'll wait. Now on that piece of paper,
draw yourself a pair of X and Y coordinate axes, like you normally would for
a graph. Make it big, so you give yourself lots of room.
Now draw a circle around the origin. Make it as good a circle as you can
sketch. Now whatever size you drew your circle, assume that's a radius
of 1. So where the circle hits your X and Y axes, label those points as
X=1 on the right, Y=1 on the top, X=-1 on the left, and Y=-1 on the bottom.
Okay, with this circle, we need some angles. Using your good ol' 360-degree
system, label those four points with their angles, where 0 degrees is facing
the right and they go counterclockwise. So 0 is at the right, 90 is up,
180 is left, and 270 is down.
Now knowing that's how the angles go, draw a line from the origin out to the
circle at about, oh, 60 degrees (up and to the right, more tall than wide).
At that point on the circle, draw a line STRAIGHT DOWN to the X axis. What
you should have now is a triangle inside the circle, with one side on the
X axis, one going straight up, and one at a 60 degree angle.
Okay, it's time for a little guessing game. Assuming that the circle has
a radius of 1 like you drew it, how tall is that vertical side of the
triangle? It's almost as tall as the circle, but not quite... more than
half the height of the circle, maybe around 3/4 the height, something like
that.
What was your guess? Probably somewhere between 0.7 and 0.9, I would think.
It should look about that tall. Whatever your guess is, write it down, and
keep it handy... it's going to be very important.
Now do the same thing for the bottom horizontal side of the triangle, the
one along the X axis. How long is that from the looks of it? It appears
around half the width of the circle, so you'd probably guess around 0.5 or
so. Anyway, write that one down too.
Okay, So you've got this triangle inside this circle, with the longest side
at an angle of 60 degrees and a length of 1 (the radius of the circle),
and two sides going straight vertical and horizontal, with lengths somewhere
near the numbers you guessed.
I'm gonna pull out my calculator, which supports Trig functions. Lemme
punch up the numbers....
Sin(60) = 0.8660254
Cos(60) = 0.5000000
Notice any correlation? You should... they're the lengths of the sides you
were guessing! :-) That, quite simply, is what the Sin and Cos functions
are... if you have a circle with radius 1, and a line at any angle from
the origin to the circle, then the Sine of that angle is the Y-component
(height) of that line, and the Cosine of the angle is the X-component
(width) of the line.
Other examples? Well now that you know what the Sin and Cos functions mean,
what are the Sin and Cos of 90 degrees? Well let's see... that's the line
going straight up from the origin, along the Y axis. The height is
the height of circle, exactly. And the width... well, there is no width,
since it's not going left or right whatsoever.
Sure enough,
Sin(90) = 1.0000000
Cos(90) = 0.0000000
Likewise, the trend continues.....
Angle Sine Cosine
0 0 1
90 1 0
180 0 -1
270 -1 0
Which demonstrates a very important point about these functions
Fact: The Sine and Cosine functions will never go less than -1,
and never greater than 1.
... and that makes sense, considering the circle has a radius of 1.
(Terminology: The circle you drew is often called the "unit circle" by
math books and teacher-type people).
Now by looking at the circle, you can see how the height changes less and
less as you approach Sin=1 or Sin=-1, and likewise the width changes less
and less as you approach Cos=1 or Cos=-1. It turns out that the Sin and
Cos functions are not linear whatsoever... and because of that, calculating
them for any given angle is a real pain in the rear. Sure, you have the
occasional angles like 90 and 180 which have 1s and 0s, or 30 and 60 which
have one of the components exactly 0.5, but most of the time you have values
that are not the nicest of numbers.
For this reason, you often hear 3D coders referring to "Sine Tables", which
are precalculated tables holding the Sin and Cos values for every angle in
their system (in this example, a 360 degree system. It turns out in coding
that a 256 degree system is much more convenient, for reasons you can
probably guess). These do-it-once tables turn an otherwise painful
calculation into a simple memory look-up. :-)
(BTW - earlier I mentioned in addition to Sin and Cos the Tan, Sec, Csc
and Cot functions... these can all be created from Sin and Cos by the
following: Tan(x) = Sin(x)/Cos(x)
Sec(x) = 1/Cos(x)
Csc(x) = 1/Sin(x)
Cot(x) = Cos(x)/Sin(x) = 1/Tan(x)
Most of those aren't very useful in vector coding, with the exception of
Tangent... it will come in handy at times. Everything else isn't too
important for now, but keep it on the back burner for future reference).
Okay, so now you've learned what you need to know from Trig... that the
Sin and Cos functions can be used to find the X and Y parts of a line at
any given angle. You just take the length of the line, multiply the Sin
or Cos (whichever you're looking for, Y or X respectively) by the line's
length, and wham you've got your result. This will be used EXTENSIVELY
in the rest of the doc and in 3D in general, as almost everything depends
on these components.
There is certainly a lot more to trigonometry, and entire books have been
dedicated to the subject. My highly over-simplified version here should
hopefully be enough to get your foot in the door. If you want more
complex and detailed info, I'd highly suggest a good math textbook covering
the subject (Trig is often grouped in with pre-calculus texts, incase you
have a difficult time finding a separate book). But this should be good
enough for the time being. :)
All set? Then let's get out of this plane of thought (sorry, very bad pun)
and get into some three-space nitty gritty, starting with...
_____Section Two - The 3D Cartesian Coordinate System
Okay, you're undoubtedly already used to doing graphics in 2D using the X
and Y axes; it's what you've been doing in algebra all along. Well using
X and Y is the 2D standard of the Cartesian coordinate system, and likewise,
we need to add another axis of depth for 3D - The Z axis. But where does
this Z axis go?
Well X and Y are perpendicular to each other in the 2D plane. It's the same
as the plane of your screen, for example. Well in 3D, we can get depth by
putting the Z axis perpendicular to that entire plane altogether, going
either into or out of your screen.
A common term for a line or plane perpendicular to another plane is
"orthogonal". That is, we want a Z axis that's orthogonal to the XY screen
plane.
But in which direction? It can either go into or out of the plane, so which
one is right? Well this is really entirely by convention... the standard
way is to use a "right handed" orientation. What's a right handed
orientation? Okay, hold up your right hand in front of your face. Point
your thumb toward your nose. Now look at your fingers... they curl
counterclockwise. This is the basis behind a right-handed system. When you
have the XY plane, the two axes for X and Y are to the right and going up,
respectively. So if you start your hand at the first axis, X, and curl your
right hand's fingers in the direction of the second axis, Y, your thumb
will point out toward your nose.
So the Z axis goes out of the screen, toward you, by a right-handed system
(for the same reason, if you used the YX plane instead of the XY plane,
the curl would be in the opposite direction and Z would go into the screen
instead).
Cheesy ASCII graph....
Y
|
|
| Screen Plane
|
|
-------X
/
/
/
Z
The graph above is the way we're going to do it in this doc. All 3D
Cartesian really is, is just the same coordinate system you're used to, but
with the added dimension so you can locate a point anywhere in space and
not just on a plane. End of story (You might find later that other
coordinate systems, like spherical and cylindrical, can help out with some
routines... but I'll go over those in time).
Short section, eh? There's more, but not much. :-) Well, now with the 3D
system in your grasp, it's time to put it to use, and get some 3D points to
show up on-screen.
_____Section Three - Perspective Projection
Now we've got this nice XYZ spacial coordinate system... but how do we take
advantage of it and get some stuff on-screen from it? In 2D, it was easy...
you just used the same X axis as in your coordinates, and the Y axis was the
same only flipped upside down (since as you know, in coding it's easier if
the Y axis goes down, for calculation reasons). But how are we going to
take this Z thing into account and make things look right?
The way we do it is by "Perspective Projection". Perspective is a pretty
basic idea which you see continuously in your life.... Things further away
from you look smaller than things closer up. Pretty obvious fact that you've
lived with throughout your existence. :)
Well all we have to do is turn that simple principle into math...
English way: "Things further away from you look smaller than things
closer up."
Math way: "The projected size of any object in the eye is inversely
proportional to its distance from the eye".
It's more "math-like", but still makes sense, right? They both mean the
same thing more or less, but the second phrase is more easily turned into
equation form... the kind we can put into our code.
Okay, by our ASCII graph of the coordinate system, your eye lies right along
our Z axis, staring down in the negative direction (the Z axis goes out of
your screen, and you're looking in). So an object's, or point's, distance
from the eye is going to have a lot to do with the Z coordinate of that
point.
So the first thing we need to settle is, if our eye (or in our case, the
video screen) is sitting somewhere along the Z axis.... where along the Z
axis is it? In truth, this is entirely up to you... the screen is just
a "camera", and we're trying to find a convenient place for it to sit.
All we know is that it goes along the positive Z axis.
It turns out for calculation reasons that a very effective place to put the
camera is at Z=256. You'll see why in a minute... (and no, none of this
is carved in stone. Cameras can go anywhere and view in any direction,
it's just that the math gets more complicated).
Okay, now we've got the camera at (0,0,256) and pointing in the negative
direction. That means that our Cartesian origin is exactly 256 units away
from us, right along our line of sight. The next thing we need to make up
is a frame of reference for X and Y.... How big, visually, is a unit along
X or Y? Well we can use any set of values we see fit, but just to make it
easier on the brain, we want to use something we're already used to...
something intuitive...
How about 1 pixel? It's easy to compute, since it's the same as your
screen plane. Okay, so we know _somewhere_ viewable along this axis, X and
Y are going to mean 1 pixel units.
But where along the Z axis? If things get larger as they get closer and
smaller as they get further away, where's a good distance to say where the
unit/pixel plane sits?
Heck, why not just use the Z=0 plane? After all, we know the origin is
perfectly visible (256 units down the -Z axis) so the origin is easily in
reach, and probably will make it easy to calculate our perspective viewing.
Okay, we've got all we need to set up some perspective equations. Now let's
do some simple examples in our heads so we can find out where these
equations are coming from...
In 320x200 resolution (you can use any resolution you want, really, but this
is just for demonstration), the center point of your screen is at (160,100).
Makes sense, and you're probably very used to this by now. Well, we're
viewing along the -Z axis, so that's where our axis is going down. Right
along the line of that pixel. No up, no down, no left, no right. That's it.
Now we know that at Z=0, Every X and Y unit mean one pixel. So where would
(5,5,0) be positioned? Well, it's the same as our screen plane, so there's
no distance adjustments to do. It's 5 to the right of the origin, so
ScrX=160+5 = 165. And it's 5 above the origin, which is in the opposite
direction of our "screen plane" Y, so that's ScrY=100-5 = 95. You've got
your projected point.
So what to do with points not on Z=0? Howsabout (5,5,128)? Well if we
think about it, Z=0 is 256 units distance from the screen. Well Z=128 is
256-128 = 128 units distance from the screen. Exactly half of the distance.
Half the distance? That makes it twice the size! :-) So instead of adding
5 to X and subtracting 5 from Y, you'd use 10 instead for each axis. That
would give us screen coords (170,90) for this point. Same 3D X and Y as in
the first example, but the fact that it's so much closer makes it look
further from the center of the screen... the essence of perspective. :)
Now in general, our equations go something like this
ScrX = ( Lens*X / Distance ) + CenterX
ScrY = CenterY - ( Lens*Y / Distance )
I'll explain each piece. First, ScrY _would_ be the same basic equation
as ScrX, except that we have to do the subtraction instead because Y goes
down onscreen, not up. Anyway, we have a few variables here...
ScrX and ScrY are the screen point of the 3D point we're trying to project.
I figure you guessed that one already. :-)
Distance is the distance of the point from the eye. As we discussed before,
this has a _direct_ correlation to the Z coordinate of our 3D point. Now
since we're on the positive Z axis but viewing in the negative direction,
and we know that at Z=0 the distance is 256, then any point where Z > 0
will have a distance < 256. Likewise, if Z < 0, the point will be further
away than the origin, and distance > 256. This makes distance a very
simple value:
Distance = (256-Z)
Pretty easy, eh? :-) Now, Lens is a multiplier used to give your projection
the right "field of view" that you want. You can manipulate Lens to give
the projection a very narrow range of vision, or to give it the classic
"wall-eye" view as well. But in general, a really messed-up field of view
will make people want to vomit. It's not natural.
So we want to set it to something that will "feel" natural. Well, from our
calculations and the fact that we want a unit/pixel relationship at Z=0,
we can get our Lens factor immediately... 256. It's also a nice multiplier,
as you can use bit-shifts to get it, instead of a costly MUL instruction.
And finally, CenterX and CenterY are positive integers that match to the
center X and Y point onscreen; 160 and 100 in this case (the Center value
for any resolution is just the resolution/2, which makes sense).
So, from there, our equations boil down to
ScrX = ( 256*X / (256-Z) ) + 160
ScrY = 100 - ( 256*Y / (256-Z )
The first thing you should recognize is that we don't need to calculate
(256-Z) twice. Also, if you use fixed point, you can calculate the divide
only once as well, but that's for a later article (I'm not focusing on
optimizations in this one). Anyway, let's work out one of our previous
examples using these equations and see if we get the same result. How about
the (5,5,128) one... let's see...
Distance = 256-Z = 256-128 = 128
ScrX = ( 256*X / 128 ) + 160
= ( 256*5 / 128 ) + 160
= 10 + 160
= 170
ScrY = 100 - ( 256*Y / 128 )
= 100 - ( 256*5 / 128 )
= 100 - 10
= 90
Yup, same answer! And these equations go quite easily into code. :-)
Now you'll find that using straight integer math with these equations will
work well at first, but there are added advantages to using fixed point
math as well. If you're familiar with fixed point, you should have few
problems trying to adapt this to it, speeding things up in the process.
If you're not familiar with it, don't sweat it; I'll cover it in an
upcoming article.
Well, looks like that's the end of this article... make sure to check out
the sample source in Pascal and C within this supplement, and try a few
experiments out on your own! You'll want to get very familiar with
projection as we get into more advanced stuff later on... and since it's
at least a week until the next DemoNews, you've got the time, so take
advantage of it. :-)
Next issue, it'll be time to start on our path to not just getting these
points up there, but getting them to move. Straight movement left, right,
up, down, in and out is easy... you just add or subtract from X, Y, or Z.
But rotation, that's another story.
Until next time,
Chris Hargrove
a.k.a. Kiwidog, of Terraformer & Hornet
Coding & Organization
email: <kiwidog@vt.edu>
