基本圖形生成算法直線圓弧

1、基本圖形生成算法直線圓弧第1頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二 通常認(rèn)為，基本二維圖形包括點(diǎn)、直線、圓、橢圓、多邊形域和字符串等。復(fù)雜曲線及各種復(fù)雜圖形均可由直線段和圓弧來擬合，因此研究直線和圓弧的生成算法是二維圖形生成技術(shù)的基礎(chǔ)。第2頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二在光柵顯示器生成一個(gè)對(duì)象，實(shí)質(zhì)上是往幀緩沖區(qū)的相應(yīng)單元中寫入數(shù)據(jù)；如畫一條直線，實(shí)質(zhì)上是發(fā)現(xiàn)最佳逼近直線的像素序列、并填入相應(yīng)顏色的過程，這個(gè)過程稱為直線的光柵化，或者稱為直線的掃描轉(zhuǎn)換。第3頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二“發(fā)現(xiàn)最佳逼近直線的像素序列”就

2、是發(fā)現(xiàn)直線生成的算法。不同的算法有不同的效率，但各種算法的核心都是圍繞著判別和生成x、y增量的過程和方法（走筆規(guī)則）展開研究的。第4頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二通常從以下四方面評(píng)價(jià)直線掃描轉(zhuǎn)換算法的質(zhì)量：一、顯示像素點(diǎn)應(yīng)盡量靠近理想直線，直線要直，走樣??；二、直線端點(diǎn)準(zhǔn)確，且繪制無定向性，即以哪一個(gè)端點(diǎn)為繪制起點(diǎn)得到的線段應(yīng)重合；三、直線的亮度和色澤要均勻，避免造成視覺上一段亮一段暗的感覺。這通過所繪制的像素點(diǎn)密度保持均勻來實(shí)現(xiàn)；四、畫線速度盡可能快，即算法效率要高。第5頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換常用的直線生成算法有逐

3、點(diǎn)比較法、正負(fù)法、數(shù)值微分法和Bresenham算法等。簡(jiǎn)介逐點(diǎn)比較法詳細(xì)介紹數(shù)值微分法和Bresenham算法。第6頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二算法的判斷規(guī)則在繪圖過程中，畫筆每走一步，就要與理想圖形進(jìn)行比較，然后決定下一步的走向，用步步逼近的方法畫出指定起止點(diǎn)間的直線段。直線的掃描轉(zhuǎn)換逐點(diǎn)比較法第7頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二走筆約定以第一象限為例。當(dāng)畫筆（光標(biāo)當(dāng)前位置）位于理想直線上方，則橫向走筆，即畫筆沿x方向移動(dòng)一個(gè)單位；當(dāng)畫筆位于理想直線下方時(shí)，則縱向走筆，即畫筆沿y方向移動(dòng)一個(gè)單位。直線的掃描轉(zhuǎn)換逐點(diǎn)比較法第8頁，共58

4、頁，2022年，5月20日，12點(diǎn)25分，星期二要確定畫線時(shí)光標(biāo)移動(dòng)的方向，必須要知道當(dāng)前光標(biāo)點(diǎn)與理想直線的位置關(guān)系。位置關(guān)系通過坐標(biāo)的偏差來決定。以第一象限為例分析逐點(diǎn)比較法的偏差計(jì)算過程。直線的掃描轉(zhuǎn)換逐點(diǎn)比較法第9頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二設(shè)要繪制的直線為OA（即理想直線），當(dāng)前點(diǎn)為M，當(dāng)前點(diǎn)與理想直線的相對(duì)位置（即點(diǎn)M在OA的上方或下方）用偏差值 的正負(fù)來判斷。 的計(jì)算公式為：直線的掃描轉(zhuǎn)換逐點(diǎn)比較法tan函數(shù)在是單調(diào)遞增函數(shù)，因此 的正負(fù)體現(xiàn)b 和a 的大小。第10頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二偏差與走筆的關(guān)系分析：當(dāng) 0時(shí)

