問題タブ [polyhedra]

x、y、および z 点のリストで定義された多面体のセットがあります。元の多面体を重ね合わせると、結果の多面体を見つけたいと思います。

境界 (x、y、z) を使用して各多面体の境界三角形を見つけ、SAT を調べましたが、重なり合う多面体の頂点を取得できるアルゴリズムは考えられませんでした。

注: これらの多面体にはそれぞれ 30 ～ 40 個のポイントがあり、私は約 5 個持っているので、大雑把な力ずくの方法では遅すぎる可能性があります。

このプロセスの名前は何ですか: 頂点の接続データを持つ既知の 2D ファセット (例: 三角形) から多面体を構築しますか?

もっと簡単に言えば、3D のすべてのピースがあり、どのコーナーをどのコーナーに接続する必要があるかがわかっている場合、3D オブジェクトを計算してからそれらをすべて接続するために使用されるプロセスは何ですか?

また、この研究の一般的に使用されているアルゴリズムまたは適切な出発点はありますか?

編集:三角形分割について話していると思いますが、ポリゴンを生成したくありません。既に知っています。面が適切に接続されるように、面を 3 次元で配置する必要があります。

堅牢な衝突検出アルゴリズムを探していて、Christer Ericson によるRealtime Collision Detectionという素晴らしい本を見つけました。特定の点が凸多面体の内部にあるかどうかをチェックする特定のアルゴリズムを使用しようとしています (3D 空間では、これらは四角錐、立方体、および四面体 (別名、すべての辺が三角形であるピラミッド) です)。私の場合、四角錐があります。ポイントの検証は、指定された数の半空間の交差ボリュームを使用し、多面体の側面によって張られるすべての平面の前または後ろにポイントがあるかどうかを判断することによって行われます。n特定の多面体の半空間の数を表す引数 (以下を参照) の使用法を理解するのが困難です。

DistPointPlane(...)与えられた点と平面の間の距離を計算して

3D空間で平面をPlane表す構造であること

アルゴリズムが行うことは、基本的に次のとおりです。

1. 与えられた点について、凸多面体の各平面までの距離を計算します
2. 距離が負か正かをチェック
   1. 距離が負の場合、ポイントは平面の法線の反対側にあるため、その後ろにあります。
   2. それ以外の点は平面の法線と同じ側にあるため、その前にあります
3. 指定された多面体のすべての平面の後ろを指している場合は内側にあり、そうでない場合は外側にあります

四角錐に関して言えば、私が知る限り、3D 空間を 2 つの半空間5 planes * 2 = 10 halfspaces( 私が得られないのは、n上記のアルゴリズムのコードでの使用です。Planeインスタンスの配列を反復するループの終了条件として使用されます。ただし、前述のように、半角スペースは 10 個あります。

掘り下げて考えたことの 1 つは、2 つの平面の交点が線 (ピラミッドの端) であるという事実です。Wolfram Mathworldをさらに引用

線を一意に特定するには、線上の特定の点も見つける必要があります。これは、両方の平面上に同時にある点を見つけることによって決定できます

任意の 2 つの辺 (底面を含む) について、ピラミッドの ​​2 つの頂点の間にある線を取得するため、ピラミッドの各頂点はこの要件を満たします。したがって、交差に関しては 5 (底部に 4、頂点に 1) ありますが、本のテキスト (関数の実装の上のコメントを含む) は曖昧であり、それを読むと間違った考えが得られる可能性があります (少なくともそれは私の場合）。

私の考え方は真実に近いのでしょうか、それとも数学の知識に関して大きな部分が欠けているのでしょうか?

私はコードを Python 3 に移植し、アルゴリズムを変更して、追加の引数を取らずに平面のリストだけをループして (私の考えが正しければ、基本的に元のものと同じです)、 でプロットしましたmatplotlib。それは完全に正常に動作しますが、私はそれを正しく理解しているかどうかを知りたいです:

ポイントを使用して平面を作成し、交点をとって多面体を形成し、それらの多面体を使用してネフ多面体を構築しています。およそ 2500 の多面体のうち、1 つがセグメンテーション違反を引き起こしているようです。

同じ入力を使用したレプリケーションを次に示します。