質問＜１９８８＞２００４／１０／５
from=久喜工太郎
「線と球と当たり判定」

3D空間で、線分 AB と、球体 C があり、球体の半径をrとすると、
線分ABと球体Cが交差するかを求めるにはどうすればいいですか？
(A,B,Cは、3次元ベクトルとする)
これはプログラムで処理したい内容なので、二次方程式や、連立方程式は
使わずに、できるだけ簡単かつ高速に処理できるような内容でお願いします。

★希望★完全解答★

お便り２００４／１０／６
from=juin

球の中心をOとする。
線分ABを分割する。分点をA=p0,p2,..,pn=Bとし、|pi-pi+1|＜rとする。
(1)ある分点pkに対して、|pk-O|＜rならば交差している。
(2)すべての分点pkに対して|pk-O|＞ｒのときを考える。
|pk-O|の小さい方から２つの分点を選びpk1,pk2とする。
[1] |(pk1+pk2)/2-O|＜rならば交差している。
[2] |(pk1+pk2)/2-O|＞rならば交差していない。

お便り２００４／１０／１２
from=久喜工太郎

juinさんにアドバイスいただいたやり方だと計算時間がかかってしまいますし、
しかも、精度が低いようです。
別の方法で、できるだけ簡単かつ高速に処理できるような内容はありません
でしょうか？
（※文章の表現をadminが若干変えました。）

お便り２００４／１０／２８
from=naoya

ゲームプログラミング関係の掲示板に質問に行ったほうが適切なアドバイスが
もらえるかもしれないなぁ、と思う。

とりあえず問題が3Dプログラミングみたいなので、ベクトルを駆使します。
正射影ベクトルを使えば出来ます。速さ重視のようなのでループなしで四則演算
と比較のみで出来るようなものを考えてみました。

A(a), B(b), C(c)とする。

①線分AB上でもっとも球の中心に近い点E(e)の決定をする。
点Cから直線ABにおろした垂線の足をH(h)とする。

a,b,c,e,h:vector
  r(半径):scalar

    (b-a)・(c-a)
h-a=────── (b-a) が成り立つ。（∵正射影ベクトル）
    (b-a)・(b-a)

(i)(b-a)・(c-a)≧0のとき
    |h-a|≦|b-a| ならば E=H (e=h)
    |h-a|＞|b-a| ならば E=B (e=b)
(ii)(b-a)・(c-a)＜0のとき
    無条件に E=A (e=a)

となる。

② 点Eと点Cの距離をしらべて、球と線分の位置関係を判定する。
(i)  |e-c|≦r ならば、交差している。
(ii) |e-c|＞r ならば、交差していない。