張煒喆

（同濟(jì)大學(xué)電子與信息工程學(xué)院，上海，201804）

0 引言

隨著圖形學(xué)技術(shù)的突破和發(fā)展，光線追蹤算法正在逐步取代光柵化算法，成為實(shí)時渲染領(lǐng)域新的主流技術(shù)。不論是光線追蹤還是光柵化，它們都離不開三角形這一最基礎(chǔ)的幾何模型。因此，能否快速準(zhǔn)確的計算出光線和三角形的交點(diǎn)決定了整個渲染過程的效率。

解決該問題的一個十分樸素的思路是首先聯(lián)立射線的參數(shù)方程和平面的參數(shù)方程，求解出光線與三角形所在平面的交點(diǎn)，然后通過三次叉積的計算來判斷該交點(diǎn)是否在三角形內(nèi)部。但是由于要經(jīng)過兩個復(fù)雜的步驟以及多次向量計算，該算法在如今并沒有被實(shí)際項(xiàng)目采用。M?ller和Trumbore后來提出了一種改進(jìn)的被簡稱為MT的算法[1]，也是現(xiàn)在最為通行的算法，它將三角形和射線的交點(diǎn)用三角形的重心坐標(biāo)的形式表示，經(jīng)過一系列移項(xiàng)，使其轉(zhuǎn)化為形如Ax=c的形式，其中A是一個可逆矩陣，x和c都是列向量。在此基礎(chǔ)上，MT算法利用克萊姆法則對該等式求解，從而可以得到三角形與射線交點(diǎn)的用重心坐標(biāo)表示的數(shù)學(xué)形式。該算法極大地降低了計算射線-三角形交點(diǎn)的時間復(fù)雜度。

目前存在的更快的求解射線與三角形交點(diǎn)的方法大多從利用各式各樣的數(shù)據(jù)結(jié)構(gòu)來優(yōu)化的角度出發(fā)，比如基于空間劃分，將圖像空間遞歸的拆分為不同層次的樹結(jié)構(gòu)[2]，或是通過層次包圍，動態(tài)的計算包圍了三角邊頂點(diǎn)的最小矩形包圍盒[3]等。這些算法在提高計算效率的同時也大幅增加了內(nèi)存空間的開銷。

本文從純算法理論的角度出發(fā)，旨在減少單位時間內(nèi)基本運(yùn)算的次數(shù)。首先通過一次坐標(biāo)變換，將射線和三角形從全局坐標(biāo)系轉(zhuǎn)換到重心坐標(biāo)系中，再求解變化后的坐標(biāo)的交點(diǎn)。該算法所用到的計算步驟比MT算法更少，因此可以做到每次求解三角形與射線交點(diǎn)的速度都比MT算法更快。此外，該算法構(gòu)造變換的方式能夠確保其矩陣形式所使用的許多系數(shù)為此前被預(yù)計算出來的值，不需要做多余和額外的存儲，因此能夠使得預(yù)處理的內(nèi)存開銷最小化。

相較于其他算法，該算法具有良好的拓展性和應(yīng)用價值。對于已經(jīng)使用了MT算法實(shí)現(xiàn)的光線追蹤器或是光柵化渲染項(xiàng)目，不需要大幅調(diào)整自身的代碼結(jié)構(gòu)，而只需要將其中用MT算法求解光線與三角形交點(diǎn)的模塊替換為本文提供的算法就可以在得到相同圖像的同時大幅提高圖片渲染以及圖像生成的效率。對于使用數(shù)據(jù)結(jié)構(gòu)來加速計算光線與三角形交點(diǎn)的案例，該算法的思路依然可以部分應(yīng)用于其中，從而加速整個計算的過程。

1 數(shù)學(xué)定義

2 算法步驟

在三角形初始化的過程中，首先計算出定義1.3中提到的從全局坐標(biāo)系到重心坐標(biāo)系的轉(zhuǎn)換矩陣T，并將該矩陣作為三角形信息的一部分儲存下來。由于矩陣計算的過程會把該坐標(biāo)轉(zhuǎn)換為齊次坐標(biāo)系中進(jìn)行計算，根據(jù)齊次坐標(biāo)系的性質(zhì)，易知該矩陣第四行的值不參與相關(guān)涉及到變量的運(yùn)算，且它的值一定為( )0,0,0,1，故可以只儲存該矩陣前三行的內(nèi)容，從而節(jié)省了大量的內(nèi)存空間。

當(dāng)我們計算出了轉(zhuǎn)換矩陣T的值，則可以按照以下四個步驟得到坐標(biāo)的重心表示形式：

3 時間復(fù)雜度分析

