/*********************************************************************************************/
/*                                                                                           */
/*  Java 3D Engine Basics Tutorials - Tut x.x                                                */
/*  Auth: bkenwright@xbdev.net                                                               */
/*                                                                                           */
/*                                                                                           */
/*********************************************************************************************/

import java.awt.image.*;
import java.awt.*;
import java.applet.*;


/*********************************************************************************************/
/*                                                                                           */
/*  class Vector3                                                                            */
/*  Its much more tidier in the long run, if we represent our x,y and z data values as       */
/*  a single class - then when we need to add or subract or even do a dot product operation  */
/*  on them we can just do a + b or a - b...                                                 */
/*                                                                                           */
/*********************************************************************************************/

class Vector3
{
   public float m_x, m_y, m_z;
   
   public Vector3(){}
   public Vector3(float x, float y, float z)
	 { m_x=x;  m_y=y;  m_z=z; };
   public Vector3(double x, double y, double z)
	 { m_x=(float)x;  m_y=(float)y;  m_z=(float)z; }
	 
	 
   static public Vector3 add(Vector3 a, Vector3 b)
   {
      Vector3 result = new Vector3();
      result.m_x = a.m_x + b.m_x;
      result.m_y = a.m_y + b.m_y;
      result.m_z = a.m_z + b.m_z;
      return result;
   }//End add(..)
   
   static public Vector3 subtract(Vector3 a, Vector3 b)
   {
      Vector3 result = new Vector3();
      result.m_x = a.m_x - b.m_x;
      result.m_y = a.m_y - b.m_y;
      result.m_z = a.m_z - b.m_z;
      return result;
   }//End add(..)
   
   static public Vector3 invert(Vector3 a)
   {
      Vector3 result = new Vector3();
      result.m_x = -a.m_x;
      result.m_y = -a.m_y;
      result.m_z = -a.m_z;
      return result;
   }// End invert(..)
   
   static public float dot(Vector3 a, Vector3 b)
   {
      float result = a.m_x*b.m_x  +  a.m_y*b.m_y  +  a.m_z*b.m_z;
      return result;
   }// End dot(..)
   
   static public Vector3 cross(Vector3 a, Vector3 b)
   {
      Vector3 result = new Vector3();
      result.m_x  =   a.m_y * b.m_z  -  a.m_z * b.m_y;
      result.m_y  =  -a.m_x * b.m_z  +  a.m_z * b.m_x;
      result.m_z  =   a.m_x * b.m_z  -  a.m_z * b.m_x;
      return result;
   }// End cross(..)
   
   static public Vector3 scale(Vector3 a, float f)
   {
      Vector3 result = new Vector3();
      result.m_x = a.m_x * f;
      result.m_y = a.m_y * f;
      result.m_z = a.m_z * f;
      return result;
   }// End scale(..)
   
   static public float length(Vector3 a)
   {
      float result = a.m_x*a.m_x + a.m_y*a.m_y + a.m_z*a.m_z;
      result = (float)Math.sqrt(result);
      return result;
   }// End length(..)
   
   static public Vector3 normalize(Vector3 a)
   {
      Vector3 result = new Vector3();
      float len = length(a);
      result.m_x =  a.m_x / len;
      result.m_y =  a.m_y / len;
      result.m_z =  a.m_z / len;
      return result;
   }// End normalize(..)
   
   static public Vector3 rotatey(Vector3 a, float angle)
   {
      float cosA = (float)Math.cos(angle);
      float sinA = (float)Math.sin(angle);
      
      Vector3 result = new Vector3();
      result.m_x =  a.m_x*cosA + a.m_z*sinA;
      result.m_y =  a.m_y;
      result.m_z = -a.m_x*sinA + a.m_z*cosA;
      return result;
   }// End rotatey(..)
   
}//End Vector3

/*********************************************************************************************/
/*                                                                                           */
/*  class Triangle                                                                           */
/*  We need a way of representing our triangles...so that we can have a number of them       */
/*  and not have to deal with large numbers of arrays of values and things.  By putting      */
/*  them in a class each triangle is all nice and tidy.                                      */
/*                                                                                           */
/*********************************************************************************************/

class Triangle
{
   float x0, y0, z0;
   float x1, y1, z1;
   float x2, y2, z2;
   Color c;
   
   // Average z
   float avg_z;
   
   // Transformed coords
   float tx0, ty0, tz0;
   float tx1, ty1, tz1;
   float tx2, ty2, tz2;
   Color tc;
   
   // Triangle Normal
   float tnx, tny, tnz;
   
   // Cull our triangle if we can't see it
   boolean bCull;
   
   public Triangle(){} // default constructor
   public Triangle( float x0_, float y0_, float z0_,
                    float x1_, float y1_, float z1_,
                    float x2_, float y2_, float z2_,
                    Color c_  )
   {
       tx0=x0=x0_; ty0=y0=y0_; tz0=z0=z0_;
       tx1=x1=x1_; ty1=y1=y1_; tz1=z1=z1_;
       tx2=x2=x2_; ty2=y2=y2_; tz2=z2=z2_;
       tc = c = c_;
       bCull = false;
   }// End of Triangle(..) constructor
   
   public Triangle( Vector3 a, Vector3 b, Vector3 ccc, Color c_ )
   {
       tx0=x0=a.m_x; ty0=y0=a.m_y; tz0=z0=a.m_z;
       tx1=x1=b.m_x; ty1=y1=b.m_y; tz1=z1=b.m_z;
       tx2=x2=ccc.m_x; ty2=y2=ccc.m_y; tz2=z2=ccc.m_z;
       tc = c = c_;
   }// End of Translate(..) constructor
  
   public void Translate( float x, float y, float z )
   {
   			tx0 += x;  ty0 += y;  tz0 += z;
   			tx1 += x;  ty1 += y;  tz1 += z;
   			tx2 += x;  ty2 += y;  tz2 += z;
   }// End of Translate(..)
   
