import java.awt.Color;
import Vertex3D;
import Matrix3D;
import Surface;
import ZRaster;
import Vector3D;
import Light;
import Point3D;
import Surface;

class EdgeEqn {
    public float A, B, C;
    public int flag;    

    public EdgeEqn(Vertex3D v0, Vertex3D v1)
    {
        A = v0.y - v1.y;
        B = v1.x - v0.x;
        C = -0.5f * (A*(v0.x + v1.x) + B*(v0.y + v1.y));

        flag = 0;
        if (A >= 0) flag += 8;
        if (B >= 0) flag += 1;
    }

    public void flip()
    {
        A = -A;
        B = -B;
        C = -C;
    }

    public float evaluate(int x, int y)
    {
        return (A*x + B*y + C);
    }
}

public class Triangle {
    private static Vertex3D vlist[];
    protected int v[];
    protected float r[], g[], b[];
    protected Surface surface;
    private boolean culled;
    private Vertex3D vert[];
	Point3D centroid;
	
	public static final int NONE = 0;
    public static final int FLAT = 1;
    public static final int GOURAUD = 2;
	public static int LightModel=FLAT;  //initialize with flat shading
	
    public Triangle()
    {
    }

    public Triangle(int v0, int v1, int v2)
    {
        v = new int[3];
        v[0] = v0;
        v[1] = v1;
        v[2] = v2;    
        r = new float[3];
        g = new float[3];
        b = new float[3];
        vert = new Vertex3D[3];
        vert[0] = new Vertex3D();
        vert[1] = new Vertex3D();
        vert[2] = new Vertex3D();
        scale = -1;
        culled = false;
		
    }
	
	public Triangle(Vertex3D v0, Vertex3D v1, Vertex3D v2)
    {
          
        r = new float[3];
        g = new float[3];
        b = new float[3];
        vert = new Vertex3D[3];
        vert[0] = new Vertex3D(v0);
        vert[1] = new Vertex3D(v1);
        vert[2] = new Vertex3D(v2);
		for(int i=0; i<3; i++){
			r[i]=vert[i].r;
			g[i]=vert[i].g;
			b[i]=vert[i].b;
		}
        scale = -1;
        culled = false;
		
    }
    
    public void setSurface(Surface s)
    {
        surface = s;
    }

    public Surface getSurface()
    {
        return surface;
    }

    public boolean isVisible()
    {
        return (!culled);
    }
    
    
		/** computes plane equation given the 3 verticies
	 *  page 309 of book
	 */
	public void PlaneEqn3D(float eqn[], Vertex3D v0, Vertex3D v1, Vertex3D v2)	    {
	   /*
		double  A, B, C, D, area2;
		float x0, y0, z0, x1, y1, z1, x2, y2,z2;
		x0=v0.x;
		y0=v0.y;
		z0=v0.z;
		x1=v1.x;
		y1=v1.y;
		z1=v1.z;	
		x2=v2.x;
		y2=v2.y;
		z2=v2.z;
		
		A=y1*z2-y0*(x1*z2-z1*x2)+z0*(x1*y2-y1*x2);
		B=x0*(z2-z1)-1*(x1*z2-z1*x2)+z0*(x1*y2-y1*x2);
		C=x0*(y1-y2)-y0*(x1-x2)+1*(x1*y2-y1*x2);
		
		D=-(x0*(y1*z2-y2*z1) -y0*(z1*z2-x2*z1) + z0*(x1*y2-y1*x2));
	
		
		eqn[0]=(float)A;
		eqn[1]=(float)B;
		eqn[2]=(float)C;
		eqn[3]=(float)D;
		*/
		Vector3D t0=new Vector3D(v0);
		Vector3D t1=new Vector3D(v1);
		Vector3D t2=new Vector3D(v2);
		Vector3D.subtractVector(t1,t0);
		Vector3D a=new Vector3D(t1);
		Vector3D.subtractVector(t2,t0);
		Vector3D b=new Vector3D(t2);
		Vector3D.cross(a,b);
		//Vector3D.dot(a,t0);
		
		eqn[0]=a.x;
		eqn[1]=a.y;
		eqn[2]=a.z;
		eqn[3]=-Vector3D.dot(a,t0);
			   
	}
    /*
        ... you'll need to modify the following two methods ...
    */
    /*
	public void Illuminate(Light l[], int lights, Point3D eye, boolean cull)
    {
       for (int i = 0; i < 3; i++) {
            r[i] = surface.r;
            g[i] = surface.g;
            b[i] = surface.b;
        }
    }
	*/
	
