直線和直線圖形

直線和直線圖形第一頁(yè)，共五十一頁(yè)，編輯于2023年，星期日(1)水平線(2)垂直線(3)一般線因此，在設(shè)計(jì)算法時(shí)就必須考慮點(diǎn)的選取。應(yīng)該選擇最靠近直線的可尋點(diǎn)來(lái)逼近直線，選擇得好，繪出來(lái)的直線就直，否則就會(huì)產(chǎn)生彎曲。2.1直線以及直線的繪制第二頁(yè)，共五十一頁(yè)，編輯于2023年，星期日2.直線的終止點(diǎn)要準(zhǔn)

在繪制直線過程中，由于精度的影響，直線的終點(diǎn)與原終點(diǎn)有一個(gè)累積誤差。例如：

因此在提高設(shè)備的精度外，也要從算法上保證繪圖的誤差最小。圖2.2終點(diǎn)不準(zhǔn)造成圖形不封閉2.1直線以及直線的繪制第三頁(yè)，共五十一頁(yè)，編輯于2023年，星期日3.直線的粗細(xì)要均勻

對(duì)于由象素點(diǎn)組成的顯示器來(lái)說，如果輸出的直線選點(diǎn)不均勻，則造成直線粗細(xì)不均勻，從直線上反映直線亮度不均勻；對(duì)于其他設(shè)備來(lái)說，給人感覺直線有粗有細(xì)。圖2.3不均勻的直線4.速度要快

雖然圖形系統(tǒng)中硬件設(shè)備影響繪圖的速度，但算法的好壞也影響速度，能夠以較快的速度完稱圖形，這是每一個(gè)圖形系統(tǒng)希望的。所以在選擇和設(shè)計(jì)生成直線的算法時(shí)，速度指標(biāo)也要加以重視。此外，對(duì)于生成直線時(shí)的特殊要求，如直線具有不同亮度、不同線寬、不同線型等。2.1直線以及直線的繪制第四頁(yè)，共五十一頁(yè)，編輯于2023年，星期日2.2生成直線的幾種常用算法計(jì)算機(jī)中常用的輸出顯示器是光柵圖形顯示器，它可以看作是由象素構(gòu)成的矩陣。因此，當(dāng)顯示一條直線時(shí)，實(shí)際上是將最逼近于該直線的象素點(diǎn)選中。也就是說表示一條直線，就是要用靠近直線的一些網(wǎng)格點(diǎn)來(lái)代表這一直線。下面是幾種生成直線常用的算法：2.2.1逐點(diǎn)比較法逐點(diǎn)比較法算法的基本思想是：在繪制直線的過程中，每繪制一個(gè)點(diǎn)與原直線進(jìn)行比較，根據(jù)比較的結(jié)果決定下一步的走向，這樣一步一步逼近直線。第五頁(yè)，共五十一頁(yè)，編輯于2023年，星期日逐點(diǎn)比較法的執(zhí)行過程：開始偏差判別選中象素終點(diǎn)判別是結(jié)束偏差計(jì)算否該算法執(zhí)行中使得每一個(gè)繪制點(diǎn)盡可能靠近直線而不發(fā)生遠(yuǎn)離直線的趨向。圖2.4逐點(diǎn)比較法執(zhí)行過程由一個(gè)點(diǎn)到下一個(gè)點(diǎn)的走向方法有在X，Y方向上同時(shí)走一步，或只在X方向走一步，或向Y方向走一步。逐點(diǎn)比較法規(guī)定每一次只在X方向或Y方向走一步。2.2.1逐點(diǎn)比較法第六頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例如：假設(shè)要畫直線為O(0,0)到A(XA,YA),即OA線段靠近OA線段的待選點(diǎn)為K0，K’0,K1，K’1,

K2，

K3，

K4等，那么究竟怎樣選取呢？問題：OAK0K’0K1K2K’1K3K4K5mn2.2.1逐點(diǎn)比較法注：網(wǎng)格點(diǎn)表示象素第七頁(yè)，共五十一頁(yè)，編輯于2023年，星期日畫線的步驟：(1)從O開始，沿X方向先走一步到K0點(diǎn)K’0K1下一點(diǎn)的選擇更加遠(yuǎn)離OA直線是下一步選擇的畫直線點(diǎn)(2)再下一步可走K’1或K2點(diǎn)K’1K2下一點(diǎn)的選擇更加遠(yuǎn)離OA直線是下一步選擇的畫直線點(diǎn)按照這個(gè)規(guī)則選取畫直線的點(diǎn)，選取的點(diǎn)為：K0，K1，K2，K3，K4，K5為繪制直線OA要用到的點(diǎn)OAK0K’0K1K2K’1K3K4K5mn2.2.1逐點(diǎn)比較法第八頁(yè)，共五十一頁(yè)，編輯于2023年，星期日在繪制直線過程中，需要考慮以下幾個(gè)問題：(1)如何計(jì)算偏差和判別偏差；(2)如何判別繪制到終點(diǎn)以結(jié)束算法；用上例來(lái)說明關(guān)于偏差問題(第一象限,斜率小于90度)有以下結(jié)論：即：=–

