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

基本圖形生成算法直線圓弧第1頁，課件共58頁，創(chuàng)作于2023年2月

通常認(rèn)為，基本二維圖形包括點(diǎn)、直線、圓、橢圓、多邊形域和字符串等。復(fù)雜曲線及各種復(fù)雜圖形均可由直線段和圓弧來擬合，因此研究直線和圓弧的生成算法是二維圖形生成技術(shù)的基礎(chǔ)。第2頁，課件共58頁，創(chuàng)作于2023年2月在光柵顯示器生成一個(gè)對(duì)象，實(shí)質(zhì)上是往幀緩沖區(qū)的相應(yīng)單元中寫入數(shù)據(jù)；如畫一條直線，實(shí)質(zhì)上是發(fā)現(xiàn)最佳逼近直線的像素序列、并填入相應(yīng)顏色的過程，這個(gè)過程稱為直線的光柵化，或者稱為直線的掃描轉(zhuǎn)換。第3頁，課件共58頁，創(chuàng)作于2023年2月“發(fā)現(xiàn)最佳逼近直線的像素序列”就是發(fā)現(xiàn)直線生成的算法。不同的算法有不同的效率，但各種算法的核心都是圍繞著判別和生成x、y增量的過程和方法（走筆規(guī)則）展開研究的。第4頁，課件共58頁，創(chuàng)作于2023年2月通常從以下四方面評(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頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換常用的直線生成算法有逐點(diǎn)比較法、正負(fù)法、數(shù)值微分法和Bresenham算法等。簡(jiǎn)介逐點(diǎn)比較法詳細(xì)介紹數(shù)值微分法和Bresenham算法。第6頁，課件共58頁，創(chuàng)作于2023年2月算法的判斷規(guī)則——在繪圖過程中，畫筆每走一步，就要與理想圖形進(jìn)行比較，然后決定下一步的走向，用步步逼近的方法畫出指定起止點(diǎn)間的直線段。直線的掃描轉(zhuǎn)換——逐點(diǎn)比較法第7頁，課件共58頁，創(chuàng)作于2023年2月走筆約定——以第一象限為例。當(dāng)畫筆（光標(biāo)當(dāng)前位置）位于理想直線上方，則橫向走筆，即畫筆沿x方向移動(dòng)一個(gè)單位；當(dāng)畫筆位于理想直線下方時(shí)，則縱向走筆，即畫筆沿y方向移動(dòng)一個(gè)單位。直線的掃描轉(zhuǎn)換——逐點(diǎn)比較法第8頁，課件共58頁，創(chuàng)作于2023年2月要確定畫線時(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頁，創(chuàng)作于2023年2月設(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頁，創(chuàng)作于2023年2月偏差與走筆的關(guān)系分析：當(dāng)<0時(shí)，角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頁，創(chuàng)作于2023年2月從計(jì)算偏差值的公式可知，分子的正負(fù)決定

的正負(fù)，因此將公式簡(jiǎn)化如下：直線的掃描轉(zhuǎn)換——逐點(diǎn)比較法第12頁，課件共58頁，創(chuàng)作于2023年2月設(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ì)偏差函數(shù)進(jìn)行簡(jiǎn)化。有效的方法是利用前一個(gè)點(diǎn)的偏差來推算下一個(gè)點(diǎn)的偏差值，這種方法稱為遞推法。直線的掃描轉(zhuǎn)換——逐點(diǎn)比較法第13頁，課件共58頁，創(chuàng)作于2023年2月例如已知前一個(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頁，創(chuàng)作于2023年2月

若FiP0，表示第i點(diǎn)在直線上方，則有xi+1＝xi＋1（其中1為步長(zhǎng)）

yi+1＝y(tǒng)i，第i+1點(diǎn)的偏差判別式為：將遞推法用數(shù)學(xué)的方法表示為：設(shè)當(dāng)前位置為Mi（xi，yi），下一個(gè)點(diǎn)位置為Mi+1（xi+1，yi+1）直線的掃描轉(zhuǎn)換——逐點(diǎn)比較法求偏差的基本公式：第15頁，課件共58頁，創(chuàng)作于2023年2月將遞推法用數(shù)學(xué)的方法表示為：若Fi<0，表示第i點(diǎn)在直線下方，則有xi+1＝xi

yi+1＝y(tǒng)i＋1

（其中1為步長(zhǎng)），即第i+1點(diǎn)的偏差判別式為：直線的掃描轉(zhuǎn)換——逐點(diǎn)比較法求偏差的基本公式：第16頁，課件共58頁，創(chuàng)作于2023年2月直線段位置偏差值FkP0偏差值Fk<0第一象限走筆+XFk+1=Fk-|yA|走筆+YFk+1=Fk+|xA|第三象限走筆-X走筆-Y第二象限走筆+YFk+1=Fk-|xA|走筆-XFk+1=Fk+|yA|第四象限走筆-Y走筆+X各象限的判別式直線的掃描轉(zhuǎn)換——逐點(diǎn)比較法逐點(diǎn)比較法繪制直線.doc第17頁，課件共58頁，創(chuàng)作于2023年2月【注】遞推公式的作用：

意義：簡(jiǎn)化計(jì)算過程，提高效率。

原則：盡可能以加減法代替乘除法。

方法：用當(dāng)前點(diǎn)的偏差推算出走筆方向，并計(jì)算出下一步的偏差；再以畫筆的當(dāng)前位置重復(fù)上述過程，推算出畫筆下一步的動(dòng)作。第18頁，課件共58頁，創(chuàng)作于2023年2月數(shù)值微分法（DigitalDifferentialAnalyzer）簡(jiǎn)稱DDA法，利用直線的微分方程生成直線的方法。設(shè)直線的端點(diǎn)坐標(biāo)為（X0，Y0）和（X1，Y1），直線的參數(shù)方程為：直線的掃描轉(zhuǎn)換——數(shù)值微分法第19頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(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頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——數(shù)值微分法當(dāng)精度無限高的情況下，繪制出的直線無限接近理想直線。這種理想情況不可能出現(xiàn)（因?yàn)樵O(shè)備的精度有限）也沒必要追求，因此通常增量系數(shù)的取值為：第21頁，課件共58頁，創(chuàng)作于2023年2月繪制直線時(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頁，創(chuàng)作于2023年2月DDA算法的坐標(biāo)迭代公式：情況一：當(dāng)，即時(shí)，有：直線的掃描轉(zhuǎn)換——數(shù)值微分法第23頁，課件共58頁，創(chuàng)作于2023年2月情況二：當(dāng)，即時(shí)，有：直線的掃描轉(zhuǎn)換——數(shù)值微分法第24頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(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頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——數(shù)值微分法斜率<=1時(shí)，以x為基本步進(jìn)方向，x方向每次步進(jìn)增量為1。斜率>1時(shí)，以y為基本步進(jìn)方向，y方向每次步進(jìn)增量為1。第26頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——數(shù)值微分法voiddda_line(floatx0,floaty0,floatx1,floaty1){inti,epsl;floatxincre,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頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——Bresenham算法Bresenham提出的直線生成算法基本原理為：在某一計(jì)長(zhǎng)方向上，每次變化一個(gè)單位步長(zhǎng)或一個(gè)象素單位，另一個(gè)方向上是否走步取決于誤差項(xiàng)。計(jì)長(zhǎng)方向由直線的斜率k決定。當(dāng)0<=k<=1時(shí)，x為計(jì)長(zhǎng)方向；當(dāng)k>1時(shí)，y為計(jì)長(zhǎng)方向。關(guān)鍵問題是如何生成誤差項(xiàng)判斷條件。第28頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(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頁，創(chuàng)作于2023年2月直線的掃描轉(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頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——中點(diǎn)Bresenham算法算法說明：設(shè)直線斜率在0~1之間，且位于第一象限。光標(biāo)走步規(guī)則為：每次在x方向上加1，y方向根據(jù)誤差項(xiàng)判斷，或加1或加0。第31頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(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+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頁，創(chuàng)作于2023年2月直線的掃描轉(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頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——中點(diǎn)Bresenham算法點(diǎn)M與點(diǎn)Q誤差項(xiàng)d判別式推導(dǎo)：當(dāng)di<0時(shí)，M在直線下方，Pu(即yi+1=yi+1點(diǎn))為下一個(gè)點(diǎn)；當(dāng)di>=0時(shí)，M在直線上方或在直線上，Pd(即yi+1=yi點(diǎn))為下一個(gè)點(diǎn)。根據(jù)遞推思想，推導(dǎo)出di與di+1的關(guān)系。第34頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——中點(diǎn)Bresenham算法當(dāng)di<0時(shí)，xi+1=xi+1;yi+1=yi+1;則有：第35頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(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頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——中點(diǎn)Bresenham算法直線的斜率k=dy/dx，將斜率帶入判別式：當(dāng)di<0時(shí)，則有當(dāng)di>=0時(shí)，則有d的初值：di的正負(fù)決定下一個(gè)點(diǎn)的位置，與di的具體數(shù)值無關(guān)，因此，統(tǒng)一以2dxHdi替代di，以簡(jiǎn)化判別式。第37頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——中點(diǎn)Bresenham算法當(dāng)di<0時(shí)，則有當(dāng)di>=0時(shí)，則有d的初值：因此在代碼中最終用到的判別式為：第38頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——中點(diǎn)Bresenham算法繪制點(diǎn)(x,y)yesno第39頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——中點(diǎn)Bresenham算法上述推導(dǎo)的中點(diǎn)Bresenham算法繪制直線的判別式適用于直線斜率在0~1之間的情況。觀察例mid_bresenham.cpp繪制斜率在0~1之間的直線和斜率大于1的直線。當(dāng)直線大于1時(shí)，可不必重新推導(dǎo)判別式，只需交換x和y的規(guī)則。bresenham.cpp第40頁，課件共58頁，創(chuàng)作于2023年2月直線的掃描轉(zhuǎn)換——Bresenham算法中點(diǎn)Bresenham算法的誤差項(xiàng)判別式需要用到直線斜率，改進(jìn)后的Bresenham算法，思路保持不變，對(duì)誤差項(xiàng)判別式進(jìn)行簡(jiǎn)化。Bresenham算法直接比較距離t和s的大小，來確定下一個(gè)繪制的像素。第41頁，課件共58頁，創(chuàng)作于2023年2月推導(dǎo)、簡(jiǎn)化后得到的誤差項(xiàng)判別式為：當(dāng)di>=0時(shí)，xi+1=xi+1;yi+1=yi+1;有直線的掃描轉(zhuǎn)換——Bresenham算法當(dāng)di<0時(shí)，xi+1=xi+1;yi+1=yi;則有第42頁，課件共58頁，創(chuàng)作于2023年2月從推導(dǎo)得出的確定畫筆下一步位置的公式可以看出，Bresenham算法中只包括加法、減法和乘2的操作，所需要的計(jì)算量很小。Bresenham算法不僅用于繪制直線，也可用于顯示圓和其他曲線的整數(shù)增量計(jì)算，應(yīng)用很廣泛。直線的掃描轉(zhuǎn)換——Bresenham算法第43頁，課件共58頁，創(chuàng)作于2023年2月例程分析：bresenham.cpp幾個(gè)重要變量說明：dt——誤差項(xiàng)，對(duì)應(yīng)判別式d;tx、ty——x、y方向的增量，取值可為-1、0、1;interchange——記錄直線斜率情況。當(dāng)斜率>1時(shí)，該變量取值1；當(dāng)斜率<=1時(shí)，該變量取值0。直線的掃描轉(zhuǎn)換——Bresenham算法第44頁，課件共58頁，創(chuàng)作于2023年2月圓的掃描轉(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頁，創(chuàng)作于2023年2月圓的掃描轉(zhuǎn)換二、利用圓的參數(shù)方程利用參數(shù)方程繪制圓弧可以克服直角坐標(biāo)方程畫圓的弊端。參數(shù)為圓周角，當(dāng)圓周角按固定增量變化時(shí)，能獲得均勻分布在圓周上的點(diǎn)。第46頁，課件共58頁，創(chuàng)作于2023年2月圓的掃描轉(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頁，創(chuàng)作于2023年2月圓的掃描轉(zhuǎn)換——八分法畫圓圓心位于原點(diǎn)的圓有四條對(duì)稱軸線：若已知圓周上任意一點(diǎn)，可以利用圓的對(duì)稱性得到另外七個(gè)點(diǎn)的坐標(biāo)，從而得到整個(gè)圓的轉(zhuǎn)換掃描像素集。第48頁，課件共58頁，創(chuàng)作于2023年2月圓的掃描轉(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頁，創(chuàng)作于2023年2月圓的掃描轉(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頁，創(chuàng)作于2023年2月圓的掃描轉(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頁，創(chuàng)作于2023年2月圓的掃描轉(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)判別式：若di<0，下一個(gè)點(diǎn)為Pu(xi+1,yi)；否則下一個(gè)點(diǎn)為Pd(xi+1,yi-1)；第52頁，課件共58頁，創(chuàng)作于2023年2月圓的掃描轉(zhuǎn)換——中點(diǎn)Bresenham算法誤差項(xiàng)判別式的遞推公式：當(dāng)di<0時(shí)，此時(shí)有xi+1=xi+1，yi+1=yi當(dāng)di>=0時(shí)，此時(shí)有xi+1=xi+1，yi+1=yi-1第53頁，課件共58頁，創(chuàng)作于2023年2月