// Stephanie Hong

/* This is triangle scan converter that uses an edge-walking approach
both for calculating triangle edges and for color
interpolation.. (Edge-walking rasterizers proceeds from the top-most
vertex, and scan convert from top to bottom. They keep track of the
two active edges which determine the current span.)

/* NOTE: I think it's odd that the center of the first pixel is
represented by (0.0,0.0)...  How are all the points between the very
corner of the screen & the center of that pixel represented?
Shouldn't the center of the first pixel be (0.5,0.5)???  */

/* NOTE: This is some of the most un-elegant, un-modular code I've
   written in a while; some of the basic optimizations / improvements
   I would've liked to do are noted in comments.*/

import Drawable;
import Vertex2D;
import java.lang.Math.*;

class Triangle implements Drawable {
    protected Vertex2D v[];

    public Triangle() {
    }

    public Triangle(Vertex2D v0, Vertex2D v1, Vertex2D v2) {
      // NOTE:  Assumes only valid triangles are specified.
        v = new Vertex2D[3];
        v[0] = v0;
        v[1] = v1;
        v[2] = v2;
    }
    
    public void Draw(Raster r) {
      int flag;               // Provides breakpoint info (see Sort method).
      flag = this.Sort(v);    // Sort the vertices by y-coordinate (top to bottom).
      this.FillColor(r, v, flag);  // Fill in the triangle, via edge-walking.
      //this.FillSimple(r, v, flag);
    }

