第三章基本圖形生成

計(jì)算機(jī)圖形學(xué)

第三章基本圖形生成信電學(xué)院王利娟本章內(nèi)容3.1直線的生成3.2圓與橢圓的生成3.3區(qū)域填充3.5線寬與線型的處理本章預(yù)備知識(shí)光柵顯示輸出技術(shù)

目前，主要圖形輸出設(shè)備如計(jì)算機(jī)顯示器、打印機(jī)等都采用光柵顯示輸出技術(shù)。

光柵顯示技術(shù)：顯示器屏幕或打印機(jī)上打印出的圖形可以認(rèn)為是由許多像素點(diǎn)組成。

★像素點(diǎn)的坐標(biāo)位置(x,y)必須為整數(shù)值?！锟刂葡袼攸c(diǎn)的顏色值來顯示圖形或文字。本章預(yù)備知識(shí)光柵（點(diǎn)陣）顯示輸出技術(shù)屏幕分辨率為M×N大小，固定排列方式xy設(shè)備坐標(biāo)系像素(10,5)(4,6)(0,0)本章預(yù)備知識(shí)選擇繪制基本圖形的坐標(biāo)系？世界坐標(biāo)系，

為直角坐標(biāo)系xy本章預(yù)備知識(shí)如何在屏幕上繪制生成基本圖形？

通過在屏幕（或顯示設(shè)備）上確定生成一個(gè)圖形

所需的一個(gè)像素集合及其顏色。該過程稱為圖形的掃描轉(zhuǎn)換或圖形的光柵化。所謂的基本圖形生成原理，是指在點(diǎn)陣（光柵）輸出設(shè)備的情況下，如何對一條斜的直線或彎曲的曲線盡可能快地輸出其最接近理想的直線或曲線，即如何以最快的速度確定最佳逼近于圖形的像素集。本章預(yù)備知識(shí)直線的掃描轉(zhuǎn)換或光柵化

數(shù)學(xué)直線：由無窮多個(gè)無限小連續(xù)點(diǎn)組成本章預(yù)備知識(shí)圖形的掃描轉(zhuǎn)換或光柵化

屏幕上顯示直線：由盡可能接近直線的像素點(diǎn)集合并填充顏

色來表示。(1,1)(2,1)

(3,2)(4,2)

(5,3)(6,3)

(7,4)(8,4)寫像素的函數(shù)：putpixel(x,y,color)第3章基本圖形生成3.1直線的生成問題：如何發(fā)現(xiàn)最佳逼近直線的像素集？3.1.1數(shù)值微分算法3.1.2中點(diǎn)畫線算法3.1.3Bresenham畫線算法第3章基本圖形生成3.1直線的生成3.1.1數(shù)值微分（DDA）算法利用直線的微分方程生成直線k表示斜率；b表示y軸截距設(shè)直線端點(diǎn)為(x1,y1)和(x2,y2),斜率截距方程為：斜率k就是直線的微分該式子稱為

直線的微分方程第3章基本圖形生成3.1直線的生成3.1.1數(shù)值微分（DDA）算法利用直線的微分方程生成直線考慮讓x從起點(diǎn)到終點(diǎn)變化，每步遞增或遞減1，討論:若生成直線斜率|k|<1設(shè)直線上前一點(diǎn)為(xi,yi)，隨后一點(diǎn)為(xi+1,yi+1)如何查找最逼近該直線的像素集？第3章基本圖形生成3.1直線的生成3.1.1數(shù)值微分（DDA）算法利用直線的微分方程生成直線討論:若生成直線|k|<1設(shè)直線上前一點(diǎn)為(xi,yi)，

