Intro to 3D Graphics Programming: Volume III
by Chris Hargrove

Introduction

Howdy everyone!

Time for round three... :-)

This is the last introductory article before we dive into polygon fillers, and it's something that's crucial to any effective 3D system. You may be asking yourself, "Hey, I can do projection and rotation now, isn't that all I need to start making solid objects?" Well, not quite.

Let's say you want to make a cube. You know how to project the cube's vertices, so that's fine. You can rotate the vertices too, so that's not a problem either. And let's say you know how to do polygon filling too... well what happens when you start rotating the cube around?

A big mess. :) Sides in the back show up half the time, so the cube doesn't look solid at all. And then you decide you want to add lightsourcing... uhh.... wait... lightsourcing? How do I do that again?

Yup, something's definitely missing. :-)

It turns out that backface removal, lightsourcing, and a whole mess of other 3D-related issues often stem down to one small, yet very important math concept...

The normal.

What the Heck's a "Normal"?

The normal is just the name of the vector that's perpendicular to a plane. It's as simple as that (actually, I should be using the word "orthogonal", since that's the real name for perpendicular in 3D, but you get the idea). That's all it is. Every 3D plane in space has a normal; it's just the line that sticks straight out of that plane.

So what's so useful about normals? Well, if we have a 3D surface (like a polygon face), the normal tells us where the polygon is facing... it's the line that the polygon is "looking at", and that has a LOT of uses.

For one, backface removal. You only want to see a polygon face (like on a cube) when the surface is facing toward you. If it's facing away from you, you shouldn't see it (unless you want paper-thin objects). So the normal is very useful here.

And lightsourcing is entirely about normals. If you take the angle between the normal of a surface and the vector of surface to the lightsource, you can find out how much it's facing that lightsource and can use that for brightness. We'll be using this fact a lot with Lambert, Gouraud, and Phong shading, as well as Environment Mapping.

There are also other nice thing normals are used for, like calculating BSP trees and such. The list goes on and on...

But I'm probably overwhelming you with all this. Let's take it one step at a time, and all the rest of the pieces will face into place later. Don't worry if you're confused for the moment... it'll click soon enough. :)

Finding the Normal of a Plane

You've already dealt with a few normals - the axes. The Z axis sticks straight out of the XY plane, which means (tada!) that the Z axis is the normal of the XY plane. Likewise, the X axis is the normal of the YZ plane, and the Y axis is the normal of the ZX plane.

But what about arbitrary surfaces? Most of the time, with our 3D objects, we won't know where they're facing. They won't be on the axes most of the time, that much is for certain. So what do we do to find these special vectors?

The Dot and Cross Products

There are two very useful operations in linear algebra called the Dot Product, and the Cross Product. They're not really hard at all; the equations are pretty simple. But they come in very handy, as you'll soon see. Like the Trig identities, these are two of the most important things you'll ever use in 3D.

The Dot Product is just a value (or "scalar", in linear algebra terms). It's a function of two vectors, and usually denoted with a "." character. If we have two vectors A and B,

A.B = (Ax * Bx) + (Ay * By) + (Az * Bz)

That's it. Just multiply the XYZ parts together of each vector, add them up, and the resulting number is your dot product. What's it for? We'll see soon enough...

Now the Cross Product is a little more complicated of an equation. Like the Dot Product, it's a function of two vectors. But unlike the Dot Product, the result is not a scalar value.... it's another vector. If we have our A and B vectors, and C is the cross product (denoted A x B),

C = A x B

Cx = (Ay * Bz) - (By * Az)
Cy = (Az * Bx) - (Bz * Ax)
Cz = (Ax * By) - (Bx * Ay)

That's how we get each of the XYZ components of the cross product vector. Well what's C after we do this? A very nice thing... it's the vector that's ORTHOGONAL to A and B.

Yup, the Cross Product is our normal! :-)

Sure enough, if you check these equations against some normals we know, like the axes mentioned above, it turns out that

(1,0,0) x (0,1,0) = (0,0,1)     Z axis is orthogonal to the X and Y axes.
(0,1,0) x (0,0,1) = (1,0,0)     X axis is orthogonal to the Y and Z axes.
(0,0,1) x (1,0,0) = (0,1,0)     Take a wild guess. :-)

Now, we can't necessarily use this directly with our polygons. I mean, with our polys all we have is a set of vertices (each 3 for a triangle, 4 for a quadrilateral, whatever). We don't have two vectors. So we need to find two vectors in our poly that we can shove into this cross product equation, and find our normal.

