import graphics.*;

//handles low level rendering
class RasterizerApplet extends MISApplet
{
  protected int[][][] framebuffer, bgbuffer; //2D array of RGB values
  protected double[][] zbuffer;
  protected graphics.Shape[][] sbuffer; //which shapes have been rendered - comparable to zbuffer

  protected boolean pixelshading = true;
  protected boolean doTexturing = true;

  //can be overridden by child applet
  protected Light[] lights;
  protected int[] ambient = {0,0,0};

  //store material for currently rendered object in global variable
  protected Material currentMaterial;

  protected graphics.Shape currentShape;

  //current texture can be set in child applet
  //it will be used if not null
  protected Texture currentTexture = null;

  protected NoiseTexture currentNoiseTexture = null;

  //for manually overriding texture LOD
  protected double overrideLOD = -1;

  //blending values
  protected boolean doBlending = false;
  protected double currentAlpha = 0;

  protected boolean doFog = false;
  protected double fogAmount = 0.02;
  protected int[] fogColor = {255, 255, 255};
  NoiseTexture fogTexture;


  public void initialize()
  {
    super.initialize();

    framebuffer = new int[H][W][3]; //rgb values
    bgbuffer = new int[H][W][3]; //rgb values
    zbuffer = new double[H][W];
    sbuffer = new graphics.Shape[H][W];

    fogTexture = new NoiseTexture(0.01, 0.05, 0.05);
    fogTexture.type = NoiseTexture.INVERSE_F;
    //fogTexture.amp = 10.1;

  }

  public void initFrame(long time)
  {
    //clear z-buffer
    for (int w=0; w<W; w++)
    for (int h=0; h<H; h++)
    {
      zbuffer[h][w] = 0;
      //copy from background buffer to framebuffer
      framebuffer[h][w][0] = bgbuffer[h][w][0]; framebuffer[h][w][1] = bgbuffer[h][w][1]; framebuffer[h][w][2] = bgbuffer[h][w][2];
      sbuffer[h][w] = null;
    }
  }

  //just copy from framebuffer...
  public void setPixel(int x, int y, int rgb[])
  {
    rgb[0] = framebuffer[y][x][0];
    rgb[1] = framebuffer[y][x][1];
    rgb[2] = framebuffer[y][x][2];

    if (doFog && doTexturing) //blend in procedural noise to fake the fog
    {
      double z = 0.005;// * clockTime();
      for (int i=0; i<3; i++)
        rgb[i] = (int)lerp(fogAmount, rgb[i], fogTexture.get(x, y, z)*fogColor[i]);
    }
  }

  //splits a triangle into two trapezoids
  private void splitTriangle(double[] a, double[] b, double[] c)
  {
    //interpolate between a & c
    double t = (b[1]-a[1])/(c[1]-a[1]);

    double[] d = new double[8];

    //interpolate d (normals and texels too)
    for (int i=0; i < 8; i++)
    {
      if (i == 1) //y coord is same as b's
        d[i] = b[i];
      else
        d[i] = lerp(t, a[i], c[i]);
    }

    if (a[1] > c[1])
    {
      if (d[0] > b[0])
      {
        renderTrapezoid(a, a, b, d);
        renderTrapezoid(b, d, c, c);
      }
      else
      {
        renderTrapezoid(a, a, d, b);
        renderTrapezoid(d, b, c, c);
      }
    }
    else
    {
      if (d[0] > b[0])
      {
        renderTrapezoid(c, c, b, d);
        renderTrapezoid(b, d, a, a);
      }
      else
      {
        renderTrapezoid(c, c, d, b);
        renderTrapezoid(d, b, a, a);
      }
    }
  }