	public void Illuminate(Light lights[], int num_lights, Point3D eye, boolean cull){
		//check if eye is in positive half space
		
		vert[0]=vlist[v[0]];
		vert[1]=vlist[v[1]];
		vert[2]=vlist[v[2]];
		float zPlane[] = new float[4];
		PlaneEqn3D(zPlane, vert[0], vert[1], vert[2]);
		
		
		if(cull){
			if((eye.x*zPlane[0]+eye.y*zPlane[1]+eye.z*zPlane[2]+zPlane[3])<0){
				culled=true;
			}
			else{culled=false;}
		}
		
		//compute illumination model if viewable
		if(!culled){
			
			if(LightModel==NONE){
				
				for (int i = 0; i < 3; i++) {
					r[i] = surface.r;
					g[i] = surface.g;
					 b[i] = surface.b;
					 vert[i].r=r[i];
					vert[i].g=g[i];
					vert[i].b=b[i];
				}
		
			}
			
			if(LightModel==FLAT){
			//compute centroid
				centroid=new Point3D((vert[0].x+vert[1].x+vert[2].x)/3,(vert[0].y+vert[1].y+vert[2].y)/3,(vert[0].z+vert[1].z+vert[2].z)/3);
	
				float red=0;
				float green=0;
				float blue=0;
				for(int i=0; i<num_lights; i++){
				//ambient
					if(lights[i].lightType==Light.AMBIENT){
					red+=surface.kar*lights[i].ir;
					green+=surface.kag*lights[i].ig;
					blue+=surface.kab*lights[i].ib;
					}
					
					if(lights[i].lightType==Light.DIRECTIONAL){
					Vector3D n = new Vector3D(zPlane[0], zPlane[1], zPlane[2]); //normal to surface
					n.normalize();
					Vector3D l = new Vector3D(-lights[i].x, -lights[i].y, -lights[i].z); //vector to light
					l.normalize();
					Vector3D v = new Vector3D(eye.x-centroid.x, eye.y-centroid.y, eye.z-centroid.z);//vector to viewer
					v.normalize();
					Vector3D r= new Vector3D(n);
					r.scaleVector(2*Vector3D.dot(n,l));
					r.subtractVector(l);
					r.normalize();
				
					float kdv, ksv;
					kdv=Vector3D.dot(n,l);
					ksv=Vector3D.dot(v,r);
				
					red+=lights[i].ir*(surface.kdr*kdv + surface.ksr*Math.pow(ksv,surface.ns));
					green+=lights[i].ig*(surface.kdg*kdv + surface.ksg*Math.pow(ksv,surface.ns));
					blue+=lights[i].ib*(surface.kdb*kdv + surface.ksb*Math.pow(ksv,surface.ns));
				
										  
					
					}
		
				}
				if(red>1){
						red=1;
					}
				if(green>1){
					green=1;
				}
				if(blue>1){
					blue=1;
				}
				for (int i = 0; i < 3; i++) {
				
					r[i] = red;
					g[i] = green;
					b[i] = blue;
					vert[i].r=red;
					vert[i].g=green;
					vert[i].b=blue;
				}
			}
			
			if(LightModel==GOURAUD){
			
				
				float red=0;
				float green=0;
				float blue=0;
				for(int j=0; j<3; j++){
					for(int i=0; i<num_lights; i++){
					//ambient
						if(lights[i].lightType==Light.AMBIENT){
						red+=surface.kar*lights[i].ir;
						green+=surface.kag*lights[i].ig;
						blue+=surface.kab*lights[i].ib;
						}
					//Directional
						if(lights[i].lightType==Light.DIRECTIONAL){
						Vector3D n = new Vector3D(vert[j].nx,vert[j].ny,vert[j].nz); //normal to surface
						n.normalize();
						Vector3D l = new Vector3D(-lights[i].x, -lights[i].y, -lights[i].z); //vector to light
						l.normalize();
						Vector3D v = new Vector3D(eye.x-vert[j].x, eye.y-vert[j].y, eye.z-vert[j].z); //vector to viewer
						v.normalize();
						Vector3D r= new Vector3D(n);
						r.scaleVector(2*Vector3D.dot(n,l));
						r.subtractVector(l);
						r.normalize();
				
						float kdv, ksv;
						kdv=Vector3D.dot(n,l);
						ksv=Vector3D.dot(v,r);
				
						red+=lights[i].ir*(surface.kdr*kdv + surface.ksr*Math.pow(ksv,surface.ns));
						green+=lights[i].ig*(surface.kdg*kdv + surface.ksg*Math.pow(ksv,surface.ns));
						blue+=lights[i].ib*(surface.kdb*kdv + surface.ksb*Math.pow(ksv,surface.ns));
						}
		
					}
					if(red>1){
							red=1;
						}
					if(green>1){
						green=1;
					}
					if(blue>1){
						blue=1;
					}
				
						
				
					r[j] = red;
					g[j] = green;
					b[j] = blue;
					vert[j].r=red;
					vert[j].g=green;
					vert[j].b=blue;
					red=0;
					green=0;
					blue=0;
				}
				
			}
			
		
		}
	}
    
    public void ClipAndDraw(ZRaster raster, Matrix3D project)		
    {	Vertex3D vrt[]=new Vertex3D[3];
		for(int i=0; i<3; i++){
			
			vrt[i]= vlist[v[i]];
			vrt[i].r=r[i];
			vrt[i].g=g[i];
			vrt[i].b=b[i];
			// this is the key, we must account for sign differences in w such that we will be comparing like coordinates
			float w=vrt[i].w;
			if(w<0){
				w=-w;
			}
			vrt[i].x*=1/w;
			vrt[i].y*=1/w;
			vrt[i].z*=1/w;
			vrt[i].w=1;
					 
		}
		
		ClipAndDraw(raster, project,vrt[0],vrt[1],vrt[2],true);
		
    }

