概述

幾何檢測主要相交性檢測，這里的內容大體上是根據《3D數學基礎-圖形與游戲開發》這本書來的，對于這本書來說，這一部分看完了后面內容就不看了，因為后面講的太空泛了，有點像一本絕世武功的目錄一樣，看似很強，其實沒什么卵用。

1.2D隱式直線上的最近點

問題描述：
直線p * n = d，對于任意點q，找出直線上距離q最短的點q’

同高中解析幾何簡單粗暴的公式不同，這里面的算法都是基于向量來計算的。
如圖所示，對于q來說，我們做另一條平行于原直線的直線，p’ * n’ = d’，顯然有q * n = d’
于是兩條直線分別為：
$$p?n=d$$
$$p?n=q?n$$
則其距離為d-q * n，但是我覺得是不是少除了個n的模長，這里的n應該是單位向量才正確！
然后交點就為
q’ = q + (d - q * n)n
如果n不是單位向量的話，那么距離應該等于
$$\frac{d?q?n}{|n|}$$

2.參數射線上的最近點

問題描述：
參數射線R：$p(t)=p_{org}+td$
d為單位向量，參數t在0到l之間變換，l是直線的長度。對于定點q，我們想要在射線R上求出距離q最近的點q’.

這個問題的求解要比上面的簡單一點，本質上是一個向量的投影問題。
設$v=q?p_{org}$,則$v?d=td$
這樣能得出q在直線上的投影向量，我們能解出來t，然后帶回到公式即可，有：
$q^{\prime }=p_{org}+(d?(q?p_{org}))d$

3.平面上最近的點

平面和直線的表達式其實是一樣的，也是
$$p?n=d$$
最后得到的表達式其實也是一樣的，但是推導過程有差別，如下圖所示，設有平面pn=d，n為單位法向量，q為不在平面上的任意一點，p為其在平面上的投影

有
p + an = q
(p+an)n = qn
pn+ann = qn
d+a=qn
a=qn-d
因此有q’ = q+an = q + (d-qn)n，也就是點到直線的最近點的公式一樣。

4.圓或球上的最近點

對于球心為c，半徑為r的球，球外一點q，在球上求一點q’，使得q’距離q最短。
我們設向量d = c-q，
那么有$b=d?\frac{|d|?r}{|d|}$
然后有q’ = q+b
則$q^{\prime }=q+d?\frac{|d|?r}{|d|}$

5.2D隱式直線的相交性檢測

這個檢測方法簡單粗暴，直接聯立兩個方程求解即可，解的個數應對著相交、平行、重合這三種情況。

6.3D中兩條射線的相交性檢測

3D直線的隱式方程實際上是兩個屏幕的交線，這種方式當然也可以聯立四個方程，同上面一樣進行求解，但這里我們討論參數方程的情況。
設兩條直線的參數方程為：
$$r_1(t_1)=p_1+t_1{d}_1$$
$$r_2(t_2)=p_2+t_2{d}_2$$
這個具體的推導還是很秀的，讓我推導我肯定不會，書上聯立$r_1(t_1)=r_2(t_2)$,然后經過一波天秀的推導，得到了下面的解：
$$t_1=\frac{((p_2?p_1)x{d}_2)?(d_{1}x{d}_2)}{|d1xd2{|}^2}$$
$$t_2=\frac{((p_2?p_1)x{d}_1)?(d_{1}x{d}_2)}{|d1xd2{|}^2}$$
當上面式子的分母等于0的時候，對應的是兩條射線平行或者重合，其他情況下$p_1(t_1)和p_2(t_2)$是距離最近的點，如果距離等于零，則表示相交，否則則兩直線屬于異面直線。

7.射線和平面的相交檢測

射線的參數方程定義為：$p(t)=p_0+td$,平面方程為p * n = d.
相交性檢測比前面求距離的要簡單的多，因為不需要很多的幾何理解，只需要聯立求交點就行，求得到，就有交點，求不到，就沒交點，把上面的公式聯立起來，得到解
$$t=\frac{d?p_0?n}{d?n}$$
同樣的，分母為0，則沒交點。

8.AABB包圍盒和平面的相交性檢測

