Real-Rime Rendering (8) - 光線求交（Ray intersection）

提要

       光線在圖形學中可以簡單地用向量來表示：r(t) =  o +td, o表示光線的出發點，d表示光線的方向，通常是單位向量，r表示光線在t時刻的位置。

       光線求交在圖形學中有著非常重要的應用，比如Global Illumination,collision detect，更是Ray tracing算法的核心。

包圍體 Bunding Volume

       首先要提一下包圍體的一些基本概念。

      在計算機圖形學與計算幾何領域，一組物體的包圍體就是將物體組合完全包容起來的一個封閉空間。將復雜物體封裝在簡單的包圍體中，就可以提高幾何運算的效率。通常簡單的物體比較容易檢查相互之間的重疊。
一組物體的包圍體也是包含一個物體及周圍相關環境的封閉空間，因此可以用它來表示一個非空、有限的單一物體。

       AABB

       AABB的全稱是axis aligned bounding box，就是我們常常提到的包圍盒子，這個盒子的邊是平行于x/y/z軸的。 所有的2d和3d物體都是由點組成的，所以只要找出這些物體的最大值點和最小值點，那么就可以使用這兩個點表示該物體的AABB包圍盒了。
       檢測碰撞的時候我們只需要檢測這些物體的AABB（即他們的最大值點和最小值點）是否相交，就可以判斷是否碰撞了。因為AABB總是與坐標軸平行，不能在旋轉物體時簡單地旋轉AABB，而是應該在每一幀都重新計算。如果知道每個對象的內容，這個計算就不算困難，也不會降低游戲的速度。然而，還面臨著精度的問題。

        k-DOP

        DOP是Discrete orientation polyhedron的縮寫，指的是離散方向多面體，是一般化的 AABB。DOP 是一個包含物體的二維空間的凸多邊形或者三維空間的凸多面體，它是一組無限遠的定向平面移動到與物體相交而得到，于是 DOP 就是這些平面相交平面所生成的凸多面體。三維圖形中構建 DOP 的流行方法有從 6 個按照坐標軸排列的平面得到的按坐標軸排列的包圍盒，以及 10 （豎直邊上取斜面）、18（所有邊取斜面）或者 26 個平面（所有邊及定點上取斜面）得到的斜面包圍盒。從 k 個平面構建的 DOP 稱為 k-DOP；但是由于一些表面可能會縮減到一條邊或者一個定點，所以實際的表面數目可能會少于 k。 凸包是包容物體的最小凸體。如果物體是有限個點的集合，那么凸包就是一個多面體，實際上它是包容多面體的最小立體。

Bounding Sphere 

      包圍球是一個包容物體的球面。在二維圖形中，這是一個圓，包圍球就用圓心及半徑進行表示。包圍球的碰撞檢測速度非常快：當兩個球心距離不超過半徑之和時就會相交。這樣包圍球就可以用于物體可以向任意方向移動的場合。

      包圍球的創建有很多種,有著各自的質量和速度的權衡(人生就是一場Trade Off 啊!).最快的方式就是創建一個AABB,找到中心,然后以對角線為直徑畫一個球就可以了.然而這種方式找到的球并不是最合適的,一種改進的方法是還將AABB的中心當作球心,然后遍歷整個模型的頂點,找到離球心最遠的頂點(計算的時候用半徑的平方來比較可提高運算速度),那這個球就是最合適的Bounding Sphere 了.

OBB

     方向包圍盒（Oriented bounding box），簡稱OBB。方向包圍盒類似于AABB，但是具有方向性、可以旋轉，AABB不能旋轉.

     碰撞判定條件:兩個多邊形在所有軸上的投影都發生重疊，則判定為碰撞；否則，沒有發生碰撞。

       OBB這種方法是根據物體本身的幾何形狀來決定盒子的大小和方向，盒子無須和坐標軸垂直。這樣就可以選擇最合適的最緊湊的包容盒子。OBB盒子的生成比較復雜。一般是考慮物體所有的頂點在空間的分布，通過一定的算法找到最好的方向(OBB盒子的幾個軸).

光線與球相交 Ray/Sphere Intersection

        空間中的一個球只需要一個點和一個半徑值就可以定義了，用隱式的方法定義為：

||x-c||=r

p表示球體上面的點，只要把x=r(t)帶入，求解即可得交點。具體的運算過程如下（令v=o-c）。

