第03章1-基于光柵掃描轉(zhuǎn)換的二維圖元生成算法

計(jì)算機(jī)圖形學(xué)

ComputerGraphics第3章基于光柵掃描的二維圖元生成算法第3章基于光柵掃描的二維圖元生成算法本章研究如何將連續(xù)的圖形轉(zhuǎn)換成顯示器能夠識(shí)別的柵格點(diǎn)陣形式–離散化。從20世紀(jì)70年代初光柵圖形顯示器的誕生到現(xiàn)在，出現(xiàn)了大量比較成熟的光柵掃描算法，主要是針對(duì)以柵格排列像素的顯示設(shè)備，研究圖形輸出的近似算法。包括各種畫線算法、填充算法、多種線型線寬的繪制方法、字型技術(shù)、圖形的裁剪算法以及反走樣技術(shù)等3.1直線的掃描轉(zhuǎn)換在數(shù)學(xué)上，理想的直線是沒有寬度的，是由無數(shù)個(gè)點(diǎn)構(gòu)成的集合。當(dāng)我們對(duì)直線進(jìn)行光柵化時(shí)，只能在顯示器所給定的有限個(gè)象素組成的矩陣中，確定最佳逼近于該直線的一組象素，并且按掃描線順序，以指定的方式對(duì)這些象素進(jìn)行寫操作，這就是通常所說的用顯示器繪制直線或直線的掃描轉(zhuǎn)換。3.1直線的掃描轉(zhuǎn)換通常直線段是有寬度的為簡單起見，討論只有一個(gè)像素寬度的直線段的掃描轉(zhuǎn)換算法。對(duì)于具有一個(gè)像素寬度的直線段來說，近似表示它的像素集也應(yīng)該具有一個(gè)像素的寬度當(dāng)該線段的斜率落在-1到1之間時(shí)，它在每個(gè)掃描列上僅有一個(gè)像素。同樣，當(dāng)線段的斜率的絕對(duì)值大于1時(shí)，它在每個(gè)掃描行上僅有一個(gè)像素。3.1.1基本增量算法DDA直線方程：y=mx+b0<m<1，m=△y/△x；x=1，xi+1=xi+1，yi+1=yi+m3.1.1基本增量算法DDA增量算法的定義：每一步都是根據(jù)前一步進(jìn)行增量計(jì)算。這種算法通常被稱作數(shù)值微分(DDA)算法。DDA(DigitalDifferentialAnalyzeralgorithm)是用數(shù)值方法解決微分方程的一種手段如果｜m｜>1，則x的步進(jìn)會(huì)使y的步進(jìn)超過1，此時(shí)，如果采用上述算法將會(huì)使得點(diǎn)亮的象素個(gè)數(shù)太少，畫出來的線沒有很好的模擬理想直線。解決辦法是顛倒x與y的位置，給y以單位增量，而x的增量為Δx=Δy/m=1/m，即取x軸和y軸中變化最快的軸作為參考軸以保證直線被光柵化后有足夠多的象素。增量算法的缺點(diǎn)是需要用浮點(diǎn)數(shù)表示，而且每一步運(yùn)算都必須舍入取整，這不利于用硬件實(shí)現(xiàn)運(yùn)算。3.1.1基本增量算法DDA為直線類CLineType增加一個(gè)函數(shù)DDADrawLinevoidCLineType::DDADrawLine(HDChdc,COLORREFrgb){intx0,y0,x1,y1,i;doublem,y;x0=m_ptBegPos.Getx(); y0=m_ptBegPos.Gety();x1=m_ptEndPos.Getx(); y1=m_ptEndPos.Gety();m=(double)(y1-y0)/(double)(x1-x0);y=y0;CPointType*p;for(i=x0;i<x1;i++){p=newCPointType(i,(int)(y+0.5));p->DrawPoint(hdc,rgb);deletep;y+=m;}}3.1.2中點(diǎn)畫線算法消除了浮點(diǎn)加法和取整運(yùn)算，采用整數(shù)加法和比較運(yùn)算，大大提高了運(yùn)算速度主要采用整數(shù)加法和比較運(yùn)算，運(yùn)算速度大大提高，是圖形軟件廣泛采用的算法仍然假定直線斜率3.1.2中點(diǎn)畫線算法直線方程隱函數(shù)形式直線的正負(fù)劃分性3.1.2中點(diǎn)畫線算法中點(diǎn)M=(xp+1,yp+1/2)

d=F(M)=0M是直線一點(diǎn)>0M在直線上方<0M在直線下方d=0點(diǎn)亮E或者NE>0點(diǎn)亮E<0點(diǎn)亮NE

已知當(dāng)前dp，可推算出下一個(gè)像素(xp+1,yp+1)接著推算出下一個(gè)dp+1

3.1.2中點(diǎn)畫線算法由令-Δy=a,Δx=b,-Δx·b=cdp=a(xp＋1)+b(yp＋1/2)＋cdp+1=F(xp+1＋1，yp+1＋1/2)=F(xp+2，yp+3/2)，當(dāng)dp<0=F(xp+2，yp+1/2)，當(dāng)dp>0dp+1=a(xp+2)+b(yp+3/2)+c，當(dāng)dp<0a(xp+2)+b(yp+1/2)+c，當(dāng)dp>0dp+1=dp+a+b，當(dāng)dp<0dp+a，當(dāng)dp>03.1.2中點(diǎn)畫線算法dp+1=dp-Δy+Δx

