天行健 君子當自強而不息

2D隱式直線上的最近點

考慮2D中的直線L，L由所有滿足p . n = d的點p組成。

其中n是單位向量，我們的目標是對任意點q，找出直線L上距q距離最短的點q^'，它是q投影到L上的結果。讓我們畫一條經過q平行于L的輔助線M，如圖13.1所示。設n_M和d_M分別為直線方程的法向量和d值。因為L和M平行，所以它們的法向量相等：n_M=n。又因為q在M上，所以d_M為q.n。

現在可以得知，M到L的有符號距離為：d - d_m = d - q . n。這個距離顯然等于q于q^'之間的距離（如果結果只需要距離而不是q'的值，到這里可以停止計算了)。為了計算q^'，只需要將q沿n的方向位移一定距離（公式13.1）：

q^' = q + (d - q . n)n

公式13.1   計算2D隱式直線上的最近點

參數射線上的最近點

考慮在2D或3D中的參數射線R：p(t) = p_org + td

其中d是單位向量，參數t在0到L間變化，L是R的長度。 對一給定點q，我們想要找出在R上離q最近的點q^'。

這是一個簡單的向量到向量的投影問題，設v為p_org到q的向量，我們希望得到v在d上的投影，或v平行于d的部分，如圖13.2所示：

點乘v . d的結果就是滿足p(t)=q^'的t值。

t = d . v = d . (q - p_org)

q^' = p(t) = p_org + td = p_org + (d . (q - p_org))d

公式13.2   計算參數射線上的最近點

實際上，等式p(t)求得了在包含R的直線上距q最近的點。如果t<0或t>L，則p(t)不在R的范圍內。這種情況下，R上距q最近的點是原點（如果t<0）或者終點（ t>L）。

如果射線的定義是t從0到0變化，d不必是單位向量，那么在計算t值時必須除以d的模：

t = d . (q - p_org) / ||d||

平面上的最近點

考慮平面p，其定義為標準的隱式：滿足p . n = d的點的集合。

其中n為單位向量，給定一點q，我們想要找到點q^'，它是q在p上的投影。q'就是p上離q最近的點。

前面已經學過如果計算點到平面上的距離，為了計算q^'，只要在n的方向上平移一段距離（公式13.3）：

q^' = q + (d - q .n) . n

公式13.3   計算平面上的最近點

注意到，該式和用于計算在2D中隱式直線上最近點的公式13.1相同。

圓和球上的最近點

考慮2D中的點q和圓心為c、半徑為r的圓（下面的討論也適用于3D中的球體）。我們希望找到點q^'，它是圓上離q最近的點。

設d為從q指向c的向量，該向量和圓相交于q^'。設b為從q指向q^'的向量，如圖13.3所示：

可以清楚地看出，||b|| = ||d|| - r，因此：

b = ((||d|| - r)/||d||)d

將此位移加到q上，并將它投影到圓上（公式13.4）：

q^' = q + b = q + ((||d|| - r)/||d||)d

公式13.4   計算圓或球上的最近點

AABB上的最近點

設B是由極值點p_min和p_max定義的AABB。對任意點q都能很容易地計算出B上距離q最近的點q^'。所用的方法是按一定的順序沿著每條軸將q推向B。見程序清單13.1：