主页 / 问题 / 930786
Accepted
Kaznachei
Asked:2020-01-11 13:16:03 +0000 UTC2020-01-11 13:16:03 +0000 UTC

三角形填充算法

  • 772

在这里，其实算法是一样的。连接了一个处理图像的库。

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轴不知道，从我们还是in我们）。我从顶部开始，这是最低的。我把三角形分成两半。在 Y 中上升一个像素并将其从特定的 Ax 填充到另一个特定的 Bx 。这来自文章https://habr.com/post/248159/。

重写使得迭代器最初不等于0，而是顶点的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
        }
    }
}

从文章。

我不明白为什么程序执行时间会有这样的差异。你能解释一下吗

c++

1 个回答

  1. Best Answer

    在原始算法中

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

    也就是说，如果第一段是水平的，那么我们立即切换到 mode second_half。

    你

    bool first_half = y <= t1.y;

    也就是说，如果第一段是水平的，那么在第一次迭代时我们仍然保持在 mode 中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

相关问题