1如何在指定的輸出設備上根據坐標描述構造基本二維幾何圖形（點、直線、圓、橢圓、多邊形域、字符串及其相關屬性等）。第四章計算機基本圖形生成2直線段的生成圓與橢圓的生成區域填充二維圖像裁剪線寬與線型的處理

基本圖形生成算法3圖形的生成：是在指定的輸出設備上，根據坐標描述構造二維幾何圖形。圖形的掃描轉換：在光柵顯示器等數字設備上確定一個最佳逼近于圖形的象素集的過程。圖5.1用象素點集逼近直線圖形生成的概念4直線段的生成直線的繪制要求（1）直線要直；（2）直線的端點要準確，保證直線的無定向性，也就是從A點到B點和從B點到A點所畫直線應該是重合的；（3）直線的色澤和亮度要均勻，即要求繪制的像素點的密度保持均勻；

（4）畫線的速度要快。5直線的掃描轉換解決的問題：給定直線兩端點P0(x0,y0)和P1(x1,y1)，畫出該直線。數值微分法中點Bresenhan算法改進的Bresenhan算法6數值微分法(DDA法)直線的微分方程：ε=1/max(|△x|,|△y|)圖5.2DDA算法原理max(|△x|,|△y|)=|△x|，即|k|≤1的情況：max(|△x|,|△y|)=|△y|，此時|k|≥1：8增量算法直觀、易實現不利于用硬件實現數值微分法(DDA法)——特點9中點Bresenham算法直線的方程圖5.3直線將平面分為三個區域10中點Bresenham算法算法原理：根據直線的斜率確定或選擇變量在x或y方向上每次遞增一個單位，而另一方向的增量為1或0，它取決于實際直線與相鄰象素點的距離，這一距離稱為誤差項。假定0≤k≤1，即0≤Δy/Δ

x≤1，x是最大位移方向圖5.4Brensemham算法生成直線的原理判別式：則有：圖5.5Brensemham算法生成直線的原理d的意義：圖5.6Brensemham算法生成直線的原理誤差項的遞推（d<0）圖5.7誤差項遞推誤差項的遞推（d≥0）圖5.8誤差項遞推16初始值d的計算中點Bresenham算法圖5.9計算初值17改進：用2d△x代替d,令D＝2d△x則：中點Bresenham算法——改進18輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。計算初始值△x、△y、D=△x-2△y、x=x0、y=y0。繪制點(x,y)。判斷D的符號。若D<0，則(x,y)更新為(x+1,y+1)，D更新為D+2△x-2△y；否則(x,y)更新為(x+1,y),D更新為D-2△y。當直線沒有畫完時，重復上一步驟，否則結束。程序演示中點Bresenham算法——算法步驟19改進的Bresenham算法假定直線段的0≤k≤1圖5.10改進的Brensemham算法繪制直線的原理改進的Bresenham算法21誤差項的計算d初=0，每走一步：d=d+k一旦y方向上走了一步，d=d-1改進的Bresenham算法——原理改進1：令e=d-0.5e初=-0.5，每走一步有e=e+k。if(e>0)thene=e-1誤差項的計算d初=0，每走一步：d=d+kif(e>0)thend=d-1改進2：用E=2e△x來替換ee初=-0.5每走一步有e=e+kif(e>0)thene=e-1E初=-0.5*2△x=-△x每走一步有E=(e+k)*2△x=E+2△yif(e>0)thenE=(e-1)*2△x=E-2△x241.輸入直線的兩端點P0(x0,y0)和P1(x1,y1)。2.計算初始值△x、△y、e=-△x、x=x0、y=y0。3.繪制點(x,y)。4.e更新為e+2△y，判斷e的符號。若e>0，則(x,y)更新為(x+1,y+1)，同時將e更新為e-2△x；否則(x,y)更新為(x+1,y)。5.當直線沒有畫完時，重復步驟3和4。否則結束。改進的Bresenham算法——算法步驟25圓和橢圓的生成圓的特點（1）只討論中心在原點，半徑為整數的圓。（2）在進行圓的掃描轉換時，首先應該注意，可以通過八分法畫圓，即把圓分成8份。要得到整個圓的掃描轉換，只要對它的八分之一圓弧掃描即可。這種方法稱為八分法畫圓。(y,x)(-y,x)(-x,y)(-x,-y)(-y,-x)(y,-x)(x,-y)圖5.11八分法畫圓27解決問題：2.圓的生成圖5.121/8圓弧28圓的掃描轉換簡單方程生成圓弧中點Bresenham算法29簡單方程產生圓弧算法原理：利用其函數方程，直接離散計算。圓的函數方程為：