	//recursively clip and then draw the triangle
	//also pays close attention to the ordering of the verticies such that area will be positive
	public void ClipAndDraw(ZRaster raster, Matrix3D project, Vertex3D v0, Vertex3D v1, Vertex3D v2, boolean near)
    {	
		//order the verticies in z
		
		Vertex3D vrt[]=new Vertex3D[3];
		
		vrt[0] = v0;
        vrt[1] = v1;
        vrt[2] = v2;
	
		Vertex3D tmp[]=new Vertex3D[3];
		int o[]=new int[3];  //order of the verticies
		
		if(vrt[0].z<vrt[1].z){ // v0<v1
			if(vrt[2].z<vrt[0].z){ // v3<v0<v1
				tmp[0]=vrt[2];
				tmp[1]=vrt[0];
				tmp[2]=vrt[1];
				o[0]=2;
				o[1]=0;
				o[2]=1;
			}
			else if(vrt[2].z>vrt[1].z){ // v0<v1<v2
				tmp[0]=vrt[0];
				tmp[1]=vrt[1];
				tmp[2]=vrt[2];
				o[0]=0;
				o[1]=1;
				o[2]=2;
			}
			else{ //v0<v3<v1
				tmp[0]=vrt[0];
				tmp[1]=vrt[2];
				tmp[2]=vrt[1];
				o[0]=0;
				o[1]=2;
				o[2]=1;
			}
		}
		else{   // v1<v0
			if(vrt[2].z<vrt[1].z){ //v2<v1<v0
				tmp[0]=vrt[2];
				tmp[1]=vrt[1];
				tmp[2]=vrt[0];
				o[0]=2;
				o[1]=1;
				o[2]=0;
			}
			else if(vrt[2].z>vrt[0].z){ // v1<v0<v2
				tmp[0]=vrt[1];
				tmp[1]=vrt[0];
				tmp[2]=vrt[2];
				o[0]=1;
				o[1]=0;
				o[2]=2;
			}
			else{ //v1<v2<v0
				tmp[0]=vrt[1];
				tmp[1]=vrt[2];
				tmp[2]=vrt[0];
				o[0]=1;
				o[1]=2;
				o[2]=0;
			}
		}
		
		
		//clip near
		if(near){
			if(tmp[2].z<-1){ // all points are outside of clip plane
				return;
			}
			
			else if(tmp[0].z>-1){ //all points inside clip plane
			ClipAndDraw(raster, project,v0, v1, v2,false);
			}
			
			else if(tmp[1].z<-1){  //two points on outside one on inside
								//construct two triangles
				Vertex3D out[]=new Vertex3D[3];
				for(int i=0; i<3; i++){
					out[i]=new Vertex3D();
				}
				if(o[2]==0){	// vert[0] on inside
					out[2].x=evaluate(v2.z, v0.z, v2.x, v0.x, -1);
					out[2].y=evaluate(v2.z, v0.z, v2.y, v0.y, -1);
					out[2].z=evaluate(v2.z, v0.z, v2.z, v0.z, -1);
					out[2].w=evaluate(v2.z, v0.z, v2.w, v0.w, -1);
					out[2].r=evaluate(v2.z, v0.z, v2.r, v0.r, -1);
					out[2].g=evaluate(v2.z, v0.z, v2.g, v0.g, -1);
					out[2].b=evaluate(v2.z, v0.z, v2.b, v0.b, -1);
					
					out[1].x=evaluate(v1.z, v0.z, v1.x, v0.x, -1);
					out[1].y=evaluate(v1.z, v0.z, v1.y, v0.y, -1);
					out[1].z=evaluate(v1.z, v0.z, v1.z, v0.z, -1);
					out[1].w=evaluate(v1.z, v0.z, v1.w, v0.w, -1);
					out[1].r=evaluate(v1.z, v0.z, v1.r, v0.r, -1);
					out[1].g=evaluate(v1.z, v0.z, v1.g, v0.g, -1);
					out[1].b=evaluate(v1.z, v0.z, v1.b, v0.b, -1);
					
					out[0]=v0;	
				}
				else if(o[2]==1){ //vert[1] on inside
					out[0].x=evaluate(v0.z, v1.z, v0.x, v1.x, -1);
					out[0].y=evaluate(v0.z, v1.z, v0.y, v1.y, -1);
					out[0].z=evaluate(v0.z, v1.z, v0.z, v1.z, -1);
					out[0].w=evaluate(v0.z, v1.z, v0.w, v1.w, -1);
					out[0].r=evaluate(v0.z, v1.z, v0.r, v1.r, -1);
					out[0].g=evaluate(v0.z, v1.z, v0.g, v1.g, -1);
					out[0].b=evaluate(v0.z, v1.z, v0.b, v1.b, -1);
					
					out[2].x=evaluate(v2.z, v1.z, v2.x, v1.x, -1);
					out[2].y=evaluate(v2.z, v1.z, v2.y, v1.y, -1);
					out[2].z=evaluate(v2.z, v1.z, v2.z, v1.z, -1);
					out[2].w=evaluate(v2.z, v1.z, v2.w, v1.w, -1);
					out[2].r=evaluate(v2.z, v1.z, v2.r, v1.r, -1);
					out[2].g=evaluate(v2.z, v1.z, v2.g, v1.g, -1);
					out[2].b=evaluate(v2.z, v1.z, v2.b, v1.b, -1);
					
					out[1]=v1;	
				}
				else{ //vert[2] on inside
					out[0].x=evaluate(v0.z, v2.z, v0.x, v2.x, -1);
					out[0].y=evaluate(v0.z, v2.z, v0.y, v2.y, -1);
					out[0].z=evaluate(v0.z, v2.z, v0.z, v2.z, -1);
					out[0].w=evaluate(v0.z, v2.z, v0.w, v2.w, -1);
					out[0].r=evaluate(v0.z, v2.z, v0.r, v2.r, -1);
					out[0].g=evaluate(v0.z, v2.z, v0.g, v2.g, -1);
					out[0].b=evaluate(v0.z, v2.z, v0.b, v2.b, -1);
					
					out[1].x=evaluate(v1.z, v2.z, v1.x, v2.x, -1);
					out[1].y=evaluate(v1.z, v2.z, v1.y, v2.y, -1);
					out[1].z=evaluate(v1.z, v2.z, v1.z, v2.z, -1);
					out[1].w=evaluate(v1.z, v2.z, v1.w, v2.w, -1);
					out[1].r=evaluate(v1.z, v2.z, v1.r, v2.r, -1);
					out[1].g=evaluate(v1.z, v2.z, v1.g, v2.g, -1);
					out[1].b=evaluate(v1.z, v2.z, v1.b, v2.b, -1);
					
					out[2]=v2;	
					
				}
				Triangle done=new Triangle(out[0],out[1],out[2]);
				done.ClipAndDraw(raster, project,done.vert[0],done.vert[1],done.vert[2],false);
				//ClipAndDraw(raster, project,out[0],out[1],out[2],false);
				
			}
			else{	//two points on inside one on outside
					//construct one triangle
				Vertex3D out[]=new Vertex3D[3];
				for(int i=0; i<3; i++){
					out[i]=new Vertex3D();
				}
				if(o[0]==0){	// vert[0] on outside
					out[1].x=evaluate(v0.z, v2.z, v0.x, v2.x, -1);
					out[1].y=evaluate(v0.z, v2.z, v0.y, v2.y, -1);
					out[1].z=evaluate(v0.z, v2.z, v0.z, v2.z, -1);
					out[1].w=evaluate(v0.z, v2.z, v0.w, v2.w, -1);
					out[1].r=evaluate(v0.z, v2.z, v0.r, v2.r, -1);
					out[1].g=evaluate(v0.z, v2.z, v0.g, v2.g, -1);
					out[1].b=evaluate(v0.z, v2.z, v0.b, v2.b, -1);
					
					out[0].x=evaluate(v0.z, v1.z, v0.x, v1.x, -1);
					out[0].y=evaluate(v0.z, v1.z, v0.y, v1.y, -1);
					out[0].z=evaluate(v0.z, v1.z, v0.z, v1.z, -1);
					out[0].w=evaluate(v0.z, v1.z, v0.w, v1.w, -1);
					out[0].r=evaluate(v0.z, v1.z, v0.r, v1.r, -1);
					out[0].g=evaluate(v0.z, v1.z, v0.g, v1.g, -1);
					out[0].b=evaluate(v0.z, v1.z, v0.b, v1.b, -1);
					Triangle done1=new Triangle(v1,v2,out[1]);
					done1.ClipAndDraw(raster, project,done1.vert[0],done1.vert[1],done1.vert[2],false);
					Triangle done2=new Triangle(v1,out[1],out[0]);
					done2.ClipAndDraw(raster, project,done2.vert[0],done2.vert[1],done2.vert[2],false);
					
					
				}
				else if(o[0]==1){ //vert[1] on outside
					out[1].x=evaluate(v1.z, v0.z, v1.x, v0.x, -1);
					out[1].y=evaluate(v1.z, v0.z, v1.y, v0.y, -1);
					out[1].z=evaluate(v1.z, v0.z, v1.z, v0.z, -1);
					out[1].w=evaluate(v1.z, v0.z, v1.w, v0.w, -1);
					out[1].r=evaluate(v1.z, v0.z, v1.r, v0.r, -1);
					out[1].g=evaluate(v1.z, v0.z, v1.g, v0.g, -1);
					out[1].b=evaluate(v1.z, v0.z, v1.b, v0.b, -1);
					
					out[0].x=evaluate(v1.z, v2.z, v1.x, v2.x, -1);
					out[0].y=evaluate(v1.z, v2.z, v1.y, v2.y, -1);
					out[0].z=evaluate(v1.z, v2.z, v1.z, v2.z, -1);
					out[0].w=evaluate(v1.z, v2.z, v1.w, v2.w, -1);
					out[0].r=evaluate(v1.z, v2.z, v1.r, v2.r, -1);
					out[0].g=evaluate(v1.z, v2.z, v1.g, v2.g, -1);
					out[0].b=evaluate(v1.z, v2.z, v1.b, v2.b, -1);
					Triangle done1=new Triangle(out[1],v0,v2);
					done1.ClipAndDraw(raster, project,done1.vert[0],done1.vert[1],done1.vert[2],false);
					Triangle done2=new Triangle(v2,out[0],out[1]);
					done2.ClipAndDraw(raster, project,done2.vert[0],done2.vert[1],done2.vert[2],false);
					
					
				}
				else{ //vert[2] on outside
					out[1].x=evaluate(v2.z, v1.z, v2.x, v1.x, -1);
					out[1].y=evaluate(v2.z, v1.z, v2.y, v1.y, -1);
					out[1].z=evaluate(v2.z, v1.z, v2.z, v1.z, -1);
					out[1].w=evaluate(v2.z, v1.z, v2.w, v1.w, -1);
					out[1].r=evaluate(v2.z, v1.z, v2.r, v1.r, -1);
					out[1].g=evaluate(v2.z, v1.z, v2.g, v1.g, -1);
					out[1].b=evaluate(v2.z, v1.z, v2.b, v1.b, -1);
					
					out[0].x=evaluate(v2.z, v0.z, v2.x, v0.x, -1);
					out[0].y=evaluate(v2.z, v0.z, v2.y, v0.y, -1);
					out[0].z=evaluate(v2.z, v0.z, v2.z, v0.z, -1);
					out[0].w=evaluate(v2.z, v0.z, v2.w, v0.w, -1);
					out[0].r=evaluate(v2.z, v0.z, v2.r, v0.r, -1);
					out[0].g=evaluate(v2.z, v0.z, v2.g, v0.g, -1);
					out[0].b=evaluate(v2.z, v0.z, v2.b, v0.b, -1);
					Triangle done1=new Triangle(out[1],v1,v0);
					done1.ClipAndDraw(raster, project,done1.vert[0],done1.vert[1],done1.vert[2],false);
					Triangle done2=new Triangle(v0,out[0],out[1]);
					done2.ClipAndDraw(raster, project,done2.vert[0],done2.vert[1],done2.vert[2],false);
					
					
					
				}
				
				
				
			}
		}
		
		//clip far
		else{
			if(tmp[0].z>1){	// all points are outside of clip plane
				return;
			}
			else if(tmp[2].z<1){ // all  points inside clip plane
			
			for(int i=0; i<3; i++){
				vert[i] = project.transform(vrt[i]);
				vert[i].r=vrt[i].r;
				vert[i].g=vrt[i].g;
				vert[i].b=vrt[i].b;
			}
			
			
			Triangle done=new Triangle(vert[0],vert[1],vert[2]);
			done.Draw(raster);
			
			}
			else if(tmp[1].z<1){  //two points on inside one on outside
								  //construct two triangles
					Vertex3D out[]=new Vertex3D[3];
				for(int i=0; i<3; i++){
					out[i]=new Vertex3D();
				}
				if(o[2]==0){	// vert[0] on outside
					out[1].x=evaluate(v0.z, v2.z, v0.x, v2.x, 1);
					out[1].y=evaluate(v0.z, v2.z, v0.y, v2.y, 1);
					out[1].z=evaluate(v0.z, v2.z, v0.z, v2.z, 1);
					out[1].w=evaluate(v0.z, v2.z, v0.w, v2.w, 1);
					out[1].r=evaluate(v0.z, v2.z, v0.r, v2.r, 1);
					out[1].g=evaluate(v0.z, v2.z, v0.g, v2.g, 1);
					out[1].b=evaluate(v0.z, v2.z, v0.b, v2.b, 1);
					
					out[0].x=evaluate(v0.z, v1.z, v0.x, v1.x, 1);
					out[0].y=evaluate(v0.z, v1.z, v0.y, v1.y, 1);
					out[0].z=evaluate(v0.z, v1.z, v0.z, v1.z, 1);
					out[0].w=evaluate(v0.z, v1.z, v0.w, v1.w, 1);
					out[0].r=evaluate(v0.z, v1.z, v0.r, v1.r, 1);
					out[0].g=evaluate(v0.z, v1.z, v0.g, v1.g, 1);
					out[0].b=evaluate(v0.z, v1.z, v0.b, v1.b, 1);
					
					Vertex3D in[]=new Vertex3D[3];
					in[0]=out[1];
					in[1]=v1;
					in[2]=v2;
					for(int i=0; i<3; i++){
						vert[i] = project.transform(in[i]);
						vert[i].r=in[i].r;
						vert[i].g=in[i].g;
						vert[i].b=in[i].b;
					}
					Triangle done=new Triangle(vert[0],vert[1],vert[2]);
					done.Draw(raster);
					
					
					in[0]=out[1];
					in[1]=out[0];
					in[2]=v1;
					for(int i=0; i<3; i++){
						vert[i] = project.transform(in[i]);
						vert[i].r=in[i].r;
						vert[i].g=in[i].g;
						vert[i].b=in[i].b;
					}
					done=new Triangle(vert[0],vert[1],vert[2]);
					done.Draw(raster);
				}
				else if(o[2]==1){ //vert[1] on outside
					out[1].x=evaluate(v1.z, v0.z, v1.x, v0.x, 1);
					out[1].y=evaluate(v1.z, v0.z, v1.y, v0.y, 1);
					out[1].z=evaluate(v1.z, v0.z, v1.z, v0.z, 1);
					out[1].w=evaluate(v1.z, v0.z, v1.w, v0.w, 1);
					out[1].r=evaluate(v1.z, v0.z, v1.r, v0.r, 1);
					out[1].g=evaluate(v1.z, v0.z, v1.g, v0.g, 1);
					out[1].b=evaluate(v1.z, v0.z, v1.b, v0.b, 1);
					
					out[0].x=evaluate(v1.z, v2.z, v1.x, v2.x, 1);
					out[0].y=evaluate(v1.z, v2.z, v1.y, v2.y, 1);
					out[0].z=evaluate(v1.z, v2.z, v1.z, v2.z, 1);
					out[0].w=evaluate(v1.z, v2.z, v1.w, v2.w, 1);
					out[0].r=evaluate(v1.z, v2.z, v1.r, v2.r, 1);
					out[0].g=evaluate(v1.z, v2.z, v1.g, v2.g, 1);
					out[0].b=evaluate(v1.z, v2.z, v1.b, v2.b, 1);
	
					
					Vertex3D in[]=new Vertex3D[3];
					in[0]=out[1];
					in[1]=v2;
					in[2]=v0;
					for(int i=0; i<3; i++){
						vert[i] = project.transform(in[i]);
						vert[i].r=in[i].r;
						vert[i].g=in[i].g;
						vert[i].b=in[i].b;
					}
					Triangle done=new Triangle(vert[0],vert[1],vert[2]);
					done.Draw(raster);
					
					
					in[0]=out[0];
					in[1]=out[1];
					in[2]=v2;
					for(int i=0; i<3; i++){
						vert[i] = project.transform(in[i]);
						vert[i].r=in[i].r;
						vert[i].g=in[i].g;
						vert[i].b=in[i].b;
					}
					done=new Triangle(vert[0],vert[1],vert[2]);
					done.Draw(raster);
					
					
				}
				else{ //vert[2] on outside
					out[1].x=evaluate(v2.z, v1.z, v2.x, v1.x, 1);
					out[1].y=evaluate(v2.z, v1.z, v2.y, v1.y, 1);
					out[1].z=evaluate(v2.z, v1.z, v2.z, v1.z, 1);
					out[1].w=evaluate(v2.z, v1.z, v2.w, v1.w, 1);
					out[1].r=evaluate(v2.z, v1.z, v2.r, v1.r, 1);
					out[1].g=evaluate(v2.z, v1.z, v2.g, v1.g, 1);
					out[1].b=evaluate(v2.z, v1.z, v2.b, v1.b, 1);
					
					out[0].x=evaluate(v2.z, v0.z, v2.x, v0.x, 1);
					out[0].y=evaluate(v2.z, v0.z, v2.y, v0.y, 1);
					out[0].z=evaluate(v2.z, v0.z, v2.z, v0.z, 1);
					out[0].w=evaluate(v2.z, v0.z, v2.w, v0.w, 1);
					out[0].r=evaluate(v2.z, v0.z, v2.r, v0.r, 1);
					out[0].g=evaluate(v2.z, v0.z, v2.g, v0.g, 1);
					out[0].b=evaluate(v2.z, v0.z, v2.b, v0.b, 1);
					
					Vertex3D in[]=new Vertex3D[3];
					in[0]=v1;
					in[1]=out[1];
					in[2]=v0;
					for(int i=0; i<3; i++){
						vert[i] = project.transform(in[i]);
						vert[i].r=in[i].r;
						vert[i].g=in[i].g;
						vert[i].b=in[i].b;
					}
					Triangle done=new Triangle(vert[0],vert[1],vert[2]);
					done.Draw(raster);
					
					
					in[0]=out[1];
					in[1]=out[0];
					in[2]=v0;
					for(int i=0; i<3; i++){
						vert[i] = project.transform(in[i]);
						vert[i].r=in[i].r;
						vert[i].g=in[i].g;
						vert[i].b=in[i].b;
					}
					done=new Triangle(vert[0],vert[1],vert[2]);
					done.Draw(raster);
					
					
					
				}
				
				
				
			}
			else{				//two points on outside one on outside
								//makes one triangle
				Vertex3D out[]=new Vertex3D[3];
				for(int i=0; i<3; i++){
					out[i]=new Vertex3D();
				}
				if(o[0]==0){	// vert[0] on inside
					out[2].x=evaluate(v2.z, v0.z, v2.x, v0.x, 1);
					out[2].y=evaluate(v2.z, v0.z, v2.y, v0.y, 1);
					out[2].z=evaluate(v2.z, v0.z, v2.z, v0.z, 1);
					out[2].w=evaluate(v2.z, v0.z, v2.w, v0.w, 1);
					out[2].r=evaluate(v2.z, v0.z, v2.r, v0.r, 1);
					out[2].g=evaluate(v2.z, v0.z, v2.g, v0.g, 1);
					out[2].b=evaluate(v2.z, v0.z, v2.b, v0.b, 1);
					
					out[1].x=evaluate(v1.z, v0.z, v1.x, v0.x, 1);
					out[1].y=evaluate(v1.z, v0.z, v1.y, v0.y, 1);
					out[1].z=evaluate(v1.z, v0.z, v1.z, v0.z, 1);
					out[1].w=evaluate(v1.z, v0.z, v1.w, v0.w, 1);
					out[1].r=evaluate(v1.z, v0.z, v1.r, v0.r, 1);
					out[1].g=evaluate(v1.z, v0.z, v1.g, v0.g, 1);
					out[1].b=evaluate(v1.z, v0.z, v1.b, v0.b, 1);
					
					out[0]=v0;	
				}
				else if(o[0]==1){ //vert[1] on inside
					out[0].x=evaluate(v0.z, v1.z, v0.x, v1.x, 1);
					out[0].y=evaluate(v0.z, v1.z, v0.y, v1.y, 1);
					out[0].z=evaluate(v0.z, v1.z, v0.z, v1.z, 1);
					out[0].w=evaluate(v0.z, v1.z, v0.w, v1.w, 1);
					out[0].r=evaluate(v0.z, v1.z, v0.r, v1.r, 1);
					out[0].g=evaluate(v0.z, v1.z, v0.g, v1.g, 1);
					out[0].b=evaluate(v0.z, v1.z, v0.b, v1.b, 1);
					
					out[2].x=evaluate(v2.z, v1.z, v2.x, v1.x, 1);
					out[2].y=evaluate(v2.z, v1.z, v2.y, v1.y, 1);
					out[2].z=evaluate(v2.z, v1.z, v2.z, v1.z, 1);
					out[2].w=evaluate(v2.z, v1.z, v2.w, v1.w, 1);
					out[2].r=evaluate(v2.z, v1.z, v2.r, v1.r, 1);
					out[2].g=evaluate(v2.z, v1.z, v2.g, v1.g, 1);
					out[2].b=evaluate(v2.z, v1.z, v2.b, v1.b, 1);
					
					out[1]=v1;	
				}
				else{ //vert[2] on inside
					out[0].x=evaluate(v0.z, v2.z, v0.x, v2.x, 1);
					out[0].y=evaluate(v0.z, v2.z, v0.y, v2.y, 1);
					out[0].z=evaluate(v0.z, v2.z, v0.z, v2.z, 1);
					out[0].w=evaluate(v0.z, v2.z, v0.w, v2.w, 1);
					out[0].r=evaluate(v0.z, v2.z, v0.r, v2.r, 1);
					out[0].g=evaluate(v0.z, v2.z, v0.g, v2.g, 1);
					out[0].b=evaluate(v0.z, v2.z, v0.b, v2.b, 1);
					
					out[1].x=evaluate(v1.z, v2.z, v1.x, v2.x, 1);
					out[1].y=evaluate(v1.z, v2.z, v1.y, v2.y, 1);
					out[1].z=evaluate(v1.z, v2.z, v1.z, v2.z, 1);
					out[1].w=evaluate(v1.z, v2.z, v1.w, v2.w, 1);
					out[1].r=evaluate(v1.z, v2.z, v1.r, v2.r, 1);
					out[1].g=evaluate(v1.z, v2.z, v1.g, v2.g, 1);
					out[1].b=evaluate(v1.z, v2.z, v1.b, v2.b, 1);
					
					out[2]=v2;	
					
				}
				
				for(int i=0; i<3; i++){
				vert[i] = project.transform(out[i]);
				vert[i].r=out[i].r;
				vert[i].g=out[i].g;
				vert[i].b=out[i].b;
			}
			
			
			Triangle done=new Triangle(vert[0],vert[1],vert[2]);
			done.Draw(raster);
		
				
				
			}
		
		}      
		
		
    }
	
