一种扫描线算法的实现

Question

我的任务是为分配实现scanline算法的一个版本。此程序通过读取文本文件中的顶点和颜色列表来工作。一次从队列中弹出三个顶点和三种颜色，然后绘制三角形的边缘。到目前为止，我的程序做得相当完美。在此之前，我们的任务是绘制矩形，在运行测试后，程序需要翻转y坐标才能正确绘制图像。

问题就在这里。我为scanline三角形填充函数这里找到了一些算法，但我注意到，为了解释图像翻转的事实，我必须修改它们。在计算机图形网格中，较高的y值位于底部。在组织给定三角形的三个顶点时，通常要做的事情是指定y值最低的顶点作为顶点，以y值最高的顶点作为顶点。我倒置这是为了解释图像翻转。

无论我做什么，我都无法正确地填补我的形象。它将按原样处理这些函数，只要在绘制单个像素时不翻转y值，并且按期望的方式对顶点进行排序，此时y值较低。但是，产生的图像是垂直翻转的。

下面的函数基本上是程序的全部，除了我认为不需要任何修正的线条绘制功能之外。

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;
    }
}

为了提供一些透视图，这是在什么都没有填充时生成的映像：http://imgur.com/a/VOpWJ

只有fillFlatBottom运行时才会发生这种情况：http://imgur.com/a/nexR9

只有fillFlatTop运行时才会发生这种情况：http://imgur.com/a/flRCK

我到底做错了什么？很明显，直线算法并没有引起这个问题。我要么不正确地计算中点(即vNew)的点，要么我以某种方式混淆了填充算法。

Answer 1

让我们看一下其中一个函数：fillFlatTop。其思想是，对于两点CurV0和curV1，沿着三角形的两边，分别从最底部的顶点v2移动到顶点v0和v1。

让我们检查一下：

• 对于curV0，随着y从v2到v0，y由v0.y - v2.y改变。但是，您希望x更改等于v0.x - v2.x，因此对于y中的每一个1更改，您都希望有(v0.x - v2.x) / (v0.y - v2.y)
• 对于curV1，与上面相同，但是用1替换0。

如果您查看您的代码，斜率是正确的(有一个双负，但它的计算正确)。

现在，让我们来看看fillFlatBottom。与上述相同：

• 对于从curV0到v0的v1，y中的更改是与x中的v1.x - v0.x变化相对应的v1.y - v0.y，因此对于y中的每个1更改，您都希望x通过(v1.x - v0.x) / (v1.y - v0.y)进行更改。
• 对于curV1，与上面相同，使用2s而不是1s

与您的代码相比，您的斜率似乎有错误的标志，或者如果您想遵循与fillFlatTop相同的约定，您应该保持斜率原样，但将增量(x += ...)改为递减(x -= ...)，再次更改为双负：)

Answer 2

这是我用来绘制填充三角形的代码。它基于本页描述的算法：三角形填料。代码是基于模板的类的一部分，它使用std库和一些图像容器，但您可以轻松地修改代码以满足您的需要：

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;}  

如果您的图像或绘图画布是颠倒的，在调用TriangleFilled函数之前，反转y坐标。在函数调用之前更容易执行，然后在函数内部执行：

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

但是，从你任务的性质来看

此程序通过读取文本文件中的顶点和颜色列表来工作。

似乎您需要执行Gouraud填充/阴影，这是一个更长的代码。