This is the second part of a 3D thing I started a few weeks ago. Last time I talked, pretty much, only about the derivation of the rotation matrices for coordinate transformations. It was easy stuff...I hope you can agree with me on that if you read it. If you have not read then do so now. This time we are going to go into some of the more complicated areas of 3D. Once I cover that I will also discuss some optimizations for when you start to make your own 3D demo. It is still some easy stuff though. And just like last time there are more prerequisites. Although I am going to explain everything as thoroughly as possible it would still be good for you to read up on some of this. So here is what you need to know and what we are going to go over:

1.) Vectors - very important for what we are going to be discussing. I could write an entire tutorial solely on vectors but I am going to kind of limit it to a little less. I will give you a brief introduction so that you can be brought up to the same level that we will be working on. I am also going to discuss some equations you need to know as well as the derivation of those formulas.

2.) Trigonometry - yes, once again this has come up. You will need to know it. If you have not already read my Introduction to Trigonometry. It is not all that good but I still plan on writing another one.

3.) A good amount of Algebra - this will come up all the time. One of the, if not the ,most important things to get a good grasp of. We used quite a bit of Algebra in my other tutorials but this one will be even more so.

4.) A good imagination - seriously. We are going to be diving into somewhat abstract areas that are going to require some thinking.

And I think that is about it. Not very much this time but those are some pretty serious things for you to know.

The first thing I am going to talk about is deriving the perspective equations so that your 3d stuff really does look 3d. From the last tutorial you learned how to stick a point out anywhere in space and then rotate around all three axes. Well an (x, y, z) graph has no sense of perception. Meaning wherever you put a point that is where it is. In real life however as things move farther away that get closer and closer to the x- and y-axis. Thats called perception. We need to find some way to translate those points on all three axes (x,y,z) onto a two-dimensional surface, your computer screen. First look at this picture. There is a lot of information in it but I'll break it down in a second:



Now imagine that your eye is where the peak of the sideways triangle looking to the right. Your computer screen is the first horizontal line to the right at distance of "d" and 3d space is behind the screen. The z-coordinate increases as it goes away from you and decreases as it comes towards you. Since I can only show you stuff in 2d I had to leave out the x-coordinate for now. This is a side view of everything. Now lets say you have a point at the top-right hand corner. That is its actually position on a 3d graph. However there is no "depth" in your computer screen so we need to find where that point would be (proportional) if its z-coordinate was zero (literally on the screen).

Well first to do this I am going to draw you a new picture with only the information you need to know:



Not really all that big of a difference. Now keep in mind that "Triangle B" is the entire triangle, which is "Triangle A" and the quadrilateral. Let's talk about what variables we know from that picture. We definitely know "y" and "z" because that is the points position. The variable "d" is just a distance that you can choose a value for. All it represents is the distance from your eye to the screen. Just mess with some numbers and see what you like best. The higher the number the less change you will see with the perspective and vice versa for when "d" is a small number.

So out of the four variables we know three of them. All we need to do is solve for y₁ and that would be the y-position of the point projected onto a 2d screen from a 3d position right? Well, first let's talk about the relationship between Triangle A and Triangle B. They are proportional . They're what? Proportional! They are both right triangles and they're hypotenuse's have the same slope therefore they are proportional. When you know that they are proportional you can make a few assumptions. Something like this:

  d       (d+z)
----  =  ------
 y1         y

First multiply both sides by 1/d



  1     (d+z)    1
----  = ----- * ---
 y1       y      d



-- Simplify a little



  1     (d+z)
----  = -----
 y1      y*d



-- Flip both sides of the equation by taking the inverse.



      y*d
y1 = -----
     (d+z)

      for (var i = 1; i <= numPoints; i++)
      {
            sinex = Math.sin (ax);
            cosinex = Math.cos (ax);
            siney = Math.sin (ay);
            cosiney = Math.cos (ay);
            sinez = Math.sin (az);
            cosinez = Math.cos (az);
            // and then the rest of the rotation script
      }

That is kind of unnecessary since the rotation angles are not going to be changing within the "for" loop. Even if you put sine and cosine part outside of the "for" loop it is not necessary. Just create a function to call every time you increment the angle that way you are not doing anything more than you have to:

      function sineCosine (ax, ay, az)
      {
            sinex = Math.sin (ax);
            cosinex = Math.cos (ax);
            siney = Math.sin (ay);
            cosiney = Math.cos (ay);
            sinez = Math.sin (az);
            cosinez = Math.cos (az);
      }

      sine = new Array ();
      cosine = new Array ();
      rad = Math.PI / 180;
      for (var a = 0; a <= 360; a++)
      {
             sine[a] = Math.sin (a * rad);
             cosine[a] = Math.cos (a * rad);
      }

      2p (rad) = 360 (deg)

      -- divide both sides by 2 --

                p (rad) = 180 (deg)

      -- if you divide both sides by 180 you can solve for
         one degree in terms of radians --

                p / 180 (rad) = 1 (deg)

      -- therefore one degree equals p divided by 180 --

