1

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

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

из статьи.

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

4
  • Уточните, что вы понимаете под "временем компиляции" и "так и не дождался компиляции"?
    – Kromster
    11 янв 2019 в 5:25
  • Под временем компиляции я имел ввиду runtime(тупанул). С алгоритмом из статьи я дождался выполнения за 2 секунды ( и так почти с любым количеством треугольников в пределах разумного ). А с моим переписанным время выполнения при большом количестве треугольников неизвестно. Этого не дождался. Запустил код, даже через две минуты ничего не выводило.
    – Kaznachei
    11 янв 2019 в 5:28
  • Количество image.set должно примерно соответствовать площади треугольников и быть близким для обоих функций. Это выполняется?
    – MBo
    11 янв 2019 в 5:36
  • 2
    @Kaznachei отредактируйте вопрос, замените "время компиляции" корректным термином.
    – Kromster
    11 янв 2019 в 5:47

1 ответ 1

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 и принял меры для ее избежания. О чем даже написал комментарий.

1
  • Все, спасибо огромное, просто добавил условие ( y <= t1.y && t1.y != t0.y). Теперь программа выполняется. Спасибо
    – Kaznachei
    11 янв 2019 в 7:10

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.