，當(dāng)dp<0dp-Δy，當(dāng)dp>0由于d和2d的正負(fù)判別式是等價(jià)的，不妨都乘以2，則dp+1=dp-

2Δy+2Δx

，當(dāng)dp<0dp-2Δy，當(dāng)dp>0yp+1=yp+1

，當(dāng)dp<0yp，當(dāng)dp>03.1.2中點(diǎn)畫線算法voidCLineType::MidDrawLine(HDChdc,COLORREFrgb){intx0,y0,x1,y1;Intd,dx,dy,dNE,dE,x,y;x0=m_ptBegPos.Getx();y0=m_ptBegPos.Gety();x1=m_ptEndPos.Getx();y1=m_ptEndPos.Gety();dx=x1-x0;dy=y1-y0;d=dx-2*dy;dNE=2*dx-2*dy;dE=-2*dy;x=x0; y=y0;CPointType*p;3.1.2中點(diǎn)畫線算法while(x<x1){p=newCPointType(x,y);p->DrawPoint(hdc,rgb);deletep;if(d<=0){d+=dNE;y++;}elsed+=dE;x++;}}3.1.3Bresenham畫線算法0<m<1d=0;d=d+m;當(dāng)d>1時(shí)，只保留d的小數(shù)部分作為d的新值x=x+1,y則根據(jù)d>0.5來決定點(diǎn)亮(x+1,y)還是(x+1,y+1)3.1.3Bresenham畫線算法令e=d－0.5。則當(dāng)e0時(shí)，下一象素的y坐標(biāo)增加1，而當(dāng)e0時(shí)，下一象素的y坐標(biāo)不變。e的初值為－0.5。從而利用e代替d，來判斷下一點(diǎn)的取舍3.1.3Bresenham畫線算法voidCLineType::BresenhamDrawLine(HDChdc,COLORREFrgb){ intx0,y0,x1,y1,x,y,dx,dy; floatk,e; x0=m_ptBegPos.Getx();y0=m_ptBegPos.Gety(); x1=m_ptEndPos.Getx();y1=m_ptEndPos.Gety(); dx=x1-x0;dy=y1-y0; k=(float)dy/dx; e=-0.5; x=x0; y=y0; CPointType*p; for(x=x0;x<x1;x++){ p=newCPointType(x,y); p->DrawPoint(hdc,rgb); deletep; e=e+k; if(e>0){ y=y+1; e=e-1; } }}3.2園與橢圓的掃描轉(zhuǎn)換園和橢圓的掃描轉(zhuǎn)換算法要比直線復(fù)雜直線的斜率是常量，便于遞推具有對(duì)稱性，可使問題簡化3.2.1園的掃描轉(zhuǎn)換討論圓心位于坐標(biāo)原點(diǎn)的圓弧的掃描轉(zhuǎn)換算法，對(duì)于圓心為任意點(diǎn)的圓弧，可以先將其平移到原點(diǎn)，然后掃描轉(zhuǎn)換，再平移到原來位置。利用園的八對(duì)稱性，只需掃描轉(zhuǎn)換八分之一圓弧即可1.中點(diǎn)畫圓算法將圓弧的函數(shù)方程改寫為隱函數(shù)的形式：1.中點(diǎn)畫圓算法考慮第一象限內(nèi)假設(shè)已計(jì)算出當(dāng)前像素為P=(Xp,Yp)，則下一個(gè)掃描列只可能是E和SE。中點(diǎn)M=(Xp+1,Yp-(1/2))。令d=F(M)d=0中點(diǎn)在圓上;點(diǎn)亮可取E或SEd<0中點(diǎn)在圓內(nèi);點(diǎn)亮可取Ed>0中點(diǎn)在圓外;點(diǎn)亮可取SE1.中點(diǎn)畫圓算法1.中點(diǎn)畫圓算法設(shè)ep=dp-0.25通常r>1，所以d0<0，則e0<0所以d0和e0判別正負(fù)的條件是等價(jià)的1.中點(diǎn)畫圓算法voidCCircleType::MidDrawCircle(HDChdc,COLORREFrgb){ intx,y; inte=1-m_nR; x=0; y=m_nR; CPointType*p; while(x<y) { p=newCPointType(x,y); Draw8(*p,hdc,rgb); deletep; if(e<=0) e=e+2*x+3; else { e=e+2*x-2*y+5; y--; } x++; }}1.中點(diǎn)畫圓算法voidCCircleType::Draw8(CPointType&p,HDChdc,COLORREFrgb){ CPointType*pt[8]; intx,y,cx,cy; x=p.Getx(); y=p.Gety(); cx=m_ptCenter.Getx(); cy=m_ptCenter.Gety(); pt[0]=newCPointType(x+cx,y+cy); pt[1]=newCPointType(y+cx,x+cy); pt[2]=newCPointType(-y+cx,x+cy); pt[3]=newCPointType(-x+cx,y+cy); pt[4]=newCPointType(y+cx,-x+cy); pt[5]=newCPointType(x+cx,-y+cy); pt[6]=newCPointType(-x+cx,-y+cy); pt[7]=newCPointType(-y+cx,-x+cy); for(inti=0;i<8;i++) { pt[i]->DrawPoint(hdc,rgb); deletept[i]; }}3.2.2橢圓的掃描轉(zhuǎn)換生成橢圓的中點(diǎn)算法和生成圓的中點(diǎn)算法在基本處理方法上是完全一致的，只不過橢圓的方程復(fù)雜一些，相應(yīng)的計(jì)算過程也復(fù)雜一些。中心在圓點(diǎn)的橢圓的方程為：3.2.2橢圓的掃描轉(zhuǎn)換由于橢圓的對(duì)稱性，我們只需要討論第一象限內(nèi)橢圓弧的生成。在第一象限內(nèi)，我們進(jìn)一步將該段橢圓弧分為上、下兩部分，分界點(diǎn)為切線斜率為-1的點(diǎn)橢圓弧上任一點(diǎn)(x,y)的法向量由于切向量與法向量是垂直的，則分界點(diǎn)法向量斜率為1還要注意到，上半部分的法向量斜率大于1，下半部分小于13.2.2橢圓的掃描轉(zhuǎn)換對(duì)于上半部分，切線斜率<-1假設(shè)已計(jì)算出當(dāng)前像素為P=(Xp,Yp)，則下一個(gè)掃描列只可能是E和SE。中點(diǎn)M=(Xp+1,Yp-(1/2))。令d=F(M)d=0中點(diǎn)在橢圓上;點(diǎn)亮可取E或SEd<0中點(diǎn)在橢圓內(nèi);點(diǎn)亮可取Ed>0中點(diǎn)在橢圓外;點(diǎn)亮可取SE3.2.2橢圓的掃描轉(zhuǎn)換3.2.2橢圓的掃描轉(zhuǎn)換初始條件3.2.2橢圓的掃描轉(zhuǎn)換對(duì)于下半部分，切線斜>-1，所以從點(diǎn)(a,0)開始，按每一掃描列由下往上掃描轉(zhuǎn)換假設(shè)已計(jì)算出當(dāng)前像素為P=(Xp,Yp)，則下一個(gè)掃描列只可能是N和WN。中點(diǎn)M=(Xp-1/2,Yp+1)。令d=F(M)d=0中點(diǎn)在橢圓上;點(diǎn)亮可取N或WNd<0中點(diǎn)在橢圓內(nèi);點(diǎn)亮可取Nd>0中點(diǎn)在橢圓外;點(diǎn)亮可取WN3.2.2橢圓的掃描轉(zhuǎn)換3.2.2橢圓的掃描轉(zhuǎn)換初始條件3.2.2橢圓的掃描轉(zhuǎn)換因?yàn)槊看伪容^的都是中點(diǎn)的正負(fù)判別性，則從上半?yún)^(qū)轉(zhuǎn)到下半?yún)^(qū)的過程中滿足ES區(qū)域1區(qū)域2梯度矢量3.2.2橢圓的掃描轉(zhuǎn)換由于初始條件包含小數(shù)，為避免浮點(diǎn)運(yùn)算，可以采取兩邊乘以4的做法。上半?yún)^(qū)3.2.2橢圓的掃描轉(zhuǎn)換下半?yún)^(qū)3.2.2橢圓的掃描轉(zhuǎn)換voidCEllipseType::Draw4(CPointType&pt,HDChdc,COLORREFrgb){ CPointType*p[4]; intx,y,cx,cy; x=pt.Getx();y=pt.Gety(); cx=m_ptCenter.Getx(); cy=m_ptCenter.Gety(); p[0]=newCPointType(x+cx,y+cy); p[1]=newCPointType(-x+cx,y+cy); p[2]=newCPointType(x+cx,-y+cy); p[3]=newCPointType(-x+cx,-y+cy); for(inti=0;i<4;i++) { p[i]->DrawPoint(hdc,rgb); deletep[i]; }}3.2.2橢圓的掃描轉(zhuǎn)換voidCEllipseType::MidDrawEllipse(HDChdc,COLORREFrgb){ doubled; intx,y; CPointType*p; x=0;y=b; d=4*b*b-4*a*a*b+a*a; while((a*a*(2*y-1))>=2*(b*b*(x+1))){ p=newCPointType(x,y); Draw4(*p,hdc,rgb); deletep; if(d<0) d=d+4*b*b*(2*x+3); else{ d=d+4*b*b*(2*x+3)-8*a*a*(y-1); y--; } x++; }3.2.2橢圓的掃描轉(zhuǎn)換 x=a;y=0; d=4*a*a-4*a*b*b+b*b; while((b*b*(2*x-1))>2*(a*a*(y+1))){ p=newCPointType(x,y); Draw4(*p,hdc,rgb); deletep; if(d<0) d=d+4*a*a*(2*y+3); else{ d=d+4*a*a*(2*y+3)-8*b*b*(x-1); x--; } y++; }}3.3區(qū)域填充第一步先確定需要填充哪些像素第二步確定用什么顏色填充多邊形填充園域填充圖案填充3.3.1多邊形域的填充表示方法：定點(diǎn)表示和點(diǎn)陣表示