   public void ResetCoords()
   {
     tx0=x0; ty0=y0; tz0=z0;
     tx1=x1; ty1=y1; tz1=z1;
     tx2=x2; ty2=y2; tz2=z2;
     bCull = false;
     
   }// End ResetCoords()
   
   public void RotateX( float angle )
   {
      float cosA = (float)Math.cos(angle);
      float sinA = (float)Math.sin(angle);
      
      float temp_x, temp_y, temp_z;
      
      temp_x =  tx0;
      temp_y =  ty0*cosA - tz0*sinA;
      temp_z =  ty0*sinA + tz0*cosA;
      tx0 = temp_x;  ty0 = temp_y;  tz0 = temp_z;
      
      temp_x =  tx1;
      temp_y =  ty1*cosA - tz1*sinA;
      temp_z =  ty1*sinA + tz1*cosA;
      tx1 = temp_x;  ty1 = temp_y;  tz1 = temp_z;
      
      temp_x =  tx2;
      temp_y =  ty2*cosA - tz2*sinA;
      temp_z =  ty2*sinA + tz2*cosA;
      tx2 = temp_x;  ty2 = temp_y;  tz2 = temp_z;
      
   }// End RotateX(..)
   
  public void RotateY( float angle )
   {
      float cosA = (float)Math.cos(angle);
      float sinA = (float)Math.sin(angle);
      
      float temp_x, temp_y, temp_z;
      
      temp_x =   tx0*cosA + tz0*sinA;
      temp_y =   ty0;
      temp_z =  -tx0*sinA + tz0*cosA;
      tx0 = temp_x;  ty0 = temp_y;  tz0 = temp_z;
      
      temp_x =   tx1*cosA + tz1*sinA;
      temp_y =   ty1;
      temp_z =  -tx1*sinA + tz1*cosA;
      tx1 = temp_x;  ty1 = temp_y;  tz1 = temp_z;
      
      temp_x =   tx2*cosA + tz2*sinA;
      temp_y =   ty2;
      temp_z =  -tx2*sinA + tz2*cosA;
      tx2 = temp_x;  ty2 = temp_y;  tz2 = temp_z;
			 
   }// End RotateY(..)
   
   public void RotateZ( float angle )
   {
      float cosA = (float)Math.cos(angle);
      float sinA = (float)Math.sin(angle);
      
      float temp_x =  tx0*cosA - ty0*sinA;
      float temp_y =  tx0*sinA + ty0*cosA;
      float temp_z =  tz0;
      tx0 = temp_x;  ty0 = temp_y;  tz0 = temp_z;
      
      temp_x =  tx1*cosA - ty1*sinA;
      temp_y =  tx1*sinA + ty1*cosA;
      temp_z =  tz1;
      tx1 = temp_x;  ty1 = temp_y;  tz1 = temp_z;
      
      temp_x =  tx2*cosA - ty2*sinA;
      temp_y =  tx2*sinA + ty2*cosA;
      temp_z =  tz2;
      tx2 = temp_x;  ty2 = temp_y;  tz2 = temp_z;
   }// End RotateZ(..)
   
   public void CalculateNormal()
   {
      // First we need to find the direction of our triangle
      // using the cross product :)
      
      // Lets calculate the two direction vectors
      float vx0, vy0, vz0;
      float vx1, vy1, vz1;
      
      vx0 = tx2 - tx0;
      vy0 = ty2 - ty0;
      vz0 = tz2 - tz0;
    
      vx1 = tx1 - tx0;
      vy1 = ty1 - ty0;
      vz1 = tz1 - tz0;
      
      // Do the cross product
      float nx, ny, nz;
      nx =  vy0*vz1 - vz0*vy1;
      ny = -vx0*vz1 + vz0*vx1;
      nz =  vx0*vy1 - vy0*vx1;
      
      // And we normalize it so its magnitude is 1
      float length = nx*nx + ny*ny + nz*nz;
			length = (float)Math.sqrt(length);
			
			nx /= length;
			ny /= length;
			nz /= length;
      
			tnx = nx;
			tny = ny;
			tnz = nz;
   }// End CalculateNormal(..)
   
   
}// End of class triangle



/*********************************************************************************************/
/*                                                                                           */
/*  Program Entry Point                                                                      */
/*                                                                                           */
/*********************************************************************************************/

public class camera extends Applet 
{
  Image myImage;
  Graphics offScreen;
  
  int mouse_x=0;
  int mouse_y=0;
  


  
  int m_NumTris = 12;
  Triangle[] m_tri;

