ペインターのアルゴリズムを実装するときにポリゴンを注文する正しい方法は何ですか？

私はグラフappを書いており、visibility problemを処理するには、z-bufferまたはpainters algorithmのいずれかを使用することをお勧めしています。ペインターのアルゴリズムを実装するときにポリゴンを注文する正しい方法は何ですか？

私はHTML5のキャンバスにこれを書いていますので、zバッファを使用するのはひどく高価です。たとえば、500×500のキャンバスで、10個のポリゴンをループする必要があります。これは、CPUで1フレームあたり2,500,000回の繰り返しが行われることになります。私はそれが大きな数字であるかどうかわからないが、それはこのアプリのためにそれを行う間違った方法のように思える。

ペインターのアルゴリズムが適切であるようです。基本的な手順は次のとおりです。

1. Sort polygons based on their "z". 
2. Paint all polygons, but paint the ones farthest away first.

しかし、私はそれらのzを見つける方法について混乱しています。

私がちょうど最大のz（画面から最も遠い）を見つけたら、もっと遠くにあると考えられます。それで赤が最初にペイントされ、次に赤がオレンジの前にあっても、赤がオレンジで塗り潰されます。

これらのポリゴンをソートする正しい方法は何ですか？または、より一般的には、ペインタのアルゴリズムを実装するときに、ポリゴンの順序をどのように決定するのですか？

編集：thisは（各ピクセルを通過すると、ランダムにこの5歳のi7の上に色〜10FPSを割り当てます）私自身のzバッファを転がすの理由イム恐れています。

出典

2017-07-21 user1873073

複雑さは同じです。 3つの三角形をソートし、2.5Mの2Dピクセル操作を使用して盲目的に描画するか、1つのピクセルにつき1つのz演算を追加するzバッファを使用します。 CGアルゴリズムが、ある三角形が他の三角形で完全に隠されていると判断した場合にのみ、メリットが得られます。 –

3つの三角形は、周期的にお互いをカバーすることができます。つまり、一般的なソートアルゴリズムは存在しません。代わりに、問題は通常、オーバーラップしている三角形を、オーバーラップしたエッジに沿って切断して、新しい三角形/ポリゴンを形成することによって解決されます。

問題の2つのポリゴンは、他のポリゴンの平面方程式から頂点の符号付き距離でソートされたOTOHにすることができます。

出典

2017-07-21 18:37:31

すべてのポリゴンを大きなリストに入れ、並べ替えアルゴリズムを実行したか、最初にxとyが重なっているかどうかに基づいてポリゴンをグループ化する必要がありますか？ – user1873073

ソートを高速化するために、バウンディングボックス（xyzまたは非アラインメントに揃えられた）または球によるグループ化が一般的に使用されます。 –

Z-ソーティングは、通常遅いです。Z-バッファリングです。より多くのポリゴンを持つ方がZバッファを使用する方が良いでしょう。反復についてのあなたの前提は間違っています。 Zバッファリングはポリゴンごとに繰り返されるのではなく、ピクセル単位で反復されます。

あなたが持っているポリゴンの数は関係ありません。重要なのは、ピクセルでレンダリングされた領域です（オーバーラップ領域は、それが属する各ポリゴンにつき1回、複数回に分けられます）。だから、500x500のスクリーンと10のポリゴンには10*500*500の繰り返しがあると期待できません。

あなたが実装するために苦労を取得します私はHTML5のキャンバスでコーディングしないが、あなたは直接ピクセルアクセスを得なければバッファをバックシャドウと自分で自分のポリゴンをラスタライズ（またはGLSLでフラグメントシェーダのようなそれにアセスを持っています） zバッファリングもし単なる単純な状態であっても。私はそれがステンシルかアルファ・マスキングでもできると思うが、決してそれをしなかった。

のzソートは、通常、これらの場合に使用されます。