隨后一點(diǎn)為(xi+1,yi+1)(xi+1,yi+1)點(diǎn)(xi,yi)(xi+1,yi+1)需要轉(zhuǎn)換為最近的整像素位置點(diǎn)，(xk,yk)，(xk+1,yk+1)(xk,yk)(xi+1,(int)(yi+k+0.5)第3章基本圖形生成3.1直線的生成3.1.1數(shù)值微分（DDA）算法利用直線的微分方程生成直線考慮讓y從起點(diǎn)到終點(diǎn)變化，每步遞增或遞減1，討論:若生成直線斜率|k|>1設(shè)直線上前一點(diǎn)為(xi,yi)，隨后一點(diǎn)為(xi+1,yi+1)(xi+1,yi+1)(xi,yi)(xk,yk)(xk+1,yk+1)第3章基本圖形生成3.1直線的生成3.1.1數(shù)值微分（DDA）算法利用直線的微分方程生成直線讓y從起點(diǎn)到終點(diǎn)變化，每步遞增或遞減1，討論:若生成直線斜率|k|>1(xi+1,yi+1)(xi,yi)(xk,yk)(xk+1,yk+1)第3章基本圖形生成3.1直線的生成3.1.1數(shù)值微分（DDA）算法利用直線的微分方程生成直線若生成直線斜率|k|=1若生成直線斜率|k|=0若生成直線斜率|k|=∞復(fù)習(xí)

繪圖軟件程序設(shè)計(jì)如何在屏幕上繪制生成基本圖形？光柵掃描顯示技術(shù)直線的生成數(shù)值微分DDA算法直線的微分方程:|k|<1;

|k|>1;

|k|=1;

|k|=0;

|k|=第3章基本圖形生成3.1直線的生成3.1.1數(shù)值微分（DDA）算法利用直線的微分方程生成直線算法代碼：算法中根據(jù)|k|來決定是x變化還是y變化假設(shè)直線兩端點(diǎn)：

計(jì)算kdx=x2－

x1;dy=y2－

y1;if(dx≠0)k=dy/dx;

判斷k的取值范圍分成|k|≤1和|k|>1兩種情況if(k<=1&&k>=-1){}else{}確定每步遞增還是遞減，并確定像素點(diǎn)一般認(rèn)為A(x1,y1)為起點(diǎn)，B(x2,y2)為終點(diǎn)，所以x＝x1,y＝y(tǒng)1;|k|≤1時(shí)，x每步改變1，計(jì)算y±＝k

if(x1＜x2)

for(x＝x1;x＜x2;x＋＋)

{putpixel(x,int(y+0.5),color);y＋＝k;}

else

for(x＝x1;x＞＝x2;x－－)

{putpixel(x,int(y+0.5),color);y－＝k;}確定每步遞增還是遞減，并確定像素點(diǎn)|k|>1時(shí)，y每步改變1，計(jì)算x±=1/k

if(y1＜y2)

for(y＝y(tǒng)1;y＜y2;y＋＋){putpixel(int(x+0.5),y,color);x＋＝1／k;}

else

for(y＝y(tǒng)1;y＞＝y(tǒng)2;y－－){putpixel(int(x＋0.5),y,color);x－＝1／k;}確定每步遞增還是遞減，并確定像素點(diǎn)|k|>1時(shí)，y每步改變1，計(jì)算x±=1/k

if(y1＜y2)

for(y＝y(tǒng)1;y＜y2;y＋＋){putpixel(int(x+0.5),y,color);x＋＝1／k;}

else

for(y＝y(tǒng)1;y＞＝y(tǒng)2;y－－){putpixel(int(x＋0.5),y,color);x－＝1／k;}|k|=∞的特殊情況（即豎直線：x1＝x2)if(y1＜y2

)

for(y＝y(tǒng)1;y＜＝y(tǒng)2;y＋＋

)putpixel(x,y,color);

else

for(y＝y(tǒng)1;y＞＝y(tǒng)2;y－－

)putpixel(x,y,color);第3章基本圖形生成3.1直線的生成3.1.1數(shù)值微分（DDA）算法利用直線的微分方程生成直線例：畫直線段P0(0,0)－－P1(5,2)

計(jì)算直線斜率

沿著x方向查找像素集xi+1=xi+1yi+1=yi+kint(yi+1+0.5)

0 0 01 0.40 2 0.81 3 1.21 4 1.62 5 2.02 int()表示向下取整的函數(shù)3.1.2中點(diǎn)畫線算法第3章基本圖形生成3.1直線的生成分析直線生成算法，總結(jié)規(guī)律（以k[0,1]為例）：

若直線在x方向增加一個(gè)像素單位，則在y方向增量只能在01之間。設(shè)直線上當(dāng)前像素點(diǎn)為P0(xk,yk),則下一個(gè)最逼近直線的像素點(diǎn)只能在其正右方或右上方。中點(diǎn)畫線法的算法表達(dá)式：3.1.2中點(diǎn)畫線算法第3章基本圖形生成3.1直線的生成問題：如何判斷M與Q點(diǎn)的關(guān)系？3.1.2中點(diǎn)畫線算法第3章基本圖形生成3.1直線的生成設(shè)直線兩端點(diǎn)為(x1,y1)，(x2,y2)直線的線性方程令3.1.2中點(diǎn)畫線算法第3章基本圖形生成3.1直線的生成根據(jù)直線方程點(diǎn)在直線上點(diǎn)在直線上方點(diǎn)在直線下方欲判斷M點(diǎn)是在Q點(diǎn)上方還是在Q點(diǎn)下方，只需把M代入F(x,y),并檢查它的符號(hào)。3.1.2中點(diǎn)畫線算法第3章基本圖形生成3.1直線的生成構(gòu)造判別式當(dāng)d<0，M在直線(Q點(diǎn))下方，取右上方P2；當(dāng)d>0，M在直線(Q點(diǎn))上方，取正右方P1；當(dāng)d=0，選P1或P2均可，