  public void init() 
  {
  	 Dimension appletSize = this.getSize();
	   myImage = createImage(appletSize.width,appletSize.height);
   	 offScreen = myImage.getGraphics();
   	 
   	 m_tri = new Triangle[m_NumTris];
   	 // Front
   	 m_tri[0] = new Triangle(-1.0f, -1.0f, -1.0f,  -1.0f, 1.0f, -1.0f,  1.0f,  1.0f, -1.0f,  Color.red);
     m_tri[1] = new Triangle(-1.0f, -1.0f, -1.0f,   1.0f, 1.0f,-1.0f,   1.0f, -1.0f, -1.0f,  Color.red);
				
		 // Back
   	 m_tri[2] = new Triangle(-1.0f, -1.0f,  1.0f,  1.0f,  1.0f, 1.0f,  -1.0f, 1.0f,  1.0f,  Color.green);
     m_tri[3] = new Triangle(-1.0f, -1.0f,  1.0f,  1.0f, -1.0f, 1.0f,   1.0f, 1.0f,  1.0f,  Color.green);									 
   	 
   	 // Bottom
   	 m_tri[4] = new Triangle(-1.0f, -1.0f,  -1.0f,   1.0f, -1.0f, 1.0f,   -1.0f, -1.0f, 1.0f,   Color.blue);
     m_tri[5] = new Triangle(-1.0f, -1.0f,  -1.0f,   1.0f, -1.0f, -1.0f,   1.0f, -1.0f,  1.0f,  Color.blue);	
    
     // Top
     m_tri[6] = new Triangle(-1.0f,  1.0f,  -1.0f,  -1.0f, 1.0f, 1.0f,   1.0f,  1.0f, 1.0f,  Color.orange);
     m_tri[7] = new Triangle(-1.0f,  1.0f,  -1.0f,   1.0f, 1.0f,  1.0f,  1.0f, 1.0f, -1.0f,  Color.orange);
    
     // Left
     m_tri[8] = new Triangle(-1.0f, -1.0f,  -1.0f,   -1.0f,  1.0f, 1.0f,   -1.0f, 1.0f, -1.0f,  Color.yellow);
     m_tri[9] = new Triangle(-1.0f, -1.0f,  -1.0f,   -1.0f, -1.0f, 1.0f,   -1.0f, 1.0f,  1.0f,  Color.yellow);
    
     // Right
     m_tri[10] = new Triangle(1.0f, -1.0f,  -1.0f,   1.0f, 1.0f, -1.0f,   1.0f,  1.0f, 1.0f,  Color.pink);
     m_tri[11] = new Triangle(1.0f, -1.0f,  -1.0f,   1.0f, 1.0f,  1.0f,   1.0f, -1.0f, 1.0f,  Color.pink);
    
    
  }// End of init(..)

  
   // find the distance between a ray and a plane.
   public float distRayPlane(Vector3 vStart,
                             Vector3 vEnd,
                             Vector3 vnPlaneNormal,
                             Vector3 vPointOnPlane)
   {
      float cosAlpha;
      float deltaD;
      
      float planeD = Vector3.dot( vnPlaneNormal, vPointOnPlane );

      Vector3 vRayVector = Vector3.subtract(vEnd, vStart);
      Vector3 vnRayVector = Vector3.normalize(vRayVector);
      
      cosAlpha = Vector3.dot( vnPlaneNormal, vnRayVector );


      // parallel to the plane (alpha=90)
      if ( Math.abs(cosAlpha) < 0.001f ) return Vector3.length(vRayVector);

      deltaD = planeD - Vector3.dot(vStart, vnPlaneNormal);
    
      float l = (deltaD/cosAlpha);
      
      //float k = Vector3.dot( vnPlaneNormal, vPointOnPlane );
      //float a0 = Vector3.dot( vnPlaneNormal, vStart );
      //l = (k - a0)/cosAlpha;
      
      return l;
   }// End of distRayPlane(..)


   public Vector3 PointOnPlane( Vector3 vStart, Vector3 vEnd,
                      Vector3 vPlaneNormal, Vector3 vPointOnPlane )
	 {
        Vector3 vn = Vector3.subtract(vEnd,vStart);
        vn = Vector3.normalize(vn);
        float Length = distRayPlane(vStart,vEnd,vPlaneNormal,vPointOnPlane);
        Vector3 px = Vector3.scale( vn, Length );
        px = Vector3.add( vStart, px );
        
        return px;
   }// End of PointOnPlane(..)


  // Amazing function - it takes a triangle, and a plane, and slices our
  // triange..producing the 3 new triangles.  Returns 0 if it didn't cut
  // the triangle - 1 or 2 depending on how many times it cut the triangle
  // on the positive side of the triangle.  It uses an arry of 3 triangles
  // so we can also use the cut triangle(s) for something else incase we
  // use this function for somethign special :)
  // Returns 3 for all on the positve side of plane
  // Returns 0 for all on the negative side of plane
  // Returns 1 for 1 tri tnew[0] on positive side and tri[1] and tri[2] on neg side
  // Returns 2 for 2 tri tnew[0] & tnew[1] on pos side and of course tri[2] on neg
  int ClipTriangle( Triangle t,
                    Triangle tnew[],
                    Vector3 vPointOnPlane,
                    Vector3 vPlaneNormal )
  {
     // Checking - not necessary though
     vPlaneNormal = Vector3.normalize(vPlaneNormal);
     
     // Clipping
     Vector3 p0 = new Vector3( t.tx0, t.ty0, t.tz0 );
     Vector3 p1 = new Vector3( t.tx1, t.ty1, t.tz1 );
     Vector3 p2 = new Vector3( t.tx2, t.ty2, t.tz2 );
     
     Vector3 v1 = Vector3.subtract( p1, p0 );
     Vector3 v2 = Vector3.subtract( p2, p0 );
     
     //System.out.println("v1  x:" + v1.m_x + " y:" + v1.m_y + " z:" + v1.m_z );
     
     // Okay, lets see if our triangle actually cuts the plane
     float k = Vector3.dot( vPlaneNormal, vPointOnPlane );
     
     float a0 = Vector3.dot( vPlaneNormal, p0 );
     float a1 = Vector3.dot( vPlaneNormal, p1 );
     float a2 = Vector3.dot( vPlaneNormal, p2 );
     
     // Determine how many points are on the positive side of our plane
     int iCount = 0;
     boolean p0in = false;
     boolean p1in = false;
     boolean p2in = false;
     if( (k - a0)> 0 ){ iCount++; p0in=true; }
     if( (k - a1)> 0 ){ iCount++; p1in=true; }
     if( (k - a2)> 0 ){ iCount++; p2in=true; }
     
     //System.out.println("iCount = " + iCount );
     
     // If our triangle is fully on one side, or fully on the other side
     if( iCount==0) return 0;  // All on the positive side on plane
		 if( iCount==3) return 3;  // all on the negative side of plane
     
     
     // These two vectors will hold the two points on the plane that
     // actually cut the triangle.
     // For example if we go from PointA to PointB on our triangle,
     // and it goes through the plane, the point where A->B cuts the
     // plane is called px0 for example.
     Vector3 px0 = new Vector3();
     Vector3 px1 = new Vector3();
     
     
     // Now we have the two points on the plane that make
     // up the intersection points, that we can construct
     // the three new triangles from.
     if(iCount==1 )
     {
				Vector3 pA = new Vector3();
				Vector3 pB = new Vector3();
				Vector3 pC = new Vector3();
				
				if( p0in ){ pA=p0; pB=p1; pC=p2; };
				if( p1in ){ pA=p1; pB=p0; pC=p2; };
				if( p2in ){ pA=p2; pB=p1; pC=p0; };
				
				px0 = PointOnPlane( pA /*vStart*/, pB /*vEnd*/,
                      vPlaneNormal, vPointOnPlane );
     
        px1 = PointOnPlane( pA /*vStart*/, pC /*vEnd*/,
                      vPlaneNormal, vPointOnPlane );
                      
				Triangle t1 = new Triangle( pA, px0, px1, t.tc );
				tnew[0] = t1;
				   
				Triangle t2 = new Triangle( pB, px1, pC, t.tc );
			  Triangle t3 = new Triangle( pB, px0, px1, t.tc );
				tnew[1] = t2;
			  tnew[2] = t3;
				/*
				System.out.println("p0in: " + p0in + " p1in: " +  p1in + " p2in:" + p2in );
				System.out.println("p0  x:" + p0.m_x + " y:" + p0.m_y + " z:" + p0.m_z );
				System.out.println("p1  x:" + p1.m_x + " y:" + p1.m_y + " z:" + p1.m_z );
				System.out.println("p2  x:" + p2.m_x + " y:" + p2.m_y + " z:" + p2.m_z );
				
				Triangle ta = tnew[0];
				System.out.println("newp0  x:" + ta.x0 + " y:" + ta.y0 + " z:" + ta.z0 );
				System.out.println("newp1  x:" + ta.x1 + " y:" + ta.y1 + " z:" + ta.z1 );
				System.out.println("newp2  x:" + ta.x2 + " y:" + ta.y2 + " z:" + ta.z2 );
				*/
				
				return 1;		
     }// End if(iCount==1)
     
     // We are here!..so two points are inside our plane
     if(iCount==2)
     {
				
        Vector3 pA = new Vector3();
				Vector3 pB = new Vector3();
				Vector3 pC = new Vector3();
				
				//System.out.println("p0in: " + p0in + " p1in: " +  p1in + " p2in:" + p2in );
				
				if( !p0in ){ pA=p1; pB=p2; pC=p0; };
				if( !p1in ){ pA=p0; pB=p2; pC=p1; };
				if( !p2in ){ pA=p0; pB=p1; pC=p2; };
				
				
				px0 = PointOnPlane( pB /*vStart*/, pC /*vEnd*/,
                      vPlaneNormal, vPointOnPlane );
     
        px1 = PointOnPlane( pA /*vStart*/, pC /*vEnd*/,
                      vPlaneNormal, vPointOnPlane );
        
        Triangle t1 = new Triangle( pC, px0, px1, t.tc );  // red
				tnew[2] = t1;
				   
				Triangle t2 = new Triangle( pB, pA, px0, t.tc );  // dark red
			  Triangle t3 = new Triangle( pA, px0, px1, t.tc ); // green
				tnew[0] = t2;
			  tnew[1] = t3;
              
				return 2;		
     }// End if(iCount==2)
   
     // Something went wrong if we reached here :)
     return 3;
  }// End ClipTriangle(..)
  
