import java.awt.Color; import Vertex3D; import Matrix3D; import Surface; import ZRaster; 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[]; float nx, ny, nz; float ox, oy, oz; 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[4]; vert[0] = new Vertex3D(); vert[1] = new Vertex3D(); vert[2] = new Vertex3D(); scale = -1; culled = false; } public void setNormal(float xval, float yval, float zval) { float l = (float) (1 / Math.sqrt(xval*xval + yval*yval + zval*zval)); xval *= l; yval *= l; zval *= l; nx = xval; ny = yval; nz = zval; ox = nx; oy = ny; oz = nz; // original values never get changed // or used -- only used to get back to } public void setSurface(Surface s) { surface = s; } public Surface getSurface() { return surface; } public boolean isVisible() { return (!culled); } /* ... 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++) { //System.out.println("Vertex " + i + " is " + vlist[v[i]].toString()); //} float x=0, y=0, z=0; // The average normal across the triangle float eyex, eyey, eyez; // compute the direction TOWARDS the eye // therefore normal dot product should be // POSITIVE if we are NOT to cull the face // IF we are culling that is... float nx = (vlist[v[1]].z - vlist[v[0]].z) * (vlist[v[2]].y - vlist[v[1]].y) - (vlist[v[1]].y - vlist[v[0]].y) * (vlist[v[2]].z - vlist[v[1]].z) ; float ny = (vlist[v[1]].x - vlist[v[0]].x) * (vlist[v[2]].z - vlist[v[1]].z) - (vlist[v[1]].z - vlist[v[0]].z) * (vlist[v[2]].x - vlist[v[1]].x) ; float nz = (vlist[v[1]].y - vlist[v[0]].y) * (vlist[v[2]].x - vlist[v[1]].x) - (vlist[v[1]].x - vlist[v[0]].x) * (vlist[v[2]].y - vlist[v[1]].y) ; culled = false; if (cull) { for (int i = 0; i < 3; i++) { eyex = eye.x - vlist[v[i]].x; eyey = eye.y - vlist[v[i]].y; eyez = eye.z - vlist[v[i]].z; if ((eyex * nx + eyey * ny + eyez * nz) >= 0) { // Pointing away the viewer culled = true; //System.out.println(vlist[v[0]].toString()+vlist[v[1]].toString()+vlist[v[2]].toString()); //System.out.println("CULLED"); return; } } } //System.out.println(vlist[v[0]].toString()+vlist[v[1]].toString()+vlist[v[2]].toString()); //System.out.println("PASSED"); for (int i = 0; i < 3; i++) { r[i] = 0; g[i] = 0; b[i] = 0; } for (int ls = lights; ls-- > 0; ) { if(l[ls].lightType == Light.AMBIENT) { for (int i = 0; i < 3; i++) { r[i] += surface.r * surface.ka * l[ls].ir; g[i] += surface.g * surface.ka * l[ls].ig; b[i] += surface.b * surface.ka * l[ls].ib; } } else if(l[ls].lightType == Light.DIRECTIONAL) { for (int i = 0; i < 3; i++) { // Get the cosine of the angle to weight the reflection by x = l[ls].x * nx + l[ls].y * ny + l[ls].z * nz; // The light direction is FROM the surface TO the light // location. Thus, the dot product of the normal should // be positive. If not, the light makes no contribution. if(x <= 0) continue; // y = x ^ nshiney --- Phong Illum. for // specular reflection y = (float)Math.pow(x,surface.ns); y *= surface.ks; // Weight by shiney reflect x *= surface.kd; // Weight by diffuse reflect // Multiply by directional weight & light intensity // Basically, surface color times light intensity times // the sum of the diffuse and the shiney components r[i] += (surface.r * l[ls].ir) * (x + y); g[i] += (surface.g * l[ls].ig) * (x + y); b[i] += (surface.b * l[ls].ib) * (x + y); } } else if(l[ls].lightType == Light.POINT) { for (int i = 0; i < 3; i++) { // Get the cosine of the angle to weight the reflection by // NB: For the point light, we need to get the vector from // the light location to the vertex. Unlike the DIRECTIONAL // source which has x,y,z == normal vector x = l[ls].x - vlist[v[i]].x; y = l[ls].y - vlist[v[i]].y; z = l[ls].z - vlist[v[i]].z; // Normalize float tmp = ((float)(1/Math.sqrt(x*x+y*y+z*z))); x *= tmp; y *= tmp; z *= tmp; // Get the cosine of the angle x = x * nx + y * ny + z * nz; // The light direction is FROM the surface TO the light // location. Thus, the dot product of the normal should // be positive. If not, the light makes no contribution. if(x <= 0) continue; // y = x ^ nshiney - Phong Illum. for // specular reflection y = (float)Math.pow(x,surface.ns); y *= surface.ks; // Weight by shiney reflect x *= surface.kd; // Weight by diffuse reflect // Multiply by directional weight & light intensity // Basically, surface color times light intensity times // the sum of the diffuse and the shiney components r[i] += (surface.r * l[ls].ir) * (x + y); g[i] += (surface.g * l[ls].ig) * (x + y); b[i] += (surface.b * l[ls].ib) * (x + y); } } else { // Error! System.out.println("*********ERROR******** LIGHT TYPE " + l[ls].lightType); } } } float w0, w1, w2; public void ClipAndDraw(ZRaster raster, Matrix3D project) { vert[0] = (vlist[v[0]]); vert[1] = (vlist[v[1]]); vert[2] = (vlist[v[2]]); //System.out.println(vert[0].toString()+vert[1].toString()+vert[2].toString()); //project.transform(this,false); w0 = (vert[0].w > 0) ? vert[0].w : -vert[0].w; w1 = (vert[1].w > 0) ? vert[1].w : -vert[1].w; w2 = (vert[2].w > 0) ? vert[2].w : -vert[2].w; /* if (vert[0].z > w0 || vert[0].z < -w0 ){System.out.println("err0" + w0 + " " + vert[0].z);} if(vert[1].z > w1 || vert[1].z < -w1 ){System.out.println("err1" + w1 + " " + vert[1].z);} if(vert[2].z > w2 || vert[2].z < -w2) { System.out.println("err2" + w2 + " " + vert[2].z); } */ if (vert[0].z <= w0 && vert[0].z >= -w0 && vert[1].z <= w1 && vert[1].z >= -w1 && vert[2].z <= w2 && vert[2].z >= -w2) { vert[0] = project.transform(vlist[v[0]]); vert[1] = project.transform(vlist[v[1]]); vert[2] = project.transform(vlist[v[2]]); // Just draw, we are in bounds. Side clipping taken care of in Draw. /* System.out.println("DRAW"); System.out.println(vert[0].toString()+vert[1].toString()+vert[2].toString()); */ Draw(raster); } else { Vertex3D [] ref = Zclip(w0,w1,w2); // Null -- means that we are outside of the z planes if (ref == null) return; if (ref.length < 3) { System.out.println("***Got clipped to less than 3 vertices?!?"); return; } drawUp(ref, raster, project); } } private void drawUp(Vertex3D [] ref, ZRaster raster, Matrix3D project) // Chop up a polygon into triangles, and draw them up as we go { for(int i = 0; i < ref.length - 2; i++) { // Now this is a real hack. Because we cannot create a triangle // without adding to the vertex list, c'est la vie! So, we fake // each triangle by assigning their vertices to the CURRENT // triangle. Notice the colors of the vertices are not changed. // This is bad. vert[0] = ref[i ]; vert[1] = ref[i+1]; vert[2] = ref[i+2]; w0 = (vert[0].w > 0) ? vert[0].w : -vert[0].w; w1 = (vert[1].w > 0) ? vert[1].w : -vert[1].w; w2 = (vert[2].w > 0) ? vert[2].w : -vert[2].w; if (vert[0].z <= w0 && vert[0].z >= -w0 && vert[1].z <= w1 && vert[1].z >= -w1 && vert[2].z <= w2 && vert[2].z >= -w2) { vert[0] = project.transform(vert[0]); vert[1] = project.transform(vert[1]); vert[2] = project.transform(vert[2]); /* System.out.println("DRAWING ING ING"); System.out.println(vert[0].toString()+vert[1].toString()+vert[2].toString()); */ Draw(raster); } } } private Vertex3D[] Zclip(float w0, float w1, float w2) { Vertex3D [] workV = new Vertex3D[10]; Vertex3D [] vout = new Vertex3D[10]; float [] w = new float[4]; w[0] = w0; w[1] = w1; w[2] = w2; w[3] = w0; int idx = 0; workV[0] = vert[0]; workV[1] = vert[1]; workV[2] = vert[2]; workV[3] = vert[0]; /* for(int i = 0; i < 3; i++) { System.out.println("Vertex " + i + " is " + vert[i].toString()); } */ for(int i = 0; i < 3; i++) { if(workV[i].z > w[i]) { // Too far if(workV[i + 1].z > w[i+1]) { // Also too far // Nothing to do if both are too far } else if(workV[i + 1].z < -w[i+1]) { // Too near! Two points out vout[idx++] = nearside(workV[i], workV[i + 1], w[i], true); vout[idx++] = nearside(workV[i+1], workV[i], -w[i+1], false); } else { vout[idx++] = nearside(workV[i], workV[i + 1], w[i], true); } } else if(workV[i].z < -w[i]) { // Too near if(workV[i + 1].z < -w[i+1]) { // Also too near // Nothing to do if both are too near } else if(workV[i + 1].z > w[i+1]) { // Too far! 2 pts out. vout[idx++] = nearside(workV[i], workV[i + 1], -w[i], false); vout[idx++] = nearside(workV[i+1], workV[i], w[i+1],true); } else { vout[idx++] = nearside(workV[i], workV[i + 1], -w[i],false); } } else if(workV[i + 1].z > w[i+1]) { // Next one too far // Know current is inside vout[idx++] = workV[i]; vout[idx++] = nearside(workV[i+1], workV[i], w[i+1], true); } else if(workV[i + 1].z < -w[i+1]) { // Next one too near // Know current is inside vout[idx++] = workV[i]; vout[idx++] = nearside(workV[i+1], workV[i], -w[i+1], false); } else { // If both are inside, then just add the previous vertex vout[idx++] = workV[i]; } } /* for(int i = 0; i < 10; i++) { if(vout[i] == null) break; System.out.println("PostClip " + i + " is " + vout[i].toString()); } System.out.println("DISPLAYED POSTCLIP"); */ if (idx == 0) return null; workV = new Vertex3D[idx]; while(idx-- > 0) { workV[idx] = vout[idx]; } return workV; } /* private Vertex3D intersect(Vertex3D a, Vertex3D b) { Vertex3D c = new Vertex3D(a.x,a.y,a.z); c.copy(a); // All entries are a.w Vertex3D llb = new Vertex3D(lb.x*a.w,lb.y*a.w,lb.z*a.w); llb.w = a.w; Vertex3D lub = new Vertex3D(ub.x*a.w,ub.y*a.w,ub.z*a.w); lub.w = a.w; if(c.z < llb.z && llb.z < b.z) { c.w = szw*(-a.w-c.z); c.x += szx*(-a.w-c.z)*(c.w/a.w); c.y += szy*(-a.w-c.z)*(c.w/a.w); c.z = -c.w; } if(c.z > lub.z && lub.z > b.z) { c.w = szw*(lub.z-c.z); c.x += szx*(lub.z-c.z)*(c.w/lub.w); c.y += (lub.z-c.z)*(c.w/lub.w)*szy; c.z = c.w; } } } */ private Vertex3D nearside(Vertex3D p, Vertex3D q, float w,boolean far) // Return the in-between vertex which is on the z = 0 plane // First one is the outside one { // Basically, p.x - q.x / p.z - q.z == p.x - new.x / p.z - new.z // where new.z == 0 (parentheses are left to the reader to insert) Vertex3D nV = new Vertex3D(); if(!far) { if(q.z <= w) { System.out.println("ERROR " + w + " ... " + q.z); } nV.w = (((-p.w - p.z) * (q.w - p.w)) / (q.z - p.z)); nV.x = (((-p.w - p.z) * (q.x - p.x)) / (q.z - p.z))*(nV.w/p.w) + p.x; nV.y = (((-p.w - p.z) * (q.y - p.y)) / (q.z - p.z))*(nV.w/p.w) + p.y; nV.z = -nV.w; } else { if(q.z >= w) { System.out.println("ERROR " + w + " ... " + q.z); } nV.w = (((p.w - p.z) * (q.w - p.w)) / (q.z - p.z)); nV.x = (((p.w - p.z) * (q.x - p.x)) / (q.z - p.z))*(nV.w/p.w) + p.x; nV.y = (((p.w - p.z) * (q.y - p.y)) / (q.z - p.z))*(nV.w/p.w) + p.y; nV.z = nV.w; } //if(far) nV.z = w; else nV.z = -w; // Interpolate between the normals linearly. Then, renormalize. // This is a good guess at what the vertex normal should be. //nV.nx = ((p.z) * (q.nx - p.nx)) / (p.z - q.z) + p.nx; //nV.ny = ((p.z) * (q.ny - p.ny)) / (p.z - q.z) + p.ny; //nV.nz = ((p.z) * (q.nz - p.nz)) / (p.z - q.z) + p.nz; // Renormalize //float l = nV.nx * nV.nx + nV.ny * nV.ny + nV.nz * nV.nz; //l = (1f / ((float)Math.sqrt(l))); //nV.nx *= l; //nV.ny *= l; //nV.nz *= l; /* System.out.println("NEAR Vp " + p.toString() + "\nVq " + q.toString() + "\nnV " + nV.toString()); */ return nV; } private Vertex3D farside(Vertex3D p, Vertex3D q, float w) // Return the in-between vertex which is on the z = MAXZ plane { // Basically, p.x - q.x / p.z - q.z == p.x - new.x / p.z - new.z // where new.z == 0 (parentheses are left to the reader to insert) Vertex3D nV = new Vertex3D(); // Recall new z is 0 nV.x = ((p.z - ZRaster.MAXZ) * (q.x - p.x)) / (p.z - q.z) + p.x; nV.y = ((p.z - ZRaster.MAXZ) * (q.y - p.y)) / (p.z - q.z) + p.y; nV.z = ZRaster.MAXZ; nV.w = 1; // Interpolate between the normals linearly. Then, renormalize. // This is a good guess at what the vertex normal should be. nV.nx = ((p.z - ZRaster.MAXZ) * (q.nx - p.nx)) / (p.z - q.z) + p.nx; nV.ny = ((p.z - ZRaster.MAXZ) * (q.ny - p.ny)) / (p.z - q.z) + p.ny; nV.nz = ((p.z - ZRaster.MAXZ) * (q.nz - p.nz)) / (p.z - q.z) + p.nz; // Renormalize float l = nV.nx * nV.nx + nV.ny * nV.ny + nV.nz * nV.nz; l = (1f / ((float)Math.sqrt(l))); nV.nx *= l; nV.ny *= l; nV.nz *= l; /* System.out.println("FAR Vp " + p.toString() + "\nVq " + q.toString() + "\nnV " + nV.toString()); */ return nV; } 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; } } }