Алгоритм заливки треугольника

108
05 августа 2019, 13:20

Вот тут по сути алгоритм один и тот же. Подключил библиотеку, которая работает с изображениями.

for (int i=0; i<total_height; i++) {
    bool second_half = i>t1.y-t0.y || t1.y==t0.y;
    int segment_height = second_half ? t2.y-t1.y : t1.y-t0.y;
    float alpha = (float)i/total_height;
    float beta  = (float)(i-(second_half ? t1.y-t0.y : 0))/segment_height; // be careful: with above conditions no division by zero here
    Vec2i A =               t0 + (t2-t0)*alpha;
    Vec2i B = second_half ? t1 + (t2-t1)*beta : t0 + (t1-t0)*beta;
    if (A.x>B.x) std::swap(A, B);
    for (int j=A.x; j<=B.x; j++) {
        image.set(j, t0.y+i, color); // attention, due to int casts t0.y+i != A.y
    }
}

Хочу нарисовать треугольник и заполнить его. Координатная система тут трехмерная и начало в нижнем левом углу ( как в школе , ось Y вверх, ось X направо, ось Z не знаю, либо от нас, либо в нас ) . Начинаю с вершины, которая ниже всего. Типа делю треугольник пополам. Поднимаюсь на один пиксель по Y и заполняю его от определенного A.x до другого определенного B.x . Это из статьи https://habr.com/post/248159/.

Переписал так, чтобы итератор не равнялся нулю изначально, а Y-координате вершины, которая имеет меньшую Y-координату

for(int y = t0.y; y <= t2.y; y++)
    {
        bool first_half = y <= t1.y;
        int segment_height = first_half ? (t1.y - t0.y):(t2.y - t1.y);
        float beta = (y - (first_half ? t0.y:t1.y))/static_cast<float>(segment_height);
        float alpha = (y - t0.y)/static_cast<float>(total_height);
        Vec2i A = t0 + (t2 - t1)*alpha;
        Vec2i B = first_half ? (t0 + (t1 - t0)*beta) : (t1 + (t2 - t1)*beta);
        if (A.x > B.x) std::swap(A,B);
        for (int j = A.x; j < B.x; j++)
            image.set(j, y, color);
    }

Если количество треугольников небольшое. То разница в примерно в 0.05 секунд. А если треугольников больше десяти тысяч я так и не дождался выполнения программы. А вот с алгоритмом из статьи время выполнения программы такое же, как будто я рисую немного треугольников. Вот функция

void triangle(Vec2i t0, Vec2i t1, Vec2i t2, TGAImage &image, TGAColor color) {
    if (t0.y==t1.y && t0.y==t2.y) return; // i dont care about degenerate triangles
    if (t0.y>t1.y) std::swap(t0, t1);
    if (t0.y>t2.y) std::swap(t0, t2);
    if (t1.y>t2.y) std::swap(t1, t2);
    int total_height = t2.y-t0.y;
    for (int i=0; i<total_height; i++) {
        bool second_half = i>t1.y-t0.y || t1.y==t0.y;
        int segment_height = second_half ? t2.y-t1.y : t1.y-t0.y;
        float alpha = (float)i/total_height;
        float beta  = (float)(i-(second_half ? t1.y-t0.y : 0))/segment_height; // be careful: with above conditions no division by zero here
        Vec2i A =               t0 + (t2-t0)*alpha;
        Vec2i B = second_half ? t1 + (t2-t1)*beta : t0 + (t1-t0)*beta;
        if (A.x>B.x) std::swap(A, B);
        for (int j=A.x; j<=B.x; j++) {
            image.set(j, t0.y+i, color); // attention, due to int casts t0.y+i != A.y
        }
    }
}

из статьи.

Не понимаю, почему такая разница во времени выполнения программы. Объясните, пожалуйста

Answer 1

В оригинальном алгоритме

bool second_half = i>t1.y-t0.y || t1.y==t0.y;

То есть если первый отрезок является горизонтальным, то мы сразу переходим в режим second_half.

У вас

bool first_half = y <= t1.y;

То есть если первый отрезок является горизонтальным, то на самой первой итерации мы все равно остаемся в режиме first_half. Далее

int segment_height = first_half ? (t1.y - t0.y):(t2.y - t1.y);

значение segment_height получается равным 0. И далее

float beta = (y - (first_half ? t0.y:t1.y))/static_cast<float>(segment_height);

возникает деление 0 на 0, возможно скрытое из-за использования плавающего типа в делении.

Оригинальный вариант уныл, неэффективен и пионерск, но все таки его автор распознал опасность потенциального деления на 0 и принял меры для ее избежания. О чем даже написал комментарий.

READ ALSO
Массив с потокобезопасными объектами C++

Массив с потокобезопасными объектами C++

Допустим, у меня есть класс Foo

86
Как обратится к тексту на textEdit в qt?

Как обратится к тексту на textEdit в qt?

Мне нужно програмно изменить текст в QTextEditИ не знаю как к нему обратится, точнее к его тексту

114
Аналоги функций Python str и int в С++

Аналоги функций Python str и int в С++

В Python есть две функции: str и intЕсть ли возможность так переключаться между строкой и числом в C++? У меня есть a = 10

113