#include <math.h></math.h>

#include <stdio.h></stdio.h>

#include <stdlib.h></stdlib.h>

#include <helianthus.h></helianthus.h>

typedef struct {

  double x, y;

  double color[4];

} Vertex;

int cs = 5, vw = 120, vh = 90;

int lx1, ly1, lx2, ly2, lx3, ly3;

Vertex tv1, tv2, tv3;

void grid(int w, int h) {

  saveState();

  strokeWidth(0.1);

  stroke(colorByNameA("gray", 0.5));

  for(int x = 0; x <= w; ++x) line(x, 0, x, h);

  for(int y = 0; y <= h; ++y) line(0, y, w, y);

  restoreState();

}

void dot(int x, int y)

  { rect(x, y, 1, 1); }

void dotColored(int x, int y, double *color) {

  saveState();

  fill(colorByRGBA(color[0], color[1], color[2], color[3]));

  dot(x, y);

  restoreState();

}

void lineBase(int x1, int y1, int x2, int y2) {

	int x_start_line;	// put the lowest x in start line and the highest in end line

	int x_end_line;

	int y_start_line;	// put the lowest y in start line and the highest in end line

	int need_reflect;

	int dist_point_to_line;

	int switch_roles = FALSE;

	int delta_x;

	int delta_y;

	int temp;

	// take care of end cases when the two points share an index value

	// take care of end cases when the two points share an index value// take care of end cases when the two points share an index value// take care of end cases when the two points share an index value

	//	need to take care of the case where the point is outside of the window frame

		// Initialization for the Bershenham algorithm:

	x_start_line = x1, y_start_line = y1;

	x_end_line = x1;

	delta_x = (x2 - x1);

	if (delta_x < 0)

		delta_x = delta_x * (-1);	// make delta_x positive

	delta_y = (y2 - y1);

	if (delta_y < 0)

		delta_y = delta_y * (-1);	// make delta_y positive

	if (delta_x != 0 || delta_y != 0)

	{

		// first case: 0

		if (delta_y < delta_x)	// check if the incline is a fraction or not, because they are both positive

		{						// meaning -1

			if (x1 < x2)

			{

				x_start_line = x1, y_start_line = y1;

				x_end_line = x2;

				need_reflect = (y1 < y2) ? 1 : -1;	// take care of the case of negative incline

			}

			else	// the start point is p2

			{

				x_start_line = x2, y_start_line = y2;

				x_end_line = x1;

				need_reflect = (y2 < y1) ? 1 : -1;	// take care of the case of negative incline

			}

		}

		else	// the incline is either incline>1 or incline<-1

		{		// so we need to change the x and y roles

			if (y1 < y2)	// the start point is p1 and switch the x and y

			{

				x_start_line = y1;	// swith roles of x and y

				y_start_line = x1;

				x_end_line = y2;

				need_reflect = (x1 < x2) ? 1 : -1;

			}

			else	// the start point is p2 and switch the x and y roles

			{

				x_start_line = y2;

				y_start_line = x2;

				x_end_line = y1;

				need_reflect = (x2 < x1) ? 1 : -1;

			}

			switch_roles = TRUE;

			temp = delta_x;	// switch the delta_x and delta_y because the roles have changed

			delta_x = delta_y;

			delta_y = temp;

		}

		dist_point_to_line = 2 * delta_y - delta_x;

		// Testing Barriers:

		if (x_end_line > vw)	// need to add barrier for viewport height without causing lines to disappear

			x_end_line = vw;

		if (x_start_line < 0)

			x_start_line = 0;

		if (y_start_line < 0)

			y_start_line = 0;

		for (int i = x_start_line; i <= x_end_line; i++)	// go over the incline from start point to end point and draw the line

		{													// put each pixel in the right place

			switch_roles ? dot(y_start_line, i) : dot(i, y_start_line);

			// new stuff for edge walking

			// end of new stuff

			if (dist_point_to_line > 0)

			{

				y_start_line = y_start_line + need_reflect;

				dist_point_to_line = dist_point_to_line - 2 * delta_x;

			}

			dist_point_to_line = dist_point_to_line + 2 * delta_y;

		}	//x_start_line,x_end_line,switch_roles,y_start_line,need_reflect,dist_point_to_line,delta_x,delta_y

	}

}

