真實(shí)感圖形生成第一頁，共七十五頁，2022年，8月28日真實(shí)感圖形生成的步驟場景造型取景變換、透視投影視域裁剪、消除隱藏面光亮度計算

第二頁，共七十五頁，2022年，8月28日光亮度計算1．依據(jù)：光照明模型局部光照明模型：朗伯模型、Phong模型整體光照明模型：Whitted模型，光能輻射度方程（隱式）追求目標(biāo)：光照效果的真實(shí)感

第三頁，共七十五頁，2022年，8月28日掃描線方法光線跟蹤方法光能輻射度方法追求目標(biāo)：畫面生成的實(shí)時性

2．計算方法：繪制算法第四頁，共七十五頁，2022年，8月28日本講座內(nèi)容一、光照明模型的基本原理二、快速光線跟蹤算法1.平行2n面包圍盒算法2.空間分割算法

三、光能輻射度方法1.形狀因子計算2.逐步求精算法

第五頁，共七十五頁，2022年，8月28日一、光照明模型的基本原理1.概述視覺的形成物體的顏色漫反射和鏡面反射第六頁，共七十五頁，2022年，8月28日2．Phong光照明模型為計算方便，鏡面高光分量可改寫成:漫反射分量泛光鏡面高光分量LiNRiViθiθiPHi第七頁，共七十五頁，2022年，8月28日3．光度學(xué)的基本概念光通量：單位時間內(nèi)通過某一面積的光能量發(fā)光強(qiáng)度：沿給定方向單位立體角發(fā)出的光通量光亮度：面光ds沿給定方向的光亮度為在該方向上單位投影面積的發(fā)光強(qiáng)度照度:單位面積表面所接受的光通量第八頁，共七十五頁，2022年，8月28日朱一寧模型

目標(biāo)：計算面元dSj朝觀察者方向v的光亮度,先計算dSj所接受來自周圍環(huán)境的入射光能jjiNiSidjNjdiSjdSjdSir第九頁，共七十五頁，2022年，8月28日由dSi發(fā)出并到達(dá)dSj的光通量為：面元dSj所接受的照度:第十頁，共七十五頁，2022年，8月28日到達(dá)dSj的光能除一部分被表面吸收外，大部分通過反射和折射繼續(xù)向空間輻射。令K為光通量輻射比，D為未被吸收的光能向空間任一方向立體角輻射的概率密度，則dSj朝觀察者方向內(nèi)輻射的光能為:第十一頁，共七十五頁，2022年，8月28日dSj朝觀察者方向的光亮度為:dVNθdSi第十二頁，共七十五頁，2022年，8月28日設(shè)對dSj有光能貢獻(xiàn)的發(fā)光面元集合為S，則表面朝V方向的光亮度為:第十三頁，共七十五頁，2022年，8月28日第十四頁，共七十五頁，2022年，8月28日當(dāng)D取不同的分布函數(shù)時，可得朗伯模型，Phong模型，Cook-Torrance模型……

當(dāng)S取發(fā)光面元集合時得各種局部光照明模型；當(dāng)S包括所有周圍環(huán)境表面時，可得整體光照明模型當(dāng)S取不同的幾何形狀時，可得線光源光照模型和面光源光照模型第十五頁，共七十五頁，2022年，8月28日第十六頁，共七十五頁，2022年，8月28日二、快速光線跟蹤1.光線跟蹤的基本原理問題：1）如何尋找B，D：光線跟蹤2）如何計算IB，ID：遞歸過程3）受遮擋時的計算：陰影測試

眼睛

