幾何體的消隱算法實(shí)現(xiàn)

課程名稱：《計(jì)算機(jī)圖形學(xué)》教學(xué)部：年級(jí)：班級(jí)：學(xué)號(hào)：姓名：簡單幾何體的消隱算法實(shí)現(xiàn)他(二)平面公式法根據(jù)解析幾何原理，通過標(biāo)準(zhǔn)的平面方程可以判斷給定點(diǎn)是在平面的正面還是背面。平面公式法利用此原理來判斷觀察點(diǎn)位于物體表面的哪一面，如位于背面一側(cè)，則表面不可見，應(yīng)被消隱；反之則可見。對(duì)物體得任意表面，可將其劃分為若十個(gè)平面，在根據(jù)平面上任意三點(diǎn)的坐標(biāo)可以求得其平面方程。標(biāo)準(zhǔn)得平面方程為Ax+By+Cz+D=0;其中A、B、C、D為決定平面得常數(shù)。如果(x1,y1,z1)、(x2,y2,z2)、(x3,y3,z3)為平面上已知得三點(diǎn)坐標(biāo)，則可求得A、B、C、D如下：(A=y1(x2-x3)+y2(z3-z1)+y3(z1-z2);B=z1(x2-x3)+z2(x3-x1)+z3(x1-x2);C=x1(y2-y3)+x2(y3-y1)+x3(y1-y2);D=-x1(y2z3-y3z2)-x2(y3z1-y1z3)-x3(y1z2-y2z1);設(shè)觀察點(diǎn)坐標(biāo)為(x,y,z)，如果Ax+By+Cz+D=0,則觀察點(diǎn)(x,y,z)位于平面上；Ax+By+Cz+D>0則觀察點(diǎn)(x,y,z)位于平面背面一側(cè)，平面不可見，應(yīng)被隱藏；Ax+By+Cz+D<0，則觀察點(diǎn)(x,y,z)位于平面正面一側(cè)，平面是可見面，應(yīng)被畫出。通過對(duì)物體進(jìn)行適當(dāng)旋轉(zhuǎn)和平移后，可將物體變換到以觀察點(diǎn)為原點(diǎn)得觀察坐標(biāo)系中，如果在觀察坐標(biāo)系中求得了平面得方程Ax+By+Cz+D=0，將觀察點(diǎn)坐標(biāo)(0，0，0)代入上面得判斷準(zhǔn)則，則可得出如下得簡單判據(jù)：D>0，則平面不可見，應(yīng)被隱藏；D<0，則平面是可見面，應(yīng)被畫出。平面公式法算法簡便，是在實(shí)際中使用最頻繁得消隱算法。但它只能用于凸面體得消隱，而不適用于凹面體消隱。背面消除法背面消除法是直接運(yùn)用背面消隱原理的消隱算法。在數(shù)學(xué)上，物體表面的法向量即是表面的朝向，因此，法向量方向背向觀察點(diǎn)的物體表面都應(yīng)被消隱。表面的法向量是否背向觀察點(diǎn)可以通過表面法向量與視向量的點(diǎn)積來決定。如圖1所示，設(shè)經(jīng)坐標(biāo)變換后，坐標(biāo)系的原點(diǎn)O即是觀察點(diǎn)，空間中任意平面ABC的法向量為，法向量為與平面的交點(diǎn)為P，則從向量OP即是平面ABC的視向量。如果>0，則物體表面是可見的朝向觀察點(diǎn)的面；如果，則物體表面是不可見的背向觀察點(diǎn)的面，應(yīng)被消隱。設(shè)。為向量和之間的夾角，視向量的長度為線段OP的長度|OP|，則根據(jù)向量點(diǎn)積的定義可知=|OP|||cosM如果>0,則cos0>0（即〉0>0）；反之，如果，則cos00（即0）。因此，背面消除法的判據(jù)簡化為：cos00,則物體表面不可見，應(yīng)被消隱；cos0>0則物體表面可見，應(yīng)被畫出。根據(jù)面法向量的定義可知，在平面上按逆時(shí)針方向選取P1（x1,y1,z1）、P2（x2,y2,z2）、P3（x3,y3,z3）三點(diǎn)，則經(jīng)過投影變化后，視向量與Z軸是平行的，因此向量和之間的夾角0即為Z軸與向量的夾角，所以由于||>0，所以cos0的正負(fù)取決于C，因此背面消除法的判據(jù)轉(zhuǎn)化為：C0，則物體表面不可見，應(yīng)被消隱；C>0，則物體表面可見，應(yīng)被畫出。（四） 徑向預(yù)排序法徑向預(yù)排序法根據(jù)物體在三維坐標(biāo)系XY平面中的角位置來判斷哪些物體擋住了其它物體，物體的哪些表面擋住了其它表面。對(duì)具有相同角位置的物體或表面，與觀察點(diǎn)較近的將擋住較遠(yuǎn)的。徑向預(yù)排序法示例徑向預(yù)排序法消隱的要點(diǎn)是先對(duì)物體及物體的表面進(jìn)行由遠(yuǎn)及近的排序?qū)哂邢嗤俏恢玫奈矬w或表面，先畫較遠(yuǎn)的，后畫較近的，這樣如果較近的物體或表面擋住了較遠(yuǎn)的物體或表面，則被遮擋的部分被覆蓋而實(shí)現(xiàn)消隱。但對(duì)具有不同角位置的物體或表面，先畫哪一個(gè)可根據(jù)需要來決定。如果存在凹面物體的消隱，一般應(yīng)先畫物體中心部分，再畫物體的兩側(cè)，以正確地表現(xiàn)互相重疊的凹面模型。徑向預(yù)排序法可以對(duì)任意形狀的物體進(jìn)行消隱處理。但需要預(yù)先知道觀察角度，并根據(jù)角位置對(duì)物體的畫圖順序預(yù)先排序。而且構(gòu)造模型的編碼受到這種排序的限制，模型不能進(jìn)行旋轉(zhuǎn)變換。（五） 徑向排序法徑向排序法是對(duì)徑向預(yù)排序法的改進(jìn)算法，使得構(gòu)造模型的編碼能根據(jù)觀察角度的變化，來自動(dòng)調(diào)整物體或表面的遠(yuǎn)近順序即畫圖順序，以實(shí)現(xiàn)對(duì)模型的旋轉(zhuǎn)變換，以便能從不同的角度來觀察物體。算法需要檢測旋轉(zhuǎn)變換的角度，并隨角度的變化而調(diào)整物體或表面的遠(yuǎn)近順序。（六） Z緩沖區(qū)法z緩沖區(qū)法首先建立一個(gè)大的緩沖區(qū)，用來存儲(chǔ)三維物體沿Z軸透視投影而得到的二維圖形的所有象素的值，因此叫做Z緩沖區(qū)。Z緩沖區(qū)的單元個(gè)數(shù)與屏幕上象素點(diǎn)的個(gè)數(shù)相同，也和幀緩沖區(qū)的單元個(gè)數(shù)相同，而且它們之間是一一對(duì)應(yīng)的Z緩沖區(qū)每個(gè)單元的大小取決于圖形在觀察坐標(biāo)系中Z方向的變化范圍。緩區(qū)的每個(gè)單元的值是對(duì)應(yīng)象素點(diǎn)所對(duì)應(yīng)的物體表面點(diǎn)坐標(biāo)值。利Z緩沖區(qū)法進(jìn)行消隱和造型的過程就是對(duì)屏幕中每一點(diǎn)進(jìn)行判斷并給幀緩沖區(qū)Z緩沖區(qū)中相應(yīng)單元進(jìn)行賦值的過程?，F(xiàn)用形式化語言描述該算法如下:Z緩沖區(qū)消隱算法（1） 將幀緩沖區(qū)各單元的值置為背景色值；2） 將Z緩沖區(qū)各單元的值置為Z坐標(biāo)可能出現(xiàn)的最大值；3） 循環(huán)：對(duì)每一物體（循環(huán)：對(duì)物體每一面的每一點(diǎn)（x,y,z）（i） 對(duì)（x,y,z）做透視投影變換，得到變換后的X、Y坐標(biāo)（x*,y*）；ii） 如果Z緩沖區(qū)中（x*,y*）對(duì)應(yīng)單元的值小于z，則（a） 將Z緩沖區(qū)中（x*,y*）對(duì)應(yīng)單元的值置為z;b） 將幀緩沖區(qū)中（x*,y*）對(duì)應(yīng)單元的值置為點(diǎn)（x,y,z）的屬性值（通常是亮度、顏色值或顏色查找表的索引值）；}iii） 如果Z緩沖區(qū)中（x*,y*）對(duì)應(yīng)單元的值大于z，則（a） 說明目前幀緩沖區(qū)中（x*,y*）對(duì)應(yīng)單元的所表示的物體上點(diǎn)比點(diǎn)（x,y,z）更接近觀察點(diǎn)，即點(diǎn)（x,y,z）應(yīng)被消隱；b） 將Z緩沖區(qū)和幀緩沖區(qū)中（x*,y*）對(duì)應(yīng)單元的值均保持不變；}}}4） 循環(huán)：對(duì)屏幕上每一點(diǎn)（x*,y*）根據(jù)幀緩沖區(qū)中（x*,y*）對(duì)應(yīng)單元的值畫出象素點(diǎn)。}Z緩沖區(qū)消隱算法簡單、可靠，而且消隱和表現(xiàn)效果很好。但需要的內(nèi)存容量大，運(yùn)算復(fù)雜，費(fèi)時(shí)。三消隱算法在VC++下的實(shí)現(xiàn)voidCMyView::Project（floatX,floatY,floatZ）//此函數(shù)求點(diǎn)的平行投影和透視投影坐標(biāo)值(XObs=-X*Aux1+Y*Aux3;YObs=-X*Aux5-Y*Aux6+Z*Aux4;//求透視投影坐標(biāo)值ZObs=-X*Aux7-Y*Aux8-Z*Aux2+Rol;XProj=DE*XObs/ZObs;YProj=DE*YObs/ZObs;}voidCMyView::WLineTo(floatX,floatY,floatZ,CDC*pDC)//用三維點(diǎn)坐標(biāo)直接從當(dāng)前點(diǎn)畫線到一點(diǎn)的函數(shù)(Project(X,Y,Z);〃將三維點(diǎn)作投影XScreen=floor(0.5+XProj*Scale+150);//圓整YScreen=floor(0.5+100-YProj);//圓整pDC->LineTo(XScreen,YScreen);//畫線到一點(diǎn)}voidCMyView::WMoveTo(floatX,floatY,floatZ,CDC*pDC)//三維坐標(biāo)下直接將當(dāng)前點(diǎn)移動(dòng)到某點(diǎn)的函數(shù)(Project(X,Y,Z);//將三維點(diǎn)作投影XScreen=floor(0.5+XProj*Scale+150);//圓整YScreen=floor(0.5+100-YProj);//圓整pDC->MoveTo(XScreen,YScreen);//移動(dòng)到某點(diǎn)}voidCMyView::VisionVector(intSt1)/*該函數(shù)用于求觀察方向矢量St1isthefirstpointofaface.*/v1=O1-St[St1][1];v2=O2-St[St1][2];v3=O3-St[St1][3];}voidCMyView::NormalVector(intSt1,intSt2,intSt3)//此函數(shù)用表面三個(gè)頂點(diǎn)調(diào)用求該表面的法矢//St_iisthei_thpointofaface.(floatP1,P2,P3,Q1,Q2,Q3;//求一個(gè)向量P1=St[St2][1]-St[St1][1];P2=St[St2][2]-St[St1][2];P3=St[St2][3]-St[St1][3];//求另一個(gè)向量Q1=St[St3][1]-St[St1][1];Q2=St[St3][2]-St[St1][2];Q3=St[St3][3]-St[St1][3];〃用向量積求法向量n1=P2*Q3-Q2*P3;n2=P3*Q1-Q3*P1;n3=P1*Q2-Q1*P2;}floatCMyView::ScaleProduct(floatv1,floatv2,floatv3,floatn1,floatn2,floatn3)//此函數(shù)用于求觀察方向矢量與表面法矢的數(shù)量積(floatSProduct;SProduct=v1*n1+v2*n2+v3*n3;return(SProduct);}voidCMyView::DrawFace(CDC*pDC)//畫出立體上的平面(intS,NS,No;floatX,Y,Z,X0,Y0,Z0;NS=Fc[F][0];for(S=1;S<=NS;S++)(No=Fc[F][S];X=St[No][1];Y=St[No][2];Z=St[No][3];if(S==1)(WMoveTo(X,Y,Z,pDC);X0=X;Y0=Y;Z0=Z;}elseWLineTo(X,Y,Z,pDC);}WLineTo(X0,Y0,Z0,pDC);}voidCMyView::DrawObject()//此函數(shù)用于繪出消隱立體圖(intSt1,St2,St3;CDC*pDC二GetDC();CPenpen1(PS_SOLID,1,(COLORREF)1),pen2(PS_DOT,1,(COLORREF)1);CPen*pOldPen=pDC->SelectObject(&pen1);for(F=1;F<=NF;F++)(St1=Fc[F][1]; St2=Fc[F][2];St3=Fc[F][3];VisionVector(St1);//求觀察方向矢量NormalVector(St1,St2,St3);//求表面法矢if(ScaleProduct(v1,v2,v3,n1,n2,n3)>0)//判斷數(shù)量積正否(pDC->SelectObject(&pen1);DrawFace(pDC);//數(shù)量積大于零，表面可見，畫出此表面}}pDC->SelectObject(pOldPen);ReleaseDC(pDC);}voidCMyView::VisionPoint()//此函數(shù)用于給出視點(diǎn)位置(//投影時(shí)初始值即正弦值和余弦值及其乘積的計(jì)算、賦值floatTh,Ph;Th = 3.1415926 * Theta / 180;Ph = 3.1415926 * Phi / 180;Aux1 = sin(Th);Aux2 = sin(Ph);Aux3=cos(Th);Aux4=cos(Ph);Aux5=Aux3*Aux2;Aux6=Aux1*Aux2;Aux7=Aux3*Aux4;Aux8=Aux1*Aux4;//給出視點(diǎn)位置O1=Rol*Aux7;O2=Rol*Aux8;O3=Rol*Aux2;}voidCMyView::Mydraw()(RedrawWindow();ReadVertics();ReadFaces();//繪出透視投影下的凸多面體圖形VisionPoint();//給出視點(diǎn)位置DrawObject();//畫出立體的圖形}//CMyViewmessagehandlersvoidCMyView::OnKeyDown(UINTnChar,UINTnRepCnt,UINTnFlags)(//此函數(shù)用來利用上下左右鍵移動(dòng)視點(diǎn)角度位置,C鍵切換投影類型.switch(nChar)(caseVK_UP: //上下左右鍵選擇Phi二Phi-IncAng;Mydraw();break;caseVK_DOWN:Phi=Phi+IncAng;Mydraw();break;caseVK_RIGHT:Theta二Theta+IncAng;Mydraw();break;caseVK_LEFT:Theta二Theta-IncAng;Mydraw();break;default:break;}}voidCMyView::OnTumianti()(Rol=600.0;S=1;Theta=60;Phi=135;DE=1000;Mydraw();CDC*pDC二GetDC();pDC->TextOut(10,10,〃按下鍵盤上的“上”、“下”、“左”、“右”箭頭可從各方位觀看圖形")；ReleaseDC(pDC);}voidCMyView::OnYuanjin()( //TODO:AddyourcommandhandlercodehereRedrawWindow();CClientDC*pdc=newCClientDC(this);CPen*pen1=newCPen(PS_SOLID,1,RGB(0,0XFF,0));CPen*pen2二newCPen(PS_SOLID,1,RGB(255,0,0));CPen*OldPen=pdc->SelectObject(pen1);CBrushbrush;brush.CreateSolidBrush(RGB(0,0,0));CBrush*oldbrush=(CBrush*)pdc->SelectObject(&brush);intflag,col,r,ww,k1,k2,r1,r2,n,d,m,p,osw,osh,left,top;intxs1,xs2,xs3,xs4,ys1,ys2,ys3,ys4,i,j,lastp;doublex,y,z,cx,cy,cz,thx,th1,th3,yw,zw,xw,thy,th,th2;doublePI,ed,od,eh,zzw,ppw;doublexs[50][17],zs[50][17],ys[50][17],zc[50][17],x1,y1;intzz[850],pp[850];r1=100;r2=40;k1=20;k2=16;ed=1500;eh=0;od=0;n=0;PI=3.14159;th3=1;thx=0.9;〃計(jì)算頂點(diǎn)坐標(biāo)值for(d=-1;d<=1;d+=2)(for(th1=0;th1<=2*PI+0.1;th1+=2*PI/k1)( n=n+1;m=0;for(th2=0;th2<=2*PI+0.1;th2+=2*PI/k2)( m=m+1;x=r1+r2*cos(th2);y=r2*sin(th2);z=0;thy=th1;zw=z;xw=x;x=zw*cos(thy)-xw*sin(thy);z=zw*sin(thy)+xw*cos(thy);x=x+r1/2*d;if(d==1)(yw=y;zw=z;y=yw*cos(PI/2)-zw*sin(PI/2);z=yw*sin(PI/2)+zw*cos(PI/2);thy=th3;zw=z;xw=x;x=zw*cos(thy)-xw*sin(thy);z=zw*sin(thy)+xw*cos(thy);yw=y;zw=z;y=yw*cos(thx)-zw*sin(thx);z=yw*sin(thx)+zw*cos(thx);x=x*ed/(ed-od-z);y=(y*ed-eh*(od+z))/(ed-od-z);xs[n][m]=x;ys[n][m]=y;zs[n][m]=z;}flag=0;}flag=0;}p=0;for(n=1;n<=k1;n+=1)( for(m=1;m<=k2;m+=1)( zc[n][m]=int((zs[n][m]+zs[n+1][m+1])/2);zz[p]=zc[n][m];pp[p]=p;}}lastp二p-1;〃排序for(i=2;i<=lastp;i+=1)( for(j=i-1;j>=0;j+=-1)( if(zz[j]>zz[j+1])(zzw=zz[j];zz[j]=zz[j+1];zz[j+1]=zzw;ppw=pp[j];pp[j]=pp[j+1];pp[j+1]=ppw;}}}〃繪圖for(p=0;p<=lastp;p+=1)( n=int(pp[p]/k2)+1;m=pp[p]%k2+1;i