import java.awt.Color; 
import java.lang.*;
import Vertex3D; 
import Matrix3D; 
import Surface;	
import ZRaster;	
 
//	Triangle.java -	based on code supplied by 6.837	instructors
//	Modified by	Bern Walker

//	Last revision -	11/21/98



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[]; 
 
	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 void	setSurface(Surface s) 
	{ 
		surface	= s; 
	} 
 
	public Surface getSurface()	
	{ 
		return surface;	
	} 
 
	public boolean isVisible() 
	{ 
		return (!culled); 
	} 
	 
	 
	/* 
		Methods	modified by	Bern Walker, 11/21/98
	*/ 
	public void	Illuminate(Light l[], int lights, Point3D eye, boolean cull) 
	{ 
		//	Calculate normal of	triangle
		float[]	normal = new float[3];
		float nsize;
		normal[0] =	vlist[v[0]].y* (vlist[v[1]].z -	vlist[v[2]].z)
					+vlist[v[1]].y * (vlist[v[2]].z	- vlist[v[0]].z)
					+vlist[v[2]].y * (vlist[v[0]].z	- vlist[v[1]].z);
		normal[1] =	vlist[v[0]].z *	(vlist[v[1]].x - vlist[v[2]].x)
					+vlist[v[1]].z * (vlist[v[2]].x	- vlist[v[0]].x)
					+vlist[v[2]].z * (vlist[v[0]].x	- vlist[v[1]].x);
		normal[2] =	vlist[v[0]].x *	(vlist[v[1]].y - vlist[v[2]].y)
					+vlist[v[1]].x * (vlist[v[2]].y	- vlist[v[0]].y)
					+vlist[v[2]].x * (vlist[v[0]].y	- vlist[v[1]].y);
		nsize =	(float)	Math.sqrt(normal[0]*normal[0] +	normal[1]*normal[1]
							+ normal[2]*normal[2]);
		for(int	i=0;i <	3;i++) normal[i] = normal[i]/nsize;	// Normalize the normal
		
		if (cull) {
		// Test	if normal of triangle pointed away from	eye	- cull if so.
			float test = normal[0]*(eye.x-vlist[v[0]].x)
						 + normal[1] * (eye.y -	vlist[v[0]].y)
						 + normal[2] * (eye.z -	vlist[v[0]].z);
			if (test <=	0) {
				culled = true;
				return;
			} else culled =	false;
		}
		
		// If it makes it this far,	set	the	vertices one at	a time,
		// according to	the	light list.
	   for (int	i =	0; i < 3; i++) { 
	   // For each vertice...
			for(int	j =	0;j	< l.length;	j++) {
			// ...step through each	light source in	turn.
				if (l[j].lightType == l[j].AMBIENT)	{
					// Basic diffuse ambient light - surface properties
					// times light properties
					r[i] +=	surface.r *	l[j].ir	* surface.ka; 
					g[i] +=	surface.g *	l[j].ig	* surface.ka; 
					b[i] +=	surface.b *	l[j].ib	* surface.ka; 
				} else if (l[j].lightType == l[j].DIRECTIONAL) {
					//calculate	the	dot	product	of the triangle	normal
					//and the vector to	the	lightsource.
					float dotprod =	normal[0]*(eye.x - l[j].x)
									+ normal[1]*(eye.y - l[j].y)
									+ normal[2]*(eye.z - l[j].z);
					r[i] +=	surface.r *	l[j].ir	* dotprod *	surface.kd;
					g[i] +=	surface.g *	l[j].ig	* dotprod *	surface.kd;
					b[i] +=	surface.b *	l[j].ib	* dotprod *	surface.kd;
				}
			}
		} 
	} 
	 
	public void	ClipAndDraw(ZRaster	raster,	Matrix3D project) 
	{ 
		if (culled)	{
			return;
			} else {
// Test	hither and yon for compliance
			Vertex3D[] result1 = new Vertex3D[4];
			Vertex3D[] result2 = new Vertex3D[5];
			int	first = -1;
			int	cnt	= 0;
			//Hither (z	> -1)
			
			for(int	m=0;m <2;m++) {
				if (vlist[v[m]].z >= -1) {
					if (first == -1) {
					    first = cnt;
					}
					result1[cnt]= vlist[v[m]];
					cnt++;
					if (vlist[v[m+1]].z	< -1) {
						float deltax=vlist[v[m+1]].x-vlist[v[m]].x;
						float deltay=vlist[v[m+1]].y-vlist[v[m]].y;
						float deltaz=vlist[v[m+1]].z-vlist[v[m]].z;
						float distance=(1 +	vlist[v[m]].z)/(vlist[v[m]].z -	vlist[v[m+1]].z);
						result1[cnt]= new Vertex3D(vlist[v[m]].x + deltax*distance,
												   vlist[v[m]].y + deltay*distance,
												   vlist[v[m]].z + deltaz*distance);
						cnt++;
					}
				} else {
				// Case: Out ==> in
					if (vlist[v[m+1]].z	>= -1) {
						if (first == -1) first = cnt;
						float deltax=vlist[v[m+1]].x-vlist[v[m]].x;
						float deltay=vlist[v[m+1]].y-vlist[v[m]].y;
						float deltaz=vlist[v[m+1]].z-vlist[v[m]].z;
						float distance=(-1 - vlist[v[m]].z)/(vlist[v[m+1]].z - vlist[v[m]].z);
						result1[cnt]= new Vertex3D(vlist[v[m]].x + deltax*distance,
												   vlist[v[m]].y + deltay*distance,
												   vlist[v[m]].z + deltaz*distance);
						cnt++;
					}

			    }
			if (vlist[v[2]].z >= -1) {
				if (first == -1) first = 0;
				result1[cnt]=vlist[v[2]];
				cnt++;
				if (vlist[v[0]].z <	-1)	{
					float deltax=vlist[v[0]].x-vlist[v[2]].x;
				    float deltay=vlist[v[0]].y-vlist[v[2]].y;
					float deltaz=vlist[v[0]].z-vlist[v[2]].z;
					float distance=(1 +	vlist[v[2]].z)/(vlist[v[2]].z -	vlist[v[0]].z);
					result1[cnt]= new Vertex3D(vlist[v[2]].x + deltax*distance,
											   vlist[v[2]].y + deltay*distance,
											   vlist[v[2]].z + deltaz*distance);
					cnt++;
				}
			} else {
					if (vlist[v[0]].z	>= -1) {
						if (first == -1) first = 0;
						float deltax=vlist[v[0]].x-vlist[v[2]].x;
						float deltay=vlist[v[0]].y-vlist[v[2]].y;
						float deltaz=vlist[v[0]].z-vlist[v[2]].z;
						float distance=(-1 - vlist[v[2]].z)/(vlist[v[0]].z - vlist[v[2]].z);
						result1[cnt]= new Vertex3D(vlist[v[2]].x + deltax*distance,
												   vlist[v[2]].y + deltay*distance,
												   vlist[v[2]].z + deltaz*distance);
						cnt++;
					}
			}
			
			// Yon z = 1
			first = -1;
			int cnt2 = 0; 
			for(m=0;m<(cnt -1);m++) {
				if (result1[m].z <= 1) {
					if (first == -1) first = cnt2;
					result2[cnt2]=result1[m];
					cnt2++;
					if (result1[m+1].z > 1) {
						float deltax=result1[m+1].x-result1[m].x;
						float deltay=result1[m+1].y-result1[m].y;
						float deltaz=result1[m+1].z-result1[m].z;
						float distance=(1 - result1[m].z)/(result1[m+1].z-result1[m].z);
						result2[cnt2]=new Vertex3D(result1[m].x+distance*deltax,
												   result1[m].y+distance*deltay,
												   result1[m].z+distance*deltaz);
						cnt2++;
					}
				} else {
					if (result1[m+1].z <= 1) {
						float deltax=result1[m+1].x-result1[m].x;
						float deltay=result1[m+1].y-result1[m].y;
						float deltaz=result1[m+1].z-result1[m].z;
						float distance=(result1[m].z-1)/(result1[m].z-result1[m+1].z);
						result2[cnt2]=new Vertex3D(result1[m].x+distance*deltax,
												   result1[m].y+distance*deltay,
												   result1[m].z+distance*deltaz);
						cnt2++;
					}
				}
			}
			
			if (result1[cnt-1].z <= 1) {
				if (first == -1) first = cnt2;
				result2[cnt2]=result1[cnt-1];
				cnt2++;
				if (result1[0].z > 1) {
					float deltax=result1[0].x-result1[cnt-1].x;
					float deltay=result1[0].y-result1[cnt-1].y;
					float deltaz=result1[0].z-result1[cnt-1].z;
					float distance=(1 - result1[cnt-1].z)/(result1[0].z-result1[cnt-1].z);
					result2[cnt2]=new Vertex3D(result1[cnt-1].x+distance*deltax,
											   result1[cnt-1].y+distance*deltay,
											   result1[cnt-1].z+distance*deltaz);
					cnt2++;
				}
			} else {
				if (result1[0].z <= 1) {
					float deltax=result1[0].x-result1[cnt-1].x;
					float deltay=result1[0].y-result1[cnt-1].y;
					float deltaz=result1[0].z-result1[cnt-1].z;
					float distance=(result1[cnt-1].z-1)/(result1[cnt-1].z-result1[0].z);
					result2[cnt2]=new Vertex3D(result1[cnt-1].x+distance*deltax,
											   result1[cnt-1].y+distance*deltay,
											   result1[cnt-1].z+distance*deltaz);
					cnt2++;
				}
			}
				
						
			//Skipping a bit, making triangles from	the	new	point list.
			//
			// I decompose the 4-5 point polygons I	may	obtain from	clipping
			// into	triangles by taking	3 points for one, then substituting	the	middle
			// vertex for an untouched one next	in line	for	a new triangle.
			
			vert[0]	= project.transform(result2[0]); 
			vert[1]	= project.transform(result2[1]); 
			vert[2]	= project.transform(result2[2]); 
			Draw(raster); 
			if (result2[3] == null){
			    return;
			    }else {
				vert[0]	= project.transform(result2[0]);
				vert[1]	= project.transform(result2[2]);
				vert[2]	= project.transform(result2[3]);
				Draw(raster);
				if (result2[4] == null)	{
				    return;
				    } else {
					vert[0]	= project.transform(result2[0]);
					vert[1]	= project.transform(result2[3]);
					vert[2]	= project.transform(result2[4]);
					Draw(raster);
			    }
			}
			}
			}
	}
	         
 


// And here, the vanilla code resumes....

	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; 
		} 
	} 
}