So thats where I came up with "rad"...its used to translate from degrees to radians for the math objects. So to access the sines and cosines of your angles (ax, ay, and az) you will need something like this:

      sinex = sine[Math.round (ax)];
      cosinex = cosine[Math.round (ax)];
      siney = sine[Math.round (ay)];
      cosiney = cosine[Math.round (ay)];
      sinez = sine[Math.round (az)];
      cosinez = cosine[Math.round (az)];

I had to add in that Math.round () stuff because the array elements are integers. And even our look-up table could use some optimizations! I only talk about this because two arrays of 360 elements each is quite a bit of information for a 206k web plug-in to handle...in other words it could slow down everything. If you are dealing with a more powerful programming language this next part is pretty much irrelevant.

First of all let's remember some trigonometric identities. The cofunction identities to be exact. They are:

       sin q = cos (90 - q)
       cos q = sin (90 - q)

And let's talk about why those are the way they are. Do you know what a sine and cosine curve looks like? Here is a quick ASCII picture I made:

Sine curve:  y = sin (x) in degrees:


      |    ,;'';
      |  .'     '.
      | /         \
      |/___________\______________
      |             \          /
      |              \        /
      |               *      *
      |                 ".."

-- Description:  this graph only shows one period of the curve.  A period
   is the amount of range that the curve needs to make one full curve.
   Everything else are just duplications that slide down the x-axis.
   The curve starts at (0,0) goes up to a peak at (90,1), back down to
   intercept the x-axis at (180,0), down more to the lowest part at
   (270,-1), and finally back up to intercept the x-axis at (360,0).


Cosine curve:  y = cos (x) in degrees:


      |';                   ;'
      |  '.               .'
      |    \             /
      |_____\___________/_____
      |      \         /
      |       \       /
      |        *     *
      |         ".."

-- Description:  this graph also only shows one period of the curve.
   The curve starts at (0,1), goes down to intercept the x-axis at (90,0),
   goes down further to its lowest point at (180,-1), turns back up and
   intercepts the x-axis at (270,0), and finally ends at (360,1).

      cosine = new Array ();
      rad = Math.PI / 180;
      for (var a = 0; a <= 360; a++)
      {
            cosine[a] = Math.cos (a * rad);
      }

      sinex = cosine[90 - Math.round (ax)];
      cosinex = cosine[Math.round (ax)];
      siney = cosine[90 - Math.round (ay)];
      cosiney = cosine[Math.round (ay)];
      sinez = cosine[90 - Math.round (az)];
      cosinez = cosine[Math.round (az)];

      sin (-q) = -sin q      csc (-q) = -csc q
      cos (-q) = cos q       sec (-q) = sec q
      tan (-q) = -tan q      cot (-q) = -cot q

      sinex = cosine[Math.abs (90 - Math.round (ax))];
      cosinex = cosine[Math.round (ax)];
      siney = cosine[Math.abs (90 - Math.round (ay))];
      cosiney = cosine[Math.round (ay)];
      sinez = cosine[Math.abs (90 - Math.round (az))];
      cosinez = cosine[Math.round (az)];

      | 1  0  0  Tx |
      | 0  1  0  Ty |
      | 0  0  1  Tz |
      | 0  0  0  1  |

Uh-oh! There is something tricky going on in there! Yes that is a 4x4 matrix...so theoritically we are dealing with the 4th dimension...scary eh? It is very simple to understand though. There is no way for me to graphically show you, and is near impossible to visualize but yet it is still easy to understand...for now. And no! The 4th dimension is not time (in this instance...I am not sure in other applications).

We now have a quadruple pair (I guess that is what it would be called...do not quote me though)...it would look like (x, y, z, w) where "w" is the coordinate in the 4th dimension. Whats great about "w" is that it is always going to be one for us...always, always, always. Remember that because thats what makes the 4th dimension so easy to deal with. The reason we add this in the matrix is because we need to have it so that when mulitplied by the matrix it will only add numbers to the matrix it is being multiplied by. If you mulitply that (above) out with this...:

      | x |
      | y |
      | z |
      | w | <- equal to one