  boolean odd = false;
  public void RenderTriangle(Triangle t)
  {
     // Add this line if you want only a single side of the square (the red one)
     // to be rendered - for test purposes
     
     // Add this line, if you only want a single one of the trianges rendered
     //if( t.tc != Color.red ) return;
     //odd = !odd;
     //if( odd ) return;
     
     
     Triangle[] tnew = new Triangle[3];
     tnew[0] = new Triangle();
     tnew[1] = new Triangle();
     tnew[2] = new Triangle();
     
     
     Vector3 vPointOnPlane = new Vector3( 0, 0, 1.0 );
     Vector3 vPlaneDirection = new Vector3( 0, 0, -1 );
     int clip = ClipTriangle( t,
                   tnew,
                   vPointOnPlane,
                   vPlaneDirection );
     
     
     
     if( clip == 3 ) // All on the positive side of the plane
		 {								            
        ScreenPerspective( myImage,
	                         t.tx0, t.ty0, t.tz0,
	                         t.tx1, t.ty1, t.tz1,
	                         t.tx2, t.ty2, t.tz2,
	                         t.tc);
	    }// End if(..)
	    else if(clip==1 || clip==2) // triangles on the positive side of plane
	    {
	       for(int i=0; i<clip; i++)
	       {
	          ScreenPerspective( myImage,
	                             tnew[i].tx0, tnew[i].ty0, tnew[i].tz0,
	                             tnew[i].tx1, tnew[i].ty1, tnew[i].tz1,
	                             tnew[i].tx2, tnew[i].ty2, tnew[i].tz2,
	                             tnew[i].tc);
	        }// End for loop
	    }// End else if(...)

	    
  }// End of RenderTriangle(..)
  
