How can I draw filled triangles in C++?

Question

VERY IMPORTANT NOTE: Im trying to fill a triangle. I have already made the 3D part. Sorry if this wasn't understandable.

I'm currently trying to create a simple 3D-Engine. Well, I have successfully drawn a triangle using this method.

void DrawTriangle(int x1, int y1, int x2, int y2, int x3, int y3) {
  drawLine(x1, y1, x2, y2); //Usage: drawLine(x, y, x1, y1)
  drawLine(x2, y2, x3, y3);
  drawLine(x3, y3, x1, y1);
}

After this method worked surprisingly well and a cube appeared very convincing, I tried to add lighting. Now I'm facing a pretty big problem. After a long thought I found this method of filling a triangle but here is the problem. It paints a few triangles but not all. Unfortunately I cannot show any pictures because I do not have a camera and a screenshot would not work (as I explain later). My theory is that it only draws bottom flat triangles (or the other way around). What should I change about my method so that it works? Thanks in advance.

This is my filling code:

void FillTriangle(int x1, int y1, int x2, int y2, int x3, int y3) {
 drawLine(x1, y1, x2, y2);
 drawLine(x2, y2, x3, y3);
 drawLine(x3, y3, x1, y1);
 for(int x = x1; x<=x2; x++) {
    for(int y = y1; y<=y2; y++) {
     drawLine(x3, y3, x, y);
    }
  }
}

• I'm currently working with an Arduino UNO
• I'm using the Nokia 5110 display
• I'm using C++
• I'm using this library for displaying
• Do not downvote, just comment what you need to know.
• I have already tried this code but it wasn't working.

Answer 1

There's plenty of different rasterization algorithms, but many articles you find these days are optimized for systems with fast floating point math. For your use case, the ones on this page would probably work better: http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html.

If you already have a function to draw lines, you can use the Bresenham triangle algorithm to do the job:

1. Draw the line V1V2 using the bresenham algorithm, but stop if the algorithm moves one pixel in y-direction.
2. Draw also the line V1V3 using the bresenham algorithm, and stop if the algorithm moves one pixel in y-direction.
3. At this point we are on the same y-coordinate for line V1V2 as well as for line V1V3.
4. Draw the horizontal lines between both current line points.
5. Repeat above steps until you triangle is completely rasterised.

Answer 2

A relatively fast algorithm in pseudocode:

function fill_a_triangle(x1,y1,x2,y2,x3,y3)
  //get length of all sides
  d1 = sqrt(((y2-y1)**2)+((x2-x1)**2))
  d2 = sqrt(((y3-y2)**2)+((x3-x2)**2))
  d3 = sqrt(((y1-y3)**2)+((x1-x3)**2))
  if(((d1<d2)or(d1=d2))and((d1<d2)or(d1=d2)))
    tx = x1
    ty = y1
    vx = (x2-x1)/d1
    vy = (y2-y1)/d1
    counter = 0
    while(counter<d1)
      draw_a_line(x3,y3,tx,ty)
      //drawing a line from point(x3,y3) to point(tx,ty).
      tx = tx + vx
      ty = ty + vy
      counter = counter + 1
  else if((d2<d3)or(d2=d3))
    tx = x2
    ty = y2
    vx = (x3-x2)/d2
    vy = (y3-y2)/d2
    counter = 0
    while(counter<d2)
      draw_a_line(x1,y1,tx,ty)
      tx = tx + vx
      ty = ty + vy
      counter = counter + 1
  else
    tx = x3
    ty = y3
    vx = (x1-x3)/d3
    vy = (y1-y3)/d3
    counter = 0
    while(counter<d3)
      draw_a_line(x2,y2,tx,ty)
      tx = tx + vx
      ty = ty + vy
      counter = counter + 1

Note that how accurately this algorithm performs is affected by how you implement it. If it doesn't work, try drawing the individual dots in a line rather than using a built in function.