Direct3d で凹型ポリゴンを描画する効率的かつ簡単な方法はありますか?

StackOverflow https://stackoverflow.com/questions/91202

  •  01-07-2019
  •  | 
  •  

質問

C#とdirectxを使用してポリゴンを描画しようとしています

ファイルから取得できるのは順序付けられたポイントのリストだけであり、3D 世界で平面ポリゴンを描画する必要があります。

ポイントをロードし、trianglefan とdrawuserprimitives を使用して凸形状を描画できます。

これは、ポリゴンが非常に凹んでいる場合 (実際にはそうなっている可能性があります)、明らかに不正確な結果をもたらします。

この問題に取り組んでいるのが私だけであるとは想像できません (ただし、私は gfx/directx の初心者です。私の経歴は gui\windows アプリケーション開発です)。

誰かが私を助けることができる簡単に従うことができるリソース/チュートリアル/アルゴリズムを教えてくれませんか?

役に立ちましたか？

解決

Direct3D は三角形しか描画できません (線や点も描画できますが、それは重要ではありません)。したがって、三角形よりも複雑な形状を描画したい場合は、その形状と等しい、接触する三角形を多数描画する必要があります。

あなたの場合、それは凹型多角形の三角形分割の問題です。頂点が多数ある場合は、それらをそのまま保持できます。「インデックス バッファー」を計算するだけで済みます (最も単純なケースでは、三角形ごとに 3 つのインデックスがあり、三角形がどの頂点を使用するかを示します)。次に、頂点/インデックス バッファーに入れるか、DrawUserPrimitives を使用して、それを描画します。

単純な (凸型または凹型だが、自己交差や穴がない) ポリゴンを三角形化するためのいくつかのアルゴリズムは、次のとおりです。 VTerrainサイト.

私は過去に Ratcliff のコードを使用したことがあります。非常にシンプルでうまく機能します。VTerrain にはデッドリンクがあります。コードは見つかります ここ. 。これは C++ ですが、C# への移植は簡単です。

あ、三角扇風機は使わないでください。これらは用途が非常に限られており、非効率的であり、間もなく廃止されます（例:Direct3D 10 ではサポートされなくなりました)。トライアングルリストを使用するだけです。

他のヒント

三角測量は明白な答えですが、しっかりした三角測量器を書くのは難しいです。2 か月を無駄にする時間がない限り、試してはいけません。

役立つコードがいくつかあります。

GPC ライブラリ。とても使いやすいですが、ライセンスが気に入らないかもしれません:

http://www.cs.man.ac.uk/~toby/alan/software/gpc.html

三角形もあります:

http://www.cs.cmu.edu/~quake/triangle.html

そして拳：

http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html

もう 1 つの (そして私が好む) オプションは、GLU テッセレーターを使用することです。GLU ライブラリは DirectX プログラムから問題なくロードして使用できます。これを使用するために OpenGL コンテキストは必要なく、すべての Windows マシンにプリインストールされています。ソースが必要な場合は、SGI リファレンス実装から三角測量コードを取り出すことができます。一度やりましたが、ほんの数時間しかかかりませんでした。

三角測量についてはここまでです。別の方法もあります。ステンシルのトリックを使用できます。

一般的なアルゴリズムは次のようになります。

  1. カラーと深度の書き込みを無効にします。ステンシル書き込みを有効にし、現在のステンシル値を反転するようにステンシル バッファーを設定します。ステンシルは 1 ビットで十分です。ああ、ステンシル バッファーもクリアする必要があります。

  2. 画面上のランダムな点を選択します。どれでも構いません。この点をアンカーと呼びます。

  3. ポリゴンの各エッジに対して、エッジとアンカーを構築する 2 つの頂点から三角形を構築します。その三角形を描きます。

  4. これらの三角形をすべて描画したら、ステンシル書き込みをオフにし、ステンシル テストとカラー書き込みをオンにして、選択した色で全画面クワッドを描画します。これにより、凸多角形内のピクセルのみが塗りつぶされます。

アンカーを多角形の中央に配置し、多角形の境界ボックスと同じ大きさの長方形を描画することをお勧めします。これにより、フィルレートが少し節約されます。

ところで、ステンシル技術は自己交差するポリゴンにも機能します。

それが役立つことを願っています、nils

ステンシル バッファーを使用できるのであれば、それは難しくないはずです。一般的なアルゴリズムは次のとおりです。

Clear the stencil buffer to 1.
Pick an arbitrary vertex v0, probably somewhere near the polygon to reduce floating-point errors.
For each vertex v[i] of the polygon in clockwise order:
    let s be the segment v[i]->v[i+1] (where i+1 will wrap to 0 when the last vertex is reached)
    if v0 is to the "right" of s:
        draw a triangle defined by s, v[i], v[i+1] that adds 1 to the stencil buffer
    else
        draw a triangle defined by s, v[i], v[i+1] that subtracts 1 from the stencil buffer
end for
fill the screen with the desired color/texture, testing for stencil buffer values >= 2.

「s の右側」とは、v[i] の上に立って v[i+1] を向いている人の視点からという意味です。これは外積を使用してテストできます。

クロス(v0 - v[i], v[i+1] - v[i]) > 0

プロジェクトのためにこれをやらなければならなかったのです。私が見つけた最も単純なアルゴリズムは「Ear Clipping」と呼ばれるものです。それに関する素晴らしい論文がここにあります。 TriangulationByEarClipping.pdf

約 250 行の C++ コードと、そのブルート フォース バージョンを実装するのに 4 時間かかりました。他のアルゴリズムのパフォーマンスは優れていますが、これは実装も理解も簡単でした。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top