根據(jù)MT算法的描述[1]，它至少需要進(jìn)行三次向量混合積的計算，而每次向量混合積的計算需要12次乘法運(yùn)算和5次加法運(yùn)算（此處暫時不考慮向量中有0的情況）。為了方便統(tǒng)計和比較效率，我們定義1次乘法運(yùn)算或1次加法運(yùn)算為1次元運(yùn)算。忽略MT算法中涉及到的標(biāo)量除法等耗時較少的計算，則MT算法至少需要進(jìn)行34次元運(yùn)算。

對于本文提出的方法，按照算法步驟中的4個步驟依次統(tǒng)計運(yùn)算次數(shù)：

(a)該步驟是一個4×4的矩陣左乘一個4× 1的列向量，由于該矩陣的第四行為(0 ,0,0,1)，列向量的第四行為1（齊次坐標(biāo)的性質(zhì)），展開化簡后可以得出需要的元計算為18次。

(b)該步驟為一個標(biāo)量除以一個標(biāo)量，由于除法可以看作是乘法的逆運(yùn)算，故需要元計算1次。

(c)該步驟需要2次標(biāo)量乘法和2次加法，合計元計算2次。

(d)該步驟為比較的過程，不計入運(yùn)算的步驟中。

將以上四個步驟需要的元計算次數(shù)進(jìn)行加總，得出本文提出的算法需要的元計算次數(shù)至少為23次，遠(yuǎn)小于MT算法需要的34次。

4 空間復(fù)雜度分析

由于MT算法不需要儲存額外的變量信息，因此不存在超出所有變量自身以外的內(nèi)存空間開銷。

本文提出的算法所需的額外內(nèi)存占用主要在于預(yù)處理時使用的轉(zhuǎn)換矩陣T。由于不需要考慮T矩陣第四行的值，所以單個三角形需要額外儲存的內(nèi)存為12個自由變量。同時，由于該矩陣只與三角形自身的性質(zhì)相關(guān)，而與射線的參數(shù)無關(guān)，因此該部分內(nèi)存可以在計算完所有需要和同一三角形相交的射線后釋放，總體上來說不會大幅增加內(nèi)存的消耗。

5 實(shí)際運(yùn)行結(jié)果

本文采取了兩種方式來比較該算法和通用的MT算法的性能：一是分別獨(dú)立實(shí)現(xiàn)兩種算法，用不同三角形數(shù)量的測試集各自進(jìn)行一輪測試；二是將該算法分別嵌入一個完整的光柵化項(xiàng)目和一個完整的光線追蹤器中，比較在實(shí)際項(xiàng)目中該算法和MT算法的效率。

實(shí)驗(yàn)表明，在這兩種情況下，本文提出的算法都比MT算法更快。

■5.1 獨(dú)立計時實(shí)驗(yàn)

此部分比較了本文提出算法的運(yùn)行時間和原始版本的MT算法的運(yùn)行時間，同時也比較了MT算法在sse4框架[4]下的一個改編版本：該框架經(jīng)過高度的調(diào)整，可以在現(xiàn)代CPU上快速的執(zhí)行MT算法。根據(jù)文獻(xiàn)[5]設(shè)計的測試程序，該程序能夠生成指定數(shù)量以及指定射線-三角形命中率（射線-三角形命中率指的是有射線能夠與之相交的三角形占總?cè)切蝹€數(shù)的比例）的射線和三角形的集合，其中每條射線都與至少一個三角形相交。該程序能夠進(jìn)行本文提出算法的12-自由元版本、9-自由元版本、原始的MT算法以及在sse4框架下的改編MT算法的比較。

在未經(jīng)特殊申明的情況下，本文涉及的所有實(shí)驗(yàn)皆在以下運(yùn)行環(huán)境運(yùn)行：CPU 2.8GHz Core i7-7700HQ，內(nèi)存16 GB of RAM，硬盤512 GB of SSD，操作系統(tǒng)Windows 10 2004 64位，IDE編譯優(yōu)化設(shè)置為-O3級別的Visual Studio 2019。

本文對上述涉及到的兩種算法進(jìn)行了輕微的修改，但是仍然盡可能地使其接近原始算法的意圖，以方便能用C++的形式進(jìn)行復(fù)現(xiàn)。由于當(dāng)前sse4框架下的MT算法還使用了SIMD功能以提升其并行性，本文在實(shí)現(xiàn)該算法時刪除了這一特性以保障一個平等的實(shí)驗(yàn)測試環(huán)境。值得一提的是，SIMD提供的并行特性并不與本文提出的算法排斥，因此將該部分功能添加到本文提出的算法中將是未來的研究方向之一。

