圓弧與線寬及屬性

掃描轉(zhuǎn)換圓弧A

-直接生成B-多邊形逼近法

C-正負(fù)法D-Bresenham算法

掃描轉(zhuǎn)換圓弧A

-直接生成B-多邊形逼近法

C-正負(fù)法D-Bresenham算法A.直接采用圓方程(離散點)

(x-xc)2+(y-yc)2=r2沿x軸從xc-r到xc+r以單位步長計算對應(yīng)的y值來得到圓周每點的位置。每一步包含很大的計算量，而且，所畫像素位置間的間距是不一致的。圓斜率絕對值大于1后，交換x和y來調(diào)整間距。但增加計算量和處理過程。開根，計算量大，不可取。

掃描轉(zhuǎn)換圓弧A

-直接生成B-多邊形逼近法

C-正負(fù)法D-Bresenham算法B-多邊形逼近法圓的正內(nèi)接多邊形逼近法原理計算多邊形各頂點的遞推公式

Xi+1 cosα -sinα

Xi =

Yi+1 sinα cosα

Yi因為:α是常數(shù)，sinα

，cosα只在開始時計算一次。所以，一個頂點只需4次乘法，共4n次乘法，外加直線段的中點算法的計算量。離散點方法取等量的變量但得不到均勻曲線離散角度方法取等量的變量得到均勻曲線以固定角度為步長生成顯示時，圓就可沿圓周等距點繪制出來。沿圓周使用較大的角度分步時，可用直線段連接逼近圓的路徑。為在光柵系統(tǒng)上得到更連續(xù)的邊界，可將步長設(shè)為1/r，繪制的像素位置約為一個單位間隔。消除了不等間距現(xiàn)象開根，三角函數(shù)運算，計算量大，不可取。

問題：給定最大逼近誤差（最大距離）DELTA

，如何確定多邊形的邊數(shù)n或α

？另外，用矢量運算可以簡化計算，推出求頂點的逆推公式d=R–Rcos(α

/2)<=DELTAcos(α

/2)>=(R–DELTA)/R

α

<=2arccos(R–DELTA)/Rα

max=2arccos(R–DELTA)/Rn=360/α

掃描轉(zhuǎn)換圓弧A

-直接生成B-多邊形逼近法

C-正負(fù)法D-Bresenham算法C-正負(fù)法(1/5)基本原理假定初始點P0∈G0，沿某方向(假定為X軸）前進(jìn)△X時，到達(dá)G+或G-(假定為G-)中的P1,再沿另外一方向(Y軸)前進(jìn)△Y,到達(dá)P2。若P2∈G+，則改變前進(jìn)方向，否則繼續(xù)向G+前進(jìn)?！桩嬊€F(x,y)具有正負(fù)劃分性F(x,y)二階連續(xù)曲線上各點曲率半徑足夠大C-正負(fù)法(2/5)初始定向確定的符號C-正負(fù)法(3/5)前進(jìn)規(guī)則取判別式C-正負(fù)法(4/5)正負(fù)法生成圓弧考慮第一像限圓弧段（圓弧是易畫曲線）

取初始點P0(x0,y0)=(0,R)

初始定向為：D=4,△X=1,△y=-1則P1為（x0+1,y0)=(1,R);又因為D(Pi)=F(Pi)F(P1)=F(Pi)F(1,R)C-正負(fù)法(5/5)所以由前進(jìn)規(guī)則得前進(jìn)點遞推公式1）當(dāng)D(Pi)>=0時，Xi+1=Xi,Yi+1=yi-1;當(dāng)D(Pi)<0時，Xi+1=Xi+1,Yi+1=yi；

判別式的初值D(P1)=F(P1)=F(1,R)=1

掃描轉(zhuǎn)換圓弧A

-直接生成B-多邊形逼近法

C-正負(fù)法D-Bresenham算法D-Bresenham法208-點對稱性21生成一個，得到

下列8點:只需生成1/8個圓函數(shù)是單值的

可以采用Bresenham方法只需考慮E

或

SE22圓的隱式方程令對于一個圓有并且

23選擇

E或SE函數(shù)為所以并且

