6. 距離


距離の求めかた。

パラメータで表される,,の二乗距離を求めたいなら、


この関数のでの極小値を考えれば良い。これは連続で微分可能な関数なので

か、さもなくばの境界での点ある。


6.1 点からリニアなコンポーネント


ここで言うリニアコンポーネントとは、直線,線分の両方を含めたものである。


以下の議論は3次元に限らずいかなる次元でも成り立つ。


点をとする。線はパラメータを使ってと書く。は線上の点,は線の方向。


半直線(ray)も同じ形式で、という制限がつくだけだ。

線分(line segment)の場合、という制限になる。


に最も近い線上の点は、のこの線への投影地点であるから、



Pから線分までの距離は、


言うまでもなく半直線と点との距離を求めていて、という制限があるときに、なる答えになったら、


ですよ、と。以下、線分の時も同様。

での割り算は結構な計算コストがかかるので、かそういうの先に確認してから、本当に必要になってから計算するのが常道である。

もし可能ならばを単位ベクトルとなるように正規化しておいても良い。


6.2 リニアコンポーネントからリニアコンポーネント


,

,

の2つのリニアコンポーネント間の距離を考えてみる。

言うまでもなくならば、直線 , ならばray , ならば線分。に関しても同様。


二乗距離

なので、これ展開して係数うざいんで置き換えたら


こんな感じ。

s,tで偏微分,が(0,0)となる点か、領域の境界かが最小。この前者の方程式をs,tについて解くには、行列表現

を考え、両辺の左からを掛けるとてっとり早い。


また のときは逆行列は存在しないが、これは

で、これが0ということは、,が平行であることを意味する。この場合は、上のどこか一点ととの距離を求めると良い。これはにしとけばシンプルでよい。


直線と直線との距離

上で求めたので割愛。

線からrayか線分

これも同様なので割愛。


rayからrayか線分,線分から線分


これ実は少し面倒。


例えば線分と線分との交点。線分は、だが、

が、なら何の問題もないが、解がこの範囲外だとしたらどうすれば良いのか?


たとえば、だったとしよう。は範囲内だが、は範囲外である。

は、s,tによる2次方程式だから、(x,y,z)=(s,t,(s,t))の描く図形はパラボロイド(paraboloid:放物線を回転させたような図形)である。この図形をz=でスライスしたらこれはを中心とする楕円である。そのへんを考えてを大きくしていき、この楕円が大きくなっていくときに、と最初に接するのはどこかを考える。

これは、で、である。これがを最小化する境界の端点。楕円が傾いているかも知れないのでになる。のうち片方が領域からはみ出している場合については、これと同様。


の両方が領域からはみ出している場合、たとえば、のような場合は、と、どちらかがを最小化する境界の端点。このどちらが解なるかと言うと..


を考えてみると、パラボロイドなので、(s,t)=(1,1)の地点では,の両方が負になることはない。

なら , , なので上に解。

なら , , なので上に解。


以下、の両方が領域からはみ出している場合は、これと同様。

そんなわけで全部で3×3=9の場合分け。


6.3 点から3角形


点:

3角形:

との距離を求めてみる。


例によって二乗距離

これ展開して係数うざいんで置き換えたら


とまあ、さっきと同じ式が出てくるではありませんか。


じゃあ例によって、を解くと



なら何も問題はないんですけど、これがの外にある場合はどうなるのかと。


これは、例によって、パラボロイド考えて、そのスライスがどこの境界に接するか考えていけばok。


そんなわけで場合分けは7個。


6.4 リニアコンポーネントから三角形


直線:,

3角形:

例によって二乗距離


(係数は例によって適当に置き換えた)

で最小。これは

となるので、逆行列使えば簡単に求まる。

この解ならその点で最小。これがこの領域外だと、例によって、もよりの境界上で最小。


線から三角形


同様なので割愛。


半直線から三角形、線分から三角形


同様なので割愛。


6.5 点から四角形


点から3角形の時と同様。求まった解が領域外の時についての場合分けが増えるだけ。


6.6 リニアコンポーネントから四角形


リニアコンポーネントから三角形の時と同様。求まった解が領域外の時についての場合分けが増えるだけ。


