複雑な多角形 (つまり、自己交差) の場合、ワインディング規則または偶奇規則のどちらを選択するかによって、多角形の塗りつぶし方法が異なります。
しかし、交差していないポリゴンの場合、Winding と Even Odd の塗りつぶしルールの間にパフォーマンスの違いがあります。実装固有であることは理解していますが、複雑でないポリゴンに対してどのアルゴリズムがより効率的であるかを理解しています。
フォローアップの質問は、これらの各アルゴリズムの複雑さ (つまり、O(what?)) です。パフォーマンスを向上させるために、ポリゴン内のいくつかのポイント (主に重複または同じ線上にあるポイント) を取り除く価値があるかどうかを知りたいです。
PS：それが問題であれば、私はxlibを使用しています
PPS: 別のグラフィックス カードを使用してもパフォーマンスは変わらないため、問題がハードウェアに関連していないことを確認できます
現在、X のほとんどの実装はグラフィック カードの 2D ハードウェアを使用しているため、この 2 つの違いはおそらく無視できる程度です。
これはパフォーマンスに関する質問なので、私の答えが正しい可能性は約 10% です (パフォーマンスに関しては、測定しないと間違っている可能性が 90% あります)。確認したい場合は、小さなパフォーマンス テストを作成して自分で確認するしかありません。
x11perfが役立つかもしれません。
ハードウェアに依存しないポリゴン塗りつぶしのアルゴリズムは、http: //cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolygen.c ?rev=HEAD にあります。
ポリゴンが凸面であることが確実な場合は、はるかに高速な 2 番目のバージョンがあります: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipolycon.c?rev=HEAD
2 番目のバージョンは、塗りつぶし規則を無視します (これは凸多角形には適用されません)。アルゴリズムに関するコメント: http://cvsweb.xfree86.org/cvsweb/xc/programs/Xserver/mi/mipoly.h?rev=HEAD
アルゴリズムは次のように機能します。アウトラインを計算し、エッジ間にスパン オブジェクト (軸、y 座標と幅のみ) を作成します。EvenOdd ルールを使用すると、交差がある場合にさらにスパン オブジェクトが作成されます。何もない場合 (たとえば、多角形が凸状の場合)、実行時の違いはわかりません。これは、塗りつぶしルールが miFillPolygon のメイン ループのブール変数になるためです (つまり、ほとんどのコードは両方で同じです)。塗りつぶしルール)。
ポリゴンのアウトラインを最適化してパフォーマンスを改善しようとしても、ポリゴンに非常に多くの不要なポイントが含まれていることがわかっている場合を除いて、一般的なケースではあまり効果がありません (たとえば、ポリゴン内のポイント数の半分を取り除くことができます)。よくあるケース）。10 個未満のポイントでポリゴンを最適化すると、おそらくそれ以上のコストがかかります。
しかし、繰り返しになりますが、これはすべて直感や古い記事の知識に基づいています. gfx カード ドライバのバグが結果を台無しにしているかどうかを知りたい場合は、手を汚して、各ケースにかかる時間を測定するテストを作成する必要があります。外部要因のため、複雑なアルゴリズムのランタイムを単純に調べる方法はありません: メモリ割り当てルーチンの速度、空きメモリの量 (いつスワッピングを開始するか)、使用できる CPU コアの数、使用できる CPU コアの数他のプロセスは、CPU、画面上の最終的なポリゴンのクリッピング、実装の詳細と最適化、バグなどのためにあなたと戦うでしょう.