  protected void renderTriangle(double[][] triangle)
  {
//dumpVertices(triangle);
    double[] a = triangle[0], b = triangle[1], c = triangle[2];

    //are any of the vertices on the same y?  Then it's already a trapezoid
    if (a[1] == b[1])
    {
      if (a[1] > c[1]) //a & b above c
      {
        if (a[0] < b[0]) //a left of b
          renderTrapezoid(a, b, c, c);
        else //b left of a
          renderTrapezoid(b, a, c, c);
      }
      else //c above a & b
      {
        if (a[0] < b[0]) //a left of b
          renderTrapezoid(c, c, a, b);
        else //b left of a
          renderTrapezoid(c, c, b, a);
      }
    }
    else if (a[1] == c[1])
    {
      if (a[1] > b[1]) //a & c above b
      {
        if (a[0] < c[0]) //a left of c
          renderTrapezoid(a, c, b, b);
        else //c left of a
          renderTrapezoid(c, a, b, b);
      }
      else //b above a & c
      {
        if (a[0] < c[0]) //a left of c
          renderTrapezoid(b, b, a, c);
        else //c left of a
          renderTrapezoid(b, b, c, a);
      }
    }
    else if (b[1] == c[1])
    {
      if (a[1] > b[1]) //a above b & c
      {
        if (b[0] < c[0]) //b left of c
          renderTrapezoid(a, a, b, c);
        else //c left of b
          renderTrapezoid(a, a, c, b);
      }
      else //b & c above a
      {
        if (b[0] < c[0]) //b left of c
          renderTrapezoid(b, c, a, a);
        else //c left of b
          renderTrapezoid(c, b, a, a);
      }
    }
    else //split triangle into 2
    {
      //which vertex is in the middle?
      if ((a[1] >= b[1] && a[1] <= c[1]) || (a[1] <= b[1] && a[1] >= c[1]))
        splitTriangle(c, a, b); //maintain relative order (ccw)
      else if ((b[1] >= a[1] && b[1] <= c[1]) || (b[1] <= a[1] && b[1] >= c[1]))
        splitTriangle(a, b, c);
      else if ((c[1] >= a[1] && c[1] <= b[1]) || (c[1] <= a[1] && c[1] >= b[1]))
        splitTriangle(b, c, a);
    }
  }

  private void renderTrapezoid(double[] tl, double[] tr, double[] bl, double[] br)
  {
//System.err.println("in renderTrapezoid");
//System.err.println("tl = ("+tl[0]+", "+tl[1]+", "+tl[2]+") - (" + tl[3]+", "+tl[4]+", "+tl[5]+")");
//System.err.println("tr = ("+tr[0]+", "+tr[1]+", "+tr[2]+") - (" + tr[3]+", "+tr[4]+", "+tr[5]+")");
//System.err.println("bl = ("+bl[0]+", "+bl[1]+", "+bl[2]+") - (" + bl[3]+", "+bl[4]+", "+bl[5]+")");
//System.err.println("br = ("+br[0]+", "+br[1]+", "+br[2]+") - (" + br[3]+", "+br[4]+", "+br[5]+")");

    //bounds checking - make sure trapezoid is at least somewhat inside screen
    if (bl[0] > W && tl[0] > W) return; //both left x-coords off the screen?
    if (br[0] < 0 && tr[0] < 0) return; //both right x-coords off the screen?
    if (br[1] > H && bl[1] > H) return; //both bottom y-coords off the screen? (bottom > top)
    if (tl[1] < 0 && tr[1] < 0) return; //both top y-coords off the screen?

    if ((int)tl[1] != (int)tr[1]) System.err.println("Warning: top of trapezoid is not vertically aligned!");
    if ((int)bl[1] != (int)br[1]) System.err.println("Warning: bottom of trapezoid is not vertically aligned!");

    int top = (int)tl[1], bottom = (int)bl[1];
    int height = top - bottom;

    if (height == 0) //don't want divide by zeros
    {
      renderLine(tl, tr);
      //renderLine(bl, br);

      return;
    }
//System.err.println("top = " + top + ", bottom = " + bottom);

    double xLeft = (int)tl[0], xRight = (int)tr[0];

    //how much to go left and right for each scanline
    double dxLeft =  (bl[0] - tl[0])/height; // dy = -1/height => -(tl - bl)
    double dxRight = (br[0] - tr[0])/height;

//System.err.println("dxLeft = " + dxLeft + ", dxRight = " + dxRight);
//System.err.println("u = " + br[6] + ", v = " + br[7]);

    //each scanline
    for (int y = top; y > bottom; y--)
    {
      if (y >= H || y < 0) continue; //vert bounds checking for pixel

//System.err.println("y = " + y);
//if (xRight < xLeft) System.err.println("xLeft = " + xLeft + ", xRight = " + xRight);

      //xRight and xLeft might cross each other at tip of triangle...
      if (xRight < xLeft)
      {
        double tmp = xLeft;
        xLeft = xRight;
        xRight = tmp;
      }

      //how far down are we
      double u = ((double)y - bottom)/height;

      double zLeft = lerp(u, bl[2], tl[2]), zRight = lerp(u, br[2], tr[2]);

      //normals
      double nxLeft = lerp(u, bl[3], tl[3]), nxRight = lerp(u, br[3], tr[3]);
      double nyLeft = lerp(u, bl[4], tl[4]), nyRight = lerp(u, br[4], tr[4]);
      double nzLeft = lerp(u, bl[5], tl[5]), nzRight = lerp(u, br[5], tr[5]);

      //for texture coordinates
      double LOD = 0;  //calculate mipmap level
      double tuLeft = 0, tuRight = 0, tvLeft = 0, tvRight = 0;
      if (currentTexture != null && doTexturing)
      {
        tuLeft = lerp(u, bl[6], tl[6]);
        tuRight = lerp(u, br[6], tr[6]);
        tvLeft = lerp(u, bl[7], tl[7]);
        tvRight = lerp(u, br[7], tr[7]);
      }

      //each pixel in scanline
      for (int x = (int)xLeft; x <= (int)xRight; x++)
      {
        if (x >= W || x < 0) continue; //horiz bounds checking for pixel
//System.err.println("x = " + x);

        double v;
       
        //check for x < xLeft
        if (x <= xLeft) v = 0;
        else if (Math.abs(xRight - xLeft) < 0.001) v = 0.5; //single pixel
        else v = ((double)x - xLeft)/(xRight - xLeft);

        //interpolate z value at current pixel
        double z = lerp(v, zLeft, zRight);

//System.err.println("z = " + z);
        if (z < zbuffer[y][x])
        {
          //update z-buffer
          zbuffer[y][x] = z;

          //calculate MIPmap level

          /*
          if (currentTexture != null && doTexturing)
          {
            double v1;
            if (xRight == xLeft || (double)x < xLeft) v1 = 0;
            else v1 = ((double)x - xLeft + 1)/(xRight - xLeft);

            int w0 = currentTexture.getWidth(), h0 = currentTexture.getHeight();
            double dtu = lerp(v1, tuLeft, tuRight) - lerp(v, tuLeft, tuRight);
            double dtv = lerp(v1, tvLeft, tvRight) - lerp(v, tvLeft, tvRight);
            dtu *= w0; dtv *= h0; //convert to pixel values on texture

            LOD = 1/dtu*dtv;

            //double dtu = w0 * (tuRight - tuLeft), dtv = h0 * (tvRight - tvLeft);
            //double dxx = (xRight - xLeft) * (xRight - xLeft);

            //LOD = dtu/(xRight - xLeft);
            //LOD = Math.sqrt( (dtu * dtu)/dxx  + (dtv * dtv)/dxx );

            LOD = Math.log(LOD)/Math.log(2);
  //System.err.println(LOD);
          }
        */
          if (overrideLOD  >= 0) LOD = overrideLOD;


          double[] left = new double[] {0, 0, 0, nxLeft, nyLeft, nzLeft, tuLeft, tvLeft};
          double[] right = new double[] {0, 0, 0, nxRight, nyRight, nzRight, tuRight, tvRight};
          renderPixel(x, y, z, v, left, right, LOD);

          sbuffer[y][x] = currentShape;
        }
      }

      xLeft  += dxLeft;
      xRight += dxRight;
    }
  }