...you will be merely adding on Tx, Ty, and Tz. Something crucial to remember is that those values are increments. Meaning if you set Tx to one it will slide the point along the x-axis continually because you keep adding one to the point's position.

You can also use a matrix to scale a point:

      | Sx  0  0  0 |
      |  0 Sy  0  0 |
      |  0  0 Sz  0 |
      |  0  0  0  1 |

You do not really need the fourth column and row with that matrix though.

Alright, I think I have outlined everything for movie coordinates around in 3D. We did rotations, translations, and scalings. Now I am going to go back to optimizations. This will be geared more towards the "advanced" user even though anybody can do this. I say "advanced" (and I use that term loosely) because there are not too many pratical uses for it...it will also take more thought than anything else we have covered. This next part I'm writing is for optimizations having to do with polygon fills. If you plan on ever getting into C/C++ (or you might already) then this next part is a necessity when dealing with 3D. Something we need to talk about first is vectors. It turned out that my "short" tutorial on vectors that I was planning on including in this tutorial become very large. I went ahead and put it in a seperate tutorial. You can read it here. Even if you do not plan on reading this solid polygon stuff I highly suggest you read the tutorial about vectors.

Ok so you have read about vectors (please do before reading this) and you have most likely already figured out how to fill three points with a triangle. Now we are going to talk about removing hidden polygons. This process of removing polgons that cannot be seen is called geometry culling. There are many algorithms out there but we are going to only discuss a few...the most profitable in Flash.

First let me say a few things. When building something like this you need to think it out before you start actually working on it. I'm not going to discuss the way your script should be structured (I'm not very good at that stuff anyway), but its something that should be well thought out. I doubt I am using good programming aesthics, but I put my polygon fill script in the right triangle I use to fill three points and then in an "initialize" script I duplicate the triangle and pass along the three points it is supposed to fill. I then have a main script transforming the points whilst the triangle fill is grabbing those points and filling them out.

Ok back to optimizations. Like I said before we are going to be discussing geometry culling...if you cant see the polygon why render it and waste CPU power? This is a big thing in games. There are tons of algorithms with big names attached to them: view frustum culling, back-face culling, occlusion culling, contribution culling etc. Everything from something as simple as detecting whether a polygon is in your field of view to something as hard as detecting whether some polygons are blocking others. I imagine that most 3D engines used for games (do not quote me on this) use quite a few culling algoritms to minimize the number of polygons. Kind of like a filter. That will be somewhat like what we are going to do. But, for Flash's sake we are going to talk about the most basic kind.

Let's do the easiest first...and I mean easy: view frustum culling. All it says is that if the polygon is not in your field of view then do not worry about rendering it. In more powerful computer languages you would test the polygon on six planes that made up your field of view: a front, back, left, right, top and bottom plane. You would test it to see if the polygon was inside those planes or not...if it is render...if it is not don't render. However Flash makes this much easier. All you need to do is see if your polygon is on the stage or not. The simplest way to do that would be to make a large movie clip that takes up your entire stage exactly. Then you simply check for a hitTest () on the polygon and the big movie clip...if there is a hit render, if there is not a hit do not render. However that will only test the left, right, top, and bottom planes. To test the back plane you check if your polygon has gone behind you. We already discussed that though. Testing the front plane has another name attached to it so I will explain that seperately.

So first put your polygons through that filter where you test if its in your field of view. The next easiest is called contribution culling. If the polygon is too far and you can't see it dont even bother with it. Its more like common sense if you ask me. For this set a variable for the maximum distance that you want the user to be able to see. Say, like one thousand. Then do a simple "if" statement checking if the polygon goes greater than that. Something you will notice is that it looks a little weird because the polygon will just disappear. You may want to fade the polygon out first.

The hardest form of culling for us (and last on the list) is back-face culling. It works for enclosed objects and it says that if a polygon is facing away from you then do not render it. I touched on this subject in my first solid 3d file (ED. not available) but it should make more sense now if you read my vector tutorial.

To find out if a polygon is facing you or not you need to first find the normal vector of the plane which the polygon sits on. To find a normal vector you need two other vectors on the plane. You can do this by using the sides of the polygon. Then by taking the cross product of the two vectors you can find the normal. Once you have your normal you want to find the angle that the normal makes with the "viewpoint" vector. A viewpoint vector is merely a vector going from your eye to the screen, perpendicular to the screen. Whats so great about the viewpoint vector is that its easy to find. Something like: (0,0,1) would work. Thats perpendicular to the screen right?

