opengl - 頂点の巻き順

Question

巻き順とは何か、裏面カリングにどのように使われるかを理解しています。

しかし、Blender のような 3D モデリング プログラムがどのようにして三角形の任意のグループを取得し、それらをすべて正しく巻くことができるのか、正確にはわかりません。

私は答えをグーグルで調べてみましたが、これが私が見つけた最高のものでした:

http://www.gamedev.net/topic/550481-vertex-winding-order-counter-clockwise-oder-vertex---algorithm/

基本的に、各三角形について、その中心 (正確には重心) を見つけ、その三角形から法線ベクトルを計算します。これにより光線が得られます。この光線を取り、他のすべての三角形との交差に対してテストします。偶数の場合、巻線は正しく、奇数の場合、巻線は正しくありません (これは、法線ベクトルを正確に生成した方法に依存すると思いますが、何らかの方法で奇数/偶数戦略を使用します)。とにかく、それはこのプロセス全体が一般的に O(n^2) であることを意味します。1000 個の三角形がある場合、三角形ごとに、他の 999 個の三角形の交差に対してテストする必要があります。頂点を正しく巻くためのあまり明白でない方法はありますか?それはより効率的ですか?

Answer 1

あなたはそれを間違って理解しました。それはしません

test it against intersection against every other triangle.

まず、三角形の表面の法線ベクトルのみに基づいて、三角形の向きを変える (ワインドアップする) ことができます。次に、残りのオプションは2つだけです-モデル全体が良いか、反転しています;)

したがって、実際には 1 つの三角形のみをチェックし、最後のチェックの結果に基づいて残りを巻き上げる必要があります。これにより、基本的に O(n) が得られます。

編集:ああ、このアプローチがいつ失敗するかはわかっていると思います。たとえば、Google Sketchup はうまく機能せず、顔の向きを自分で調整する必要がある場合があることを思い出しました。ただし、(ランダムな三角形の場合) ランダム光線の数を増やすと、すべてを正しくマークする可能性が実際に高くなります。

EDIT2：そして、5万人以上の男が私に反対票を投じる前に-モデルが完全に混乱している場合（すべての三角形がランダムな順序になっている場合）、それらすべてを他の凸面に対してチェックする以外に、それらすべてを適切に方向付ける方法はありませんモデルは例外です。