5、，角b a，點(diǎn)M在理想直線下方，按約定，畫筆應(yīng)向上（+y）走一步；當(dāng)P0時(shí)，角bPa ，點(diǎn)M在理想直線上方或在直線上，按約定，畫筆應(yīng)向右（+x）走一步。直線的掃描轉(zhuǎn)換逐點(diǎn)比較法第11頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二從計(jì)算偏差值的公式可知，分子的正負(fù)決定 的正負(fù)，因此將公式簡(jiǎn)化如下：直線的掃描轉(zhuǎn)換逐點(diǎn)比較法第12頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二設(shè)當(dāng)前位置為Mi（xi，yi），則計(jì)算偏差的函數(shù)為從偏差函數(shù)可知，光標(biāo)每移動(dòng)一個(gè)點(diǎn)，就要與理想直線的終點(diǎn)坐標(biāo)進(jìn)行計(jì)算、比較，然后確定下一步走筆的方向和步長(zhǎng)的增量，這樣繪制直線效率必然會(huì)很低，因此要對(duì)偏差函

6、數(shù)進(jìn)行簡(jiǎn)化。有效的方法是利用前一個(gè)點(diǎn)的偏差來推算下一個(gè)點(diǎn)的偏差值，這種方法稱為遞推法。直線的掃描轉(zhuǎn)換逐點(diǎn)比較法第13頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二例如已知前一個(gè)點(diǎn)的偏差值FiP0，說明點(diǎn)在理想直線的上方，畫筆應(yīng)該沿+x方向移動(dòng)一個(gè)步長(zhǎng)；反之，則應(yīng)該沿+y向移動(dòng)一個(gè)步長(zhǎng)。開始繪制直線時(shí)，光標(biāo)位于理想直線的起點(diǎn)，因此始終有F0=0。直線的掃描轉(zhuǎn)換逐點(diǎn)比較法第14頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二 若FiP0，表示第i點(diǎn)在直線上方， 則有xi+1 xi1（其中1為步長(zhǎng)） yi+1 yi， 第i+1點(diǎn)的偏差判別式為： 將遞推法用數(shù)學(xué)的方法表示為：設(shè)當(dāng)

7、前位置為Mi（xi，yi）， 下一個(gè)點(diǎn)位置為Mi+1（xi+1，yi+1）直線的掃描轉(zhuǎn)換逐點(diǎn)比較法求偏差的基本公式：第15頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二將遞推法用數(shù)學(xué)的方法表示為： 若Fi0，表示第i點(diǎn)在直線下方， 則有xi+1 xi yi+1 yi 1 （其中1為步長(zhǎng)），即第i+1點(diǎn)的偏差判別式為：直線的掃描轉(zhuǎn)換逐點(diǎn)比較法求偏差的基本公式：第16頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線段位置偏差值FkP0偏差值Fk0第一象限走筆 +XFk+1=Fk-|yA |走筆 +YFk+1=Fk+|xA |第三象限走筆 -X走筆 -Y第二象限走筆 +YF

8、k+1=Fk-|xA |走筆 -XFk+1=Fk+|yA |第四象限走筆 -Y走筆 +X各象限的判別式直線的掃描轉(zhuǎn)換逐點(diǎn)比較法逐點(diǎn)比較法繪制直線.doc第17頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二【注】遞推公式的作用： 意義：簡(jiǎn)化計(jì)算過程，提高效率。 原則：盡可能以加減法代替乘除法。 方法：用當(dāng)前點(diǎn)的偏差推算出走筆方向，并計(jì)算出下一步的偏差；再以畫筆的當(dāng)前位置重復(fù)上述過程，推算出畫筆下一步的動(dòng)作。第18頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二數(shù)值微分法（Digital Differential Analyzer）簡(jiǎn)稱DDA法，利用直線的微分方程生成直線的方

