【正文】 對所有的邊進行分組，若某邊的下低端點 y值為 ymin，則該邊就放在 ymin所對應的桶中；然后用排序方法，按下端點的 x坐標值遞增的順序?qū)⑼唤M中的邊排列成行。 第 3章 基本圖形生成算法 ET和 AEL中的基本元素為多邊形的邊。 （ 2）按從下到上的順序?qū)γ織l掃描線重復以下各步，直至 AEL和 ET為空 。 算法雖然簡單易行，但對于復雜圖形而言，一些像素的顏色值需反復改變多次，且多邊形外的像素處理過多，輸入、輸出的量比有序邊表大的多。 多邊形外的像素處理大大減少，被重復取補的像素數(shù)目也有減少，但仍有一些像素被重復取補。使用一個布爾變量 inside來指示當前點的狀態(tài)，若點在多邊形內(nèi)，則 inside為真。 inside 的初始值為假，每當當前訪問像素為被打上標志的點，就把 inside取反。若訪問當前像素時，對 inside作必要操作之后， inside為真，則把該像素置為多邊形要填充的顏色。 第 3章 基本圖形生成算法 種子填充算法 基本思想：假設在多邊形區(qū)域內(nèi)部至少有一個像素是已知的（此像素稱為種子像素），由此出發(fā)找到區(qū)域內(nèi)所有其他像素，并對其進行填充。 可以使用棧結(jié)構(gòu)來實現(xiàn)該算法，算法的執(zhí)行步驟如下： 種子像素入棧，當棧非空時，重復執(zhí)行如下三步操作： （ 1）棧頂像素出棧； （ 2）將出棧像素置成多邊形填充的顏色； （ 3）按左、上、右、下的順序檢查與出棧像素相鄰的四個像素，若其中某個像素不在邊界上且未置成多邊形色，則把該像素入棧。它也常稱為漫水法。 第 3章 基本圖形生成算法 3． 掃描線種子填充算法 算法思想：在任意不間斷區(qū)間中只取一個種子像素（不間斷區(qū)間指在一條掃描線上一組相鄰元素），填充當前掃描線上的該段區(qū)間；然后確定與這一區(qū)段相鄰的上下兩條掃描線上位于區(qū)域內(nèi)的區(qū)段，并依次把它們保存起來，反復進行這個過程，直到所保存的每個區(qū)段都填充完畢。 第 3章 基本圖形生成算法 圓域的填充 對每條掃描線，計算它與圓域的相交區(qū)間。然后，為當前掃描線設置一個活化圓表。結(jié)點內(nèi)存放當前掃描線的區(qū)間端點，以及用于計算下一條掃描線與圓相交的區(qū)間端點所需的增量。 第 3章 基本圖形生成算法 區(qū)域填充屬性 1．填充樣式 2．填充顏色 3．填充圖案 第 3章 基本圖形生成算法 字符 字符存儲與顯示 1．點陣字符 每個字符都是利用掩膜來定義，并將其寫入幀緩存保存和顯示。讀取幀緩存中這些像素值，就可以在屏幕上顯示此字符。 第 3章 基本圖形生成算法 2．矢量字符 矢量字符被表達為一個點坐標的序列，相鄰兩點表示一條矢量，字符的形狀便由矢量序列刻劃。然后取出端點坐標，對其進行適當?shù)膸缀巫儞Q，再根據(jù)各端點的標志顯示出字符。一般來說，字體確定風格，字形確定外觀，字號確定尺寸。 ? xrxxl ytyyb ?? ?? 第 3章 基本圖形生成算法 直線裁剪 1． CohenSutherland裁剪算法（編碼裁剪法） 基本思想：對于每條待裁剪的線段 P1P2分為三種情況處理：（ 1）若 P1P2完全在窗口內(nèi)，則顯示該線段 P1P2，簡稱 “ 取 ” 之；（ 2）若 P1P2完全在窗口外，則丟棄該線段，簡稱 “ 舍 ” 之；（ 3）若線段既不滿足 “ 取 ” 的條件，也不滿足 “ 舍 ” 的條件，則求線段與窗口邊界的交點，在交點處把線段分為兩段，其中一段完全在窗口外，可舍棄之，然后對另一段重復上述處理。具體編碼過程為： 延長窗口的四條邊線（ yt、 yb、 xr、 xl），將二維平面分成九個區(qū)域。 ??? ????? ????? ????? ??ot he rxlxcot he rxrxcot he rybycot he rytyclrbt 01010101第 3章 基本圖形生成算法 ?如果某線段的兩個端點的四位 二進制編碼全為 “ 0000”，可直 接保留； ?如果對兩端點的四位二進制編碼進行邏輯與（按位乘）運算，結(jié)果不為零，可直接舍棄； ?否則，這一線段可能與窗口相交。 裁剪窗口 第 3章 基本圖形生成算法 2．中點分割算法 基本思想：當一條直線段既不能直接保留也不能直接舍棄，需要求其與區(qū)域的交點時，不斷地用對分方法，舍去線段的不可見部分，用中點去逼近線段與窗口邊界的交點。如果 qk≥0，則該線段平行于裁剪邊界并且在窗口內(nèi)。 ?當 pk0時，線段從裁剪邊界延長線的內(nèi)部延伸到外部。 第 3章 基本圖形生成算法 梁友棟 Barsky裁剪算法在尋找線段可見部分（如果有可見線段）時可以歸結(jié)為四個步驟： （ 1）如果對所有的 k都有 pk=0和 qk0，刪除線段并結(jié)束。 （ 2）對所有 pk0的 k，計算 rk=qk/pk ，將 0和各個rk值之中的最大值賦給 u1。 （ 4）如果 u1u2，則線段完全落在裁剪窗口之外，不可見，可直接舍棄。 第 3章 基本圖形生成算法 多邊形裁剪 1． SutherlandHodgman算法 基本思想：每次用窗口的一條邊界對多邊形進行裁剪，把落在窗口外部的圖形去掉，落在窗口內(nèi)部的圖形保留，并把它作為下一次待裁剪的多邊形。 第 3章 基本圖形生成算法 2． WeilerAtherton裁剪算法 基本思想：將待裁剪多邊形（簡寫為 P1）和裁剪矩形窗口（簡寫為 P2）均設定為按順時針方向排列。 第 3章 基本圖形生成算法 曲線裁剪 對于被裁剪的曲線所圍成的區(qū)域，找出包圍（外接）此區(qū)域的最小矩形，稱其為曲線邊界對象的包圍矩形（或包圍盒），然后測試包圍矩形是否與矩形裁剪窗口有重疊。 第 3章 基本圖形生成算法 字符裁剪 1．字符串裁剪 把整個字符串作為整體來對待。 3．矢量 \像素裁剪 每個字符都看作是由一系列矢量（線段）或像素構(gòu)成的，故對每一個矢量或像素都必須個別地進行裁剪。 對空間任意一點 P（ x,y,z）按其所處位置賦予 6位二進制編碼。 第 3章 基本圖形生成算法 反走樣 對圖形進行光柵化時，是用離散的像素顯示在連續(xù)空間定義的對象。 用于減少或消除走樣的技術(shù)稱為