  int ClipLine( Vector3 p0, Vector3 p1,
	              Vector3 pnew[],  Vector3 vPointOnPlane,  Vector3 vPlaneNormal )
  {
     vPlaneNormal = Vector3.normalize(vPlaneNormal);
     
     Vector3 v1 = Vector3.subtract( p1, p0 );
     
     //System.out.println("v1  x:" + v1.m_x + " y:" + v1.m_y + " z:" + v1.m_z );
     
     // Okay, lets see if our triangle actually cuts the plane
     float k = Vector3.dot( vPlaneNormal, vPointOnPlane );
     
     float a0 = Vector3.dot( vPlaneNormal, p0 );
     float a1 = Vector3.dot( vPlaneNormal, p1 );
     
     // Determine how many points are on the positive side of our plane
     int iCount = 0;
     boolean p0in = false;
     boolean p1in = false;

     if( (k - a0)> 0 ){ iCount++; p0in=true; }
     if( (k - a1)> 0 ){ iCount++; p1in=true; }
     
     if( iCount==0) return 0;  // All on the positive side on plane
		 if( iCount==2) return 2;  // all on the negative side of plane
     
     Vector3 px0 = new Vector3();

		 Vector3 pA = new Vector3();
		 Vector3 pB = new Vector3();
				
		 if( p0in ){ pA=p0; pB=p1;};
		 if( p1in ){ pA=p1; pB=p0;};
				
		 px0 = PointOnPlane( pA /*vStart*/, pB /*vEnd*/,
                      vPlaneNormal, vPointOnPlane );

     pnew[0] = pA;
     pnew[1] = px0;
     
     return 1;		

  }// End ClipLine(..)
  
  
  void SortRenderOrder(Triangle t[], int iNumTris)
  {
     // First lets generate an average z for each triangle
     float average_z;
     for( int i=0; i<iNumTris; i++ )
     {
        average_z = t[i].tz0 + t[i].tz1 + t[i].tz2;
        average_z /= 3.0f;
        t[i].avg_z = average_z;
     }// End for loop
     
     // Now lets do a bruit force sort, so each triangle is in order
     // of our average z
     for( int outer=0; outer<iNumTris; outer++ )
     {
        for( int inner=0; inner<iNumTris; inner++ )
        {
            if( t[outer].avg_z > t[inner].avg_z )
            {
               Triangle temp = t[outer];
               t[outer] = t[inner];
               t[inner] = temp;
            }// End if(..)
        }// End inner for loop
     }// End outer for loop
     
  }// SortRenderOrder(..)

  
  void RenderAllTriangles(Triangle t[], int iNumTris)
  {   
     for(int i=0; i<iNumTris; i++)
     {
        if(t[i].bCull == false )
           RenderTriangle( t[i] );
     }// End for loop
  }// End of RenderAllTriangles(..)
  
  float DotProduct(float x0, float y0, float z0,
	                 float x1, float y1, float z1 )
  {
    return( x0*x1 + y0*y1 + z0*z1 );
  }// End of DotProduct(..)
  
  void CullTriangles( Triangle t[], int iNumTris )
  {
     // Our default camera is at 0,0,0 and faces in the positive z
     // direction
     
     for(int i=0; i<iNumTris; i++)
     {
        float cosA = DotProduct( t[i].tnx, t[i].tny, t[i].tnz,
                                 0.0f,     0.0f,     1.0f );

        // Well instead of checking for equal or less than 0, due to errors
        // with number rounding and things...we need to check for
        // less than 0.32 :)
				                              
        if( cosA < 0.32f )
           t[i].bCull = true;
        else
           t[i].bCull = false;
     }//End for loop
     
     
  }// End CullTriangles(..)
  
  void CalculateNormals(Triangle t[], int iNumTris)
  {
     for( int i=0; i<iNumTris; i++ )
     {
        t[i].CalculateNormal();
     }// End for loop
  }// End of CalculateNormals(..)
  
  void ResetAllCoords(Triangle t[], int iNumTris)
  {
  	 for(int i=0; i<iNumTris; i++)
     {
        t[i].ResetCoords();  
     }// End for loop
  }// End of ResetAllCoords(..)
  
  
  void RenderWireFloor(Image image, Vector3 rot, Vector3 mov)
  {
      float xstart = -200;   float xend = 400;
      float zstart = -50;    

      float zinc = 5;
      
      Vector3 vFrom = new Vector3();
      Vector3 vTo = new Vector3();
      
      Vector3[] lnew = new Vector3 [2];
      lnew[0] = new Vector3();
      lnew[1] = new Vector3();
      
      for(int x=0; x<100; x++)
      {
         //for(int z=0; z<5; z++)
         {
            vFrom.m_x  =  xstart;
            vFrom.m_y  = -1.0f;
            vFrom.m_z  =  zstart;
            vTo.m_x = xend;
            vTo.m_y = -1.0f;
            vTo.m_z = zstart;
            
            vFrom = Vector3.subtract(vFrom, mov);
            vTo   = Vector3.subtract(vTo, mov);
            vFrom = Vector3.rotatey( vFrom, -rot.m_y );
            vTo   = Vector3.rotatey( vTo, -rot.m_y );
            ///////////////////////////////////////////////////
            // Test Theory
            //========================================================
            /*
            double eye_x = mov.m_x;
            double eye_z = mov.m_z;
            
            double pSin = Math.sin(rot.m_y);
            double pCos = Math.cos(rot.m_y);
            double rot_eye_x = pSin*eye_z + pCos*eye_x;
            double rot_eye_z = pCos*eye_z - pSin*eye_x;
		
            double z1 = vFrom.m_z;
            double z2 = vTo.m_z;
            double x1 = vFrom.m_x;
            double x2 = vTo.m_x;
		
					  // Now that we have our world_eye x and z posotion values, we
					  // can use these to effect the values of our drawing.
					  double rz1,rz2,rx1,rx2;
			                
					  rz1=pCos*x1+pSin*z1 - rot_eye_x;     // perpendicular line to the players
					  rz2=pCos*x2+pSin*z2 - rot_eye_x;     // view point
			
				
					  rx1=pCos*z1-pSin*x1 - rot_eye_z;
					  rx2=pCos*z2-pSin*x2 - rot_eye_z;
					  
					  vFrom.m_z = (float)rz1;
					  vTo.m_z = (float)rz2;
					  vFrom.m_x = (float)rx1;
					  vTo.m_x = (float)rx2;
					  */
					  
            //========================================================
            ///////////////////////////////////////////////////
            
            int clip = ClipLine(vFrom, vTo, lnew, new Vector3(0,0,3.5), new Vector3(0,0,-1) );
            if( clip == 2 )
            {
  		        LineScreenPerspective(image, vFrom, vTo, new Color(0x00,0xff,0x00) );
  		        //System.out.println("vFrom: " + vFrom.m_x + ", " + vFrom.m_y + " ," +vFrom.m_z );
  		        //System.out.println("vTo:   " + vTo.m_x + ", " + vTo.m_y + " ," +vTo.m_z );
  		      }
  		      else
  		      {
  		        LineScreenPerspective(image, lnew[0], lnew[1], new Color(0x00,0x00,0xff) );
  		        
  		        //System.out.println("vFrom: " + vFrom.m_x + ", " + vFrom.m_y + " ," +vFrom.m_z );
  		        //System.out.println("vTo:   " + vTo.m_x + ", " + vTo.m_y + " ," + vTo.m_z );
  		        //System.out.println("lnew[0]: " + lnew[0].m_x + ", " + lnew[0].m_y + " ," +lnew[0].m_z );
  		        //System.out.println("lnew[1]: " + lnew[1].m_x + ", " + lnew[1].m_y + " ," +lnew[1].m_z );
  		      }
  		       
  		        
  		      zstart+=zinc;

  		   }// End for y
  		   //xstart+=2;
  		}// End for x
  	
  		
  }// End of RenderWireFloor(..)
  

