【正文】 ????????????? 解方程有 – ，光線與球無(wú)交 – ，光線與球相切， t=－ B/2 – ，光線與球有兩個(gè)交點(diǎn) – t0，交點(diǎn)無(wú)效 – t代入光線參數(shù)方程，可求得交點(diǎn)坐標(biāo) 242 CBBt ????042 ?? CB042 ?? CB042 ?? CB? 交點(diǎn)的坐標(biāo) ? 交點(diǎn)處的法向量 ? 代數(shù)法求交點(diǎn)和法向量總共需要 17次加減運(yùn)算、 17次乘法運(yùn)算、 1次開(kāi)方運(yùn)算和3次比較操作 ),( iii zyx）（ R zzR yyR xx cicici ??? ,幾何解法 ? 幾何法求交示意 tcathcSrR0ScDLocR( T)Rl基本步驟 ? 計(jì)算光線起點(diǎn)到球心的距離平方 – 光線的起點(diǎn)在球內(nèi)，光線與球有且僅有一個(gè)交點(diǎn) – 光線的起點(diǎn)在球外，光線與球有兩個(gè)交點(diǎn)或一個(gè)切點(diǎn)或沒(méi)有交點(diǎn) 222022 )()()()()( cccccoc zzyyxxRSRSL ??????????22 RL oc ?22 RL oc ?? 計(jì)算光線起點(diǎn)到光線離球心最近點(diǎn) A距離 – 當(dāng)光線的起點(diǎn)在球外，若 ，則球在光線的背面，光線與球無(wú)交點(diǎn) dcdcdclocoa zzzyyyxxxRRSt ???????????? )()()()( 0000?cat? 計(jì)算半弦長(zhǎng)的平方，來(lái)判定交點(diǎn)的個(gè)數(shù) – ，光線與球無(wú)交 – ，光線與球相切 – ，光線與球有兩個(gè)交點(diǎn) 222222 caochc tLRDRt ?????02 ?hct02 ?hct02 ?hct? 計(jì)算光線起點(diǎn)到光線與球交點(diǎn)的距離來(lái)計(jì)算交點(diǎn)的位置 ? t代入光線的參數(shù)方程，可以得到交點(diǎn)的位置 2222caoccahcca tLRtttt ??????? 交點(diǎn)的坐標(biāo) ? 交點(diǎn)處的球面法向 ? 幾何法求交點(diǎn)和法向總共需要 16次加減運(yùn)算、 13次乘法運(yùn)算、 1次開(kāi)方運(yùn)算和 3次比較操作 ? 比代數(shù)法少 1次加減運(yùn)算和 4次乘法運(yùn)算 ),(),( 000 tzztyytxxzyx dddiii ???????）（ R zzR yyR xx cicici ??? ,光線與多邊形求交 ? 光線與多邊形求交分為兩步 ? 計(jì)算多邊形所在的平面與光線的交點(diǎn) ? 判斷所得的交點(diǎn)是否在多邊形內(nèi)部 ? 直線平面求交方法參見(jiàn)前面的章節(jié) 光線與二次曲面求交 ? 光線與一般表示形式的二次曲面的求交方法 ? 二次曲面方程的一般形式表示 ? 矩陣形式 0222222),( 223 ??????????? JIzHzGyF y zEyDxC x zB x yAxzyxF01]1[ ?????????????????????????zyxJIGDHGFCGFEBDCBAzyx? 把光線的參數(shù)方程代入二次曲面的一般形式有 ? 解出 t， 有 JIzHzGyzFyEyDxzCxyBxAxcIzzHzGyzyzyFyEyDxzxzxCyxyxBxAxbHzzFyEyzCxyBxAxacbtatddddddddddddddddddddd???????????????????????????????0200002000000200000000002222222222])()()([22220242 acbbt ????? t為實(shí)數(shù)，將 t代入 光線參數(shù)方程 可得交點(diǎn)坐標(biāo) ? 交點(diǎn)處的法向量 ),(),( 000 tzztyytxxzyx dddiii ???????)(2)(2)(2,),(IHzFyCxzGFzEyAxyDCzByAxxzFyFxFzyxiiiniiiniiinnnn???????????????????????????光線跟蹤算法的加速 ? 基本的光線跟蹤算法，每一條射線都要和所有的物體求交，處理地效率很低 ? 光線跟蹤加速技術(shù)是實(shí)現(xiàn)光線跟蹤算法的重要組成部分 – 包括：提高求交速度、減少求交次數(shù)、減少光線條數(shù)、采用廣義光線和采用并行算法等 自適應(yīng)深度控制 ? 對(duì)復(fù)雜的場(chǎng)景，沒(méi)有必要跟蹤光線到很深的深度，應(yīng)根據(jù)光線所穿過(guò)的區(qū)域的性質(zhì)來(lái)改變跟蹤深度，來(lái)自適應(yīng)的控制深度 ? 前面給出的光線跟蹤算法的源代碼就是可以做到自適應(yīng)的控制深度的。 包圍盒及層次結(jié)構(gòu) ? 包圍盒技術(shù)是加速光線跟蹤的基本方法之一，由 Clark于 1976年提出 ? 1980年， Rubin和 Whitted將它引進(jìn)到光線跟蹤算法之中，加速光線與景物的求交測(cè)試 基本思想 ? 用一些形狀簡(jiǎn)單的包圍盒將復(fù)雜景物包圍起來(lái)，求交的光線首先跟包圍盒進(jìn)行求交測(cè)試，若相交，則光線再與景物求交，否則光線與景物必?zé)o交 ? 利用形狀簡(jiǎn)單的包圍盒與光線求交的速度較快來(lái)提高算法的效率 層次結(jié)構(gòu) ? 包圍盒技術(shù)的一個(gè)重要改進(jìn)是引進(jìn)層次結(jié)構(gòu) ? 根據(jù)景物的分布情況，將相距較近的景物組成一組局部場(chǎng)景，相鄰各組又組成更大的組 ? 整個(gè)景物空間組織成樹(shù)狀的層次結(jié)構(gòu) ? 求交測(cè)試方法 – 測(cè)試光線首先進(jìn)入該層次的根節(jié)點(diǎn)，并從根節(jié)點(diǎn)開(kāi)始，從上向下與各相關(guān)節(jié)點(diǎn)的包圍盒進(jìn)行求交測(cè)試。若一節(jié)點(diǎn)的包圍盒與光線有交，則光線將遞歸地與其子節(jié)點(diǎn)進(jìn)行求交測(cè)試，否則，該節(jié)點(diǎn)的所有景物均與光線無(wú)交，該節(jié)點(diǎn)的子樹(shù)無(wú)需作求交測(cè)試 平行平面層次包圍盒技術(shù) ? 1986年， Kay和 Kajiya提出 ? 通常采用的長(zhǎng)方體具有包裹景物不緊的特點(diǎn) ? 根據(jù)景物的實(shí)際形狀選取 n組不同方向的平行平面包裹一個(gè)景物或一組景物來(lái)作為層次包圍盒 三維 DDA算法 ? 光線跟蹤算法效率不高的主要要原因是光線求交的盲目性 ? 將景物空間剖分為網(wǎng)格，利用空間連慣性，加速光線跟蹤 ? 三維 DDA算法－ 1986年， Fujimoto等提出一個(gè)基于空間均勻網(wǎng)格剖分技術(shù)的快速光線跟蹤算法 ? 景物空間均勻分割成為一系列均勻的 3維網(wǎng)格，建立輔助數(shù)據(jù)結(jié)構(gòu) SEADS ? 確定后的 SEADS結(jié)構(gòu)中每一個(gè)網(wǎng)格可用三元組 (i， j， k)精確定位，均設(shè)立其所含景物面片的指針 ? 光線跟蹤的光線只須依次與其所經(jīng)過(guò)的空間網(wǎng)格中所含景物面片進(jìn)行求交測(cè)試 ? 將直線光柵化的 DDA算法推廣到三維，來(lái)加速光線跟蹤，稱為光線的三維網(wǎng)格跨越算法 ? 光線的方向向量 ，主軸方向就是 。算法先將光線垂直投影到交于主軸的兩個(gè)坐標(biāo)平面上，然后對(duì)兩投影線分別執(zhí)行二維 DDA算法 ? 算法廣泛的應(yīng)用于各種商業(yè)動(dòng)畫軟件中 ),( zyx VVVV),m a x ( zyxd VVVV ?空間八叉樹(shù)剖分技術(shù) ? 空間非均勻網(wǎng)格剖分算法 ? 將含有整個(gè)場(chǎng)景的空間立方體按三個(gè)方向中剖面分割成八個(gè)子立方體網(wǎng)格，組織成一棵八叉樹(shù)，若某一子立方體網(wǎng)格中所含景物面片數(shù)大于給定的閾值，則為該子立方體作進(jìn)一步的剖分，直到面片數(shù)目小于閾值 ? 利用空間連貫性加速光線跟蹤 ? 八叉樹(shù)的最大深度表示空間分割所達(dá)到的層次，稱為空間分辨率 ? 八叉樹(shù)的深度為 N，八叉樹(shù)終結(jié)節(jié)點(diǎn)的編碼 , ,i在 [0..N]之間， F為異于 0， 1．．． 7的符號(hào) ? 由八叉樹(shù)結(jié)點(diǎn)編碼方式很容易找到空間任一點(diǎn)所在的空間網(wǎng)格單元 FFFqqq i ??21 }7,2,1,0{, 21 ?? ?nqqq八叉樹(shù)剖分性質(zhì) ? 為一空間點(diǎn)，坐標(biāo)為整數(shù)，其二進(jìn)制表示為： ， ， ， ? 性質(zhì) A: P所在單位立方體網(wǎng)格編碼為 ),( zyxPNiiix ?21? Njjjy ?21?Nkkkz ?21? ? ? Nlkji lll ,2,1,1,0, ???Nlkjiq llll ,2,1,42 ?????性質(zhì) B ? P位于一編碼 為的空間網(wǎng)格內(nèi)，則該空間網(wǎng)格的前左下角坐標(biāo)為： – 其中 0的個(gè)數(shù)都為 N－ i個(gè) FFFqqq i ??210021 ?? iiiix ??0021 ?? ijjjy ??0021 ?? ikkkz ??光線跟蹤過(guò)程 ? 先利用性質(zhì) A求光線起點(diǎn) 所在單位立方體網(wǎng)格的八叉樹(shù)編碼 Q ? 位于立方體邊界上的起點(diǎn)要根據(jù)光線前進(jìn)方向 R判別光線是否已射出場(chǎng)景。若光線已射出場(chǎng)景，則算法結(jié)束 ? Q的空間線性八叉樹(shù)結(jié)點(diǎn)表查找結(jié)果 – 查找是否成功的布爾量 T – 未獲匹配位數(shù) B 0P? 設(shè) Q為 ，那么在 八叉樹(shù)中含結(jié)點(diǎn) 時(shí)， T取真值 ? 未獲匹配位數(shù) B定義為八叉樹(shù)終結(jié)點(diǎn)表中與 Q獲得最大程度匹配結(jié)點(diǎn)其編碼尾部不匹配的位數(shù)。上面的 B為 N－ i ? T決定當(dāng)前立方體是否包含景物面片，而Q和 B確定當(dāng)前立方體的空間位置和大小 Nqqq ?21FFFqqq i ??21? T取真值，用光線和該立方體中所含三角形面片求交，若有交，則返回最近交點(diǎn)，算法結(jié)束，否則取 T為假，繼續(xù)向前搜索 ? T為假的兩種情況 – 查找結(jié)果使 T取假，包含起點(diǎn)且不包含任何景物面片的最大空間網(wǎng)格為 ，其中 F的個(gè)數(shù)為 B1 – 求交失敗 T為假，應(yīng)跨過(guò)當(dāng)前立方體網(wǎng)格 FFqqqq ii ?? 121 ?? 新的網(wǎng)格 前左下角坐標(biāo)由性質(zhì) B確定 ? 跨越一空間網(wǎng)格后，先求出當(dāng)前空間網(wǎng)格上的出口點(diǎn)坐標(biāo)，重置光線起點(diǎn) – 光線和六個(gè)面求交 – 預(yù)先計(jì)算光線在各坐標(biāo)平面上投影線的截距和斜率，快速求解 ? 以新出發(fā)點(diǎn)重復(fù)跟蹤過(guò)程，直至光線射出場(chǎng)景或求到交點(diǎn)為止