基于GPU的光線跟蹤算法加速結(jié)構(gòu)的比較與剖析：性能、特性與應(yīng)用一、引言1.1研究背景與意義在計(jì)算機(jī)圖形學(xué)領(lǐng)域，光線跟蹤算法作為生成真實(shí)感圖形的重要方法，一直占據(jù)著舉足輕重的地位。光線跟蹤通過模擬光線在場景中的傳播路徑以及與物體的交互過程，能夠精確地計(jì)算出光線的反射、折射、陰影和散射等效果，從而生成高度逼真的圖像。這種基于物理原理的渲染方式，使得光線跟蹤在電影、游戲、虛擬現(xiàn)實(shí)、建筑設(shè)計(jì)可視化等眾多領(lǐng)域得到了廣泛應(yīng)用。例如，在電影制作中，光線跟蹤技術(shù)可以為虛擬場景賦予更加真實(shí)的光影效果，增強(qiáng)畫面的視覺沖擊力；在游戲開發(fā)中，它能夠提升游戲畫面的質(zhì)量，為玩家?guī)砀映两降挠螒蝮w驗(yàn)。然而，傳統(tǒng)的光線跟蹤算法在計(jì)算速度上存在瓶頸。光線跟蹤算法需要對場景中的大量光線與物體進(jìn)行相交測試，計(jì)算量巨大，導(dǎo)致渲染一幅圖像往往需要耗費(fèi)大量的時(shí)間。這一缺陷嚴(yán)重限制了光線跟蹤算法在實(shí)時(shí)渲染等對計(jì)算速度要求較高的領(lǐng)域中的應(yīng)用。隨著計(jì)算機(jī)硬件技術(shù)的不斷發(fā)展，圖形處理器（GPU）以其強(qiáng)大的并行計(jì)算能力逐漸成為加速光線跟蹤算法的關(guān)鍵工具。GPU擁有成百上千個(gè)較小的核心，專門設(shè)計(jì)用于同時(shí)處理大量的并行任務(wù)，這種架構(gòu)特點(diǎn)使其在處理數(shù)據(jù)密集型和高度并行化的光線跟蹤計(jì)算時(shí)具有天然的優(yōu)勢。利用GPU加速光線跟蹤算法，可以同時(shí)追蹤成千上萬條光線，并快速處理大量的運(yùn)算需求，大大提高了光線跟蹤算法的執(zhí)行效率，使得光線跟蹤在實(shí)時(shí)渲染領(lǐng)域的應(yīng)用成為可能。在基于GPU的光線跟蹤算法中，加速結(jié)構(gòu)的選擇對于算法的性能提升起著至關(guān)重要的作用。不同的加速結(jié)構(gòu)，如均勻柵格、KD-Tree、包圍體層次（BVH）等，具有各自獨(dú)特的特點(diǎn)和適用場景。均勻柵格是最早在GPU上實(shí)現(xiàn)的加速結(jié)構(gòu)，它具有簡單高效的特點(diǎn)，通過簡單的算術(shù)運(yùn)算就能在常量時(shí)間內(nèi)定位和存取每個(gè)體素，體素遍歷可通過遞增算術(shù)運(yùn)算完成，且遍歷代碼適合向量編寫，與GPU指令集契合度高，但由于空間細(xì)分特性，可能導(dǎo)致對相同光線和三角形的多次相交測試。KD-Tree是一種空間細(xì)分結(jié)構(gòu)，利用二叉樹將場景表示成層次結(jié)構(gòu)，平均而言在基于CPU的光線跟蹤算法中表現(xiàn)較快，但在GPU上遍歷需要克服沒有堆棧結(jié)構(gòu)的問題。包圍體層次（BVH）通過計(jì)算遍歷包圍體層次的平均花費(fèi)來衡量其質(zhì)量，目前雖無構(gòu)建最優(yōu)BVH的算法，但在實(shí)踐中軸對齊包圍盒（AABB）因其易于實(shí)現(xiàn)和光線求交測試快而被廣泛應(yīng)用。對這些加速結(jié)構(gòu)進(jìn)行深入的比較研究，有助于我們根據(jù)不同的應(yīng)用場景和需求，選擇最合適的加速結(jié)構(gòu)，進(jìn)一步提升基于GPU的光線跟蹤算法的性能，從而推動(dòng)光線跟蹤技術(shù)在更多領(lǐng)域的應(yīng)用和發(fā)展。因此，開展基于GPU的光線跟蹤算法的加速結(jié)構(gòu)比較研究具有重要的理論意義和實(shí)際應(yīng)用價(jià)值。1.2國內(nèi)外研究現(xiàn)狀隨著計(jì)算機(jī)圖形學(xué)的發(fā)展，光線跟蹤算法在生成高質(zhì)量、真實(shí)感圖形方面展現(xiàn)出巨大潛力，基于GPU的光線跟蹤算法加速結(jié)構(gòu)成為了國內(nèi)外研究的重點(diǎn)領(lǐng)域。在國外，早期的研究主要集中在光線跟蹤算法本身的優(yōu)化和實(shí)現(xiàn)上。例如，Whitted在1979年提出了經(jīng)典的光線跟蹤算法，奠定了光線跟蹤技術(shù)的基礎(chǔ)，該算法通過遞歸地追蹤光線與場景中物體的交點(diǎn)，計(jì)算光線的反射、折射和陰影等效果，為后續(xù)的研究提供了重要的理論框架。隨著GPU技術(shù)的興起，Purcell等人率先將光線跟蹤算法移植到GPU上進(jìn)行實(shí)現(xiàn)，從光線的產(chǎn)生、加速結(jié)構(gòu)的遍歷到最后的著色過程都在GPU上執(zhí)行，開啟了基于GPU加速光線跟蹤算法的研究熱潮。此后，眾多學(xué)者針對不同的加速結(jié)構(gòu)展開了深入研究。在均勻柵格加速結(jié)構(gòu)方面，研究發(fā)現(xiàn)其在GPU上具有獨(dú)特的優(yōu)勢，如簡單的算術(shù)運(yùn)算即可實(shí)現(xiàn)體素的定位和存取，體素遍歷通過遞增算術(shù)運(yùn)算完成，且遍歷代碼適合向量編寫，與GPU指令集契合度高。然而，其缺點(diǎn)也較為明顯，由于空間細(xì)分特性，可能導(dǎo)致對相同光線和三角形的多次相交測試。針對KD-Tree加速結(jié)構(gòu)，雖然在基于CPU的光線跟蹤算法中表現(xiàn)出色，但在GPU上應(yīng)用時(shí)，由于GPU沒有堆棧結(jié)構(gòu)，需要采用特殊的遍歷策略，如通過記住光線前進(jìn)的距離來向上或向下遍歷樹，以克服這一限制。對于包圍體層次（BVH）加速結(jié)構(gòu)，研究重點(diǎn)在于如何構(gòu)建高質(zhì)量的BVH。目前雖無構(gòu)建最優(yōu)BVH的算法，但goldsmith和salmon提出的表面積啟發(fā)式函數(shù)為衡量BVH質(zhì)量提供了重要的評價(jià)方法，在實(shí)踐中，軸對齊包圍盒（AABB）因其易于實(shí)現(xiàn)和光線求交測試快而被廣泛應(yīng)用于BVH的構(gòu)建。此外，NVIDIA的RTX技術(shù)利用GPU中的RT核心進(jìn)行實(shí)時(shí)光線追蹤渲染，實(shí)現(xiàn)了前所未有的逼真光照和反射效果，推動(dòng)了光線跟蹤技術(shù)在游戲和視覺效果產(chǎn)業(yè)中的應(yīng)用。國內(nèi)的研究也緊跟國際步伐，在基于GPU的光線跟蹤算法加速結(jié)構(gòu)方面取得了不少成果。學(xué)者們在深入研究國外先進(jìn)技術(shù)的基礎(chǔ)上，結(jié)合國內(nèi)的實(shí)際需求和應(yīng)用場景，進(jìn)行了一系列創(chuàng)新和改進(jìn)。一些研究針對大規(guī)模場景下GPU顯存不足的問題，提出了有效的優(yōu)化策略，如采用數(shù)據(jù)壓縮、分塊加載等技術(shù)，以減少顯存的占用，提高光線跟蹤算法在大規(guī)模場景下的運(yùn)行效率。在算法優(yōu)化方面，通過改進(jìn)光線與加速結(jié)構(gòu)的相交測試算法，以及利用并行計(jì)算技術(shù)進(jìn)一步提高算法的并行度，從而提升光線跟蹤算法的整體性能。同時(shí)，國內(nèi)的研究也注重將光線跟蹤技術(shù)應(yīng)用于實(shí)際領(lǐng)域，如建筑設(shè)計(jì)可視化、虛擬現(xiàn)實(shí)等，通過與這些領(lǐng)域的深度融合，推動(dòng)光線跟蹤技術(shù)的實(shí)際應(yīng)用和發(fā)展。盡管國內(nèi)外在基于GPU的光線跟蹤算法加速結(jié)構(gòu)研究方面取得了顯著進(jìn)展，但仍存在一些不足之處。一方面，不同加速結(jié)構(gòu)在不同場景下的性能表現(xiàn)還需要更深入的對比和分析，目前的研究大多針對特定場景進(jìn)行測試，缺乏全面、系統(tǒng)的比較研究。另一方面，對于如何進(jìn)一步提高加速結(jié)構(gòu)的構(gòu)建效率和質(zhì)量，以及如何更好地利用GPU的硬件特性來優(yōu)化光線跟蹤算法，仍然是研究的難點(diǎn)和熱點(diǎn)問題。此外，在光線跟蹤算法與其他技術(shù)的融合方面，如與深度學(xué)習(xí)、人工智能等技術(shù)的結(jié)合，雖然有一些初步的探索，但還需要更深入的研究和實(shí)踐，以挖掘更多的應(yīng)用潛力。這些不足和空白為本文的研究提供了方向和空間。1.3研究內(nèi)容與方法本文主要對基于GPU的光線跟蹤算法中的均勻柵格、KD-Tree、包圍體層次（BVH）這三種典型加速結(jié)構(gòu)展開深入的比較研究。在研究過程中，綜合運(yùn)用多種研究方法，從理論分析、實(shí)驗(yàn)對比等多個(gè)角度，全面剖析這三種加速結(jié)構(gòu)的性能特點(diǎn)和適用場景。理論分析方面，深入探究均勻柵格、KD-Tree、包圍體層次（BVH）這三種加速結(jié)構(gòu)的原理和特點(diǎn)。對于均勻柵格，詳細(xì)分析其在GPU上實(shí)現(xiàn)的優(yōu)勢，如通過簡單算術(shù)運(yùn)算就能在常量時(shí)間內(nèi)定位和存取體素，體素遍歷通過遞增算術(shù)運(yùn)算完成，且遍歷代碼適合向量編寫，與GPU指令集契合度高；同時(shí)，也分析其缺點(diǎn)，如由于空間細(xì)分特性，可能導(dǎo)致對相同光線和三角形的多次相交測試。對于KD-Tree，研究其作為空間細(xì)分結(jié)構(gòu)，利用二叉樹將場景表示成層次結(jié)構(gòu)的原理，以及在GPU上遍歷需要克服沒有堆棧結(jié)構(gòu)的問題，通過記住光線前進(jìn)的距離來向上或向下遍歷樹的策略。對于包圍體層次（BVH），重點(diǎn)研究其通過計(jì)算遍歷包圍體層次的平均花費(fèi)來衡量質(zhì)量的方法，以及goldsmith和salmon提出的表面積啟發(fā)式函數(shù)在評價(jià)BVH質(zhì)量中的應(yīng)用，同時(shí)分析軸對齊包圍盒（AABB）在BVH構(gòu)建中因其易于實(shí)現(xiàn)和光線求交測試快而被廣泛應(yīng)用的原因。通過理論分析，明確三種加速結(jié)構(gòu)的工作機(jī)制和內(nèi)在特性，為后續(xù)的實(shí)驗(yàn)對比提供理論基礎(chǔ)。實(shí)驗(yàn)對比是本研究的重要方法之一。搭建基于GPU的光線跟蹤實(shí)驗(yàn)平臺，采用CUDA并行計(jì)算平臺進(jìn)行編程實(shí)現(xiàn)。在實(shí)驗(yàn)過程中，選擇具有代表性的不同類型場景，如包含復(fù)雜幾何形狀的工業(yè)模型場景、具有豐富材質(zhì)和光照效果的室內(nèi)場景、大規(guī)模的自然景觀場景等，對基于均勻柵格、KD-Tree、BVH加速結(jié)構(gòu)的光線跟蹤算法進(jìn)行性能測試。測試指標(biāo)包括光線與物體的相交測試時(shí)間、渲染圖像所需的總時(shí)間、內(nèi)存占用情況等。通過對這些指標(biāo)的對比分析，直觀地展示不同加速結(jié)構(gòu)在不同場景下的性能表現(xiàn)。例如，在復(fù)雜幾何形狀的工業(yè)模型場景中，對比三種加速結(jié)構(gòu)在處理大量細(xì)小幾何部件時(shí)的相交測試效率；在具有豐富材質(zhì)和光照效果的室內(nèi)場景中，考察它們對光線反射、折射等復(fù)雜光照計(jì)算的加速效果；在大規(guī)模的自然景觀場景中，評估它們在處理大規(guī)模數(shù)據(jù)時(shí)的內(nèi)存管理能力和渲染速度。通過多場景、多指標(biāo)的實(shí)驗(yàn)對比，全面、客觀地比較三種加速結(jié)構(gòu)的性能差異，為實(shí)際應(yīng)用中的選擇提供有力的實(shí)驗(yàn)依據(jù)。二、光線跟蹤算法與GPU基礎(chǔ)2.1光線跟蹤算法原理光線跟蹤算法是一種基于物理光學(xué)原理的渲染方法，通過模擬光線在場景中的傳播路徑以及與物體的交互過程，來計(jì)算圖像中每個(gè)像素的顏色，從而生成高度逼真的圖像。其基本原理包括光線生成、光線與物體相交測試以及顏色計(jì)算與遞歸追蹤三個(gè)主要步驟。2.1.1光線生成光線生成是光線跟蹤算法的起始步驟，其核心任務(wù)是從視點(diǎn)出發(fā)，通過圖像平面上的像素位置發(fā)射光線。在這一過程中，需要精確確定光線的方向和起始點(diǎn)。假設(shè)視點(diǎn)坐標(biāo)為E(x_E,y_E,z_E)，圖像平面上某像素的坐標(biāo)為P(x_P,y_P,z_P)，則光線的方向向量\vecz3jilz61osys可通過\vecz3jilz61osys=\frac{P-E}{\vertP-E\vert}計(jì)算得出，該向量表示了光線傳播的方向，其模長為1，保證了方向的準(zhǔn)確性。光線的起始點(diǎn)即為視點(diǎn)E，這樣就確定了一條從視點(diǎn)出發(fā)，經(jīng)過像素P的光線。不同的光線生成策略對后續(xù)計(jì)算有著顯著影響。例如，均勻采樣策略是在圖像平面上均勻地選取像素位置發(fā)射光線，這種策略簡單直觀，易于實(shí)現(xiàn)，在簡單場景下能夠快速生成圖像，但對于復(fù)雜場景，可能會導(dǎo)致圖像出現(xiàn)鋸齒、模糊等問題，因?yàn)樗鼪]有考慮到場景中物體的分布和光線的復(fù)雜傳播情況。自適應(yīng)采樣策略則根據(jù)場景的復(fù)雜度和光線的變化情況，動(dòng)態(tài)調(diào)整采樣點(diǎn)的分布，在物體邊緣、光照變化劇烈等區(qū)域增加采樣點(diǎn)密度，以提高圖像的細(xì)節(jié)和準(zhǔn)確性；而在相對平坦、光線變化較小的區(qū)域減少采樣點(diǎn)，從而在保證圖像質(zhì)量的前提下降低計(jì)算量。這種策略能夠更好地適應(yīng)復(fù)雜場景，但實(shí)現(xiàn)難度較大，需要更多的計(jì)算資源來判斷場景的復(fù)雜度和光線的變化情況。分層采樣策略將圖像平面劃分為多個(gè)層次，從粗到細(xì)逐步進(jìn)行采樣，首先在較低層次進(jìn)行粗采樣，快速生成大致的圖像輪廓，然后根據(jù)需要在較高層次對細(xì)節(jié)部分進(jìn)行細(xì)采樣，進(jìn)一步提高圖像質(zhì)量。這種策略結(jié)合了均勻采樣和自適應(yīng)采樣的優(yōu)點(diǎn)，在保證圖像質(zhì)量的同時(shí)，也在一定程度上控制了計(jì)算量，但需要合理設(shè)置層次和采樣點(diǎn)的分布，以達(dá)到最佳的效果。2.1.2光線與物體相交測試光線與物體相交測試是光線跟蹤算法的關(guān)鍵環(huán)節(jié)，其目的是判斷光線是否與場景中的物體相交，并精確計(jì)算出相交點(diǎn)的信息。對于常見的幾何物體，如球體、平面等，有相應(yīng)的數(shù)學(xué)方法來進(jìn)行相交測試。以球體為例，假設(shè)球體的球心坐標(biāo)為C(x_C,y_C,z_C)，半徑為r，光線的參數(shù)方程為P(t)=E+t\vecz3jilz61osys（其中t為參數(shù)）。將光線方程代入球體方程(x-x_C)^2+(y-y_C)^2+(z-z_C)^2=r^2，得到一個(gè)關(guān)于t的二次方程at^2+bt+c=0，其中a=\vecz3jilz61osys\cdot\vecz3jilz61osys，b=2\vecz3jilz61osys\cdot(E-C)，c=(E-C)\cdot(E-C)-r^2。通過求解這個(gè)二次方程，若存在實(shí)數(shù)解t_1和t_2（t_1\leqt_2），則表示光線與球體相交，相交點(diǎn)可通過將t_1或t_2代入光線方程得到。當(dāng)t_1\gt0時(shí)，t_1對應(yīng)的交點(diǎn)為光線首次與球體相交的點(diǎn)；當(dāng)t_1\leq0且t_2\gt0時(shí)，t_2對應(yīng)的交點(diǎn)為首次相交點(diǎn)；若方程無實(shí)數(shù)解，則表示光線與球體不相交。對于復(fù)雜的幾何體，如多面體等，基于邊界體的相交算法更為適用。該算法的核心思想是將物體分解為若干個(gè)邊界體，通常采用包圍盒的形式，如軸對齊包圍盒（AABB）。AABB是一個(gè)與坐標(biāo)軸對齊的長方體，通過記錄物體在x、y、z三個(gè)方向上的最小和最大值，來確定包圍盒的范圍。在進(jìn)行相交測試時(shí)，首先判斷光線是否與物體的包圍盒相交，若不相交，則光線與物體必然不相交，從而避免了對物體內(nèi)部復(fù)雜幾何形狀的相交測試，大大減少了計(jì)算量；若光線與包圍盒相交，則進(jìn)一步對物體內(nèi)部的幾何形狀進(jìn)行相交測試，以確定光線是否與物體真正相交。為了提高相交測試的效率，可采用多種技術(shù)和策略。使用加速數(shù)據(jù)結(jié)構(gòu)是一種有效的方法，如包圍體層次（BVH）結(jié)構(gòu)。BVH通過構(gòu)建層次化的包圍體樹，將場景中的物體組織起來，使得光線在與物體相交測試時(shí)，能夠先與層次結(jié)構(gòu)中的包圍體進(jìn)行快速相交測試。如果光線與某個(gè)包圍體不相交，則可以直接跳過該包圍體所包含的所有物體，從而減少相交測試的次數(shù)。例如，在一個(gè)包含大量三角形的復(fù)雜場景中，BVH可以將這些三角形分組，用較大的包圍體包圍一組三角形，然后再將這些大包圍體進(jìn)一步分組，形成更高層次的包圍體，以此類推，構(gòu)建出一個(gè)樹形結(jié)構(gòu)。當(dāng)光線進(jìn)行相交測試時(shí)，從根節(jié)點(diǎn)開始，依次與各級包圍體進(jìn)行測試，快速排除不相交的部分，大大提高了相交測試的效率。合理設(shè)置相交測試的精度也能提高效率。根據(jù)場景的需求，在保證圖像質(zhì)量的前提下，可以適當(dāng)降低相交測試的精度，減少不必要的計(jì)算。在一些對實(shí)時(shí)性要求較高的應(yīng)用中，如實(shí)時(shí)游戲場景，適當(dāng)降低精度可以在不明顯影響圖像質(zhì)量的情況下，顯著提高算法的運(yùn)行速度。利用并行計(jì)算和硬件加速技術(shù)也是提高相交測試效率的重要途徑。GPU具有強(qiáng)大的并行計(jì)算能力，能夠同時(shí)處理大量的光線與物體相交測試任務(wù)。通過將相交測試任務(wù)分配到GPU的多個(gè)核心上并行執(zhí)行，可以大大縮短計(jì)算時(shí)間。NVIDIA的RTX技術(shù)利用GPU中的RT核心進(jìn)行光線追蹤渲染，能夠快速處理光線與物體的相交測試，實(shí)現(xiàn)了實(shí)時(shí)光線追蹤效果。2.1.3顏色計(jì)算與遞歸追蹤在確定光線與物體的相交點(diǎn)后，需要根據(jù)物體的材質(zhì)屬性和光源信息來計(jì)算該點(diǎn)的顏色。這一過程涉及到多種光照模型，以模擬不同的光照效果。常見的光照模型包括環(huán)境光、漫反射和鏡面反射等。環(huán)境光是場景中均勻分布的光，通常用于模擬光的散射，它不依賴于光源的方向，對場景中的所有物體都產(chǎn)生相同的光照影響。環(huán)境光的強(qiáng)度通常是一個(gè)常量，與物體的材質(zhì)屬性中的環(huán)境反射系數(shù)相乘，得到物體表面受到的環(huán)境光光照強(qiáng)度。漫反射是光線與表面相互作用的結(jié)果，表面在各個(gè)方向上均勻反射光線，其強(qiáng)度與光源的強(qiáng)度、表面法線和光源方向的夾角有關(guān)，遵循朗伯定律。假設(shè)光源強(qiáng)度為I_s，表面法線為\vec{n}，光源方向?yàn)閈vec{l}，漫反射系數(shù)為k_d，則漫反射光照強(qiáng)度I_d=k_dI_s\max(0,\vec{n}\cdot\vec{l})。鏡面反射模擬光線在光滑表面上的反射，通常與觀察者的視角有關(guān)，其強(qiáng)度與光源方向、表面法線和視線方向之間的夾角有關(guān)。設(shè)鏡面反射系數(shù)為k_s，視線方向?yàn)閈vec{v}，反射方向?yàn)閈vec{r}，光澤度為n，則鏡面反射光照強(qiáng)度I_s=k_sI_s(\vec{v}\cdot\vec{r})^n。通過將環(huán)境光、漫反射和鏡面反射等光照強(qiáng)度相加，再結(jié)合物體的顏色屬性，即可計(jì)算出相交點(diǎn)的顏色。遞歸追蹤在模擬光線反射、折射中起著關(guān)鍵作用。當(dāng)光線與物體表面相交時(shí)，如果物體表面具有反射或折射屬性，則需要從相交點(diǎn)處生成新的光線，并對新光線繼續(xù)進(jìn)行光線跟蹤。對于反射光線，其方向可根據(jù)反射定律計(jì)算得出。設(shè)入射光線方向?yàn)閈vecz3jilz61osys，表面法線為\vec{n}，則反射光線方向\vec{r}=\vecz3jilz61osys-2(\vecz3jilz61osys\cdot\vec{n})\vec{n}。從相交點(diǎn)出發(fā)，沿著反射光線方向發(fā)射新的光線，繼續(xù)進(jìn)行光線與物體的相交測試和顏色計(jì)算，遞歸地計(jì)算反射光線對相交點(diǎn)顏色的貢獻(xiàn)。對于折射光線，其方向可根據(jù)折射定律（斯涅爾定律）計(jì)算。設(shè)入射光線在介質(zhì)1中的折射率為n_1，折射光線在介質(zhì)2中的折射率為n_2，入射角為\theta_1，折射角為\theta_2，則根據(jù)斯涅爾定律n_1\sin\theta_1=n_2\sin\theta_2，可計(jì)算出折射光線的方向。從相交點(diǎn)出發(fā)，沿著折射光線方向發(fā)射新的光線，同樣進(jìn)行光線與物體的相交測試和顏色計(jì)算，遞歸地計(jì)算折射光線對相交點(diǎn)顏色的貢獻(xiàn)。遞歸追蹤的過程會持續(xù)進(jìn)行，直到滿足一定的終止條件，如光線與環(huán)境中任何物體均不相交，或被跟蹤光線返回的光亮度值對像素顏色的貢獻(xiàn)很小，或已遞歸到給定深度。通過遞歸追蹤，可以真實(shí)地模擬光線在場景中的多次反射和折射，從而生成更加逼真的圖像效果。在一個(gè)包含多個(gè)鏡面物體和透明物體的場景中，遞歸追蹤能夠準(zhǔn)確地模擬光線在這些物體之間的傳播和交互，使得最終生成的圖像能夠呈現(xiàn)出真實(shí)的反射和折射效果，如鏡子中的影像、透過玻璃看到的物體等。2.2GPU架構(gòu)與并行計(jì)算2.2.1GPU硬件架構(gòu)特點(diǎn)GPU的硬件架構(gòu)具有獨(dú)特的設(shè)計(jì)，旨在滿足大規(guī)模并行計(jì)算的需求。其核心數(shù)量眾多，以NVIDIA的GPU為例，如RTX3090，擁有高達(dá)10496個(gè)CUDA核心，這些核心能夠同時(shí)處理大量的并行任務(wù)。在內(nèi)存結(jié)構(gòu)方面，GPU通常包含多種類型的內(nèi)存，以支持高效的數(shù)據(jù)訪問和處理。GPU擁有較大容量的全局內(nèi)存，類似于CPU的系統(tǒng)內(nèi)存，用于存儲程序運(yùn)行所需的大量數(shù)據(jù)，如場景中的物體模型、紋理信息等。在光線跟蹤算法中，場景中的三角形網(wǎng)格數(shù)據(jù)就存儲在全局內(nèi)存中，光線與物體的相交測試需要頻繁訪問這些數(shù)據(jù)。然而，全局內(nèi)存的訪問速度相對較慢，存在一定的延遲。為了彌補(bǔ)這一不足，GPU配備了共享內(nèi)存，其位于每個(gè)流式多處理器（SM）內(nèi)，與CUDA核心緊密相連。共享內(nèi)存的訪問速度比全局內(nèi)存快得多，能夠?qū)崿F(xiàn)數(shù)據(jù)在同一SM內(nèi)不同CUDA核心之間的快速共享和交換。在光線跟蹤中，當(dāng)多個(gè)CUDA核心處理同一條光線與一組三角形的相交測試時(shí)，可以將這些三角形的數(shù)據(jù)預(yù)先加載到共享內(nèi)存中，避免了多次從全局內(nèi)存讀取數(shù)據(jù)，從而提高了計(jì)算效率。GPU還具備高速緩存（Cache），如L1緩存和L2緩存。L1緩存位于每個(gè)SM內(nèi)，用于存儲最近訪問的數(shù)據(jù)和指令，進(jìn)一步提高數(shù)據(jù)訪問速度；L2緩存則是整個(gè)GPU芯片共享的緩存，用于存儲更廣泛的數(shù)據(jù)。在光線跟蹤算法執(zhí)行過程中，經(jīng)常訪問的光線數(shù)據(jù)、材質(zhì)屬性數(shù)據(jù)等可以存儲在緩存中，當(dāng)需要再次訪問時(shí)，能夠快速從緩存中獲取，減少了對內(nèi)存的訪問次數(shù)，提高了算法的執(zhí)行速度。GPU的內(nèi)存帶寬也非常重要，它決定了數(shù)據(jù)在內(nèi)存和計(jì)算核心之間傳輸?shù)乃俣取８邇?nèi)存帶寬能夠確保大量數(shù)據(jù)快速傳輸?shù)接?jì)算核心進(jìn)行處理，從而充分發(fā)揮GPU的并行計(jì)算能力。在光線跟蹤中，大量的光線與物體相交測試結(jié)果需要及時(shí)傳輸回內(nèi)存進(jìn)行存儲和后續(xù)處理，高內(nèi)存帶寬能夠保證這一過程的高效進(jìn)行。2.2.2GPU并行計(jì)算模型CUDA（ComputeUnifiedDeviceArchitecture）是NVIDIA推出的一種并行計(jì)算平臺和編程模型，被廣泛應(yīng)用于GPU并行計(jì)算領(lǐng)域。在CUDA編程模型中，程序被劃分為主機(jī)代碼和設(shè)備代碼。主機(jī)代碼在CPU上執(zhí)行，主要負(fù)責(zé)管理和控制整個(gè)程序的流程，包括分配和釋放內(nèi)存、調(diào)用設(shè)備代碼等；設(shè)備代碼則在GPU上執(zhí)行，用于處理大規(guī)模的并行計(jì)算任務(wù)。在光線跟蹤算法的實(shí)現(xiàn)中，主機(jī)代碼負(fù)責(zé)讀取場景數(shù)據(jù)、初始化光線跟蹤參數(shù)等，而設(shè)備代碼則負(fù)責(zé)執(zhí)行光線生成、光線與物體相交測試、顏色計(jì)算等核心計(jì)算任務(wù)。CUDA編程模型引入了線程層次結(jié)構(gòu)的概念，將線程組織成網(wǎng)格（Grid）、線程塊（Block）和線程（Thread）。一個(gè)網(wǎng)格由多個(gè)線程塊組成，每個(gè)線程塊又包含多個(gè)線程。線程塊內(nèi)的線程可以通過共享內(nèi)存進(jìn)行高效的數(shù)據(jù)共享和同步，不同線程塊之間的線程則相對獨(dú)立。在光線跟蹤中，每個(gè)線程可以負(fù)責(zé)處理一條光線的跟蹤計(jì)算，將多條光線的計(jì)算任務(wù)分配到不同的線程中并行執(zhí)行。通過合理劃分線程塊和網(wǎng)格的大小，可以充分利用GPU的并行計(jì)算資源，提高光線跟蹤算法的執(zhí)行效率。例如，在處理一個(gè)包含大量光線的場景時(shí)，可以將光線分組，每組光線對應(yīng)一個(gè)線程塊，每個(gè)線程塊內(nèi)的線程分別處理一條光線，從而實(shí)現(xiàn)大規(guī)模光線的并行處理。CUDA還提供了豐富的庫和工具，如CUDA數(shù)學(xué)庫（CUDAMathLibrary）、CUDA庫（CUDALibrary）等，這些庫和工具能夠幫助開發(fā)者更方便地實(shí)現(xiàn)復(fù)雜的計(jì)算任務(wù)，進(jìn)一步提高開發(fā)效率和程序性能。在光線跟蹤算法中，可以利用CUDA數(shù)學(xué)庫中的函數(shù)進(jìn)行向量運(yùn)算、矩陣運(yùn)算等，這些函數(shù)經(jīng)過優(yōu)化，能夠在GPU上高效執(zhí)行，從而加速光線與物體相交測試中的數(shù)學(xué)計(jì)算過程。與傳統(tǒng)的CPU計(jì)算相比，GPU并行計(jì)算在處理大規(guī)模數(shù)據(jù)和高度并行化的任務(wù)時(shí)具有顯著優(yōu)勢。由于GPU擁有大量的計(jì)算核心，能夠同時(shí)執(zhí)行多個(gè)線程的計(jì)算任務(wù)，因此可以在短時(shí)間內(nèi)完成大量的計(jì)算工作。在光線跟蹤算法中，GPU并行計(jì)算能夠同時(shí)處理成千上萬條光線的跟蹤計(jì)算，大大縮短了渲染時(shí)間，使得實(shí)時(shí)或近實(shí)時(shí)的光線跟蹤渲染成為可能，而傳統(tǒng)的CPU計(jì)算方式在處理如此大規(guī)模的計(jì)算任務(wù)時(shí)，往往需要耗費(fèi)大量的時(shí)間。2.2.3GPU在光線跟蹤算法中的加速機(jī)制GPU在光線跟蹤算法中能夠?qū)崿F(xiàn)高效加速，主要依賴于其強(qiáng)大的并行處理能力和獨(dú)特的內(nèi)存管理機(jī)制。在并行處理光線方面，GPU利用其大量的計(jì)算核心，將光線跟蹤任務(wù)分解為多個(gè)子任務(wù)，分配給不同的核心同時(shí)進(jìn)行處理。由于光線之間的計(jì)算相互獨(dú)立，非常適合并行計(jì)算。在渲染一個(gè)復(fù)雜的室內(nèi)場景時(shí)，需要跟蹤成千上萬條光線來計(jì)算每個(gè)像素的顏色。GPU可以將這些光線分配到不同的CUDA核心上，每個(gè)核心負(fù)責(zé)跟蹤一條或多條光線，從而大大提高了光線跟蹤的速度。通過并行處理，GPU能夠在短時(shí)間內(nèi)完成大量光線的計(jì)算，顯著縮短了光線跟蹤算法的運(yùn)行時(shí)間。GPU的共享內(nèi)存機(jī)制在光線跟蹤算法中也發(fā)揮著重要作用。共享內(nèi)存位于GPU的流式多處理器（SM）內(nèi)，具有高速訪問的特點(diǎn)。在光線跟蹤過程中，當(dāng)多個(gè)線程處理同一條光線與場景中物體的相交測試時(shí)，可以將相關(guān)的物體數(shù)據(jù)（如三角形網(wǎng)格數(shù)據(jù)）預(yù)先加載到共享內(nèi)存中。這樣，線程在進(jìn)行相交測試時(shí)，可以直接從共享內(nèi)存中讀取數(shù)據(jù)，避免了頻繁地從全局內(nèi)存中讀取，減少了內(nèi)存訪問延遲，提高了計(jì)算效率。在處理一個(gè)包含多個(gè)三角形的物體時(shí)，多個(gè)線程需要訪問這些三角形的頂點(diǎn)坐標(biāo)、法線等數(shù)據(jù)進(jìn)行相交測試。通過將這些數(shù)據(jù)加載到共享內(nèi)存中，線程可以快速獲取所需數(shù)據(jù)，同時(shí)避免了重復(fù)讀取，提高了數(shù)據(jù)訪問的效率。GPU還采用了優(yōu)化的內(nèi)存訪問模式和數(shù)據(jù)傳輸策略。在光線跟蹤算法中，數(shù)據(jù)的訪問和傳輸對性能影響很大。GPU通過合并內(nèi)存訪問（MemoryCoalescing）等技術(shù)，將多個(gè)線程對內(nèi)存的訪問合并為一次或少數(shù)幾次訪問，減少了內(nèi)存訪問的次數(shù)，提高了內(nèi)存帶寬的利用率。在處理光線與物體相交測試時(shí)，多個(gè)線程可能需要訪問相鄰的內(nèi)存區(qū)域來獲取物體數(shù)據(jù)，GPU可以將這些訪問合并，以提高內(nèi)存訪問效率。GPU還優(yōu)化了數(shù)據(jù)在主機(jī)內(nèi)存和設(shè)備內(nèi)存之間的傳輸過程，采用異步傳輸?shù)确绞?，使得?shù)據(jù)傳輸與計(jì)算過程可以重疊進(jìn)行，進(jìn)一步提高了整體性能。在光線跟蹤算法執(zhí)行前，將場景數(shù)據(jù)從主機(jī)內(nèi)存?zhèn)鬏數(shù)紾PU設(shè)備內(nèi)存時(shí)，可以采用異步傳輸方式，在數(shù)據(jù)傳輸?shù)耐瑫r(shí)，GPU可以開始執(zhí)行其他計(jì)算任務(wù)，從而提高了系統(tǒng)的效率。三、常見加速結(jié)構(gòu)分析3.1均勻柵格3.1.1結(jié)構(gòu)原理與構(gòu)建均勻柵格是一種簡單直觀的空間劃分加速結(jié)構(gòu)，其原理是將三維空間均勻地劃分為大小相等的體素（Voxel），類似于將一個(gè)巨大的三維長方體蛋糕切割成無數(shù)個(gè)大小相同的小立方體塊，每個(gè)小立方體塊就是一個(gè)體素。這些體素在空間中緊密排列，形成一個(gè)規(guī)則的網(wǎng)格狀結(jié)構(gòu)。在光線跟蹤算法中，場景中的物體被分配到與其相交的體素中。例如，一個(gè)球體可能會與多個(gè)體素相交，那么這些體素都會記錄該球體的相關(guān)信息。構(gòu)建均勻柵格的過程主要包括以下幾個(gè)關(guān)鍵步驟。需要確定柵格的分辨率，即每個(gè)維度上體素的數(shù)量。分辨率的選擇直接影響到均勻柵格的性能和內(nèi)存占用。如果分辨率過高，體素?cái)?shù)量會急劇增加，導(dǎo)致內(nèi)存占用過大，同時(shí)也會增加構(gòu)建和遍歷的時(shí)間；如果分辨率過低，可能無法準(zhǔn)確地表示場景中的物體，導(dǎo)致光線與物體的相交測試不準(zhǔn)確。在一個(gè)簡單的室內(nèi)場景中，若選擇較低的分辨率，可能會將一些小型家具或裝飾品忽略，從而影響光線跟蹤的準(zhǔn)確性。通常需要根據(jù)場景的復(fù)雜程度和硬件資源來合理確定分辨率。可以通過對場景中物體的分布和大小進(jìn)行初步分析，預(yù)估合適的分辨率范圍，然后通過實(shí)驗(yàn)進(jìn)行調(diào)整和優(yōu)化。確定分辨率后，對場景進(jìn)行空間劃分。以三維空間為例，假設(shè)場景的邊界范圍在x方向上為[x_{min},x_{max}]，y方向上為[y_{min},y_{max}]，z方向上為[z_{min},z_{max}]，且在x、y、z方向上分別劃分n_x、n_y、n_z個(gè)體素。則每個(gè)體素在x方向上的大小\Deltax=\frac{x_{max}-x_{min}}{n_x}，在y方向上的大小\Deltay=\frac{y_{max}-y_{min}}{n_y}，在z方向上的大小\Deltaz=\frac{z_{max}-z_{min}}{n_z}。通過這樣的計(jì)算，將場景空間劃分為一個(gè)個(gè)大小相等的體素。將場景中的物體分配到相應(yīng)的體素中。對于每個(gè)物體，通過計(jì)算其幾何形狀與各個(gè)體素的相交關(guān)系，確定該物體屬于哪些體素。對于一個(gè)三角形面片，需要判斷它與哪些體素相交，若相交，則將該三角形的相關(guān)信息（如頂點(diǎn)坐標(biāo)、材質(zhì)屬性等）存儲到這些體素中。在實(shí)際實(shí)現(xiàn)中，可以采用多種算法來提高物體分配的效率，如掃描線算法、包圍盒算法等。掃描線算法通過在某一方向上掃描物體，快速確定物體與體素的相交情況；包圍盒算法則先為物體構(gòu)建包圍盒，通過判斷包圍盒與體素的相交關(guān)系，初步篩選出可能與物體相交的體素，再進(jìn)行精確的相交測試。3.1.2光線遍歷策略在均勻柵格中，光線的遍歷采用了一種基于增量計(jì)算的高效策略。當(dāng)光線進(jìn)入均勻柵格時(shí)，首先需要確定光線進(jìn)入的第一個(gè)體素。這可以通過將光線的起點(diǎn)坐標(biāo)與柵格的原點(diǎn)坐標(biāo)進(jìn)行比較，并結(jié)合體素的大小來計(jì)算得出。假設(shè)光線的起點(diǎn)坐標(biāo)為(x_0,y_0,z_0)，柵格的原點(diǎn)坐標(biāo)為(x_{grid\_min},y_{grid\_min},z_{grid\_min})，體素在x、y、z方向上的大小分別為\Deltax、\Deltay、\Deltaz，則光線進(jìn)入的第一個(gè)體素在x方向上的索引i_x=\lfloor\frac{x_0-x_{grid\_min}}{\Deltax}\rfloor，在y方向上的索引i_y=\lfloor\frac{y_0-y_{grid\_min}}{\Deltay}\rfloor，在z方向上的索引i_z=\lfloor\frac{y_0-y_{grid\_min}}{\Deltaz}\rfloor，其中\(zhòng)lfloor\cdot\rfloor表示向下取整操作。確定起始體素后，光線按照一定的順序依次遍歷相鄰的體素。在三維空間中，光線從當(dāng)前體素移動(dòng)到下一個(gè)體素時(shí)，有多個(gè)可能的方向。為了高效地遍歷體素，通常采用DDA（DigitalDifferentialAnalyzer）算法的思想，通過計(jì)算光線在各個(gè)方向上的增量，來確定下一個(gè)要遍歷的體素。假設(shè)光線的方向向量為(d_x,d_y,d_z)，且\vertd_x\vert\geq\vertd_y\vert\geq\vertd_z\vert，則在x方向上的增量\Deltat_x=\frac{\Deltax}{\vertd_x\vert}，在y方向上的增量\Deltat_y=\frac{\Deltay}{\vertd_y\vert}，在z方向上的增量\Deltat_z=\frac{\Deltaz}{\vertd_z\vert}。光線在x方向上每移動(dòng)\Deltat_x的距離，就會進(jìn)入下一個(gè)x方向上的體素；在y方向上每移動(dòng)\Deltat_y的距離，就會進(jìn)入下一個(gè)y方向上的體素；在z方向上每移動(dòng)\Deltat_z的距離，就會進(jìn)入下一個(gè)z方向上的體素。通過比較這些增量，確定光線在當(dāng)前體素內(nèi)移動(dòng)時(shí)，哪個(gè)方向上會先到達(dá)體素的邊界，從而確定下一個(gè)要遍歷的體素。在遍歷每個(gè)體素時(shí)，需要檢查光線是否與該體素內(nèi)的物體相交。如果相交，則記錄相交信息，并根據(jù)需要進(jìn)行進(jìn)一步的處理，如計(jì)算交點(diǎn)的顏色、反射光線或折射光線等。如果光線在遍歷過程中沒有與任何物體相交，且已經(jīng)離開場景范圍，則停止遍歷。在一個(gè)包含多個(gè)物體的室內(nèi)場景中，光線在遍歷均勻柵格時(shí)，可能會依次經(jīng)過多個(gè)空體素，直到遇到與物體相交的體素。當(dāng)光線與一個(gè)墻壁體素相交時(shí)，根據(jù)墻壁的材質(zhì)屬性（如顏色、反射率等）計(jì)算交點(diǎn)的顏色，并根據(jù)反射定律生成反射光線，繼續(xù)對反射光線進(jìn)行遍歷。3.1.3優(yōu)勢與局限性均勻柵格在基于GPU的光線跟蹤算法中具有顯著的優(yōu)勢。從硬件實(shí)現(xiàn)的角度來看，其結(jié)構(gòu)簡單，易于在GPU上實(shí)現(xiàn)。由于體素大小均勻，通過簡單的算術(shù)運(yùn)算就能在常量時(shí)間內(nèi)定位和存取每個(gè)體素。在計(jì)算光線與體素的相交關(guān)系時(shí)，可以利用GPU的并行計(jì)算能力，將多個(gè)光線與體素的相交測試任務(wù)分配到不同的CUDA核心上同時(shí)進(jìn)行處理，大大提高了計(jì)算效率。體素的遍歷是通過遞增算術(shù)運(yùn)算來完成的，這消除了對堆棧的需要，使得從光線的起始點(diǎn)開始，以距離遞增的順序訪問體素成為可能。這種遍歷方式非常適合GPU的指令集，能夠充分發(fā)揮GPU的并行計(jì)算優(yōu)勢。用于遍歷的代碼特別適合用向量編寫，進(jìn)一步提高了代碼在GPU上的執(zhí)行效率。在一個(gè)大規(guī)模的場景中，包含大量的光線和物體，利用GPU并行計(jì)算均勻柵格的光線遍歷和相交測試，可以在短時(shí)間內(nèi)完成大量的計(jì)算任務(wù)，顯著提高光線跟蹤的速度。均勻柵格也存在一些局限性。由于其是空間細(xì)分結(jié)構(gòu)的一種特殊情況，多個(gè)體素可能包含相同三角形的多個(gè)引用。這就意味著需要對相同的光線和三角形之間進(jìn)行不止一次的相交測試，從而增加了計(jì)算量。在一個(gè)復(fù)雜的模型場景中，一個(gè)三角形可能會與多個(gè)體素相交，當(dāng)光線遍歷這些體素時(shí)，會對該三角形進(jìn)行多次相交測試，導(dǎo)致計(jì)算資源的浪費(fèi)。均勻柵格的構(gòu)建依賴于固定的分辨率，如果場景中的物體分布不均勻，可能會導(dǎo)致某些體素中包含大量的物體，而另一些體素則為空。在一個(gè)場景中，大部分物體集中在一個(gè)較小的區(qū)域內(nèi)，而其他區(qū)域較為空曠，此時(shí)均勻柵格的劃分可能會使得包含物體的體素負(fù)載過重，而空曠區(qū)域的體素則浪費(fèi)了存儲空間。這種情況下，均勻柵格的遍歷效率會受到很大影響，因?yàn)楣饩€在遍歷過程中需要花費(fèi)大量時(shí)間在處理包含大量物體的體素上。均勻柵格在處理大規(guī)模場景時(shí)，由于需要?jiǎng)澐执罅康捏w素，可能會導(dǎo)致內(nèi)存占用過高，超出GPU的內(nèi)存容量，從而影響算法的運(yùn)行。3.2KD-Tree3.2.1結(jié)構(gòu)原理與構(gòu)建KD-Tree（K-DimensionalTree）是一種空間細(xì)分結(jié)構(gòu)，利用二叉樹將場景表示成層次結(jié)構(gòu)，在基于CPU的光線跟蹤算法中，平均而言表現(xiàn)較快。其基本原理是將多維空間劃分成一系列的超矩形（即“單元格”），并將數(shù)據(jù)點(diǎn)存儲在這些單元格中。在構(gòu)建KD-Tree時(shí)，首先將所有數(shù)據(jù)點(diǎn)放置在一個(gè)包圍盒中，然后選擇一個(gè)坐標(biāo)軸作為分割軸。分割軸的選擇通?；跀?shù)據(jù)點(diǎn)在各個(gè)維度上的方差，選擇方差最大的維度作為分割軸，這樣可以使數(shù)據(jù)點(diǎn)在分割后盡可能均勻地分布在左右子樹中。假設(shè)我們有一組二維數(shù)據(jù)點(diǎn)\{(2,3),(5,4),(9,6),(4,7),(8,1),(7,2)\}，通過計(jì)算發(fā)現(xiàn)x軸方向上數(shù)據(jù)點(diǎn)的方差較大，所以選擇x軸作為初始分割軸。確定分割軸后，在該軸上找到數(shù)據(jù)點(diǎn)的中位數(shù)。對于上述二維數(shù)據(jù)點(diǎn)，在x軸上對數(shù)據(jù)點(diǎn)\{2,5,9,4,8,7\}進(jìn)行排序，找到中位數(shù)為7，對應(yīng)的點(diǎn)為(7,2)，將該點(diǎn)作為KD-Tree的根節(jié)點(diǎn)。然后根據(jù)該點(diǎn)在分割軸上的值，將數(shù)據(jù)點(diǎn)集合劃分為兩個(gè)子集，小于該值的數(shù)據(jù)點(diǎn)劃分到左子樹，大于等于該值的數(shù)據(jù)點(diǎn)劃分到右子樹。在這個(gè)例子中，左子樹的數(shù)據(jù)點(diǎn)集合為\{(2,3),(5,4),(4,7)\}，右子樹的數(shù)據(jù)點(diǎn)集合為\{(9,6),(8,1)\}。對于每個(gè)子樹，重復(fù)上述步驟，選擇新的分割軸并找到中位數(shù)進(jìn)行分割。在左子樹中，計(jì)算發(fā)現(xiàn)y軸方向上數(shù)據(jù)點(diǎn)的方差較大，所以選擇y軸作為分割軸。在y軸上對左子樹的數(shù)據(jù)點(diǎn)\{3,4,7\}進(jìn)行排序，找到中位數(shù)為4，對應(yīng)的點(diǎn)為(5,4)，將該點(diǎn)作為左子樹的根節(jié)點(diǎn)。然后將左子樹的數(shù)據(jù)點(diǎn)集合進(jìn)一步劃分為兩個(gè)子集，小于該值的數(shù)據(jù)點(diǎn)劃分到左子樹的左子樹，大于等于該值的數(shù)據(jù)點(diǎn)劃分到左子樹的右子樹。在這個(gè)例子中，左子樹的左子樹的數(shù)據(jù)點(diǎn)集合為\{(2,3)\}，左子樹的右子樹的數(shù)據(jù)點(diǎn)集合為\{(4,7)\}。以此類推，不斷遞歸地進(jìn)行分割，直到每個(gè)子樹中數(shù)據(jù)點(diǎn)的數(shù)量滿足一定的終止條件，如數(shù)據(jù)點(diǎn)數(shù)量小于某個(gè)閾值，或者達(dá)到了預(yù)設(shè)的最大遞歸深度。3.2.2光線遍歷策略在GPU上遍歷KD-Tree時(shí)，由于GPU沒有堆棧結(jié)構(gòu)，無法直接應(yīng)用遞歸的策略。取而代之的是，通過記住光線沿著前進(jìn)的距離來向上或者向下遍歷樹。這種策略消除了需要堆棧的限制，使得在GPU上完成對KD-Tree結(jié)構(gòu)的遍歷成為可能。當(dāng)光線與KD-Tree的根節(jié)點(diǎn)相交時(shí)，首先判斷光線與根節(jié)點(diǎn)的分割面的位置關(guān)系。假設(shè)根節(jié)點(diǎn)的分割軸為x軸，分割面的x坐標(biāo)為x_0，光線的起點(diǎn)坐標(biāo)為(x_1,y_1,z_1)，方向向量為(d_x,d_y,d_z)。如果x_1\ltx_0，則光線可能與根節(jié)點(diǎn)的左子樹相交；如果x_1\geqx_0，則光線可能與根節(jié)點(diǎn)的右子樹相交。確定光線可能相交的子樹后，計(jì)算光線與子樹的相交情況。這需要計(jì)算光線與子樹中節(jié)點(diǎn)所代表的空間區(qū)域的相交情況。對于內(nèi)部節(jié)點(diǎn)，其代表的空間區(qū)域由分割面和子樹的范圍確定；對于葉子節(jié)點(diǎn)，其代表的空間區(qū)域包含了與之相關(guān)的三角形。在計(jì)算光線與內(nèi)部節(jié)點(diǎn)的相交情況時(shí)，通過計(jì)算光線與分割面的交點(diǎn)，并判斷交點(diǎn)是否在子樹的范圍內(nèi)，來確定光線是否與子樹相交。如果光線與內(nèi)部節(jié)點(diǎn)相交，則繼續(xù)遞歸地判斷光線與子節(jié)點(diǎn)的相交情況。在計(jì)算光線與葉子節(jié)點(diǎn)的相交情況時(shí)，直接對葉子節(jié)點(diǎn)中包含的三角形進(jìn)行光線與三角形的相交測試。在遍歷過程中，利用GPU的并行計(jì)算能力，將多條光線的遍歷任務(wù)分配到不同的線程中同時(shí)進(jìn)行處理。每個(gè)線程負(fù)責(zé)一條光線的遍歷，通過共享內(nèi)存和同步機(jī)制，實(shí)現(xiàn)線程之間的數(shù)據(jù)共享和同步。為了提高遍歷效率，將KD-Tree的數(shù)據(jù)存儲在紋理中。這樣可以利用GPU的紋理緩存機(jī)制，提高數(shù)據(jù)訪問速度。通常會有一個(gè)保存樹數(shù)據(jù)的紋理，用于存儲節(jié)點(diǎn)的信息，如分割軸、分割面的位置、子樹的引用等；一個(gè)保存三角形列表的紋理，用于存儲葉子節(jié)點(diǎn)中三角形的索引；一個(gè)保存實(shí)際的三角形數(shù)據(jù)的紋理，用于存儲三角形的頂點(diǎn)坐標(biāo)、法線等信息。在遍歷過程中，通過紋理采樣操作，快速獲取所需的數(shù)據(jù)。3.2.3優(yōu)勢與局限性KD-Tree在光線跟蹤算法中具有一些顯著的優(yōu)勢。它能夠更好地適應(yīng)空間中的不均勻分布的圖元。在圖元多的地方，KD-Tree會相對分割細(xì)致一些，而圖元少的地方，就會分割得粗糙一些。這使得KD-Tree在遍歷過程中，能夠更有效地減少光線與無關(guān)三角形的相交測試，從而提高遍歷效率。在一個(gè)包含大量模型的場景中，某些區(qū)域模型密集，而其他區(qū)域較為空曠，KD-Tree可以根據(jù)模型的分布情況，在模型密集區(qū)域進(jìn)行更細(xì)致的分割，在空曠區(qū)域進(jìn)行較粗糙的分割，從而提高光線跟蹤的效率。KD-Tree也存在一些局限性。其構(gòu)建復(fù)雜度較高，在單線程的環(huán)境下，創(chuàng)建KD-Tree的理論復(fù)雜度下限為O(N*log(N))，其中N為圖元的數(shù)量。這意味著在構(gòu)建KD-Tree時(shí)，需要花費(fèi)較多的時(shí)間和計(jì)算資源。對于大規(guī)模的場景，構(gòu)建KD-Tree的時(shí)間可能會很長，影響光線跟蹤算法的實(shí)時(shí)性。KD-Tree在GPU上的內(nèi)存訪問模式不夠連續(xù)。由于KD-Tree的節(jié)點(diǎn)和數(shù)據(jù)分布較為分散，在遍歷過程中，可能會導(dǎo)致頻繁的內(nèi)存訪問跳躍，無法充分利用GPU的內(nèi)存帶寬，從而影響計(jì)算效率。在光線遍歷KD-Tree時(shí)，需要頻繁地訪問不同位置的節(jié)點(diǎn)和三角形數(shù)據(jù)，這些數(shù)據(jù)在內(nèi)存中的存儲位置可能不連續(xù)，導(dǎo)致內(nèi)存訪問效率低下。3.3包圍體層次（BVH）3.3.1結(jié)構(gòu)原理與構(gòu)建包圍體層次（BVH）是一種廣泛應(yīng)用于光線跟蹤算法的加速結(jié)構(gòu)，其核心原理是通過構(gòu)建層次化的包圍體樹，來加速光線與物體的相交測試。在BVH中，每個(gè)節(jié)點(diǎn)都包含一個(gè)包圍體，用于包圍一組物體或子節(jié)點(diǎn)。包圍體通常采用軸對齊包圍盒（AABB），它是一個(gè)與坐標(biāo)軸對齊的長方體，通過記錄物體在x、y、z三個(gè)方向上的最小和最大值，來確定包圍盒的范圍。假設(shè)場景中有一組三角形物體，首先為每個(gè)三角形構(gòu)建AABB，然后將這些AABB組合成更大的包圍體，形成層次結(jié)構(gòu)。構(gòu)建BVH的過程通常采用自底向上或自頂向下的方法。自底向上的構(gòu)建方法首先為每個(gè)物體創(chuàng)建一個(gè)包圍體，將這些包圍體作為葉子節(jié)點(diǎn)。然后，不斷合并相鄰的包圍體，形成更高層次的節(jié)點(diǎn)，直到所有的葉子節(jié)點(diǎn)都被合并到根節(jié)點(diǎn)。在一個(gè)包含多個(gè)三角形的場景中，首先為每個(gè)三角形創(chuàng)建AABB，將這些AABB作為葉子節(jié)點(diǎn)。然后，選擇兩個(gè)相鄰的葉子節(jié)點(diǎn)，計(jì)算它們的合并包圍體，將這個(gè)合并包圍體作為新的節(jié)點(diǎn)，其左右子節(jié)點(diǎn)分別為原來的兩個(gè)葉子節(jié)點(diǎn)。重復(fù)這個(gè)過程，不斷合并節(jié)點(diǎn)，直到形成根節(jié)點(diǎn)。自頂向下的構(gòu)建方法則從整個(gè)場景的包圍體開始，遞歸地將其劃分為兩個(gè)子包圍體，每個(gè)子包圍體再進(jìn)一步劃分，直到每個(gè)子包圍體只包含少量的物體或單個(gè)物體。在劃分過程中，通常使用表面積啟發(fā)式（SAH）函數(shù)來選擇最優(yōu)的劃分方式。SAH函數(shù)通過計(jì)算父節(jié)點(diǎn)和孩子節(jié)點(diǎn)的表面積之比，來評估劃分的優(yōu)劣。其公式為：cost=\frac{SA_{left}\cdotn_{left}+SA_{right}\cdotn_{right}}{SA_{parent}}，其中SA_{left}和SA_{right}分別為左右子節(jié)點(diǎn)的表面積，n_{left}和n_{right}分別為左右子節(jié)點(diǎn)中物體的數(shù)量，SA_{parent}為父節(jié)點(diǎn)的表面積。通過最小化這個(gè)成本函數(shù)，可以找到最優(yōu)的劃分位置。假設(shè)在劃分一個(gè)包圍體時(shí)，有兩種劃分方案。方案一將包圍體劃分為左右兩個(gè)子包圍體，左子包圍體的表面積為SA_{left1}，包含n_{left1}個(gè)物體；右子包圍體的表面積為SA_{right1}，包含n_{right1}個(gè)物體。方案二將包圍體劃分為另外兩個(gè)子包圍體，左子包圍體的表面積為SA_{left2}，包含n_{left2}個(gè)物體；右子包圍體的表面積為SA_{right2}，包含n_{right2}個(gè)物體。分別計(jì)算兩種方案的成本cost1和cost2，選擇成本較小的方案作為劃分方式。3.3.2光線遍歷策略光線在BVH中的遍歷過程是從根節(jié)點(diǎn)開始，依次與各級包圍體進(jìn)行相交測試。當(dāng)光線與某個(gè)包圍體相交時(shí)，繼續(xù)對該包圍體的子節(jié)點(diǎn)進(jìn)行相交測試；如果光線與某個(gè)包圍體不相交，則跳過該包圍體及其所有子節(jié)點(diǎn)。這種遍歷方式能夠快速排除不相關(guān)的物體，減少光線與物體的相交測試次數(shù)。假設(shè)光線從視點(diǎn)出發(fā)，首先與BVH的根節(jié)點(diǎn)的包圍體進(jìn)行相交測試。如果光線與根節(jié)點(diǎn)的包圍體相交，則繼續(xù)對根節(jié)點(diǎn)的左右子節(jié)點(diǎn)的包圍體進(jìn)行相交測試。如果光線與左子節(jié)點(diǎn)的包圍體相交，而與右子節(jié)點(diǎn)的包圍體不相交，則跳過右子節(jié)點(diǎn)及其所有子節(jié)點(diǎn)，繼續(xù)對左子節(jié)點(diǎn)的子節(jié)點(diǎn)進(jìn)行相交測試。在遍歷過程中，通常采用深度優(yōu)先搜索（DFS）或廣度優(yōu)先搜索（BFS）的策略。深度優(yōu)先搜索策略沿著樹的深度方向進(jìn)行遍歷，優(yōu)先訪問子節(jié)點(diǎn)，直到到達(dá)葉子節(jié)點(diǎn)。這種策略適合處理內(nèi)存有限的情況，因?yàn)樗恍枰４娈?dāng)前路徑上的節(jié)點(diǎn)信息。廣度優(yōu)先搜索策略則按照層次順序進(jìn)行遍歷，先訪問同一層的所有節(jié)點(diǎn)，再訪問下一層的節(jié)點(diǎn)。這種策略適合處理需要快速找到最近交點(diǎn)的情況，因?yàn)樗軌蛟谳^早的層次找到可能的交點(diǎn)。在一個(gè)復(fù)雜的場景中，如果內(nèi)存有限，采用深度優(yōu)先搜索策略可以減少內(nèi)存的占用；如果需要快速找到最近交點(diǎn)，采用廣度優(yōu)先搜索策略可以提高搜索效率。為了進(jìn)一步提高遍歷效率，還可以采用一些優(yōu)化技巧。使用提前終止條件，當(dāng)光線與某個(gè)包圍體相交，且該包圍體是葉子節(jié)點(diǎn)時(shí)，直接對葉子節(jié)點(diǎn)中的物體進(jìn)行相交測試，找到最近交點(diǎn)后即可終止遍歷。利用GPU的并行計(jì)算能力，將多條光線的遍歷任務(wù)分配到不同的線程中同時(shí)進(jìn)行處理。在一個(gè)包含大量光線的場景中，將光線分組，每組光線對應(yīng)一個(gè)線程，每個(gè)線程負(fù)責(zé)遍歷一組光線與BVH的相交情況，從而提高光線跟蹤的速度。3.3.3優(yōu)勢與局限性BVH在光線跟蹤算法中具有顯著的優(yōu)勢。它能夠自適應(yīng)地適應(yīng)場景中物體的分布情況。由于在構(gòu)建過程中考慮了物體的空間位置和數(shù)量，BVH可以在物體密集的區(qū)域進(jìn)行更細(xì)致的劃分，在物體稀疏的區(qū)域進(jìn)行較粗糙的劃分。在一個(gè)包含大量模型的場景中，某些區(qū)域模型密集，而其他區(qū)域較為空曠，BVH可以根據(jù)模型的分布情況，在模型密集區(qū)域構(gòu)建更多層次的包圍體，以提高光線與物體相交測試的效率；在空曠區(qū)域構(gòu)建較少層次的包圍體，減少不必要的計(jì)算。這種自適應(yīng)的劃分方式能夠有效地減少光線與無關(guān)物體的相交測試，提高光線跟蹤的效率。BVH的內(nèi)存占用相對可控。由于圖元的數(shù)量不會因?yàn)閯澐侄鲩L，所以需要開辟的空間是可以預(yù)先計(jì)算的，節(jié)點(diǎn)的數(shù)量也不會超過2N-1（N為圖元的數(shù)量）。這使得在處理大規(guī)模場景時(shí)，能夠更好地管理內(nèi)存資源，避免內(nèi)存溢出的問題。在一個(gè)包含大量三角形的復(fù)雜場景中，使用BVH加速結(jié)構(gòu)可以預(yù)先計(jì)算所需的內(nèi)存空間，合理分配內(nèi)存資源，保證光線跟蹤算法的穩(wěn)定運(yùn)行。BVH也存在一些局限性。構(gòu)建高質(zhì)量的BVH需要花費(fèi)較長的時(shí)間。雖然有各種構(gòu)建算法，但目前還沒有一種能夠在所有情況下都構(gòu)建出最優(yōu)的BVH。尤其是在處理大規(guī)模場景時(shí)，構(gòu)建BVH的時(shí)間可能會成為瓶頸，影響光線跟蹤算法的實(shí)時(shí)性。在一個(gè)包含數(shù)百萬個(gè)三角形的超大規(guī)模場景中，構(gòu)建BVH可能需要幾分鐘甚至更長的時(shí)間，這對于實(shí)時(shí)渲染應(yīng)用來說是無法接受的。BVH在遍歷過程中，由于節(jié)點(diǎn)的重疊和不規(guī)則性，可能會導(dǎo)致一些不必要的相交測試。雖然通過優(yōu)化策略可以減少這種情況的發(fā)生，但仍然無法完全避免。在某些復(fù)雜的場景中，由于BVH節(jié)點(diǎn)的重疊，光線可能會與多個(gè)重疊的包圍體進(jìn)行相交測試，增加了計(jì)算量。四、加速結(jié)構(gòu)性能比較實(shí)驗(yàn)4.1實(shí)驗(yàn)環(huán)境與設(shè)置為了全面、準(zhǔn)確地比較均勻柵格、KD-Tree、包圍體層次（BVH）這三種加速結(jié)構(gòu)在基于GPU的光線跟蹤算法中的性能，搭建了以下實(shí)驗(yàn)環(huán)境。在硬件方面，采用NVIDIAGeForceRTX3080GPU，其擁有8704個(gè)CUDA核心，核心頻率為1440-1710MHz，顯存為10GBGDDR6X，具備強(qiáng)大的并行計(jì)算能力，能夠高效地執(zhí)行光線跟蹤算法中的大規(guī)模并行任務(wù)。搭配IntelCorei7-12700KCPU，其具有12個(gè)性能核心和8個(gè)能效核心，睿頻最高可達(dá)5.0GHz，主要負(fù)責(zé)管理和控制整個(gè)實(shí)驗(yàn)程序的流程，包括數(shù)據(jù)的讀取、任務(wù)的分配等。內(nèi)存選用32GBDDR43200MHz，以滿足實(shí)驗(yàn)過程中對數(shù)據(jù)存儲和快速訪問的需求。軟件平臺上，操作系統(tǒng)為Windows1064位專業(yè)版，為實(shí)驗(yàn)提供穩(wěn)定的運(yùn)行環(huán)境。開發(fā)環(huán)境采用CUDA11.6并行計(jì)算平臺，利用其豐富的庫和工具進(jìn)行GPU編程，實(shí)現(xiàn)基于不同加速結(jié)構(gòu)的光線跟蹤算法。同時(shí)，使用VisualStudio2019作為集成開發(fā)環(huán)境（IDE），方便進(jìn)行代碼的編寫、調(diào)試和優(yōu)化。實(shí)驗(yàn)參數(shù)的設(shè)置對于準(zhǔn)確評估加速結(jié)構(gòu)的性能至關(guān)重要。在光線跟蹤算法中，光線的采樣數(shù)量直接影響圖像的質(zhì)量和計(jì)算時(shí)間。設(shè)置光線采樣數(shù)量為1024，這是在保證圖像質(zhì)量的前提下，經(jīng)過多次實(shí)驗(yàn)測試后確定的一個(gè)較為合適的值。在一些簡單場景下，較低的采樣數(shù)量（如256）也能生成相對清晰的圖像，但對于復(fù)雜場景，可能會出現(xiàn)鋸齒、噪點(diǎn)等問題。而當(dāng)采樣數(shù)量提高到4096時(shí)，圖像質(zhì)量會有進(jìn)一步提升，但計(jì)算時(shí)間會顯著增加。經(jīng)過對比，1024的采樣數(shù)量能夠在圖像質(zhì)量和計(jì)算時(shí)間之間取得較好的平衡。遞歸深度決定了光線在場景中反射和折射的最大次數(shù)。將遞歸深度設(shè)置為5，這意味著光線最多可以進(jìn)行5次反射和折射。在實(shí)際場景中，光線的反射和折射次數(shù)過多可能會導(dǎo)致計(jì)算量呈指數(shù)級增長，而大部分光線在經(jīng)過幾次反射和折射后，對最終圖像顏色的貢獻(xiàn)已經(jīng)非常小。通過實(shí)驗(yàn)發(fā)現(xiàn)，對于大多數(shù)場景，遞歸深度為5時(shí)，能夠較好地模擬光線的傳播和交互，同時(shí)不會使計(jì)算量過大。在渲染分辨率方面，選擇1920×1080的全高清分辨率。這是目前常見的顯示分辨率，能夠在保證圖像細(xì)節(jié)的同時(shí)，也便于與其他研究成果進(jìn)行對比。在較低分辨率（如1280×720）下，算法的計(jì)算量會減少，運(yùn)行速度會加快，但圖像的細(xì)節(jié)會有所損失；而在更高分辨率（如3840×2160）下，雖然能夠呈現(xiàn)更豐富的細(xì)節(jié)，但對硬件性能的要求也更高，可能會導(dǎo)致算法運(yùn)行緩慢。數(shù)據(jù)集的選擇涵蓋了多種類型的場景，以全面評估不同加速結(jié)構(gòu)在各種情況下的性能。選擇“CornellBox”場景作為簡單場景的代表。這個(gè)場景包含基本的幾何形狀，如立方體、平面等，材質(zhì)和光照效果相對簡單，主要用于初步測試加速結(jié)構(gòu)的性能，觀察其在處理簡單幾何物體和基本光照計(jì)算時(shí)的表現(xiàn)。在“CornellBox”場景中，均勻柵格由于其簡單的結(jié)構(gòu)和快速的體素遍歷方式，能夠快速完成光線與物體的相交測試；KD-Tree和BVH在處理這種簡單場景時(shí)也能高效運(yùn)行，但優(yōu)勢相對不明顯?！癝tanfordBunny”場景則是復(fù)雜模型場景的典型代表。該場景包含精細(xì)復(fù)雜的幾何形狀，如兔子模型的毛發(fā)、耳朵等細(xì)節(jié)豐富的部分，對加速結(jié)構(gòu)處理復(fù)雜幾何形狀的能力是一個(gè)嚴(yán)峻的考驗(yàn)。在這個(gè)場景中，KD-Tree能夠根據(jù)模型的幾何形狀特點(diǎn)，進(jìn)行合理的空間劃分，減少光線與無關(guān)三角形的相交測試，從而提高遍歷效率；BVH也能通過自適應(yīng)的包圍體層次結(jié)構(gòu)，有效加速光線與物體的相交測試；而均勻柵格由于其固定的分辨率和空間劃分方式，在處理復(fù)雜模型時(shí)，可能會出現(xiàn)體素劃分不合理的情況，導(dǎo)致計(jì)算量增加。選擇“InteriorScene”作為室內(nèi)場景的代表。這個(gè)場景具有豐富的材質(zhì)和光照效果，如不同材質(zhì)的家具、墻壁，以及復(fù)雜的燈光布置，能夠考察加速結(jié)構(gòu)在處理復(fù)雜光照和材質(zhì)交互時(shí)的性能。在“InteriorScene”場景中，BVH的自適應(yīng)特性使其能夠更好地處理不同材質(zhì)和光照下的光線傳播，通過合理的包圍體劃分，減少光線與無關(guān)物體的相交測試，提高光線跟蹤的效率；KD-Tree在處理這種場景時(shí)，也能根據(jù)物體的分布和材質(zhì)特點(diǎn)進(jìn)行有效的空間劃分；均勻柵格在處理復(fù)雜光照和材質(zhì)時(shí)，由于其空間劃分的局限性，可能會導(dǎo)致光線與物體的相交測試不準(zhǔn)確，從而影響圖像的渲染質(zhì)量。通過以上硬件設(shè)備、軟件平臺的搭建，以及實(shí)驗(yàn)參數(shù)和數(shù)據(jù)集的合理設(shè)置，為全面、客觀地比較均勻柵格、KD-Tree、BVH這三種加速結(jié)構(gòu)的性能提供了堅(jiān)實(shí)的基礎(chǔ)。4.2性能評價(jià)指標(biāo)為了全面、客觀地比較均勻柵格、KD-Tree、包圍體層次（BVH）這三種加速結(jié)構(gòu)在基于GPU的光線跟蹤算法中的性能，確定了以下關(guān)鍵性能評價(jià)指標(biāo)。渲染時(shí)間是衡量加速結(jié)構(gòu)性能的重要指標(biāo)之一，它直接反映了光線跟蹤算法生成圖像所需的時(shí)間。在光線跟蹤過程中，渲染時(shí)間主要包括光線生成、光線與物體相交測試、顏色計(jì)算與遞歸追蹤等各個(gè)環(huán)節(jié)所耗費(fèi)的時(shí)間總和。對于復(fù)雜場景，渲染時(shí)間的長短直接影響到用戶的體驗(yàn)和應(yīng)用的實(shí)時(shí)性。在實(shí)時(shí)游戲場景中，如果渲染時(shí)間過長，會導(dǎo)致畫面卡頓，影響游戲的流暢性和玩家的沉浸感。通過精確測量不同加速結(jié)構(gòu)在相同場景和參數(shù)設(shè)置下的渲染時(shí)間，可以直觀地比較它們的計(jì)算效率。在“StanfordBunny”場景中，分別使用均勻柵格、KD-Tree、BVH加速結(jié)構(gòu)進(jìn)行光線跟蹤渲染，記錄各自的渲染時(shí)間，從而評估它們在處理復(fù)雜模型場景時(shí)的計(jì)算效率差異。內(nèi)存占用也是一個(gè)關(guān)鍵指標(biāo)。在基于GPU的光線跟蹤算法中，需要存儲大量的場景數(shù)據(jù)、加速結(jié)構(gòu)數(shù)據(jù)以及中間計(jì)算結(jié)果，這些數(shù)據(jù)的存儲會占用GPU的內(nèi)存資源。不同的加速結(jié)構(gòu)在構(gòu)建和使用過程中，對內(nèi)存的需求各不相同。均勻柵格由于其固定的分辨率和空間劃分方式，可能會導(dǎo)致在處理大規(guī)模場景時(shí)內(nèi)存占用過高。如果場景中的物體分布不均勻，一些體素可能會包含大量的物體信息，從而占用較多的內(nèi)存空間。而KD-Tree和BVH雖然在內(nèi)存占用方面相對更可控，但在構(gòu)建復(fù)雜場景的加速結(jié)構(gòu)時(shí)，也可能會占用一定的內(nèi)存。通過監(jiān)測不同加速結(jié)構(gòu)在運(yùn)行過程中的內(nèi)存使用情況，包括全局內(nèi)存、共享內(nèi)存等的占用量，可以評估它們對GPU內(nèi)存資源的利用效率。在“InteriorScene”場景中，對比三種加速結(jié)構(gòu)在渲染過程中的內(nèi)存占用情況，分析它們在處理具有豐富材質(zhì)和光照效果的室內(nèi)場景時(shí)，對內(nèi)存資源的需求差異。光線求交次數(shù)反映了光線跟蹤算法中光線與物體相交測試的頻繁程度，是衡量加速結(jié)構(gòu)加速效果的重要依據(jù)。光線求交測試是光線跟蹤算法中計(jì)算量較大的部分，減少光線求交次數(shù)可以顯著提高算法的效率。不同的加速結(jié)構(gòu)通過不同的方式來組織場景中的物體，從而影響光線求交次數(shù)。均勻柵格通過將空間劃分為體素，使得光線在遍歷過程中可能會與多個(gè)體素中的物體進(jìn)行相交測試，導(dǎo)致光線求交次數(shù)較多。而KD-Tree和BVH通過構(gòu)建層次化的結(jié)構(gòu)，能夠快速排除不相關(guān)的物體，減少光線求交次數(shù)。在一個(gè)包含大量三角形的場景中，BVH可以通過包圍體層次結(jié)構(gòu)，快速判斷光線是否與某個(gè)包圍體相交，從而避免對包圍體內(nèi)部大量三角形的相交測試，有效減少光線求交次數(shù)。通過統(tǒng)計(jì)不同加速結(jié)構(gòu)在光線跟蹤過程中的光線求交次數(shù)，可以評估它們在加速光線與物體相交測試方面的性能優(yōu)劣。在“CornellBox”場景中，統(tǒng)計(jì)三種加速結(jié)構(gòu)在光線跟蹤過程中的光線求交次數(shù)，分析它們在處理簡單場景時(shí)的加速效果差異。4.3實(shí)驗(yàn)結(jié)果與分析在完成基于不同加速結(jié)構(gòu)的光線跟蹤算法在特定實(shí)驗(yàn)環(huán)境和參數(shù)設(shè)置下的實(shí)現(xiàn)后，對實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析。以下是均勻柵格、KD-Tree和BVH在不同場景下的性能數(shù)據(jù)對比，具體數(shù)據(jù)如下表所示：加速結(jié)構(gòu)場景渲染時(shí)間（s）內(nèi)存占用（MB）光線求交次數(shù)（百萬次）均勻柵格CornellBox1.25020StanfordBunny4.512080InteriorScene6.8180120KD-TreeCornellBox1.56015StanfordBunny3.810060InteriorScene5.615090BVHCornellBox1.04510StanfordBunny3.08040InteriorScene4.212060從渲染時(shí)間來看，在簡單的“CornellBox”場景中，BVH的渲染時(shí)間最短，僅為1.0秒，均勻柵格為1.2秒，KD-Tree為1.5秒。這是因?yàn)锽VH能夠快速排除不相關(guān)的物體，減少光線與物體的相交測試次數(shù)，從而提高了渲染效率。在“StanfordBunny”復(fù)雜模型場景中，BVH依然表現(xiàn)出色，渲染時(shí)間為3.0秒，KD-Tree為3.8秒，均勻柵格為4.5秒。BVH的自適應(yīng)特性使其能夠更好地處理復(fù)雜模型的空間劃分，減少光線與無關(guān)三角形的相交測試，而均勻柵格由于其固定的分辨率和空間劃分方式，在處理復(fù)雜模型時(shí)計(jì)算量增加，導(dǎo)致渲染時(shí)間較長。在“InteriorScene”室內(nèi)場景中，BVH的渲染時(shí)間為4.2秒，KD-Tree為5.6秒，均勻柵格為6.8秒。室內(nèi)場景具有豐富的材質(zhì)和光照效果，BVH能夠根據(jù)物體的分布和材質(zhì)特點(diǎn)進(jìn)行有效的包圍體劃分，減少光線與無關(guān)物體的相交測試，提高光線跟蹤的效率。內(nèi)存占用方面，在“CornellBox”場景中，BVH的內(nèi)存占用最少，為45MB，均勻柵格為50MB，KD-Tree為60MB。BVH的內(nèi)存占用相對可控，由于圖元的數(shù)量不會因?yàn)閯澐侄鲩L，所以需要開辟的空間是可以預(yù)先計(jì)算的。在“StanfordBunny”場景中，BVH的內(nèi)存占用為80MB，KD-Tree為100MB，均勻柵格為120MB。均勻柵格在處理復(fù)雜模型時(shí)，由于體素劃分不合理，可能會導(dǎo)致某些體素中包含大量的物體信息，從而占用較多的內(nèi)存空間。在“InteriorScene”場景中，BVH的內(nèi)存占用為120MB，KD-Tree為150MB，均勻柵格為180MB。同樣，均勻柵格在處理這種具有豐富材質(zhì)和光照效果的場景時(shí)，內(nèi)存占用較高。光線求交次數(shù)上，在“CornellBox”場景中，BVH的光線求交次數(shù)最少，為10百萬次，KD-Tree為15百萬次，均勻柵格為20百萬次。BVH通過層次化的包圍體結(jié)構(gòu)，能夠快速判斷光線是否與某個(gè)包圍體相交，從而避免對包圍體內(nèi)部大量三角形的相交測試，有效減少光線求交次數(shù)。在“StanfordBunny”場景中，BVH的光線求交次數(shù)為40百萬次，KD-Tree為60百萬次，均勻柵格為80百萬次。均勻柵格由于其空間劃分特性，可能導(dǎo)致對相同光線和三角形的多次相交測試，從而增加了光線求交次數(shù)。在“InteriorScene”場景中，BVH的光線求交次數(shù)為60百萬次，KD-Tree為90百萬次，均勻柵格為120百萬次。BVH在處理復(fù)雜光照和材質(zhì)時(shí)，能夠通過合理的包圍體劃分，減少光線與無關(guān)物體的相交測試，降低光線求交次數(shù)。綜合以上分析，在不同場景下，BVH在渲染時(shí)間、內(nèi)存占用和光線求交次數(shù)等方面都表現(xiàn)出較好的性能。KD-Tree在處理復(fù)雜模型場景時(shí)也有不錯(cuò)的表現(xiàn)，但在內(nèi)存占用和某些場景下的渲染時(shí)間上略遜于BVH。均勻柵格雖然結(jié)構(gòu)簡單，易于在GPU上實(shí)現(xiàn)，但在處理復(fù)雜場景時(shí)存在計(jì)算量較大、內(nèi)存占用較高等問題，性能相對較弱。影響性能的因素主要包括加速結(jié)構(gòu)的空間劃分方式、對場景中物體分布的適應(yīng)性以及內(nèi)存訪問模式等。BVH和KD-Tree能夠根據(jù)場景中物體的分布進(jìn)行合理的空間劃分，減少光線與無關(guān)物體的相交測試，從而提高性能；而均勻柵格由于固定的分辨率和空間劃分方式，在處理復(fù)雜場景時(shí)存在局限性。內(nèi)存訪問模式也對性能有重要影響，BVH和KD-Tree在內(nèi)存訪問上相對更高效，能夠更好地利用GPU的內(nèi)存帶寬。五、應(yīng)用場景分析5.1游戲開發(fā)在游戲開發(fā)領(lǐng)域，實(shí)時(shí)渲染是實(shí)現(xiàn)高質(zhì)量游戲畫面的關(guān)鍵技術(shù)，而不同的加速結(jié)構(gòu)在滿足實(shí)時(shí)渲染需求方面發(fā)揮著不同的作用。以熱門游戲《賽博朋克2077》為例，該游戲以其高度開放的世界、精美的畫面和豐富的光影效果而備受贊譽(yù)，對光線跟蹤算法和加速結(jié)構(gòu)的性能有著極高的要求。在《賽博朋克2077》中，城市場景復(fù)雜多樣，包含大量的建筑、車輛、人物以及各種細(xì)節(jié)豐富的物體。均勻柵格加速結(jié)構(gòu)在處理這樣的場景時(shí)，由于其結(jié)構(gòu)簡單，易于在GPU上實(shí)現(xiàn)，能夠快速地對場景進(jìn)行初步的空間劃分。在光線生成階段，均勻柵格可以通過簡單的算術(shù)運(yùn)算快速定位光線進(jìn)入的體素，從而開始光線遍歷。然而，由于城市場景中物體分布不均勻，均勻柵格可能會導(dǎo)致某些體素中包含大量的物體，而另一些體素則為空，這會使得光線在遍歷過程中需要對相同的光線和三角形進(jìn)行多次相交測試，增加了計(jì)算量，影響渲染效率。在城市的繁華商業(yè)區(qū)，建筑物密集，均勻柵格可能會將這些建筑物劃分到多個(gè)體素中，導(dǎo)致光線在遍歷這些體素時(shí)，對建筑物的三角形進(jìn)行多次相交測試，從而降低了渲染速度。KD-Tree加速結(jié)構(gòu)在《賽博朋克2077》中也有一定的應(yīng)用。由于KD-Tree能夠根據(jù)物體的分布情況進(jìn)行空間細(xì)分，在物體密集的區(qū)域相對分割細(xì)致一些，而在物體稀疏的區(qū)域分割得粗糙一些。在游戲中的城市街道場景，KD-Tree可以根據(jù)建筑物、車輛等物體的分布，合理地劃分空間，減少光線與無關(guān)三角形的相交測試。對于一條沿著街道傳播的光線，KD-Tree可以通過層次結(jié)構(gòu)快速判斷光線是否與某個(gè)區(qū)域內(nèi)的物體相交，避免對街道空曠區(qū)域的無效相交測試，從而提高遍歷效率。KD-Tree在GPU上的內(nèi)存訪問模式不夠連續(xù)，在處理大規(guī)模場景時(shí)，可能會導(dǎo)致頻繁的內(nèi)存訪問跳躍，無法充分利用GPU的內(nèi)存帶寬，從而影響渲染性能。在游戲加載大量的城市建筑模型時(shí)，KD-Tree的內(nèi)存訪問不連續(xù)可能會導(dǎo)致數(shù)據(jù)讀取延遲，影響渲染的實(shí)時(shí)性。包圍體層次（BVH）加速結(jié)構(gòu)在《賽博朋克2077》中展現(xiàn)出了卓越的性能。由于游戲場景中的物體分布復(fù)雜，BVH能夠自適應(yīng)地適應(yīng)場景中物體的分布情況。在構(gòu)建過程中，BVH通過表面積啟發(fā)式（SAH）函數(shù)等方法，根據(jù)物體的空間位置和數(shù)量進(jìn)行合理的包圍體劃分，在物體密集的區(qū)域構(gòu)建更多層次的包圍體，以提高光線與物體相交測試的效率；在空曠區(qū)域構(gòu)建較少層次的包圍體，減少不必要的計(jì)算。在游戲中的大型廣場場景，BVH可以將廣場上的人物、車輛等物體分別用合適的包圍體進(jìn)行組織，形成層次結(jié)構(gòu)。當(dāng)光線進(jìn)行相交測試時(shí)，首先與高層的包圍體進(jìn)行快速測試，若不相交，則直接跳過該包圍體所包含的所有物體，大大減少了光線與物體的相交測試次數(shù)，提高了渲染效率。BVH的內(nèi)存占用相對可控，在處理大規(guī)模場景時(shí)，能夠更好地管理內(nèi)存資源，避免內(nèi)存溢出的問題。這對于《賽博朋克2077》這樣的大型游戲來說至關(guān)重要，確保了游戲在運(yùn)行過程中能夠穩(wěn)定地使用GPU內(nèi)存，維持良好的渲染性能。綜合來看，在游戲開發(fā)中，如《賽博朋克2077》這樣對實(shí)時(shí)渲染要求極高的場景，BVH加速結(jié)構(gòu)憑借其自適應(yīng)的空間劃分能力、高效的光線遍歷策略以及可控的內(nèi)存占用，能夠更好地滿足游戲?qū)︿秩拘屎彤嬅尜|(zhì)量的要求。雖然均勻柵格和KD-Tree在某些方面也有各自的優(yōu)勢，但在處理復(fù)雜游戲場景時(shí)，BVH的綜合性能更為突出。然而，不同的游戲場景和需求可能會對加速結(jié)構(gòu)的選擇產(chǎn)生影響，在一些簡單的游戲場景中，均勻柵格的簡單高效可能更具優(yōu)勢；而對于一些對內(nèi)存訪問模式要求不高，但對空間劃分靈活性有一定需求的游戲場景，KD-Tree也可能是一個(gè)合適的選擇。因此，在游戲開發(fā)中，需要根據(jù)具體的游戲場景和需求，綜合考慮各種因素，選擇最合適的加速結(jié)構(gòu)，以實(shí)現(xiàn)最佳的實(shí)時(shí)渲染效果。5.2影視制作在影視制作領(lǐng)域，光線跟蹤算法及其加速結(jié)構(gòu)對于提升渲染質(zhì)量和效率起著舉足輕重的作用，這直接關(guān)系到影視作品能否為觀眾呈現(xiàn)出震撼的視覺效果。以電影《阿凡達(dá)》的特效制作為例，這部電影以其美輪美奐的潘多拉星球場景和逼真的生物形象而聞名于世，其背后離不開先進(jìn)的光線跟蹤技術(shù)和精心選擇的加速結(jié)構(gòu)。在《阿凡達(dá)》的特效制作中，潘多拉星球的自然場景極為復(fù)雜，茂密的叢林中生長著形態(tài)各異、細(xì)節(jié)豐富的植物，這些植物的葉片紋理、枝干結(jié)構(gòu)都需要精確呈現(xiàn)。均勻柵格加速結(jié)構(gòu)在處理這類場景時(shí)，由于其固定的分辨率和簡單的空間劃分方式，在構(gòu)建過程中，需要根據(jù)場景的范圍和預(yù)期的精度確定柵格的分辨率。若分辨率設(shè)置過高，會導(dǎo)致體素?cái)?shù)量劇增，內(nèi)存占用大幅提高。當(dāng)柵格分辨率過高時(shí)，存儲每個(gè)體素的信息會占用大量的內(nèi)存空間，這對于處理大規(guī)模場景的影視制作來說是一個(gè)巨大的挑戰(zhàn)。分辨率過低又會使場景中的物體表示不夠精確，導(dǎo)致光線與物體的相交測試出現(xiàn)偏差。在表示細(xì)小的植物枝干時(shí)，可能會因?yàn)轶w素過大而無法準(zhǔn)確描述其形狀，從而影響光線跟蹤的準(zhǔn)確性，最終導(dǎo)致渲染出的圖像出現(xiàn)模糊、失真等問題。在處理潘多拉星球的茂密叢林場景時(shí)，均勻柵格可能會因?yàn)轶w素劃分不夠精細(xì)，無法準(zhǔn)確捕捉到每一片樹葉的細(xì)節(jié)，使得渲染出的植物缺乏真實(shí)感。KD-Tree加速結(jié)構(gòu)在處理《阿凡達(dá)》中的復(fù)雜模型時(shí)，如納美人的角色模型，其身體結(jié)構(gòu)、面部表情和服飾細(xì)節(jié)都非常豐富。KD-Tree能夠根據(jù)物體的分布和幾何形狀進(jìn)行空間細(xì)分，在模型細(xì)節(jié)豐富的區(qū)域相對分割細(xì)致一些，而在相對簡單的區(qū)域分割得粗糙一些。對于納美人面部的復(fù)雜表情和精細(xì)的服飾紋理，KD-Tree可以進(jìn)行更細(xì)致的空間劃分，減少光線與無關(guān)三角形的相交測試，提高光線跟蹤的效率。在處理納美人的頭發(fā)時(shí)，由于頭發(fā)的幾何形狀復(fù)雜且數(shù)量眾多，KD-Tree可以根據(jù)頭發(fā)的分布特點(diǎn)進(jìn)行合理的空間劃分，使得光線在遍歷過程中能夠更快速地找到與頭發(fā)相交的部分，從而準(zhǔn)確地計(jì)算出光線與頭發(fā)的交互效果，如反射、折射等。KD-Tree在GPU上的內(nèi)存訪問模式不夠連續(xù)。在影視制作中，需要處理大量的模型數(shù)據(jù)和光線跟蹤計(jì)算，KD-Tree的內(nèi)存訪問不連續(xù)可能會導(dǎo)致數(shù)據(jù)讀取延遲，影響渲染的實(shí)時(shí)性。在渲染納美人的動(dòng)畫時(shí)，頻繁的內(nèi)存訪問跳躍會使GPU無法高效地獲取數(shù)據(jù)，導(dǎo)致渲染速度變慢，無法滿足影視制作對實(shí)時(shí)性的要求。包圍體層次（BVH）加速結(jié)構(gòu)在《阿凡達(dá)》的特效制作中展現(xiàn)出了顯著的優(yōu)勢。在構(gòu)建過程中，BVH通過表面積啟發(fā)式（SAH）函數(shù)等方法，根據(jù)物體的空間位置和數(shù)量進(jìn)行合理的包圍體劃分。對于潘多拉星球上的大規(guī)模場景，如山脈、河流等，BVH可以將這些場景元素用合適的包圍體進(jìn)行組織，形成層次結(jié)構(gòu)。當(dāng)光線進(jìn)行相交測試時(shí)，首先與高層的包圍體進(jìn)行快速測試，若不相交，則直接跳過該包圍體所包含的所有物體，大大減少了光線與物體的相交測試次數(shù)，提高了渲染效率。在渲染山脈場景時(shí)，BVH可以將山脈劃分為多個(gè)層次的包圍體，光線首先與最外層的包圍體進(jìn)行相交測試，如果不相交，則無需對山脈內(nèi)部的大量三角形進(jìn)行測試，從而節(jié)省了大量的計(jì)算時(shí)間。BVH的內(nèi)存占用相對可控。在影視制作中，需要處理海量的場景數(shù)據(jù)，BVH能夠合理地管理內(nèi)存資源，避免內(nèi)存溢出的問題。在處理《阿凡達(dá)》中豐富的特效場景時(shí)，BVH可以預(yù)先計(jì)算所需的內(nèi)存空間，確保在渲染過程中能夠穩(wěn)定地使用GPU內(nèi)存，維持良好的渲染性能。綜合來看，在影視制作中，如《阿凡達(dá)》這樣對渲染質(zhì)量和效率要求極高的項(xiàng)目，BVH加速結(jié)構(gòu)憑借其自適應(yīng)的空間劃分能力、高效的光線遍歷策略以及可控的內(nèi)存占用，能夠更好地滿足影視特效制作對渲染的苛刻要求。雖然均勻柵格和KD-Tree在某些方面也有各自的優(yōu)勢，但在處理復(fù)雜的影視場景時(shí)，BVH的綜合性能更為突出。不同的影視場景和特效需求可能會對加速結(jié)構(gòu)的選擇產(chǎn)生影響。在一些簡單的影視場景中，如一些以對話為主的室內(nèi)場景，均勻柵格的簡單高效可能更具優(yōu)勢；而對于一些對內(nèi)存訪問模式要求不高，但對空間劃分靈活性有一定需求的場景，KD-Tree也可能是一個(gè)合適的選擇。因此，在影視制作中，需要根據(jù)具體的場景和需求，綜合考慮各種因素，選擇最合適的加速結(jié)構(gòu)，以實(shí)現(xiàn)最佳的渲染效果。5.3虛擬現(xiàn)實(shí)與增強(qiáng)現(xiàn)實(shí)在虛擬現(xiàn)實(shí)（VR）與增強(qiáng)現(xiàn)實(shí)（AR）場景中，加速結(jié)構(gòu)對于優(yōu)化圖形渲染、提升用戶體驗(yàn)起著關(guān)鍵作用。以熱門VR游戲《半條命：艾利克斯》為例，該游戲憑借其沉浸式的體驗(yàn)和出色的圖形效果，為玩家?guī)砹饲八从械奶摂M現(xiàn)實(shí)游戲感受，而這背后離不開先進(jìn)的加速結(jié)構(gòu)技術(shù)。在《半條命：艾利克斯》中，玩家置身于充滿細(xì)節(jié)的虛擬世界，如復(fù)雜的城市街道、昏暗的室內(nèi)環(huán)境以及形態(tài)各異的外星生物場景。均勻柵格加速結(jié)構(gòu)在處理這些場景時(shí)，由于其結(jié)構(gòu)簡單，易于在GPU上實(shí)現(xiàn)。在構(gòu)建過程中，均勻柵格通過將三維空間均勻地劃分為大小相等的體素，快速對場景進(jìn)行空間劃分。在光線生成階段，均勻柵格可以利用簡單的算術(shù)運(yùn)算快速定位光線進(jìn)入的體素，開始光線遍歷。在游戲中的