	// computes value by evaluating a line for zclipping
	public float evaluate(float z1, float z2, float p1, float p2, float zval){
		float slope, b;
		slope=(p2-p1)/(z2-z1);
		b=p2-slope*z2;
		float val=slope*zval+b;	
		return val;
	}
	
    public void setVertexList(Vertex3D list[])
    {
        vlist = list;
    }

    protected EdgeEqn edge[];
    protected float area;
    protected int xMin, xMax, yMin, yMax;
    protected float scale;
    private static byte sort[][] = {
        {0, 1}, {1, 2}, {0, 2}, {2, 0}, {2, 1}, {1, 0}
    };

    public void PlaneEqn(float eqn[], float p0, float p1, float p2)
    {
        float Ap, Bp, Cp;

        float sp0 = scale * p0;
        float sp1 = scale * p1;
        float sp2 = scale * p2;
        Ap = edge[0].A*sp2 + edge[1].A*sp0 + edge[2].A*sp1;
        Bp = edge[0].B*sp2 + edge[1].B*sp0 + edge[2].B*sp1;
        Cp = edge[0].C*sp2 + edge[1].C*sp0 + edge[2].C*sp1;
        eqn[0] = Ap;
        eqn[1] = Bp;
        eqn[2] = Ap*xMin + Bp*yMin + Cp;
    }

