天行健 君子當(dāng)自強(qiáng)而不息

　

2D隱式直線上的最近點(diǎn)

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

其中n是單位向量，我們的目標(biāo)是對(duì)任意點(diǎn)q，找出直線L上距q距離最短的點(diǎn)q^'，它是q投影到L上的結(jié)果。讓我們畫(huà)一條經(jīng)過(guò)q平行于L的輔助線M，如圖13.1所示。設(shè)n_M和d_M分別為直線方程的法向量和d值。因?yàn)長(zhǎng)和M平行，所以它們的法向量相等：n_M=n。又因?yàn)?/span>q在M上，所以d_M為q.n。

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

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

公式13.1   計(jì)算2D隱式直線上的最近點(diǎn)

　

參數(shù)射線上的最近點(diǎn)

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

其中d是單位向量，參數(shù)t在0到L間變化，L是R的長(zhǎng)度。 對(duì)一給定點(diǎn)q，我們想要找出在R上離q最近的點(diǎn)q^'。

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

點(diǎn)乘v . d的結(jié)果就是滿足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   計(jì)算參數(shù)射線上的最近點(diǎn)

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

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

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

　

平面上的最近點(diǎn)

考慮平面p，其定義為標(biāo)準(zhǔn)的隱式：滿足p . n = d的點(diǎn)的集合。

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

前面已經(jīng)學(xué)過(guò)如果計(jì)算點(diǎn)到平面上的距離，為了計(jì)算q^'，只要在n的方向上平移一段距離（公式13.3）：

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

公式13.3   計(jì)算平面上的最近點(diǎn)

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

　

圓和球上的最近點(diǎn)

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

設(shè)d為從q指向c的向量，該向量和圓相交于q^'。設(shè)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   計(jì)算圓或球上的最近點(diǎn)

　

AABB上的最近點(diǎn)

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

注意，如果q本來(lái)就在矩形邊界框內(nèi)部，代碼運(yùn)行的結(jié)果將返回原來(lái)的點(diǎn)。