中點

MESE當(dāng)前點中點

M’中點

M”掃描轉(zhuǎn)換圓弧-Bresenham

方法25理想線26理想線27決策變量

令28理想線情況1:E293031由于32其中33理想線

情況2:SE3435因為3637此處3839用

計算不是常量

40總結(jié)在整個圓上，不再是常量與直線算法結(jié)構(gòu)相同與直線算法的主要差別

需要在每一步計算新

需要實數(shù)計算中點

MESE當(dāng)前點中點

M’中點

M”掃描轉(zhuǎn)換圓弧-Bresenham

方法42初始條件令

r

為一個整數(shù).從開始計算下一個中點M

位于處所以

Bresenham直線掃描轉(zhuǎn)換算法的優(yōu)點如下：⒈

不必計算直線的斜率，因此不做除法。⒉

不用浮點數(shù)，只用整數(shù)。⒊

只做整數(shù)加減運算和乘2運算，而乘2運算可以用

移位操作實現(xiàn)。

Bresenham算法的運算速度很快，

并適于用硬件實現(xiàn)。

圓的Bresenham算法的程序circle(xc,yc,radius,c)intxc,yc,radius,c;{intx,y,p;x=0;y=radius;p=5-4*radius;while(x<y){

plot_circle_points(xc,yc,x,y,c);

if(p<0)p=p+2*x+3;

else{

p=p+2*(x-y)+5;

y-=1;

}

x+=1;

}if(x==y)

plot_circle_points(xc,yc,x,y,c);}

plot_circle_points(xc,yc,x,y,c)intxc,yc,x,y,c;{putpixel(xc+x,yc+y,c);putpixel(xc+x,yc+y,c);putpixel(xc+x,yc-y,c);putpixel(xc-x,yc-y,c);putpixel(xc+y,yc+x,c);putpixel(xc-y,yc+x,c);putpixel(xc+y,yc-x,c);putpixel(xc-y,yc-x,c);}

Bresenham的圓生成算法

掃描轉(zhuǎn)換橢圓弧A

–角度微分法B-中點畫法

橢圓生成方法可通過橢圓長軸和短軸尺寸不同而修改畫圓程序?qū)崿F(xiàn)。橢圓為到兩定點(焦點)距離之和等于常數(shù)點的集合。假如短軸和長軸與坐標(biāo)軸方向平行，可簡化橢圓方程。“標(biāo)準(zhǔn)位置”橢圓是指其長軸和短軸平行于x和y軸，參數(shù)rx和ry標(biāo)出長、短半軸。橢圓方程可借助于橢圓中心坐標(biāo)和參數(shù)rx和ry寫為：Pf1+pf2=Const標(biāo)準(zhǔn)位置橢圓的參數(shù)方程：

x=xc+rxcosθ，

y=yc+rysinθ?？紤]對稱性可用來進(jìn)一步減少計算量。標(biāo)準(zhǔn)位置橢圓在四分像限中是對稱的，必須計算一個整四分像限中橢圓曲線的像素位置，再由對稱性得到其它三個像限中的像素位置。橢圓生成方法Pf1+pf2=ConstA

掃描轉(zhuǎn)換橢圓弧A

–角度微分法B-中點畫法

中點橢圓生成基本思想給定長短軸參數(shù)rx、ry(假設(shè)ry≤rx)和橢圓中心位置(xc,yc)。先確定中心在原點的標(biāo)準(zhǔn)位置的橢圓點(x,y)，即：取(xc,yc)=(0,0)，然后，將點變換為圓心在(xc,yc)的點。定義橢圓隱函數(shù)形式為：

fellipse(x,y)=ry2x2+rx2y2-rx2ry2=0中點橢圓生成基本思想