30圓的極坐標方程為：簡單方程產生圓弧31構造函數F(x,y)=x2+y2-R2。對于圓上的點，有F(x,y)=0；對于圓外的點，F(x,y)>0；而對于圓內的點，F(x,y)<0。

給定圓心在原點，半徑為整數R的圓，其方程為中點Bresenham畫圓圖5.13中點Bresenham畫圓的原理33當d≤0時，下一點取Pu(xi+1,yi)；當d>0時，下一點取Pd(xi+1,yi-1)。構造判別式：中點Bresenham畫圓誤差項的遞推（d≤0）圖5.14d≤0的情況誤差項的遞推（d>0）圖5.15d>0的情況36判別式的初始值中點Bresenham畫圓改進：用d-0.25代替d此時有：381.輸入圓的半徑R。2.計算初始值d=1-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d<0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當x<y時，重復步驟3和4。否則結束。程序演示中點Bresenham畫圓——算法步驟橢圓的特點我們將橢圓定義為兩個定點（焦點）的距離之和等于常數的點的集合。我們在這里只討論中心在坐標原點的標準橢圓的生成算法。橢圓的函數為由于橢圓在四分象限中是對稱的，所以只需要計算在第一象限中橢圓弧上的像素點的位置，其他象限中的點的位置可通過對稱性得到。中點Bresenham畫橢圓方法

基本思想：先判斷最大位移方向以及位移步長。在上半部分，因為|k|<=1，最大位移方向是x，所以每次在x方向上加1，在y方向上或者減1或者減0；在下半部分，因為|k|>=1，最大位移方向為y，因此y方向每次減1，而x方向上加1或者加0。中點Bresenham畫橢圓算法的步驟(1)輸入橢圓的長半軸和短半軸；(2)計算d的初值，并賦初值

;(3)繪制點(x,y)及其在四分象限上的另外3個對稱點；(4)判斷d的符號。根據d的符號對點的坐標進行更新。(5)當時，重復步驟(3)和(4)，否則轉到步驟(6)；中點Bresenham畫橢圓算法的步驟(6)用上半部分計算的最后點（x,y)來計算下半部分中d的初值；(7)繪制點(x,y)及其在四分象限上的另外3個對稱點；(8)判斷d的符號，根據d的符號對d值進行更。(9)重復步驟（7）和（8）；否則結束。43區域填充區域填充可以分兩步進行，第一步先確定需要填充哪些素，第二步確定用什么顏色來填充。區域填充指從區域的一點（種子點）開始，由內向外將填充色擴展到整個區域的過程。這里的區域是指已經表示成點陣形式的填充圖形，它是一個像素集合。區域通常有內點表示和邊界表示兩種形式。44區域填充多邊形區域填充邊填充種子填充45多邊形區域填充一種常用的掃描方法是掃描線算法，計算掃描線與多邊形的相交區間，再用要求的顏色顯示這些區間的像素，即完成填充工作。區間的端點可以通過計算掃描線與多邊形邊界線的交點獲得。46基本思想：按掃描線順序，計算掃描線與多邊形的相交區間，再用要求的顏色顯示這些區間的所有象素。掃描線算法——原理圖5.16x-掃描線算法填充多邊形471.確定多邊形所占有的最大掃描線數，得到多邊形頂點的最小和最大y值（ymin和ymax）。2.從y=ymin到y=ymax，每次用一條掃描線進行填充。3.對一條掃描線填充的過程可分為四個步驟： 求交；排序；交點配對；區間填色。掃描線算法——算法步驟48交點的取整規則：使生成的像素全部位于多邊形之內。（用于直線等圖元掃描轉換的四舍五入原則可能導致部分像素位于多邊形之外，從而不可用）。假定非水平邊與掃描線y=e相交，交點的橫坐標為x，規則如下：掃描線算法——取整規則