頂點(diǎn)表示是用多邊形的頂點(diǎn)的序列來描述多邊形，該表示幾何意義強(qiáng)、占內(nèi)存少，但它不能直觀地說明哪些像素在多邊形內(nèi)。

點(diǎn)陣表示是用位于多邊形內(nèi)的象素的集合來刻劃多邊形，該方法雖然沒有多邊形的幾何信息，但具有面著色所需要的圖像表示形式。

多邊形填充就是把多邊形的頂點(diǎn)表示轉(zhuǎn)換為點(diǎn)陣表示，即從多邊形的給定邊界出發(fā)，求出位于其內(nèi)部的各個(gè)像素，并將幀緩沖器內(nèi)的各個(gè)對(duì)應(yīng)元素設(shè)置為相應(yīng)的灰度或顏色。1.有序邊表算法充分利用了相鄰像素之間的連貫性，避免了逐點(diǎn)判斷和反復(fù)求交計(jì)算，達(dá)到了減少計(jì)算量和提高速度為簡單起見，考慮的是非自交多邊形，即邊與邊之間除了頂點(diǎn)外無其它交點(diǎn)。要掃描自交多邊形，只需將算法稍加修改即可達(dá)到目的按照掃描線順序計(jì)算掃描線與多邊形的相交區(qū)間，再用要求的顏色顯示這些區(qū)間內(nèi)的像素，即填充。區(qū)間的端點(diǎn)通過計(jì)算掃描線與多邊形邊界的交點(diǎn)而得到1.有序邊表算法首先，將在整個(gè)繪圖窗口內(nèi)掃描轉(zhuǎn)換多邊形的問題分解到一條掃描線上來考慮，這樣，只要完成繪圖窗口內(nèi)每一條掃描線上位于多邊形內(nèi)部的區(qū)段的填充工作，也就完成了整個(gè)多邊形的掃描轉(zhuǎn)換。由觀察不難發(fā)現(xiàn)，一條掃描線和多邊形的邊有偶數(shù)個(gè)交點(diǎn)，若我們將這些交點(diǎn)按橫坐標(biāo)從小到大的順序進(jìn)行排序，則第1個(gè)交點(diǎn)與第2個(gè)交點(diǎn)之間，第3個(gè)交點(diǎn)與第4個(gè)交點(diǎn)之間，其像素位于多邊形內(nèi)部，這種性質(zhì)稱為掃描線的連貫性1.有序邊表算法一條掃描線上的填充過程可分為下面三個(gè)步驟：(1)求掃描線與多邊形各邊的交點(diǎn)；(2)對(duì)所求得的交點(diǎn)按x坐標(biāo)從小到大排序；(3)將交點(diǎn)兩兩配對(duì)，并填充每一區(qū)段。在多邊形的填充算法中，關(guān)鍵是求掃描線與各邊的交點(diǎn)問題，這里面有兩個(gè)問題需要解決一是當(dāng)掃描線與多邊形頂點(diǎn)相交時(shí)，交點(diǎn)的取舍問題二是多邊形邊界上像素的取舍問題，前者用于保證交點(diǎn)正確配對(duì)，后者用于避免填充擴(kuò)大化。1.有序邊表算法解決掃描線與多邊形的交點(diǎn)問題可以采用“下閉上開”的方法；解決邊界上的像素取舍問題可以采用“左閉右開”的辦法。在求交點(diǎn)時(shí)要充分利用邊的連貫性，可以提高求交的效率。假設(shè)直線的斜率為k，由于每次y遞增一個(gè)像素單位，則x遞增1/k，在某條邊未達(dá)到頂點(diǎn)時(shí)，下一交點(diǎn)可以此方法遞推1.有序邊表算法掃描線算法中采用了較靈活的數(shù)據(jù)結(jié)構(gòu)，即邊的分類表ET和活化邊表AET，兩個(gè)表結(jié)構(gòu)中的基本元素都是邊結(jié)構(gòu)。邊結(jié)構(gòu)定義為structEdge{//多邊形邊結(jié)構(gòu)

intymax; //邊的最大y坐標(biāo)

doublex; //邊的起始x坐標(biāo)或邊與掃描線的交點(diǎn)坐標(biāo)

doubledx;//邊的斜率的倒數(shù)

structEdge*nextEdge;//指向下一條邊的指針};1.有序邊表算法邊的分類表ET是按照邊的下端點(diǎn)的y坐標(biāo)對(duì)非水平邊進(jìn)行分類的指針數(shù)組1.有序邊表算法活化邊表AET由與當(dāng)前掃描線相交的邊組成，它記錄多邊形的邊和掃描線的所有交點(diǎn)的x坐標(biāo)，并且隨掃描線的遞增而不斷變化。

邊的分類表的作用是避免盲目求交。當(dāng)處理一條掃描線時(shí)，為了求得它和多邊形的所有交點(diǎn)，必須將它與所有的邊進(jìn)行求交測試。而實(shí)際上只有某幾條邊與該掃描線有交點(diǎn)。邊的分類表正是用來排除不必要的求交測試的。1.有序邊表算法#include<windows.h>…邊結(jié)構(gòu)定義classCMyPolygon{private: intm_nVertics; //多邊形頂點(diǎn)數(shù) POINT*m_pHead; //頂點(diǎn)表頭指針public: CMyPolygon(void); ~CMyPolygon(void); CMyPolygon(intvertics,POINT*p); voidShow(HDChdc);private: voidGetEdge(POINT&pb,POINT&pe,inti); voidSort(intn,double*a); intGetMaxY(void);};1.有序邊表算法CMyPolygon::CMyPolygon(intvertics,POINT*p){inti=0,k=0;POINTmin=p[0];while(i<vertics){//找出y坐標(biāo)最小的頂點(diǎn)序號(hào)k，vertics：最高點(diǎn) if(p[i].y<min.y){ min=p[i]; k=i; } i++;}m_nVertics=vertics; //設(shè)置頂點(diǎn)個(gè)數(shù)

m_pHead=newPOINT[m_nVertics];for(i=0;i<m_nVertics;i++){//將第k個(gè)頂點(diǎn)設(shè)置成第一個(gè)頂點(diǎn)

if(k+i<m_nVertics) m_pHead[i]=p[k+i]; else m_pHead[i]=p[k+i-m_nVertics];}}1.有序邊表算法voidCMyPolygon::GetEdge(POINT&pb,POINT&pe,inti){POINTtemp;if(i>=m_nVertics||i<0)return;pb=m_pHead[i];if(i<m_nVertics-1)pe=m_pHead[i+1];elsepe=m_pHead[0];if(pb.y>pe.y){temp=pb;pb=pe;pe=temp;}}1.有序邊表算法voidCMyPolygon::Show(HDChdc){constintmaxIntersections=100;//最大交點(diǎn)數(shù)目inti,j,k,n,min,max,tx;min=m_pHead[0].y;//起始掃描線

max=GetMaxY();//結(jié)尾掃描線

n=max-min;Edge**ET=newEdge*[n];//定義邊表指針數(shù)組

Edge*AET=NULL; //定義活化邊表

POINTposBeg,posEnd; //定義線段的起點(diǎn)和終點(diǎn)

Edge*p,*q,*pNode,*pt; //定義邊指針

doublea[maxIntersections];//存放交點(diǎn)橫坐標(biāo)的數(shù)組for(i=0;i<n;i++)//建立邊表ET(EdgeTable) ET[i]=NULL;1.有序邊表算法for(j=0;j<m_nVertics;j++){ //逐邊進(jìn)行處理

GetEdge(posBeg,posEnd,j); //獲取第j條邊

if(posBeg.y!=posEnd.y){ pNode=newEdge; //建立一個(gè)邊結(jié)點(diǎn)

pNode->x=(double)posBeg.x;pNode->dx=(double)(posEnd.x-posBeg.x)/(posEnd.y-posBeg.y); pNode->ymax=posEnd.y-1; //下閉上開

pNode->nextEdge=NULL;if(!ET[posBeg.y-min])//將邊插入到ET中

ET[posBeg.y-min]=pNode; else{ p=ET[posBeg.y-min]; q=p;//指向前驅(qū)結(jié)點(diǎn)

p=p->nextEdge;//指向當(dāng)前結(jié)點(diǎn)

while(p){ q=p; p=p->nextEdge; } q->nextEdge=pNode; } }}1.有序邊表算法for(i=0;i<n;i++){ //開始掃描，各邊依次加入到AET中

if(ET[i]){//有新邊加入

pt=ET[i]; while(pt){//從ET中取出新邊，并將該邊從ET中去除

pNode=pt; pt=pt->nextEdge; pNode->nextEdge=NULL; if(!AET)//插入新邊并按x坐標(biāo)由小到大排序

AET=pNode; else{//AET非空

p=AET; while(p->nextEdge) p=p->nextEdge; p->nextEdge=pNode; } } }1.有序邊表算法if(AET){//刪除AET中ymax小于當(dāng)前掃描線的邊

p=AET; q=NULL; //當(dāng)前指針和前驅(qū)指針

while(p){ if(p->ymax<i+min){ if(!q){ //刪除頭結(jié)點(diǎn)

pNode=p; p=p->nextEdge; AET=p; } else{//刪除非頭結(jié)點(diǎn)

pNode=p; p=p->nextEdge; q->nextEdge=p; } deletepNode; } else{ q=p; p=p->nextEdge; } }}1.有序邊表算法if(AET){//對(duì)AET中的邊兩兩配對(duì)，填充每一區(qū)段

p=AET; k=0; while(p){//取出所有交點(diǎn)

a[k]=p->x; p->x=p->x+p->dx; k++; p=p->nextEdge; }

Sort(k,a); //本掃描線上共有k個(gè)交點(diǎn)，對(duì)k個(gè)交點(diǎn)排序1.有序邊表算法

for(j=0;j<k;j++){if(j%2==0){ tx=(int)a[j];//左邊交點(diǎn)向右取整

if((a[j]-(double)tx)) posBeg.x=tx+1; else posBeg.x=tx; posBeg.y=i+min; posEnd.x=(int)a[j+1];//右邊交點(diǎn)向左取整

posEnd.y=i+min; MoveToEx(hdc,posBeg.x,posBeg.y,NULL); LineTo(hdc,posEnd.x,posEnd.y); } } }}//所有掃描線處理完畢delete[]ET;}1.有序邊表算法有序邊表算法的優(yōu)點(diǎn)是對(duì)顯示的每個(gè)像素僅訪問一次，效率較高與設(shè)備無關(guān)算法較復(fù)雜，數(shù)據(jù)量較大，不適合硬件實(shí)現(xiàn)2.邊標(biāo)志填充算法采用對(duì)圖像進(jìn)行逐位求反的方法，免去對(duì)邊排序的工作量對(duì)圖像M作偶數(shù)次求反運(yùn)算，其結(jié)果還是M，而對(duì)M作奇數(shù)次求反運(yùn)算的結(jié)果是的反2.邊標(biāo)志填充算法本算法的優(yōu)點(diǎn)是簡單缺點(diǎn)是對(duì)于復(fù)雜圖形，每一象素可能被訪問多次，輸入／輸出的量比有序邊表算法大得多為了減少邊填充算法訪問象素的次數(shù)，可引入柵欄。所謂柵欄指的是一條與掃描線垂直的直線，柵欄位置通常取過多邊形頂點(diǎn)、且把多邊形分為左右兩半2.邊標(biāo)志填充算法掃描線與多邊形邊有交點(diǎn)，就將交點(diǎn)與柵欄之間的象素取補(bǔ)。若交點(diǎn)位于柵欄左邊，則將交點(diǎn)之右，柵欄之左的所有象素取補(bǔ)；若交點(diǎn)位于柵欄右邊，則將柵欄之右，交點(diǎn)之左的象素取補(bǔ)2.邊標(biāo)志填充算法柵欄填充算法只是減少了象素重復(fù)訪問的數(shù)目。邊標(biāo)志算法進(jìn)一步改進(jìn)了柵欄填充算法，使得算法對(duì)每個(gè)象素僅訪問一次?；驹恚菏紫扔靡环N特殊的顏色在幀緩沖器中將多邊形的邊界（水平邊的部分邊界除外）勾畫出來。然后再把位于多邊形內(nèi)的各個(gè)像素著上所需的顏色。步驟1：以值為boundary-color的特殊顏色勾畫多邊形P的邊界。步驟2：設(shè)interior_point是一布爾變量。對(duì)每一條掃描線從左到右進(jìn)行搜索，如果當(dāng)前像素位于多邊形P內(nèi)，則interior_point=true，需要填上值為polygon_color的顏色；否則該像素在多邊形P外，需要填上值為background_color的顏色3.種子填充算法種子填充算法是根據(jù)已知的一個(gè)多邊形區(qū)域內(nèi)部的一個(gè)象素點(diǎn)來找到區(qū)域內(nèi)其它的象素點(diǎn)進(jìn)行填充的區(qū)域必須是連通的四連通區(qū)域和八連通區(qū)域3.種子填充算法簡單的種子填充算法如下：(1)將種子象素壓入棧中；(2)當(dāng)棧非空時(shí)從棧中彈出一個(gè)象素；將該象素置成所要求的色彩值；檢查每個(gè)與當(dāng)前象素鄰接的四連通象素是否是邊界色或已置成所要求的色彩值，若是則返回(2)，否則將該象素壓入棧中回到(2)當(dāng)棧為空時(shí)，算法結(jié)束3.種子填充算法初始時(shí)棧中只有(3，3)象素；彈出(3，3)，由于該象素未置成色彩值且也不是邊界色，故填色彩值；同時(shí)將(3，4)(3，2)(2，3)及(4，3)壓入棧中；棧中有四個(gè)元素；彈出(4，3)并置上要求的色彩值，再將(4，4)(4，2)(5，3)壓入棧中；棧中有6個(gè)元素；依次類推，象素被選中并填充的次序如圖中箭頭所示3.種子填充算法所謂改進(jìn)的掃描線種子填充算法，是在任意不間斷掃描線區(qū)間中只取一個(gè)種子象素。不間斷區(qū)間即指在一條掃描線上一組相鄰的元素1）從包含種子象素的棧中彈出種子象素；2）沿著掃描線對(duì)種子象素進(jìn)行填充，直到遇到邊界象素為止，這樣就填充了種子所在的掃描線中的元素；3）區(qū)間內(nèi)最左、最右元素為Xleft，Xright;則在XleftXXright區(qū)間中檢查與當(dāng)前掃描線相鄰的上、下兩條掃描線是否全為邊界象素或已填充過的象素。若不是，則對(duì)于XleftXXrigh，把與當(dāng)前掃描線相鄰的上、下兩條掃描線中該區(qū)間的最右象素作為種子壓入棧中。算法結(jié)束條件為?？铡４怂惴ㄟm用于用邊界定義的區(qū)域。3.種子填充算法S→A→C→B→D→F→G→H→E3.3.2圓域的填充上面所討論的多邊形區(qū)域的填充原理也可以推廣到圓域的填充。對(duì)每條掃描線，先計(jì)算它與圓域的相交區(qū)間，再把區(qū)間內(nèi)象素用指定顏色填充3.3.3圖案填充2023/1/3169(a)山巒景色(b)待填充區(qū)域輪廓線(d)(e)(g)(c)圖案模式(f)(d)待填充區(qū)域的像素位圖