How to do that? Not too hard, really. We can form two vectors from any three points in a poly. Say we have a quadrilateral polygon...

P2
  .         P1
          .



   .
   P3         . P4

Okay, all we need to do is get two tail-to-tail vectors from the poly. Solution? Simple, just pick a point, and use the vectors to the two points "connected" to it along the edges...

P2
  .___ A    P1
      ----.
           \
            \ B
             \
    .         \
    P3         . P4

Be warned, though.... the cross product function is NOT commutative. That is, A x B is NOT the same as B x A. As a matter of fact, B x A is the exact OPPOSITE vector of A x B.... it's the same line, just pointing in the other direction! :)

How to know which one to use as A and which as B? It depends on what kind of objects you're using. If you're importing from a modeler of sorts, most modelers either order the vertices a certain way or have some kind of field telling you which way the normal is. Then you'll know which vector is supposed to be first, so your normal is in the right direction.

Otherwise, if you're making your objects manually, you'll have to be a little more innovative. Many people like to create their faces so the vertices go in either a consistent clockwise or counter-clockwise order. Then you start at a consistent point in the polygon (like the first vertex), and you know which point goes with which vector.

It's really a matter of taste, but whatever you do, you should be consistent. Manually correcting normals that go wrong is a real pain in the rear, so getting the system down right the first time will help you a lot in the long run.

(BTW... in the above ASCII picture, the order that A and B are in will result in a normal that goes up, towards where the "P1" label is).

Now to get nice, accurate normals, we don't want the poly's location in space to have any effect on it... true "vectors" aren't points, they're rays going from the origin to a point. Well, P1 probably isn't going to be at (0,0,0). So for the cross product we need to calculate the vertices as if it were. This is just done by translating the points, subtracting P1 from both the P2 (for vector A) and from P4 (for vector B)...

A = (P2 - P1)
B = (P4 - P1)

Bam, now we just shove A and B into the cross product formula, and out comes our normal. Almost.

(Don't you just LOVE these "almosts" and "not quites"? :-)

Size Matters

Only one more thing we have to do to the normal to get it exactly the way we want it. We need to scale it down (or up), so that the vector has an exact length of 1. Why 1? Because having normals of length 1 is a really nice thing as far as calculation is concerned. It's mainly for the "angle between" equation we need for lightsourcing. I'll get to all that in a little bit, but for now, just trust me.... we want it one unit in length. :)

Doing that isn't really difficult... we just use the distance formula. From algebra you probably remember that in 2D, the distance between any two points is

length = sqrt( (x2-x1)^2 + (y2-y1)^2 )

That gives us the distance, or length, of that line segment. The same thing applies in 3D, by adding the Z component...

length = sqrt( (x2-x1)^2 + (y2-y1)^2 + (z2-z1)^2 )

Well a vector has just one point... the other point is at the origin, so if we want to find the length of our normal, we just set point 1 to (0,0,0), and

length = sqrt( x^2 + y^2 + z^2 )

Odds are, when you pump in your normal's values you got from the cross product, the length is NOT going to be equal to 1. It could be 0.2, it could be 10.583, it could be three-thousand-something. Anything. Well since all we care about is direction, not length, we can divide every XYZ component in the normal by its length, and the new length will become 1.

As an example, say our normal was (3,6,2). The length would be

length = sqrt( 3^2 + 6^2 + 2^2 ) = sqrt(9+36+4) = sqrt(49) = 7

So if we divide each component by 7, our final, scaled normal would be

(3/7, 6/7, 2/7)

Now as you can see, if all our normals are going to be length 1, then we need to use decimal places.... no component is ever going to be above 1 in size. But using floating point is incredibly slow, and pure integers don't allow for decimal places. The solution? Fixed point.

A Sidetrack on Fixed Point

Fixed point is an easy way to represent non-integer numbers with only integers in the processor. It's done by taking a certain number of bits in a register, and dedicating them to decimal places instead of integer values. Like if we have a 16-bit word, we can do 8.8 fixed point by using the upper 8 bits as the "whole" portion of the number, and the lower 8 bits as the "fractional" portion.

Examples of 8.8 fixed point....

1.0   =  0100h
1.5   =  0180h
0.25  =  0040h
3.75  =  03C0h
5.125 =  0520h

...and so on. All we're doing is using the high byte as the whole, and the low byte as the precision. How precise? Well since we have 8 bits in the fraction, it means we can go down to 1/256 for a fractional value. The more the fractional bits you use, the more accurate your decimal places can be... but the fewer number of whole-number bits you have left (so your value can't go up as high).