    protected boolean triangleSetup(Raster r)
    {
        if (edge == null) edge = new EdgeEqn[3];

        /*
            Compute the three edge equations
        */
        edge[0] = new EdgeEqn(vert[0], vert[1]);
        edge[1] = new EdgeEqn(vert[1], vert[2]);
        edge[2] = new EdgeEqn(vert[2], vert[0]);

        /*
            Trick #1: Orient edges so that the
            triangle's interior lies within all
            of their positive half-spaces.

            Assuring that the area is positive
            accomplishes this
        */
        area = edge[0].C + edge[1].C + edge[2].C;

        if (area == 0)
            return false;
            
        if (area < 0) {
            edge[0].flip();
            edge[1].flip();
            edge[2].flip();
            area = -area;
        }

        /*
            Trick #2: compute bounding box
        */
        int xflag = edge[0].flag + 2*edge[1].flag + 4*edge[2].flag;
        int yflag = (xflag >> 3) - 1;
        xflag = (xflag & 7) - 1;

        xMin = (int) (vert[sort[xflag][0]].x);
        xMax = (int) (vert[sort[xflag][1]].x + 1);
        yMin = (int) (vert[sort[yflag][1]].y);
        yMax = (int) (vert[sort[yflag][0]].y + 1);

        /*
            clip triangle's bounding box to raster
        */
        xMin = (xMin < 0) ? 0 : xMin;
        xMax = (xMax >= r.width) ? r.width - 1 : xMax;
        yMin = (yMin < 0) ? 0 : yMin;
        yMax = (yMax >= r.height) ? r.height - 1 : yMax;
        return true;
    }
    
