基于GPU交互式光線跟蹤算法的設(shè)計(jì)與實(shí)現(xiàn)

第７卷第３期２００９年９月南京Ｔ程學(xué)院學(xué)報(bào)（自然科學(xué)版）ＪＩｍｍａＩｏｆＶ０１．７，Ｎｏ．３ＦＡｉｌｉｏｎ）Ｓｅｐ．，２００９Ｎａｍｉｎｇｈｒ＊ｌｉｔｕｔｅ?訂１ｈ‘ｈｎ．ｈ唱，ｙ（Ｎａｔｕｒａｌｓ‘‘ｉｅｍ。ｃ文章編號(hào)：１６７２—２５５８（２００９）０３—００６１—０７基于ＧＰＵ交互式光線跟蹤算法的設(shè)計(jì)與實(shí)現(xiàn)陸建勇１，曹雪虹２，焦良葆２（１．南京郵電大學(xué)通信與信息工程學(xué)院，江蘇２．南京工程學(xué)院通信工程學(xué)院，江蘇南京，２１０００３；１南京，２１１６７）摘要：由于（；Ｐｕ并行處理能力和可編程能力的提高，計(jì)算量巨大的光線跟蹤算法在（；Ｐｕ上的實(shí)現(xiàn)成為研究熱點(diǎn)．在ＣＵＤＡ平臺(tái)上驗(yàn)證了Ｆｏｌｅｙ等人所采用的ＫＤ—ｔｒｅｅ加速算法，實(shí)現(xiàn)了交互式光線跟蹤．在圖像分辨率為５１２Ｘ５１２，跟蹤深度為４時(shí)，針對(duì)復(fù)雜場景的渲染速度達(dá)到１５ｆ／ｓ，基本實(shí)現(xiàn)交互式光線跟蹤．關(guān)鍵詞：并行計(jì)算；ＧＰＵ；光線跟蹤；ＫＤ－ｔｒｅｅ；流計(jì)算中圖分類號(hào)：ＴＮ９１ｌ文獻(xiàn)標(biāo)識(shí)碼：ＡＤｅｓｉｇｎａｎｄＩｍｐｌｅｍｅｎｔａｔｉｏｎｏｆＩｎｔｅｒａｃｔｉｖｅＲａｙＴｒａｃｉｎｇＡｌｇｏｒｉｔｈｍＢａｓｅｄｏｎＧＰＵＬＵＪｉａｎ－ｙｏｎ９１，ＣＡＯＸｕｅ?ｈｏｎ９２，ＪＩＡＯＬｉａｎｇ—ｂａ０２（１．ＳｃｈｏｏｌｏｆＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎａｎｄＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，Ｎａｎｊｉｎｇ２１０００３，Ｃｈｉｎａ；ＵｎｉｖｅｒｓｉｔｙｏｆＰｏｓｔｓａｎｄＴｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ，Ｎａ－ｊｉｎｇ２．ＳｃｈｏｏｌｏｆＣｏｍｍｕｎｉｃａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＮａｎｊｉｎＩｎｓｔｉｔｕｔｅｏｆＴｅｃｈｎｏｌｏｇｙ，Ｎａｎｊｉｎｇ２１１１６７，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：ＴｈａｎｋｓａｌｇｏｒｉｔｈｍｏｎｏｎｔｏｔｈｅｉｍｐｒｏｖｅｍｅｎｔｓｏｆｐａｒａｌｌｅｌａｃｏｍｐｕｔａｔｉｏｎｐｏｗｅｒａｎｄｐｒｏｇｒａｍｍｉｎｇａｂｉｌｉｔｉｅｓｏｆＧＰＵ，ｒａｙｓｔｒｕｃｔｕｒｅ，ａｔｒａｃｉｎｇＧＰＵｈａｓｂｅｃｏｍｅｈｅａｔｅｄａｒｅａｏｆｒｅｓｅａｒｃｈ．ＵｓｉｎｇｔｈｅＫＤ—ｔｒｅｅｄａｔａｍｏｄｅｌｓｙｓｔｅｍｉｓｃｏｎｓｔｒｕｃｔｅｄＣＵＤＡｐｌａｔｆｏｒｍａｎｄｐａｒａｌｌｅｌｐｒｏｃｅｓｓｉｎｇｏｆｒａｙｔｒａｃｉｎｇｉｓａｃｈｉｅｖｅｄ．Ｉｎｔｅｒａｃｔｉｖｅｒａｙｔｒａｃｉｎｇａｎｃａｎｂｅａｃｈｉｅｖｅｄｗｈｅｎｉｍａｇｅｒｅｓｏｌｕｔｉｏｎｒａｔｉｏｉｓ５１２Ｘ５１２，ｔｈｅｔｒａｃｉｎｇｄｅｐｔｈ４ａｎｄｉｎｔｅｒａｃｔｉｖｅｒｅｎｄｅｒｉｎｇｒａｔｅ１５ｆ／ｓ．Ｋｅｙｗｏｒｄｓ：ｐａｒａｌｌｅｌｃｏｍｐｕｔｉｎｇ；ＧＰＵ；ｍｙｔｒａｃｉｎｇ；ＫＤ—ｔｒｅｅ；ｓｔｒｅａｍｃｏｍｐｕｔｉｎｇ光線跟蹤是一種真實(shí)感繪制算法，利用光路可逆原理，通過逆向跟蹤光線，生成栩栩如生漂亮非凡的圖像．光線跟蹤算法需要跟蹤每條從視點(diǎn)出發(fā)的光線，其巾涉及到大量的求交測(cè)試運(yùn)算，計(jì)算量非常龐大，因此這一技術(shù)基本是離線處理．隨著光線跟蹤開始最大程度地利用ＣＰＵ技術(shù)的最新進(jìn)步成果，通過硬件的支持來實(shí)現(xiàn)真實(shí)感圖形的顯示，能達(dá)到實(shí)時(shí)交互的速率．目前，提高光線跟蹤算法速度的關(guān)鍵在于提高求交的效率、減少求交的次數(shù)、減少光線條數(shù)以及采用加速的數(shù)據(jù)結(jié)構(gòu)等１１?！浚陙?，隨著ＧＰＵ在并行計(jì)算能力、存儲(chǔ)容量和可編程能力方面的發(fā)展，在ＧＰＵ上實(shí)現(xiàn)交互式光線跟蹤，甚至實(shí)時(shí)光線跟蹤成為研究熱點(diǎn)Ｈ。Ｊ．本文驗(yàn)證了Ｆｏｌｅｙ等人所采用的ＫＤ—ｔｒｅｅ加速算法№］．實(shí)驗(yàn)結(jié)果達(dá)到了交互式光線跟蹤的效果．收稿日期：２００９—０９—０２；修回日期：２００９—１２—０１基金項(xiàng)目：西ｆ】子巾圍研究院資助項(xiàng)目；南京Ｔ程學(xué)院科研基金項(xiàng)目（ＫＸＪ０８１Ｍ２）作者簡介：陸建勇（１９８４一），男，碩十研究生．研究方向?yàn)樾盘?hào)與信息處理．Ｅ?ｌｌｆｌｌａｉ！：Ｉｊｙ．ｈａ＠１６３．ｃｏｒｎ萬方數(shù)據(jù)６２南京工程學(xué)院學(xué)報(bào)（自然科學(xué)版）２００９年９月１相關(guān)工作Ｗｈｉｔｔｅｄ在文獻(xiàn)［７］中指出，渲染方程的計(jì)算時(shí)間中，大于９５％的時(shí)間花費(fèi)在光線與幾何體求交計(jì)算的代碼中．這就意味著光線跟蹤算法中，幾乎所有的計(jì)算都發(fā)生在求交中，而從著色函數(shù)中調(diào)用跟蹤光線函數(shù)能夠以任意順序進(jìn)行，都不會(huì)影響最終的結(jié)果．因此，光線跟蹤的一個(gè)重要的特性就是計(jì)算光線與幾何體求交能以并行的方式執(zhí)行．另外，Ｗａｌｄ在文獻(xiàn)［８］中指出，原則上，隨著能夠執(zhí)行首次光線計(jì)算的處理器的增加，速度上的提升將隨著所使用的ＣＰＵ的數(shù)量呈線性增長．因此，ＧＰＵ上實(shí)現(xiàn)光線跟蹤能大幅度提高運(yùn)算速度．Ｐｕｒｃｅｌｌ【９３和Ｃａｒｒ【ｌ剛等人幾乎同時(shí)提出來第一個(gè)由ＧＰＵ實(shí)現(xiàn)的光線跟蹤算法框架．Ｐｕｒｃｅｌｌ等人提出的光線跟蹤算法將所有的光線跟蹤內(nèi)核都建立在ＧＰＵ之上，包括視線產(chǎn)生器、遍歷器、求交器和著色器．而Ｃａｒｒ等人僅僅把ＧＰＵ作為一個(gè)光線和三角片求交器，將其它的光線跟蹤工作留給ＣＰＵ．這兩種方法的不同之處在于，Ｐｕｒｃｅｌｌ把光線跟蹤的所有處理過稗都在ＧＰＵ上完成，而Ｃａｒｒ等人把光線跟蹤的不同工作分別交由ＣＰＵ和ＧＰＵ處理，所以前者能夠消除岡為ＣＰＵ與ＧＰＵ之間頻繁的數(shù)據(jù)傳輸帶來的損失，但這種方法會(huì)使ＧＰＵ大量處于空閑階段．Ｃａｒｔ等人的方法能夠獲得更高的ＧＰＵ使用率，因?yàn)楣饩€在被發(fā)送到ＧＰＵ之前，已經(jīng)提前在ＣＰＵ上被處理成束，所以內(nèi)在的就已經(jīng)獲得了光線的一致性，但是這種方法會(huì)由于ＣＰＵ—ＧＰＵ之間大量的數(shù)據(jù)傳輸而帶來性能上的損失．為了提高光線和場景的求交速度，對(duì)于ＣＰＵ提出了很多的加速結(jié)構(gòu)．最近，很多這種加速結(jié)構(gòu)己經(jīng)被引入到ＧＰＵ上，常用的三種加速結(jié)構(gòu)為：均勻柵格（ＵｎｉｆｏｒｍＧｒｉｄ），ＫＤ．ｔｒｅｅ和包闈體層次（ＢＶＨ）．均勻柵格是在基于ＧＰＵ光線跟蹤算法中第一個(gè)被使用的加速結(jié)構(gòu)，因?yàn)檫@種結(jié)構(gòu)無論是在構(gòu)造還是在遍歷上都非常的簡單，Ｃｈｒｉｓｔｅｎ，Ｋａｒｌｓｓｏｎ，Ｌｊｕｎｇｓｔｅｄｔ等人都用這種加速結(jié)構(gòu)作為基于ＧＰＵ的光線跟蹤算法的加速結(jié)構(gòu)．但是它的性能同ＣＰＵ上的實(shí)現(xiàn)相比要差．ＫＤ—ｔｒｅｅ被認(rèn)為是ＣＰＵ上對(duì)于光線跟蹤算法而言最快的加速結(jié)構(gòu)，但是ＧＰＵ卻缺少實(shí)現(xiàn)這個(gè)樹的遍歷的堆棧結(jié)構(gòu)．Ｆｏｌｅｙ等人【６１提出了一個(gè)能夠在ＧＰＵ上實(shí)現(xiàn)的ＫＤ—ｔｒｅｅ，并且指出ＫＤ—ｔｒｅｅ的性能超過均勻柵格．斯坦福大學(xué)Ｄａｎｉｅｌ等人…’在Ｆｏｌｅｙ研究的基礎(chǔ)上進(jìn)行了改進(jìn)，采用了Ｐａｃｋｅｔｓ、Ｐｕｓｈ—Ｄｏｗｎ和ｓｈｏｎ．Ｓｔａｃｋ，進(jìn)一步提升了光線跟蹤器的性能．Ｔｈｒａｎｅ等人¨２１提出了ＧＰＵ上的第一個(gè)ＢＶＨ實(shí)現(xiàn)．２ＧＰＵ編程架構(gòu)簡介Ｎｖｉｄｉａ公司針對(duì)ＧＰＵ的通用運(yùn)算，提出的ＧＰＵ與ＣＵＤＡ（ＣｏｍｐｕｔｅＵｎｉｆｉｅｄＤｅｖｉｃｅＡｒｃｈｉｔｅｃｔｕｒｅ，計(jì)算統(tǒng)～設(shè)備體系結(jié)構(gòu)）相結(jié)合進(jìn)行并行運(yùn)算的方法，可以通過片上（Ｏｎ—ｃｈｉｐ）上百個(gè)處理器同步協(xié)作，從而快速解決復(fù)雜的運(yùn)算問題‘‘３】．ＣＵＤＡ是把ＧＰＵ作為并行運(yùn)算設(shè)備進(jìn)行程序發(fā)布和管理運(yùn)算，不需要將計(jì)算映射到圖形應(yīng)用程序接口的硬件和軟件的架構(gòu)．為了實(shí)現(xiàn)這一功能，ＣＵＤＡ定義了相應(yīng)的邏輯架構(gòu)，并于ＧＰＵ設(shè)備相對(duì)應(yīng)，如圖ｌ所示．其中，Ｔｈｒｅａｄ是最小的邏輯運(yùn)算單位，多個(gè)Ｔｈｒｅａｄ組成Ｂｌｏｃｋ．這些Ｔｈｒｅａｄ可以處理相同或不同的運(yùn)算過程，每個(gè)Ｔｈｒｅａｄ在Ｂｌｏｃｋ中有唯一的標(biāo)識(shí)符，通過標(biāo)識(shí)符在程序中進(jìn)行判斷，就可以讓某個(gè)或某些特定位置的數(shù)據(jù)得到相同或不同的運(yùn)算處理．萬方數(shù)據(jù)第７卷第３期陸建勇，等：基于ＧＰＵ交互式光線跟蹤算法的設(shè)計(jì)與實(shí)現(xiàn)圖ｌＣＵＤＡ邏輯架構(gòu)及其與設(shè)備內(nèi)存的對(duì)應(yīng)關(guān)系３算法設(shè)計(jì)３．１架構(gòu)實(shí)驗(yàn)采用如圖２所示的程序架構(gòu)．為避免ＣＰＵ和ＧＰＵ之間的內(nèi)存倒換，在場景構(gòu)建中將讀人的紋理貼圖數(shù)據(jù)以及光線的參數(shù)和加速結(jié)構(gòu)（ＫＤ．ｔｒｅｅ）這些數(shù)據(jù)寫入到紋理內(nèi)存．然后，將這些數(shù)據(jù)作為渲染引擎的輸入．渲染引擎的主要工作流程如圖２右邊框圖所示，包括光線求交、判斷光源可見、計(jì)算光強(qiáng)貢獻(xiàn)以及生成次級(jí)光線后再次進(jìn)行光線求交等，最終通過ｏｐｅｎＧＬ生成效果圖．場景構(gòu)建，ｉｌｌ構(gòu)建ＫＩ）樹紋理拷貝光線生成．ｌｌ１．／渲染引擎＼上＼ｏｐｅｎＧＬ硅爪圖２基于ＧＰＵ的光線跟蹤算法流程圖１）光線的生成．在進(jìn)行光線跟蹤渲染時(shí)，首先要確定視點(diǎn)、觀察方向和視角，并由此確定生成的圖像平面，如圖３（ａ）所示．當(dāng)確定了圖像平面后，根據(jù)圖像分辨率確定像素位置，從而得到初始光線，開始進(jìn)行渲染．本文的初始視點(diǎn)位置、觀察方向由程序輸入；視角選?。叮罚常福?。作為缺省值，視點(diǎn)距離圖像平面的距離為ｌ，其余的兩個(gè)數(shù)值符合三角關(guān)系ｘｄｉｒｅｃｔｉｏｎｌｅｎｇｔｈ：０．５。ｔａｎｆ羋１ｒｉｇｈｔｌ．ｅｎｇｔｈ、二，根據(jù)視點(diǎn)位置、觀察方向、視角和圖像分辨率，可以確定像平面上每個(gè)像素點(diǎn)的位置，再根據(jù)視點(diǎn)位置，可以確定每條初始光線的方向，從而確定初始光線，如圖３（ｂ）所示．２）光線求交．光線牛成后，便使光線在ＫＤ—ｔｒｅｅ巾搜索最近的相交ｉ角片，求出交點(diǎn)坐標(biāo)及光線參數(shù)ｔ．萬方數(shù)據(jù)南京Ｔ程學(xué)院學(xué)報(bào)（自然科學(xué)版）２００９年９月（ａ）視點(diǎn)、觀察方向和像平面（”光線及其參數(shù)（ｆ為參數(shù)）圖３光線的生成３）判斷光源可見性．陰影效果在真實(shí)感圖像的生成和物體位置判斷方面是一個(gè)非常重要的元素，光線跟蹤可以自動(dòng)生成陰影效果．當(dāng)確定光線和ｉ角面的交點(diǎn)后，在光源與交點(diǎn)之問生成探測(cè)光線，并利用ＫＤ—ｔｒｅｅ的求交方法，判斷在交點(diǎn)和光源之間是否有物體遮擋，如有遮擋，則光源對(duì)該像素點(diǎn)的色彩無直接貢獻(xiàn)，否則在計(jì)算像素色彩時(shí)，需要考慮光源的貢獻(xiàn)．由于對(duì)光源貢獻(xiàn)的不同處理，最終渲染的效果自動(dòng)出現(xiàn)陰影．４）計(jì)算光強(qiáng)貢獻(xiàn)．像素點(diǎn)的色彩由光線與場景中物體的交點(diǎn)處材質(zhì)的漫反射分量、鏡面反射分量和環(huán)境分量組成．光線每反射一次便需計(jì)算一次交點(diǎn)處的顏色值，這樣經(jīng)過多次反射后，像素點(diǎn)最終色彩便是多次采樣值的累加．３．２ＫＤ．ｔｒｅｅ加速結(jié)構(gòu)ＫＤ—ｔｒｅｅ是一種空間剖分結(jié)構(gòu)，用一棵二叉樹將場景表示為一個(gè)層次結(jié)構(gòu)，以便于光線快速與ｊ角片求交．ＫＤ—ｔｒｅｅ算法主要包括ＫＤ—ｔｒｅｅ的構(gòu)建和ＫＤ—ｔｒｅｅ的遍歷．３．２．１ＫＤ．ｔｒｅｅ的構(gòu)建一個(gè)ＫＤ—ｔｒｅｅ的創(chuàng)建過程是一個(gè)自頂向下的遞歸的過程：１）輸入整個(gè)場景的三角片集合及包圍盒；２）將整個(gè)場景的所有ｉ角片進(jìn)行預(yù)處理，包括預(yù)先提取和排序，為每個(gè)三角片建立ＡＡＢＢ（ＡｘｉｓＡｌｉｇｎｅｄＢｏｕｎｄｉｎｇＢｏｘ即軸對(duì)稱綁定盒）；３）月ｊ遞歸的方法從ｔ：Ｎ下構(gòu)建ＫＤ．ｔｒｅｅ（重）選擇分割平面，通過計(jì)算最小代價(jià)函數(shù)，用ＳＡＨ找到最佳分割面；②用最佳分割面平面進(jìn)行空間分割；③將圖元對(duì)象分配給左、右子節(jié)點(diǎn)．這個(gè)遞歸過程不斷進(jìn)行，直到達(dá)到選擇的最大的深度值，或者在一個(gè)節(jié)點(diǎn)巾的三角形的數(shù)量小于給定的閾值．Ｈａｒｖａｎ【１４’等人對(duì)基于ＣＰＵ的光線跟蹤算法的加速結(jié)構(gòu)進(jìn)行了比較，得…的結(jié)論是對(duì)于眾多不同類型的測(cè)試場景，平均而青，ＫＤ—ｔｒｅｅ是最快的．Ｈａｒｖａｎ還指出，當(dāng)ＫＤ—ｔｒｅｅ的最大深度為１６、包含的最小的三角形數(shù)量等于２的時(shí)候，性能最優(yōu)．從上述過程可以看ｆ｝｛，在構(gòu)建ＫＤ．ｔｒｅｅ的過程巾，如何選取分割平面的位置對(duì)ＫＤ．ｔｒｅｅ的遍歷時(shí)間有很大影響．ＭａｃＤｏｎａｌｄ提出了基于表面積的最小代價(jià)函數(shù)來評(píng)價(jià)分割平面的ＳＡＨ算法¨５｜，其基本思想是一條光線同一個(gè)子節(jié)點(diǎn)相交的概率，與子節(jié)點(diǎn)中的表面積和父親節(jié)點(diǎn)中的表面積之比成正比．使朋的代價(jià)函數(shù)為萬方數(shù)據(jù)第７卷第３期陸建勇，等：基于ＧＰＵ交互式光線跟蹤算法的設(shè)計(jì)與實(shí)現(xiàn)Ｃ＝ｃ－ｔｒａｙ＋ｐｒｏｂ（ｈｉｔＬ）×ｃｏｓｔ（Ｌ）＋ｐｒｏｂ（ｈｉｔＲ）×ｃｏｓｔ（Ｒ）＝ｃ?ｔｒａｙ＋ＳＡ（Ｌ）×ＴｒｉＣｏｕｎｔ（Ｌ）＋ＳＡ（Ｒ）×ＴｒｉＣｏｕｎｔ（Ｒ）３．２．２ＫＤ－ｔｒｅｅ的遍歷ＫＤ—ｔｒｅｅ的遍歷就是光線在ＫＤ．ｔｒｅｅ中搜索最近的相交的三角片，見圖４，算法的過程為：１）初始化，對(duì)于每條光線，在光線同場景中的包圍體相交的地方，找出參數(shù)范圍［ｔｍｉｎ，ｔｍａｘ］；２）從根節(jié)點(diǎn)開始求交，并求出光線在該根包圍盒的全局跨度區(qū)間［ｓｃｅｎｅ—ｍｉｎ，ｓｃｅｎｅ—ｍａｘ］；３）如果是中間節(jié)點(diǎn)，則通過分割片面將跨度區(qū)間分為［ｔ—ｍｉｎ，ｔ—ｓｐｌｉｔ］和［ｔ—ｓｐｌｉｔ，ｔ—ｍａｘ］兩部分；４）如果光線的跨度區(qū)間橫跨分割片面的兩側(cè)，說明該光線同時(shí)穿過兩個(gè)子包圍盒，則先和第一個(gè)子節(jié)點(diǎn)求交，并將第二個(gè)子節(jié)點(diǎn)壓人堆棧；５）否則，光線和相交的子節(jié)點(diǎn)求交；６）如果該節(jié)點(diǎn)是葉子節(jié)點(diǎn)，光線和該葉子節(jié)點(diǎn)中的所有三角片求交，如果相交則返回交點(diǎn)坐標(biāo)和光線參數(shù)ｔ；７）否則，將堆棧中的子節(jié)點(diǎn)彈出，返回２）．ｓｃｅｎｅｒａｉｎ圖４ＫＤ—ｔｒｅｅ的遍歷４實(shí)驗(yàn)結(jié)果及分析對(duì)３個(gè)復(fù)雜的場景進(jìn)行渲染：Ｒｏｂｏｔｓ、ＬｉｖｉｎｇＲｏｏｍ和Ｋｉｔｃｈｅｎ，如圖５所示．實(shí)驗(yàn)環(huán)境為：１）ＧＰＵ卡采用Ｎｉｖｉｄａ公司的Ｇｅｆｏｒｃｅ＝４；３）光源數(shù)為點(diǎn)光源１個(gè)．ＧＴＸ２６０；２）每根光線的計(jì)算強(qiáng)度為光線遍歷深度圖５ＬｉｖｉｎｇＲｏｏｍ、Ｒｏｂｏｔｓ和Ｋｉｔｃｈｅｎ渲染場景萬方數(shù)據(jù)南京工程學(xué)院學(xué)報(bào)（自然科學(xué)版）２００９年９月本文所指ＧＰＵ上繪制速度，即并行算法所用的渲染時(shí)間，包括了初始光線在ＫＤ．ｔｒｅｅ上的求交時(shí)間、次級(jí)光線的計(jì)算時(shí)間開銷、各次級(jí)光線的求交時(shí)間、初級(jí)及各次級(jí)光線交點(diǎn)的光源可見性判斷開銷、初級(jí)及各次級(jí)光線交點(diǎn)的色彩計(jì)算時(shí)間開銷、各交點(diǎn)的紋理貼圖的時(shí)間等；而Ｄａｎｉｅｌ的并行算法中只包含求交運(yùn)算的時(shí)間，因此，本項(xiàng)目并行算法的實(shí)際求交速度要大于４８．０Ｍｒａｙｓ／ｓ．具體繪制速度見表ｌ，算法效率比較見表２．表１不同分辨率、不同場景下光線跟蹤繪制速度表２算法并行效率比較每秒計(jì)算的光線數(shù)ＧＰＵ跟蹤器Ｋｉｔｃｈｅｎ（Ｍｍｙｓ／ｓ）Ｒｏｂｏｔｓ５結(jié)語在Ｆｏｌｅｙ等人提出的ＫＤ－ｔｒｅｅ算法的基礎(chǔ)上，通過對(duì)光線跟蹤并行粒度的分析和設(shè)計(jì)。在ＧＰＵ上實(shí)現(xiàn)了交互式光線跟蹤算法．在Ｇｅｆｏｒｃｅ前，在ｌ０２４×ｌＧＴＸ２６０上，圖像分辨率為５１２×５１２時(shí)場景處理速度約為１５￡／ｓ．目０２４分辨率上尚未能達(dá)到實(shí)時(shí)交互的要求，主要瓶頸在于ＧＰＵ與ＣＰＵ之間的數(shù)據(jù)通信．這需要對(duì)算法進(jìn)行進(jìn)一步的改進(jìn)和并行粒度的優(yōu)化設(shè)計(jì)．參考文獻(xiàn)：［１］ＡＮＤＲＥＷＳＧ．ＡｎＩｎｔｒｏｄｕｃｔｉｏｎｔｏＲａｙＴｒａｃｉｎｇ［Ｍ］．Ｌｏｎｄｏｎ：ＡｃａｄｅｍｉｃｒｅｎｄｅｒｉｎｇｕｓｉｎｇＰｒｅｓｓＬｉｄ．，１９８９．［２］ＢＲＵＣＥＷ，ＧＥＯＲＧＥＤ，ＳＴＥＶＥＮＰ．Ｉｎｔｅｒａｃｔｉｖｅｔｈｅｒｅｎｄｅｒｃａｃｈｅ［ｃ］／／ＡＣＭＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅＰｒｏｃｅｅｄｉｎｇ：１０．Ａｉｒｅ—ｌａ—Ｖｉｌｌｅ：Ｅｕｒｅ目ｍｐｈｉｃｓＡｓｓｏｃｉａｔｉｏｎ．１９９９：２３５—２．４６．［３】ＢＲＵＣＥＷ。ＧＥＯＲＧＥＤ，ＤＯＮＡＬＤＰＧ．ＥｎｈａｎｃｉｎｇａｎｄＡｉｒｅ—ｌａ－Ｖｉｌｌｅ：ＥｕｒｏｇｒａｐｈｉｅｓＡｓｓｏｃｉａｔｉｏｎ．２００２：３７—４２．ｏｐｔｉｍｉｚｉｎｇｔｈｅｒｅｎｄｅｒｃａｃｈｅ［ｃ］／／ＡＣＭＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅＰｒａｃｅｅｄｉｎｇ：２８．［４］ＳＴＥＶＥＮＰ。ＭＩＣＨＡＥＬＰ．ＩｎｔｅｒａｃｔｉｖｅＰａｙＴｒａｃｉｎｇｆｏｒＬａｒｇｅＶｏｌｕｍｅＶｉｓｕａｌｉｚａｔｉｏｎ［ｃ］／／ＩＥＥＥＴｒａｎｓａｃｔｉｏｎｓｏｎｃｏｍｐｕｔｅｒｇｒａｐｈｉｃｓａｎｄｖｉｓｕａｌ．ｉｚａｔｉｏｎ。２００３．５：１—１３．［５］ＩＮＧＯＷ．Ｒｅａｌ－ｔｉｍｅＲａｙＴｒａｃｉｎｇａｎｄＩｎｔｅｒａｃｔｉｖｅＧｌｏｂａｌＩｌｌｕｍｉｎａｔｉｏｎ［Ｄ］．Ｓａｒｒｌａｎｄ：ＳａａｒｌａｎｄＵｎｉｖｅｒｓｉｔｙ，２００４．［６］ＦＯＬＥＹＴ，ＳＵＧＥＲＭＡＮＪ．ＫＤ．ｔｒｅｅａｃｃｅｌｅｒａｔｉｏｎｓｔｒｕｃｔｕｒｅｓｆｏｒ８ＧＰＵｒａｙｔｒａｃｅｒ［ｃ］／／ＰｒｏｃｅｅｄｉｎｇｓｏｆｔｈｅＡＣＭＳＩＧＧＲＡＰＨ／ＥＵＲＯ．ＧＲＡＰＨＩＣＳｃｏｎｆｅｒｅｎｃｅｏｎＧｒａｐｈｉｃｓｈａｌｄｗａｌ℃．ＮｅｗＹｏｒｋ：ＡＣＭＰｒｅ∞．２００５：１５－２２．ｍｏｄｅｌｆｏｒ［７】ＴＵＲＮＥＲＷ．Ａｎｉｍｐｒｏｖｅｄｉｌｌｕｍｉｎａｔｉｏｎｓｈａｄｅｄｄｉｓｐｌａｙ［Ｊ］．ＣｏｍｍｕｎＡＣＭ，１９８０，２３（６）：３４３—３４９．萬方數(shù)據(jù)第７卷第３期陸建勇，等：基于ＧＰＵ交互式光線跟蹤算法的設(shè)計(jì)與實(shí)現(xiàn)６７［８】ＩＮＧＯＷ，ＣＡＲＳＴＥＮＢ．Ｉｎｔｅｒａｃｔｉｖｅｒｅｎｄｅｒｉｎｇｗｉｔｈｃｏｈｅｒｅｎｔｍｙｔｒａｃｉｎｇ［Ｊ］．ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓＦｏｎｎｎ。２００１，２０（３）：１５３—１６４．［９】ＴＩＭＯＴＨＹＪＰ，ＩＡＮＢ，ＷＩＬＬＩＡＭＢＭ，ｅｔａ１．ＲａｙｔｒａｃｉｎｇｏｎｐｒｏｇｒａｍｍａｂｌｅｇｒａｐｈｉｃｓｈｕｌｄｗＡｌ．ｅ［Ｊ］．ＡＣＭＴｍｒｍａｃｔｉｏｎｓｏｎＧｒａｐ