(1)=0時(shí)，點(diǎn)在直線上，(2)>0時(shí)，點(diǎn)在直線上方，(3)<0時(shí)，點(diǎn)在直線下方，設(shè)需要繪制直線OA的斜率為,根據(jù)算法繪制的當(dāng)前直線的斜率為，變量表示-的值OAK0K’0K1K2K’1K3K4K52.2.1逐點(diǎn)比較法走X方向一步走X方向一步走Y方向一步第九頁(yè)，共五十一頁(yè)，編輯于2023年，星期日計(jì)算偏差的公式如下：設(shè)O(0,0)表示直線起始點(diǎn),(Xc,Yc)表示繪制直線的當(dāng)前點(diǎn),A(Xe,Ye)表示直線的終點(diǎn)，并且A點(diǎn)在第一象限內(nèi)而且直線斜率小于90度=(Yc/Xc)–(Ye/Xe)=(Yc*Xe-Xc*Ye)/(Xc*Xe)（公式1）在繪制直線過程中，我們可以根據(jù)的正負(fù)來(lái)決定下一步的方向，一步一步逼近直線。=

–根據(jù)計(jì)算出偏差，以此來(lái)進(jìn)行偏差判斷。2.2.1逐點(diǎn)比較法第十頁(yè)，共五十一頁(yè)，編輯于2023年，星期日偏差計(jì)算公式：這就是逐點(diǎn)比較生成直線過程中的偏差計(jì)算公式。（公式1）（公式2）=(Yc*Xe-Xc*Ye)/(Xc*Xe)=(Yc*Xe-Xc*Ye)對(duì)于，由于分母(Xc*Xe)中的Xc和Xe都是第一象限內(nèi)，所以t的正負(fù)只與(Yc*Xe-Xc*Ye)有關(guān)，于是上面的公式可以簡(jiǎn)化為：2.2.1逐點(diǎn)比較法第十一頁(yè)，共五十一頁(yè)，編輯于2023年，星期日

(1)在左圖中，K1(X1,Y1)點(diǎn)處,有：

F1=Xe*Y1–X1*Ye>0故K1下一點(diǎn)選擇在X方向走一步K2(2)K2的坐標(biāo)如下:OAK0K’0K1K2K’1K3K4K5在計(jì)算過程中,每次都要計(jì)算二個(gè)乘積之差,計(jì)算量太大,下面構(gòu)造一個(gè)遞推關(guān)系.=(Yc*Xe-Xc*Ye)X2=X1+1

Y2=Y1

F2=Xe*Y2

–X2*Ye=Xe*Y1-(X1+1)*Ye=

F1-Ye<0,K3在Y方向增加一步2.2.1逐點(diǎn)比較法第十二頁(yè)，共五十一頁(yè)，編輯于2023年，星期日

F2<0,K3的坐標(biāo)如下:X3=X2Y2=Y1+1F3=F2+Xe>0因此K3下一點(diǎn)選擇在X方向走一步K4F4<0,K5的坐標(biāo)以及偏差如下:X5=X4Y5=Y4+1F5=F4+Xe>0OAK0K’0K1K2K’1K3K4K5F3>0,K4的坐標(biāo)如下:X4=X3+1Y4=Y3F4=F3-Ye<0因此K5下一點(diǎn)選擇在Y方向走一步K32.2.1逐點(diǎn)比較法第十三頁(yè)，共五十一頁(yè)，編輯于2023年，星期日根據(jù)上面的計(jì)算過程,總結(jié)以上推導(dǎo):(1)Fi>=0,走X方向一步,即Xi+1=Xi+1

