c# - 2D タイル ベースの形状を単純化されたポリゴンに変換する

Question

上の画像に見られるように、タイルの 2D 配列があり、それぞれがゲーム ワールド内に 4 つのポイントを持っています。個々のタイルから構築されたこれらの形状を単純化された (不要な頂点はなく、アウトラインを形成するために必要な頂点のみ) ポリゴン形状に変換する方法を探しています。

私はここや他の場所を見回してきましたが、ほとんど運がありませんでした. しかし、検索する正しい用語を知らないかもしれません。どんな助けでも大歓迎です。

追加情報: これを使用して動的照明を最適化しようとしています。誰かがタイルベースの世界で高速で動的な影を実現するための別のアプローチを持っている場合、それも質問に答えます.

Answer 1

次のアルゴリズムを提案します：

1. すべてのエッジ位置を 2D 配列に格納します (エッジ位置はエッジの中心です)。
2. この配列で重複するエッジをカウントしています (1 は重複なし、2 は別のエッジと交差しています。他の値は不可能です)。
3. 重複カウント 1 (重複なし) で配列から最初のマークされていないエッジを選択し、最初のエッジに到達するまで特定の方向 (たとえば時計回り) に単純な再帰塗りつぶしアルゴリズムを適用します。このすべてのエッジが 1 つの簡略化されたポリゴンを形成します。マークされていないエッジが確立されていない場合は、GOTO 5.
4. ステップ 3 のすべてのエッジを使用済みとしてマークします。手順 3 に進みます。
5. 終わり。

アルゴリズムをより直感的に表現するために、以下の画像を投稿しました。

Answer 2

単純なアプローチは、単純にすべてのタイルをステップ実行し、トランジション エッジをポリゴンにマークすることですが、一般的なエッジ検出ルーチンを再利用してパフォーマンスを向上させることができます。

その後、おそらくこれらのポリゴンをテッセレーションして三角形のコレクションに変換することに興味があるでしょう (後のシャドウ/ライティング/交差の計算をより簡単にします)。この場合の唯一の問題は、凹面になってしまう場合です。多角形ですが、適切なテッセレータを使用すると、凸多角形に分割できます。XNA にはテッセレーション用に組み込まれたものはないと思いますので、それを行うにはユーティリティ ライブラリを見つける必要があるかもしれません。