第十七頁，共七十五頁，2022年，8月28日光線跟蹤終止條件光線射出畫面，不再與場景中的景物相交被跟蹤的結(jié)點(diǎn)對屏幕象素顯示光亮度的貢獻(xiàn)小于一定閾值達(dá)到光線跟蹤的最大深度第十八頁，共七十五頁，2022年，8月28日算法描述1．由視點(diǎn)向屏幕上所有象素中心發(fā)射光線；2．每一根光線與場景中所有景物求交，找到最近的交點(diǎn)；3．計算該點(diǎn)處由光源直接照射產(chǎn)生的光亮度Il；4．若該點(diǎn)處表面為鏡面或透射面，則作遞歸光線跟蹤，計算周圍環(huán)境通過該點(diǎn)向觀察者方向投射的整體鏡面反射光亮度Ir和透射光亮度It；5．顯示每一象素處的光亮度第十九頁，共七十五頁，2022年，8月28日算法分析：1．求交計算量占整個光線跟蹤計算量90%以上減少求交計算量的方法包圍盒方法空間剖分方法2．點(diǎn)采樣容易導(dǎo)致畫面走樣 方法：自適應(yīng)超級采樣基于層次包圍盒的快速光線跟蹤算法第二十頁，共七十五頁，2022年，8月28日2.基于層次包圍盒的快速光線跟蹤算法包圍盒：以簡單的測試代替光線對包圍盒內(nèi)所含景物的復(fù)雜求交運(yùn)算目標(biāo)：快速剔除不交的物體對包圍盒形狀的要求：包裹要緊密求交測試要簡便第二十一頁，共七十五頁，2022年，8月28日平行2n面包圍盒優(yōu)點(diǎn)：多面體可以較緊密地逼近一個物體平面求交計算較為簡單表示方法：平面方程Ax+By+Cz-d=0其中d表達(dá)了平面與原點(diǎn)之間的距離為節(jié)省存貯量，平面法向A，B，C隱含表示同一景物的三種平行包圍體(a)(b)(c)第二十二頁，共七十五頁，2022年，8月28日景物的平行2n面包圍盒的確定 —確定各平行面的d值1）多面體的平行2n面包圍盒設(shè)幾何造型變換矩陣為M（3×3），平移矢量為T將變換后頂點(diǎn)矢量投影到平面法矢上對于一組平行平面第二十三頁，共七十五頁，2022年，8月28日2）隱函數(shù)曲面的平行2n面包圍盒 隱函數(shù)曲面曲面上任一點(diǎn)投影到包圍盒平面法矢上現(xiàn)欲求在滿足約束條件下的條件極值。運(yùn)用拉格朗日乘數(shù)法可求出第二十四頁，共七十五頁，2022年，8月28日平移矢量T對的影響

——附加一個沿T方向的平移量組合物體的平行2n面包圍盒第二十五頁，共七十五頁，2022年，8月28日光線與包圍盒邊界面的求交給定一光線代入平面方程由于Ni預(yù)先設(shè)定，對于給定光線，a，b為常數(shù)令則（一次減法，一次乘法）第二十六頁，共七十五頁，2022年，8月28日光線與平行2n面包圍盒的求交由于平行2n包圍盒為凸體，只需求光線位于各組平行面之間區(qū)段的交若則光線位于之間的區(qū)段為光線與包圍盒的交第二十七頁，共七十五頁，2022年，8月28日注：算法并行地計算當(dāng)前區(qū)段與前面區(qū)段公共段的交。若無交，則不必再繼續(xù)計算下去。當(dāng)為負(fù)時，光線投射方向與平面法向相反，交換的位置第二十八頁，共七十五頁，2022年，8月28日場景的層次包圍盒結(jié)構(gòu)求交測試計算量由降至同一層次的結(jié)點(diǎn)按光線與其包圍盒入口點(diǎn)的t值（）排序存入一鏈表中

總是取光線最先進(jìn)入的包圍盒內(nèi)所含景物作進(jìn)一步測試由于鏈表中相鄰結(jié)點(diǎn)的包圍盒可能重迭，只有當(dāng)求得的光線與包圍盒內(nèi)景物交點(diǎn)的t值小于光線與下一相鄰結(jié)點(diǎn)包圍盒入口點(diǎn)的t值時，才能停止進(jìn)一步的求交測試。

光線第二十九頁，共七十五頁，2022年，8月28日基于空間剖分的快速光線跟蹤算法將空間劃分為網(wǎng)格，光線只與它所穿過的空間網(wǎng)格中所含景物進(jìn)行求交。利用空間網(wǎng)格的鄰接性質(zhì)，引導(dǎo)光線從一個網(wǎng)格進(jìn)入它將穿過的下一網(wǎng)格。一旦發(fā)現(xiàn)光線與景物的第一個交點(diǎn)，即結(jié)束求交。第三十頁，共七十五頁，2022年，8月28日現(xiàn)有的空間分割光線跟蹤算法3DDDA算法將空間劃分為均勻的立方體網(wǎng)格，利用光線的線性幾何，采用增量算法，求得光線與當(dāng)前網(wǎng)格的出口點(diǎn)，并直接查取光線進(jìn)入的下一網(wǎng)格。

問題：1.不適合于景物分布稀疏的場景2.占用大量存貯空間第三十一頁，共七十五頁，2022年，8月28日Glassner算法將空間按景物實(shí)際分布劃分成八叉樹結(jié)構(gòu)，每一網(wǎng)格僅包含一定數(shù)量的景物表面，空網(wǎng)格不再細(xì)分。求出光線與當(dāng)前空間網(wǎng)格出口點(diǎn)的t值，再向前移動Δt，生成光線位于下一網(wǎng)格內(nèi)的一點(diǎn)（x，y，z）。利用Hash查找技術(shù)，找到包含這一點(diǎn)的下一八叉樹網(wǎng)格。