So you have the two vectors: a normal vector and a viewpoint vector. I said before that you need to find the angle between the two vectors. To do this you would use the dot product like I mentioned in my vector tutorial. Once you find the angle you see if it goes greater than 90 because that means it would be pointing the other way. Here is what some really basic code would look like (note: I am not following any kind of programming principles whatsoever...you will most likely not want to use this):

      // given points A, B, and C in clockwise order

      // vectors made up of the polygon's sides
      vec1 = new Array (null, B.x-A.x, B.y-A.y, B.z-A.z);
      vec2 = new Array (null, C.x-B.x, C.y-B.y, C.z-B.z);

      // find the normal vector with the cross product
      crossx = vec1[2]*vec2[3] - vec1[3]*vec2[2];
      crossy = vec1[3]*vec2[1] - vec1[1]*vec2[3];
      crossz = vec1[1]*vec2[2] - vec1[2]*vec2[1];
      normal = new Array (null, crossx, crossy, crossz);


      // view point vector
      viewVec = new Array (null, 0, 0, 1);

      // find the magnitudes of "normal" and "viewVec"
      len1 = Math.sqrt (normal[1]*normal[1] + normal[2]*normal[2] +
                                              normal[3]*normal[3]);
      len2 = Math.sqrt (viewVec[1]*viewVec[1] + viewVec[2]*viewVec[2] +
                                                viewVec[3]*viewVec[3]);

      // find the dot product of the two vectors "normal" and "viewVec"
      dot = normal[1]*viewVec[1] + normal[2]*viewVec[2] + normal[3]*viewVec[3];


      // find the angle between the two vectors
      cosTheta = dot / (len1 * len2);
      theta = Math.acos (cosTheta * (Math.PI / 180));

      // if theta is greater than ninety then dont worry about it
      if (theta > 90) {
            this._visible = false;
      } else {
            // polygon script
      }

      // given points A, B, and C in clockwise order

      // vectors made up of the polygon's sides
      vec1 = new Array (null, B.x-A.x, B.y-A.y);
      vec2 = new Array (null, C.x-B.x, C.y-B.y);

      // find only the z-component of the normal vector
      crossz = vec1[1]*vec2[2] - vec1[2]*vec2[1];

      // if crossz is greater than zero the polygon is facing away.
      if (crossz > 0) {
             this._visible = false;
      } else {
             // polygon script
      }

      // given points A, B, and C in clockwise order

      // vectors made up of the polygon's sides
      vec1 = new Array (null, B.x-A.x, B.y-A.y, B.z-A.z);
      vec2 = new Array (null, C.x-B.x, C.y-B.y, C.z-B.z);

      // find the normal vector with the cross product
      var crossx = vec1[2]*vec2[3] - vec1[3]*vec2[2];
      var crossy = vec1[3]*vec2[1] - vec1[1]*vec2[3];
      var crossz = vec1[1]*vec2[2] - vec1[2]*vec2[1];
      normal = new Array (null, crossx, crossy, crossz);


      // view point vector
      viewVec = new Array (null, 0, 0, 1);

      // find the magnitudes of "normal" and "viewVec"
      len = Math.sqrt (normal[1]*normal[1] + normal[2]*normal[2] +
                                             normal[3]*normal[3]);

      // find the angle between the two vectors
      cosTheta = crossz / len;

      /* If the cosine of theta goes less than 0 then the polygon is facing
         the other way.  The cosine of an angle greater than 90 and less
         than 270 is a negative number so you only need to test the ratio
         for its sign.  */
      if (cosTheta < 0) {
            this._visible = false;
      } else {
            // polygon script
      }

