3

問題の仕様：頂点座標（i、j）、（i + 1、j）、（i、j + 1）、（i + 1、j + 1）[i = 0、...、m-1; j = 0、...、n-1]および頂点座標（x_1、y_1）、...、（x_n、y_n）を持つポリゴンP。ここで、Pとオーバーラップするすべてのピクセルのパーセンテージを効率的に計算したいと思います。Pは非凸、または自己交差である可能性があります。

基本的に、これはスキャンラインラスタライズアルゴリズムの「ソフト」な一般化であり、ピクセルの中心がポリゴンの内側/外側にあるかどうかを効率的にチェックします。

私は次のアプローチを考えることができます：

（1）画像をアップサンプリングし（たとえば、10 * 10倍）、ポリゴン内にあるサブピクセルの中心の数を数え、100で割ります。問題：時間効率、メモリ効率、精度。

（2）少し大きく、（0.5,0.5）変換されたグリッドでスキャンラインアルゴリズムを使用して、完全に内側/外側にあるピクセルを計算し、「境界線」ピクセルのリストを作成し、エッジに沿って反時計回りに歩きます。途中のすべてのピクセルとの交差領域を計算します。問題：微妙なコーディングが必要で、バグを簡単に導入できます。

私の質問：誰かがすでにこの問題に遭遇しました、そしてあなたは3番目の優れたアプローチを知っていますか？そうでない場合は、（1）または（2）でより良い経験をしましたか？この問題はアンチエイリアシングのコンテキストで発生する可能性があると思いますか？

4

2 に答える 2

3

正確な幾何学的分析を行うことはそれほど難しくないかもしれません。

最初にポリゴンで部分的に覆われているピクセルを処理します。レイトレーシングの手法を使用して、ポリゴンのエッジと交差するすべてのピクセルをすばやく見つけることができます。次に、コーエン-サザランドアルゴリズムを使用して、エッジとピクセルの間の交点を効率的に見つけることができます。したがって、そのピクセルのカバレッジ領域を計算できます。

隣接するピクセルがセグメントの交点を共有するため、コーエン-サザランドに関連する2つのクリッピング操作のいずれかを回避できることに注意してください。たとえば、2つの隣接するピクセルがあり、それらがポイント、、、AおよびでセグメントとB交差する場合、とは同じになります。クリッピング時にセグメントをルーチンに渡すと、作業の繰り返しを避けることができます。p->qa1a2b1b2a2b1a2->qB

ポリゴンの頂点を含むピクセルを特別に処理する必要がありますが、それほど難しいことではありません。コーエン-サザランドもここで役立ちます。

自己交差するポリゴンは、2つ以上のエッジと交差するピクセルを処理するためのいくつかの特殊なケースもスローします。これらをすべての場合に正確に処理するのは難しいかもしれないことは容易に想像できるので、ここでアップサンプリングのアプローチを実行したいと思います。

これらのエッジピクセルが特定されたら、標準のスキャンライン処理を実行して、ポリゴンの内部ピクセルを塗りつぶすことができます。

編集：実際、私がそれについてもっと考えると、コーエン-サザランドのステップを完全にスキップすることができます。リンクされた紙のアルゴリズムは、セグメントとピクセルグリッド間の交点を返すように簡単に拡張できます。セグメントは、指定されたピクセルをに残しmin( tMaxX, tMaxY )ます。次のピクセルのエントリポイントとして再利用する最後の出口ポイントを追跡します。

于 2012-12-12T11:45:38.987 に答える
0

私はするだろう

1a) ピクセルが部分的に重なっている場合のアップサンプル:

ただし、画像全体ではなく、チェックする現在のピクセルのみ、または現在のスキャンラインのすべてのピクセルが役立つ場合があります。

メモリ引数がありません。

速度？16x16 までは、速度が問題になるとは思いません。

于 2012-12-10T21:22:21.880 に答える