計算機圖形學直線生成

1、12(x,y)坐標地址線性表地址線性表1D表示顯示屏幕顯示屏幕2D表示像素由其左下角坐標表示像素由其左下角坐標表示3一、數(shù)學直線在數(shù)學上，理想的直線是一條無限小的連續(xù)的點數(shù)學直線二、光柵平面顯示的直線在光柵顯示平面上，只能用二維光柵格網(wǎng)上盡可能靠近這條直線的象素點的集合來表示它。每個象素的坐標x和y只能是整數(shù)，也就是說相鄰象素的坐標值是階躍的而不是連續(xù)的。光柵直線三、直線的掃描轉(zhuǎn)換直線的掃描轉(zhuǎn)換，就是要找出顯示平面上最佳逼近理想直線的那些象素的坐標值，并將這些象素置成所要求的顏色。直線的掃描轉(zhuǎn)換4由于一幅圖中可能包含成千上萬條直線，所以要求繪制算法應該：1、最接近數(shù)學上的直線；2、畫線速度盡可

2、能的快；3、沿著線段分布的象素應均勻。不均勻的例子如右圖，對同樣長的線段進行圖中的掃描轉(zhuǎn)換，會因為斜率不同，產(chǎn)生的象素個數(shù)不相等，這樣將導致象素亮度分布不均勻。5缺點：每步都需要一個浮點乘法運算和一個取整運算，所以效率太低。bkxy斜率截距直線方程：k表示斜率，b是y軸截距。給定兩個端點P0(x0,y0)和P1(x1,y1)，線段的斜率k和截距b為：)/()(/0101xxyyxyk00 xkyb從起點到終點，x每次增加(或減少)1，用直線方程計算對應的y值，再用SetPixel(x,int(y),color)輸出該像素。6數(shù)值微分法即DDA法(DigitalDifferentialAnaly

3、zer)，是一種基于直線的微分方程來生成直線的方法。7一、直線DDA算法描述：設(shè)(x1，y1)和(x2，y2)分別為所求直線的起點和終點坐標，由直線的微分方程得直線的斜率k：=k=直線的斜率(21)1.可通過計算由x方向的增量x引起y的改變來生成直線：xi+1=xi+x(22)yi+1=yi+y=yi+xk(23)2.也可通過計算由y方向的增量y引起x的改變來生成直線：yi+1=yi+y(24)xi+1=xi+x=xi+y/k(25)式(22)至(25)是遞推的。8二、直線DDA算法思想：選定|x2x1|和|y2y1|中較大者作為步進方向(假設(shè)|x2x1|較大)，取該方向上的增量為一個象素單位

4、(x=1)，然后利用式(21)計算另一個方向的增量(y=xk=k)。通過遞推公式(22)至(25)，把每次計算出的(xi+1，yi+1)經(jīng)取整后送到顯示器輸出，則得到掃描轉(zhuǎn)換后的直線。算法實現(xiàn)中還應注意直線的生成方向，以決定x及y是取正值還是負值。究竟用方法1,還是方法2來生成直線？9二、直線DDA算法思想（續(xù)）之所以取x2x1和y2y1中較大者作為步進方向，是考慮沿著線段分布的象素應均勻，這在下圖中可看出。100 1 2 3 4 5321Line: P(0, 0)- P(5, 2)舉例:線段P0(0,0)和P1(5,2)的DDA方法掃描轉(zhuǎn)換。xint(y+0.4)y+0.4522.0+0.4

5、421.6+0.4311.2+0.4210.8+0.4100.4+0.4000+0.40111給定兩個端點P0(x0,y0)和P1(x1,y1)，線段的斜率k和截距b為：)/()(0101xxyyk00 xkyb畫線過程從x的左端點x0開始，向x右端點步進，步長=1(像素)，計算相應的y坐標：y=kx+b，取像素點(x,int(y)作為當前點的坐標。計算yi+1=kxi+1+b=k(xi+x)+b=kxi+b+kx=yi+kx當x=1時yi+1=yi+k即：當x每遞增1，y遞增k(即直線斜率)。（xi,int(yi+0.5)（xi,yi)（xi+1,yi+1)（xi+1,int(yi+1+0.

6、5)？復雜度：？復雜度：加法加法+取整取整121、已知直線的兩端點坐標：(x1，y1)，(x2，y2)2、已知畫線的顏色：color3、計算兩個方向的變化量：x =x2x1y =y2y14、求出兩個方向最大變化量的絕對值：steps=max(|x |，|y |)5、計算兩個方向的增量(考慮了生成方向)：dx=x /stepsdy=y/steps6、設(shè)置初始象素坐標：x=x1,y=y17、用循環(huán)實現(xiàn)直線的繪制：for(i=1；i=Math.abs(y1-y0)length=Math.abs(x1-x0);elselength=Math.abs(y1-y0);dx=(float)Math.abs(

7、x1-x0)/length;dy=(float)Math.abs(y1-y0)/length;floatx=x0;floaty=y0;inti=1;while(i=length)SetPixel(x,y,color);x=x+dx;y=int(y+dy);i+;五、DDA算法生成直線的部分JAVA語言程序14DDA算法簡單，實現(xiàn)容易；DDA算法與基本算法相比，減少了浮點乘法，提高了效率。但是由于在循環(huán)中涉及實型數(shù)的運算（x與dx、y與dy用浮點數(shù)表示），每一步要進行取整，因此生成直線的速度較慢，不利于硬件實現(xiàn)，因而效率仍有待提高。六、直線DDA算法特點：15算法描述算法的復雜度描述算法實例1：

8、（100，200）和（500，400）的源代碼算法實例2：（100，400）和（500，200）的源代碼16Bresenham算法1965年提出，在生成直線的算法中，Bresenham算法是最有效的算法。Bresenham算法是一種基于誤差判別式來生成直線的方法。17l一、基本思想比較從理想直線到位于直線上方的像素的距離d1和相鄰的位于直線下方的像素的距離d2，根據(jù)距離誤差項的符號確定與理想直線最近的象素。yyk+1yykxkxk+1xP2P1d2d1018圖3-3根據(jù)誤差量來確定理想的像素點假設(shè)當前直線上的像素坐標為(xi, yi)，那么下一步需要在列xi+1上確定掃描線y的值。如圖3-3所

9、示，對于直線斜率k在01之間的情況，從給定線段的左端點P0(x0, y0)開始，逐步處理每個后續(xù)列(x位置)，并在掃描線y值最接近線段的像素上繪出一點。y值要么不變，要么遞增值要么不變，要么遞增1，可通過比較，可通過比較d1和和d2來來決定。決定。一、基本思想（續(xù)）yi+1yyixiXi+1d2d119二、直線描述：Bresenham算法也是采用遞推步進的辦法，令每次最大變化方向的坐標步進一個象素，同時另一個方向的坐標依據(jù)誤差判別式的符號來決定是否也要步進一個象素。xi+1=xi+1(26)yi+1=yi+k(27)xi+1=xi+x(22)yi+1=yi+y=yi+xk(23)我們首先討論k

10、=y/x，當0k1且x1x2且y1y2時的Bresenham算法。從DDA直線算法可知這些條件成立時，公式(2-2)、(2-3)可寫成：20根據(jù)誤差項根據(jù)誤差項d決定決定y是否增是否增1iiiybxkyyd) 1(1（) 1(1) 1(2bxkyyydiii（1221(221byxkddii）) 12(222)(21bxyyxxyddxii設(shè)y=y1y0,x=x1x0，則k=y/x，代入上式，得；) 12(2bxyc是常量，與像素位置無關(guān))(21ddxdi令則di的計算僅包括整數(shù)運算，其符號與(d1-d2)的符號相同。當di0時，像素(xi1，yi1)與直線上理想位置更接近；當di=0時，兩個

11、像素與直線上理想位置一樣接近，可約定取(xi1，yi1)。yi+1yyixiXi+1d2d12122對于i+1步，誤差參數(shù)為：cyxxydiii11122cyxxyddxdiii22)(21)(2)(2111iiiiiiyyxxxydd此時參數(shù)C已經(jīng)消去，且xi+1=xi+1,得：)(2211iiiiyyxydd如果選擇右上方像素，即：，則：11iiyyxyddii221iiyy1yddii21xyd 20如果選擇右方像素，即：，則：23l決定當前像素點的縱坐標（橫坐標）是加1還是不變l決定下一個像素點的決策變量xyddii221yddii21240 1 2 3 4 5321Line: P(0

12、, 0)- P(5, 2)舉例:線段P0(0,0)和P1(5,2)的Bresenham方法掃描轉(zhuǎn)換。5d+2(y-x)54d+2y13d+2(y-x)32d+2y312y-x101xdy221100025條件：0k1且x1x21、輸入線段的兩個端點坐標和畫線顏色：x1，y1，x2，y2，color；2、設(shè)置象素坐標初值：x=x1，y=y1；3、設(shè)置初始誤差判別值：d=2y-x；4、分別計算：x=x2-x1、y=y2-y1；5、循環(huán)實現(xiàn)直線的生成：for(x=x1；x=0)y=y+1；d=d+2(y-x)；elsed=d+2y；26由于程序中不含實型數(shù)運算，因此速度快、效率高，是一種有效的畫線算法。四、直線Bresenham算法特點：？復雜度：？復雜度：乘法乘法+加法加法27Bresenham算法描述Bresenham算法的復雜度描述Bresenham算法實例1：（0，0）和（40