營(yíng)員交流長(zhǎng)郡中學(xué)

1、3D圖像引擎初探長(zhǎng)郡中學(xué) 梁盾 沈業(yè)基前言半個(gè)世紀(jì)多以來(lái)，計(jì)算機(jī)硬件發(fā)展速度極快想必大家應(yīng)該都認(rèn)識(shí)這位計(jì)算機(jī)界的“老爺爺”Eniac前言還記得小時(shí)候第一次買電腦，玩了好久的游戲就是這個(gè)前言現(xiàn)在很多大型3d游戲，畫面十分驚艷前言以假亂真的電影畫面硬件在進(jìn)步CpuGpuMx400/440算法也在進(jìn)步幾個(gè)大名鼎鼎的圖像引擎：Frostbite 2.0（寒霜）Unreal Engine 3（虛幻）CryENGINE 3.思考我們作為對(duì)“算法”和“數(shù)據(jù)結(jié)構(gòu)”相當(dāng)熟悉的OIer，雖然做題比較行，但我們似乎并不太熟悉這些與生活聯(lián)系相當(dāng)緊密的東西。剛才展示一些3D電影中出現(xiàn)的圖片中那些以假亂真的渲染效果到底是

2、怎么做出來(lái)的呢？那些高效而又逼真的3D圖像引擎到底是怎么實(shí)現(xiàn)的呢？解惑我向?qū)?D引擎方面比較有研究的劉汝佳老師問(wèn)了這個(gè)問(wèn)題，得到了如下答復(fù)：3D電影可以用大量時(shí)間使用離線算法得到最好的效果，例如光線追蹤、光子映射等算法；而3D引擎由于對(duì)效率要求很高，所以一般會(huì)退而求其次地采用一些雖然不盡符合物理規(guī)律，但實(shí)際效果還不錯(cuò)的算法，如法線貼圖、Z-Buffer等算法。解惑可以看出離線渲染和在線渲染各有側(cè)重，各有千秋下面我將分離線渲染和在線渲染兩方面與大家交流交流離線渲染光線追蹤由于光路可逆原理，我們可以從眼睛發(fā)射出若干條射線來(lái)反著尋找我們看到的物體。具體而言，就是對(duì)于屏幕上的每一個(gè)像素，我們引一條從眼

3、睛射向這個(gè)點(diǎn)的射線，模擬這條射線的運(yùn)動(dòng)軌跡直到得到這個(gè)像素最后是什么樣子。光線追蹤在簡(jiǎn)單情況下，所有物體既不反射光也不透明，則每當(dāng)射線碰到一個(gè)物體時(shí)，我們可以直接計(jì)算這個(gè)物體的顏色。而光線追蹤最nb的地方在于可以處理反射與折射的情況如果射線碰到了一個(gè)反射性物體，我們發(fā)出一條新的反射光線，從碰撞點(diǎn)射出，指向 碰撞表面的外部。同理，如果射線碰到了一個(gè)透明物體，我們派生出一條新的折射光線，從碰撞點(diǎn)射出，指向碰撞表面的內(nèi)部。如果 碰撞面兩側(cè)的物體的折射系數(shù)不同，則光線的方向?qū)l(fā)生改變。光線追蹤處理每條射線的過(guò)程偽代碼如下：(LRJ老師提供)光線追蹤優(yōu)勢(shì)：對(duì)于鏡面、玻璃和水面，光線追蹤可以渲染出相當(dāng)華麗