規則1：X為小數，即交點落于掃描線上兩個相鄰像素之間時：交點位于左邊界之上，向右取整；交點位于右邊界之上，向左取整；圖5.17取整規則1

規則2：邊界上象素的取舍問題，避免填充擴大化。規定落在右邊邊界上的像素不予填充。（具體實現時，只要對掃描線與多邊形的相交區間左閉右開）圖5.18取整規則2掃描線算法——取整規則規則3：當掃描線與多邊形頂點相交時，交點的取舍，保證交點正確配對。圖5.19取整規則3掃描線算法——取整規則52解決方法：當掃描線與多邊形的頂點相交時，若共享頂點的兩條邊分別落在掃描線的兩邊，交點只算一個；若共享頂點的兩條邊在掃描線的同一邊，這時交點作為零個或兩個。掃描線算法——取整規則53實際處理：只要檢查頂點的兩條邊的另外兩個端點的Y值，兩個Y值中大于交點Y值的個數是0，1，2，來決定取0，1，2個交點。圖5.20取整規則3掃描線算法——取整規則54圖5.21與掃描線相交的多邊形頂點的交點數掃描線算法——取整規則

邊填充邊填充算法的基本思想對于每一條掃描線和每條多邊形邊的交點，將該掃描線上的交點右方的所有像素取補。對多邊形的每條邊作此處理，多邊形的順序隨意。最簡單的邊填充算法填充一個多邊形的示意圖邊填充算法最適用于具有幀緩沖器的圖形系統，可以按照任意順序處理多邊形的邊。在處理邊時，僅訪問與該邊有交點的掃描線上交點右方的像素。處理完所有邊后，按照掃描線順序讀出幀緩沖器的內容，送入顯示設備。本算法簡單易行，但是對于復雜圖形，每一像素點可能會被訪問多次，系統開銷顯然要比有序邊表的算法要大。邊填充算法的優缺點邊填充算法的改進

柵欄：引入一條與掃描線垂直的直線，我們稱之為柵欄，柵欄通常取過多邊形頂點、且把多邊形分為左右兩半。改進的算法——柵欄填充算法—邊標志算法。該算法的基本思想是：1.對多邊形的每條邊進行直線掃描轉換，即對邊界所經過的像素打上邊標志；

2.填充：對每條與多邊形相交的掃描線，按照從左到右的順序，依次訪問該線上的像素。可以使用一個布爾變量來注明當前點的狀態，若點在多邊形內，則inside為真；反之，inside為假。inside的初始值為假，每當當前訪問像素為被打上邊標志的點時，就將此變量取反；對未打標志的像素，不變。對于當前訪問像素，操作之后的值為真，就把該像素置為多邊形色。

種子填充種子填充的思想:假設在多邊形區域內部有一像素已知，從它出發找到區域內的所有像素點。614-連通區域，8-連通區域區域的分類圖5-274－鄰接點與8－鄰接點（a）4－鄰接點（b）8－鄰接點624-連通區域：從區域上的一點出發，通過訪問已知點的4-鄰接點，在不越出區域的前提下，遍歷區域內的所有象素點。8-連通區域：從區域上的一點出發，通過訪問已知點的8-鄰接點，在不越出區域的前提下，遍歷區域內的所有象素點。區域的分類圖5-284－連通與8－連通區域64連通性：4連通可看作8連通區域，但對邊界有要求。對邊界的要求。4連通與8連通區域的區別圖5-294－連通與8－連通區域65種子填充算法種子填充算法允許從四個方向尋找下一個像素，稱為四向算法；允許從八個方向尋找下一個像素，稱為八向算法。

