營員交流長郡中學(xué)

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

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

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

4、的效果劣勢：速度比較慢，隨著場景中的物體個數(shù)增加，算法消耗的時間會急速增長初步成果實(shí)現(xiàn)其實(shí)說白了這就是一道很普通的計算幾何題，計算幾何題往往實(shí)現(xiàn)才是其關(guān)鍵LRJ老師的那道題就是UVa12313，大家可以考慮沒事的時候自己去做一做下面我講講我自己的實(shí)現(xiàn)方法，如果大家有更好的實(shí)現(xiàn)方法就上來一起交流交流吧。實(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)鍵的是三維叉積，他可以返回和這兩個向量垂直的另一個向量。實(shí)現(xiàn)創(chuàng)建三維面類：struct P f,double s表示的就是(x*f.x + y*f.y + z*f.z = s)這樣子的一個面，f的實(shí)際意義就是這個面的法向量，為了使得下面的計算變得簡便，我們把f的模變成一。假設(shè)我們要求點(diǎn)a到面b的距離，直接a/b.f-b.s即可，其中“/”為向量點(diǎn)積有了以上這些過程以后，寫起來就方便多了。實(shí)現(xiàn)色彩的合成與明暗：Lambertian著色法（也叫余弦著色法）： 即根據(jù)碰撞表面的法線和從碰撞點(diǎn)到光源的向量的點(diǎn)積計算亮度。當(dāng)夾角增大時，亮度按照余弦函數(shù)減小

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

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

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

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

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