線分（つまり、2点間）が球と交差するかどうかを判断しようとしています。セグメントが球の表面と交差するかどうかだけで、交差の位置には関心がありません。このための最も効率的なアルゴリズムが何であるかについて誰かが何か提案がありますか？（交差位置には興味がないので、通常の光線と球の交差アルゴリズムよりも単純なアルゴリズムがあるかどうか疑問に思います）
12827 次
4 に答える
11
交差するかどうかを知る場合にのみ関心がある場合、基本的なアルゴリズムは次のようになります...
光線のベクトルA->Bがあるとします。
このベクトルと球の中心との間の最短距離は、光線ベクトルと、球の中心を通過するこれに対して90度のベクトルとの交点で発生することがわかります。
したがって、2つのベクトルがあり、その方程式は完全に定義されています。線形代数を使用してベクトルの交点を計算し、したがって線の長さ（またはより効率的には線の長さの2乗）を計算し、これが半径（または半径の2乗）よりも小さいかどうかをテストできます）あなたの球の。
于 2010-01-14T21:16:10.273 に答える
5
標準的な方法はわかりませんが、交差するかどうかだけを知りたい場合は、次のようにします。
一般的なルール...sqrt（）やその他のコストのかかる操作は避けてください。可能であれば、半径の2乗を処理します。
- 開始点が球の半径の内側にあるかどうかを確認します。これが当てはまらないことがわかっている場合は、この手順をスキップしてください。あなたが中にいる場合、あなたの光線は球と交差します。
これ以降、開始点は球の外側になります。
- さて、球に合う小さな箱を想像してみてください。そのボックスの外側にいる場合は、光線のx方向、y方向、およびz方向をチェックして、光線が開始するボックスの側面と交差するかどうかを確認します。これは、単純な符号チェック、またはゼロとの比較である必要があります。あなたが外にいて、そこから離れている場合、あなたはそれと交差することは決してありません。
これからは、より複雑な段階になります。出発点は、架空のボックスと球の間にあります。微積分と幾何学を使用して簡略化された式を取得できます。
やりたいことの要点は、光線と球の間の最短距離が球の半径よりも小さいかどうかを判断することです。
光線を（x0 + i t、y0 + j t、z0 + k t）で表し、球の中心を（xS、yS、zS）とします。したがって、（xS-x0-i t、yS-y0-j t、zS-z0-k t）の最短値が得られるようなtを見つけたいと思います。
x = xS-x0、y = yX-y0、z = zS-z0、D=ベクトルの2乗の大きさ
D = x ^ 2 -2 * x i t +（i * t）^ 2 + y ^ 2-2 * y j t +（j * t）^ 2 + z ^ 2-2 * z k t +（k * t）^ 2
D =（i ^ 2 + j ^ 2 + k ^ 2）t ^ 2-（x i + y j + z k）* 2 * t +（x ^ 2 + y ^ 2 + z ^ 2）
dD / dt = 0 = 2 * t *（i ^ 2 + j ^ 2 + k ^ 2）-2 *（x i + y j + z * k）
t =（x i + y j + z * k）/（i ^ 2 + j ^ 2 + k ^ 2）
tをD=...の方程式に戻します。結果が球の半径の2乗以下の場合、交差があります。それが大きい場合、交差はありません。
于 2010-01-14T20:16:30.987 に答える
4
このページには、この問題の正確な解決策があります。基本的に、直線の方程式を球の方程式に代入し、結果の2次方程式の判別式を計算します。判別式の値は交差を示します。
于 2010-01-14T20:46:29.550 に答える
-1
正確さが必要な場合は、とにかくその位置で作業する必要があります。アルゴリズムで速度を向上させる唯一の方法は、光線と球の交差から光線の境界ボックスの交差に切り替えることです。
または、さらに深く掘り下げて、sqrtやその他の内部関数呼び出しを改善してみることができます
于 2010-01-14T05:17:31.043 に答える