对于复杂的多边形（即：自相交），绕组或奇偶填充规则之间的选择会影响多边形的填充方式。
但是对于不相交的多边形，绕组或奇偶填充规则之间是否存在任何性能差异。我知道这将是特定于实现的，但哪种算法对非复杂多边形更有效。
一个后续问题是这些算法中的每一个的复杂性是多少（即 O(what?) ）。我想知道是否值得去掉多边形中的一些点（主要是重复的或在同一条线上的点）以提高性能。
PS：如果这很重要，我正在使用 xlib
PPS：我可以确认问题与硬件无关，因为使用不同的显卡不会改变性能
hhafez
问问题
6074 次
1 回答
5
今天，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
The algorithm works this way: It calculates the outline, then creates span objects (which are just a x,y coordinate and a width) between the edges. If you use the EvenOdd rule, more span objects will be created if there are intersections. If there are none (for example, when the polygon is convex), then you will not notice a runtime difference because the filling rule amounts to a boolean variable in the main loop of the miFillPolygon (i.e. most of the code is the same for both fill rules).
Trying to improve performance by optimizing the outline of the polygon will not buy you much in the common case except if you know that your polygons contain a very high number of unnecessary points (say, you can get rid of half the number of points in the common case). Optimizing a polygon with < 10 points will probably cost more than it achieves.
But again: This are all based on gut feeling or the knowledge of an old article. If you want to know if bugs in your gfx card driver mess with the result, you have to get your hands dirty and write a test which measures how long each case takes. There is no way to tell the runtime of any complex algorithm by simply looking at it because of external factors: Speed of the memory allocation routines, amount of free memory (when does swapping start), number of CPU cores you can use, how many other processes will fight you for the CPU, clipping of the final polygon on the screen, implementation details and optimizations, bugs, etc.
于 2009-01-28T08:17:24.703 回答