《直線、圓、橢圓的生成.ppt》由會員分享，可在線閱讀，更多相關(guān)《直線、圓、橢圓的生成.ppt（88頁珍藏版）》請在裝配圖網(wǎng)上搜索。
第三章直線、圓、橢圓生成算法,圖形的掃描轉(zhuǎn)換（光柵化）確定一個像素集合，用于顯示一個圖形的過程。步驟如下：1、確定有關(guān)像素2、用圖形的顏色或其它屬性，對像素進行寫操作。對一維圖形，不考慮線寬，則用一個像素寬的直線來顯示圖形。二維圖形的光柵化，即區(qū)域的填充：確定像素集，填色或圖案。任何圖形的光柵化，必須顯示在一個窗口內(nèi)，否則不予顯示。即確定一個圖形的哪些部分在窗口內(nèi)，哪些在窗口外，即裁剪。,,圖形顯示前需要：掃描轉(zhuǎn)換+裁剪●裁剪---〉掃描轉(zhuǎn)換：最常用，節(jié)約計算時間?！駫呙柁D(zhuǎn)換---〉裁剪：算法簡單；,本章內(nèi)容,3.1掃描轉(zhuǎn)換直線段3.1.1DDA算法3.1.2中點畫線法3.1.3Bresenham畫線算法3.2圓弧、橢圓弧掃描轉(zhuǎn)換3.2.1中點算法3.2.2內(nèi)接正多邊形迫近法3.2.3等面積正多邊形逼近法3.2.4生成圓弧的正負法,3.1直線段的掃描轉(zhuǎn)換算法,直線的掃描轉(zhuǎn)換:確定最佳逼近于該直線的一組象素，并且按掃描線順序，對這些象素進行寫操作。三個常用算法：數(shù)值微分法（DDA）中點畫線法Bresenham算法。,3.1.1數(shù)值微分法（ＤＤＡ）,假定直線的起點、終點分別為：（x0,y0),(x1,y1)，且都為整數(shù)。,,,,,,,,,,,(Xi+1,Yi+k),(Xi,Int(Yi+0.5)),(Xi,Yi),,柵格交點表示象素點位置,。,。,。,。,3.1.1數(shù)值微分(DDA)法,基本思想已知過端點P0(x0,y0),P1(x1,y1)的直線段Ly=kx+b直線斜率為這種方法直觀，但效率太低，因為每一步需要一次浮點乘法和一次舍入運算。,計算yi+1=kxi+1+b=kxi+b+k?x=yi+k?x當(dāng)?x=1;yi+1=yi+k即：當(dāng)x每遞增1，y遞增k(即直線斜率)；注意上述分析的算法僅適用于?k?≤1的情形。在這種情況下，x每增加1,y最多增加1。當(dāng)?k??1時，必須把x，y地位互換,增量算法：在一個迭代算法中，如果每一步的x、y值是用前一步的值加上一個增量來獲得，則稱為增量算法。DDA算法就是一個增量算法。,數(shù)值微分(DDA)法,voidDDALine(intx0,inty0,intx1,inty1,intcolor)?intx；floatdx,dy,y,k;dx,=x1-x0,dy=y1-y0;k=dy/dx,y=y0;for(x=x0;x?x1,x++)?drawpixel(x,int(y+0.5),color);y=y+k;??,數(shù)值微分(DDA)法,例：畫直線段P0(0,0)--P1(5,2)xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.5,,,,,,,,,,,,012345,3,2,1,Line:P0(0,0)--P1(5,2),,,,,,,實現(xiàn)DDA畫線程序,步驟：第一步：建立一個DDALine的工程文件；第二步：添加ddaline()成員函數(shù)方法：在工作區(qū)中選擇CLASSVIEW類窗口，右擊CDDAlineView類，選擇“addmemberfunction…”，定義如下的成員函數(shù)：voidddaline(CDC*pDC,intx0,inty0,intx1,inty1,COLORREFcolor);,第三步：編寫自定義的成員函數(shù)ddaline()程序,voidCDDALineView::ddaline(CDC*pDC,intx0,inty0,intx1,inty1,COLORREFcolor){intlength,i;floatx,y,dx,dy;length=abs(x1-x0);if(abs(y1-y0)>length)length=abs(y1-y0);dx=(float)(x1-x0)/length;dy=(float)(y1-y0)/length;x=x0+0.5;y=y0+0.5;for(i=1;iSetPixel((int)x,(int)y,color);x=x+dx;y=y+dy;}},第四步：編寫OnDraw()函數(shù),voidCDDALineView::OnDraw(CDC*pDC){CDDALineDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);//TODO:adddrawcodefornativedatahereddaline(pDC,100,100,400,100,RGB(255,0,0));ddaline(pDC,400,100,400,400,RGB(0,255,0));ddaline(pDC,400,400,100,400,RGB(0,0,255));ddaline(pDC,100,400,100,100,RGB(255,255,0));ddaline(pDC,100,100,400,400,RGB(255,0,255));ddaline(pDC,100,400,400,100,RGB(0,255,255));},數(shù)值微分(DDA)法,缺點：在此算法中，y、k必須是float，且每一步都必須對y進行舍入取整，不利于硬件實現(xiàn)。,中點畫線法,原理：,假定直線斜率0
取P2。M在Q的上方->P1離直線更近更近->取P1M與Q重合，P1、P2任取一點。問題：如何判斷M與Q點的關(guān)系？,,,,,,,,,,,,,P=(,x,p,,,y,p,),,,,,,,,Q,P2,P1,3.1.2中點畫線法,假設(shè)直線方程為：ax+by+c=0其中a=y0-y1,b=x1-x0,c=x0y1-x1y0由常識知：∴欲判斷中點M點是在Q點上方還是在Q點下方，只需把M代入F(x,y),并檢查它的符號。,,,,,,,,,,,,,P=(,x,p,,,y,p,),,,,,,,,Q,P2,P1,,構(gòu)造判別式：d=F(M)=F(xp+1,yp+0.5)=a(xp+1)+b(yp+0.5)+c當(dāng)d0，M在直線(Q點)上方，取右方P1；當(dāng)d=0，選P1或P2均可，約定取P1；能否采用增量算法呢？,,,,,,,,,,,,,P=(,x,p,,,y,p,),,,,,,,,Q,P2,P1,,若d?0->M在直線上方->取P1;此時再下一個象素的判別式為d1=F(xp+2,yp+0.5)=a(xp+2)+b(yp+0.5)+c=a(xp+1)+b(yp+0.5)+c+a=d+a；增量為a,,,,,,,,,,,,,P=(,x,p,,,y,p,),,,,,,,,Q,P2,P1,若dM在直線下方->取P2;此時再下一個象素的判別式為d2=F(xp+2,yp+1.5)=a(xp+2)+b(yp+1.5)+c=a(xp+1)+b(yp+0.5)+c+a+b=d+a+b；增量為a＋b,,,,,,,,,,,,,P=(,x,p,,,y,p,),,,,,,,,Q,P2,P1,畫線從(x0,y0)開始，d的初值d0=F(x0+1,y0+0.5)=a(x0+1)+b(y0+0.5)+c=F(x0,y0)+a+0.5b=a+0.5b由于只用d的符號作判斷，為了只包含整數(shù)運算,可以用2d代替d來擺脫小數(shù)，提高效率。,voidMidpointLine(intx0,inty0,intx1,inty1,intcolor){inta,b,d1,d2,d,x,y;a=y0-y1,b=x1-x0,d=2*a+b;d1=2*a,d2=2*(a+b);x=x0,y=y0;drawpixel(x,y,color);while(xy1){if(dSetPixel(x,y,color);}}}},Bresenham畫線算法,在直線生成的算法中Bresenham算法是最有效的算法之一。令k=Δy/Δx，就0≤k≤1的情況來說明Bresenham算法。由DDA算法可知：yi+1=yi+k(1)由于k不一定是整數(shù)，由此式求出的yi也不一定是整數(shù)，因此要用坐標為（xi,yir）的象素來表示直線上的點，其中yir表示最靠近yi的整數(shù)。,Bresenham畫線算法,設(shè)圖中xi列上已用（xi,yir）作為表示直線的點，又設(shè)B點是直線上的點，其坐標為（xi+1,yi+1），顯然下一個表示直線的點（xi+1,yi+1,r）只能從圖中的C或者D點中去選。設(shè)A為CD邊的中點。若B在A點上面則應(yīng)取D點作為（xi+1,yi+1,r），否則應(yīng)取C點。,,,,,,,,,xi,Xi+1,Yi,r,Yi+1,r,C,D,B,,A,,,ε(x)的幾何意義,為能確定B在A點上面或下面，令ε(xi+1)=yi+1-yir-0.5(2)若B在A的下面，則有ε(xi+1)0。由圖可知yi+1,r=yir+1，若ε(xi+1)≥0(3)yi+1,r=yir，若ε(xi+1)≤0,Bresenham畫線算法,由式（2）和式（3）可得到ε(xi+2)=yi+2-yi+1,r-0.5=yi+1+k-yi+1,r-0.5（4）yi+1-yir-0.5+k-1,當(dāng)ε(xi+1)≥0yi+1-yir-0.5+k,當(dāng)ε(xi+1)≤0ε(xi+2)=ε(xi+1)+k-1,當(dāng)ε(xi+1)≥0ε(xi+2)=ε(xi+1)+k,當(dāng)ε(xi+1)≤0由式（1）和式（2）可得到ε(x2)=k-0.5(5),Bresenham畫線算法,BresenhamLine(CDC*pDC,intx1,inty1,intx2,inty2,COLORREFcolor){intx,y,dx,dy,p;//傳入端點坐標x值相等if(x1==x2){if(y1SetPixel(x1,i,color);}else{for(inti=y2;iSetPixel(x1,i,color);}return;},//斜率判斷，斜率絕對值大于，則m為false，否則為trueBOOLm=(fabs(y2-y1)x2){p=x1;x1=x2;x2=p;p=y1;y1=y2;y2=p;}x=x1;y=y1;dx=x2-x1;dy=y2-y1;,//斜率絕對值小于等于if(m){//第一種情況，y遞增if(y1SetPixel(x,y,color);if(pSetPixel(x,y,color);if(p<0){x++;p=p-(dy<<1);}else{x++;y--;p=p-((dy+dx)SetPixel(x0-x,y0+y,c);pDC->SetPixel(x0+x,y0-y,c);pDC->SetPixel(x0-x,y0-y,c);pDC->SetPixel(x0+y,y0+x,c);pDC->SetPixel(x0-y,y0+x,c);pDC->SetPixel(x0+y,y0-x,c);pDC->SetPixel(x0-y,y0-x,c);},對于圓心在（x0,y0)、半徑為r的圓，先對圓心在原點，半徑為r的8分圓進行掃描轉(zhuǎn)換，每確定一個象素，可輸出原始圓的8個點。,3.2.4中點畫圓法,利用圓的對稱性，只須討論1/8圓。第二個8分圓P為當(dāng)前點亮象素，那么，下一個點亮的象素可能是P1（Xp+1，Yp）或P2（Xp+1，Yp-1)。,,,,,,,,,,,,,,,M,P1,P2,P（Xp，Yp）,構(gòu)造函數(shù)：F（X，Y）=X2+Y2-R2；則F（X，Y）=0（X，Y）在圓上；F（X，Y）0（X，Y）在圓外。設(shè)M為P1、P2間的中點，M=(Xp+1,Yp-0.5),,,,,,,,,,,,,,,M,P1,P2,有如下結(jié)論：F（M）M在圓內(nèi)->取P1F（M）>=0->M在圓外->取P2為此，可采用如下判別式：,,,,,,,,,,,,,,,M,P1,P2,d=F(M)=F(xp+1,yp-0.5)=(xp+1)2+(yp-0.5)2-R2若d=0,則P2為下一個象素，那么再下一個象素的判別式為：d1=F(xp+2,yp-1.5)=(xp+2)2+(yp-1.5)2-R2=d+（2xp+3）+（-2yp+2）即d的增量為2(xp-yp)+5.d的初值:d0=F(1,R-0.5)=1+(R-0.5)2-R2=1.25-R,,,,,,,,,,,,,,,M,P1,P2,算法步驟：1.輸入圓的半徑R。2.計算初始值d=1.25-R、x=0、y=R。3.繪制點(x,y)及其在八分圓中的另外七個對稱點。4.判斷d的符號。若d<0，則先將d更新為d+2x+3，再將(x,y)更新為(x+1,y)；否則先將d更新為d+2(x-y)+5，再將(x,y)更新為(x+1,y-1)。5.當(dāng)x<=y時，重復(fù)步驟3和4。否則結(jié)束。,MidpointCircle(intr,intcolor){intx,y;floatd;x=0;y=r;d=1.25-r;drawpixel(x,y,color);while(xSetPixel((x0+y),(y0+x),color);pDC->SetPixel((x0+y),(y0-x),color);pDC->SetPixel((x0+x),(y0-y),color);pDC->SetPixel((x0-x),(y0-y),color);pDC->SetPixel((x0-y),(y0-x),color);pDC->SetPixel((x0-y),(y0+x),color);pDC->SetPixel((x0-x),(y0+y),color);return0;},（4）編寫OnDraw(CDC*pDC)函數(shù)，程序如下：voidCMidPointCircleView::OnDraw(CDC*pDC){CMidPointCircleDoc*pDoc=GetDocument();ASSERT_VALID(pDoc);//TODO:adddrawcodefornativedatahereMidpointCircle(pDC,100,100,10,RGB(255,0,0));MidpointCircle(pDC,500,300,60,RGB(255,255,0));}(5)編譯、運行程序，查看結(jié)果。,3.2.5Bresenham畫圓算法,現(xiàn)在從A點開始向右下方逐點來尋找弧AB要用的點。如圖中點Pi-1是已選中的一個表示圓弧上的點，根據(jù)弧AB的走向，下一個點應(yīng)該從Hi或者Li中選擇。顯然應(yīng)選離AB最近的點作為顯示弧AB的點。假設(shè)圓的半徑為R，顯然，當(dāng)xhi2+yhi2-R2≥R2-(xli2+yli2)時，應(yīng)該取Li。否則取Hi。令di=xhi2+yhi2+xli2+yli2-2R2顯然，當(dāng)di≥0時應(yīng)該取Li。否則，取Hi。,,,,,,,,,,,Pi-1,Hi,Li,應(yīng)取Hi還是取Li,剩下的問題是如何快速的計算di。設(shè)圖中Pi-1的坐標為(xi-1,yi-1)，則Hi和Li的坐標為(xi,yi-1)和(xi,yi-1-1)di=xi2+yi-12+xi2+(yi-1-1)2-2R2=2xi2+2yi-12-2yi-1-2R2di+1=(xi+1)2+yi2+(xi+1)2+(yi-1)2-2R2=2xi2+4xi+2yi2-2yi-2R2+3,,,,,,,,,,,Pi-1,Hi,Li,應(yīng)取Hi還是取Li,Bresenham畫圓算法,當(dāng)di取Hi->yi=yi-1，則di+1=di+4xi-1+7當(dāng)di≥0時->取Li->yi=yi-1-1，則di+1=di+4(xi-1-yi-1)+11易知x0=0，y0=R,x1=x0+1因此d0=12+y02+12+(y0-1)2-2R2=3-2y0=3-2R,,,,,,,,,,,Pi-1,Hi,Li,應(yīng)取Hi還是取Li,Bresenham畫圓算法代碼,,,voidCircleBres(intradius){intx=0,y=radius,p=3-2*radius;while(x向圓外Pi在圓外時->F(xi,yi)>0->向下->向圓內(nèi),,,,,即求得Pi點后選擇下一個象素點Pi+1的規(guī)則為：當(dāng)F(xi,yi)≤0取xi+1=xi+1，yi+1=yi;當(dāng)F(xi,yi)＞0取xi+1=xi，yi+1=yi-1;這樣用于表示圓弧的點均在圓弧附近，且使F(xi,yi)時正時負，故稱正負法?？焖儆嬎愕年P(guān)鍵是F(xi,yi)的計算，能否采用增量算法？,若F(xi,yi)已知，計算F(xi+1,yi+1)可分兩種情況：1、F(xi,yi)≤0->xi+1=xi+1，yi+1=yi;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2->=(xi+1)2+yi2-R2=F(xi,yi)+2xi+12、F(xi,yi)＞0->xi+1=xi，yi+1=yi-1;->F(xi+1,yi+1)=(xi+1)2+(yi+1)2-R2->=xi2+(yi–1)2-R2=F(xi,yi)-2yi+13、初始值：圓弧起點(0,R),圓弧終點(R，0),3.2.7生成圓弧的多邊形逼近法,圓的內(nèi)接正多邊形迫近法圓的等面積正多邊形迫近法,圓的內(nèi)接正多邊形逼近法,思想：當(dāng)一個正多邊形的邊數(shù)足夠多時，該多邊形可以和圓無限接近。即因此，在允許的誤差范圍內(nèi)，可以用正多邊形代替圓。設(shè)內(nèi)接正n邊形的頂點為Pi(xi,yi),Pi的幅角為?i,每一條邊對應(yīng)的圓心角為a，則有xi=Rcos?iyi=Rsin?i,圓的內(nèi)接正多邊形逼近法,內(nèi)接正n邊形代替圓計算多邊形各頂點的遞推公式Xi+1Rcos(a+?i)=Yi+1Rsin(a+?i)Xi+1cosa-sinaXi=Yi+1sinacosaYi因為:a是常數(shù)，sina，cosa只在開始時計算一次所以，一個頂點只需4次乘法，共4n次乘法，外加直線段的中點算法的計算量。,,,,,,,,,,,圓的等面積正多邊形逼近法,當(dāng)用內(nèi)接正多邊形逼近圓時，其面積要小于圓的面積；而當(dāng)用圓的外切正多邊形逼近圓時，其面積則要大于圓的面積。為了使近似代替圓的正多邊形和圓之間在面積上相等，只有使該正多邊形和圓弧相交，稱之為圓的等面積正多邊形。,圓的等面積正多邊形逼近法,,步驟：求多邊形徑長，從而求所有頂點坐標值由逼近誤差值，確定邊所對應(yīng)的圓心角α,3.3橢圓的掃描轉(zhuǎn)換,3.3.1橢圓的特征,,對于橢圓上的點，有F(x,y)=0；對于橢圓外的點，F(xiàn)(x,y)>0；對于橢圓內(nèi)的點，F(xiàn)(x,y)0，取Pd(xi+1,yi-1),誤差項的遞推d1≤0：取Pu(xi+1,yi),,增量為：b2(2xi+3),d1>0：取Pd(xi+1,yi-1),,增量為：b2(2xi+3)+a2(-2yi+2),判別式的初始值弧起點為(0,b)，故第一個中點為(1,b-0.5),再來推導(dǎo)橢圓弧下半部分的繪制公式原理,請思考？,判別式和初始值,若d2≤0，取(xi+1,yi-1)若d2>0，取(xi,yi-1),用上半部分計算的最后點(x，y)來計算下半部分中d的初值：d=b2(x+0.5)2+a2(y-1)2-a2b2,遞推式,d>0,取正下方元素（xi，yi-1）,遞推式,d<＝0,取右下方元素（xi+1，yi-1）,算法描述,(1)輸入橢圓的長半軸a和短半軸b。(2)計算初始值：d=b2+a2(-b+0.25),x=0,y=b.(3)繪制點(x,y)及其在四分象限上的另外3個對稱點.(4)判斷d的符號。若d＜=0，則先將d更新為d+b2(2xi+3),再將（xi,yi）更新為（xi+1,yi）;否則先將d更新為d+b2(2xi+3)+a2(-2yi+2),再將（xi,yi）更新為（xi+1,yi-1）(5)當(dāng)b2(x+1)
下載提示(請認真閱讀)
- 1.請仔細閱讀文檔，確保文檔完整性，對于不預(yù)覽、不比對內(nèi)容而直接下載帶來的問題本站不予受理。
- 2.下載的文檔，不會出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入（下載+內(nèi)容+預(yù)覽）歸上傳者、原創(chuàng)作者；如果您是本文檔原作者，請點此認領(lǐng)！既往收益都歸您。
文檔包含非法信息？點此舉報后獲取現(xiàn)金獎勵！
下載文檔到電腦，查找使用更方便
14.9
積分
- 配套講稿：
如PPT文件的首頁顯示word圖標，表示該PPT已包含配套word講稿。雙擊word圖標可打開word文檔。
- 特殊限制：
部分文檔作品中含有的國旗、國徽等圖片，僅作為作品整體效果示例展示，禁止商用。設(shè)計者僅對作品中獨創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞：
-
直線
橢圓
生成
- 溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
裝配圖網(wǎng)所有資源均是用戶自行上傳分享，僅供網(wǎng)友學(xué)習(xí)交流，未經(jīng)上傳用戶書面授權(quán)，請勿作他用。
直線、圓、橢圓的生成.ppt
鏈接地址：http://ioszen.com/p-12202390.html