該函數(shù)具有下列特性：fellipse(x,y)＜0，假如(x,y)位于橢圓邊界內(nèi)；fellipse(x,y)＝0，假如(x,y)在橢圓邊界上；fellipse(x,y)＞0，假如(x,y)位于橢圓邊界外。將橢圓函數(shù)fellipse(x,y)作為中點算法的決策參數(shù)。在每個取樣位置，按照橢圓函數(shù)在沿橢圓軌跡兩個候選像素間中點求值的符號選擇下一個像素。中點橢圓生成區(qū)域劃分中點法依據(jù)橢圓斜率將第一像限的橢圓(ry≤rx)分成兩部分。根據(jù)斜率變化確定步長方向：斜率絕對值小于1的區(qū)域1內(nèi)x方向取單位步長；斜率絕對值大于1的區(qū)域2內(nèi)y方向取單位步長。第一象限橢圓區(qū)域劃分區(qū)域1：橢圓切線斜率小于1；區(qū)域2：橢圓切線斜率大于1。中點橢圓生成區(qū)域劃分

第一象限橢圓區(qū)域劃分區(qū)域1：橢圓切線斜率小于1；區(qū)域2：橢圓切線斜率大于1。區(qū)域分割條件在每一步中，需檢測曲線的斜率值。橢圓的斜率：

dy/dx=-2ry2x/2rx2y在兩區(qū)域交界處：dy/dx=-1，即：2ry2x=2rx2y。因此，區(qū)域1和區(qū)域2的交替條件是：

2ry2x≥2rx2y在上半部分,法向量的y分量大在下半部分,法向量的x分量大上半部分下半部分法向量兩分量相等M1M2中點橢圓生成路徑選擇區(qū)域1和區(qū)域2可以多種方法來處理：從(0,ry)開始，先沿橢圓路徑順時針x方向步進(jìn)(△x=1，△y≤0)；斜率絕對值大于1時，變?yōu)閥方向步進(jìn)(△y=-1，△x≥0)

；從(rx,0)開始，先沿橢圓路徑逆時針y方向步進(jìn)(△y=1，△x≤0)；當(dāng)斜率絕對值小于1時，變?yōu)閤方向步進(jìn)(△x=-1，△y≥0)

；利用并行處理器可同時計算兩區(qū)域內(nèi)的像素位置。(rx

,0)(0,ry)候選高像素候選低像素候選像素中點前一像素橢圓弧第一象限區(qū)域1內(nèi)的橢圓弧橢圓的中點畫法與圓弧中點算法類似：確定一個象素后，接著在兩個候選象素的中點計算一個判別式的值，由判別式的符號確定更近的點先討論橢圓弧的上部分

當(dāng)前點:(Xp，Yp),

中點:(Xp+1,Yp-0.5)

d1=F(Xp+1,Yp-0.5)=b2(Xp+1)2+a2(Yp-0.5)2-a2b2對區(qū)域1，

根據(jù)d1的符號來決定下一像素是取正右方的那個，還是右下方的那個。

若d1＜0，中點在橢圓內(nèi)，取正右方象素，判別式更新為：

d1'=F(Xp+2,Yp-0.5)=d1+b2(2Xp+3)

d1的增量為b2(2Xp+3)當(dāng)d1≥0，中點在橢圓外，取右下方象素，判別式更新為：

d1'=F(Xp+2,Yp-1.5)=d1+b2(2Xp+3)+a2(-2Yp+2)

d1的增量為b2(2Xp+3)+a2(-2Yp+2)區(qū)域2中點橢圓生成算法

區(qū)域2(|切線斜率|＞1)

其初始點取區(qū)域1中選擇的最后位置。在負(fù)y方向以單位步長取樣，在每一步中取水平像素間的中點對決策參數(shù)求值為：

d2k=fellipse(xk+1/2,yk-1)=ry2(xk+1/2)2+rx2(yk-1)2-rx2ry2區(qū)域2(rx,0)區(qū)域2中點橢圓生成算法

區(qū)域2中(|切線斜率|＞1)

假如d2k＞0，中點位于橢圓邊界之外，

選擇xk處像素；假如d2k≤0，中點位于橢圓邊界之內(nèi)或上，

選擇xk+1處像素。區(qū)域2(rx,0)此時判別式要初始化。

d2=F(Xp+0.5,Yp-1)=b2(Xp+0.5)2+a2(Yp-1)2-a2b2

若d2<0,則

d2’=F(Xp+1.5,Yp-2)=d2+b2(2Xp+2)+a2(-2Yp+3)