Sure enough, you're not limited to equal splits. With 16 bits you can do things like 15.1 fixed point (which only goes down to 0.5 for decimal units but allows numbers up to 32767), or you can do 1.15, which can only have a whole number of 0 or 1, but goes down to 1/32768 of decimal accuracy. You choose what works well for your system.

(Incidentally, since I code 32-bit mostly these days, I use 16.16 fixed point for pretty much everything 3D-wise. It's accurate enough in decimal places, yet has wholes up to 64k which is a nice range).

To sum up, fixed point is just treating integers as fractional numbers by working with the numbers a few powers of 2 above what the number actually means. In 8.8, 0100h (256) means 1, 512 means 2, 768 means 3, etc... you're just scaling the operations up a bit so you can stick with integer operations.

Adding and subtracting fixed point is just like regular integer add and sub. You don't have to do anything special...

1.5  + 1.5  = 3.0     0180h + 0180h = 0300h
2.75 - 2.25 = 0.5     02C0h - 0240h = 0080h

...and so on. On the other hand, multiplication and division have to be adjusted by the number of places in your precision, since the resulting number would be too high for multiply, and too low for divide...

1.5  * 3.0  = 4.5     0180h * 0300h = 048000h
                      NOPE!  We have to divide by 100h (8 bits precision).
                      0180h * 0300h = 048000h / 100h = 0480h   (correct)

Likewise, division needs to get multiplied by your precision. This must be done BEFORE you divide, or you'll end up losing all your decimal places.

7.5  / 2.5  = 3.0     0780h / 0280h = 0003h
                      WRONG! We need to multiply....
                      0780h * 0100h = 078000h / 0280h = 0300h  (correct)

Note that this means for multiply and divide that you'll need more space than just what's in your fixed point registers. Luckily multiply and divide on the Intel processors multiply into and from EDX:EAX, so you've got extra space already even if you're using assembly language. And the adjustment mul/divs are all powers of two, so you can use bit shifts instead (if you are using 386 regs, make sure you look up the SHLD and SHRD instructions... they come in real useful for this...)

Okay, enough of that sidetrack. That's the basics of fixed point. It's an excellent alternative to floating point, and it's the only way to get really good speed with 3D on an integer unit, since you can't use fast normals that aren't 1 unit in length.

That's all you need to know about finding normals! :-) Here's the quick summary. To get a normal from any polygon (with any number of vertices)

Choose three vertices from the poly that are connected by two edges. The middle vertex is the base of both your vectors, so translate all three points so that this base point is at the origin.
The two vectors are the two other points after translation. Choose your first and second vector in the right order so that the normal goes in the direction you want it, "in" or "out", so to speak. If your vertex ordering is consistent or you're importing from a modeler, this shouldn't be a big problem.
Take the cross product of the two vectors, in the right order.
Scale the cross product down so its length is equal to 1. This is your final normal for the poly (yay!) :)

You Want Me To Do All That REALTIME?!?

Heck no! :) Calculating normals for every surface every frame would be incredibly slow. Major MAJOR waste of time. But you don't have to worry about that, because you can precalculate your normals for the original object, and guess what?

If you rotate the normals by the same angles that you rotate the object, the normals will still be correct! :-)

So just generate your normals when you load up your object, or store them in the object file itself (if you have your own file format, this can be an easier option). As you rotate your object by rotating all the vertices, just treat the normals like regular vertices. So when rotating a cube, for example, you won't be rotating 8 points... you'll be rotating 14 points, i.e. the 8 vertices and the 6 normals.

In Our Next Episode

There are certainly other ways to deal with normals besides straight rotation and such, and I'll show you these methods as time goes on. We'll also be using these normals (and the thus-far-useless Dot Product) next time, when we start our polygon filling escapade! :) The next article will cover how to fill polygons with a flat color, and also how to lightsource that color using our normals, so don't throw this article away just yet... this info will become very useful very quickly.

In the meantime, the supplement will have example source that shows how to use normals for simple backface removal. I'll put a lot of comments in there so you can see what the normals are doing to make it possible. It's quite easy...

Anyway, take a look at that source (in Pascal and C, once again... BTW some people have asked me if I'll be doing more ASM source later on, and the answer is yes, I will be)... and play around with some of this stuff on your own! :) I realize there's not much to gain from this article by itself, but it'll give you time to get a very critical portion of your 3D system going. Even if it's still wireframe, it's a big step.

Until next time...

Kiwidog / Hornet , Terraformer

Discuss this article in the forums

Date this article was posted to GameDev.net: 10/19/1999
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General