多角形を塗りつぶす:ワインディングルールと偶数奇数ルールのパフォーマンス

Question

複雑な多角形の場合 (例:自己交差)、曲がり塗りルールと偶数-奇数塗りつぶしルールの選択により、ポリゴンの塗りつぶし方法が異なります。

しかし、交差しないポリゴンの場合、曲がり塗りつぶしルールと偶数奇数塗りつぶしルールの間にパフォーマンスの違いはありますか。実装固有のものであることは理解していますが、非複雑なポリゴンに対してはどのアルゴリズムがより効率的ですか。

フォローアップの質問は、これらの各アルゴリズムの複雑さ (すなわち、 O(what?) ) は何ですか。パフォーマンスを向上させるために、ポリゴン内のいくつかのポイント (主に重複または同じ線上にあるポイント) を削除する価値があるかどうかを知りたいです。

追伸：それが少しでも重要であれば、私はxlibを使用しています

PPS:別のグラフィックス カードを使用してもパフォーマンスは変わらないため、問題はハードウェアに関連していないことが確認できました。

Answer 1

現在、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

アルゴリズムは次のように動作します。アウトラインを計算し、エッジ間にスパン オブジェクト (X、Y 座標と幅だけ) を作成します。EvenOdd ルールを使用すると、交差がある場合にさらに多くのスパン オブジェクトが作成されます。何もない場合 (たとえば、ポリゴンが凸状の場合)、塗りつぶしルールは miFillPolygon のメイン ループ内のブール変数になるため、実行時の違いはわかりません (つまり、コードの大部分は両方の塗りつぶしルールで同じです)。

ポリゴンのアウトラインを最適化してパフォーマンスを向上させようとしても、ポリゴンに非常に多くの不要なポイントが含まれていることがわかっている場合 (たとえば、よくあるケース）。ポイントが 10 未満のポリゴンを最適化すると、おそらく、達成できる以上のコストがかかります。

しかし、もう一度:これらはすべて直感または古い記事の知識に基づいています。gfx カード ドライバーのバグによって結果が乱れているかどうかを知りたい場合は、手を汚して、各ケースにかかる時間を測定するテストを作成する必要があります。外部要因のため、単純に複雑なアルゴリズムの実行時間を知ることはできません。メモリ割り当てルーチンの速度、空きメモリの量 (スワップがいつ開始されるか)、使用できる CPU コアの数、CPU をめぐって競合する他のプロセスの数、画面上の最終ポリゴンのクリッピング、実装の詳細と最適化、バグなど。