Реализация алгоритма развертки

Question

Мне поручено реализовать версию алгоритма сканирования для задания. Эта программа работает путем чтения в списке вершин и цветов из текстового файла. Три вершины и три цвета выталкиваются из очереди за раз, затем обращаются к краям треугольника. До сих пор моя программа прекрасно справлялась. Прежде чем это сделать, нам было поручено задание, которое рисовало прямоугольники, и сразу же после прохождения тестов сразу же стало ясно, что программе необходимо перевернуть координаты y, чтобы изображение было правильно отображено.

В этом проблема. Я нашел несколько алгоритмов для функций заполнения треугольника scanline here, но я заметил, что мне придется их модифицировать, чтобы учесть тот факт, что изображение перевернуто. В сетке компьютерной графики более высокие значения 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, поэтому для каждого 1 изменения y, вы хотите иметь (v0.x - v2.x)/(v0.y - v2.y)

• Для curV1, то же самое, что и выше, но заменяя 0 с с 1 с.

Если вы посмотрите на свой код, наклоны верны (есть двойное отрицательное значение, но оно работает правильно).

Теперь давайте рассмотрим fillFlatBottom. То же самое, что и выше:

• Для curV0 перехода от v0 к v1, изменение y является v1.y - v0.y соответствующего v1.x - v0.x изменению x, поэтому для каждых 1 изменений y вы хотите x изменить с помощью (v1.x - v0.x)/(v1.y - v0.y).

• Для curV1, такой же, как и выше, с 2 с вместо 1 s

Сравнивая это с вашим кодом, кажется, что наклон, что у вас есть имеет неправильный знак, или если вы хотите идти с той же конвенции, как fillFlatTop вы должны держать на склонах, как они есть, но изменения приращения (x += ...) в пошаговом (x -= ...), опять-таки, иметь двойной отрицательный :-)

Answer 2

Вот код, который я используйте для рисования заполненный треугольник. Он основан на алгоритме, описанном на этой странице: Triangle Fillers . Кодом является частью класса на основе шаблона, и он использует зУю библиотеку и некоторые изображения контейнера, но вы можете легко изменить код в отели:

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, и это немного длинный фрагмент кода.