4、的效果劣勢(shì)：速度比較慢，隨著場(chǎng)景中的物體個(gè)數(shù)增加，算法消耗的時(shí)間會(huì)急速增長(zhǎng)初步成果實(shí)現(xiàn)其實(shí)說(shuō)白了這就是一道很普通的計(jì)算幾何題，計(jì)算幾何題往往實(shí)現(xiàn)才是其關(guān)鍵LRJ老師的那道題就是UVa12313，大家可以考慮沒(méi)事的時(shí)候自己去做一做下面我講講我自己的實(shí)現(xiàn)方法，如果大家有更好的實(shí)現(xiàn)方法就上來(lái)一起交流交流吧。實(shí)現(xiàn)創(chuàng)建三維向量類：struct pointdouble x,y,z;P operator +(P a,P b) return P(a.x+b.x,a.y+b.y,a.z+b.z); /向量加法P operator -(P a,P b) return P(a.x-b.x,a.y-b.y,a.z-b

5、.z); /向量減法P operator *(P a,double b) return P(a.x*b,a.y*b,a.z*b); /數(shù)乘P operator /(P a,double b) return a*(1/b); /還是數(shù)乘P operator *(P a,P b) return P(a.y*b.z-a.z*b.y,a.z*b.x-b.z*a.x,a.x*b.y-a.y*b.x);/三維叉積double operator /(P a,P b) return a.x*b.x+a.y*b.y+a.z*b.z; /點(diǎn)積double mo(P a) return sqrt(a.x*a.x+a

6、.y*a.y+a.z*a.z); /模其中比較關(guān)鍵的是三維叉積，他可以返回和這兩個(gè)向量垂直的另一個(gè)向量。實(shí)現(xiàn)創(chuàng)建三維面類：struct P f,double s表示的就是(x*f.x + y*f.y + z*f.z = s)這樣子的一個(gè)面，f的實(shí)際意義就是這個(gè)面的法向量，為了使得下面的計(jì)算變得簡(jiǎn)便，我們把f的模變成一。假設(shè)我們要求點(diǎn)a到面b的距離，直接a/b.f-b.s即可，其中“/”為向量點(diǎn)積有了以上這些過(guò)程以后，寫起來(lái)就方便多了。實(shí)現(xiàn)色彩的合成與明暗：Lambertian著色法（也叫余弦著色法）： 即根據(jù)碰撞表面的法線和從碰撞點(diǎn)到光源的向量的點(diǎn)積計(jì)算亮度。當(dāng)夾角增大時(shí)，亮度按照余弦函數(shù)減小

7、。這么做的目的是為了讓模型更加有立體感。實(shí)現(xiàn)實(shí)現(xiàn)很難嗎？不，代碼量比殺菌計(jì)劃還要小一點(diǎn)！最麻煩的地方：1.求射線與面的交點(diǎn)；2.處理射線反射與折射；不擔(dān)心常數(shù)的話可以使用高斯消元，擔(dān)心常數(shù)的話拿出你的筆和紙用力算吧如果大家有興趣實(shí)現(xiàn)的話建議先完成殺菌計(jì)劃。遺留的一個(gè)問(wèn)題代碼實(shí)現(xiàn)出來(lái)了，但是我們?cè)趺礃訉D片輸出出來(lái)呢？會(huì)python的同學(xué)可以直接使用PIL來(lái)處理，只用c+的話這里我們可以觀摩一下范浩強(qiáng)神牛曾經(jīng)寫過(guò)的光線追蹤算法。BMP或者PNG都是位圖文件，我們可以直接把他當(dāng)做二進(jìn)制文件讀取并且修改。詳細(xì)資料： 具體實(shí)現(xiàn)： 優(yōu)化觀察這個(gè)圖，我們會(huì)發(fā)現(xiàn)幾個(gè)問(wèn)題：鋸齒嚴(yán)重?zé)o法處理光的輝映、焦散的情況

8、優(yōu)化怎樣抗鋸齒呢？最樸素的方法就是直接把原來(lái)的一個(gè)像素分成n*n個(gè)像素，最后這個(gè)點(diǎn)的顏色就是n*n個(gè)像素顏色的平均值，如下對(duì)比圖：N越大，效果就越好，但渲染時(shí)間也越長(zhǎng)。一般游戲里設(shè)置的幾級(jí)抗鋸齒，我猜大概就是N有多大的意思吧。優(yōu)化解決光的輝映、焦散的情況。實(shí)際上這個(gè)問(wèn)題難以解決，需要用到另外一個(gè)算法：光子映射。介于本人水平。研究這個(gè)算法的任務(wù)就交給大家吧！有興趣的同學(xué)請(qǐng)自行wiki或者百度。幾張高清成品圖花費(fèi)了大量時(shí)間進(jìn)行參數(shù)修改，最終完成了幾張自己覺得還行的作品，誠(chéng)邀大家圍觀 _ 在線渲染雖然光線追蹤渲染出來(lái)的畫面挺不錯(cuò)的，但是花費(fèi)的時(shí)間相當(dāng)長(zhǎng)，比如前幾頁(yè)的圖片，每張圖片差不多要兩分鐘才能運(yùn)