void lineNew(int x1, int y1, int x2, int y2) {

  if (y1 > y2) { int x = x1, y = y1; x1 = x2; y1 = y2; x2 = x; y2 = y; }

	int x = x1;

	int dx = x2 - x1;

	int dy = y2 - y1;

	if (dy > 0) {

    int sign_x = dx < 0 ? -1 : 1;

    int step_x = dx/dy;

    int sub_step_x = abs(dx)%dy;

    int sub_step_accum = -dy/2;

    for(int y = y1; y < y2; ++y) {

      dot(x, y);

      x += step_x;

      sub_step_accum += sub_step_x;

      if (sub_step_accum > 0) {

        sub_step_accum -= dy;

        x += sign_x;

      }

    }

  } else {

    dot(x1, y1);

  }

	dot(x2, y2);

}

void row(int y, int x1, int x2) {

  if (x1 > x2) { int x = x1; x1 = x2; x2 = x; }

  if (x1 < 0) x1 = 0;

  if (x2 > vw) x2 = vw;

  for(int x = x1; x < x2; ++x) dot(x, y);

}

void triangle(int vx1, int vy1, int vx2, int vy2, int vx3, int vy3) {

  if (vy1 > vy3) { int x = vx1, y = vy1; vx1 = vx3; vy1 = vy3; vx3 = x; vy3 = y; }

  if (vy2 > vy3) { int x = vx2, y = vy2; vx2 = vx3; vy2 = vy3; vx3 = x; vy3 = y; }

  if (vy1 > vy2) { int x = vx1, y = vy1; vx1 = vx2; vy1 = vy2; vx2 = x; vy2 = y; }

	// split triangle to two triangles by the middle vertex

	//

	//       *__

	//      /    --__    - top triangle here

	//     /-------__-*  - split triangle by this line

	//    /    __--

	//   / __--          - bottom triangle here

	//  *--

	// include pixels at left and top sides, but exclude at right and bottom

	// it required to seamless clue neighboring triangles without overlapping

	if (vy1 >= vy3) return;

	if (vy1 >= vh || vy3 <= 0) return;

	if (vx1 >= vw && vx2 >= vw && vx3 >= vw) return;

	if (vx1 <= 0  && vx2 <= 0  && vx3 <= 0 ) return;

	// configure line from top vertex to bottom vertex

	int x1 = vx1;

	int dx1 = vx3 - vx1;

	int dy1 = vy3 - vy1;

  int sign_x1 = dx1 < 0 ? -1 : 1;

  int step_x1 = dx1/dy1;

  int sub_step_x1 = abs(dx1)%dy1;

  int sub_step_accum1 = -dy1/2;

  // draw top triangle

	if (vy2 > vy1) {

    // configure line from top vertex to middle vertex

    int x2 = vx1;

    int dx2 = vx2 - vx1;

    int dy2 = vy2 - vy1;

    int sign_x2 = dx2 < 0 ? -1 : 1;

    int step_x2 = dx2/dy2;

    int sub_step_x2 = abs(dx2)%dy2;

    int sub_step_accum2 = -dy2/2;

    // skip invisible rows

    int y1 = vy1, y2 = vy2;

    if (y1 < 0) {

      const int rows = (y2 < 0 ? y2 : 0) - y1;

      y1 += rows;

      x1 += rows*step_x1;

      sub_step_accum1 += rows*sub_step_x1;

      if (sub_step_accum1 > 0) {

        const int count = sub_step_accum1/dy1 + 1;

        sub_step_accum1 -= count*dy1;

        x1 += count*sign_x1;

      }

      x2 += rows*step_x2;

      sub_step_accum2 += rows*sub_step_x2;

      if (sub_step_accum2 > 0) {

        const int count = sub_step_accum2/dy2 + 1;

        sub_step_accum2 -= count*dy2;

        x2 += count*sign_x2;

      }

    }

    if (y2 > vh) y2 = vh;

    // iterate over visible rows

    for(int y = y1; y < y2; ++y) {

      row(y, x1, x2);

      // increment line 1

      x1 += step_x1;

      sub_step_accum1 += sub_step_x1;

      if (sub_step_accum1 > 0)

        { sub_step_accum1 -= dy1; x1 += sign_x1; }

      // increment line 2

      x2 += step_x2;

      sub_step_accum2 += sub_step_x2;

      if (sub_step_accum2 > 0)

        { sub_step_accum2 -= dy2; x2 += sign_x2; }

    }

  }

  // draw bottom triangle

	if (vy3 > vy2) {

    // configure line from middle vertex to bottom vertex

    int x2 = vx2;

    int dx2 = vx3 - vx2;

    int dy2 = vy3 - vy2;

    int sign_x2 = dx2 < 0 ? -1 : 1;

    int step_x2 = dx2/dy2;

    int sub_step_x2 = abs(dx2)%dy2;

    int sub_step_accum2 = -dy2/2;

    // skip invisible rows

    int y1 = vy2, y2 = vy3;

    if (y1 < 0) {

      const int rows = -y1;

      y1 += rows;

      x1 += rows*step_x1;

      sub_step_accum1 += rows*sub_step_x1;

      if (sub_step_accum1 > 0) {

        const int count = sub_step_accum1/dy1 + 1;

        sub_step_accum1 -= count*dy1;

        x1 += count*sign_x1;

      }

      x2 += rows*step_x2;

      sub_step_accum2 += rows*sub_step_x2;

      if (sub_step_accum2 > 0) {

        const int count = sub_step_accum2/dy2 + 1;

        sub_step_accum2 -= count*dy2;

        x2 += count*sign_x2;

      }

    }

    if (y2 > vh) y2 = vh;

    // iterate over visible rows

    for(int y = y1; y < y2; ++y) {

      row(y, x1, x2);

      // increment line 1

      x1 += step_x1;

      sub_step_accum1 += sub_step_x1;

      if (sub_step_accum1 > 0)

        { sub_step_accum1 -= dy1; x1 += sign_x1; }

      // increment line 2

      x2 += step_x2;

      sub_step_accum2 += sub_step_x2;

      if (sub_step_accum2 > 0)

        { sub_step_accum2 -= dy2; x2 += sign_x2; }

    }

  }

}

