3D ポリゴン メッシュと対応する 2D ポリゴン メッシュ (実際にはUV マップから) があり、ジオメトリを 2D 平面にマッピングするために使用しています。平面上のポイントが与えられた場合、その 2D ポイントを 3D にマッピングするために、そのポイントが置かれているポリゴンを効率的に見つけるにはどうすればよいでしょうか?
私が考えることができる最善のアプローチは、ポリゴンを 2D インターバル ツリーに格納し、それを使用して候補ポリゴンを取得することです。より簡単なアプローチはありますか？
明確にするために、これはシェーダー用ではありません。私は実際に 2D の物理シミュレーションを取り、それを 3D メッシュに巻き付けてレンダリングしています。各オブジェクトを描画するには、実際の 2D 位置に対応する 3D のポイントを把握する必要があります。*
したがって、単に実装しようとしている場合は、おそらくすべての三角形のグローバル検索から開始します。各三角形の 2 次元点の重心座標を計算し、重心座標がすべて正である三角形を見つけ、次に、それらを使用して 3d にマップします (stu の位置に 3d ポイントを掛けます)。最初にこれを行い、十分に高速でない場合にのみ、より複雑なものを試します。
2 次元の点ではなく三角形で反復できる場合、重心法はおそらく十分に高速です。しかし、マッピングする必要がある任意の位置に多数の 2D ポイントがあり、ポイントはフレームごとに位置が変わるようです。
このような状況の場合は、フレームごとにローカル アップデートを実装することで、大幅な高速化が得られる可能性があります。各 2d ポイントは、それがどの三角形の中にあるかを覚えています。それを現在の三角形として設定します。新しい位置が現在の三角形内にあるかどうかをテストします。そうでない場合は、メッシュをターゲットの 2d ポイントに最も近い隣接する三角形に移動します。エッジに隣接する各三角形は、エッジ上の 2 つの共通点と別の点で構成されます。エッジに隣接する三角形の他のポイントのうち、ターゲットに最も近いポイントを見つけて、それを現在のポイントとして設定します。それから繰り返します - それはかなり早く見つけるべきだと思いますか? 各三角形の最大サイズをキャッシュすることもできます。
しかし、コメントで述べたように、凹み、穴、または個別の接続されたコンポーネントを持つメッシュで問題が発生する可能性があり、局所的な最小値に陥る可能性があります。これに対処するには、いくつかの方法があります。最も簡単な方法は、訪問したすべての三角形のリストを保持し (三角形のフラグ、 vector< bool > または set<三角形インデックス > として)、三角形の再訪問を拒否することだと思います。現在の三角形のすべての近隣を訪問したことがわかった場合は、グローバル検索に戻ります。このような失敗はめったに起こらない可能性が高いため、パフォーマンスがそれほど損なわれることはありません。
この種のフレームごとの更新は非常に高速であり、三角形を含む最初の部分を計算するためのまともなアプローチでさえあるかもしれません - ランダムな三角形を選択してそこから歩くだけです (n 個すべての三角形をチェックすることから、おおよそ aターゲットへの直線）。十分に高速でない場合は、2d メッシュ ポイントの kd ツリー (または類似のもの) と、各メッシュ ポイントの単一の接触三角形インデックスを保持することができます。反復をシードするには、kd ツリーでターゲットの 2d ポイントに最も近いポイントを見つけ、隣接する三角形を現在の三角形に設定してから反復します。
私が見たトライアングル メッシュの 1 つのアプローチは次のとおりです。トライアングルを選択し、各辺が半分のスペースを定義していると想像してください。特定のエッジの場合、ハーフ スペース境界はエッジを含む線であり、ハーフ スペースには三角形は含まれません。対応する半分のスペースにターゲット ポイントが含まれるエッジを選択します。次に、エッジの反対側の三角形を選択し、プロセスを繰り返します。
この方法を使用すると、最終的にターゲット ポイントを含む三角形に到達します。
この方法は、2D インターバル ツリーを実装するよりも簡単であると言えますが、検索の効率は低くなります (n三角形の数が O(log n) ではなく O(√n) である場合)。また、ポリゴン メッシュに対しても機能するはずです。 、ポリゴンが凸状である限り。