9、算完成，當(dāng)然，我寫丑了也是很大的原因= =即使是寫得相當(dāng)優(yōu)異的光線追蹤算法，也達(dá)不到在線渲染的要求，頂多在部分場(chǎng)景的關(guān)鍵部位使用少量的光線追蹤算法。在線渲染這里我們可以大致的計(jì)算一下在線渲染的復(fù)雜度要求：每秒30幀，分辨率1440*900，因此每秒需要計(jì)算的像素個(gè)數(shù)為38880000，每個(gè)像素差不多需要O(1)出解！這似乎非常困難在線渲染這里我向大家介紹一下z-buffer算法，中文叫做“深度緩沖”，實(shí)際上偽代碼相當(dāng)簡(jiǎn)單：For 場(chǎng)景中的每一個(gè)物體 For 這個(gè)物體在屏幕上可能顯示的每一個(gè)像素 if 從這個(gè)像素看到的這個(gè)物體不會(huì)被別的物體擋住 then 計(jì)算這個(gè)點(diǎn)的顏色可以發(fā)現(xiàn)，這個(gè)算法的復(fù)雜

10、度是O(n+sigma(每個(gè)物體在屏幕上顯示的 像素個(gè)數(shù))雖然在某些情況下這個(gè)算法甚至?xí)裙饩€追蹤還要慢，但是真實(shí)場(chǎng)景都是相當(dāng)迅速的在線渲染觀察z-buffer算法的偽代碼可以發(fā)現(xiàn)他的優(yōu)缺點(diǎn)。優(yōu)點(diǎn)：速度快缺點(diǎn)：無(wú)法處理陰影，折射和反射在線渲染由于需要體現(xiàn)出在線的速度，我仿照現(xiàn)在的第一人稱射擊類游戲，使得攝像機(jī)可以通過(guò)WASD和鼠標(biāo)來(lái)控制攝像機(jī)在場(chǎng)景內(nèi)部移動(dòng)。為了實(shí)現(xiàn)這些交互式功能，我使用的開發(fā)平臺(tái)是QT在線渲染Z-buffer算法不負(fù)眾望，在進(jìn)過(guò)了一些常數(shù)優(yōu)化以后，對(duì)于一個(gè)有30個(gè)三角形的場(chǎng)景可以輕易的達(dá)到50fps！雖然畫面稍遜，并且但是我們可以在場(chǎng)景內(nèi)部移動(dòng)了！在線渲染但是，劉汝佳老師給了

11、我一個(gè)場(chǎng)景內(nèi)有70000個(gè)三角形的兔子高模！70000多個(gè)三角形的計(jì)算已經(jīng)讓我的小程序跑得氣喘吁吁，幀數(shù)直接降到15，嚴(yán)重影響動(dòng)畫的流暢性優(yōu)化這是一個(gè)艱巨的任務(wù)，我不斷的更新程序，將常數(shù)優(yōu)化加到山窮水盡，幀數(shù)也僅僅提升到了20幀，而人眼至少需要30幀才不會(huì)感覺到卡頓繼續(xù)優(yōu)化的空間在哪里？看了看自己筆記本上的intel core標(biāo)志，反映了過(guò)來(lái)：多線程優(yōu)化！優(yōu)化想必大家平時(shí)都發(fā)現(xiàn)到：自己的程序cpu占用量總是只有1/芯片線程數(shù)，怎樣才可以利用到cpu的全部力量呢？答案就是多線程。C/C+可以使用fork()來(lái)使得自己的程序變成多進(jìn)程，所以在noi等比賽中都是嚴(yán)令禁止使用fork。這里我直接使用了qt中的qthread類，方便多線程管理優(yōu)化考慮到現(xiàn)在大部分電腦的芯片線程個(gè)數(shù)沒(méi)有超過(guò)8，所以我創(chuàng)建了8個(gè)線程來(lái)運(yùn)算。多線程優(yōu)化的大致思路就是把這n個(gè)三角形的運(yùn)算平均分給8個(gè)進(jìn)程來(lái)進(jìn)行運(yùn)算，最后在使用主進(jìn)程來(lái)整合8個(gè)進(jìn)程的運(yùn)算結(jié)果。優(yōu)化結(jié)果相當(dāng)可喜可賀，下表是添加了多線程優(yōu)化的效果，大家觀察這個(gè)表格，可以發(fā)現(xiàn)多線程優(yōu)化是相當(dāng)給力的！之所以fps不隨線程數(shù)線性增長(zhǎng)，是因?yàn)橹鬟M(jìn)程整合所有線程的運(yùn)算結(jié)果也是瓶頸之一使用線程數(shù)1248平均fps25