約定取P1；能否采用增量算法呢？把M代入F(x,y)采用增量計(jì)算dd≥0時(shí)，取正右方像素P1，再下一個(gè)像素的判斷，計(jì)算d1d<0時(shí)，取右上方像素P2，再下一個(gè)像素的判斷，計(jì)算d2d的增量為ad的增量為a+bd的初值第一個(gè)像素取左端點(diǎn)(x1,y1)，則判斷第二個(gè)像素的判別式為：算法運(yùn)行中只使用d的符號(hào)，增量a或a+b都是整數(shù)，只有初始值包含小數(shù)，因此，把d以及增量都擴(kuò)大2倍，即擺脫了小數(shù)，也不會(huì)改變符號(hào)

中點(diǎn)畫線法的迭代表達(dá)式

程序分析

參數(shù)計(jì)算a＝y(tǒng)1－y2;b＝x2－x1;

d0以及增量

d0＝2a＋b;d1=2a;d2=2(a＋b)

循環(huán)結(jié)構(gòu)確定像素x＝x1;y＝y(tǒng)1;putpixel(x,y,color)

for(x＝x1;x＜＝x2;x

＋＋){if(d＜0){y＋＋

;d＋＝d2;}

else{d＋＝d1;}

putpixel(x,y,color);}例：用中點(diǎn)畫線法畫直線段P0(0,0)－－P1(5,2)3.1.2中點(diǎn)畫線算法第3章基本圖形生成3.1直線的生成

計(jì)算a＝y(tǒng)1－y2＝－2；b＝x2－x1＝5

計(jì)算參數(shù)：

d0＝2a＋b=12a＝－42(a＋b)＝6

xk

dk

yk 0 d0=1 0 1 d1=d0+2a=－3 0 2 d2=d1+2(a+b)=3

1 3 d3=d2+2a=－1

1

4 d4=d3+2(a+b)=525d5=d4+2a=42例：用中點(diǎn)畫線法畫直線段P0(0,0)－－P1(5,2)3.1.2中點(diǎn)畫線算法第3章基本圖形生成3.1直線的生成(0,0)(1,0)(2,1)(3,1)(4,2)(5,2)3.1.3Bresenham畫線算法第3章基本圖形生成3.1直線的生成基本原理:構(gòu)造決策變量dk來確定下一個(gè)像素點(diǎn)if(d1>d2)，取P2if(d1<d2)，取P1構(gòu)造dk=△x(d1-d2)，根據(jù)dk的符號(hào)確定下一個(gè)像素考慮0<k<1情況3.1.3Bresenham畫線算法第3章基本圖形生成3.1直線的生成計(jì)算dkif(dk>0)，直線理想位置接近右上方像素P2(xk+1,yk+1)if(dk<0)，直線理想位置接近正右方像素P1(xk+1,yk)if(dk=0)，約定取右上方點(diǎn)P2(xk+1,yk+1)計(jì)算dk每步的增量取右上方像素P2時(shí)，yk+1=yk+1，增量為：2△y-2△x取正右方像素P1時(shí)，yk+1=yk，增量為：2△y3.1.3Bresenham畫線算法第3章基本圖形生成3.1直線的生成計(jì)算初始判別量d13.1.3Bresenham畫線算法第3章基本圖形生成3.1直線的生成Bresenham畫線法的迭代表達(dá)式程序分析

參數(shù)計(jì)算dx＝x2－x1;dy＝y(tǒng)2－y1;dp＝2dy－dx;

循環(huán)確定下一像素

y＝y(tǒng)1;

for(x＝x1;x＜＝x2;x＋＋){putpixel(x,y,color)；

if(dp＞＝0){y＋＋;dp－＝2dx;}

dp＋＝2*dy;}例：用Bresenham畫線法畫直線段,給出兩端點(diǎn)

為：P0(20,10)－－P1(30,18)3.1.3Bresenham畫線算法第3章基本圖形生成3.1直線的生成

計(jì)算△y

，△x

△y＝

y2－

y1＝8；

△x＝

x2－

x1＝10

計(jì)算參數(shù)dk：

d0＝2△y－△x＝62△y＝162△y－2△x＝－4

例：用Bresenham畫線法畫直線段,給出兩端點(diǎn)

為：P0(20,10)－－P1(30,18)3.1.3Bresenham畫線算法第3章基本圖形生成3.1直線的生成idi(xi+1,yi+1)idi(xi+1,yi+1)06(21,11)56(26,15)12(22,12)62(27,16)2-2(23,12)7-2(28,16)314(24,13)814(29,17)410(25,14)910(30,18)

d0＝2△y－△x＝62△y＝162△y－2△x＝－4