表1展現(xiàn)了本次實(shí)驗(yàn)的結(jié)果。表格中展現(xiàn)的百分?jǐn)?shù)代表該算法在當(dāng)前實(shí)驗(yàn)環(huán)境下運(yùn)行所需的時間和MT算法在當(dāng)前實(shí)驗(yàn)環(huán)境下運(yùn)行所需時間的比例?？梢钥吹剑徽撊切螖?shù)和射線-三角形命中率如何變化，本文提出算法的12-自由元版本都穩(wěn)定的快于9-自由元的版本，而12-自由元的版本在所有實(shí)驗(yàn)條件下運(yùn)行時間均在MT算法的30%～50%之間。當(dāng)射線-三角形命中率僅為0.1時，12-自由元版本依然在運(yùn)行效率上略高于sse4框架下的MT算法，隨著射線-三角形命中率的增高，12-自由元的版本和sse4框架下的MT算法的效率差距逐漸拉大，在射線-三角形命中率高達(dá)0.9時，12-自由元的版本運(yùn)行時間約為sse4框架下的MT算法的50%左右。當(dāng)射線-三角形命中率為最低的0.1時，9-自由元的版本比sse4框架下的MT算法效率略低，但是隨著射線-三角形命中率增大到0.5和0.9，其運(yùn)行速度反超sse4框架下的MT算法，處在12-自由元的版本和sse4框架下的MT算法中間。

表1 不同數(shù)據(jù)集下三種算法和MT算法運(yùn)行效率對比

值得注意的是，對于每個三角形，sse4框架下的MT算法需要預(yù)先計算一個頂點(diǎn)、兩條邊和三角形的法線，總共需要48個字節(jié)的額外內(nèi)存開銷（假設(shè)所有數(shù)據(jù)為單精度浮點(diǎn)數(shù)），而9-自由元的版本僅需額外36個字節(jié)的內(nèi)存空間（假設(shè)所有數(shù)據(jù)為單精度浮點(diǎn)數(shù)）。

■5.2 在真實(shí)場景下的應(yīng)用

為了測試本文提出的算法在真實(shí)復(fù)雜場景下的正確性和有效性，該部分選取了兩個顯示效果明顯的渲染項(xiàng)目，其中一個項(xiàng)目由Blinn-Phong光照模型[6]在光柵化下實(shí)現(xiàn)，另一個項(xiàng)目則使用了一個初階版本的路徑追蹤器完成。

本次測試所做的工作僅僅為將這兩個項(xiàng)目中用MT算法求解射線-三角形交點(diǎn)的函數(shù)修改為本文提出的算法，其余部分未做任何改動。最終得到的結(jié)果如表2所示?？梢钥吹?，在真實(shí)場景下本文提出的算法在效率上的提升不如上一個實(shí)驗(yàn)顯著。原因在于在真實(shí)的渲染項(xiàng)目中，除了計算射線-三角形的交點(diǎn)以外，還有其他的函數(shù)消耗大量時間，比如模型的加載，計算光的反射，圖層的處理等。這兩個場景最終渲染生成的圖像如圖1和圖2所示。

表2 兩個場景下本文提出的算法和MT算法運(yùn)行效率對比

圖1 基于Blinn—Phong光照模型和光柵化渲染

圖2 基于路徑追蹤器渲染

6 結(jié)論

本文提出并測試了一種新型的計算射線-三角形交點(diǎn)的方法，它以對每個三角形進(jìn)行預(yù)處理和儲存少量的額外信息為代價，能夠快速的求解出射線與三角形的交點(diǎn)。儲存的額外信息并不會妨礙渲染工作的進(jìn)行，即使是在一些大型的渲染項(xiàng)目中，它依然可以穩(wěn)定并準(zhǔn)確的運(yùn)行。

該算法在效率上遠(yuǎn)遠(yuǎn)優(yōu)于通用的MT算法，并在一定條件下優(yōu)于MT算法的改進(jìn)版本。在完整的渲染工程中，本文提出的方法在獲得相同視覺效果的同時取得了比MT算法更快的結(jié)果。進(jìn)一步的工作可以考慮將本文提出的算法和前述所涉及到的數(shù)據(jù)結(jié)構(gòu)相結(jié)合，以期能夠得到時間復(fù)雜度更小的綜合實(shí)現(xiàn)方案。

文獻(xiàn)[5]指出，世界上并不存在一種最快的求解射線與三角形交點(diǎn)的方法，不同的算法在不同的運(yùn)行條件和數(shù)據(jù)集下各有優(yōu)劣。隨著圖形學(xué)和實(shí)時渲染技術(shù)的進(jìn)一步發(fā)展，對于在短時間獲取穩(wěn)定準(zhǔn)確圖像的需求不會減少。本文提出的算法正是在這樣的背景下進(jìn)行的一點(diǎn)思考，如果能夠該思路融入到一些已經(jīng)實(shí)現(xiàn)的光柵化項(xiàng)目和路徑追蹤器項(xiàng)目中，將很有希望能夠獲取更大的成果。