Implementing a scanline algorithm

Question

I've been tasked with implementing a version of the scanline algorithm for an assignment. This program works by reading in a list of vertices and colors from a text file. Three vertices and three colors are popped from a queue at a time, then the triangle's edges are drawn. So far, my program does this pretty much perfectly. Prior to doing this, we were tasked with an assignment that drew rectangles, and it immediately became clear after running tests that the program needed to flip the y coordinates in order for the image to be drawn correctly.

Therein lies the problem. I found some algorithms for scanline triangle fill functions here, but I noticed that I'd have to modify them in order to account for the fact that the image is flipped. In a computer graphics grid, higher y values are toward the bottom. When organizing the three vertices of a given triangle, the normal thing to do is designate the vertex with the lowest y value as the top, and the vertex with the highest y value as the bottom. I inverted this in order to account for the image flip.

No matter what I do, I can't get my image to fill correctly. It'll work with these functions as is, so long as I don't flip the y values when individual pixels are drawn and the vertices are sorted in the expected manner where lower y values are toward the top. However, the resulting image is flipped vertically.

The following functions are pretty much the entirety of the program, aside from the line drawing one which I don't think needs any correction.

void FrameBuffer::drawTriangle(const Vertex& v0, const Vertex& v1, const Vertex& v2, const Color& c0, const Color& c1, const Color& c2, Functional status) {
    //Start by organizing vertices from top to botttom (need to rearrange colors as well)
    Vertex vTop, vMid, vLow;
    Color cTop, cMid, cLow;

    vTop = v0;  cTop = c0;
    if (v1[Y] > vTop[Y]) {
        vMid = vTop;    cMid = cTop;
        vTop = v1;      cTop = c1;
    }
    else {
        vMid = v1;      cMid = c1;
    }

    if (v2[Y] > vTop[Y]) {
        vLow = vMid;    cLow = cMid;
        vMid = vTop;    cMid = cTop;
        vTop = v2;      cTop = c2;
    }
    else if (v2[Y] > vMid[Y]) {
        vLow = vMid;    cLow = cMid;
        vMid = v2;      cMid = c2;
    }
    else {
        vLow = v2;      cLow = c2;
    }

    //Draw the edges of the triangle
    drawLine(vTop, vMid, cTop, cMid, status);
    drawLine(vTop, vLow, cTop, cLow, status);
    drawLine(vMid, vLow, cMid, cLow, status);

    //Fill the triangle; first case is flat bottom
    if (vMid[Y] == vLow[Y]) {
        fillFlatBottom(vTop, vMid, vLow, status);
    }
    //Second case is flat top
    else if (vTop[Y] == vMid[Y]) {
        fillFlatTop(vTop, vMid, vLow, status);
    }
    //General case; triangle can be split into flat bottom above a flat top
    else {
        Vertex vNew;        //This represents the point on the triangle across from the "midpoint"
        vNew[Y] = vMid[Y];
        vNew[X] = vTop[X] + ((vMid[Y] - vTop[Y]) / (vLow[Y] - vTop[Y])) * (vLow[X] - vTop[X]);
        vNew[Z] = (vLow[Z] * (vNew[X] - vTop[X]) * (vNew[Y] - vMid[Y]) + vTop[Z] * (vNew[X] - vMid[X]) * (vNew[Y] - vLow[Y]) + vMid[Z] * (vNew[X] - vLow[X]) * (vNew[Y] - vTop[Y]) - vMid[Z] * (vNew[X] - vTop[X]) * (vNew[Y] - vLow[Y]) - vLow[Z] * (vNew[X] - vMid[X]) * (vNew[Y] - vTop[Y]) - vTop[Z] * (vNew[X] - vLow[X]) * (vNew[Y] - vMid[Y])) / ((vNew[X] - vTop[X]) * (vNew[Y] - vMid[Y]) + (vNew[X] - vMid[X]) * (vNew[Y] - vLow[Y]) + (vNew[X] - vLow[X]) * (vNew[Y] - vTop[Y]) - (vNew[X] - vTop[X]) * (vNew[Y] - vLow[Y]) - (vNew[X] - vMid[X]) * (vNew[Y] - vTop[Y]) - (vNew[X] - vLow[X]) * (vNew[Y] - vMid[Y]));

        fillFlatBottom(vTop, vMid, vNew, status);
        fillFlatTop(vMid, vNew, vLow, status);
    }
}

//Draw from bottom up (something is happening here that causes errors)
void FrameBuffer::fillFlatTop(const Vertex& v0, const Vertex& v1, const Vertex& v2, Functional status) {
    double xSlope1 = -(v2[X] - v0[X]) / (v2[Y] - v0[Y]);
    double xSlope2 = -(v2[X] - v1[X]) / (v2[Y] - v1[Y]);

    Vertex curV0 = v2;
    Vertex curV1 = v2;

    //v0 is the highest point with the highest y value and v2 is the lowest (for this case) with the lowest y value
    while (curV0[Y] < v0[Y] && curV1[Y] < v0[Y]) {
        Color curC0 = image.get(curV0[X], curV0[Y]);
        Color curC1 = image.get(curV1[X], curV1[Y]);

        drawLine(curV0, curV1, curC0, curC1, status);

        curV0[Y] += 1;  curV0[X] -= xSlope1;
        curV1[Y] += 1;  curV1[X] -= xSlope2;
    }
}

