Fill triangle(Flat-bottom, Flat-top)

Fill triangle is also a classic issue in computer graphic.

In this section, we're going to use a classic solution to fill triangle(fill mesh) which call - Flat bottom, Flat top.

The point is, we divide a triangle into 2 triangles(up and bottom), we get the Mx,My. And then render(scanline) those triangles sparately.

But first thing, we need to figure out the triangle oriantation, cuz it can be any rotate and direction.

To clarify this, we need to sort those triangle vectors from up to buttom.

So, in this case, we jsut need to compare the y-axis:

void draw_filled_triangle(int x0, int y0, int x1, int y1, int x2, int y2, uint32_t color) {
  // We need to sort the vertices by y-coordinate ascending( y0 < y1 < y2)
  if (y0 > y1) {
    int_swap(&y0, &y1);
    int_swap(&x0, &x1);
  }
  if (y1 > y2) {
    int_swap(&y1, &y2);
    int_swap(&x1, &x2);
  }
  if (y0 > y1) {
    int_swap(&y0, &y1);
    int_swap(&x0, &x1);
  }
}

Next step, we need to find out the position of Mx and My. cuz it make us know the edge of sparated triangles.

Since we sort the triangle, we know the My is equal to y1.y (Like above image).

But for Mx, we consider below diagram:

We find that the triangle ABE and triangle ACD are the similar triangle

So we replace into vector:

Solve the formula:

And we get the Mx!

Next step, we start to fill the trangle:

Start the flat bottom first:

We start from top at x0 y0 ,and scan each line by slope line of y0 to y1 and y0 to y2.

So in this time, we're talking about how x change per y. That is Δx / Δ y.

void fill_flat_bottom_triangle(int x0, int y0, int x1, int y1, int x2, int y2, uint32_t color) {
  // Find the two slopes (two triangle legs)
  float inv_slope_1 =  (float)(x1 - x0) / (y1 - y0);
  float inv_slope_2 =  (float)(x2 - x0) / (y2 - y0);

  float x_start = x0;
  float x_end = x0;

  // Loop all the scnaline from top to bottom
  for (int y = y0; y <= y2; y++) {
    draw_line(x_start, y, x_end, y, color);

    x_start += inv_slope_1;
    x_end += inv_slope_2;
  }
}

then the flat top

this time, we're from bottom x2,y2 up to scan each line.

void fill_flat_top_triangle(int x0, int y0, int x1, int y1, int x2, int y2, uint32_t color) {
  // Find the two slopes (two triangle legs)
  float inv_slope_1 =  (float)(x2 - x0) / (y2 - y0);
  float inv_slope_2 =  (float)(x2 - x1) / (y2 - y1);

  float x_start = x2;
  float x_end = x2;

  // Loop all the scnaline from bottom to bottom
  for (int y = y2; y >= y0; y--) {
    draw_line(x_start, y, x_end, y, color);

    x_start -= inv_slope_1;
    x_end -= inv_slope_2;
  }
}

Resources: pikuma course