3D での点と三角形の衝突検出

StackOverflow https://stackoverflow.com/questions/99542

  •  01-07-2019
  •  | 
  •  

質問

次の物理シミュレーションでの浮動小数点エラーを修正するにはどうすればよいですか:

  • 原点(x,y,z)、
  • 力を加えた後の目的の点 (x'、y'、z')。
  • エッジ BC を共有する 2 つの三角形 (A、B、C) と (B、C、D)

私は衝突検出にこの方法を使用しています。

For each Triangle
    If the original point is in front of the current triangle, and the desired point is behind the desired triangle:
        Calculate the intersection point of the ray (original-desired) and the plane (triangle's normal).
        If the intersection point is inside the triangle edges (!)
            Respond to the collision.
        End If
    End If
Next Triangle

私が抱えている問題は、点が時々浮動小数点演算の灰色の領域に入り、ライン BC に非常に近いため、技術的には常にどちらかの三角形と衝突するはずであるにもかかわらず、どちらの三角形にも衝突できないことです。彼らは利点を共有しています。これが起こると、点は 2 つのエッジを共有する三角形の間を通過します。コードの 1 行に次のマークを付けました (!) そこが私が変えるべきところだと信じているからです。

非常に限られた状況で有効なアイデアの 1 つは、エッジ テストをスキップすることです。三角形を効果的に平面に変換します。これはメッシュが凸包の場合にのみ機能しますが、凸形状を作成する予定です。

私は特に、すべての前後テストにドット積と三角形の法線を使用しています。

役に立ちましたか？

解決

これは、エッジと頂点を含むジオメトリに対して単一の光線を照射する場合に避けられない問題です。物理シミュレーションがいかに最小の数値誤差を追求しているかは驚くべきことです。

他の回答者が提案した説明や解決策の中には機能しないものもあります。特に：

  • 数値の不正確さにより、光線が「ギャップを通過」する可能性があります。問題は、線 BC に対してテストする前に、光線を平面 ABC と交差させる (たとえば、点 P を取得する) ことです。次に、線 BC に対してテストする前に、光線を平面 BCD と交差させます (たとえば、点 Q を取得します)。P と Q はどちらも最も近い浮動小数点近似によって表されます。これらが配置されるべき平面上に正確に配置されることを期待する理由はありません。したがって、BC の左側に P があり、BC の右側に Q の両方が存在する可能性はすべてあります。

  • 以下のテストを使用しても役に立ちません。問題は、光線と平面の交点の不正確さです。

  • 平方根は問題ではありません。必要な計算はすべて、ドット積と浮動小数点除算を使用して実行できます。

本物の解決策をいくつか紹介します。

  • 凸メッシュの場合は、あなたが言うように、すべての平面に対してテストし、エッジと頂点を無視することができます（したがって、問題を完全に回避できます）。

  • 光線を各三角形と順番に交差させないでください。代わりに、 スカラー三重積. 。(この方法では、各三角形を考慮するときに光線とエッジ BC に対してまったく同じ一連の計算が行われ、数値の不正確さが 2 つの三角形間で少なくとも一貫していることが保証されます。)

  • 非凸メッシュの場合は、エッジと頂点に幅を与えます。つまり、メッシュの各頂点に小さな球を配置し、メッシュの各エッジに沿って細い円柱を配置します。光線をこれらの球と円柱、および三角形と交差させます。これらの追加の幾何学的図形は、メッシュのエッジと頂点を通過する光線を阻止します。

この本を強くお勧めします リアルタイムの衝突検出 クリスター・エリクソン著。この正確な問題については 446 ～ 448 ページで説明し、光線と三角形を交差させるためのスカラー 3 倍積アプローチの説明は 184 ～ 188 ページにあります。

他のヒント

エッジ上にあるかどうかのテストが含まれていないように思えます（「三角形のエッジの内側」と書いています）。コードを「以下」(内側または重複) に変更してみてください。

浮動小数点の精度が有効になるように、レイが三角形の間に正確に収まる可能性は少し低いと思います。これが本当に問題であると確信していますか?

いずれにせよ、考えられる解決策は、1 つの光線だけを発射する代わりに、互いに非常に近い 3 つの光線を発射することです。1 つがちょうどその中間にある場合、他の 2 つのうち少なくとも 1 つは三角形上にあることが保証されます。

これにより、問題が本当に浮動小数点エラーなのか、それともより可能性の高いものなのかを少なくともテストできます。

@声明：確かに、コード内ですでに「以上」比較を使用しています。ご提案ありがとうございます。+1

私の現在の解決策は、エッジテストに小さなナッジ量を追加することです。基本的に、各三角形がテストされると、浮動小数点の誤差を打ち消すために、そのエッジが非常に少量だけ押し出されます。ゼロと等しいかどうかをテストするのではなく、浮動小数点計算の結果が 0.01 より小さいかどうかをテストするようなものです。

これは合理的な解決策でしょうか?

距離を測定する場合は、平方根に注意してください。彼らは捨てるというひどい癖がある 半分 あなたの精度。これらの計算をいくつか積み重ねると、すぐに大きな問題が発生する可能性があります。これが私が使用した距離関数です。

double Distance(double x0, double y0, double x1, double y1)
{
  double a, b, dx, dy;

  dx = abs(x1 - x0);
  dy = abs(y1 - y0);

  a = max(dx, dy));
  if (a == 0)
    return 0;
  b = min(dx, dy);

  return a * sqrt( 1 + (b*b) / (a*a) );
}

最後の演算は平方根ではないため、精度が失われることはありません。

私が取り組んでいたプロジェクトでこれを発見しました。それを研究し、それが何をするのかを理解した後、私は彼に祝福を与える責任があると思われるプログラマーを追跡しましたが、彼は私が何を言っているのか全く分かりませんでした。

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top