66種子填充算法的思想：可以使用棧結構來實現簡單的種子填充算法。原理如下：種子像素先入棧；只要棧不空時重復下列步驟：1.棧頂像素出棧；2.將出棧像素置成多邊形色；3.按照左、上、右、下順序檢查與出棧像素相鄰的四個像素，如果其中某個像素不在邊界且未置成多邊形色，則把該像素入棧。67改進的種子填充算法簡單的種子填充算法會把太多的像素壓入堆棧，甚至會造成一些像素重復入棧多次的現象，顯然降低了系統的工作效率，除此以外，還要求很大的存儲空間存放棧。為了改進上述算法，采用鏈隊列來實現種子填充算法。改進的種子填充算法該算法的基本思路是：從鏈隊列中獲得一個像素點，判斷其四連通像素點，若沒有填充，則填充它，并將它入隊列，如此循環，直到隊列空為止。對遞歸種子填充算法的改進之處：1.使用鏈隊列：在遞歸種子填充算法中，堆棧是系統預先設定的，使得該算法存在一些缺陷。本算法不使用遞歸，而使用鏈隊列，是因為鏈隊列有兩個特點：一是當鏈隊列為空時，它不占用存儲空間，只當數據入鏈隊列時才分配存儲空間給它；二是由于在定義鏈隊列前沒有限定它的大小，所以從理論上看，有多大的可使用內存，就可以建立多大的鏈隊列。2.在遞歸種子填充算法中，采用的是先入棧，出棧后再填充，即當填充某點時，不管它的四連通點是否已被填充，都要進入堆棧，這會導致很多的冗余像素點入棧。而本算法采用的是先填充再入鏈隊列，在入隊列之前要判斷像素點是否已被填充，若未被填充才入隊列，否則不予考慮。這樣將會減少入隊列的冗余像素，即每一個像素點只入隊列一次。對遞歸種子填充算法的改進之處：71裁剪在二維觀察中，需要在觀察坐標系下對窗口進行裁剪，即只保留窗口內的那部分圖形，去掉窗口外的圖形。假設窗口是標準矩形，即邊與坐標軸平行的矩形，由上（y=wyt）、下（y=wyb）、左（x=wxl）、右（x=wxr）四條邊描述。72裁剪——點的裁剪73二維直線段的裁剪已知條件：（1）窗口邊界wxl，wxr，wyb，wyt的坐標值；（2）直線段端點p1p2的坐標值x1,y1,x2,y2。

p2

p1

p3

p4

實交點：直線段與窗口矩形邊界的交點;虛交點：處于直線段延長線或窗口邊界延長線上的交點。

p5

p675Cohen-Sutherland算法編碼：對于任一端點(x,y)，根據其坐標所在的區域，賦予一個4位的二進制碼D3D2D1D0。編碼規則如下：（1）若x<wxl，D0=1，否則D0=0；（2）若x>wxr，D1=1，否則D1=0；（3）若y<wyb，D2=1，否則D2=0；（4）若y>wyt，D3=1，否則D3=0。0

0

0

0

0

0

1

1

1

0

0

0

0

0

0

1

1

1

1

1

1

0

0

0

0

0

0

1

1

1

0

0

0

0

0

0

77 （1）判斷 裁剪一條線段時，先求出直線段端點p1和p2的編碼code1和code2，然后：

a.若code1|code2=0，對直線段簡取之；

b.若code1&code2≠0，對直線段簡棄之；Cohen-Sutherland算法78 （2）求交 若上述判斷條件不成立，則需求出直線段與窗口邊界的交點。b.上、下邊界交點的計算：x=x1+(y-y1)/k。a.左、右邊界交點的計算：y=y1+k(x-x1)；其中，k＝（y2-y1）/（x2-x1）。Cohen-Sutherland算法79p2

p1

p2

p1

p3p1p2p2p1p2p1p4p1p2Cohen-Sutherland算法80用編碼方法實現了對完全可見和不可見直線段的快速接受和拒絕；求交過程復雜，有冗余計算，并且包含浮點運算，不利于硬件實現。Cohen-Sutherland算法中點分割算法