As you can see a little better. I was able to eliminate a sqrt () and an acos (), both very CPU demanding. It is still slow for Flash but that is as far as I have been able to optimize it (actually I still have one more that I'll go over at the end). I am open to suggestions though.

So thats back-face culling huh? Yep! We just covered some pretty serious subjects and it was pretty easy right? There is still one more thing and then you are finished. Lighting!

The way lights work (I'm sure you know this but I thought I should point it out anyway) is that as a flat surface faces a light more and more the intensity of the light increase, and as the surface starts to rotate away, the light because less. The sad thing about lights is that they are going to be CPU demanding. Calculating lights is pretty much the same as back-face culling except we are not going to be able to optimize it as much. This time instead of a "viewpoint" vector you are going to have a "lightVector" which will be the direction vector from the light to the polygon. After you have the "lightVector" you find the normal of the polygon and then find the cosine of the angle between the two vectors. There are two good things about finding the cosine of the angle: first it will keep you from using an inverted cosine which is slow, and it gives you the perfect values. For example, the polygon was facing directly at the light the intesity would be at its highest right? What would be the angle between the two vectors at that point? Zero degrees. What is the cosine of zero? One. And if the polygon started rotating away from the light the angle between the two vectors would start to increase to 90 right (I say 90 because anything greater than the light can't shine on)? Well what does the cosine of the angle go towards as the angle goes to 90? Zero. So when the maximum light should be shone the ratio is one and when the least amount of light should be shone the ratio is zero. This fits prefectly. All you need to do is multiply the ratio by the maximum amount of light there should be. After that you could even add in a value for an ambeince type effect. Here is some sample code:

      /* given points A, B, and C in clockwise order for the polygon
         and (Lx, Ly, Lz) for the coordinates of the light */

      // vectors made up of the polygon's sides
      vec1 = new Array (null, B.x-A.x, B.y-A.y, B.z-A.z);
      vec2 = new Array (null, C.x-B.x, C.y-B.y, C.z-B.z);

      // find the normal vector with the cross product
      var crossx = vec1[2]*vec2[3] - vec1[3]*vec2[2];
      var crossy = vec1[3]*vec2[1] - vec1[1]*vec2[3];
      var crossz = vec1[1]*vec2[2] - vec1[2]*vec2[1];
      normal = new Array (null, crossx, crossy, crossz);

      // find the center of the polygon
      center = new Array ();
      center[1] = (A.x + B.x + C.x) / 3;
      center[2] = (A.y + B.y + C.y) / 3;
      cemter[3] = (A.z + B.z + C.z) / 3;

      // direction vector from the light to the polygon
      dirVec = new Array (null, center[1]-Lx, center[2]-Ly, center[3]-Lz;

      // find the magnitudes of "normal" and "dirVec"
      len1 = Math.sqrt (normal[1]*normal[1] + normal[2]*normal[2] +
                                              normal[3]*normal[3]);
      len2 = Math.sqrt (dirVec[1]*dirVec[1] + dirVec[2]*dirVec[2] +
                                              dirVec[3]*dirVec[3]);

      // find the dot product of the two vectors "normal" and "direVec"
      dot = normal[1]*dirVec[1] + normal[2]*dirVec[2] + normal[3]*dirVec[3];

      // find the cosine of the angle between the two vectors
      cosTheta = dot / (len1 * len2);

      // Find the intesity of the light. Both the variables "amb" and
         "maxLight" would be defined beforehand.
      intesity = amb + (cosTheta * maxLight);

And as you can see from that its pretty slow. You have two square roots, quite a few divides, and it is just overall messy. I'm going to present an optimization for both lighting and culling in a minute but I want to make sure you understand this. You may want to read over it again. If there is still something really unclear email me and I will add in some more to help clarify things.

More optimization

So we have discussed some pretty interesting stuff in the field of 3D: transformations, translations, optimizations, culling, and lighting. The most CPU demanding of all of them is the culling and lighting. Now to present an optimization for this...its the last thing in the tutorial...I promise.

The thing which takes the most CPU power and which takes place in both culling and lighting is finding the normal vector and the length of that vector. An alternative would be to find the normal vector and length when the points are set up initially and then just rotate the normal vector along with the points. I cannot really give an example script so you are going to have to pay attention closely.

In the script that all your points are laid out find the components of the normal vector afterwards (crossx, crossy, crossz). In the same script you need to find its length also to speed things up too. Once you have all the components of the vector rotate it around like all your other points and then when you are determining lighting or culling you can use the rotated normal. That gets rid of finding a normal and one sqrt ().

"Why I Write"

Ok...tons of information has been covered this time! Probably too much for you to take in all at once. I know that there is no way I could get this in one sitting but I'm kind of slow anyway. And if you have read all of this (good for you...seriously) then you are probably wondering why I wrote this in the first place since most of this stuff is out of Flash's capabilities in a practical manner. Yes, in fact most of this is out of Flash's reach but also most of this can be used for other things. What if you were not interested in solid objects but more like objects sitting in space where you can walk around them. Even though they would be static images you could use many of these techniques and "concepts" (I really don't like using that word) to improve your file. I am also doing this because it will help you to just know it. Even if you will never use it its good practice and will help you think a little differently (not a lot...I don't think I am capable of encouraging that type of movement) and perhaps approach problems differently. I also have a few other "secret" reasons as to why I write this kitsch (I have low self esteem) and maybe some day I will tell why (as if anyone cares).

This may be my last tutorial on 3D for awhile because there are some any other things I want to cover. If I do end up making another it will be a "quick and dirty" tutorial on movement in 3D, collision respones, and I will most likely lay down some of the basics to creating a "3D World" in Flash kind of like this.

I wish I had more time for this kind of stuff. Thanks for reading.

- Brandon Williams