Yi+1=YiFi+1=Fi-Ye(2)Fi<0,走Y方向一步,即Xi+1=XiYi+1=Yi+1Fi+1=Fi+Xe由以上的推導(dǎo)過程可知,在計(jì)算偏差Fi的過程中利用了上一步的偏差和終點(diǎn)坐標(biāo)(Xe,Ye),而與中間點(diǎn)無(wú)關(guān),從而簡(jiǎn)化了計(jì)算過程.因此解決了繪制直線的第一個(gè)問題:偏差的計(jì)算和判斷2.2.1逐點(diǎn)比較法第十四頁(yè)，共五十一頁(yè)，編輯于2023年，星期日繪制直線的第二個(gè)問題:(2)如何判別繪制到終點(diǎn)以結(jié)束算法；對(duì)于終點(diǎn)判別可采用計(jì)數(shù)方法:

設(shè)在X,Y方向的增量分別為X和Y,對(duì)于步長(zhǎng)為一個(gè)參數(shù)來(lái)說,就是生成直線過程中X方向走X,Y方向走Y,因而計(jì)算器值為max(X,Y)在計(jì)長(zhǎng)方向每走一步計(jì)數(shù)器減1,直到計(jì)數(shù)器值為零,則結(jié)束直線算法.2.2.1逐點(diǎn)比較法第十五頁(yè)，共五十一頁(yè)，編輯于2023年，星期日(1)Fi>=0,走X方向一步,即Xi+1=Xi+1Yi+1=YiFi+1=Fi-Ye(2)Fi<0,走Y方向一步,即Xi+1=XiYi+1=Yi+1Fi+1=Fi+Xe例如:使用逐點(diǎn)比較法繪制從O(0,0)到A(4,2))直線段OA2.2.1逐點(diǎn)比較法第十六頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例如:使用逐點(diǎn)比較法繪制從O(0,0)到A(4,2))直線段計(jì)數(shù)器max(4,2)的值為4,計(jì)長(zhǎng)方向?yàn)閄,直線的斜率為0.5(1)設(shè)直線先在X方向走一步,計(jì)數(shù)器為3,K1有關(guān)數(shù)據(jù)為:Y1=Y0=0X1=X0+1=1F1=F0-Ye

=-2F1<0,點(diǎn)在直線下方,下一點(diǎn)走Y方向一步OAK12.2.1逐點(diǎn)比較法第十七頁(yè)，共五十一頁(yè)，編輯于2023年，星期日OAK1(2)K2在Y方向走一步,

有關(guān)數(shù)據(jù)為:Y2=Y1+1=1

X2=X1=1

F2=-2

+4=2

F2>0,點(diǎn)在直線上方,走X方向一步K22.2.1逐點(diǎn)比較法第十八頁(yè)，共五十一頁(yè)，編輯于2023年，星期日OAK1K2(3)K3在X方向走一步,計(jì)數(shù)器為2,

有關(guān)數(shù)據(jù)為:Y3=Y2=1X3=X2+1=2

F3=2

-2=0

F3=0,點(diǎn)在直線上,走X方向一步K32.2.1逐點(diǎn)比較法第十九頁(yè)，共五十一頁(yè)，編輯于2023年，星期日OAK1K2K3(4)K4在X方向走一步,計(jì)數(shù)器為1,K4有關(guān)數(shù)據(jù)為:Y4=Y3=1

X4=X3+1=3F4=0

-2=-2

F4<0,點(diǎn)在直線下方,走Y方向一步K42.2.1逐點(diǎn)比較法第二十頁(yè)，共五十一頁(yè)，編輯于2023年，星期日K3OAK1K2K4(5)下一點(diǎn)在Y方向走一步,K5有關(guān)數(shù)據(jù)為:Y5=Y4+1=2

X5=X4=3F5=-2

+4=2

F5>0,點(diǎn)在直線上方,走X方向一步K52.2.1逐點(diǎn)比較法第二十一頁(yè)，共五十一頁(yè)，編輯于2023年，星期日K3OAK1K2K4K5(6)在X方向走一步,計(jì)數(shù)器為0,K6有關(guān)數(shù)據(jù)為:Y6=Y5=2

X6=X5+1=4F5=2

-2=0

因?yàn)橛?jì)數(shù)器為0,所以結(jié)束直線繪制K62.2.1逐點(diǎn)比較法第二十二頁(yè)，共五十一頁(yè)，編輯于2023年，星期日繪制直線點(diǎn)的具體選擇過程:OAK2K3K4K1K5K62.2.1逐點(diǎn)比較法第二十三頁(yè)，共五十一頁(yè)，編輯于2023年，星期日?qǐng)D各象限筆畫走向(2)Fi<0,走Y方向一步,即(1)Fi>=0,走X方向一步Xi+1=Xi+1