void rowNew(int y, int x1, int x2, double *color, double *inc) {

  if (x1 < x2) {

    if (x1 >= vw || x2 <= 0) return;

    if (x1 < 0) {

      int skip = -x1;

      for(int i = 0; i < 4; ++i) color[i] += skip*inc[i];

      x1 += skip;

    }

    if (x2 > vw) x2 = vw;

    for(int x = x1; x < x2; ++x) {

      dotColored(x, y, color);

      for(int i = 0; i < 4; ++i) color[i] += inc[i];

    }

  } else {

    if (x2 >= vw || x1 <= 0) return;

    if (x1 > vw) {

      int skip = vw - x1;

      for(int i = 0; i < 4; ++i) color[i] += skip*inc[i];

      x1 += skip;

    }

    if (x2 < 0) x2 = 0;

    for(int x = x1-1; x >= x2; --x) {

      for(int i = 0; i < 4; ++i) color[i] -= inc[i];

      dotColored(x, y, color);

    }

  }

}

void triangleNew(const Vertex *v1, const Vertex *v2, const Vertex *v3) {

  if (v1->y > v3->y) { const Vertex *v = v1; v1 = v3; v3 = v; }

  if (v2->y > v3->y) { const Vertex *v = v2; v2 = v3; v3 = v; }

  if (v1->y > v2->y) { const Vertex *v = v1; v1 = v2; v2 = v; }

	// split triangle to two triangles by the middle vertex

	//

	//       *__

	//      /    --__    - top triangle here

	//     /-------__-*  - split triangle by this line

	//    /    __--

	//   / __--          - bottom triangle here

	//  *--

	// include pixels at left and top sides, but exclude at right and bottom

	// it required to seamless clue neighboring triangles without overlapping

	const int vx1 = (int)floor(v1->x);

	const int vy1 = (int)floor(v1->y);

	const int vx2 = (int)floor(v2->x);

	const int vy2 = (int)floor(v2->y);

	const int vx3 = (int)floor(v3->x);

	const int vy3 = (int)floor(v3->y);

	const int dx31 = vx3 - vx1;

	const int dy31 = vy3 - vy1;

	const int dx21 = vx2 - vx1;

	const int dy21 = vy2 - vy1;

	const int dx32 = vx3 - vx2;

	const int dy32 = vy3 - vy2;

	if (dy31 <= 0) return;

	if (vy1 >= vh || vy3 <= 0) return;

	if (vx1 >= vw && vx2 >= vw && vx3 >= vw) return;

	if (vx1 <= 0  && vx2 <= 0  && vx3 <= 0 ) return;

	// calculate area

	const int double_area = dx31*dy31 - dx21*dy21 + dx32*dy32 - 2*dx32*dy31;

	if (!double_area) return;

	const double one_div_2a = 1.0/double_area;

	// configure line from top vertex to bottom vertex

  const int sign_x1 = dx31 < 0 ? -1 : 1;

  const int step_x1 = dx31/dy31;

  const int sub_step_x1 = abs(dx31)%dy31;

	int x1 = vx1;

  int sub_step_accum1 = -dy31/2;

  // configure interpolation coefficients for the middle vertex

	const double k2_dx = one_div_2a*dy31;

	const double k2_dy = one_div_2a*(dy31*step_x1 - dx31);

  double k2 = 0;

  // draw top triangle

	if (vy2 > vy1) {

    // configure line from top vertex to middle vertex

    const int sign_x2 = dx21 < 0 ? -1 : 1;

    const int step_x2 = dx21/dy21;

    const int sub_step_x2 = abs(dx21)%dy21;

    int x2 = vx1;

    int sub_step_accum2 = -dy21/2;

    // configure interpolation coefficients for the bottom vertex

    const double k3_dx = -one_div_2a*dy21;

    const double k3_dy = -one_div_2a*(dy21*step_x1 - dx21);

    double color[4], inc[4];

    double k3 = 0;

    for(int i = 0; i < 4; ++i)

      inc[i] = k2_dx*v2->color[i] + k3_dx*v3->color[i] - (k2_dx + k3_dx)*v1->color[i];

    // skip invisible rows

    int y1 = vy1, y2 = vy2;

    if (y1 < 0) {

      const int rows = (y2 < 0 ? y2 : 0) - y1;

      y1 += rows;

      x1 += rows*step_x1;

      k2 += rows*k2_dy;

      k3 += rows*k3_dy;

      sub_step_accum1 += rows*sub_step_x1;

      if (sub_step_accum1 > 0) {

        const int count = sub_step_accum1/dy31 + 1;

        sub_step_accum1 -= count*dy31;

        x1 += count*sign_x1;

        k2 += count*sign_x1*k2_dx;

        k3 += count*sign_x1*k3_dx;

      }

      x2 += rows*step_x2;

      sub_step_accum2 += rows*sub_step_x2;

      if (sub_step_accum2 > 0) {

        const int count = sub_step_accum2/dy21 + 1;

        sub_step_accum2 -= count*dy21;

        x2 += count*sign_x2;

      }

    }

    if (y2 > vh) y2 = vh;

    // iterate over visible rows

    for(int y = y1; y < y2; ++y) {

      double k1 = 1 - k2 - k3;

      for(int i = 0; i < 4; ++i)

        color[i] = k1*v1->color[i] + k2*v2->color[i] + k3*v3->color[i];

      rowNew(y, x1, x2, color, inc);

      // increment line 1

      x1 += step_x1;

      k2 += k2_dy;

      k3 += k3_dy;

      sub_step_accum1 += sub_step_x1;

      if (sub_step_accum1 > 0) {

        sub_step_accum1 -= dy31;

        x1 += sign_x1;

        k2 += sign_x1*k2_dx;

        k3 += sign_x1*k3_dx;

      }

      // increment line 2

      x2 += step_x2;

      sub_step_accum2 += sub_step_x2;

      if (sub_step_accum2 > 0)

        { sub_step_accum2 -= dy21; x2 += sign_x2; }

    }

  }

  // draw bottom triangle

	if (vy3 > vy2 && vy2 < vh) {

    // configure line from middle vertex to bottom vertex

    const int sign_x2 = dx32 < 0 ? -1 : 1;

    const int step_x2 = dx32/dy32;

    const int sub_step_x2 = abs(dx32)%dy32;

    int sub_step_accum2 = -dy32/2;

    int x2 = vx2;

    // configure interpolation coefficients for the top vertex

    const double k1_dx = -one_div_2a*dy32;

    const double k1_dy = -one_div_2a*(dy32*step_x1 - dx32);

    double color[4], inc[4];

    double k1 = -one_div_2a*dy32*(x1 - vx2);

    for(int i = 0; i < 4; ++i)

      inc[i] = k1_dx*v1->color[i] + k2_dx*v2->color[i] - (k1_dx + k2_dx)*v3->color[i];

    // skip invisible rows

    int y1 = vy2, y2 = vy3;

    if (y1 < 0) {

      const int rows = -y1;

      y1 += rows;

      x1 += rows*step_x1;

      k1 += rows*k1_dy;

      k2 += rows*k2_dy;

      sub_step_accum1 += rows*sub_step_x1;

      if (sub_step_accum1 > 0) {

        const int count = sub_step_accum1/dy31 + 1;

        sub_step_accum1 -= count*dy31;

        x1 += count*sign_x1;

        k1 += count*sign_x1*k1_dx;

        k2 += count*sign_x1*k2_dx;

      }

      x2 += rows*step_x2;

      sub_step_accum2 += rows*sub_step_x2;

      if (sub_step_accum2 > 0) {

        const int count = sub_step_accum2/dy32 + 1;

        sub_step_accum2 -= count*dy32;

        x2 += count*sign_x2;

      }

    }

    if (y2 > vh) y2 = vh;

    // iterate over visible rows

    for(int y = y1; y < y2; ++y) {

      double k3 = 1 - k1 - k2;

      for(int i = 0; i < 4; ++i)

        color[i] = k1*v1->color[i] + k2*v2->color[i] + k3*v3->color[i];

      rowNew(y, x1, x2, color, inc);

      // increment line 1

      x1 += step_x1;

      k1 += k1_dy;

      k2 += k2_dy;

      sub_step_accum1 += sub_step_x1;

      if (sub_step_accum1 > 0) {

        sub_step_accum1 -= dy31;

        x1 += sign_x1;

        k1 += sign_x1*k1_dx;

        k2 += sign_x1*k2_dx;

      }

      // increment line 2

      x2 += step_x2;

      sub_step_accum2 += sub_step_x2;

      if (sub_step_accum2 > 0)

        { sub_step_accum2 -= dy32; x2 += sign_x2; }

    }

  }

}

