17

私の質問はかなり単純です。2 つの四面体があり、それぞれに現在の位置、空間内の線形速度、角速度、重心 (実際には回転の中心) があります。

このデータを使用して、(1) ある時点で衝突するかどうか、衝突する場合は (2) どのくらいの時間衝突したか、および (3) を正確に判断する (高速) アルゴリズムを見つけようとしています。 ) 衝突点。

ほとんどの人は、三角形と三角形の衝突検出を行うことでこれを解決しますが、これは、異なる三角形をチェックする際に、1 つの四面体の同じエッジを他の四面体の同じエッジに対してチェックするなどの冗長な操作で、いくつかの CPU サイクルを無駄にします。これは、物事を少し最適化することを意味するだけです。心配する必要はありません。

問題は、自己回転を考慮した公開の CCD (連続衝突検出) 三角形 - 三角形アルゴリズムを認識していないことです。

したがって、次のデータを入力するアルゴリズムが必要です。

  • 3 つの三角形の頂点データ
  • 回転/質量の位置と中心
  • 線速度と角速度

そして、次のように出力されます。

  • 衝突の有無
  • 衝突が発生した時間
  • 宇宙のどの点で衝突が発生したか

よろしくお願いします。

4

7 に答える 7

6

一般的に使用される個別の衝突検出では、連続する個別の時点で、各形状の三角形の衝突がチェックされます。計算は簡単ですが、テストされた離散ポイント間で衝突が発生するため、高速で移動するオブジェクトが別のオブジェクトに衝突するのを見逃す可能性があります。

連続衝突検出では、最初に、無限の時間にわたって各三角形によってトレースされたボリュームが計算されます。一定の速度で回転せずに移動する三角形の場合、この体積は三角柱のように見えます。次に、CCD はボリューム間の衝突をチェックし、最終的に、三角形が実際に同じスペースを共有しているかどうか、またその時間を追跡します。

角速度が導入されると、各三角形によってトレースされるボリュームはプリズムのようには見えなくなります。DNA のストランドのようなネジの形に似ているかもしれませんし、直線的にドラッグしながら任意の軸を中心に三角形を回転させることで得られる他の重要な形に見えるかもしれません。このようなボリュームの形状を計算するのは簡単なことではありません。

あるアプローチでは、四面体が直線的に移動していない場合、指定された角速度ベクトルで回転しているときに四面体全体を含む球を最初に計算することがあります。各頂点の回転円を計算し、そこから球を導き出すことができます。球が与えられると、押し出された CCD ボリュームを、球の半径を持ち、線形速度ベクトルに沿って進む円柱として近似できるようになりました。このような円柱の衝突を見つけると、衝突を検索する領域の最初の近似値が得られます。

2 番目の補完的なアプローチでは、各三角形によってトレースされる実際のボリュームを、ほぼプリズムに近い小さなサブボリュームに分割することで近似しようとする場合があります。時間の 2 つの増分で三角形の位置を取得し、それらの時点で三角形の頂点をトレースすることによって生成されたサーフェスを追加します。実際の曲線ではなく直線を結んでいるため、近似値です。全体的なエラーを回避するための近似では、三角形が回転のごく一部しか完了しないように、連続する各モーメント間の期間を十分に短くする必要があります。持続時間は、角速度から導き出すことができます。

2 番目のアプローチでは、さらに多くのポリゴンが作成されます。最初のアプローチを使用して検索ボリュームを制限し、次に 2 番目のアプローチを使用してより高い精度を得ることができます。

これをゲーム エンジンで解決している場合は、上記の精度で十分であることがわかるかもしれません (計算コストにはまだ身震いするでしょう)。むしろ、CAD プログラムを作成している場合や論文に取り組んでいる場合は、満足のいくものではないと感じるかもしれません。後者の場合、2 番目のアプローチを改良する必要があるかもしれません。おそらく、回転して移動する三角形が占める体積をより適切に幾何学的に記述することによってです (小さな回転角度に制限されている場合)。

于 2009-07-11T09:46:39.307 に答える
1

これが閉じた形の数学的アプローチの概要です。これの各要素は個別に表現するのが簡単であり、これらの最終的な組み合わせは、それを書き出すことができれば、閉じた形の表現になります。

1）四面体の各点の運動方程式は、それ自体の座標系ではかなり単純です。重心（CM）の動きは直線に沿ってスムーズに移動し、コーナーポイントはCMを通る軸を中心に回転します。ここでは、z軸と見なされます。したがって、各コーナーポイントの方程式（時間、t）はp = v t + x + r（sin（wt + s）i + cos（wt + s）j）です。ここで、vは重心のベクトル速度です。rは、xy平面への投影の半径です。i、j、およびkは、x、y、およびzの単位ベクトルです。およびxsは、t=0での回転の開始位置と位相を説明します。

