6

2次元の（必ずしも凸ではない）ポリゴンの方向付けされたバウンディングボックス（obb）ツリーを構築するコードを書いています。

これまでのところ、凸包を見つけ、船体に回転キャリパー法を使用することで、ポリゴンの面積が最小のobbを見つけることができました。

下の写真はその一例です。赤い線と赤い点が付いた黄色で塗りつぶされたポリゴンは、元のポリゴンを表しています。凸包は青色で黒い線で示され、obbは紫色の線で示されています。

（編集）要求に応じて：インタラクティブバージョン-Chromeでのみテスト済み

ここで、コードを拡張して、OBBだけでなく、OBBツリーを構築したいと思います。これは、ポリゴンをカットし、ポリゴンの半分ごとに新しいOBBを計算する必要があることを意味します。

これを行うための推奨される方法は、OBBを半分にカットしてポリゴンをカットすることのようです。しかし、いずれかの軸の中央でobbをカットすると、ポリゴン上に新しい頂点を作成する必要があるように見えます（そうでない場合、そのパーティションの凸包を見つけるにはどうすればよいですか？）。

  1. このような頂点の追加を回避する方法はありますか？
  2. そうでない場合、（実装の難しさに関して）それを行う最も簡単な方法は何ですか？最もランタイム効率の良い方法は何ですか？
4

2 に答える 2

4

これは、OBBツリーを作成する凹多角形の例です。

これを新しい凹多角形のセットに分割するには、境界ボックスを中央で切り取り、必要に応じて新しい「交差」頂点を追加することで、現在の多角形を簡単に切り取ることができます。

：

これは、O（頂点）時間で実行できます。これは、すべてのエッジを単純に反復処理し、エッジが赤い分割線と交差する場合は交差頂点を追加できるためです。

次に、ポリゴンをこれらの交差する頂点に関して分割して、より小さな（ただしおそらく凹面の）ポリゴンの新しいセットを取得できます。そのようなポリゴンは少なくとも2つ（赤い線の片側に1つ）ありますが、それ以上になることもあります。この次の図では、新しいポリゴンが強調のために色付けされています。

これらの小さなポリゴンの方向付けされたバウンディングボックスを再帰的に計算すると、目的の結果が得られます。たとえば、再帰深度2のボックスは次のとおりです。

ここに画像の説明を入力してください

うまくいけば、これは私と同じように苦労している誰かを助けるのに十分明確です！

于 2012-05-29T05:08:03.530 に答える
3

これがあなたがそれ以上の文脈なしで必要なものであるかどうかは本当にわかりませんが、ここに行きます...

凹多角形を凸多角形のセットに分割する

上記の私のコメントでは、代わりに凸多角形のセットを取得するために、凹多角形を再帰的に細分割することを提案しました。1つの（一般的な）アプローチは次のとおりです。

  1. ポリゴンが凸面の場合は停止します。（ポリゴンを配列に追加すると思います）
  2. ポリゴンのマークされていないエッジを選択します。エッジをマークします。
  3. ポリゴンをエッジ全体に分割します（実際には、エッジと一致する無限の線）。
  4. 両方の結果ポリゴンに対してこのアルゴリズムを再帰的に繰り返します（空でない場合）。

注：これはまさにBSPツリーの構築方法です。上記のアルゴリズムを除いて、ツリーノードを構築してポリゴンを格納していません。たぶん、BSPのみの解決策は、（OBBを使用する代わりに）問題の解決策になるでしょう。

ポリゴンの凸面のテスト（ステップ1）

エッジごとに、各頂点をエッジ上、エッジの前、または後ろに分類します。すべての頂点は、エッジ上またはエッジの前にある必要があります。そうでない場合（エッジの後ろに少なくとも1つの頂点）、ポリゴンは凹面です。「分類」の部分の詳細については、別の質問に対する私の回答を参照してください。これも同様です。

残り

凸状のサブポリゴンのリストを取得したら、元の投稿で行ったように、それらのOBBを生成できます。ただし、OBBツリーはありません...

細分割すると、頂点が追加されます（質問の懸念事項）。アプリケーションによっては、細分化されたポリゴンを使用する必要がない場合もあります。BSPツリーを使用し、単純な衝突のみが必要な場合は、ツリーをトラバースしてポイント/エッジの分類を行い、ポリゴンの頂点を処理しません。

とにかく、アプリケーションに何をさせたいのかわからないので、さらに何を推奨すればよいかわかりませんが、これが役立つことを願っています。

編集：おそらくこれがあなたがやりたいことだと気づきました：BSPツリーを構築し、ルートノードからリーフノードまでの各ノードのOBBを生成します。したがって、ルートノードOBBには凹多角形全体が含まれ、葉ノードには凸多角形のみが含まれます。元のDoomエンジンが似たようなことをしたことを覚えています（軸合わせされたBBを除く）。

于 2012-05-28T23:30:37.990 に答える