Camera Implementation In 3D Engines,  Ohad Eder Pressman
                                         aka Kombat/iMMoRTaLS


   Heyho,

      Must be lots of you out there just dying to put a camera in there 3D
   engine, well you won't believe how simple it is :)

      Till today, U probably used 3 matrices or 1 for rotating an object, if
   you had 3 matrices you had one for rotating the object around the x-axis,
   one for the y-axis and one for the z-axis. Now, we aren't exactly talking
   about the rotation of an object, but about the rotation of a whole
   3D world or a 3D scene. This means we need to apply some transformation
   on all of our vertices.
   What we are going to do, is calculate a 3x3 matrix that will represent
   the rotation of the whole 3D world around our camera.

      If you look at your world and at your camera, you can figure out that
   there are 2 steps in this transformation, because we are not only rotating
   all our scene, we are rotation all our scene AROUND some point, around the
   camera source point.

   Lets look at the primitive definition of a camera :

   1. An x,y,z component representing the Source of the camera.
   2. An x,y,z component representing the Destination of the camera.
   3. A Roll value which tells us the angle around the camera's Z axis.

   All this information comes in the .3DS format, and I suggest reviewing
   3DSRDR by Jare. There is another component called the FOV (Field Of
   View), which controls the perspective of the camera, this doesn't
   interest us at the moment.


   Lets take a little look at some scene, from the top :

	TOP :

	Z-Axis
	/\
	|
	|              Camera Destination
	|            *
        |           /
        |          /
        |         /
        |        /
        |       /
        |      /
	|     *
	|       Camera Source
	|
	|____________________________> X-Axis
        0

      from the two point we can create a vector which will represent the
   direction of our camera in our 3D world.


      In all following code I will u simplified variable names, except for
   the full code enclosed at the end.


   First we create this direction vector :

      N.x = CameraTarget.x - CameraSource.x;
      N.y = CameraTarget.y - CameraSource.y;
      N.z = CameraTarget.z - CameraSource.z;


   Now, we need to normalize this vector :

      L = sqrt( N.x*N.x + N.y*N.y + N.z*N.z );
      N.x /= L;
      N.y /= L;
      N.z /= L;

      (Basically you should check if the vector length is 0 so that u don't
       fdiv by zero, but 3dstudio speaking the chances are 0%)


      What we have now is the N vector representing the direction of the
   camera, we need another vector, that will represent where our 'up' is,
   this vector depends on the Roll of the camera. Take your head for instance,
   your up vector currently points to the sky or the ceiling...
   If you rotate your head 90 degrees to the right, your up is no longer the
   ceilings but the door or the wall.

   Lets define this up vector :

      UP.x = sin(Roll);
      Up.y = 0;
      Up.z = -Cos(Roll);

   The following steps are pure mathematics, so try and keep up :

     1. Define 2 new vectors, U and V.

     2. U = Cross Product of N and Up. (U = N x Up)

     3. Normalize U.

     4. V = Cross Product of U and N. (V = U x N)

     5. Normalize V.

     6. Build your matrix from the three vectors : -U, V, N.

   Steps 1 through 5 are purly mathematical, I showed how to normalize a
   vector be4, if you don't know how to calculate the cross production of
   two vectors, this is the way :

   [A cross of two vectors gives a new vector, that its direction is an onyx,
   (normal) to the plane that the two vectors represent]

      A = B Cross C (A = B x C) <=>

      A.x = B.y * C.z - B.z * C.y;
      A.y = B.z * C.x - B.x * C.z;
      A.z = B.x * C.y - B.y * C.x;

   Step 6 is the final step in which you build your camera matrix,

   Let us define our matrix, cmatrix[3][3] (OTM :)


      cmatrix[0][0] = -U.x;
      cmatrix[1][0] =  V.x;
      cmatrix[2][0] =  N.x;

      cmatrix[0][1] = -U.y;
      cmatrix[1][1] =  V.y;
      cmatrix[2][1] =  N.y;

      cmatrix[0][2] = -U.z;
      cmatrix[1][2] =  V.z;
      cmatrix[2][2] =  N.z;


   Now that we have our matrix, well, we have a matrix, good for us.

   Lets take a basic loop of an engine :

     1. Hey I'm the begining of the loop.

     2. Rotate Objects, Move Objects, etc'.
    
     3. Perform Camera Transformation.

     4. Apply Perspective on Vertices.

     5. Draw your scene.

     6. Go back to 1 untill you get bored...

   What we are dealing with is step 3, which can be broke down to 2
   sub-steps :

     A. Centering our world around our camera. We need to rotate our world
        around the camera, so first we must center the world around the
        Camera_Source Point.

     B. Transforming our would according to the camera. That's just
        multiplying all them damn vertices by that damn camera matrix we
        just calculated.

	Here's some code to feast on :

           Vector U, V;

           for (i=0;i<NumVertices;i++)
           {
              // Put New vertex in U
              U.x = Vertices[i].x - Camera_Source.x;
              U.y = Vertices[i].y - Camera_Source.y;
              U.z = Vertices[i].z - Camera_Source.z;

              // Transform Vertex into V, simple Vector*Matrix multiplication
              V.x = cmatrix[0][0]*N.x+cmatrix[0][1]*N.y+cmatrix[0][2]*N.z;
              V.y = cmatrix[1][0]*N.x+cmatrix[1][1]*N.y+cmatrix[1][2]*N.z;
              V.z = cmatrix[2][0]*N.x+cmatrix[2][1]*N.y+cmatrix[2][2]*N.z;

              // V now holds our new Vretex, the only thing left now is some
              // Perspective... (X/Z, Y/Z) or some FOV arctans
           }

	Here's the 'full' source for the camera calculation function :

           void Camera_Matrix(Camera *Camera1)
           {
              Vector Up, N, U, V;

              Up.x = sin(Camera1->Roll);
              Up.y = 0;
              Up.z = -cos(Camera1->Roll);

              Vec_Sub(&Camera1->Target,&Camera1->Source,&N);

              VNorm(&N);

              Cross(&N,&Up,&U);

              VNorm(&U);

              Cross(&U,&N,&V);

              VNorm(&V);

              Camera1->Mat.BuildMatrix(-U.x,-U.y,-U.z,
                                       V.x,V.y,V.z,
                                       N.x,N.y,N.z);
           }



	I liked writing this, ofcourse there are many other aspects of Keyframing
	3D-Engines like splines, quaternions, hirarchey, etc', but I really don't
	have time for all that at the moment... :)

   if you get any problems with the source, or if you got it working,
   or if you want me to write about anything else concerning 3D, or if you
   want to tell me about your darkest dreams (no 10x)

   Contacts :

         kombat@netvision.net.il    (Faster)
         ohadp@shani.net            (Slower)


   You can check my groups homepage at :

         http://www.geocities.com/SiliconValley/Heights/4443


   * All code in this article is written very simply and 100% Non-Optimized,
     Your most likely to write all mathematical functions in 100% Assembler
     and use that damn FPU, A 1 cycle fmul worths something these days...



   thanks to all the dudes who ever tought me something, you know who you
   are...



                                                     Kombat/iMMoRTaLS, 1997