2021222530101518例：用Bresenham畫線法畫直線段,給出兩端點(diǎn)

為：P0(20,10)－－P1(30,18)3.1.3Bresenham畫線算法第3章基本圖形生成3.1直線的生成(21,11),(22,12),(23,12),(24,13),(25,14),(26,15),(27,16),(28,16),(29,17),(30,18)第3章基本圖形生成3.2圓與橢圓的生成問題：如何發(fā)現(xiàn)最佳逼近圓或橢圓的像素集？3.2.1圓的特性3.2.2中點(diǎn)畫圓算法3.2.3Bresenham畫圓算法3.2.4橢圓的生成算法3.2.1圓的特性第3章基本圖形生成3.2圓與橢圓的生成圓的直角坐標(biāo)方程畫圓方法一

沿x軸從xc－r到xc＋r以單位步長改變，并計(jì)算相應(yīng)y值計(jì)算量大，所畫像素位置間距不一致，x的改變量均勻，但y不一致3.2.1圓的特性第3章基本圖形生成3.2圓與橢圓的生成圓的極坐標(biāo)參數(shù)方程畫圓方法二采用極坐標(biāo)形式，以固定角度為邊長，可以繪出等距點(diǎn)，但牽涉到三角函數(shù)調(diào)用、浮點(diǎn)運(yùn)算，速度太慢減少計(jì)算量是關(guān)鍵

圓的對稱性只要畫出其中一個(gè)8

分圓，根據(jù)對稱性可

得另外7個(gè)8分圓上的

對應(yīng)點(diǎn)關(guān)鍵為一個(gè)8分圓的

生成算法3.2.1圓的特性第3章基本圖形生成3.2圓與橢圓的生成處理對象：圓心在原點(diǎn)的圓??；一般取第一象限內(nèi)以y=x為界的上半部分，即第二8分圓3.2.2中點(diǎn)畫圓算法第3章基本圖形生成3.2圓與橢圓的生成基本原理Q在M上（M在Q下），取P1Q在M下（M在Q上），取P2考慮對象：中心在原點(diǎn)的圓的第二8分圓；第3章基本圖形生成3.2圓與橢圓的生成3.2.2中點(diǎn)畫圓算法構(gòu)造函數(shù)：

圓上的點(diǎn)F(x,y)＝0

圓外的點(diǎn)F(x,y)＞0

圓內(nèi)的點(diǎn)F(x,y)＜0第3章基本圖形生成3.2圓與橢圓的生成3.2.2中點(diǎn)畫圓算法設(shè)M是P1和P2的中點(diǎn)，即M＝(xp＋1,yp－0.5),

當(dāng)F(M)＜0時(shí)，M在圓內(nèi)，說明P1距離圓弧更近，取P1；當(dāng)F(M)＞0時(shí)，P取P2第3章基本圖形生成3.2圓與橢圓的生成3.2.2中點(diǎn)畫圓算法構(gòu)造判別式：if(d>0)，中點(diǎn)M在圓外，Q距P2近，取右下方點(diǎn)P2作為下一個(gè)像素if(d<0)，中點(diǎn)M在圓內(nèi)，Q距P1近，取正右邊點(diǎn)P1作為下一個(gè)像素if(d＝0)，中點(diǎn)M在圓上，約定取右下方點(diǎn)P2

計(jì)算增量

d＜0時(shí)，取正右方像素P1，再下一個(gè)像素的判斷，計(jì)算d1

d≥0時(shí)，取右下方像素P2，再下一個(gè)像素的判斷，計(jì)算d2d的增量為2xp＋3d的增量為2(xp－yp)＋5

計(jì)算d的初值順時(shí)針方向生成第二個(gè)8分圓，所以第一個(gè)像素取為(0,r)，則判斷第二個(gè)像素的判別式為：d0包含小數(shù)，而e=d0-0.25=1-r為整數(shù)算法中判別d的符號(hào)，等同于判斷e是否大于-0.25d的增量都是整數(shù)，因此，e始終為整數(shù)，所以，判斷e>-0.25與e>0等同。算法中有浮點(diǎn)數(shù)，用e＝d－0.25代替

中點(diǎn)畫圓法的迭代表達(dá)式程序分析賦初值d＝1－r;x＝0;y＝r;循環(huán)確定下一像素While(x＜＝y(tǒng)){if(d＜0)d＋＝2*x＋3；

else{d＋＝2*(x－y)＋5;y－－;}

x＋＋;

WholeCircle(xc,yc,x,y,color);}第3章基本圖形生成3.2圓與橢圓的生成3.2.2中點(diǎn)畫圓算法第3章基本圖形生成3.2圓與橢圓的生成3.2.3Bresenham畫圓算法設(shè)Pi(xi,yi)是已經(jīng)選取的一個(gè)像素點(diǎn)，根據(jù)這段第二8分圓的特點(diǎn)，可以判定下一個(gè)像素將從Hi(xi+1,yi)和Di(xi+1,yi-1)兩點(diǎn)中選取第3章基本圖形生成3.2圓與橢圓的生成3.2.3Bresenham畫圓算法構(gòu)造函數(shù)：第3章基本圖形生成3.2圓與橢圓的生成3.2.3Bresenham畫圓算法引入判別式根據(jù)di的符號(hào)可以選擇候選像素為Di還是Hi

