4

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

  • 原点（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 つのアイデアは、エッジ テストをスキップすることです。三角形を効果的に平面に変えます。これは、メッシュが凸包である場合にのみ機能しますが、凸形状を作成する予定です。

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

4

5 に答える 5

10

これは、エッジと頂点を持つジオメトリに対して単一の光線を発射する場合に避けられない問題です。物理シミュレーションが最小の数値の不正確さを探しているように見えるのは驚くべきことです!

他の回答者によって提案された説明と解決策の一部は機能しません。特に：

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

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

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

ここにいくつかの本当の解決策があります：

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

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

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

Christer Ericson著のReal-Time Collision Detectionという本を強くお勧めします。446 ～ 448 ページにはこの正確な問題についての議論があり、184 ～ 188 ページには光線と三角形を交差させるスカラー三重積アプローチの説明があります。

于 2009-02-18T22:27:19.350 に答える
2

エッジにあるかどうかのテストを含めていないようです（「三角形のエッジの内側」と書いています）。コードを「以下」(内側またはオーバーラップ) に変更してみてください。

于 2008-09-19T04:11:01.453 に答える
1

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

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

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

于 2008-09-19T04:14:36.827 に答える
0

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

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) );
}

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

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

于 2008-10-03T19:01:04.063 に答える
0

@Statement:実際、コードで「以上」の比較を既に使用しています。提案ありがとうございます。+1

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

これは合理的な解決策ですか？

于 2008-09-19T04:25:30.000 に答える