Yi+1=YiFi+1=Fi–YeXi+1=XiYi+1=Yi+1Fi+1=Fi+Xe(1)Fi>=0,走Y方向一步Xi+1=Xi

Yi+1=Yi+1

Fi+1=Fi+Xe(2)Fi<0,走X方向一步,即Xi+1=Xi-1Yi+1=YiFi+1=Fi+Ye(1)Fi>=0,走X方向一步Xi+1=Xi-1

Yi+1=YiFi+1=Fi+Ye(2)Fi<0,走Y方向一步,即Xi+1=XiYi+1=Yi-1Fi+1=Fi-Xe(1)Fi>=0,走Y方向一步Xi+1=Xi

Yi+1=Yi-1

Fi+1=Fi-Xe(2)Fi<0,走X方向一步,即Xi+1=Xi+1Yi+1=YiFi+1=Fi-Ye第二十四頁(yè)，共五十一頁(yè)，編輯于2023年，星期日表2-1判別式計(jì)算線段位置走步方向偏差值Fk>=0走步方向偏差值Fk<=0第一象限+XFk+1=Fk-|YA|+YFk+1=Fk+|XA|第二象限-X-Y第三象限+YFk+1=Fk-|XA|-XFk+1=Fk+|YA|第四象限-Y+X例如：在屏幕坐標(biāo)系下,生成直線O(X1,Y1)A(X2,Y2)且OA與水平線的夾角的斜率小于90度.OA2.2.1逐點(diǎn)比較法第二十五頁(yè)，共五十一頁(yè)，編輯于2023年，星期日2.2.2數(shù)值微分法數(shù)值微分法算法的基本思想是：在生成直線的某點(diǎn)上增加一個(gè)同X和Y的一階導(dǎo)數(shù)成比例的小步長(zhǎng),在這種情況下的一階導(dǎo)數(shù)是連續(xù)的,而且對(duì)于X和Y成正比。數(shù)值微分法(DigitalDifferentialAnalyzer,又稱DDA法)推導(dǎo)如下:設(shè)直線的起點(diǎn)坐標(biāo)(Xs,Ys),終點(diǎn)坐標(biāo)位(Xe,Ye),令

X=Xe-Xs,Y=Ye-Ys要生成直線的微分方程是:第二十六頁(yè)，共五十一頁(yè)，編輯于2023年，星期日令:取時(shí)間步長(zhǎng),數(shù)值解的遞推公式為:公式3可以求得直線(Xs,Ys)(Xe,Ye)上的點(diǎn),但由于顯示時(shí)要用象素來(lái)表示,所以繪制直線的點(diǎn)是整數(shù)要用舍入法來(lái)找到最靠近直線的點(diǎn).2.2.2數(shù)值微分法對(duì)于終點(diǎn)判別可采用計(jì)數(shù)方法:

計(jì)數(shù)器值等于x,y方向增量最大值;每繪制一個(gè)象素點(diǎn),計(jì)數(shù)器減1.第二十七頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例如:繪制從(0,0)到(5,5)的直線運(yùn)用DDA方法計(jì)算如下:初始值計(jì)算:x=0,y=0,count=5,dx=1,dy=1繪制過程如下:0(1)count=4x=1y=1畫點(diǎn)(1,1)(2)count=3x=2y=2畫點(diǎn)(2,2)(3)count=2x=3y=3畫點(diǎn)(3,3)(4)count=1x=4y=4畫點(diǎn)(4,4)(5)count=0x=5y=5畫點(diǎn)(5,5)2.2.2數(shù)值微分法第二十八頁(yè)，共五十一頁(yè)，編輯于2023年，星期日練習(xí):繪制從(0,0)到(-8,-4)的直線運(yùn)用DDA方法計(jì)算如下:初始值計(jì)算:x=0,y=0,c=8,dx=-1,dy=-0.5繪制過程如下:(1)c=7x=-1y=-0.5畫點(diǎn)(-1,-1)(2)c=6x=-2y=-1畫點(diǎn)(-2,-1)(3)c=5x=-3y=-1.5畫點(diǎn)(-3,-2)(4)c=4x=-4y=-2畫點(diǎn)(-4,-2)(5)c=3x=-5y=-2.5畫點(diǎn)(-5,-3)(6)c=2x=-6y=-3畫點(diǎn)(-6,-3)(7)c=1x=-7y=-3.5畫點(diǎn)(-7,-4)(8)c=0