  Vector3 m_EyeAngle = new Vector3( 0, 0, 0 );
  Vector3 m_EyePos   = new Vector3( 0, 0, -10 );
  Vector3 m_BoxPos   = new Vector3( 0, 0, 0 );
  

  public void paint(Graphics g) 
  {
      // Clear screen
      offScreen.setColor(Color.white);
      offScreen.fillRect(0,0,this.getSize().width,this.getSize().height);
			
      Dimension appletSize = this.getSize();
      int width  = appletSize.width;
      int height = appletSize.height;

		      
      ResetAllCoords( m_tri, m_NumTris );
      
      // Lets rotate all of the triangles and translate them back into the horizon
      for(int i=0; i<m_NumTris; i++)
      {												
		      
            Vector3 vBoxTempPos = Vector3.subtract( m_BoxPos, m_EyePos);			      
            m_tri[i].Translate( vBoxTempPos.m_x, 
				vBoxTempPos.m_y, 
                                vBoxTempPos.m_z);
															
            m_tri[i].RotateY(-m_EyeAngle.m_y);
            m_tri[i].RotateZ(-m_EyeAngle.m_z);
            m_tri[i].RotateX(-m_EyeAngle.m_x);
      }

      RenderWireFloor(myImage, m_EyeAngle, m_EyePos);

      CalculateNormals( m_tri, m_NumTris );
      CullTriangles( m_tri, m_NumTris );
      SortRenderOrder( m_tri, m_NumTris );
      RenderAllTriangles( m_tri, m_NumTris );

		             
      //offScreen.drawLine( mouse_x_left+10,  mouse_y_left+10,
      //                    mouse_x_right+10, mouse_y_right+10);
  	 
      g.drawImage(myImage,0,0,this);
  }// End of paint(..)



  public void update(Graphics g){ paint(g); }

  public void LineScreenPerspective( Image image,
	                                   Vector3 inA, Vector3 inB,
	                                   Color c )
  {
  		    // Get the screen size of our applet
		      Dimension appletSize = this.getSize();
		      int width  = appletSize.width;
		      int height = appletSize.height;
		
		      float x0, y0, z0;
		      float x1, y1, z1;
		      
		      x0 = inA.m_x;
		      y0 = inA.m_y;
		      z0 = inA.m_z;
		      
		      x1 = inB.m_x;
		      y1 = inB.m_y;
		      z1 = inB.m_z;
		      
		      if( (z0<1) && (z1<1) )
		         return;
		         
		      if( z0 < 1 ) z0 = 1;
		      if( z1 < 1 ) z1 = 1;

		      // Something worth noting - we have a pole at z=0...as when we
		      // create a perspective ..which is x_per = d*x/z for example, if
		      // z is 0 or very close to zero, we'll get an infinit number...so
		      // if we have a z value less than 1 we'll just round z to 1 and it
		      // will get clipped later down the line.
		      
		      // Whats this pTan stuff for?...well we can't just clip the z value
		      // to 1...as what if its on a really steep angle...so what we do, is
		      // we work out a new value for x and z and then clip it to the near
		      // clip plane :)
		      
		      // Add some clipping code so Z is clipped to the near view plane
		      // ++ //
		
					// From x,y,z to x,y for the screen.
					// -1-Perspective Conversion

		      // Focul point of 1 (Normalised view plane 90 degrees)
					float d = 1.0f; 
					float Perspective_x0 = -d*x0 / z0;
					float Perspective_x1 = -d*x1 / z1;
					
					// its between -1 to 1...so we need to scale it to 0 to 1...and scale to
					// the size of the screen.
					Perspective_x0 += 1;
					Perspective_x1 += 1;
					// So now its between 0 and 2 and not -1 to 1;
					Perspective_x0 *= 0.5;
					Perspective_x1 *= 0.5;
					// -2- Now we scale it to the size of the screen
					float Screen_x0 = (width-1)*Perspective_x0;
					float Screen_x1 = (width-1)*Perspective_x1;
					
					// Add some clipping to make sure its on the screen here
					// ++ //
		              
					// Now we do the same for the y value to convert it
		      // to screen coordinates … its exactly the same as for the x above,
		      // but I've combined all the stages into a single line for each
		      // one

					// Note y1 is the top of square, and y2 is the bottom of our square
					
					float Screen_y0 = ((-d*y0 / z0)+1)*0.5f *(height-1);
					float Screen_y1 = ((-d*y1 / z1)+1)*0.5f *(height-1);


          //drawLine(image, (int)Screen_x0, (int)Screen_y0, 
					//                (int)Screen_x1, (int)Screen_y1, c);
					
					offScreen.setColor( c );
					offScreen.drawLine( (int)Screen_x0,  (int)Screen_y0,
		                          (int)Screen_x1, (int)Screen_y1);
					
  
  }// End LineScreenPerspective(..)
  