若d2>=0,則

d2’=F(Xp+0.5,Yp-2)=d2+a2(-2Yp+3)

下半部分弧的終止條件為y=0d1的初始條件：

橢圓弧起點為(0，b)，第一個中點為(1,b-0.5)

初始判別式：

d0=F(1,b-0.5)=b*b+a*a(-b+0.25)程序：MidpointEllipe(a,b,color) inta,b,color; {intx,y;floatd1,d2; x=0;y=b; d1=b*b+a*a*(-b+0.25); putpixel(x,y,color); while(b*b*(x+1)<a*a*(y-0.5)) {{if(d1<0) d1+=b*b*(2*x+3);x++;} else{d1+=(b*b*(2*x+3)+a*a*(-2*y+2)) x++;y--; } putpixel(x,y,color); }//上部分

while(y>0) {if(d2<0){d2+=b*b*(2*x+2)+a*a*(-2*y+3); x++;y--；} else{d2+=a*a*(-2*y+3);y--;} putpixel(x,y,color);}}其它曲線生成算法常見曲線包括圓錐曲線、三角和指數(shù)函數(shù)、概率分布、通用多項式和樣條函數(shù)。這些曲線的顯示可采用類似于圓和橢圓函數(shù)來生成直接從顯式表示y=f(x)或參數(shù)方程中得到；用中點法繪制隱式函數(shù)f(x,y)=0曲線。直接逼近：直接方法是用直線段來逼近曲線－

“以直代曲”。沿曲線軌跡等距的線端點位置可使用參數(shù)表示；按曲線的斜率選擇獨立變量從顯式表示中生成等距位置。其它曲線生成算法直線擬合：可將曲線離散成坐標(biāo)點數(shù)據(jù)集，用直線段來將離散點連結(jié)在一起，或采用線性或非線性回歸來擬合數(shù)據(jù)組。利用對稱：利用函數(shù)對稱性來減少曲線軌跡坐標(biāo)位置的計算量。中點法：根據(jù)隱式函數(shù)f(x,y)=0

確定合適的決策參數(shù)。線寬和線型

生成具有一定寬度的直線，可以沿著生成直線是獲得的像素點，通過移動一把具有一定寬度的“刷子”來實現(xiàn)。

假設(shè)直線斜率在[-1，1]之間，可把刷子定成垂直方向，并將刷子中心點對準(zhǔn)直線上某一像素點，然后將刷子沿直線運動就刷出了一條具有一定寬度的直線。當(dāng)直線斜率不在[-1，1]之間時，只需把刷子運動方向改為水平方向即可。

用刷子來產(chǎn)生直線的算法簡單、效率高，但它刷出來的線的末端總是水平或垂直的，因此當(dāng)線寬較大時，直線的兩端就不好看了，而且在兩條直線的連接處會產(chǎn)生缺口。

對于繪制具有特殊線形的直線，如虛線、點劃線等，也需要編制相應(yīng)的算法來實現(xiàn)。3.3線畫圖元的屬性控制線型線型屬性包括實線、虛線和點線等。通過設(shè)置沿線路徑顯示的實線段的長度和間距來修改畫線算法以生成各種類型的線。虛線：在實線段之間插入與實線段等長的空白段；劃線：長度和空白段長度常作為用戶的選項來指定。點線：很短的劃線和等于或大于劃線大小的空白段。

線型段長度和中間空白段的像素數(shù)目可用像素掩模指定。像素掩模是包含數(shù)字0和1的串，指定沿線路徑哪些位置要畫。用固定數(shù)目像素來畫劃線會因斜率變化而產(chǎn)生在不同線方向生成不等長的劃線的現(xiàn)象。保持劃線等長的方法：按照線斜率來調(diào)整實心段和中間空白段的像素數(shù)目。將劃線看作單獨的線段，將每條劃線的端點坐標(biāo)定位后，調(diào)用沿劃線路徑計算像素位置的畫線程序。線寬標(biāo)準(zhǔn)線寬

用在每個放樣位置處用一個像素來生成。其它線寬

作為標(biāo)準(zhǔn)