[工學]計算機圖形學第三章-文庫吧
2025-02-02 14:27 本頁面
【正文】 OFF表示不填充） AUTOCAD畫圓 26 多邊形的生成 27 多邊形的生成 28 多邊形的生成 ?目標：利用相鄰像素之間的連貫性，提高算法效率 ?處理對象：非自交多邊形 （邊與邊之間除了頂點外無其它交點） 掃描線算法 綜合利用了區(qū)域的連貫性、掃描線的連貫性和邊的連貫性，避免對象素逐點運算。 29 多邊形的生成 區(qū)間連貫性 30 多邊形的生成 掃描線連貫性 31 多邊形的生成 邊的連貫性 32 多邊形的生成 ? 基本原理 一條掃描線與多邊形的邊有偶數(shù)個交點 ? 步驟 (對于每一條掃描線 ): (1)求交點 (2)交點排序 (3)交點配對，填充區(qū)段 。 掃描線算法 33 多邊形的生成 ?交點的取整規(guī)則 ? 要求：使生成的像素全部位于多邊形之內(nèi) ? 用于線畫圖元掃描轉(zhuǎn)換的四舍五入原則導致部分像素位于多邊形之外，從而不可用 ? 假定非水平變與掃描線 y=e 相交，交點的橫坐標為 x, 規(guī)則如下 掃描線算法 34 多邊形的生成 ● 規(guī)則 1： X為小數(shù)，即交點落于掃描線上兩個相鄰像素之間 (a)交點位于左邊之上，向右取整 (b)交點位于右邊之上，向左取整 35 多邊形的生成 ● 規(guī)則 2： 邊界上象素的取舍問題，避免填充擴大化。 ●解決方法： 邊界象素：規(guī)定落在右上邊界的象素不予填充。 具體實現(xiàn)時，只要對掃描線與多邊形的相交區(qū)間左閉右開 36 多邊形的生成 ● 規(guī)則 3： 掃描線與多邊形的頂點相交時，交點的取舍，保證交點正確配對。 ●解決方法： 檢查兩相鄰邊在掃描線的哪一側(cè)。 只要檢查頂點的兩條邊的另外兩個端點的 Y值，兩個 Y值中大于交點 Y值的個數(shù)是 0， 1， 2，來決定取 0， 1， 2個交點。 37 多邊形的生成 1） 活性邊 ：與當前掃描線相交的邊。按交點 x的增量順序存放在一個鏈表中；該鏈表稱作 活性邊表（ AEL)。 ?AEL 與 ET的結(jié)點信息： ?Ymax: 所交邊的最高掃描線號 ?X：當前掃描線與邊的交點的 x坐標 ?△ X：邊的斜率的倒數(shù) ?Nextage: 下一條邊的指針 typedef struct {int ymax。 float x,deltax。 Edge *nextEdge。 }Edge。 38 多邊形的生成 2）邊的分類表 （ ET） 按照邊的下端點 y坐標對非水平邊進行分類的指針數(shù)組 , 下端點 y坐標值等于 i的邊屬于第 i類 typedef struct {int ymax。 float x,deltax。 Edge *nextEdge。 }Edge。 邊的分類表的作用是避免盲目求交。 當處理一條掃描線時，為了求出它 與多邊形邊的所有交點，必須將它 與所有的邊進行求交測試。而實際 上只有某幾條邊與該掃描線有交點。 邊的分類表正是用來排除不必要的 求求交測試的。 39 多邊形的生成 40 多邊形的生成 ▼ 求補運算 ：假定 A為一個正整數(shù)，則 M的補定義為 A – M, 記為 。計算機中取 A為 n位能表示的最大整數(shù)。即， A=0xFFFFFFFF ▼ 由來： 光柵圖形中，如果某區(qū)域已著上值為 M的顏色值做偶數(shù)次求補運算，該區(qū)域顏色不變；而做奇數(shù)次求補運算，則該區(qū)域顏色變?yōu)橹禐榈念伾?。這一規(guī)律應用于多邊形掃描轉(zhuǎn)換，就為邊緣填充算法。 ▼求補運算可用異或顯示模式實現(xiàn)。 ▼算法基本思想： 對于每條掃描線和每條多邊形邊的交點，將該掃描線上交點右方的所有象素取補。 邊填充算法 41 多邊形的生成 42 多邊形的生成 步驟 1：對多邊形的所有邊 （ 水平邊除外 ） 用特殊顏色打標志 ， 計算掃描線與邊的交點 ， 將交點置成特殊顏色 。 步驟 2：對于每條與多邊形相交的掃描線 ， 從左向右依次訪問該掃描線上的每個像素 ， 用一個布爾變量 inside來表示當前像素是在多邊形外部 ， 還是在多邊形內(nèi)部 。 inside的初始值為 false， 在從左向右的訪問過程中 ， 每當遇到一個被置成特殊顏色的像素 ， 就將 inside取反 ， 如果訪問的像素沒有被置成特殊顏色 ， 就保持 inside不變 。 經(jīng)過如上處理后 ， 若inside為 false， 則當前像素置成背景色或保持原來顏色
教學課件相關推薦
鄂ICP備17016276號-1