我需要一个像素完美的三角形填充算法来避免混叠伪像
我正在协助有人使用用户界面代码来可视化数学图像分析。 在此过程中，我们将2D形状的一部分分割为三角形，并在UI上填充其中的一些三角形。
我们正在寻找一种填充算法，该算法可以保证如果两个三角形共享一条边（具体来说，如果三角形的任意两个顶点相同），那么无论绘制顺序和锯齿如何，线上都不会有空白的未拉伸像素两者之间。 （如果某些像素被绘制两次，那就没问题。）在任意缩放下，结果应该看起来不错。 一些三角形可能是非常薄的细长条，宽度低至1像素。
理想情况下，它也应该是一个合理有效的填充算法！
在三角形渲染中不会使用抗锯齿，因为最终图像需要为1位深度。
上下文是图像识别应用程序，因此所有顶点坐标都精确到一个像素。
鉴于这些要求，看起来有一个简单的解决方案。
首先，栅格化三角形边。 您可以使用Bresenham的线条绘制算法（如下面的代码所示）或任何有效的方法。 然后填写介于两者之间的区域。 这将适用于任意薄的三角形。
为了确保没有间隙，无论绘制三角形的顺序如何，并且无论提供给三角形绘制代码的顶点的顺序如何，您都希望在共享边的三角形中以相同的方式光栅化共享边。 相同的方式每次都意味着相同的像素。
为了保证每次从相同的顶点坐标对中获得相同的像素，你基本上想要建立一个固定的顺序，即建立一个规则，它总是从给定的两个顶点中选择相同的一个顶点而不管顺序如何。给他们的。
强制执行此顺序的一种简单方法是将线（三角形边）视为二维向量，如果它指向负y的方向或平行于x轴并指向负x的方向，则将其方向翻转。 一些ASCII艺术的时间！ 🙂
3 2 1 \ | / \ | / \|/ 4 --------+--------- 0 /|\ / | \ / | \ 5 6 7 4 -> 0 5 -> 1 6 -> 2 7 -> 3 看，这里的线段，比方说，1和线段5实际上是同一种东西，唯一的区别是从原点的端点到另一个端点的方向。 因此，我们通过将段4到7转换为段0到3来减少这些情况，并消除方向模糊。 IOW，我们选择朝着增加y的OR的方向前进，如果y在边缘上是相同的，则在增加x的方向上。
以下是您可以在代码中执行此操作的方法：
#include #include #include #include #include #include #define SCREEN_HEIGHT 22 #define SCREEN_WIDTH 78 // Simulated frame buffer char Screen[SCREEN_HEIGHT][SCREEN_WIDTH]; void SetPixel(long x, long y, char color) { if ((x < 0) || (x >= SCREEN_WIDTH) || (y < 0) || (y >= SCREEN_HEIGHT)) { return; } if (Screen[y][x] == ' ') Screen[y][x] = color; else Screen[y][x] = '*'; } void Visualize(void) { long x, y; for (y = 0; y < SCREEN_HEIGHT; y++) { for (x = 0; x < SCREEN_WIDTH; x++) { printf("%c", Screen[y][x]); } printf("\n"); } } typedef struct { long x, y; unsigned char color; } Point2D; // min X and max X for every horizontal line within the triangle long ContourX[SCREEN_HEIGHT][2]; #define ABS(x) ((x >= 0) ? x : -x) // Scans a side of a triangle setting min X and max X in ContourX[][] // (using the Bresenham's line drawing algorithm). void ScanLine(long x1, long y1, long x2, long y2) { long sx, sy, dx1, dy1, dx2, dy2, x, y, m, n, k, cnt; sx = x2 - x1; sy = y2 - y1; /* 3 2 1 \ | / \ | / \|/ 4 --------+--------- 0 /|\ / | \ / | \ 5 6 7 4 -> 0 5 -> 1 6 -> 2 7 -> 3 */ if (sy < 0 || sy == 0 && sx < 0) { k = x1; x1 = x2; x2 = k; k = y1; y1 = y2; y2 = k; sx = -sx; sy = -sy; } if (sx > 0) dx1 = 1; else if (sx < 0) dx1 = -1; else dx1 = 0; if (sy > 0) dy1 = 1; else if (sy < 0) dy1 = -1; else dy1 = 0; m = ABS(sx); n = ABS(sy); dx2 = dx1; dy2 = 0; if (m < n) { m = ABS(sy); n = ABS(sx); dx2 = 0; dy2 = dy1; } x = x1; y = y1; cnt = m + 1; k = n / 2; while (cnt--) { if ((y >= 0) && (y < SCREEN_HEIGHT)) { if (x < ContourX[y][0]) ContourX[y][0] = x; if (x > ContourX[y][1]) ContourX[y][1] = x; } k += n; if (k < m) { x += dx2; y += dy2; } else { k -= m; x += dx1; y += dy1; } } } void DrawTriangle(Point2D p0, Point2D p1, Point2D p2) { long y; for (y = 0; y < SCREEN_HEIGHT; y++) { ContourX[y][0] = LONG_MAX; // min X ContourX[y][1] = LONG_MIN; // max X } ScanLine(p0.x, p0.y, p1.x, p1.y); ScanLine(p1.x, p1.y, p2.x, p2.y); ScanLine(p2.x, p2.y, p0.x, p0.y); for (y = 0; y < SCREEN_HEIGHT; y++) { if (ContourX[y][1] >= ContourX[y][0]) { long x = ContourX[y][0]; long len = 1 + ContourX[y][1] - ContourX[y][0]; // Can draw a horizontal line instead of individual pixels here while (len--) { SetPixel(x++, y, p0.color); } } } } int main(void) { Point2D p0, p1, p2, p3; // clear the screen memset(Screen, ' ', sizeof(Screen)); // generate random triangle coordinates srand((unsigned)time(NULL)); // p0 - p1 is going to be the shared edge, // make sure the triangles don't intersect for (;;) { p0.x = rand() % SCREEN_WIDTH; p0.y = rand() % SCREEN_HEIGHT; p1.x = rand() % SCREEN_WIDTH; p1.y = rand() % SCREEN_HEIGHT; p2.x = rand() % SCREEN_WIDTH; p2.y = rand() % SCREEN_HEIGHT; p3.x = rand() % SCREEN_WIDTH; p3.y = rand() % SCREEN_HEIGHT; { long vsx = p0.x - p1.x; long vsy = p0.y - p1.y; long v1x = p0.x - p2.x; long v1y = p0.y - p2.y; long v2x = p0.x - p3.x; long v2y = p0.y - p3.y; long z1 = vsx * v1y - v1x * vsy; long z2 = vsx * v2y - v2x * vsy; // break if p2 and p3 are on the opposite sides of p0-p1 if (z1 * z2 < 0) break; } } printf("%ld:%ld %ld:%ld %ld:%ld %ld:%ld\n\n", p0.x, p0.y, p1.x, p1.y, p2.x, p2.y, p3.x, p3.y); // draw the triangles p0.color = '-'; DrawTriangle(p0, p3, p1); p1.color = '+'; DrawTriangle(p1, p2, p0); Visualize(); return 0; }
样本输出：
30:10 5:16 16:6 59:17 +++ ++++++++ ++++++++++++ +++++++++++++++++ +++++++++++++++****--- +++++++++++++****----------- ++++++++++****------------------- ++++++*****---------------------------- +++****------------------------------------- ****--------------------------------------------- *----------------------------------------------------- -
传说：
- “+” - 三角形1的像素
- “ - ” - 三角形2的像素
- “*” - 三角形1和2之间共享的边缘的像素
请注意，即使没有未填充的间隙（像素），其像素（在共享边缘上）被覆盖的三角形（由于在其上方绘制的另一个三角形）如果太薄也可能显示为不相交或形状笨拙。 例：
2:20 12:8 59:15 4:17 *++++++ *+++++++++++++ *+++++++++++++++++++++ -*++++++++++++++++++++++++++++ -*++++++++++++++++++++++++++++++++++++ *+++++++++++++++++++++++++++++++++++++++++++ *+++++++++++++++++++++++++++++++++++++++++++++++++++ *+++++++++++++++++++++++++++++++++++++++++++++++++++++ *+++++++++++++++++++++++++++++++++++++++++++ -*+++++++++++++++++++++++++++++++ -*+++++++++++++++++++++ *++++++++++ *
您对相邻三角形的关注是有效的。 如果两个三角形共享一条边，则需要确保沿着该边的每个像素“仅”属于一个三角形或另一个三角形。 如果其中一个像素不属于任何一个三角形，则会有间隙。 如果它属于两个三角形，则您已经过度绘制（这是低效的），颜色可能取决于三角形呈现的顺序（可能不是确定性的）。
由于你没有使用抗锯齿，这实际上并不太难。 这不是一个智能算法，您需要仔细实施。
栅格化三角形的典型方法是计算从顶部到底部为三角形一部分的水平线段。 您可以通过跟踪当前左右边缘来实现此目的，并基本上对每条扫描线上的每条边进行x截距计算。 它也可以通过一起运行的两种Bresenhem式线绘制算法来完成。 实际上，光栅化相当于对函数的多次调用，该函数在某些扫描线y从某些左坐标x0到某些右坐标x1绘制水平线段。
void DrawHLine(int y, int x0, int x1);
通常，所做的是确保光栅化器以一致的方式对x截距进行舍入，这样无论它们是一个三角形的右边缘还是相邻三角形的左边缘，都会一致地计算x坐标。 。 这保证了共享边缘上的每个像素都属于两个三角形。
我们通过调整DrawHLine解决双重所有权问题，使其填充x0包括x0的像素。 因此，共享边缘上的所有这些双重拥有的像素被定义为属于共享边缘右侧的三角形。
您正在寻找的是一个floodfill算法。
这是一个 。
另一个环节 。
您可以谷歌’floodfill-algorithm’获取更多信息。
[编辑]
也许这个网站 [基于Shader的线框图]可以提供更多的想法。
它不是最有效的，但你可以在包含三角形的正方形上循环，并测试每个像素是否在三角形内。
伪代码：
for(x : minX -> maxX) for(y : minY -> maxY) if(triangle.contains(x,y)) drawPixel(x,y);
其中minX是三个顶点之间的最小X坐标，类似于maxX，minY和maxY。
对于更快的算法，您可以先做一些快速和脏的填充（例如斜线填充），然后对边缘周围的像素执行此操作。
这里描述了三角形测试。
这是一个研究得很好的问题。 了解bresenham线绘制算法。