9、法。設(shè)直線的端點(diǎn)坐標(biāo)為（X0，Y0）和（X1，Y1），直線的參數(shù)方程為：直線的掃描轉(zhuǎn)換數(shù)值微分法第19頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換數(shù)值微分法DDA算法的原理：由于直線的一階導(dǎo)數(shù)是連續(xù)的，且x和y是成比例的，因此可以通過在當(dāng)前位置( xi , yi)分別加上兩個(gè)小增量 Hx 和 H y（其中為無窮小的正數(shù)）來求出下一個(gè)點(diǎn)( xi+1, yi+1)的坐標(biāo)。式中，i=0, 1, 2 , n-1，第20頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換數(shù)值微分法當(dāng)精度無限高的情況下，繪制出的直線無限接近理想直線。這種理想情況不可能出現(xiàn)（

10、因?yàn)樵O(shè)備的精度有限）也沒必要追求，因此通常增量系數(shù)的取值為：第21頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二繪制直線時(shí)，要確定一個(gè)方向的增量為單位增量，即確定畫線的基本步進(jìn)方向，另一個(gè)方向的增量由直線的斜率決定。確定基本步進(jìn)方向的依據(jù)是理想直線的斜率k。通常設(shè)：當(dāng)直線斜率小于或等于1，x方向?yàn)榛静竭M(jìn)方向，即x=1，y的值由直線的斜率決定。當(dāng)直線斜率大于1，y為基本步進(jìn)方向，即y=1，x的值由直線的斜率決定。直線的掃描轉(zhuǎn)換數(shù)值微分法第22頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二DDA算法的坐標(biāo)迭代公式：情況一：當(dāng) ， 即 時(shí)，有：直線的掃描轉(zhuǎn)換數(shù)值微分法第23

11、頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二情況二：當(dāng) ，即 時(shí)，有：直線的掃描轉(zhuǎn)換數(shù)值微分法第24頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換數(shù)值微分法需要注意的是：由于在光柵化過程中，繪制點(diǎn)的最小單位是1，因此對(duì)求出的xi+1和yi+1的值需要進(jìn)行四舍五入。DDA算法是一種增量算法，優(yōu)點(diǎn)是直觀、易于實(shí)現(xiàn)；缺點(diǎn)是要做浮點(diǎn)運(yùn)算和舍入取整，不利于硬件實(shí)現(xiàn)。第25頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換數(shù)值微分法斜率1時(shí)，以y為基本步進(jìn)方向，y方向每次步進(jìn)增量為1。第26頁，共58頁，2022年，5月20日，12點(diǎn)25分，星

