/************************* * Duncan Bryce * * 6.837 Project #2 * * TA Jacob Schwartz * ************************/ 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 EdgeEqn[] m_edges; private PlaneEqn m_planeEqn; private Vertex2D[] 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(Vertex2D v0, Vertex2D v1, Vertex2D v2) { m_vertices = new Vertex2D[3]; m_vertices[0] = v0; m_vertices[1] = v1; m_vertices[2] = v2; m_edges = new EdgeEqn[3]; m_edges[0] = new EdgeEqn(v0, v1); m_edges[1] = new EdgeEqn(v1, v2); m_edges[2] = new EdgeEqn(v2, v0); m_planeEqn = new PlaneEqn(m_vertices, m_edges); } public void Draw(Raster raster) { //****************************************************** // // 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; int Ba, Br, Bg, Bb; int Ca, Cr, Cg, Cb; // // Current color components. These are incrementally // updated based on the above Plane Equation Variables int a, r, g, b; int v0_color, v1_color, v2_color; // // The raster's pixel array int[] pixels; // // 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 Vertex2D 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--; 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; v1_color = m_vertices[1].argb; v2_color = m_vertices[2].argb; // // 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; } m_planeEqn.computeEqns(v0_color, v1_color, v2_color, (float)xl_pts[0], (float)Math.ceil(v1_y.y)); Aa = m_planeEqn.alpha[0]; Ar = m_planeEqn.red[0]; Ag = m_planeEqn.green[0]; Ab = m_planeEqn.blue[0]; Ba = m_planeEqn.alpha[1]; Br = m_planeEqn.red[1]; Bg = m_planeEqn.green[1]; Bb = m_planeEqn.blue[1]; Ca = m_planeEqn.alpha[2]; Cr = m_planeEqn.red[2]; Cg = m_planeEqn.green[2]; Cb = m_planeEqn.blue[2]; // // Set the initial values for the alpha, red, green, and blue // planes. a = Ca; r = Cr; g = Cg; b = Cb; // // Fill the pixel array with colors based on the plane // equations created above // // // Declare temporary variables int aTmp, rTmp, gTmp, bTmp; int y, xlp, xrp; int pixa, pixr, pixg, pixb; // // Alias the Raster's pixel array for fast access pixels = raster.getPixels(); for (int pt = 0; pt < offset; pt++) { xlp = xl_pts[pt]; xrp = xr_pts[pt]; y = ((int)(Math.ceil(v1_y.y))) + pt; aTmp = a; rTmp = r; gTmp = g; bTmp = b; for (int z = y * raster.getWidth() + xlp; z <= y * raster.getWidth() + xrp; z++) { pixa = (aTmp >> Ps2Defs.FRACTBITS); pixr = (rTmp >> Ps2Defs.FRACTBITS); pixg = (gTmp >> Ps2Defs.FRACTBITS); pixb = (bTmp >> Ps2Defs.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); pixels[z] = (pixa | pixr | pixg| pixb); aTmp += Aa; rTmp += Ar; gTmp += Ag; bTmp += Ab; } if ((pt + 1) == xl_pts.length) break; a += Ba + (Aa * (xl_pts[pt + 1] - xlp)); r += Br + (Ar * (xl_pts[pt + 1] - xlp)); g += Bg + (Ag * (xl_pts[pt + 1] - xlp)); b += Bb + (Ab * (xl_pts[pt + 1] - xlp)); } } // // 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, xlp, xrp; int[] pixels; int rasterWidth; // // Alias the Raster's pixel array for fast access pixels = raster.getPixels(); rasterWidth = raster.getWidth(); // // Initialize offset in the raster y = yMin * rasterWidth; for (int pt = 0; pt < offset; pt++) { xlp = y + xl_pts[pt]; xrp = y + xr_pts[pt]; for (int z = xlp; z <= xrp; z++) { pixels[z] = color; } y += rasterWidth; } } private int makeBoundary(int[] boundary, int offset, float x_start, float y_start, float x_end, float y_end, boolean isLeft) { float dx_l; float dy_l; float x, y, b, m_inv; dx_l = x_end - x_start; dy_l = y_end - y_start; m_inv = dx_l / dy_l; y = y_start; x = x_start; b = x - (m_inv * y); int y_scan = (int)((Math.ceil(y))); for (int offset_end = (offset + ((int)y_end) - ((int)Math.ceil(y))); offset_end >= offset; offset++) { x = m_inv * y_scan + b; if (isLeft) { boundary[offset] = (int)(Math.ceil(x)); } else { boundary[offset] = (int)x; } y_scan++; } return offset; } } class EdgeEqn { public int A, B, C, M; public int flag; public EdgeEqn(Vertex2D v0, Vertex2D 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 << Ps2Defs.FRACTBITS)); B = (int)(b * (1 << Ps2Defs.FRACTBITS)); C = (int)(c * (1 << Ps2Defs.FRACTBITS)); M = (int)(m * (1 << Ps2Defs.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; private Vertex2D[] vert; private EdgeEqn[] edges; private double area; private double scale; private double sp0, sp1, sp2; public PlaneEqn(Vertex2D[] vertices, EdgeEqn[] edges) { int Ap, Bp, Cp; this.edges = edges; this.vert = vertices; this.alpha = new int[3]; this.red = new int[3]; this.green = new int[3]; this.blue = 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 << Ps2Defs.FRACTBITS) / ((double) area); } public void computeEqns(int p0, int p1, int p2, 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); } 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 << (Ps2Defs.FRACTBITS - 1)); } }