[size="5"]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.
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...


[size="5"] 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. :-)


[size="5"] 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.


[size="5"] 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

[Editor's Note: Chris never finished this series, so the articles we have here are the only ones available.] 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... :-)


[size="5"] 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....
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,
Likewise, the trend continues.....

AngleSine Cosine 00190101800-1270-10Which demonstrates a very important point about these functions
... 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:
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...


[size="5"]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....

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.


[size="5"]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

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:

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

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...

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