。如果di≥0,則應(yīng)選取Di;如果di<0,則應(yīng)選取Hi;

第3章基本圖形生成3.2圓與橢圓的生成3.2.3Bresenham畫圓算法像素迭代計(jì)算di每步的增量如果di<0,應(yīng)選擇Hi,則下一點(diǎn)(xi+1,yi)的判別式是如果di>0,應(yīng)選擇Di,則下一點(diǎn)(xi+1,yi-1)的判別式是第3章基本圖形生成3.2圓與橢圓的生成3.2.3Bresenham畫圓算法像素迭代計(jì)算di每步的增量對于初值d0,x0=0,y0=r第3章基本圖形生成3.2圓與橢圓的生成3.2.3Bresenham畫圓算法Bresenham畫圓法的迭代表達(dá)式，圓弧靠近P1，圓弧靠近P2第3章基本圖形生成3.2圓與橢圓的生成3.2.3Bresenham畫圓算法程序分析參數(shù)計(jì)算x＝0;y＝r;d＝3－2*r;循環(huán)確定下一像素While(x＜y){WholeCircle(xc,yc,x,y,color);

if(d＜0)d＋＝4*x＋

6；

else{d＝4*(x－y)＋10;y－－;}

x＋＋;}if(x＝＝y(tǒng))WholeCircle(xc,yc,x,y,color);復(fù)習(xí)當(dāng)在屏幕上顯示一條直線時(shí)，在顯示器所給定的有限個(gè)像素矩陣中，確定發(fā)現(xiàn)最佳逼近該直線的像素集，并且按掃描順序?qū)@些像素進(jìn)行寫操作。這就是用顯示器繪制直線或直線的掃描轉(zhuǎn)換3.1直線的生成（直線的掃描轉(zhuǎn)換）1.什么是直線的掃描轉(zhuǎn)換？2.掌握DDA畫線、中點(diǎn)畫線和Bresenham畫線算法步驟和計(jì)算？3.直線生成規(guī)律①生成直線斜率k[0,1],（正右方）（右上方）

中點(diǎn)畫線法的迭代表達(dá)式令Bresenham畫線法的迭代表達(dá)式3.2圓與橢圓的生成基本思想：確定發(fā)現(xiàn)最佳逼近圓或橢圓的像素集，并且按掃描順序?qū)@些像素進(jìn)行寫操作。這就是圓或橢圓的掃描轉(zhuǎn)換

只要畫出其中一個(gè)8分圓，根據(jù)對稱性可得另外7個(gè)8分圓上的對應(yīng)點(diǎn)。關(guān)鍵為一個(gè)第二8分圓的生成算法圓心在原點(diǎn)的圓弧；一般取第一象限內(nèi)以y=x為界的上半部分，即第二8分圓1.如何生成一個(gè)圓?。?.2圓與橢圓的生成2.分析第二8分圓生成規(guī)律？生成第二8分圓規(guī)律第一象限內(nèi)以y=x為界的上半部分（正右方）（右下方）第二8分圓起始點(diǎn)：(0,R);終止條件為x=y;3.掌握中點(diǎn)畫圓和Bresenham畫圓算法

步驟和計(jì)算？

中點(diǎn)畫圓法的迭代表達(dá)式Bresenham畫圓法的迭代表達(dá)式，圓弧靠近P1，圓弧靠近P2第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法長半軸為a，短半軸為b，中心為原點(diǎn)的標(biāo)準(zhǔn)橢圓ab

根據(jù)橢圓對稱性的特點(diǎn),考慮對象：第一象限1/4橢圓弧(x,y)(－x,y)(－x,－y)(x,－y)N以弧上斜率為-1的點(diǎn)作為分界45o把橢圓弧分為上下兩部分上部分橢圓弧生成？？下部分橢圓弧生成？？上部分下部分第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：如何區(qū)分開上半部分和下半部分橢圓??？ab上部分下部分構(gòu)造函數(shù)：