問題：1.求下一網(wǎng)格定位點(diǎn)涉及9次乘法2.存貯全部八叉樹結(jié)點(diǎn)，包括空網(wǎng)格結(jié)點(diǎn)第三十二頁，共七十五頁，2022年，8月28日空間索引算法采用線性八叉樹結(jié)構(gòu)存貯包含景物面片的空間八叉樹結(jié)點(diǎn)，占用存貯小。采用啟發(fā)式方法求取光線與當(dāng)前網(wǎng)格出口點(diǎn)，大大減少了計算量。利用線性八叉樹結(jié)點(diǎn)編碼性質(zhì)，直接由出口點(diǎn)查找下一空間網(wǎng)格。第三十三頁，共七十五頁，2022年，8月28日問題：如何快速求取光線與當(dāng)前空間網(wǎng)格的出口點(diǎn)？思路：根據(jù)光線的前進(jìn)方向，優(yōu)先選取最有可能與光線相交的網(wǎng)格邊界面與光線進(jìn)行求交測試。為此引入光線前進(jìn)主方向，次方向，第三方向概念，其相應(yīng)坐標(biāo)分量分別以L、S、T標(biāo)識，顯然光線從垂直于主方向的空間網(wǎng)格邊界面出口的可能性最大，應(yīng)優(yōu)先測試第三十四頁，共七十五頁，2022年，8月28日若光線沿主方向邊界面射出，出口點(diǎn)應(yīng)位于邊界面正方形內(nèi)即設(shè)出口點(diǎn)為IP則第三十五頁，共七十五頁，2022年，8月28日若則光線沿次方向邊界面射出否則光線可能沿次方向或第三方向邊界面射出取S-T坐標(biāo)系算出：第三十六頁，共七十五頁，2022年，8月28日否則光線沿第三方向邊界面射出第三十七頁，共七十五頁，2022年，8月28日問題：如何高效查找光線將要進(jìn)入的下一空間網(wǎng)格？思路：利用線性八叉樹結(jié)點(diǎn)的編碼性質(zhì)，確定下一相鄰網(wǎng)格第三十八頁，共七十五頁，2022年，8月28日沿x軸正向，相鄰兄弟結(jié)點(diǎn)編碼增加1沿y軸正向，相鄰兄弟結(jié)點(diǎn)編碼增加2沿z軸正向，相鄰兄弟結(jié)點(diǎn)編碼增加4線性八叉樹結(jié)點(diǎn)的編碼方式將一空間沿x，y，z中分面一分為八01134576xyz第三十九頁，共七十五頁，2022年，8月28日設(shè)立方體空間為，該空間中任一Voxel結(jié)點(diǎn)編碼為為八進(jìn)制數(shù)，紀(jì)錄了對空間第i次分割時，含該Voxel的子結(jié)點(diǎn)在其父結(jié)點(diǎn)中的方位。表示一個只分割到第i層的空間結(jié)點(diǎn)，子空間邊長為。第四十頁，共七十五頁，2022年，8月28日八叉樹結(jié)點(diǎn)的原點(diǎn)坐標(biāo)與其結(jié)點(diǎn)編碼的關(guān)系設(shè)某一八叉樹結(jié)點(diǎn)編碼為且則其局部原點(diǎn)坐標(biāo)為：反過來，若已知某一八叉樹結(jié)點(diǎn)的局部原點(diǎn)坐標(biāo)，則可推導(dǎo)出其線性八叉樹結(jié)點(diǎn)（Voxel）編碼第四十一頁，共七十五頁，2022年，8月28日線性八叉樹結(jié)點(diǎn)按編碼順序以線性鏈表方式存貯。結(jié)點(diǎn)的父子、兄弟鄰接關(guān)系反映在編碼上，同胞兄弟的結(jié)點(diǎn)具有相同的前綴。第四十二頁，共七十五頁，2022年，8月28日由出口點(diǎn)查找下一空間網(wǎng)格的步驟1.首先由出口點(diǎn)確定下一空間網(wǎng)格的局部坐標(biāo)原點(diǎn)（先假定Voxel結(jié)點(diǎn)）對Ip[L],Ip[S],Ip[T]分別取整得O[L,S,T]若step[L]<0且光線沿L方向邊界面入口,O[L]=O[L]-1若step[S]<0且光線沿S方向邊界面入口,O[S]=O[S]-1若step[T]<0且光線沿T方向邊界面入口,O[T]=O[T]-1第四十三頁，共七十五頁，2022年，8月28日對原點(diǎn)坐標(biāo)進(jìn)行分解、拼合，求出其最小的Voxel結(jié)點(diǎn)編碼則，其中第四十四頁，共七十五頁，2022年，8月28日搜索場景空間線性八叉樹，找出包含此Voxel的八叉樹結(jié)點(diǎn)全部數(shù)碼相同，該結(jié)點(diǎn)為一Voxel結(jié)點(diǎn)求光線與Voxel內(nèi)所含景物的交點(diǎn)

