Filling a Polygon: Performance of Winding Rule vs Even Odd Rule

Question

For a complex polygon (ie: self intersecting) the choice between the Winding or the Even-Odd filling rules makes a difference in the way the polygon is filled.

But for non intersecting polygons is there any performance difference between the Winding or the Even Odd filling rules. I understand it would be implentation specific but which of the algorithms is more effecient for non complex polygons.

A follow up question what is the complexity (ie O(what?) )of each of these algorithms. I want to know whether it is worth getting rid of some points in the polygon (mainly duplicates or ones that are on the same line) to improve performance.

PS: If it matters at all, I am using xlib

PPS: I can confirm the problem is not hardware related as using a different graphics card doesn't change the performance

Answer 1

Today, most implementations of X use the 2D hardware of your graphics card so the difference between the two is probably negligible.

Since this is a performance question, chances of my answer being correct is about 10%, though (with performance, you have a 90% chance to be wrong without measuring). If you want to be sure, there is no way but to write a small performance test and see for yourself.

x11perf might help.

You can find the algorithm for the hardware independent polygon fill here: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c?rev=HEAD

There is a second version which is much faster if you are sure your polygon is convex: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD

The second version ignores the fill rule (which doesn't apply to convex polygons). Comments about the algorithm: 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.