(e)擦除(a)中(d)區(qū)域，將像素寫為背景色(f)對(duì)待填充區(qū)域進(jìn)行圖案填充(g)以透明模式把(f)繪在屏幕上3.4線寬與線型的處理在輸出圖元時(shí)，我們可以通過設(shè)置圖元的各種屬性來控制圖元的外觀。線畫圖形的屬性主要有線寬、線型和顏色在實(shí)際應(yīng)用中，除了使用單象素寬的線條，還經(jīng)常使用指定線寬和線型的直線與弧線3.4.1直線線寬的處理要產(chǎn)生具有寬度的線，可以選取寬度適中的“刷子”來進(jìn)行繪圖。但問題是“刷子”的形狀是什么樣的好？“刷子”運(yùn)動(dòng)時(shí)如何控制走向？以及線型如何控制？3.4.1直線線寬的處理線刷子的原理是用像素復(fù)制方法來得到所需的線寬效果的。在進(jìn)行掃描轉(zhuǎn)換時(shí)，同時(shí)復(fù)制k個(gè)像素，如果圖元在像素點(diǎn)的斜率m∈(-1,1)時(shí)，進(jìn)行垂直方向的像素復(fù)制，否則進(jìn)行水平方向上的像素復(fù)制。3.4.1直線線寬的處理這個(gè)方法的優(yōu)點(diǎn)是效率高，實(shí)現(xiàn)簡單，只要在相應(yīng)的掃描轉(zhuǎn)換程序中加上幾行就行了，但缺點(diǎn)也是明顯的：(1)線段的兩端或者是水平的，或者是垂直的，與直線的斜率無關(guān)，這使得寬度較大的線段看起來極不自然。(2)對(duì)折線來說，由于相鄰兩條線段的斜率不同，可能導(dǎo)致頂點(diǎn)處有缺口。(3)線寬不均勻。水平和垂直方向上線寬最大，而在|m|=1處線寬最小。(4)這種方法產(chǎn)生寬度為奇數(shù)個(gè)像素的圖元效果好，而對(duì)偶數(shù)個(gè)像素的圖元來說則是不對(duì)稱的。