    public void Draw(ZRaster raster)
    {
        float zPlane[] = new float[3];
        float rPlane[] = new float[3];
        float gPlane[] = new float[3];
        float bPlane[] = new float[3];

        if (!triangleSetup(raster)) return;
        scale = 1 / area;
        PlaneEqn(zPlane, vert[0].z, vert[1].z, vert[2].z);
        PlaneEqn(rPlane, r[0], r[1], r[2]);
        PlaneEqn(gPlane, g[0], g[1], g[2]);
        PlaneEqn(bPlane, b[0], b[1], b[2]);

        int x, y;
        float A0 = edge[0].A;        float B0 = edge[0].B;        float t0 = A0*xMin + B0*yMin + edge[0].C;
        float A1 = edge[1].A;        float B1 = edge[1].B;        float t1 = A1*xMin + B1*yMin + edge[1].C;
        float A2 = edge[2].A;        float B2 = edge[2].B;        float t2 = A2*xMin + B2*yMin + edge[2].C;
        float Az = zPlane[0];        float Bz = zPlane[1];        float tz = zPlane[2];
        float Ar = rPlane[0];        float Br = rPlane[1];        float tr = rPlane[2];
        float Ag = gPlane[0];        float Bg = gPlane[1];        float tg = gPlane[2];
        float Ab = bPlane[0];        float Bb = bPlane[1];        float tb = bPlane[2];

        yMin *= raster.width;
        yMax *= raster.width;

        /*
             .... scan convert triangle ....
        */
        for (y = yMin; y <= yMax; y += raster.width) {
	        float e0 = t0;
	        float e1 = t1;
	        float e2 = t2;
	        float r = tr;
	        float g = tg;
	        float b = tb;
	        float z = tz;
	        boolean beenInside = false;
	        for (x = xMin; x <= xMax; x++) {
	            if ((e0 >= 0) && (e1 >= 0) && (e2 >= 0)) {       // all 3 edges must be >= 0
	                int iz = (int) z;
	                if (iz <= raster.zbuff[y+x]) {
                        int pixr = (int) (255.0f*r);
	                    int pixg = (int) (255.0f*g);
	                    int pixb = (int) (255.0f*b);
                        pixr = ((pixr & ~255) == 0) ? pixr << 16 : ((r < 0)	? 0 : 255<<16);
                        pixg = ((pixg & ~255) == 0) ? pixg << 8  : ((g < 0)	? 0 : 255<<8);
                        pixb = ((pixb & ~255) == 0) ? pixb       : ((b < 0)	? 0 : 255);
		                raster.pixel[y+x] = (0xff000000 | pixr | pixg | pixb);
		                raster.zbuff[y+x] = iz;
		            }
		            beenInside = true;
	            } else if (beenInside) break;
	            e0 += A0;   e1 += A1;   e2 += A2;
	            z += Az;    r += Ar;    g += Ag;    b += Ab;
	        }
	        t0 += B0;   t1 += B1;   t2 += B2;
	        tz += Bz;   tr += Br;   tg += Bg;   tb += Bb;
        }
    }
	
