完美的填充三角形渲染算法？

Question

在哪里可以获得渲染填充三角形的算法？ Edit3: 我无法使用 OpenGL 来渲染它。我需要每像素算法。

我的目标是从三角形渲染正多边形，所以如果我使用这种三角形填充算法，每个三角形的边缘不会重叠（或在它们之间产生间隙），因为如果我使用示例 XOR 来渲染像素。

因此，渲染质量应与 OpenGL 渲染相匹配，因此我应该能够定义（例如）具有 N 个顶点的圆，并且它会正确渲染为任意大小的圆；因此它不像某些三角形填充算法那样仅使用整数坐标来渲染它。

我需要能够自己控制三角形填充：我可以添加自己的关于如何渲染每个单独像素的逻辑。所以我需要渲染背后的裸代码来完全控制它。它应该足够高效地绘制数以万计的三角形，而无需等待超过一秒钟。 （我不确定最多能多快，但我希望不会超过10秒）。

首选语言是 C++，但我可以根据需要转换其他语言。

如果没有免费的算法，我在哪里可以学习自己构建一个算法，这实际上有多难？ （我=数学菜鸟）。

我添加了 OpenGL 标签，因为这与它有某种关系。

Edit2：我在这里尝试了该算法：http://joshbeam.com/articles/triangle_rasterization/但它似乎有点破损，这里有一个带有64个三角形的圆圈：

但是如果放大，你可以看到错误：

说明：有 2 个像素与其他三角形颜色重叠，这是不应该发生的！ （或者透明度或异或等效果会产生不良渲染）。

看起来错误在较小的圆圈上更明显。如果我想对像素进行异或效果，这是不可接受的。

我可以做些什么来修复这些问题，以便它可以完美地填充它而没有重叠的像素或间隙？

Edit4：我注意到渲染非常小的圆圈不太好。我意识到这是因为坐标确实被转换为整数。如何将坐标视为浮点数并使其像在 OpenGL 中一样精确且完美地渲染圆？以下是小圆圈看起来有多糟糕的例子：

注意 OpenGL 渲染是多么完美！这就是我想要在不使用 OpenGL 的情况下实现的目标。 注意：我不仅仅想渲染完美的圆形，而是任何多边形形状。

Answer 1

总有半空间方法。

Answer 2

OpenGL 使用 GPU 来执行这项工作。这在硬件中被加速，称为光栅化。 据我所知，硬件实现是基于扫描线算法的。

Answer 3

这过去是通过创建轮廓然后填充水平线来完成的。有关更多详细信息，请参阅此链接 - http://joshbeam.com/articles/triangle_rasterization/

编辑：我认为这不会产生您想要的单独像素，每行上都应该有一个像素。

Answer 4

你的问题看起来很像共享同一条边的三角形时遇到的问题。共享一条边的三角形的作用是允许一个三角形征服空间，而另一个三角形必须将其留空。

在使用图形卡进行工作时，通常可以通过从左到右应用绘制顺序来获得此行为，同时还启用 z 缓冲区测试或测试像素是否已被绘制。因此，如果已经设置了具有完全相同 z 值的像素，则不允许更改像素。

在您的圆圈示例中，两个相邻圆段的线并不精确。您必须检查边缘的计算是否不同以及原因。

每当您绘制两个不同的形状并且看到类似的东西时，您可以修复您的模型（以便它们共享所有边缘顶点），进行 z 缓冲区测试或颜色测试。

您还可以通过使用具有更高分辨率的子缓冲区绘制边缘并对其进行下采样来最大程度地减少影响。由于这不会影响整个区域，因此与对整个场景进行下采样相比，它在空间和时间方面更具成本效益。