//Draw from top down (something is happening here that causes errors)
void FrameBuffer::fillFlatBottom(const Vertex& v0, const Vertex& v1, const Vertex& v2, Functional status) {
    double xSlope1 = -(v1[X] - v0[X]) / (v1[Y] - v0[Y]);
    double xSlope2 = -(v2[X] - v0[X]) / (v2[Y] - v0[Y]);

    Vertex curV0 = v0;
    Vertex curV1 = v0;

    //v0 is the highest point with the highest y value and v1 (for this case) is the lowest with the lowest y value
    while (curV0[Y] >= v1[Y] && curV1[Y] >= v1[Y]) {
        Color curC0 = image.get(curV0[X], curV0[Y]);
        Color curC1 = image.get(curV1[X], curV1[Y]);

        drawLine(curV0, curV1, curC0, curC1, status);

        curV0[Y] -= 1;  curV0[X] += xSlope1;
        curV1[Y] -= 1;  curV1[X] += xSlope2;
    }
}

To provide some perspective, this is the resulting image when nothing is filled: https://i.sstatic.net/av26e.jpg

This occurs when only fillFlatBottom runs: https://i.sstatic.net/PjBRx.jpg

This occurs when only fillFlatTop runs: https://i.sstatic.net/lW4pG.jpg

What exactly am I doing wrong? It's apparent that the line algorithm is not causing this problem. I'm either calculating the point across from the midpoint (that being vNew) incorrectly or I've messed up the fill algorithms somehow.

Answer 1

Here is a code I use for drawing filled triangle. It's based on algorithm described on this page: Triangle Fillers . The code is part of template based class and it uses std library and some image container, but you can easily modify the code to suite your needs:

struct spFPoint
    {
    float x;
    float y;
    };

//-----------------------
// draw triangle filled
//-----------------------
  template <class T>
  static void TriangleFilled(spImage<T> *img, T val, int x1, int y1, int x2, int y2, int x3, int y3)
    {
    // this piece of code is used only for sorting  
    spFPoint pt;
    pt.x = x1;
    pt.y = y1;
    vector <spFPoint> triangle;
    triangle.push_back(pt);
    pt.x = x2;
    pt.y = y2;
    triangle.push_back(pt);
    pt.x = x3;
    pt.y = y3;
    triangle.push_back(pt);
    stable_sort(triangle.begin(), triangle.end(), yAscFPoint);
    // here comes the actual algorithm
    spFPoint A, B, C;
    float   dx1, dx2, sx1, sx2, y;
    A = triangle[0];
    B = triangle[1];
    C = triangle[2];
    B.y-A.y > 0 ? dx1 = (B.x-A.x)/(B.y-A.y) : dx1=0;
    C.y-A.y > 0 ? dx2 = (C.x-A.x)/(C.y-A.y) : dx2=0;
    sx1 = sx2 = A.x;
    y = A.y;
    // upper half
    for (; y <= B.y; y++, sx1+=dx1, sx2+=dx2)
        ScanLine(img, val, y, sx1, sx2);  // or your function for drawing horizontal line 
    // lower half
    C.y-B.y > 0 ? dx1 = (C.x-B.x)/(C.y-B.y) : dx1=0;
    sx1 = B.x;
    y   = B.y;
    for (; y <= C.y; y++, sx1+=dx1, sx2+=dx2)
        ScanLine(img, val, y, sx1, sx2); // or your function for drawing horizontal line
    }
  //----------------------
  // draw scanline (single color)
  //----------------------
  template <class T>
  static void ScanLine(spImage<T> *img, T val, int y, int x1, int x2)
    {
    if (y < 0 || y > img->Height()-1) return;
    if ((x1 < 0 && x2 < 0) || (x1 > img->Width()-1 && x2 > img->Width()-1 )) return;
    if (x1 > x2)   // swap coordinates
       {
       x1 = x1^x2;
       x2 = x1^x2;
       x1 = x1^x2;
       }
    if (x1 < 0) x1 = 0;
    if (x2 > img->Width()-1) x2 = img->Width()-1;
    for (int j = x1; j <= x2; j++)
        img->Pixel(y, j) = val;     // draw point
    }
  //----------------------
  // sorting function
  //----------------------
  inline static bool yAscFPoint(spFPoint lhs, spFPoint rhs) { return lhs.y < rhs.y;}  

If your image or drawing canvas is upside-down, before calling TriangleFilled function, invert the y coordinates. It's easier to do it prior to function call, then inside the function:

   y1 = img->Height()-1 - y1;
   y2 = img->Height()-1 - y2;
   y3 = img->Height()-1 - y3;

But, from the nature of your assignment

This program works by reading in a list of vertices and colors from a text file.

it seems that you need to perform Gouraud filling/shading and this is a bit longer piece of code.

Answer 2

Let's just look at one of the functions: fillFlatTop for now. The idea is that for the two points CurV0 and curV1 to move along the two sides of the triangle from the bottom-most vertex v2 to the top vertices v0 and v1, respectively.

Let's check that:

• For curV0, as the y goes from that of v2 to v0, the y changes by v0.y - v2.y. But, you want the x to change equal to v0.x - v2.x, so for every 1 change in y, you want to have (v0.x - v2.x) / (v0.y - v2.y)

• For curV1, the same as above, but replacing 0s with 1s.

If you look at your code, the slopes are correct (there is a double-negative, but it works out correct).

Now, let's look at fillFlatBottom. Same as above:

• For curV0 moving from v0 to v1, change in y is v1.y - v0.y corresponding to a v1.x - v0.x change in x, so for every 1 change in y you want the x to change by (v1.x - v0.x) / (v1.y - v0.y).

• For curV1, the same as above, with 2s instead of 1s

Comparing this with your code, it seems that the slope that you have has the wrong sign, or if you wanted to go with the same convention as fillFlatTop you should keep the slopes as they are, but change the increments (x += ...) to decrements (x -= ...), again, to have the double-negative :-)