logo标签列表

将二维多边形转化为栅格图像

c++algorithmgraphicsgeometryrasterizing
11
我需要从一个由点列表表示的封闭2D多边形创建二进制位图。你能否指导我使用高效且足够简单的算法来实现，或者最好提供一些C++代码？
非常感谢！
注：我想避免向我的项目添加依赖项。但是，如果您建议一个开源库，我可以查看代码，因此也可能很有用。
5个回答
14
你需要的是“非零环绕规则”或“奇偶填充算法”。请参阅以下维基百科条目：这两种算法都很容易实现，对于大多数目的都足够快速。通过一些巧妙的处理，它们也可以被抗锯齿化。请注意保留原有html标记。
1
@plinth：对于简单的多边形来说，这不是有些过度了吗？ - yairchu
5
什么是简单多边形？@static_rtti并未指定多边形的点数或是否始终为凸多边形，因此一般解决方案才是正确答案。NZW和EO非常简单，适合于扫描线解决方案等等。 - plinth
1
@plinth：谢谢，这正是我在寻找的！当你没有那个魔法短语时，谷歌搜索可能会很棘手 :-) - static_rtti
3
@plinth：简单多边形是指其线段不相交的多边形。请参阅http://en.wikipedia.org/wiki/Simple_polygon。 - yairchu
该答案包含描述一种确定每个样本是否在多边形内的方法的链接。虽然可以使用这种方式实现，但它效率极低，在实践中从未这样做（除了在GPU上光栅化一个简单的三角形，即使是这样也需要进行拉伸...）。实际的多边形光栅化算法几乎普遍涉及对顶点进行排序、跟随边缘并填充内部跨度。这个答案中没有提到其中任何一点。 - Yakov Galka
6
你可以查看Pygame中的多边形填充例程。请参考draw_fillpoly函数。
该算法非常简单。它找到每个线段沿Y轴相交的所有位置。这些交点被排序，然后水平地填充每对交点。
这将处理复杂和相交的形状，但显然，您可以通过大量线段来压垮此算法。
不太相关，但是顺便说一下，Pete 你制作 Pygame 真的很棒 :) - yairchu
5

为了实现"奇偶规则"的强大应用

请参考Darel Rex Finley's Efficient Polygon Fill或者Blender的版本。

这是一种支持自相交线段的奇偶填充方法，无需复杂的代码来检测这种情况，并且不依赖于绕组（多边形可以反转并产生相同的结果）。

更新，我优化了Darel Rex方法的版本，避免了每个y像素循环遍历所有坐标。

独立实现：

虽然加速可能是指数级的，但从快速测试中可以看出，在2540x1600区域内手绘涂鸦时，速度提高了约7.5倍（去除round调用后为11倍），具体情况因人而异。

3
  • 将你的多边形三角化
  • 对每个三角形进行光栅化（如果你使用GPU，则它可以代替你完成此操作，这是GPU的基本操作）
    • 如果三角形没有一条与x轴平行的线段，则使用一条与中位数y点平行且穿过该点的线将其分为两个三角形
    • 现在剩余的任务是绘制一个具有与x轴平行的线段的三角形。这样的三角形有左侧线段和右侧线段
    • 迭代三角形的扫描线（从最小y到最大y）。对于每个y，在该扫描线中计算左侧和右侧线段的点。用这两个点填充扫描线段（一个简单的memset）。

复杂度为O(像素面积)

1
你会如何进行三角形的光栅化呢？每次遍历整张图像逐个绘制吗？那不是很慢吗？ - static_rtti
@static_rtti：你说的遍历整个图像是什么意思？ - yairchu
@static_rtti：我添加了如何光栅化三角形的说明。 - yairchu
这里的关键点是“计算左右段”。对于每个扫描线分别进行计算速度太慢了；更好的方法是计算增量，并将其应用于起始值。 - Pavel Minaev
1
我认为这个答案过于简单地概括了三角测量多边形所涉及的复杂性。对于简单的多边形来说并不那么困难。但是对于自相交的多边形而言，这就比较麻烦了。请参考http://www.angusj.com/delphi/clipper.php。 - ideasman42
2
除了其他人提到的扫描线算法之外，一篇名为Wavelet Rasterization by J. Manson and S. Schaefer的论文描述了一种截然不同的方法。
粗略地说，该算法将每条边喷洒到小波域中，然后进行逆小波变换以重构图像。
优点是该算法能够计算出精确的覆盖范围（即反走样），这在扫描线算法中极其难实现。它还容忍断裂的多边形，即具有不连续轮廓的多边形。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接