計算機圖形學 算法總結

《計算機圖形學 算法總結》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。

1、計算機圖形學算法總結viopond@life-sciences一、二維線畫圖元的生成掃描轉換直線段生成直線段的DDA算法利用直線方程直接計算，結果取整。用到浮點數的加法和取整。生成直線段的中點算法利用直線的正負劃分性，構造隱函數F（x,y）。每次計算F(xi+1,yi+0.5)，判斷函數正負，若為正則下一點在右側，若為負則下一點在右上。判別式F(x,y)=△xy-△yx-△xB(原直線y=mx+B，把m改寫)。計算判別式遞推的方法：分d>=0和d<0兩個情況，計算橫坐標為xi+2時的判別式表達式，獲得d的增

2、量。Breseham畫線算法d是誤差項。x下標每次加1，d相應增加斜率k。一旦d>=1,就把它減去1。當d>=0.5時，取當前象素右上方象素。當d<0.5時，取右邊象素。為方便計算，令e=d-0.5掃描轉換圓弧圓的八對稱性利用圓弧方程開根計算或者利用參數方程計算，開根/三角函數，計算量大圓弧的中點算法F(x,y)=x^2+y^2-R^2正在圓弧外，取右下。負在圓弧內，取右。第一象限：構造判別式d=F(M)=F(xi+1,yi-0.5)，遞推方法類似直線的中點算法。橢圓的中點畫法也與此類似。判別式函數不一樣而

3、已。生成圓弧的多邊形逼近法給定最大逼近誤差delta,確定圓心角，R-Rcosa<=deltan=2pi/a下一個頂點，用cosa–sina矩陣乘xisinacosayi一個頂點需4次乘法，一共4n次乘法，外加直線段中點算法的計算量圓的等面積逼近法求多邊形徑長，從而求所有頂點坐標。由逼近誤差值確定圓心角a。生成圓弧的正負法曲線把平面分成G+和G-兩個區(qū)域，前進△x時，到達P1,再前進△y到P2，之后若點與P1在同側，則前進△y，否則前進△x。判別式D(Pi)=F(Pi).F(P1)=F(xi,yi).F(x

4、0+△x,y0)二、二維填充圖元的生成掃描轉換矩形做x,y坐標的二重循環(huán)，逐點填充。共享邊界：左閉右開，下閉上開。掃描轉換多邊形逐點判斷法、掃描線算法、邊緣填充法逐點判斷法：射線法：從每個象素點發(fā)射線，交點個數偶數的在外，反之在內。避免射線通過頂點。累積角度法：記錄從該象素到多邊形每個頂點的有向角（逆時針旋轉為正），若代數和為0則在外，若為正負2pi的在內。編碼方法：從X軸起逆時針把各象限編碼，確認各頂點所在象限的編碼，然后兩頂點相減計算各邊的編碼，用4處理使編碼絕對值不大于2，最后求各邊編碼代數和。代數和

5、為0的在外，為正負4的在內。特殊情況：(1)點在邊上.預處理解決(2)代數和為正負2（取中點再編碼，遞歸）掃描線算法求掃描線與多邊形各邊的交點對所得交點從小到大排序兩兩配對，填充每個區(qū)段原則：與掃描線的交點向多邊形內取整。交點落在象素點上時，僅落在左邊上的屬于多邊形。交點為多邊形頂點時，每個邊被認為下閉上開(p74)。數據結構和算法流程P76特點：算法效率比逐點填充法高很多缺點：對各種表的維持和排序開銷太大，適合軟件實現而不是硬件實現。邊緣填充法：基本思想：對于每條掃描線盒每條多邊形邊的交點，將該掃描線上交

6、點右方的所有像素顏色取補。對多邊形的每條邊做此處理。原理：以求余運算代替掃描線算法中的排序運算。特點：適合用于具有幀緩存的圖形系統(tǒng)。算法簡單，但對于復雜圖形，每一像素被訪問多次，輸入輸出多。掃描轉換扇形區(qū)域原理同多邊形掃描轉換，問題在于確認掃描線與直邊和圓弧邊的相交順序。分情況討論，固定P1在第一象限時有4種情況，一共十六種。區(qū)域填充四向聯通區(qū)域、八向聯通區(qū)域邊界表示的四連通遞歸算法（種子填充算法）：種子像素入棧，棧非空時，重復執(zhí)行以下步驟：棧頂像素出棧，將出棧像素置色，四向檢查像素，若其中某個像素不在邊界

7、且未被置色，則該像素入棧?？捎糜谔畛鋷瓤椎钠矫鎱^(qū)域。缺點：有些像素反復入棧降低效率，棧結構占空間。遞歸執(zhí)行算法簡單但效率不高。可用下面的掃描線填充算法解決。掃描線填充算法目標：減少遞歸算法：棧頂像素出棧沿掃描線對出棧像素的左右像素進行填充，直到遇到邊界像素為止。（填充區(qū)間）檢查上下掃描線，選相應區(qū)間的最左像素作為種子入棧。特點：由區(qū)域算法定區(qū)間，再定上下鄰區(qū)間。多邊形掃描轉換與區(qū)域填充方法比較：不同點：前者將頂點表示轉換成點陣表示，后者只是改變顏色，沒有改變表示方法。前者只要求掃描線與多邊形邊界交點個數為

8、偶數。后者要求區(qū)域封閉。前者從邊界頂點信息出發(fā)，后者從區(qū)域內種子點出發(fā)。三、二維光柵圖形的混淆與反混淆用離散量（像素）表示連續(xù)的量（圖形）而引起的失真，叫做混淆或者走樣。反混淆方法提高分辨率：方便，代價巨大區(qū)域采樣方法：把直線段看做具有一定寬度的狹長矩形，當直線段與像素有交時，求出相交區(qū)域的面積。根據面積大小確定亮度值，使相鄰兩個像素的灰度之間有平緩的過渡。非加權區(qū)域采樣方法：非加權區(qū)域采樣方法性質：（1）像素亮