12、期二直線的掃描轉(zhuǎn)換數(shù)值微分法void dda_line(float x0,float y0,float x1,float y1) int i,epsl; float xincre,yincre,x,y; epsl=max(abs(x1-x0),abs(y1-y0); xincre=(x1-x0)/epsl; yincre=(y1-y0)/epsl; x=x0; y=y0; for(i=1;i=epsl;i+) drawPoint(int(x+0.5),int(y+0.5); /四舍五入取整 x=x+xincre; y=y+yincre; 第27頁，共58頁，2022年，5月20日，12點(diǎn)25分

13、，星期二直線的掃描轉(zhuǎn)換Bresenham算法Bresenham提出的直線生成算法基本原理為：在某一計(jì)長(zhǎng)方向上，每次變化一個(gè)單位步長(zhǎng)或一個(gè)象素單位，另一個(gè)方向上是否走步取決于誤差項(xiàng)。計(jì)長(zhǎng)方向由直線的斜率k決定。當(dāng)0=k1時(shí)，y為計(jì)長(zhǎng)方向。關(guān)鍵問題是如何生成誤差項(xiàng)判斷條件。第28頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法中點(diǎn)Bresenham算法依據(jù)直線的斜率截距方程。設(shè)直線的斜率為k，截距為b；直線的斜率、截距方程為：F(x, y) =y- kx b=0當(dāng)直線經(jīng)過端點(diǎn)P0(X0, Y0) 和P1(X1, Y1)時(shí)第29頁，共58頁，2022

14、年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法符號(hào)說明：P當(dāng)前點(diǎn)；M中點(diǎn)；Pd和Pu下一步可能位置；Q理想直線在x=xi+1位置上的點(diǎn)；第30頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法算法說明：設(shè)直線斜率在01之間，且位于第一象限。光標(biāo)走步規(guī)則為：每次在x方向上加1，y方向根據(jù)誤差項(xiàng)判斷，或加1或加0。第31頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法誤差項(xiàng)判別式構(gòu)造：當(dāng)前點(diǎn)P，下一個(gè)點(diǎn)可能為Pd (即yi+1=yi點(diǎn)) ，可能為Pu (即yi+1=yi+

15、1點(diǎn))。M為Pd 與Pu的中點(diǎn)。若M在Q點(diǎn)下方，說明Pu點(diǎn)離直線近，則有yi+1=yi+1;若M在Q點(diǎn)上方，說明Pd點(diǎn)離直線近，則有yi+1=yi;第32頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法直線方程為：要判斷點(diǎn)M與直線的位置關(guān)系，只需要把M的坐標(biāo)代入直線方程，若：F(xM, yM)=0，即點(diǎn)M在直線上；F(xM, yM)0，即點(diǎn)M在直線上方；F(xM, yM)0，即點(diǎn)M在直線下方；第33頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法點(diǎn)M與點(diǎn)Q誤差項(xiàng)d判別式推導(dǎo)：當(dāng)di=0時(shí)，M在直

16、線上方或在直線上，Pd (即yi+1=yi點(diǎn))為下一個(gè)點(diǎn)。根據(jù)遞推思想，推導(dǎo)出di與di+1的關(guān)系。第34頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法當(dāng)di=0時(shí)，xi+1=xi+1; yi+1=yi; 則有d的初值：繪制直線時(shí)，光點(diǎn)最初在直線的起點(diǎn)P0(x0, y0)處，可推導(dǎo)出：d0=0.5-k第36頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法直線的斜率k=dy/dx，將斜率帶入判別式：當(dāng)di=0時(shí)，則有d的初值：di的正負(fù)決定下一個(gè)點(diǎn)的位置，與di 的具體數(shù)值無關(guān)，因此，統(tǒng)一以2d

17、xHdi替代di，以簡(jiǎn)化判別式。第37頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法當(dāng)di=0時(shí)，則有d的初值：因此在代碼中最終用到的判別式為：第38頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法繪制點(diǎn)(x, y)yesno第39頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法上述推導(dǎo)的中點(diǎn)Bresenham算法繪制直線的判別式適用于直線斜率在01之間的情況。觀察例mid_bresenham.cpp繪制斜率在01之間的直線和斜率大于1的直線。

18、當(dāng)直線大于1時(shí)，可不必重新推導(dǎo)判別式，只需交換x和y的規(guī)則。bresenham.cpp第40頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二直線的掃描轉(zhuǎn)換Bresenham算法中點(diǎn)Bresenham算法的誤差項(xiàng)判別式需要用到直線斜率，改進(jìn)后的Bresenham算法，思路保持不變，對(duì)誤差項(xiàng)判別式進(jìn)行簡(jiǎn)化。Bresenham算法直接比較距離t和s的大小，來確定下一個(gè)繪制的像素。第41頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二推導(dǎo)、簡(jiǎn)化后得到的誤差項(xiàng)判別式為：當(dāng)di=0時(shí)，xi+1=xi+1; yi+1=yi+1; 有直線的掃描轉(zhuǎn)換Bresenham算法當(dāng)di1時(shí)，該變量取

19、值1；當(dāng)斜率=1時(shí)，該變量取值0。直線的掃描轉(zhuǎn)換Bresenham算法第44頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換給出圓心(xc , yc)和半徑r，逐點(diǎn)繪制圓的方式有：一、利用直角坐標(biāo)方程利用直角坐標(biāo)方程繪制圓弧思路清楚，但計(jì)算涉及開方運(yùn)算，計(jì)算量大。更大的缺點(diǎn)是，由于y不是x的線性函數(shù)，因此，當(dāng)x取值從0到r均勻遞增時(shí)，y的值變化極不均勻，尤其當(dāng)x接近r時(shí)，繪制出來的圓會(huì)出現(xiàn)較大的間斷。第45頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換二、利用圓的參數(shù)方程利用參數(shù)方程繪制圓弧可以克服直角坐標(biāo)方程畫圓的弊端。參數(shù)為圓周角，當(dāng)圓周角按固

20、定增量變化時(shí)，能獲得均勻分布在圓周上的點(diǎn)。第46頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換但是，利用圓的參數(shù)方程繪制圓弧有兩個(gè)嚴(yán)重缺陷：一、每次求點(diǎn)坐標(biāo)都需要計(jì)算三角函數(shù)，計(jì)算量大，效率低。二、t 增量的大小與半徑相關(guān)。如，若t 取某一定值，當(dāng)半徑很小時(shí)，計(jì)算出來的像素可能會(huì)重疊（相鄰像素的x和y的增量都不于1）；而當(dāng)半徑較大時(shí)，有可能會(huì)造成圓弧出現(xiàn)斷開現(xiàn)象（相鄰像素的x和y的增量過大） 。觀察例程“參數(shù)方程畫圓”第47頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換八分法畫圓圓心位于原點(diǎn)的圓有四條對(duì)稱軸線：若已知圓周上任意一點(diǎn)，可以利用圓的對(duì)

21、稱性得到另外七個(gè)點(diǎn)的坐標(biāo)，從而得到整個(gè)圓的轉(zhuǎn)換掃描像素集。第48頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換八分法畫圓drawPoint(xc+x,yc+y); /畫點(diǎn)AdrawPoint(xc-x,yc+y); /畫點(diǎn)A7drawPoint(xc+x,yc-y); /畫點(diǎn)A3drawPoint(xc-x,yc-y); /畫點(diǎn)A4drawPoint(xc+y,yc+x); /畫點(diǎn)A1drawPoint(xc-y,yc+x); /畫點(diǎn)A2drawPoint(xc+y,yc-x); /畫點(diǎn)A6drawPoint(xc-y,yc-x); /畫點(diǎn)A5第49頁，共58頁，202

22、2年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法中點(diǎn)Bresenham法求圓弧上的點(diǎn)思路與直線繪制相同?？紤]圓心在原點(diǎn)，位于圖示區(qū)域的八分之一圓弧。中點(diǎn)Bresenham畫圓算法按照從點(diǎn)(0, 0)到點(diǎn)順時(shí)針確定最佳逼近理想圓弧的像素序列。第50頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法算法基本原理：x為基本步進(jìn)方向。每一次沿x方向走一步，y方向坐標(biāo)或減1，或減0。當(dāng)前點(diǎn)為P，下一步的中點(diǎn)為M。如果點(diǎn)M在圓內(nèi)，則Pu為下一個(gè)點(diǎn)，即y方向坐標(biāo)減0；如果點(diǎn)M在圓外，則Pd為下一個(gè)點(diǎn)，即y方向坐標(biāo)減1。第51頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法設(shè)當(dāng)前點(diǎn)為P(xi, yi)，則有點(diǎn)M(xi+1, yi-0.5)。構(gòu)造誤差項(xiàng)判別式：若di0，下一個(gè)點(diǎn)為Pu(xi+1, yi)；否則下一個(gè)點(diǎn)為Pd(xi+1, yi-1)；第52頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法誤差項(xiàng)判別式的遞推公式：當(dāng)di=0時(shí)，此時(shí)有xi+1=xi+1，yi+1=yi-1第53頁，共58頁，2022年，5月20日，12點(diǎn)25分，星期二圓的掃描轉(zhuǎn)換中點(diǎn)Bresenham算法誤差項(xiàng)的初值：開始繪