3.4.1直線線寬的處理方刷子的原理是以單像素線條的每個(gè)像素作為中心，將中心所對(duì)應(yīng)的事先指定的正方形區(qū)域全部用相同的像素進(jìn)行像素復(fù)制。用方刷子繪制的線條比用線刷子得到的線條要粗一些。與線刷子的方法類似，用方刷子繪制的圖元的兩端也是垂直或水平的，且圖元的寬度與其斜率有關(guān)。但與線刷子相反的是，當(dāng)要繪制寬度為k的圖元時(shí)，在切線水平或垂直處寬度最小，而在|m|=1處，寬度達(dá)到最大。3.4.1直線線寬的處理若要產(chǎn)生寬度為k的圖元，可以首先計(jì)算出距原理想圖元k/2的兩條等距線，將它們連接起來就構(gòu)成了寬度為k的區(qū)域，然后調(diào)用填充圖元的生成函數(shù)將其填充。便得到了所求的寬度為k的圖元。這種方法的特點(diǎn)是生成的圖元的寬度均勻，兩端點(diǎn)處的邊垂直圖元在該點(diǎn)的切向，所以生成的圖形質(zhì)量較高。但計(jì)算量較大。利用這種方法，直線段被表示成矩形區(qū)域，圓弧被表示為環(huán)形區(qū)域。3.4.2圓弧線寬的處理為了生成具有寬度的圓弧，可采用與直線情形類似的方法，當(dāng)采用線刷子時(shí)，在經(jīng)過曲線斜率為1的點(diǎn)時(shí)，必須把線刷子在水平與垂直方向之間切換。由于線刷子總是置成水平或垂直的，所以在曲線接近水平與垂直的地方，線條更粗一些，而在斜率接近1的點(diǎn)附近，線條更細(xì)一些，如圖所示。當(dāng)采用正方形刷子時(shí)，無需移動(dòng)刷子方向。只需順著單象素的軌跡，把正方形中心對(duì)準(zhǔn)軌跡上的象素，把方形內(nèi)的象素全部用線條顏色填充。用正方形刷子繪制的曲線條，在接近水平與垂直的部分最細(xì)，而在斜率為1的點(diǎn)附近最粗，這恰與線刷子情形相反，如圖所示。3.4.3線型的處理