弧上斜率為-1的分界點(diǎn)(xN,yN)：1/4橢圓弧上部分：1/4橢圓弧下部分：(xN,yN)F(xN,yN)=02b2xN=2a2yN第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法構(gòu)造函數(shù)：說明(x,y)在橢圓邊界內(nèi)說明(x,y)在橢圓邊界外說明(x,y)在橢圓邊界上第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的上半部分的生成算法？沿著x方向來確定下一像素點(diǎn)。PP1P2M對于當(dāng)前確定弧上像素點(diǎn)P(xp,yp)M為候選像素點(diǎn)P1和P2的中點(diǎn)M＝(xp＋1,yp－0.5)中點(diǎn)畫橢圓法判別式：第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的上半部分的生成算法？中點(diǎn)畫橢圓法M為候選像素點(diǎn)P1和P2的中點(diǎn)判別式：if(dp>0)，M在橢圓外，下一個(gè)像素取右下方點(diǎn)P2if(dp<0)，M在橢圓內(nèi)，下一個(gè)像素取正右邊點(diǎn)P1if(dp=0)，約定取右下方點(diǎn)P2第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的上半部分的生成算法？if(dp<0),取正右方像素P1，再下一個(gè)像素的判斷，計(jì)算M第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的上半部分的生成算法？if(dp≥0

),取右下方像素P2，再下一個(gè)像素的判斷，計(jì)算M第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的上半部分的生成算法？M取弧起點(diǎn)P0(0,b)，再下一個(gè)像素的判斷，計(jì)算第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的上半部分的生成算法？滿足：第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的下半部分的生成算法？沿著y方向來確定下一像素點(diǎn)。PP1P2M對于當(dāng)前確定弧上像素點(diǎn)P(xp,yp)M為候選像素點(diǎn)P1和P2的中點(diǎn)M＝(xp＋0.5,yp－1)中點(diǎn)畫橢圓法判別式：第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的下半部分的生成算法？PP1P2MM為候選像素點(diǎn)P1和P2的中點(diǎn)中點(diǎn)畫橢圓法判別式：if(dp>0)，M在橢圓外，下一個(gè)像素取正下方點(diǎn)P1if(dp<0)，M在橢圓內(nèi)，下一個(gè)像素取右下方點(diǎn)P2if(dp=0)，約定取右下方點(diǎn)P2第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的下半部分的生成算法？if(dp<0),取右下方像素P2，再下一個(gè)像素的判斷，計(jì)算M第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的下半部分的生成算法？if(dp≥

0),取正下方像素P1，再下一個(gè)像素的判斷，計(jì)算M第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的下半部分的生成算法？下半部分中點(diǎn)判別式d0初始值：M若上半部分橢圓弧生成的最后一個(gè)像素為(xp,yp)，則下半部分第一個(gè)中點(diǎn)為：(xp＋0.5,yp－1)為由上部分轉(zhuǎn)入下部分條件滿足時(shí)的值第3章基本圖形生成3.2圓與橢圓的生成3.2.4橢圓的生成算法問題：1/4橢圓弧的下半部分的生成算法？滿足：第3章基本圖形生成3.3區(qū)域填充討論問題：如何用一種顏色或圖案來填充一個(gè)2-D區(qū)域，該區(qū)域可為多邊形、圓或橢圓，甚至是帶孔的一般步驟確定那些像素位于填充圖元的內(nèi)部；確定以什么顏色填充這些像素；第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法3.3.2邊填充算法3.3.3種子填充算法3.3.4圓和橢圓的填充算法顏色填充封閉區(qū)域算法圖案填充封閉區(qū)域算法3.3.5圖案填充第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法對于若干邊所構(gòu)成的區(qū)域，用掃描線y＝i掃描，計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間的像素問題1：多邊形區(qū)域掃描線填充算法?以掃描線“6”為例與多邊形的邊界交于A、B、C、D四個(gè)點(diǎn)把掃描線劃分為五個(gè)區(qū)間①②③④⑤其中②和④落在多邊形內(nèi)，該區(qū)間內(nèi)像素應(yīng)取填充色，其余區(qū)間的像素取背景色！0112233445566778891011P2(5,1)EP3(11,3)DP4(11,8)GFCBP5(5,5)P6(2,7)AP1(2,2)①②③④⑤多邊形P1P2P3P4P5P6，注意相交順序及交點(diǎn)排序問題第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題2：多邊形區(qū)域掃描線填充算法步驟：1．求交計(jì)算掃描線與多邊形各邊的所有交點(diǎn)；2．排序按x坐標(biāo)遞增順序?qū)稽c(diǎn)進(jìn)行排序；3．交點(diǎn)配對第1、2個(gè)，第3、4個(gè)為一對等等，每對代表一個(gè)區(qū)間4．區(qū)間填色區(qū)間內(nèi)像素置成填充色，區(qū)間外像素置成背景色第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題3：多邊形頂點(diǎn)處的掃描線交點(diǎn)取舍：情況1：共享頂點(diǎn)的兩條邊在掃描線的兩邊