  public void ScreenPerspective( Image image,
	                               float x0, float y0, float z0,
	                               float x1, float y1, float z1,
	                               float x2, float y2, float z2,
	                               Color c )
  {
			    // This is where we'll put our final values that we calculate
			    // we only have an x and a y, as we'll convert our x,y and z into
			    // a screen coordinate square which has all the sizing and things
			    // done to it already

		
		      // Get the screen size of our applet
		      Dimension appletSize = this.getSize();
		      int width  = appletSize.width;
		      int height = appletSize.height;
		
		      
		      if( (z0<1) && (z1<1) && (z2<1) )
		         return;
		         
		      if( z0 < 1 ) z0 = 1;
		      if( z1 < 1 ) z1 = 1;
		      if( z2 < 1 ) z2 = 1;
		      
		         
		      // Something worth noting - we have a pole at z=0...as when we
		      // create a perspective ..which is x_per = d*x/z for example, if
		      // z is 0 or very close to zero, we'll get an infinit number...so
		      // if we have a z value less than 1 we'll just round z to 1 and it
		      // will get clipped later down the line.
		      
		      // Whats this pTan stuff for?...well we can't just clip the z value
		      // to 1...as what if its on a really steep angle...so what we do, is
		      // we work out a new value for x and z and then clip it to the near
		      // clip plane :)
		      
		      // Add some clipping code so Z is clipped to the near view plane
		      // ++ //
		
					// From x,y,z to x,y for the screen.
					// -1-Perspective Conversion

		      // Focul point of 1 (Normalised view plane 90 degrees)
					float d = 1.0f; 
					float Perspective_x0 = -d*x0 / z0;
					float Perspective_x1 = -d*x1 / z1;
					float Perspective_x2 = -d*x2 / z2;
					
					// its between -1 to 1...so we need to scale it to 0 to 1...and scale to
					// the size of the screen.
					Perspective_x0 += 1;
					Perspective_x1 += 1;
					Perspective_x2 += 1; 
					// So now its between 0 and 2 and not -1 to 1;
					Perspective_x0 *= 0.5;
					Perspective_x1 *= 0.5;
					Perspective_x2 *= 0.5;
					// -2- Now we scale it to the size of the screen
					float Screen_x0 = (width-1)*Perspective_x0;
					float Screen_x1 = (width-1)*Perspective_x1;
					float Screen_x2 = (width-1)*Perspective_x2;
					
					// Add some clipping to make sure its on the screen here
					// ++ //
		              
					// Now we do the same for the y value to convert it
		      // to screen coordinates … its exactly the same as for the x above,
		      // but I've combined all the stages into a single line for each
		      // one

					// Note y1 is the top of square, and y2 is the bottom of our square
					
					float Screen_y0 = ((-d*y0 / z0)+1)*0.5f *(height-1);
					float Screen_y1 = ((-d*y1 / z1)+1)*0.5f *(height-1);
					float Screen_y2 = ((-d*y2 / z2)+1)*0.5f *(height-1);

          // Debug information
          /*
          System.out.println( "Color: " + c );
					System.out.println( "x0: " + Screen_x0 + "  y0: " + Screen_y0 );
					System.out.println( "x1: " + Screen_x1 + "  y1: " + Screen_y1 );
					System.out.println( "x2: " + Screen_x2 + "  y2: " + Screen_y2 );
					System.out.println("");
					*/

					// Render our data
			    drawTriangle( image,
			                  Screen_x0, Screen_y0,
			                  Screen_x1, Screen_y1,
			                  Screen_x2, Screen_y2,
			                  c );            

  }// End ScreenPerspective(...)


	public void drawTriangle( Image image,
	                          float x0, float y0,
	                          float x1, float y1,
	                          float x2, float y2,
	                          Color c )
	{
	   //First we sort our points out into y order...where it goes
	   // 0
	   // 2
	   // 1
	   float t; // temp variable
	   if( y1 < y0 )
	   {
	      t  = y0;
	      y0 = y1;
	      y1 = t;
	      
	      t  = x0;
	      x0 = x1;
	      x1 = t;
	   }
		 
		 if( y2 < y0 )
	   {
	      t  = y0;
	      y0 = y2;
	      y2 = t;
	      
	      t  = x0;
	      x0 = x2;
	      x2 = t;
	   }  
		 
		if( y1 < y2 )
	   {
	      t  = y1;
	      y1 = y2;
	      y2 = t;
	      
	      t  = x1;
	      x1 = x2;
	      x2 = t;
	   }     
	   
	   // Next part...
	   // Render top of triangle
	   float x_left  = x0;
	   float x_right = x0;
	   
	   float dy_top    = y2 - y0;
	   float dy_bottom = y1 - y2;
	   
	   float dx_left  = x2 - x0;   // to the middle then we change it
	   float dx_right = x1 - x0;   // all the way to the bottom :)
	   
	   //int dx_left_dir  = dx_left  < 0 ? -1 : 1;
	   //int dx_right_dir = dx_right < 0 ? -1 : 1;
	   
	   //dx_left  *= dx_left_dir;
	   //dx_right *= dx_right_dir;
	   
	   //dx_left  = dx_left  / dy_top;
	   //dx_right = dx_right / dy_top;
	   
		 dx_left  = (x2 - x0) / (y2 - y0);
	   dx_right = (x1 - x0) / (y1 - y0);
	   
	   int s = 0;
	   if( dx_left > dx_right )
	   {
	      t = dx_left;
	      dx_left = dx_right;
	      dx_right = t;
	      s=1;
	   }//End if
	   
	   for(float y=y0; y<y2; y++)
	   {
	        for(float x=x_left; x<x_right; x++)
	        {
	   			   setPixel(image, (int)x, (int)y, c );
		  		}// End inner for loop
		  		x_left  += dx_left;
		  		x_right += dx_right;
	   
	   }// End outer for loop
	
	   // **IMPORTANT UPDATE **
	   // Its important to check that the top of the triangle exists...as its af flat top
	   // then we have to make sure our bottom is okay :)  Not the added lines of code
	   // so its not x0 for the starting point.
     
	   // Now for the bottom of the triangle
		 if( s == 0 )
	   {
	      dx_left = (x1 - x2) / (y1 - y2);
	      x_left = x2;
	   }
	   else
	   {
	      dx_right = (x1 - x2) / (y1 - y2);
	      x_right = x2;
	   }
	
	   
	   for(float y=y2; y<y1; y++)
	   {
	      for(float x=x_left; x<x_right; x++)
	      {
	         setPixel(image, (int)x, (int)y, c);
	      }
	      x_left  += dx_left;
	      x_right += dx_right;
	   }// End outer for loop
		
	
	}//End of drawTriangle(..)