部分?jǐn)?shù)碼相同，下一未匹配數(shù)碼為F此結(jié)點(diǎn)為Voxel的祖先，包含該Voxel，且為終結(jié)點(diǎn)，求光線與該結(jié)點(diǎn)內(nèi)所含景物的交第四十五頁，共七十五頁，2022年，8月28日部分?jǐn)?shù)碼相同，但下一未匹配數(shù)不是F設(shè)匹配部分編碼為，則結(jié)點(diǎn)為包含該Voxel的最大空結(jié)點(diǎn)，求光線對該空結(jié)點(diǎn)網(wǎng)格的出口點(diǎn)。如何構(gòu)造場景的空間線性八叉樹（略）第四十六頁，共七十五頁，2022年，8月28日第四十七頁，共七十五頁，2022年，8月28日三、光能輻射度方法1．漫射場景的光能輻射度方程假定場景為一封閉的理想漫反射環(huán)境對于場景中任一面片j,Bj=Ej+ρjHj其中：為面片j向四周輻射的總的輻射度為面片j向外均勻發(fā)射的光能為面片j的漫反射系數(shù)為面片j從周圍環(huán)境接受的總的光能

第四十八頁，共七十五頁，2022年，8月28日現(xiàn)在考慮如何計算:是周圍環(huán)境其它面片輻射度()的函數(shù)，面片i向四周輻射的總的光能為BiAi,其中一部分到達(dá)面片j，記為BiAiFij，到達(dá)面片j單位面積上的光能為BiAiFij/Aj，故第四十九頁，共七十五頁，2022年，8月28日Fij的計算

Fij稱為面片i對面片j的形狀因子，

現(xiàn)在考慮面元dAi對面元dAj的形狀因子，面元dAi向四周輻射的總的光能BidAi在無遮擋的情況下，面元dAi向面元dAj的輻射的光能為第五十頁，共七十五頁，2022年，8月28日由定義

對Aj積分得對Ai取平均，即第五十一頁，共七十五頁，2022年，8月28日推論:1．

即故（標(biāo)準(zhǔn)輻射度方程）2．

3．標(biāo)準(zhǔn)輻射度方程兩端同除以，得場景各面片的光亮度方程

第五十二頁，共七十五頁，2022年，8月28日計算形狀因子的半立方體方法形狀因子計算公式的幾何解釋：dAj對單位半球面作中心投影，其投影區(qū)域?yàn)?/p>

該區(qū)域垂直投影到半球的底平面上，其投影面積為與底平面圓面積之比為，即。NiidSiSjSj取Ai的中心點(diǎn)為球心，在Ai上方建立一單位半球面。第五十三頁，共七十五頁，2022年，8月28日引申：對任何在半球面上占據(jù)相同投影區(qū)域的面片Ak，面片Ai對它們具有相同的形狀因子，即

思路：尋找面片Ak，Ak的表面形狀，朝向較為規(guī)范，計算比較容易，從而將Fij的計算轉(zhuǎn)換為Fik的計算。

第五十四頁，共七十五頁，2022年，8月28日最規(guī)范的表面是圍繞Ai，位于Ai上方的半立方體，立方體頂平面與面片Ai的法向垂直。因此，只要將面片Aj投影到半立方體表面上，Ai對其投影面積的形狀因子即為Fij。將半立方體各表面離散為均勻網(wǎng)格，假定每一網(wǎng)格上各點(diǎn)的形狀因子不變。面片Ai對每一網(wǎng)格的形狀因子稱為半立方體表面的微形狀因子。面片Ai對Aj的形狀因子歸結(jié)為兩個問題。第一，確定Aj在半立方體表面上所占網(wǎng)格；第二，計算每一網(wǎng)格的微形狀因子。第五十五頁，共七十五頁，2022年，8月28日確定Aj在半立方體表面上的投影

