填充多邊形：執行纏繞規則與偶數奇數規則

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的主循環中相當於一個布爾變量（即大部分代碼對於兩者都是相同的填充規則）。

試圖通過優化多邊形輪廓來提高性能在常見情況下不會給您帶來太多的收益，除非您知道您的多邊形包含非常多的不必要的點（例如，您可以擺脫一半數量普通情況下的點數）。使用<優化多邊形可能會比實現更多的成本。

但是，這一切都是基於直覺或對舊文章的瞭解。如果你想知道你的gfx卡驅動程序中的錯誤是否與結果相混淆，你必須弄清楚你的手並編寫一個測試每個案例需要多長時間的測試。由於外部因素的緣故，無法僅通過查看它來告訴運行時任何複雜算法：內存分配例程的速度，可用內存量（交換開始時間），可以使用的CPU內核數量，多少其他進程將與CPU對抗，裁剪屏幕上的最終多邊形，實現細節和優化，錯誤等。