	// draw on raster given 3 verticies
	public void Draw(ZRaster raster, Vertex3D v0, Vertex3D v1,Vertex3D v2)
    {
        float zPlane[] = new float[3];
        float rPlane[] = new float[3];
        float gPlane[] = new float[3];
        float bPlane[] = new float[3];

        if (!triangleSetup(raster)) return;
        scale = 1 / area;
        PlaneEqn(zPlane, v0.z, v1.z, v2.z);
        PlaneEqn(rPlane, v0.r, v1.r, v2.r);
        PlaneEqn(gPlane, v0.g, v1.g, v2.g);
        PlaneEqn(bPlane, v0.b, v1.b, v2.b);

        int x, y;
        float A0 = edge[0].A;        float B0 = edge[0].B;        float t0 = A0*xMin + B0*yMin + edge[0].C;
        float A1 = edge[1].A;        float B1 = edge[1].B;        float t1 = A1*xMin + B1*yMin + edge[1].C;
        float A2 = edge[2].A;        float B2 = edge[2].B;        float t2 = A2*xMin + B2*yMin + edge[2].C;
        float Az = zPlane[0];        float Bz = zPlane[1];        float tz = zPlane[2];
        float Ar = rPlane[0];        float Br = rPlane[1];        float tr = rPlane[2];
        float Ag = gPlane[0];        float Bg = gPlane[1];        float tg = gPlane[2];
        float Ab = bPlane[0];        float Bb = bPlane[1];        float tb = bPlane[2];

        yMin *= raster.width;
        yMax *= raster.width;

        /*
             .... scan convert triangle ....
        */
        for (y = yMin; y <= yMax; y += raster.width) {
	        float e0 = t0;
	        float e1 = t1;
	        float e2 = t2;
	        float r = tr;
	        float g = tg;
	        float b = tb;
	        float z = tz;
	        boolean beenInside = false;
	        for (x = xMin; x <= xMax; x++) {
	            if ((e0 >= 0) && (e1 >= 0) && (e2 >= 0)) {       // all 3 edges must be >= 0
	                int iz = (int) z;
	                if (iz <= raster.zbuff[y+x]) {
                        int pixr = (int) (255.0f*r);
	                    int pixg = (int) (255.0f*g);
	                    int pixb = (int) (255.0f*b);
                        pixr = ((pixr & ~255) == 0) ? pixr << 16 : ((r < 0)	? 0 : 255<<16);
                        pixg = ((pixg & ~255) == 0) ? pixg << 8  : ((g < 0)	? 0 : 255<<8);
                        pixb = ((pixb & ~255) == 0) ? pixb       : ((b < 0)	? 0 : 255);
		                raster.pixel[y+x] = (0xff000000 | pixr | pixg | pixb);
		                raster.zbuff[y+x] = iz;
		            }
		            beenInside = true;
	            } else if (beenInside) break;
	            e0 += A0;   e1 += A1;   e2 += A2;
	            z += Az;    r += Ar;    g += Ag;    b += Ab;
	        }
	        t0 += B0;   t1 += B1;   t2 += B2;
	        tz += Bz;   tr += Br;   tg += Bg;   tb += Bb;
        }
    }
}