几何体的消隐算法实现

课程名称：《计算机图形学》教学部：年级：班级：学号：姓名：简单几何体的消隐算法实现他(二)平面公式法根据解析几何原理，通过标准的平面方程可以判断给定点是在平面的正面还是背面。平面公式法利用此原理来判断观察点位于物体表面的哪一面，如位于背面一侧，则表面不可见，应被消隐；反之则可见。对物体得任意表面，可将其划分为若十个平面，在根据平面上任意三点的坐标可以求得其平面方程。标准得平面方程为Ax+By+Cz+D=0;其中A、B、C、D为决定平面得常数。如果(x1,y1,z1)、(x2,y2,z2)、(x3,y3,z3)为平面上已知得三点坐标，则可求得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);设观察点坐标为(x,y,z)，如果Ax+By+Cz+D=0,则观察点(x,y,z)位于平面上；Ax+By+Cz+D>0则观察点(x,y,z)位于平面背面一侧，平面不可见，应被隐藏；Ax+By+Cz+D<0，则观察点(x,y,z)位于平面正面一侧，平面是可见面，应被画出。通过对物体进行适当旋转和平移后，可将物体变换到以观察点为原点得观察坐标系中，如果在观察坐标系中求得了平面得方程Ax+By+Cz+D=0，将观察点坐标(0，0，0)代入上面得判断准则，则可得出如下得简单判据：D>0，则平面不可见，应被隐藏；D<0，则平面是可见面，应被画出。平面公式法算法简便，是在实际中使用最频繁得消隐算法。但它只能用于凸面体得消隐，而不适用于凹面体消隐。背面消除法背面消除法是直接运用背面消隐原理的消隐算法。在数学上，物体表面的法向量即是表面的朝向，因此，法向量方向背向观察点的物体表面都应被消隐。表面的法向量是否背向观察点可以通过表面法向量与视向量的点积来决定。如图1所示，设经坐标变换后，坐标系的原点O即是观察点，空间中任意平面ABC的法向量为，法向量为与平面的交点为P，则从向量OP即是平面ABC的视向量。如果>0，则物体表面是可见的朝向观察点的面；如果，则物体表面是不可见的背向观察点的面，应被消隐。设。为向量和之间的夹角，视向量的长度为线段OP的长度|OP|，则根据向量点积的定义可知=|OP|||cosM如果>0,则cos0>0（即〉0>0）；反之，如果，则cos00（即0）。因此，背面消除法的判据简化为：cos00,则物体表面不可见，应被消隐；cos0>0则物体表面可见，应被画出。根据面法向量的定义可知，在平面上按逆时针方向选取P1（x1,y1,z1）、P2（x2,y2,z2）、P3（x3,y3,z3）三点，则经过投影变化后，视向量与Z轴是平行的，因此向量和之间的夹角0即为Z轴与向量的夹角，所以由于||>0，所以cos0的正负取决于C，因此背面消除法的判据转化为：C0，则物体表面不可见，应被消隐；C>0，则物体表面可见，应被画出。（四） 径向预排序法径向预排序法根据物体在三维坐标系XY平面中的角位置来判断哪些物体挡住了其它物体，物体的哪些表面挡住了其它表面。对具有相同角位置的物体或表面，与观察点较近的将挡住较远的。径向预排序法示例径向预排序法消隐的要点是先对物体及物体的表面进行由远及近的排序对具有相同角位置的物体或表面，先画较远的，后画较近的，这样如果较近的物体或表面挡住了较远的物体或表面，则被遮挡的部分被覆盖而实现消隐。但对具有不同角位置的物体或表面，先画哪一个可根据需要来决定。如果存在凹面物体的消隐，一般应先画物体中心部分，再画物体的两侧，以正确地表现互相重叠的凹面模型。径向预排序法可以对任意形状的物体进行消隐处理。但需要预先知道观察角度，并根据角位置对物体的画图顺序预先排序。而且构造模型的编码受到这种排序的限制，模型不能进行旋转变换。（五） 径向排序法径向排序法是对径向预排序法的改进算法，使得构造模型的编码能根据观察角度的变化，来自动调整物体或表面的远近顺序即画图顺序，以实现对模型的旋转变换，以便能从不同的角度来观察物体。算法需要检测旋转变换的角度，并随角度的变化而调整物体或表面的远近顺序。（六） Z缓冲区法z缓冲区法首先建立一个大的缓冲区，用来存储三维物体沿Z轴透视投影而得到的二维图形的所有象素的值，因此叫做Z缓冲区。Z缓冲区的单元个数与屏幕上象素点的个数相同，也和帧缓冲区的单元个数相同，而且它们之间是一一对应的Z缓冲区每个单元的大小取决于图形在观察坐标系中Z方向的变化范围。缓区的每个单元的值是对应象素点所对应的物体表面点坐标值。利Z缓冲区法进行消隐和造型的过程就是对屏幕中每一点进行判断并给帧缓冲区Z缓冲区中相应单元进行赋值的过程。现用形式化语言描述该算法如下:Z缓冲区消隐算法（1） 将帧缓冲区各单元的值置为背景色值；2） 将Z缓冲区各单元的值置为Z坐标可能出现的最大值；3） 循环：对每一物体（循环：对物体每一面的每一点（x,y,z）（i） 对（x,y,z）做透视投影变换，得到变换后的X、Y坐标（x*,y*）；ii） 如果Z缓冲区中（x*,y*）对应单元的值小于z，则（a） 将Z缓冲区中（x*,y*）对应单元的值置为z;b） 将帧缓冲区中（x*,y*）对应单元的值置为点（x,y,z）的属性值（通常是亮度、颜色值或颜色查找表的索引值）；}iii） 如果Z缓冲区中（x*,y*）对应单元的值大于z，则（a） 说明目前帧缓冲区中（x*,y*）对应单元的所表示的物体上点比点（x,y,z）更接近观察点，即点（x,y,z）应被消隐；b） 将Z缓冲区和帧缓冲区中（x*,y*）对应单元的值均保持不变；}}}4） 循环：对屏幕上每一点（x*,y*）根据帧缓冲区中（x*,y*）对应单元的值画出象素点。}Z缓冲区消隐算法简单、可靠，而且消隐和表现效果很好。但需要的内存容量大，运算复杂，费时。三消隐算法在VC++下的实现voidCMyView::Project（floatX,floatY,floatZ）//此函数求点的平行投影和透视投影坐标值(XObs=-X*Aux1+Y*Aux3;YObs=-X*Aux5-Y*Aux6+Z*Aux4;//求透视投影坐标值ZObs=-X*Aux7-Y*Aux8-Z*Aux2+Rol;XProj=DE*XObs/ZObs;YProj=DE*YObs/ZObs;}voidCMyView::WLineTo(floatX,floatY,floatZ,CDC*pDC)//用三维点坐标直接从当前点画线到一点的函数(Project(X,Y,Z);〃将三维点作投影XScreen=floor(0.5+XProj*Scale+150);//圆整YScreen=floor(0.5+100-YProj);//圆整pDC->LineTo(XScreen,YScreen);//画线到一点}voidCMyView::WMoveTo(floatX,floatY,floatZ,CDC*pDC)//三维坐标下直接将当前点移动到某点的函数(Project(X,Y,Z);//将三维点作投影XScreen=floor(0.5+XProj*Scale+150);//圆整YScreen=floor(0.5+100-YProj);//圆整pDC->MoveTo(XScreen,YScreen);//移动到某点}voidCMyView::VisionVector(intSt1)/*该函数用于求观察方向矢量St1isthefirstpointofaface.*/v1=O1-St[St1][1];v2=O2-St[St1][2];v3=O3-St[St1][3];}voidCMyView::NormalVector(intSt1,intSt2,intSt3)//此函数用表面三个顶点调用求该表面的法矢//St_iisthei_thpointofaface.(floatP1,P2,P3,Q1,Q2,Q3;//求一个向量P1=St[St2][1]-St[St1][1];P2=St[St2][2]-St[St1][2];P3=St[St2][3]-St[St1][3];//求另一个向量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)//此函数用于求观察方向矢量与表面法矢的数量积(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()//此函数用于绘出消隐立体图(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)//判断数量积正否(pDC->SelectObject(&pen1);DrawFace(pDC);//数量积大于零，表面可见，画出此表面}}pDC->SelectObject(pOldPen);ReleaseDC(pDC);}voidCMyView::VisionPoint()//此函数用于给出视点位置(//投影时初始值即正弦值和余弦值及其乘积的计算、赋值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;//给出视点位置O1=Rol*Aux7;O2=Rol*Aux8;O3=Rol*Aux2;}voidCMyView::Mydraw()(RedrawWindow();ReadVertics();ReadFaces();//绘出透视投影下的凸多面体图形VisionPoint();//给出视点位置DrawObject();//画出立体的图形}//CMyViewmessagehandlersvoidCMyView::OnKeyDown(UINTnChar,UINTnRepCnt,UINTnFlags)(//此函数用来利用上下左右键移动视点角度位置,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;〃计算顶点坐标值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