x=-8y=-4畫點(diǎn)(-8,-4)2.2.2數(shù)值微分法第二十九頁(yè)，共五十一頁(yè)，編輯于2023年，星期日2.2.3Bresenham算法Bresenham算法的基本思想是：

每次迭代在增量最大方向上均走一步,其方向由增量的正負(fù)決定,另一個(gè)方向是否也走,取決于計(jì)算出來(lái)的誤差項(xiàng),誤差項(xiàng)所記錄的方向同最大增量方向垂直.對(duì)于終點(diǎn)判別可采用計(jì)數(shù)方法:

計(jì)數(shù)器值等于x,y方向增量最大值;每繪制一個(gè)象素點(diǎn),計(jì)數(shù)器減1.第三十頁(yè)，共五十一頁(yè)，編輯于2023年，星期日下面討論誤差項(xiàng)(假設(shè)生成的直線角度在0-45度之間,斜率為m)誤差項(xiàng)當(dāng)點(diǎn)B在A點(diǎn)上方,當(dāng)點(diǎn)B在A點(diǎn)下方,即(xi,yi)xiXi+1yi,ryi+1,r(xi+1,yi+1)ABDCE第三十一頁(yè)，共五十一頁(yè)，編輯于2023年，星期日誤差項(xiàng)之間的遞推關(guān)系:例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法第三十二頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法1.

,第三十三頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法2.

,第三十四頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法3.

,第三十五頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法4.

,第三十六頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法5.

,第三十七頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法6.

,第三十八頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法7.

,第三十九頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法8.

,第四十頁(yè)，共五十一頁(yè)，編輯于2023年，星期日例題:已知起點(diǎn)(0,0),終點(diǎn)(8,4),用Bresenham算法繪制這一線段012345678123456782.2.3Bresenham算法8.

,第四十一頁(yè)，共五十一頁(yè)，編輯于2023年，星期日2.3線寬與線型如何生成一定寬度的直線:產(chǎn)生具有一定寬度的直線,可以沿著生成直線時(shí)獲得的象素點(diǎn),通過移動(dòng)把具有一定的寬度“刷子”實(shí)現(xiàn).第四十二頁(yè)，共五十一頁(yè)，編輯于2023年，星期日假設(shè)直線斜率在[-1,1]之間,可把刷子定成垂直方向,并把刷子中心點(diǎn)對(duì)準(zhǔn)直線上某一象素點(diǎn),然后將刷子沿直線運(yùn)動(dòng),就刷出了一條具有一條寬度的直線.例如:生成直線的寬度為5設(shè)生成的直線的斜率m的值范圍是[-1,1]2.3線寬與線型中心象素點(diǎn)上二個(gè)象素下二個(gè)象素第四十三頁(yè)，共五十一頁(yè)，編輯于2023年，星期日當(dāng)直線的斜率不在[-1,1]之間時(shí),只需把刷子運(yùn)動(dòng)方向改為水平方向即可.例如:生成直線的寬度為5設(shè)生成的直線的斜率m的值范圍不是[-1,1]2.3線寬與線型第四十四頁(yè)，共五十一頁(yè)，編輯于2023年，星期日用刷子生成直線的算法簡(jiǎn)單,效率高,但有以下幾個(gè)缺點(diǎn):(1)刷出的線的末端總是水平或垂直的,因此當(dāng)線寬較大時(shí),直線的兩端不好看,而且在兩條直線的連接處會(huì)產(chǎn)生缺口.(2)斜線與水平(垂直)線不一樣寬,對(duì)于水平(垂直線),刷子與直線垂直,此時(shí)線最寬,與指定寬度相等;而對(duì)于45度斜線,刷子與直線成45度角,粗細(xì)僅為指定的線寬0.7倍.缺口2.3線寬與線型第四十五頁(yè)，共五十一頁(yè)，編輯于2023年，星期日(3)由于刷子沿直線兩側(cè)運(yùn)動(dòng),所以適合于寬度為奇數(shù)的情況;若為偶數(shù),則繪出的直線寬度與指定寬度相差一個(gè)象素.例如:生成直線的寬度為62.3線寬與線型第四十六頁(yè)，共五十一頁(yè)，編輯于2023年，星期日繪制具有特殊線型的直線,如虛線,點(diǎn)劃線等,也需要編制相應(yīng)的算法來(lái)實(shí)現(xiàn).例如:已知起始點(diǎn)(sx,sy)與終止點(diǎn)(ex,ey),繪制一條虛線，設(shè)生成的直線在第一象限中設(shè)定義虛線上實(shí)線段部分寬度為l1,實(shí)線之間距離為l2,虛線上的