void setTriangle(int x1, int y1, int x2, int y2, int x3, int y3) {

  tv1.x = lx1 = x1; tv1.y = ly1 = y1;

  tv2.x = lx2 = x2; tv2.y = ly2 = y2;

  tv3.x = lx3 = x3; tv3.y = ly3 = y3;

  printf("setTriangle(%2d, %2d, %2d, %2d, %2d, %2d);\n", lx1, ly1, lx2, ly2, lx3, ly3);

}

void setLine(int x1, int y1, int x2, int y2) {

  lx1 = x1; ly1 = y1;

  lx2 = x2; ly2 = y2;

  printf("setLine(%2d, %2d, %2d, %2d);\n", lx1, ly1, lx2, ly2);

}

void generateLine() {

  setLine( randomNumber(0, vw-1), randomNumber(0, vh-1),

           randomNumber(0, vw-1), randomNumber(0, vh-1) );

}

void generateTriangle() {

  setTriangle( randomNumber(-vw/2, vw+vw/2), randomNumber(-vh/2, vh+vh/2),

               randomNumber(-vw/2, vw+vw/2), randomNumber(-vh/2, vh+vh/2),

               randomNumber(-vw/2, vw+vw/2), randomNumber(-vh/2, vh+vh/2) );

}

void init() {

  tv1.color[0] = tv1.color[3] = 1;

  tv2.color[1] = tv2.color[3] = 1;

  tv3.color[2] = tv3.color[3] = 1;

  //generateLine();

  //setLine( 2, 18, 14,  1);

  //setLine(14,  1,  2, 18);

  //setLine( 0,  0, 12,  7);

  //generateTriangle();

  setTriangle(94, 155, 116, 46, 236, 96);

}

void deinit() { }

void draw() {

  double w = windowGetWidth();

  double h = windowGetHeight();

  saveState();

  translate(0.5*w, 0.5*h);

  zoom(cs);

  translate(-0.5*vw, -0.5*vh);

  grid(vw, vh);

  if (keyWentDown("space")) generateTriangle();

  noStroke();

  fill(colorByNameA("blue", 0.5));

  triangle(lx1, ly1, lx2, ly2, lx3, ly3);

  //triangleNew(&tv1, &tv2, &tv3);

  stroke(colorByName("black"));

  strokeWidth(0.1);

  dotColored(lx1, ly1, tv1.color);

  dotColored(lx2, ly2, tv2.color);

  dotColored(lx3, ly3, tv3.color);

  restoreState();

}

int main() {

  windowSetVariableFrameRate();

  windowSetResizable(TRUE);

  windowSetSize(2*cs*vw, 2*cs*vh);

  windowSetInit(&init);

  windowSetDeinit(&deinit);

  windowSetDraw(&draw);

  windowRun();

}