performance - 填充多边形 : Performance of Winding Rule vs Even Odd Rule

Question

对于复杂的多边形(即:自相交)，选择缠绕填充规则还是奇偶填充规则会影响多边形的填充方式。

但对于非相交多边形，缠绕或奇偶填充规则之间是否存在任何性能差异。我知道这将是特定于实现的，但哪种算法对于非复杂多边形更有效。

后续问题是这些算法中的每一个的复杂性(即 O(what?) )。我想知道是否值得去掉多边形中的一些点(主要是重复点或在同一条线上的点)以提高性能。

PS:如果重要的话，我正在使用 xlib

PPS:我可以确认问题与硬件无关，因为使用不同的显卡不会改变性能

Answer 1

如今，大多数 X 的实现都使用图形卡的 2D 硬件，因此两者之间的差异可以忽略不计。

由于这是一个性能问题，所以我的答案正确的可能性大约为 10%(对于性能，如果不进行测量，您有 90% 的可能性会出错)。如果你想确定，没有办法，只能写一个小的性能测试，你自己看看。

x11perf可能有帮助。

您可以在此处找到独立于硬件的多边形填充算法:http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

如果您确定多边形是凸的，还有第二个版本要快得多:http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

第二个版本忽略了填充规则(不适用于凸多边形)。关于算法的评论:http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipoly.h?rev=HEAD

该算法以这种方式工作:它计算轮廓，然后在边缘之间创建跨度对象(只是一个 x,y 坐标和一个宽度)。如果您使用 EvenOdd 规则，如果有交叉点，将创建更多跨度对象。如果没有(例如，当多边形是凸面时)，那么您将不会注意到运行时差异，因为填充规则相当于 miFillPolygon 主循环中的 bool 变量(即，两者的大部分代码是相同的)填写规则)。

尝试通过优化多边形的轮廓来提高性能在常见情况下不会给您带来多大好处，除非您知道您的多边形包含大量不必要的点(例如，您可以去掉一半的点)一般情况下的点)。优化具有 < 10 个点的多边形可能会比它实现的成本更高。

但再次强调:这都是基于直觉或旧文章的知识。如果你想知道你的 gfx 卡驱动程序中的错误是否会影响结果，你必须亲自动手并编写一个测试来测量每种情况需要多长时间。由于外部因素，无法通过简单地查看任何复杂算法的运行时间来判断它的运行时间:内存分配例程的速度、可用内存量(交换何时开始)、可以使用的 CPU 内核数、多少其他进程将与您争夺 CPU、屏幕上最终多边形的裁剪、实现细节和优化、错误等。