c++ - 2D ポリゴンのラスタライズ

Question

ポイントのリストとして表される閉じた 2D ポリゴンからバイナリビットマップを作成する必要があります。それを行うための効率的で十分に単純なアルゴリズム、またはもっと良いのは C++ コードを教えてください。

どうもありがとう！

PS: プロジェクトに依存関係を追加することは避けたいと思います。ただし、オープンソースのライブラリを提案していただければ、いつでもコードを参照できるので、それも役立ちます。

score 13 · Accepted Answer

あなたが望む魔法のグーグルフレーズは、「非ゼロワインディングルール」または「奇数ポリゴン塗りつぶし」のいずれかです。

次のウィキペディアのエントリを参照してください。

どちらも実装が非常に簡単で、ほとんどの目的に対して十分に高速です。ある程度の工夫をすれば、アンチエイリアスを適用することもできます。

score 6 · Accepted Answer

Pygame でポリゴン塗りつぶしルーチンを確認できます。関数を見てくださいdraw_fillpoly。

アルゴリズムは非常に単純です。各セグメントが Y 軸に沿って交差するすべての位置を見つけます。これらの交点は並べ替えられ、次に交点の各ペアを水平方向に塗りつぶします。

これは複雑で交差する形状を処理しますが、明らかに、大量のセグメントでこのアルゴリズムを押しつぶす可能性があります。

score 3 · Accepted Answer

ポリゴンを三角測量する
各三角形をラスター化します (GPU を使用している場合は、代わりにそれを行うことができます。これは GPU の原始的な操作です)。
- 三角形に x 軸に平行な線分がない場合は、x 軸に平行な線で 2 つの三角形に分割し、中央値 y でその点を通過します。
- 残りのタスクは、x 軸に平行なセグメントを持つ三角形を描くことです。このような三角形には、左側のセグメントと右側のセグメントがあります
- 三角形の走査線を繰り返します (min-y から max-y へ)。各 y について、そのスキャンラインの左右のセグメントのポイントを計算します。これらの 2 つのポイント (単純な memset) のスキャンラインセグメントを埋めます。

複雑さは O(ピクセル単位の面積)

4 に答える 4