  private void FillColor(Raster r, Vertex2D a[], int breakpt) {
    int y, yEnd, xStart, xEnd;
    float LVV[] = new float[4];   // To hold parts of current 
    float RVV[] = new float[4];    // color values on each edge,
    float LDVV[] = new float[4];  // To hold changes in color values
    float RDVV[] = new float[4];   // over each edge,
    float scanVV[] = new float[4];   // Current color values while on scanline,
    float DscanVV[] = new float[4];  // Changes in color values over scanline,
    float Lx, Rx;     // To hold current position on each edge,
    float dxInit, dyInit, bptest;  // For initial testing & changes,
    float Ldx, Rdx;   // (change in x over change=1 in y), for each edge
      
    Rdx = (a[2].x-a[0].x) / (a[2].y-a[0].y);  // Assume breakpoint is on left.

    if (breakpt == 2)  {             // Find out where breakpt really is:
      Rx = (a[1].y - a[0].y) * Rdx;    // draw a line from the breakpt
      bptest = a[0].x + Rx;            //  to the non-breakpt edge.
      if (a[1].x < bptest)             // if that intercept is to right of breakpt,
	breakpt = 0;                   //  breakpt is on left of triangle, otherwise
      else
	breakpt = 1;                   //  breakpt is on right of triangle.
    }

    if (breakpt == 0) {  // Breakpoint on left OR bottom edge parallel to scanline:
      Ldx = (a[1].x-a[0].x) / (a[1].y-a[0].y);    // Rdx already computed above.
      DEdgeColors(LDVV, a[0], a[1], Ldx);
      DEdgeColors(RDVV, a[0], a[2], Rdx);
    }
    else {               // Breakpoint on right OR top edge parallel to scanline:
      Ldx = Rdx;
      Rdx = (a[1].x-a[0].x) / (a[1].y-a[0].y);
      DEdgeColors(LDVV, a[0], a[2], Ldx);
      DEdgeColors(RDVV, a[0], a[1], Rdx);
    }

    // Find top point & initial info:
    y = (int) Math.ceil(a[0].y);   // First y that could include a pixel center.
    dyInit =  (y - a[0].y); // How far the real y-coord is, from where we are.
    Lx = a[0].x + Ldx * dyInit;    // Move an initial dx to accomodate initial dy
    Rx = a[0].x + Rdx * dyInit;    //  in both directions (i.e. move down both edges).
    LVV[0] = a[0].getA() + LDVV[0] * dyInit;   // Similar initial
    LVV[1] = a[0].getR() + LDVV[1] * dyInit;   // adjustments for
    LVV[2] = a[0].getG() + LDVV[2] * dyInit;   // color interpolations,
    LVV[3] = a[0].getB() + LDVV[3] * dyInit;
    RVV[0] = a[0].getA() + RDVV[0] * dyInit;   // for both edges.
    RVV[1] = a[0].getR() + RDVV[1] * dyInit;
    RVV[2] = a[0].getG() + RDVV[2] * dyInit;
    RVV[3] = a[0].getB() + RDVV[3] * dyInit;
    yEnd = (int) Math.floor(a[1].y);  // Last y to fill before breakpoint.

    for ( ; y<=yEnd; y++) {
      xStart = (int) Math.ceil(Lx);
      xEnd = (int) Math.floor(Rx);
      DScanlineColors(DscanVV, LVV, RVV, Lx, Rx);
      dxInit =  (xStart - Lx); // How far the real x-coord is, from where we are.      
      scanVV[0] = LVV[0] + DscanVV[0] * dxInit;   // Similar to above, but now
      scanVV[1] = LVV[1] + DscanVV[1] * dxInit;   // accomodate for initial dx.
      scanVV[2] = LVV[2] + DscanVV[2] * dxInit;
      scanVV[3] = LVV[3] + DscanVV[3] * dxInit;
      for (int x=xStart; x <= xEnd; x++)  {
	r.setPixel(RecreateColor(scanVV), x, y);
	UpdateColor(scanVV, DscanVV);
      }
      Lx += Ldx;     // Update position along edges.
      Rx += Rdx;
      UpdateColor(LVV, LDVV);
      UpdateColor(RVV, RDVV);
    }

    /* This is for the second half of the triangle, after the
       breakpoint.  Note that half of this method could be cut right
       out by simple optimizations -- by symmetry, the rest of this
       triangle is drawn just as above.  I should have broken it into
       two triangles in the 'Draw' method (after doing the breakpoint
       checking in a separate method), & just called 'Fill' twice.  Or
       at least put the repeated code into separate procedures.*/

    dyInit = (y - a[1].y); // How far the real y-coord is, from where we are.
    yEnd = (int) Math.floor(a[2].y);  // Last y to fill before endpoint.
    if (breakpt == 0) {  // Breakpoint to the left
      Ldx = (a[2].x-a[1].x) / (a[2].y-a[1].y);  // so change the left edge slope.
      Lx = a[1].x + Ldx * dyInit;    // Move an initial dx to accomodate initial dy.
      DEdgeColors(LDVV, a[1], a[2], Ldx); // also change the left edge color gradient.
      LVV[0] = a[1].getA() + LDVV[0] * dyInit;   // Similar initial
      LVV[1] = a[1].getR() + LDVV[1] * dyInit;   // adjustments for
      LVV[2] = a[1].getG() + LDVV[2] * dyInit;   // color interpolations,
      LVV[3] = a[1].getB() + LDVV[3] * dyInit;
    }
    else if (breakpt == 1){  // breakpoint to the right
      Rdx = (a[2].x-a[1].x) / (a[2].y-a[1].y);  // so change the right edge slope
      Rx = a[1].x + Rdx * dyInit;    // Move an initial dx to accomodate initial dy.
      DEdgeColors(RDVV, a[1], a[2], Rdx); // also change the right edge color gradient.
      RVV[0] = a[1].getA() + RDVV[0] * dyInit;
      RVV[1] = a[1].getR() + RDVV[1] * dyInit;
      RVV[2] = a[1].getG() + RDVV[2] * dyInit;
      RVV[3] = a[1].getB() + RDVV[3] * dyInit;
    }

    for ( ; y<=yEnd; y++) {         // Exact same code as above; ick.
      xStart = (int) Math.ceil(Lx);
      xEnd = (int) Math.floor(Rx);
      DScanlineColors(DscanVV, LVV, RVV, Lx, Rx);
      dxInit =  (xStart - Lx); // How far the real x-coord is, from where we are.      
      scanVV[0] = LVV[0] + DscanVV[0] * dxInit;   // accomodate initial dx.
      scanVV[1] = LVV[1] + DscanVV[1] * dxInit;
      scanVV[2] = LVV[2] + DscanVV[2] * dxInit;
      scanVV[3] = LVV[3] + DscanVV[3] * dxInit;
      for (int x=xStart; x <= xEnd; x++)  {
	r.setPixel(RecreateColor(scanVV), x, y);
	UpdateColor(scanVV, DscanVV);
      }
      Lx += Ldx;
      Rx += Rdx;
      UpdateColor(LVV, LDVV);
      UpdateColor(RVV, RDVV);
    }    
  } // end FillColor method

  
  private void DEdgeColors(float DVV[], Vertex2D v1, Vertex2D v2, float Dx) {
// Assumes v1 is start vertex & v2 is end vertex.
//  Find change in color over a unit change in edge:
// == (difference in color) / (Total length of edge) * (unit change)
// Total length = ((y1-y0)^2 + (x1-x0)^2)^0.5
// The unit change is the hypotenuse created when dy = 1 & dx = 'Dx'
// Since h^2 = dy^2 + dx^2  --->  h = (1 + dx^2)^.5
    float dy, dx, l,d;
    dy = v2.y - v1.y;
    dx = v2.x - v1.x;
    l = (float) Math.sqrt(dy*dy + dx*dx);
    d = (float) Math.sqrt(1.0f + Dx * Dx);
    DVV[0] = (v2.getA() - v1.getA()) / l * d;
    DVV[1] = (v2.getR() - v1.getR()) / l * d;
    DVV[2] = (v2.getG() - v1.getG()) / l * d;
    DVV[3] = (v2.getB() - v1.getB()) / l * d;
  } // end DEdgeColors method

  
  private void DScanlineColors(float SVV[], float LVV[], float RVV[],
			       float Lx, float Rx) {
// Similar to finding change in x over change in y,
//  find change in color over scanline (over change in x).
    float dx;
    dx = Rx - Lx;
    SVV[0] = (RVV[0] - LVV[0]) / dx;
    SVV[1] = (RVV[1] - LVV[1]) / dx;
    SVV[2] = (RVV[2] - LVV[2]) / dx;
    SVV[3] = (RVV[3] - LVV[3]) / dx;
  } // end DScanlineColors method
      