掃描線交點(diǎn)只能算一個(gè)如掃描線2，邊P6P1、P1P2位于掃描線2的兩邊，交點(diǎn)算一個(gè)，即掃描線2與多邊形的交點(diǎn)為2、8，給區(qū)間[2,8]著色第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題3：多邊形頂點(diǎn)處的掃描線交點(diǎn)取舍：情況2：共享頂點(diǎn)的兩條邊在掃描線的一邊

掃描線交點(diǎn)可算零個(gè)或兩個(gè)取0還是2，取決于該點(diǎn)是多邊形的局部最高點(diǎn)

還是局部最低點(diǎn)如掃描線1，與多邊形交于點(diǎn)頂點(diǎn)P2，共享該頂點(diǎn)的另外兩條邊的另外兩個(gè)頂點(diǎn)均高于P2，故取交點(diǎn)P2兩次，即像素P2用多邊形填充色著色如掃描線7，與多邊形交于頂點(diǎn)P6，邊P6P1、P5P6的另外兩頂點(diǎn)均低于P6點(diǎn)，所以，取交點(diǎn)P6

0次，P6點(diǎn)不填充第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題3：多邊形頂點(diǎn)處的掃描線交點(diǎn)取舍：第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題4：活化邊表（Active-Edge-Table）AET的概念

活化邊表（Active-Edge-Table）與當(dāng)前掃描線相交的邊稱為活化邊，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中，此鏈表稱為活化邊表！引入活化邊表的概念，目的在于提高計(jì)算效率，在處理每一條掃描線時(shí)，不必將其與所有邊求交，只需考慮與活化邊求交即可！第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題4：活化邊表活化邊表AET的結(jié)點(diǎn)內(nèi)容：

x：當(dāng)前掃描線與邊的交點(diǎn)坐標(biāo)

△x：從當(dāng)前掃描線到下一條掃描線間的x增量

ymax：該邊所交的最高掃描線號(hào)，邊上最高的頂點(diǎn)掃描線6的活性邊表P6P1P5P6P4P5P3P4ABCD掃描線7的活性邊表P4P5P3P49281108∧FG第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題4：活化邊表

更新活化邊表每離開一條掃描線，進(jìn)入下一條掃描線之前，應(yīng)做的工作：

將與當(dāng)前掃描線相交而與下一條掃描線不相交的邊，從AET表中清除！將下一條掃描線新交上的邊，加入AET中適當(dāng)?shù)奈恢茫?/p>

活化邊表(AET)的作用

通過AET，可以充分利用邊的連貫性和掃描線的連貫性，減少求交計(jì)算量，提高排序效率

新邊表(NET)概念的引入為了方便活化邊表的建立與更新，為每條掃描線建立一個(gè)新的邊表稱之為NET（New-Edge-Table

）第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題5：AET&NET第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題6：有序邊表(SET)或新邊表(NET)概念構(gòu)建新邊表為每一條掃描線建立一個(gè)新邊表，存放在該掃描線第一次出現(xiàn)的邊若某邊的較低端點(diǎn)為ymin，則該邊就存放在掃描線ymin的邊表中，邊表的每個(gè)結(jié)點(diǎn)存放對應(yīng)邊的初始信息：lower.x，△x，以及該邊的最大y值ymax構(gòu)建新邊表第3章基本圖形生成3.3區(qū)域填充3.3.1有序邊表填充算法問題5：有序邊表填充算法步驟輸入多邊形的頂點(diǎn)數(shù)及其頂點(diǎn)坐標(biāo)求填充區(qū)域的掃描線最大值、最小值對處理范圍內(nèi)的每條掃描線建立有序邊表對處理范圍內(nèi)的每條掃描線，進(jìn)行處理用有序邊表建立當(dāng)前掃描線的活化邊表從活化邊表中依次取出一對交點(diǎn)，對這兩個(gè)交點(diǎn)內(nèi)的像素填充為下一條掃描線更新活化邊表，即增加交點(diǎn)的x值和刪除不再相交的邊重新活化邊表復(fù)習(xí)：3.2圓與橢圓的生成1.如何生成第一象限1/4橢圓??？以弧上斜率為-1的點(diǎn)作為分界，把第一象限1/4橢圓弧分為上下兩部分：上部分圓弧點(diǎn)：起始點(diǎn)(0,b)，條件：2b2x2a2y

在x方向取單位步長下部分圓弧點(diǎn)：終點(diǎn)(a,0)

，條件：2b2x2a2y