AABB包圍盒有8個頂點，我們把它代入到p* n= d這個平面方程中去，然后如果八個點全部小于或者大于d則不相交，否則相交，書上有優化的辦法，可以不用求所有的八個點，但是我感覺已經沒什么必要了，沒什么明顯的復雜度改進沒必要加大算法難度。

9.三個平面的相交性檢測

也是一個解方程組的問題，三個平面是否相交于一點，如何求該點，首先三個平面分別為：
$$p{n}_1=d_1$$
$$p{n}_2=d_2$$
$$p{n}_3=d_3$$
然后聯立可以求得：
$$p=\frac{d_1(n_{3}x{n}_2)+d_2(n_{3}x{n}_1)+d_3(n_{1}x{n}_2)}{(n_{1}x{n}_2)?n_3}$$
怎么推導的就別管了，頭發要緊。

10.射線和圓/球的相交性檢測

這個檢測很有技巧性，比起直接聯立方程來說，這種方法的實現難度也同時低很多。

這個幾何體的構造就挺有東西的，直線的方程是$p(t)=p_0+td$，d為單位向量，圓的圓心為c，半徑為r。
我們的目的是求出來t，然后代入到直線方程就可以得到交點的信息。
t=a-f
a=(c-p0)d//P0C在直線上的投影
對于f，有
$$f^2+b^2=r^2$$
$$b^2=e^2?a^2$$
聯立可解得
$$f=\sqrt{r^2?e^2+a^2}$$
則有
$$t=a?\sqrt{r^2?e^2+a^2}$$
若根號內為負值，則不相交。

11.兩個圓/球的相交性檢測

對于靜止的兩個球來說，求是否相交是非常簡單的，只需要判斷他們距離的平方和兩個半徑的平方和的大小即可。

12.球和AABB的相交性檢測

只需要判斷距離球心最近的包圍盒的距離球心的距離和求半徑的關系即可。

13.球和平面的相交性檢測

只需要判斷球心和平面的距離和球半徑的關系即可。

14.射線和三角形的相交性檢測

這里涉及到三角形的重心坐標系，三角形平面上每個點都可以用三個頂點的線性組合來表示，這個坐標就是三角形的線性坐標，假設我們已知三角形的三個頂點，以及三角形平面上一點p的坐標，設p在三角形重心坐標系的坐標為(b1,b2,b3)則有
$$p_x=b_1{x}_1+b_2{x}_2+b_3{x}_3$$
$$p_y=b_1{y}_1+b_2{y}_2+b_3{y}_3$$
$$b1+b2+b3=1$$
當b1=b2=b3=$\frac{1}{3}$的時候，我們認為p點是三角形的重心坐標，由上面的式子，可以解得：
$$b_1=\frac{(p_y?y_3)(x_2?x_3)+(y_2?y_3)(x_3?p_x)}{(y_1?y_3)(x_2?x_3)+(y_2?y_3)(x_3?x_1)}$$
$$b_2=\frac{(p_y?y_1)(x_3?x_1)+(y_3?y_1)(x_1?p_x)}{(y_1?y_3)(x_2?x_3)+(y_2?y_3)(x_3?x_1)}$$
$$b_3=\frac{(p_y?y_2)(x_1?x_2)+(y_1?y_2)(x_2?p_x)}{(y_1?y_3)(x_2?x_3)+(y_2?y_3)(x_3?x_1)}$$
我們判斷三角形和射線相交的方法如下：
1.計算射線和三角形平面的交點
2.計算交點的重心坐標
3.如果重心坐標某一分量小于零，則其在三角形外，沒有交點，否則有交點，交點可以通過重心坐標乘上三角形頂點坐標獲得。

15.兩個AABB的相交性

如果一個包圍盒x最小值都大于另一個包圍盒x的最大值，則不相交，按照這個理論，有六種緯度去判斷，只要有一種不滿足，則其不相交。

16.后記

書上介紹的比我這個是要復雜一點的，還包括了動態的相交檢測，這里我沒涉及到，如果有需要用到的時候再看吧，也許那會是下輩子。。。

總結

以上是生活随笔為你收集整理的几何检测的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。