  public void drawLine(Image image, int x0, int y0, int x1, int y1, Color c)
  {
  		float sx = (float)x0;
  		float sy = (float)y0;
  		float ex = (float)x1;
  		float ey = (float)y1;
  		
  		float dx = ex-sx;
  		float dy = ey-sy;	
  		
  		int xdir = dx > 0 ? 1 : -1;
  		int ydir = dy > 0 ? 1 : -1;
  		
  		dx = dx*xdir;
  		dy = dy*ydir;
  		
  		
  		float incx =  dx / dy;
  		float incy =  dy / dx;
  		
  		incx *= xdir;
  		incy *= ydir;
  		
  		if( dy > dx )
  		{
		  		for( int y=0; y<dy; y++)
		  		{
		  				setPixel(image, (int)sx, (int)sy, c );
		  				sx += incx;
		  				sy += ydir;

		  		}// End for loop(..)
  		}
  		else
  		{
  		    for( int x=0; x<dx; x++)
		  		{
		  				setPixel(image, (int)sx, (int)sy, c );
		  				sy += incy;
		  				sx += xdir;

		  		}// End for loop(..)
  		}
  		
  }//End of drawline(..)
  
  public void setPixel(Image image, int x, int y, Color color ) 
  {
     Graphics g = image.getGraphics( );
     g.setColor( color );
     g.fillRect( x, y, 1, 1 );
     g.dispose( );
  }// End of setPixel(..)


/*********************************************************************************************/
/*                                                                                           */
/*  Capture event when mouse is pressed                                                      */
/*    Parameters:                                                                            */
/*    evt is The event...                                                                    */
/*    x is the x mouse position                                                              */
/*    y is the y mouse position                                                              */
/*    return whether or not we handled the event                                             */
/*                                                                                           */
/*********************************************************************************************/

  boolean bMouseDown = false;

  
	public boolean mouseDown(Event evt, int x, int y)
  {
      mouse_x = x;
     	mouse_y = y;
     	
  	  if(evt.id == Event.MOUSE_DOWN)
      {
          // Right mouse button
      		if( evt.metaDown() == true )
      		{
      				//System.out.println( "Right MouseDown" );
      		}
      		else // left mouse button
      		{
      				//System.out.println( "Left MouseDown" );
     					bMouseDown = true;
      		}
      }// End if
    
		 repaint();
		 return true;
	}// End of mouseDown(..)

/*********************************************************************************************/
/*                                                                                           */
/*  Capture mouse release                                                                    */
/*    Parameters:                                                                            */
/*    evt is The event...                                                                    */
/*    x is the x mouse position                                                              */
/*    y is the y mouse position                                                              */
/*    return whether or not we handled the event                                             */
/*                                                                                           */
/*********************************************************************************************/

	public boolean mouseUp(Event evt, int x, int y)
	{
	   mouse_y = y;
		 mouse_x = x;
		 bMouseDown = false;

		 return false;
	}// End of mouseUp(..)
	
/*********************************************************************************************/
/*                                                                                           */
/*  Capture mouse drags                                                                      */
/*    Parameters:                                                                            */
/*    evt is The event...                                                                    */
/*    x is the x mouse position                                                              */
/*    y is the y mouse position                                                              */
/*    return whether or not we handled the event                                             */
/*                                                                                           */
/*********************************************************************************************/
	public boolean mouseDrag(Event evt, int x, int y)
	{

	  if( bMouseDown)
	  {
	     float speedrotation = 0.01f;
	     float speed = 0.05f;
	     float dx = mouse_x - x;
		   float dy = mouse_y - y;
		   mouse_y = y;
		   mouse_x = x;
	     
	     
	     Vector3 dir = new Vector3( 0, 0, 1 );
	     dir = Vector3.rotatey(dir, m_EyeAngle.m_y);
	     dir = Vector3.scale(dir, dy*speed);
	     m_EyePos = Vector3.add(m_EyePos, dir );
	     

	     //m_EyePos.m_x += (float)(Math.cos(m_EyeAngle.m_y)*(speed*dy));
			 //m_EyePos.m_z += (float)(Math.sin(m_EyeAngle.m_y)*(speed*dy));
			 

	     m_EyeAngle.m_y += speedrotation * dx;
	     
	     repaint();
	     
	  }// End if(..)
	  
  	return true;
	}// End of mouseDrag(..)

   public boolean keyDown(Event e, int key)
	 {
   			
      double inc = 0.1;
      float speed = 2.0f;

      if(key==Event.LEFT)
         m_EyeAngle.m_y += Math.PI/32;

      if(key==Event.RIGHT)
         m_EyeAngle.m_y -= Math.PI/32;

      if(key==Event.UP)
      {
         Vector3 dir = new Vector3( 0, 0, 1 );
	       dir = Vector3.rotatey(dir, m_EyeAngle.m_y);
	       dir = Vector3.scale(dir, speed);
	       m_EyePos = Vector3.add(m_EyePos, dir );
	       
	       //float fix = (float)(Math.PI*3.0f/2.0f);
         //m_EyePos.m_x += (float)(Math.cos(m_EyeAngle.m_y - fix )*(speed));
         //m_EyePos.m_z += (float)(Math.sin(m_EyeAngle.m_y - fix )*(speed));
      }

      if(key==Event.DOWN)
      {
         //m_EyePos.m_x -= (float)(Math.cos(m_EyeAngle.m_y)*(speed));
         //m_EyePos.m_z -= (float)(Math.sin(m_EyeAngle.m_y)*(speed));
         Vector3 dir = new Vector3( 0, 0, 1 );
	       dir = Vector3.rotatey(dir, m_EyeAngle.m_y);
	       dir = Vector3.scale(dir, -speed);
	       m_EyePos = Vector3.add(m_EyePos, dir );
      }

			repaint();
      return true;
   }// End of keyDown(..)

}// End of our Applet


  //Vector3 m_EyeAngle = new Vector3( 0, 0, 0 );
  //Vector3 m_EyePos = new Vector3( 0, 0, -10 );