在y方向取單位步長（正右方）（右下方）（右下方）（正下方）復(fù)習(xí)：3.3區(qū)域填充1.有序邊表填充算法？①基本原理：按照掃描線從小到大（由下而上）的移動(dòng)順序，計(jì)算當(dāng)前掃描線與多邊形各邊交點(diǎn)，然后把這些交點(diǎn)按x值遞增順序進(jìn)行排序、配對，以確定填充區(qū)間，然后用指定顏色填充區(qū)間內(nèi)所有像素。②步驟：求交；排序；交點(diǎn)配對；填充顏色復(fù)習(xí)：3.3區(qū)域填充1.有序邊表填充算法？③求交問題：多邊形頂點(diǎn)與當(dāng)前掃描線的交點(diǎn)？復(fù)習(xí)：3.3區(qū)域填充1.有序邊表填充算法？④活化邊表AET的建立多邊形與當(dāng)前掃描線相交的邊稱為活化邊，把它們按與掃描線交點(diǎn)x坐標(biāo)遞增的順序存放在一個(gè)鏈表中，此鏈表稱為活化邊表。xΔxymaxnext當(dāng)前掃描線與邊的交點(diǎn)x坐標(biāo)從當(dāng)前掃描線到下一條掃描線間的x增量該邊所交的最高掃描線號(hào)復(fù)習(xí)：3.3區(qū)域填充1.有序邊表填充算法？⑤新邊表NET的建立——活化邊表的改進(jìn)X0|yminΔxymaxnext邊低端(y值較小的端點(diǎn))所對應(yīng)的x坐標(biāo)從當(dāng)前掃描線到下一條掃描線間的x增量該邊所交的最高掃描線號(hào)第3章基本圖形生成3.3區(qū)域填充3.3.2邊填充算法

原理是一種實(shí)區(qū)域掃描轉(zhuǎn)換算法。對每一條掃描線和多邊形的每條邊的交點(diǎn)（x,y)右方的所有像素取補(bǔ)。二次取補(bǔ)等于抹掉。邊填充算法示意圖P1P2P3P4P5P1P5P5P4P4P3P3P2如果按其它順序填充，會(huì)如何？邊填充算法示意圖缺點(diǎn)：每個(gè)象素可能訪問多次，輸入/輸出量大；圖形輸出不能與掃描同步進(jìn)行，只能全部畫完才能打印。P3P2P3P4P5P4P5P6P2P3P3P4P4P5P5P1按

任

意

順

序

填

充，

結(jié)

果

相

同第3章基本圖形生成3.3區(qū)域填充3.3.2邊填充算法

柵欄填充算法引入柵欄，以減少填充算法訪問像素的次數(shù)。柵欄：與掃描線垂直的線，通常過一頂點(diǎn)，且把多邊形一分為二?；舅枷耄簩γ織l掃描線與多邊形邊的交點(diǎn)，將交點(diǎn)和柵欄之間的像素取補(bǔ)。減少了像素訪問數(shù)目，但不徹底。

若交點(diǎn)位于柵欄左側(cè)，將交點(diǎn)之右至柵欄之左所有像素取補(bǔ)；若交點(diǎn)位于柵欄左側(cè)，將交點(diǎn)之右至柵欄之左所有像素取補(bǔ)；柵欄填充算法示意圖P1P2P3P4P5P2P3P3P4P4P5P5P1第3章基本圖形生成3.3區(qū)域填充3.3.3種子填充算法

原理

不是按掃描線順序進(jìn)行填充多邊形區(qū)域的。填充方法是從多邊形區(qū)域內(nèi)部的一點(diǎn)開始，由此出發(fā)找到區(qū)域內(nèi)所有像素，區(qū)域內(nèi)部所有像素顏色值和區(qū)域邊界上顏色值不同。區(qū)域邊界外像素可具有與邊界像素相同顏色值。第3章基本圖形生成3.3區(qū)域填充3.3.3種子填充算法

區(qū)域指已經(jīng)表示成點(diǎn)陣形式的填充圖形，它是像素的集合區(qū)域可分為4向連通區(qū)域和8向連通區(qū)域

區(qū)域填充

指先將區(qū)域的一點(diǎn)賦予指定的顏色，然后將該顏色擴(kuò)展到整個(gè)區(qū)域的過程區(qū)域填充算法要求區(qū)域是連通的從當(dāng)前點(diǎn)檢測相鄰像素的方法

四向連通八向連通4連通與8連通區(qū)域

算法原理種子像素入棧當(dāng)棧非空時(shí)，重復(fù)以下步驟：棧頂像素出棧；將出棧像素置成填充色；按“右→上→左→下”的順序檢查與出棧像素相鄰的四像素，若其中某像素不在邊界上且未被置成填充色，則將其入棧！第3章基本圖形生成3.3區(qū)域填充3.3.3種子填充算法種子填充算法演示6754S9328S247938479484795684796847978479847994794796754S9328S799第3章基本圖形生成3.3區(qū)域填充3.3.3種子填充算法

存在問題

簡單的種子填充算