半直線から四角形,線分から四角形


これも同様。


6.7 三角形から三角形


二乗距離,

の領域はデカルト積(Cartesian product) になる。

場合分けは、3角形によって7つの場合分けが発生するので、7×7=49個の場合分けが必要。


6.8 三角形から四角形

これまた同様。の領域はデカルト積。7×9=63の場合分けが必要。


6.9 四角形から四角形

これまた同様。9×9=81の場合分けが必要。


6.10 点から方位性のあるボックス(point to oriented box)


ボックス:中心,正規直交単位軸,範囲

これらを用いて点を表す:


係数で求まる。

がボックス内部にあれば、距離は0。ボックス外部にあれば、この座標系において、方位性のないボックスと点との距離を求めるようにすれば求まる。


6.11 その他


点から楕円(point to ellipse)


考えるのは軸に沿った(axis−aligned)楕円だけで十分。

方位性をもった楕円(oriented ellipses)は回転させて考えれば良い。

楕円は円を軸方向に引き延ばしただけなので、それを考慮に入れると解きやすい。


点P:

楕円:

この楕円上でこの点へもっとも近い点をとする。

このとき、は、楕円の法線である。

はパラメータ。

これを解いて

んで、楕円の方程式にこれ代入

分母であるを両辺に掛けてみる。


この解が点Pに対して楕円上で一番近い点でのtの値を表している。ニュートン法で解くと良い。


初期値は(u,v)が楕円内部なら , 楕円外部ならが良い。


点から楕円体(point to ellipsoid)


楕円体:

までの距離。以下、楕円の時と同様。


点から二次曲線or二次曲面(point to quadratic curve or quadric surface)


手順は点から楕円の時と同様。


一般的な2次方程式:



の対称行列 ,

のベクトル。

はスカラー。


と表される。そこで。

平面:

点:

との距離を調べてみる。この平面上のに最も近い点をとする。


楕円の時同様、での平面の法線になっているはずである。平面の法線はである。

はパラメータ


これを元の方程式に代入して、tについて解くのだけど、その前にと対角化してからのほうが良い。


は簡便化のための置換。


2次元のとき:

3次元のとき:


この逆行列求めるときに2次元のときは、tについての4次方程式,3次元のときはtについての6次方程式になる。


3次元で点から円(point to circle in 3D)


点P:

いま問題とする円を含む平面を考える。

平面: , 法線を表す単位ベクトル, は円の中心

この平面上の円から点までの距離を考える。

と正規直交になる,をとり円を

, は円の半径

と表す。


距離の二乗関数は

この最小値を求める。


いまなのでこれを微分(積の微分法)すれば、がわかる。

また、これを微分すれば

すなわち、なのでは単位長ベクトルだとわかる。

また、なので積の微分法によりよって、に対して垂直である。

以上からをこの平面に投影したものに平行である。


のこの平面への投影をとすると


は単位ベクトルなので正規化すると

Pにもっとも近い円上の点


なら距離は

ならの投影点がと同じということなのでPから円上のどの点に対しても等距離。このとき距離は


3次元上の円から円(circle to circle in 3D)


二つの円の距離を求める

円1:

円2:


二乗距離を考えて、

以下、ごちょごちょするのだが結構面倒くさい。8次方程式が出てくる。


3次元上の楕円から楕円(ellipse to ellipse in 3D)

パラメータによる楕円



あるいは、平面と楕円体との交差領域で楕円を定義




・多項式による解法(solution as polynomial system)


これはもう何というか、やってられない。円と楕円は12次方程式,楕円同士だと16次方程式になる。


・三角法による解法(trigonometric solution)


これもややこしい。ごちゃごちゃ。


・数値計算による解法(numerical solution)


もう、これくらい複雑ならパウェル法(Powell’s method)とかで解いてしまったほうがてっとりばやい。


参考文献

1.『3DGame EngineDesign』 , David H.Eberly , MORGANKAUFMANNPUBLISHERS ,ISBN1−55860−593−2.

2.『Mathematics for 3d Game Programming and Computer Graphics (Game Development Series)』 , Eric Lengyel , Charles River Media , ISBN 1−58450−277−0 .