2）各オブジェクトには、モーションを簡単に表すための独自の座標系がありますが、それらを比較するには、それぞれを共通の座標系に回転させる必要があります。これは、画面の座標系でもあります。（ただし、異なる座標系は空間に固定されており、四面体と一緒に移動しないことに注意してください。）したがって、回転行列を決定し、それらを各軌道（つまり、各四面体の点とCM）に適用します。

3）これで、すべて同じ座標系内の各軌道の方程式が得られ、交差の時間を見つける必要があります。これは、四面体の点からCMまでの線分のいずれかが別の三角形のいずれかと交差するかどうかをテストすることで見つけることができます。ここにあるように、これにも閉じた形の式があります。

これらのステップを階層化すると、ひどく醜い方程式になりますが、計算で解くのは難しくありません（ただし、四面体の回転では、極小値にとらわれないようにする必要があります）。別のオプションは、それをMathematicaのようなものに接続してクランキングを行うことかもしれません。（すべての問題に簡単に答えられるわけではありません。）

于 2009-07-13T21:22:17.470 に答える
1

私はかなりの時間をこのような幾何学の問題について疑問に思ってきました.正確な解決策は、単純なステートメントにもかかわらず、類似の 2D の場合でさえ、複雑すぎて実用的ではないようです.

しかし直観的に、線形並進速度と線形角速度を考慮すると、そのような解が存在することがわかります。ここで話しているのは、特殊でありながら複雑なケースであるため、Web や書籍で答えが見つかるとは思わないでください。いずれにせよ、反復的な解決策はおそらくあなたが望むものです。世界の残りの部分はそれらに満足しているのに、そうすべきではないのはなぜですか?

于 2009-07-11T22:09:30.630 に答える
1

回転していない四面体を衝突させようとしている場合は、ミンコフスキー和をとって光線チェックを実行することをお勧めしますが、回転では機能しません。

私が思い付くことができる最善の方法は、境界球を使用してスイープ球衝突を実行し、二分法または what-have-you を使用してチェックする時間の範囲を与えることです。

于 2009-07-13T06:56:08.277 に答える
0

申し訳ありませんが、私は数学好きではなく、正しい用語が何であるかわかりません。私の悪い言葉が私の意味を隠しすぎないことを願っています。

任意のタイムステップを選択します。

タイムステップで移動している軸に垂直な 2 次元で各形状の境界を計算します。

タイムステップの場合: 任意の 2 つのオブジェクトの境界のシャフトが交差する場合、半分のタイムステップと再帰を開始します。

有限交点が発生する点を発見するための、ますます精度の高い二分探索の一種。

于 2009-07-13T09:00:30.740 に答える
0

あなたの問題は線形計画問題にキャストされ、正確に解決されます。

最初に、(p0,p1,p2,p3) が時刻 t0 の頂点であり、(q0,q1,q2,q3) が時刻 t1 の最初の四面体の頂点であるとします。次の 4 次元の閉じたボリューム

V = { (r,t) | (r,t) = a0 (p0,t0) + … + a3 (p3,t0) + b0 (q0,t1) + … + b3 (q3,t1) }

ここで、a0...a3 および b0...b3 パラメータは区間 [0,1] にあり、合計は 1 になります。

a0+a1+a2+a3+b0+b1+b2+b3=1

2 番目の四面体も同様に凸多角形です (上記のすべてに ' を追加して、その移動する四面体の 4d ボリュームを V' と定義します。

これで、2 つの凸多角形の交点が凸多角形になります。これが最初に発生すると、次の線形計画問題が満たされます。

(p0,p1,p2,p3) が (q0,q1,q2,q3) に移動し、(p0',p1',p2',p3') が (q0',q1',q2',q3') に移動する場合次に、交差の最初の時間がポイント/時間 (r,t) で発生します。

t0*(a0+a1+a2+a3)+t1*(b0+b1+b2+b3) を最小化します。

0 <= ak <=1, 0<=bk <=1, 0 <= ak’ <=1, 0<=bk’ <=1, k=0..4
a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1) 
  = a0’*(p0’,t0) + … + a3’*(p3’,t0) + b0’*(q0’,t1) + … + b3’*(q3’,t1)

最後の式は、(r,t) の各次元に 1 つずつ、実際には 4 つの方程式です。これは、16 の値 ak、bk、ak'、および bk' の合計 20 の線形制約です。解決策があれば、

(r,t)= a0*(p0,t0) + … + a3*(p3,t0) + b0*(q0,t1) + … + b3*(q3,t1)

最初の交差点です。そうでなければ、それらは交差しません。

于 2012-07-29T09:11:13.867 に答える