線型是指線條的不同樣式，如實(shí)線，虛線，點(diǎn)畫線等。線型可以用一個(gè)布爾值的序列來存放。例如可以用一個(gè)32位整數(shù)來存放線型，根據(jù)每位的值來確定相應(yīng)位像素是否顯示，從而得到不同的線型。用這樣的位串控制線型時(shí)，線型必須以32個(gè)像素為周期進(jìn)行重復(fù)。

3.5字符字符是指數(shù)字、字母、漢字等符號(hào)，用于圖形的標(biāo)注、說明等。國際上最流行的字符集是“美國信息交換用標(biāo)準(zhǔn)代碼集“（AmericanStandardCodeforInformationInterchange），簡稱ASCII碼。該字符集規(guī)定了127個(gè)字符代碼。其中代碼0—31表示控制字符，代碼32—127表示英文字母、標(biāo)點(diǎn)符號(hào)、數(shù)字符號(hào)、各種運(yùn)算符以及特殊符號(hào)。每個(gè)ASCII碼用一個(gè)字節(jié)（實(shí)際上只要七位二進(jìn)制）代碼表示。3.5字符我國除采用ASCII碼外，還另外制訂了漢字代碼的國家標(biāo)準(zhǔn)字符集。最常用的字符集是”信息交換用漢字編碼字符集基本集”GB2312—80。該字符集包含了六千多個(gè)常用漢字，以及英文字母、數(shù)字和其它圖形符號(hào)。分成94個(gè)區(qū)94個(gè)位。區(qū)碼和位碼各用一個(gè)字節(jié)（實(shí)際上只要七位二進(jìn)制）來表示。為了能識(shí)別哪些字節(jié)表示ASCII碼，哪些字節(jié)表示漢字編碼，一般采用多余的一位（最高位）來標(biāo)識(shí)。最高位為0時(shí)，表示ASCII碼，最高位為1時(shí)表示漢字編碼。為了在終端顯示器或繪圖儀上輸出字符，系統(tǒng)中必須裝備有相應(yīng)的字符庫。字符庫中儲(chǔ)存了每個(gè)字符的形狀信息3.5字符字符庫分為矢量型和點(diǎn)陣型兩種。在筆式繪圖儀上采用矢量型字符比較適合，矢量型字符庫采用矢量代碼序列表示字符的各個(gè)筆畫，輸出一個(gè)字符時(shí)，系統(tǒng)中的字符處理器解釋該字符的每個(gè)矢量代碼，輸出對(duì)應(yīng)的矢量，達(dá)到產(chǎn)生字符的目的。在終端顯示器上顯示字符一般采用點(diǎn)陣型字符庫。點(diǎn)陣型字符庫為每個(gè)字符定義一個(gè)字符掩膜，即表示該字符的象素圖案的一個(gè)點(diǎn)陣。3.5.1矢量字符為了建立一個(gè)矢量字符庫，必須對(duì)每個(gè)字符定義一個(gè)矢量代碼序列，下面以AutoCAD系統(tǒng)使用的矢量字符來說明。在AutoCAD中，使用一種稱為形（shape）的圖形實(shí)體來定義西文字符、漢字甚至一些簡單的圖形。形定義中使用直線和圓弧作為基本筆劃。每個(gè)形的定義包括一個(gè)標(biāo)題行和若干個(gè)描述行：*＜形編號(hào)＞，＜字節(jié)數(shù)＞，＜形名稱＞＜字節(jié)1＞＜字節(jié)2＞，…，0標(biāo)題行中，形編號(hào)是1到255的整數(shù)值。字節(jié)數(shù)表示形定義描述行中包括結(jié)束符0在內(nèi)的字節(jié)數(shù)目。形名稱用大寫字母才可以被調(diào)用，否則只作為形的一種解釋性信息，不存入存儲(chǔ)器，因而不占用存儲(chǔ)空間。描述行由若干個(gè)用逗號(hào)隔開的字節(jié)組成，并以0作為形定義的結(jié)束字節(jié)。帶有前綴0的字節(jié)是十六進(jìn)制。無前綴0的字節(jié)是十進(jìn)制。描述行中的每個(gè)字節(jié)包含矢量長度和方向兩種信息。字節(jié)的低四位表示矢量方向，高四位表示矢量長度。矢量的方向編碼如圖所示。注意，所有矢量都具有“相同“的長度，即不同方向的矢量的長度不一樣。例如，45方向的矢量一個(gè)單位長相當(dāng)于水平方向的2單位長。3.5.1矢量字符圖所示的二極管符號(hào)的形定義為：*133，11，DIODE040，044，04C，042，04C，040，048，04C，046，04C，0形描述的第一個(gè)字節(jié)040中，最高位0表示本字節(jié)為十六進(jìn)制數(shù)。后面兩位數(shù)4和0分別表示字節(jié)的高四位和低四位。高四位的4表示矢量長度為4，低四位的0表示矢量方向?yàn)樗较蛴曳较颉?.5.1矢量字符3.5.2點(diǎn)陣字符在點(diǎn)陣字符庫中，每個(gè)字符都定義成一個(gè)字符掩膜的矩陣。矩陣中的每個(gè)元素都是一位二進(jìn)制數(shù)。該位為1時(shí)，表示字符的筆劃經(jīng)過此位，對(duì)應(yīng)于此位的象素應(yīng)置為字符顏色；該位為0時(shí)，表示字符的筆劃不經(jīng)過此位置，對(duì)應(yīng)此位的象素應(yīng)置為背景色（若當(dāng)前的寫方式是“替換“方式）或不改變（若當(dāng)前寫方式是“與“方式）。一般認(rèn)為定義西文字符的掩膜矩陣尺寸應(yīng)不小于57，而定義漢字字符的掩膜矩陣尺寸應(yīng)不小于1616。在我國廣泛使用的微機(jī)漢字系統(tǒng)，如CCDOS等等，都采用1616點(diǎn)陣漢字作為顯示用字符，而在打印時(shí)，采用2424，4040甚至7272的點(diǎn)陣字符。一個(gè)57西文字符點(diǎn)陣包括35個(gè)點(diǎn)，需要35