  //draws a line in a specific color
  protected void renderLine(double[] a, double[] b, int[] color)
  {
    for (double t = 0; t < 1.0; t += 0.05)
    {
      int x = (int)lerp(t, a[0], b[0]);
      if (x >= W || x < 0) continue; //horiz bounds checking for pixel

      int y = (int)lerp(t, a[1], b[1]);
      if (y >= H || y < 0) continue; //vert bounds checking for pixel

      double z = lerp(t, a[2], b[2]);

      if (z < zbuffer[y][x])
      {
        zbuffer[y][x] = z;
        framebuffer[y][x][0] = color[0];
        framebuffer[y][x][1] = color[1];
        framebuffer[y][x][2] = color[2];
      }
    }
  }

  //same as renderLine but with fancier rendering
  protected void renderLine(double[] a, double[] b)
  {
    double LOD = 0;
    for (double t = 0; t < 1.0; t += 0.05)
    {
      int x = (int)lerp(t, a[0], b[0]);
      if (x >= W || x < 0) continue; //horiz bounds checking for pixel

      int y = (int)lerp(t, a[1], b[1]);
      if (y >= H || y < 0) continue; //vert bounds checking for pixel

      double z = lerp(t, a[2], b[2]);

      if (z > zbuffer[y][x])
      {
        zbuffer[y][x] = z;
        renderPixel(x, y, z, t, a, b, LOD);
      }
    }
  }

