import GfxLib.*; import java.awt.*; /******************************************************* * * The Triangle class is an implementation of a * scan-converter. It can scan-convert any triangle, * and can interpolate the colors at the vertices of * these triangles * ******************************************************/ public class Triangle implements Drawable { private PlaneEqn m_planeEqn; private EdgeEqn[] m_edgeEqns; private Point3D[] m_vertices; private static final int sort[][] = { {0, 2, 1}, {1, 0, 2}, {0, 1, 2}, {2, 1, 0}, {2, 0, 1}, {1, 2, 0} }; public Triangle() { m_planeEqn = new PlaneEqn(); m_edgeEqns = new EdgeEqn[3]; m_vertices = new Point3D[3]; for (int i = 0; i < 3; i++) { m_edgeEqns[i] = new EdgeEqn(); m_vertices[i] = null; } } public Triangle(Point3D v0, Point3D v1, Point3D v2) { m_vertices = new Point3D[3]; m_vertices[0] = v0; m_vertices[1] = v1; m_vertices[2] = v2; m_edgeEqns = new EdgeEqn[3]; m_edgeEqns[0] = new EdgeEqn(v0, v1); m_edgeEqns[1] = new EdgeEqn(v1, v2); m_edgeEqns[2] = new EdgeEqn(v2, v0); //System.out.println("Initialized vertices: " + v0 + ", " + v1 + ", " + v2); m_planeEqn = new PlaneEqn(m_edgeEqns); } public void reset(Point3D v0, Point3D v1, Point3D v2) { m_vertices[0] = v0; m_vertices[1] = v1; m_vertices[2] = v2; m_edgeEqns[0].reset(v0, v1); m_edgeEqns[1].reset(v1, v2); m_edgeEqns[2].reset(v2, v0); m_planeEqn.reset(m_edgeEqns); } public void Draw(Raster raster) { // // Check error conditions: // for (int i = 0; i < 3; i++) { if (Float.isNaN(m_vertices[i].x)) return; if (Float.isNaN(m_vertices[i].y)) return; if (Float.isNaN(m_vertices[i].z)) return; if (Float.isInfinite(m_vertices[i].x)) return; if (Float.isInfinite(m_vertices[i].y)) return; if (Float.isInfinite(m_vertices[i].z)) return; } //****************************************************** // // Plane Equation Variables // //****************************************************** // Each plane equation is of the form Ax + By + C. // These variables store the coefficients of the // plane equations for the red, green, blue, and alpha // components of color // int Aa, Ar, Ag, Ab, Az; int Ba, Br, Bg, Bb, Bz; int Ca, Cr, Cg, Cb, Cz; // // Current color components. These are incrementally // updated based on the above Plane Equation Variables int a, r, g, b, z; int v0_color, v1_color, v2_color; int v0_z, v1_z, v2_z; // // The raster's pixel array int[] pixels; int[] zBuffer; // // int offset, offset_l, offset_r; int sz; //****************************************************** // // Edge-walking Variables // //****************************************************** // // Integer arrays to store the left and right edges of the triangle, // respectively. The value stored is the integer value closest to // the edge of the triangle, but inside the triangle. The values // are stored from top to bottom, such that xl_pts[0] represents // the x-coordinate of the left edges at the highest y-coordinate // in the triangle. Each subsequent element of the array represents // the x-coordinate at the next scan line. // int[] xl_pts, xr_pts; // // The vertices of this Triangle, sorted by y-coordinate Point3D v1_y, v2_y, v3_y; // // The slope of the left and right edges of the triangle, repsectively float m1, m2; // // A flag used in sorting this Triangle's vertices int yflag; /****************************************************** * * SCAN CONVERSION * * The triangle is scan-converted in 2 steps: * * Step #1: Calculate the pixel values representing the * edges of the triangle. This is done by calculating * the ideal x-coordinate at each scan line, and then * converting it to the integer value inside the * triangle which is closest to the edge * * Step #2: Scan convert the area between the calculated * edges, using plane equations to interpolate the * colors between the vertices * ***************************************************/ //******************************************************* // // STEP 1: Calculate the pixel values of the Triangle's edges // //******************************************************* // // Sort the vertices of the Triangle yflag = 0; if (m_vertices[0].y > m_vertices[1].y) yflag |= 1; if (m_vertices[1].y > m_vertices[2].y) yflag |= 2; if (m_vertices[2].y > m_vertices[0].y) yflag |= 4; yflag--; if (yflag < 0) // triangle has 3 colinear pts. { yflag = 1; } v1_y = m_vertices[sort[yflag][2]]; // The top of the triangle v2_y = m_vertices[sort[yflag][1]]; // The midpoint of the triange v3_y = m_vertices[sort[yflag][0]]; // The bottom of the triangle // // Calculate the slopes of the left and right edges m1 = ((v1_y.x - v2_y.x)/(v2_y.y - v1_y.y)); // The left edge m2 = ((v1_y.x - v3_y.x)/(v3_y.y - v1_y.y)); // The right edge // // Create arrays to hold the pixel values of the edges sz = (int)(v3_y.y) - ((int)(Math.ceil(v1_y.y))); if (sz < 0) // No integer pixels are within the triangle { return; } else { xl_pts = new int[sz + 1]; xr_pts = new int[sz + 1]; } // // Calculate the left and right edges for each triangle. // Note that there are 3 cases to account for: // flat-topped, flat-bottomed, and everything else. // // // Case #1: Flat-topped triangle // if (Math.ceil(v1_y.y) == Math.ceil(v2_y.y)) { if ((int)v2_y.y == (int)v3_y.y) return; else { if (v1_y.x < v2_y.x) { offset_l = makeBoundary(xl_pts, 0, v1_y.x, v1_y.y, v3_y.x, v3_y.y, true); offset_r = makeBoundary(xr_pts, 0, v2_y.x, v2_y.y, v3_y.x, v3_y.y, false); } else { offset_l = makeBoundary(xl_pts, 0, v2_y.x, v2_y.y, v3_y.x, v3_y.y, true); offset_r = makeBoundary(xr_pts, 0, v1_y.x, v1_y.y, v3_y.x, v3_y.y, false); } offset = offset_l; } } // // Case #2: Flat-bottom triangle // else if ((int)v2_y.y == (int)v3_y.y) { if (v2_y.x < v3_y.x) { offset_l = makeBoundary(xl_pts, 0, v1_y.x, v1_y.y, v2_y.x, v2_y.y, true); offset_r = makeBoundary(xr_pts, 0, v1_y.x, v1_y.y, v3_y.x, v3_y.y, false); } else { offset_l = makeBoundary(xl_pts, 0, v1_y.x, v1_y.y, v3_y.x, v3_y.y, true); offset_r = makeBoundary(xr_pts, 0, v1_y.x, v1_y.y, v2_y.x, v2_y.y, false); } offset = offset_l; } // // Case #3: All other triangles // else { if (m1 > m2) { offset_l = makeBoundary(xl_pts, 0, v1_y.x, v1_y.y, v2_y.x, v2_y.y, true); offset_r = makeBoundary(xr_pts, 0, v1_y.x, v1_y.y, v3_y.x, v3_y.y, false); offset = makeBoundary(xl_pts, (((int)Math.ceil(v2_y.y)) - ((int)Math.ceil(v1_y.y))), v2_y.x, v2_y.y, v3_y.x, v3_y.y, true); } else { offset_l = makeBoundary(xl_pts, 0, v1_y.x, v1_y.y, v3_y.x, v3_y.y, true); offset_r = makeBoundary(xr_pts, 0, v1_y.x, v1_y.y, v2_y.x, v2_y.y, false); offset = makeBoundary(xr_pts, (((int)Math.ceil(v2_y.y)) - ((int)Math.ceil(v1_y.y))), v2_y.x, v2_y.y, v3_y.x, v3_y.y, false); } } //******************************************************* // // STEP 2: SCAN CONVERT TRIANGLE // //******************************************************* // // Initalize plane equations for interpolation // v0_color = m_vertices[0].argb; v0_z = (int)(m_vertices[0].z * (1 << GfxLibDefs.FRACTBITS)); v1_color = m_vertices[1].argb; v1_z = (int)(m_vertices[1].z * (1 << GfxLibDefs.FRACTBITS)); v2_color = m_vertices[2].argb; v2_z = (int)(m_vertices[2].z * (1 << GfxLibDefs.FRACTBITS)); m_planeEqn.computeEqns(v0_color, v1_color, v2_color, v0_z, v1_z, v2_z, (float)xl_pts[0], (float)Math.ceil(v1_y.y)); // // If all vertices are the same color, we do not need to interpolate. // We call the more efficient flatDraw() method // if ((v0_color == v1_color) && (v1_color == v2_color)) { flatDraw(raster, xl_pts, xr_pts, ((int)Math.ceil(v1_y.y)), v0_color, offset); return; } Aa = m_planeEqn.alpha[0]; Ar = m_planeEqn.red[0]; Ag = m_planeEqn.green[0]; Ab = m_planeEqn.blue[0]; Az = m_planeEqn.z[0]; Ba = m_planeEqn.alpha[1]; Br = m_planeEqn.red[1]; Bg = m_planeEqn.green[1]; Bb = m_planeEqn.blue[1]; Bz = m_planeEqn.z[1]; Ca = m_planeEqn.alpha[2]; Cr = m_planeEqn.red[2]; Cg = m_planeEqn.green[2]; Cb = m_planeEqn.blue[2]; Cz = m_planeEqn.z[2]; //System.out.println("Tri4: " ); // // Set the initial values for the alpha, red, green, and blue // planes. a = Ca; r = Cr; g = Cg; b = Cb; /* * NEW ZBUFFER CODE! */ z = Cz; // // Fill the pixel array with colors based on the plane // equations created above // // // Declare temporary variables int aTmp, rTmp, gTmp, bTmp, zTmp; int y, xlp, xrp; int pixa, pixr, pixg, pixb; int rasterWidth, rasterHeight, maxIndex; // // Alias the Raster's pixel array for fast access pixels = raster.getPixels(); rasterWidth = raster.getWidth(); rasterHeight = raster.getHeight(); maxIndex = rasterWidth * rasterHeight; /* * NEW ZBUFFER CODE! */ zBuffer = raster.getZBuffer(); y = ((int)(Math.ceil(v1_y.y))) * rasterWidth; for (int pt = 0; pt < offset; pt++) { xlp = xl_pts[pt]; xrp = xr_pts[pt]; //System.out.println("Scan converting... " + xlp + ", " + xrp + ", " +y); // // Perform clipping // if ((xrp < 0) || (xlp > rasterWidth) || (y < 0) || (y >= maxIndex)) { } else { if (xlp < 0) { int xlDiff = -xlp; aTmp = a + Aa * xlDiff; bTmp = b + Ab * xlDiff; gTmp = g + Ag * xlDiff; rTmp = r + Ar * xlDiff; zTmp = z + Az * xlDiff; xlp = 0; } else { aTmp = a; rTmp = r; gTmp = g; bTmp = b; zTmp = z; } if (xrp > raster.getWidth()) { xrp = raster.getWidth() - 1; } for (int k = y + xlp; k <= y + xrp; k++) { pixa = (aTmp >> GfxLibDefs.FRACTBITS); pixr = (rTmp >> GfxLibDefs.FRACTBITS); pixg = (gTmp >> GfxLibDefs.FRACTBITS); pixb = (bTmp >> GfxLibDefs.FRACTBITS); pixa = ((pixa & ~255) == 0) ? pixa << 24 : ((aTmp < 0) ? 0 : 0xff000000); pixr = ((pixr & ~255) == 0) ? pixr << 16 : ((rTmp < 0) ? 0 : 0x00ff0000); pixg = ((pixg & ~255) == 0) ? pixg << 8 : ((gTmp < 0) ? 0 : 0x0000ff00); pixb = ((pixb & ~255) == 0) ? pixb : ((bTmp < 0) ? 0 : 0x000000ff); if (zBuffer[k] > z) { pixels[k] = (pixa | pixr | pixg| pixb); zBuffer[k] = z; } aTmp += Aa; rTmp += Ar; gTmp += Ag; bTmp += Ab; zTmp += Az; } // for (int k = y * ... } // if ( ...clipped...) else { if ((pt + 1) == xl_pts.length) break; float tmp = xl_pts[pt + 1] - xl_pts[pt]; a += Ba + (Aa * tmp); r += Br + (Ar * tmp); g += Bg + (Ag * tmp); b += Bb + (Ab * tmp); z += Bz + (Az * tmp); y += rasterWidth; } } // // Scan-converts a triangle with no interpolation private void flatDraw(Raster raster, int[] xl_pts, int[] xr_pts, int yMin, int color, int offset) { // // Declare temporary variables int y, yMax, xlp, xrp; int[] pixels, zBuffer; int rasterHeight, rasterWidth; int Az, Bz, Cz, z; int zTmp; Az = m_planeEqn.z[0]; Bz = m_planeEqn.z[1]; Cz = m_planeEqn.z[2]; z = Cz; // // Alias the Raster's pixel array for fast access pixels = raster.getPixels(); rasterWidth = raster.getWidth(); rasterHeight = raster.getHeight(); zBuffer = raster.getZBuffer(); yMax = yMin + offset; y = yMin * rasterWidth; for (int pt = 0; pt < offset; pt++) { xlp = xl_pts[pt]; xrp = xr_pts[pt]; zTmp = z; if (xlp < 0) xlp = 0; if (xrp >= rasterWidth) xrp = rasterWidth-1; xlp+=y; xrp+=y; for (int k = xlp; k <= xrp; k++) { if ((k < 0) || (k>= rasterWidth * rasterHeight)) { } else { if (zBuffer[k] > zTmp) { pixels[k] = color; zBuffer[k] = zTmp; } } zTmp += Az; } y += rasterWidth; if ((pt + 1) >= xl_pts.length) break; z += Bz + (Az * (xl_pts[pt + 1] - xl_pts[pt])); } } private int makeBoundary(int[] boundary, int offset, float x_start, float y_start, float x_end, float y_end, boolean isLeft) { float b, m_inv, x; int y_scan; m_inv = (x_end-x_start) / (y_end-y_start); b = x_start - (m_inv * y_start); y_scan = (int)((Math.ceil(y_start))); x = m_inv * y_scan + b; for (int offset_end = (offset + ((int)y_end) - y_scan); offset_end >= offset; offset++) { //if (isLeft) boundary[offset] = (int)(Math.ceil(x)); if (isLeft) boundary[offset] = x > (int)x ? (int)(x+1) : (int)x; else boundary[offset] = (int)x; x += m_inv; } return offset; } /* private int makeBoundary(int[] boundary, int offset, float x_start, float y_start, float x_end, float y_end, boolean isLeft) { int x, y, b, m_inv; m_inv = (int)(((x_end - x_start)/(y_end - y_start)) * (1 << GfxLibDefs.FRACTBITS)); y = (int)(y_start * (1 << GfxLibDefs.FRACTBITS)); x = (int)(x_start * (1 << GfxLibDefs.FRACTBITS)); b = (int)((x_start - (((x_end - x_start)/(y_end - y_start)) * y_start)) * (1 << GfxLibDefs.FRACTBITS)); int y_scan = (int)((Math.ceil(y_start))); //System.out.println("m, y, x, b, ys: "+ m_inv + ", " + y + ", " + x + ", " + b + ", " + y_scan); x = m_inv * y_scan + b; for (int offset_end = (offset + ((int)y_end) - y_scan); offset_end >= offset; offset++) { boundary[offset] = x >> GfxLibDefs.FRACTBITS; if (isLeft) { if ((x & 4096) != 0) boundary[offset]++; } x += m_inv; } return offset; } */ } class EdgeEqn { public int A, B, C, M; public int flag; public EdgeEqn() {} public EdgeEqn(Point3D v0, Point3D v1) { double a = v0.y - v1.y; double b = v1.x - v0.x; double c = -0.5f*(a*(v0.x + v1.x) + b*(v0.y + v1.y)); double m = (-a)/b; A = (int)(a * (1 << GfxLibDefs.FRACTBITS)); B = (int)(b * (1 << GfxLibDefs.FRACTBITS)); C = (int)(c * (1 << GfxLibDefs.FRACTBITS)); M = (int)(m * (1 << GfxLibDefs.FRACTBITS)); flag = 0; if (A >= 0) flag+=8; if (B >= 0) flag++; } public void reset(Point3D v0, Point3D v1) { double a = v0.y - v1.y; double b = v1.x - v0.x; double c = -0.5f*(a*(v0.x + v1.x) + b*(v0.y + v1.y)); double m = (-a)/b; A = (int)(a * (1 << GfxLibDefs.FRACTBITS)); B = (int)(b * (1 << GfxLibDefs.FRACTBITS)); C = (int)(c * (1 << GfxLibDefs.FRACTBITS)); M = (int)(m * (1 << GfxLibDefs.FRACTBITS)); flag = 0; if (A >= 0) flag+=8; if (B >= 0) flag++; } public void flip() { A = -A; B = -B; C = -C; } public int evaluate(int x, int y) { return (A*x + B*y + C); } } class PlaneEqn { public int[] alpha; public int[] red; public int[] green; public int[] blue; public int[] z; private EdgeEqn[] edges; private double area; private double scale; private double sp0, sp1, sp2; public PlaneEqn() { this.alpha = new int[3]; this.red = new int[3]; this.green = new int[3]; this.blue = new int[3]; this.z = new int[3]; } public PlaneEqn(EdgeEqn[] edges) { this.edges = edges; this.alpha = new int[3]; this.red = new int[3]; this.green = new int[3]; this.blue = new int[3]; this.z = new int[3]; area = edges[0].C + edges[1].C + edges[2].C; if (area < 0) { edges[0].flip(); edges[1].flip(); edges[2].flip(); area = -area; } scale = (1 << GfxLibDefs.FRACTBITS) / ((double) area); } public void reset(EdgeEqn[] edges) { this.edges = edges; area = edges[0].C + edges[1].C + edges[2].C; if (area < 0) { edges[0].flip(); edges[1].flip(); edges[2].flip(); area = -area; } scale = (1 << GfxLibDefs.FRACTBITS) / ((double) area); } public void computeEqns(int p0, int p1, int p2, int z0, int z1, int z2, float xMin, float yMin) { ComputeEqn(blue, p0 & 255, p1 & 255, p2 & 255, xMin, yMin); p0 >>= 8; p1 >>= 8; p2 >>= 8; ComputeEqn(green, p0 & 255, p1 & 255, p2 & 255, xMin, yMin); p0 >>= 8; p1 >>= 8; p2 >>= 8; ComputeEqn(red, p0 & 255, p1 & 255, p2 & 255, xMin, yMin); p0 >>= 8; p1 >>= 8; p2 >>= 8; ComputeEqn(alpha, p0 & 255, p1 & 255, p2 & 255, xMin, yMin); ComputeEqn(z, z0, z1, z2, xMin, yMin); } // // Inline this for speed? private final void ComputeEqn(int[] eqn, int p0, int p1, int p2, float xMin, float yMin) { int Ap, Bp, Cp; sp0 = scale * p0; sp1 = scale * p1; sp2 = scale * p2; Ap = (int)(edges[0].A*sp2 + edges[1].A*sp0 + edges[2].A*sp1); Bp = (int)(edges[0].B*sp2 + edges[1].B*sp0 + edges[2].B*sp1); Cp = (int)(edges[0].C*sp2 + edges[1].C*sp0 + edges[2].C*sp1); eqn[0] = Ap; eqn[1] = Bp; eqn[2] = (int)(Ap*xMin) + (int)(Bp*yMin) + Cp + (1 << (GfxLibDefs.FRACTBITS - 1)); } }