Cohen-Sutherland算法需要對被裁剪的線段和窗口各邊求交點，如果不斷地在線段的中點處將線段一分為二，則可避免求交運算，該算法就是中點分割算法。該算法還是采用線段端點編碼和相應的檢查方法，核心是檢查最遠可見點的算法。先要判斷完全可見和完全不可見線段，對于部分可見的線段，依次用中點分割的方法求得最遠可見點。82中點分割算法的核心思想是通過二分逼近來確定直線段與窗口的交點。中點分割算法83特點：主要計算過程只用到加法或位移運算，易于硬件實現，同時適合于并行計算。

中點分割算法中點分割算法步驟①判斷直線段P1P2是否全部在窗口外，若是，則結束，無可見段輸出；否則，繼續②；②判斷點P2是否為可見，若是，則P2就是離P1最遠的可見點，結束該算法，否則進行③；③取P1P2中點Pm，如果點PmP2全部在窗口外，則用P1Pm代替P1P2，否則以PmP2代替P1P2，對新的P1P2從第一步重新開始。重復上述過程，直到PmP2的長度小于給定的誤差為止。

中點分割算法步驟

上述過程找到了距點P1最遠的可見點，把兩個端點對調一下，即對直線段P1P2用同樣的算法步驟，即可找出距點P2最遠的可見點。連接這兩個可見點，即得到了要輸出的可見段。86多邊形的裁剪問題的提出：

87Sutherland-Hodgeman多邊形裁剪基本思想：將多邊形的邊界作為一個整體，每次用窗口的一條邊界對要裁剪的多邊形進行裁剪，體現分而治之的思想。88算法實施策略：為窗口各邊界裁剪的多邊形存儲輸入與輸出頂點表。在窗口的一條裁剪邊界處理完所有頂點后，其輸出頂點表將用窗口的下一條邊界繼續裁剪。窗口的一條邊以及延長線構成的裁剪線把平面分為兩個區域，包含窗口區域的區域稱為可見側；不包含窗口區域的域為不可見側。Sutherland-Hodgeman多邊形裁剪89沿著多邊形依次處理頂點會遇到四種情況：Sutherland-Hodgeman多邊形裁剪92特點93假定按順時針方向處理頂點，且將用戶多邊形定義為Ps，窗口矩形為Pw。算法從Ps的任一點出發，跟蹤檢測Ps的每一條邊，當Ps與Pw相交時（實交點），按如下規則處理：(1)若是由不可見側進入可見側，則輸出可見直線段，轉(3)；Weiler-Atherton多邊形裁剪94(2)若是由可見側進入不可見側，則從當前交點開始，沿窗口邊界順時針檢測Pw的邊，即用窗口的有效邊界去裁剪Ps的邊，找到Ps與Pw最靠近當前交點的另一交點，輸出可見直線段和由當前交點到另一交點之間窗口邊界上的線段，然后返回處理的當前交點；(3)沿著Ps處理各條邊，直到處理完Ps的每一條邊，回到起點為止。Weiler-Atherton多邊形裁剪下圖示了Weiler-Atherton算法裁剪凹多邊形的過程和結果。962.文字裁剪 文字裁剪的策略包括幾種：串精度裁剪字符精度裁剪筆劃、象素精度裁剪

3.外部裁剪 保留落在裁剪區域外的圖形部分、去掉裁剪區域內的所有圖形，這種裁剪過程稱為外部裁剪，也稱空白裁剪。其他裁剪97直線線寬的處理圓弧線寬的處理線型的處理線寬與線型的處理

98線刷子：垂直刷子、水平刷子線型與線寬——線寬線刷子線刷子原理“線刷子”的原理：如果直線斜率在-1和1之間，就把“刷子”設置成鉛垂方向，刷子的中點對準直線一端點，然后讓“刷子”的中心朝著直線的另一端移動，這樣就可以生成具有一定寬度的直線；如果直線的斜率不在-1和1之間，則把“刷子”設置成水平方向。實現上述算法時，只要將直線掃描變換算法的內循環做一下修改就可以。線帽可以通過添加“線帽”來調整