若根號內為負數，即相交不發生。另外，由于這里只需要取最近的交點，因此正負號只需取負號。

        對于其他的類似的二次曲面，比如圓柱，圓錐，圓環，求解的方式和圓球的類似，都很直接。首先是寫出二次曲面的隱式表達式，然后將光線的表達式帶入，最后求解，通過方程的根的情況來判斷相交的情況。

優化

       上面的算法只是最粗暴的算法，很多情況下有些計算不是必要的，有很多優化的空間。

        首先我們計算一個向量 l = c - o，o是光線的出發點。

        第一個判斷是求出l的長度，和球的半徑相比，如果有 l^2<r^2 ，則光線的源頭就在球體內部，光線肯定和球體相交，如最右邊的圖否則再進行第二次判斷.

        計算 l 和 d 的點乘， s = ld ,若s<0,則說明球體在光線的后面，肯定不相交，如中間圖。

        接下來還要進行一次判斷，通過求解 m^2 = l^2 - s^2（Pythagorean theorem），得到球心到直線的垂直距離，若m^2>r^2, 光線不與球相交，否則光線與球相交，這種情況下再求解交點。

          交點的求解還需要一點功夫。首先計算 q^2 = r^2-m^2，這里q>=0，再計算t1=s-q,t2=s+q，帶入光線的方程，得到光線和球相交遠近端的位置。

偽代碼

         優化了的算法將計算盡量推遲，算是Lazy Evaluation 策略，免去了很多不必要的計算。

光線與平面相交 Ray/Plane  Intersection

        平面在空間幾何中可以用一個向量（法向量）和平面中的一點P0來表示。

平面就是滿足下式的點集：n.（P-P0）= 0

得到：n.P=d; d=n.P0;

給定射線r(t) =  o +td,平面方程為n.p+d=0,將p(t)帶入到平面方程，最后求得t：

 t = (-d-(n.p0))/(n.d)

光線與Box相交  Ray/Box Intersection

        這里的Box用OBB來代替。需要求的的結果還是t，光線運行的距離。

        這里將OBB看作是由三個夾板（slab）組成的Box， 問題就轉化為求解光線和OBB的每個面的的t值的問題。對于每一組夾層，光線都可以得到兩個t值，tmin和tmax，計算下面的式子：

上圖表示的是二維的情況。

        接下來是見證奇跡的時刻：如果tmin<tmax，那么光線和OBB相交，反之，不相交，不相信的畫看上面的圖。

        偽代碼如下：

ac是是OBB的中心，au，av，aw分別是三組面的法向量。

光線三角形相交  Ray/Triangle Intersection

最先想到的是 首先判斷射線是否與三角形所在的平面相交，如果相交，再判斷交點是否在三角形內。
判斷射線是否與平面相交
判斷點是否在三角形內
但是，上面的方法效率并不很高，因為需要一個額外的計算，那就是計算出三角形所在的平面，而下面要介紹的方法則可以省去這個計算。

首先要介紹的三角形的重心坐標。

在三角形情形中，重心坐標也叫面積坐標，因為 P 點關于三角形 ABC 的重心坐標和三角形 PBC, PCA 及 PAB 的（有向）面積成比例，為,則P的重心坐標就是.

三角行中的一點，隱式表達式為：

這里的u，v，(1-u-v)其實就是重心坐標。

還是和前面一樣，將光線的表達式帶入

寫成矩陣的形式，最左邊的矩陣記為M。

求解這個線性方程組，就可以得到t,u,v。記e1 =p1-p0, e2=p2-p0 , s=o-p0.由于克萊默法則得到：

由行列式的定義知：det(a,b,c)=|a,b,c|=-(axc).b=-(cxb).a.

記q = dxe，r=sxe，式子可以化為：

到這里，就可以求t，u，v了。

之所以在計算中用了很多中間量，是因為這樣可以加速運算。

最后給出偽代碼.

第四行求的a是M的行列式。第五行是判斷行列式不能為0.

參考

包圍體 - http://zh.wikipedia.org/wiki/%E5%8C%85%E5%9B%B4%E4%BD%93

碼農干貨系列【1】--方向包圍盒(OBB)碰撞檢測 - http://www.cnblogs.com/iamzhanglei/archive/2012/06/07/2539751.html

wiki重心坐標 - http://zh.wikipedia.org/wiki/%E9%87%8D%E5%BF%83%E5%9D%90%E6%A0%87

Real time rendering 3rd