/****************************************************************************/
class EdgeEqn {
  public float A, B, C;
  public int flag;    

  public EdgeEqn(Vector3D v0, Vector3D 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);
  }
}

/****************************************************************************/
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);
  //System.out.println("REDS --> "+r[0]+", "+r[1]+", "+r[2]);
  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;
  }
}
}