c++ - 栅格化 2D 多边形

Question

我需要从表示为点列表的封闭二维多边形创建二进制位图。您能否指出有效且足够简单的算法来做到这一点，或者更好的是一些 C++ 代码？

非常感谢！

PS：我想避免向我的项目添加依赖项。但是，如果您建议一个开源库，我可以随时查看代码，因此它也很有用。

Answer 1

您想要的神奇谷歌短语是“非零缠绕规则”或“偶数多边形填充”。

请参阅维基百科条目：

• 非零缠绕规则
• 偶数多边形填充

两者都非常容易实现，并且对于大多数目的来说足够快。有了一些聪明，它们也可以被制作成抗锯齿。

Answer 2

您可以查看 Pygame 中的多边形填充例程。看draw_fillpoly功能。

该算法非常简单。它找到每个线段沿 Y 轴相交的所有位置。这些交叉点被排序，然后水平填充每对交叉点。

这将处理复杂和相交的形状，但显然你可以用大量的段来粉碎这个算法。

Answer 3

对于“奇偶规则”的强大实施

请参阅Darel Rex Finley 的 Efficient Polygon Fill或Blender 的版本。

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

---

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

独立实现：

• C99。
• Rust（带有测试）。

虽然加速可能是指数级的，但从快速测试来看，round在 2540x1600 区域 YMMV 上使用任意手绘涂鸦，它的速度提高了约 7.5 倍（移除呼叫时为 11 倍）。

Answer 4

• 对多边形进行三角剖分
• 光栅化每个三角形（如果您使用的是 GPU，那么它可以为您完成，这是 GPU 的原始操作）
  • 如果三角形没有平行于 x 轴的线段，则将其分成两个三角形，其中一条线平行于 x 轴并通过它的中位数为 y 的点
  • 现在剩下的任务是绘制一个三角形，该三角形的线段平行于 x 轴。这样的三角形有一个左侧线段和一个右侧线段
  • 迭代三角形的扫描线（min-y 到 max-y）。对于每个 y 计算该扫描线中左右线段的点。填充扫描线段这两个点（一个简单的 memset）。

复杂度为 O（以像素为单位的面积）