  //renders a pixel at given x, y, by interpolating btwn two vertices
  protected void renderPixel(int x, int y, double z, double t, double[] left, double[] right, double LOD)
  {
    //prevent double rendering
    if (sbuffer[y][x] == currentShape) return;

    int r, g, b;

    Material mat = currentMaterial.deepCopy();

    double nxLeft = left[3], nyLeft = left[4], nzLeft = left[5];
    double nxRight = right[3], nyRight = right[4], nzRight = right[5];
    double tuLeft = left[6], tuRight = right[6];
    double tvLeft = left[7], tvRight = right[7];

    if (currentTexture != null && doTexturing)
    {
      double tu = lerp(t, tuLeft, tuRight);
      double tv = lerp(t, tvLeft, tvRight);

      int[] texcol = currentTexture.get(tu, tv, LOD);

      //set the diffuse color to the texture's color
      mat.diffuseColor[0] = texcol[0]; mat.diffuseColor[1] = texcol[1]; mat.diffuseColor[2] = texcol[2];
    }

    if (pixelshading)
    {
      //interpolate normal
      double nx = lerp(t, nxLeft, nxRight);
      double ny = lerp(t, nyLeft, nyRight);
      double nz = lerp(t, nzLeft, nzRight);

      //noise up the normal?
      if (currentNoiseTexture != null && (currentNoiseTexture.target & NoiseTexture.N) != 0 && doTexturing)
      {
        double za = z; //za is z-animated
        if (currentNoiseTexture.ani > 0) za += clockTime()/currentNoiseTexture.ani;

        double val = currentNoiseTexture.get(x, y, za);
        if (currentNoiseTexture.op == NoiseTexture.ADD)
        {
          nx += val; ny += val; nz += val;
        }
        else if (currentNoiseTexture.op == NoiseTexture.MULTIPLY)
        {
          nx *= val; ny *= val; nz *= val;
        }
      }

      Vector3 normal = new Vector3(nx, ny, nz);
      normal.normalize();

      double[] rgb = Shader.shade(normal, mat, lights, ambient);

      r = (int)rgb[0]; g = (int)rgb[1]; b = (int)rgb[2];
    }
    else //vertex shading
    {
      //interpolate rgb which are stored in normal data
      r = (int)lerp(t, nxLeft, nxRight);
      g = (int)lerp(t, nyLeft, nyRight);
      b = (int)lerp(t, nzLeft, nzRight);
    }

    if (currentNoiseTexture != null && doTexturing)
    {
      double za = z; //za is z-animated
      if (currentNoiseTexture.ani > 0) za += clockTime()/currentNoiseTexture.ani;

      double val = currentNoiseTexture.get(x, y, za);

      double dr = 0, dg = 0, db = 0; //how to change rgb

      //set defaults based on operation
      if (currentNoiseTexture.op == NoiseTexture.ADD)
        dr = dg = db = 0;
      else if (currentNoiseTexture.op == NoiseTexture.MULTIPLY)
        dr = dg = db = 1;

      if ((currentNoiseTexture.target & NoiseTexture.R) != 0)
        dr = val;
      if ((currentNoiseTexture.target & NoiseTexture.G) != 0)
        dg = val;
      if ((currentNoiseTexture.target & NoiseTexture.B) != 0)
        db = val;

      if (currentNoiseTexture.op == NoiseTexture.ADD)
      {
        r += dr; g += dg; b += db;
      }
      else if (currentNoiseTexture.op == NoiseTexture.MULTIPLY)
      {
        r *= dr; g *= dg; b *= db;
      }

      r = Math.max(r, 0) & 255;
      g = Math.max(g, 0) & 255;
      b = Math.max(b, 0) & 255;
    }

//if (x > 215 && y > 350 && x < 230 && y < 380)
//if (framebuffer[y][x][1] != 0)
//System.err.println("(x,y,r,g,b) = (" +x+ "," +y+ "," +r+ "," +g+ "," +b+ ")");

    if (doBlending)
    {
      r = (int)lerp(currentAlpha, r , framebuffer[y][x][0]);
      g = (int)lerp(currentAlpha, g , framebuffer[y][x][1]);
      b = (int)lerp(currentAlpha, b , framebuffer[y][x][2]);
    }

    framebuffer[y][x][0] = r;
    framebuffer[y][x][1] = g;
    framebuffer[y][x][2] = b;
  }

  public double lerp(double t, double a, double b)
  {
    return a + t*(b-a);
  }

  public void dumpVertices(double[][] vertices)
  {
    System.err.println("vertices:");
    for (int i = 0; i < vertices.length; i++)
      System.err.println("("+vertices[i][0]+", "+vertices[i][1]+", "+vertices[i][2]+") - ("+vertices[i][3]+", "+vertices[i][4]+", "+vertices[i][5]+")");
  }
}