  private void UpdateColor(float a[], float Da[])  {
    	a[0] += Da[0];	a[1] += Da[1];	a[2] += Da[2];	a[3] += Da[3];
  }


  private int RecreateColor(float a[]) {
    return ( (Math.round(a[0]) << 24) |
	     (Math.round(a[1]) << 16) |
	     (Math.round(a[2]) << 8) |
	     (Math.round(a[3]) ) );
  }

  private void FillSimple(Raster r, Vertex2D a[], int breakpt) {
    int y, yEnd, xEnd;
    float Lx, Rx, dyInit, bptest;
    float Ldx, Rdx;   // (change in x over change in y), for each edge

    Rdx = (a[2].x-a[0].x) / (a[2].y-a[0].y);  // Assume breakpoint is on left.

    if (breakpt == 2)  {             // Find out where breakpt really is:
      Rx = (a[1].y - a[0].y) * Rdx;    // draw a line from the breakpt
      bptest = a[0].x + Rx;            //  to the non-breakpt edge.
      if (a[1].x < bptest)         // if that intercept is to right of breakpt,
        breakpt = 0;               //  breakpt is on left of triangle, otherwise
      else
        breakpt = 1;                   //  breakpt is on right of triangle.
    }

    if (breakpt == 0)   // Breakpt on left OR bottom edge parallel to scanline:
      Ldx = (a[1].x-a[0].x) / (a[1].y-a[0].y);    // Rdx already computed above.
    else {              // Breakp on right OR top edge parallel to scanline:
      Ldx = Rdx;
      Rdx = (a[1].x-a[0].x) / (a[1].y-a[0].y);
    }

    // Find top point
    y = (int) Math.ceil(a[0].y);
    dyInit =  (y - a[0].y);    // How far the real y-coord is, from where we are.
    Lx = a[0].x + Ldx * dyInit;   // Move an initial dx to accomodate initial dy
    Rx = a[0].x + Rdx * dyInit;   //  in both directions (ie traverse both edges)
    yEnd = (int) Math.floor(a[1].y);  // Last y to fill before breakpoint.

    for ( ; y<=yEnd; y++) {
      xEnd = (int) Math.floor(Rx);
      for (int x= (int)Math.ceil(Lx); x <= xEnd; x++)      
        r.setPixel(a[0].argb, x, y);
      Lx += Ldx;
      Rx += Rdx;
    }

    dyInit = (y - a[1].y); // How far the real y-coord is, from where we are.
    yEnd = (int) Math.floor(a[2].y);  // Last y to fill before endpoint.
    if (breakpt == 0) {  // Breakpoint to the left
      Ldx = (a[2].x-a[1].x) / (a[2].y-a[1].y);  // so change the left edge slope
      Lx = a[1].x + Ldx * dyInit;    // Move an initial dx to accomodate initial dy.
      }
    else if (breakpt == 1){  // breakpoint to the right
      Rdx = (a[2].x-a[1].x) / (a[2].y-a[1].y);  // so change the right edge slope
      Rx = a[1].x + Rdx * dyInit;    // Move an initial dx to accomodate initial dy.
    }
    
      for ( ; y<=yEnd; y++) {
        xEnd = (int) Math.floor(Rx);
        for (int x= (int)Math.ceil(Lx); x <= xEnd; x++)      
          r.setPixel(a[0].argb, x, y);
        Lx += Ldx;
        Rx += Rdx;
      }
  } // end FillSimple method


  private int Sort(Vertex2D a[]) {
// First sorts vertices such that:
//   v[0] == topmost vertex (leftmost if v[0].y = v[1].y)
//   v[1] == middle vertex (leftmost if  v[1].y = v[2].y, breakpoint if exists)
//   v[2] == bottom vertex (rightmost if  v[1].y = v[2].y, endpoint)
// Note: (0,0) represents the upper left corner of the drawing field.
// Then returns an integer flag equal to:
//   0 iff there is no breakpoint due to bottom edge parallel to scanline
//   1 iff there is no breakpoint due to top edge parallel to scanline
//   2 iff there is a breakpoint.

    Vertex2D temp;
    for (int i=0; i<2; i++)         // bubble sort the vertices by y-coordinate
      for (int j=0; j<(2-i); j++)    // (can be done MORE EFFICIENTLY)
	if (a[j].y > a[j+1].y) {     // (Also, needs to CHECK VALIDITY of triangle)
	  temp = a[j];
	  a[j] = a[j+1];
	  a[j+1] = temp; }

    for (int i=0; i<2; i++)
      if (v[i].y == v[i+1].y) {     // sort vertices with equal y-coords
	if (v[i].x > v[i+1].x) {     // by their x-coords, s.t. 
	  temp = a[i];               // leftmost vertices are listed first.
	  a[i] = a[i+1];
	  a[i+1] = temp;         // if v[0].y==v[1].y, v[1].y != v[2].y; can return
	}
	if (i==0) return(1); else return(0);     // no breakpoint
      }

    return(2);                  // there is a breakpoint.
  } // end Sort method

  public void print(String s) {    System.out.print(s);   }
  
} // end Triangle class