取景變換和背面標(biāo)志，將Aj變換到以Ai為中心的半立方體局部坐標(biāo)系中。dSiQSjq對Aj作區(qū)域裁剪，以確定它投影到半立方體哪些表面上。 裁剪平面：z=x,z=-x,z=y,z=-y,x=y,x=-y。z-buffer消隱z-buffer中存儲各網(wǎng)格的可見面號，而不是其深度值，故又稱item-buffer。被遮擋的表面形狀因子為零。第五十六頁，共七十五頁，2022年，8月28日xtopxsidezxyAsidezsiderijdSiyside=1ytopztop=1rijAtopqq計算每一網(wǎng)格的形狀因子對于位于半立方體頂面網(wǎng)格第五十七頁，共七十五頁，2022年，8月28日對于位于半立方體側(cè)面網(wǎng)格（以左側(cè)面為例）由于半立方體表面各網(wǎng)格與其中心的相對方位是固定的，故可預(yù)先將半立方體表面各網(wǎng)格的微形狀因子計算好，存儲在一查找表中備用。

xtopxsidezxyAsidezsiderijdSiyside=1ytopztop=1rijAtopqq第五十八頁，共七十五頁，2022年，8月28日輻射度方程的求解（1）由形狀因子組成的系數(shù)矩陣主對角占優(yōu)，可迭代求解。可取各面片之Ei作為迭代初值，一般迭代6－8次即可收斂。（2）對紅、綠、藍(lán)三原色分別求解輻射度方程（Ej,ρj與光譜分布有關(guān)）。（3）采用插值與平均方法將各面片中心的輻射度轉(zhuǎn)換為各面片頂點(diǎn)處的輻射度。注意：景物面片的輻射度解與視點(diǎn)無關(guān)第五十九頁，共七十五頁，2022年，8月28日畫面繪制選定視點(diǎn)和視線方向，對場景中的景物作取景變換。采用光線投射或掃描線算法，確定屏幕上每一象素中的可見面。采用雙線性插值方法，確定象素中心處表面采樣點(diǎn)的輻射度。畫面顯示。第六十頁，共七十五頁，2022年，8月28日計算量分析例：某畫面包含1740個面片圖1圖2圖3形狀因子計算180min00解輻射度方程10min10min0畫面繪制16min16min16min總計206min26min16min第六十一頁，共七十五頁，2022年，8月28日3.光能輻射度逐步求精算法圖形學(xué)發(fā)展的兩根主線:追求畫面生成的真實(shí)感和實(shí)時性.在追求真實(shí)感方面由線畫圖形->消隱圖形->連續(xù)色調(diào)光柵圖形由多邊形圖形->Gouraudshading->Phongshading由朗伯模型->Phong模型->整體光照模型由掃描線算法->光線跟蹤算法->光能輻射度方法第六十二頁，共七十五頁，2022年，8月28日在追求畫面實(shí)時生成方面硬件支持繪制處理。景物細(xì)節(jié)簡化技術(shù)?；趫D象的繪制。逐步求精的畫面生成算法。第六十三頁，共七十五頁，2022年，8月28日逐步求精畫面的繪制算法的特點(diǎn)一開始就生成畫面,包含有用的視覺信息。畫面由粗糙逐步變得精細(xì),真實(shí)感不斷增強(qiáng)。每一步的計算都利用了前面步驟的計算結(jié)果。第六十四頁，共七十五頁，2022年，8月28日基于光能輻射度的畫面計算和生成過程場景輻射度方程:Bi=Ei+ρi∑BjFij1)計算形狀因子,確定系數(shù)矩陣,計算量存儲量均為O(N2)2)迭代法求解方程組,獲得環(huán)境中的光能分布3)取景變換,確定可見面,計算并顯示每一象素上可見面的光亮度值問題:第一步計算量占整個方法的90%,任何有用的結(jié)果和畫面顯示都必須在系數(shù)矩陣確定后才能生成第六十五頁，共七十五頁，2022年，8月28日光能輻射度方程的迭代形式令則第六十六頁，共七十五頁，2022年，8月28日分析:上述方程表明,每一面片的輻射度增量應(yīng)為其他面片向它入射的光能的線性組合,這一過程稱之為Gathering。每一步迭代的代價 在接受面片i上建立一個半立方體，計算n個形狀因子（所有Fij）。更新一個面片(i)的輻射度。第六十七頁，共七十五頁，2022年，8月28日改進(jìn) 在方程右側(cè)的和式中，選擇對刷新貢獻(xiàn)最大的一項，取面片j作為輻射源，則(Dueto)=每一步迭代的效果在輻射源面片j上建立一個半立方體，計算n個形狀因子（所有Fji）,場景中大部分面片的輻射度均有所更新。這一過程稱之為Shooting。第六十八頁，共七十五頁，2022年