《计算机图形学》课程设计-简单几何体的消隐算法实现.doc

课程名称：计算机图形学论文题目：简单几何体的消隐算法实现教学部： 年 级： 班 级： 学 号： 姓 名： 简单几何体的消隐算法实现摘 要：用计算机生成三维物体的真实图形是计算机图形学研究的重要内容。真实图形在仿真模拟、几何造型、广告影视、指挥控制和科学计算的可视化等许多领域都有广泛应用。经过消隐得到的投影图称为物体的真实图形。较常用的消隐算法有画家算法、z-buffer算法及其它一些改进算法。消隐算法从算法基本思想、算法描述和算法步骤等方面对画家算法、z-buffer算法和其它改进算法进行了分析,并得出了它们相关的特点。并在vc+中实现了z-buffer算法和区域子分割算法。关键词：z-buffer算法；背面消除法；消隐算法近年来，产生真实的虚拟环境是计算机图形学孜孜以求的目标。在虚拟对象或场景的创建中要用到许多综合处理过程，每一种都非常令人感兴趣也非常重要。计算机辅助设计、科学可视化、模拟训练、医疗成像、娱乐、广告等等，所有的这些，都要依赖于当今最前沿的计算机图形技术。伴随着计算机硬件、软件的飞速发展，计算机图形学技术也得到了质的飞跃。特别是面向对象技术和多媒体技术取得的成功，使得图形学成为计算机软件业中一个重要的分支。而程序设计方法、数据库系统和人工智能等新技术渗入到计算机图形学领域，又为计算机图形学提供了更加宽阔的发展空间和强劲动力。计算机图形学是研究通过计算机将数据转换成图形，并在专用显示设备上显示的原理、方法和技术的学科。主要介绍了计算机图形系统的基本知识，图形生成与显示的算法，图形的表示与图形的数据结构，图形的几何变换与投影变换，图形的裁剪技术，图形消隐处理，真实感图形的生成等内容。面消隐作为图形学中一个分支是本文的一个重要的研究内容。一 图形学中的面消隐概述 （一）面消隐的基本概念由于屏幕上的一些图元被另一些图元挡住所造成的。例如，当需要描绘一个由多边形面组成的三维物体时，那么它的一部分必然要被挡住，要在屏幕上显示的必须是可见的东西。打个比方，对于一个立方体，无论从哪个方向进行透视处理，最多只能看到其中的三个面。这样，就要想出一种方法来决定哪些面是所能看到的。 如果使用从屏幕到世界的视处理方法，那么很自然的就能保证只有图元上正确的部分才显示在屏幕上。在这种视处理中，可见性在屏幕的每一个像素上进行判断。从人眼发出一条射线，穿过一个给定的像素，那么首先与这条射线相交的表面在这一个像素上就是可见的。从这个表面反射的光线能够进入我们的眼睛。 用计算机生成三维物体的真实图形，是计算机图形学研究的重要内容。真实图形在仿真模拟、几何造型、广告影视、指挥控制和科学计算的可视化。等许多领域都有广泛应用。在用显示设备描述物体的图形时，必须把三维信息经过某种投影变换，在二维的显示表面上绘制出来。由于投影变换失去了深度信息，往往导致图形的二义性。要消除二义性，就必须在绘制时消除被遮挡的不可见的线或面，习惯上称作消除隐藏线和隐藏面，或简称为消隐。经过消隐得到的投影图称为物体的真实图形。消隐算法是把线框图变成实体图必要的算法。通过看相关的报道知道，地面勘测卫星，气象卫星等要不断的向地面的工作站发送图片资料来帮助技术人员进行研究。而那个量是非常庞大的，因而接收到图像时往往是已经过压缩和消隐后得到的图片。由于最普通的图元就是多边形，所以讨论的许多技术都是只针对多边形模型的。由此将重点讨论用于多边形地形、体素模型的一些技术，为了能够更深入的了解消隐有关的基本知识，做了如下的一些介绍和研究。（二） 常用的面消隐算法面消隐是计算机生成三维物体的真实图形的重要内容，最常用最基本的消隐算法有画家算法，平面公式法，背面消除法，径向预排序法，z-buffer算法。它们的基础都是背面消隐原理，所谓背面消隐原理， 即相对观察点来说朝向后面的物体表面是 不可见的，应被隐藏。二 简单几何体的消隐算法（一） 画家算法1算法的基本思想画家算法（也称为深度排序方法）比较适合于处理简单多面体的消隐问题其主要思想是将多面体要显示的各个面按照距离视点的远近进行排序，如果有相互部分遮挡的情况，则按照交线将其分成更小的面再进行排序，同时将排序的结果放置在一个表中当要显示这个多面体时，就按照这个表的顺序，也就是按照与视点的距离由远及近地依次显示各个多边形面这样如果某些面之间有重叠，也只可能是离视点较近的面遮住较远的面，从而就自然而然地解决了消隐的问题，就象是画家在画油画时一般先画背景，然后再画中间的景物。2 算法过程的描述画家算法是比较适合于处理简单多面体的消隐问题，具体过程描述如下： step1:将屏幕设成背景色step2:把要画的物体（多边形）按其离开视点的从远到近排序。由此构成深度优先级表。然后从远到近画物体（多边形），近的就因为优先级高而覆盖远的多边形。由此可消隐。3 多边形优先级的考虑画家算法是按照与视点的距离由远及近地依次显示各个多边形面，所以多边形优先级的判定是很重要的。判定过程具体描述如下：step1:首先对一个简单的画面，如图3-1（a）所示可以直接建立一个确定的深度优先表，排序可以一次完成，不会有任何的歧义。例如，多边形可按其最大或最小值排序，都可以很容易地把它们按深度大小分开。step2:但是，当画面略微复杂一点，如图3-1（b）所示，却无法按简单的z向排序建立确定的深度优先表，以确定每一个多边形的优先级。例如，若按最小z坐标值（zmin）对p、q排序，则在深度优先表中，p应排在q之前，如按此顺序将p、q写入帧缓冲器，则q将部分地遮挡p。但实际上是p部分地遮挡q。如果按最大z坐标值（zmax）对p、q排序，同样也不能得到正确的消隐结果。（二） 平 面 公 式 法 根据解析几何原理，通过标准的平面方程可以判断给定点是在平面的正面还是背面。平面公式法利用此原理来判断观察点位于物体表面的哪一面，如位于背面一侧 ，则表面不可见，应被消隐；反之则可见。 对物体得任意表面，可将其划分为若干个平面，在根据平面上任意三点的坐标可以求得其平面方程。标准得平面方程为 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，则平面不可见，应被隐藏； d 0，则物体表面是可见的朝向观察点的面；如果，则物体表面是不可见的背向观察点的面，应被消隐。 设为向量和之间的夹角，视向量的长度为线段op 的长度|op|，则根据向量点积的定义可知=|op|cos 。如果 0，则cos 0（ 即 0）； 反之，如果，则cos 0（ 即 ）。 因此，背面消除法的判据简化为： cos 0，则物体表面不可见，应被消隐；cos 0则物体表面可见，应被画出。 根据面法向量的定义可知，在平面上按逆时针方向选取p1（x1, y1, z1）、p2（x2, y2, z2）、p3（x3, y3, z3）三点，则经过投影变化后，视向量与z轴是平行的，因此向量和之间的夹角即为z 轴与向量的夹角，所以由 于|0， 所以cos 的正负取决于c，因此背面消除法的判据转化为：c 0，则物体表面不可见，应被消隐；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+下的实现void cmyview:project(float x, float y, float z)/ 此函数求点的平行投影和透视投影坐标值 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;void cmyview:wlineto(float x, float y, float z,cdc*pdc)/ 用三维点坐标直接从当前点画线到一点的函数 project(x, y, z); / 将三维点作投影 xscreen = floor(0.5 + xproj * scale +150); / 圆整 yscreen = floor(0.5 + 100 - yproj); / 圆整 pdc-lineto(xscreen, yscreen); / 画线到一点void cmyview:wmoveto(float x, float y, float z,cdc*pdc)/ 三维坐标下直接将当前点移动到某点的函数 project (x, y, z); / 将三维点作投影 xscreen = floor(0.5 + xproj * scale + 150); / 圆整 yscreen = floor(0.5 + 100 - yproj); / 圆整 pdc-moveto(xscreen, yscreen); /移动到某点void cmyview:visionvector(int st1) /* 该函数用于求观察方向矢量 st1 is the first point of a face. */ v1=o1-stst11; v2=o2-stst12; v3=o3-stst13;void cmyview:normalvector(int st1, int st2, int st3)/ 此函数用表面三个顶点调用求该表面的法矢 / st_i is the i_th point of a face. float p1, p2, p3, q1, q2, q3; / 求一个向量p1 = stst21 - stst11;p2 = stst22 - stst12;p3 = stst23 - stst13; / 求另一个向量q1 = stst31 - stst11;q2 = stst32 - stst12;q3 = stst33 - stst13; /用向量积求法向量n1 = p2 * q3 - q2 * p3;n2 = p3 * q1 - q3 * p1;n3 = p1 * q2 - q1 * p2;float cmyview:scaleproduct(float v1, float v2, float v3, float n1, float n2, float n3)/ 此函数用于求观察方向矢量与表面法矢的数量积 float sproduct;sproduct = v1 * n1 + v2 * n2 + v3 * n3;return(sproduct);void cmyview:drawface(cdc*pdc)/ 画出立体上的平面 int s, ns, no; float x, y, z, x0, y0, z0; ns = fcf0; for ( s = 1; sselectobject(&pen1); for ( f = 1; f 0 ) / 判断数量积正否 pdc-selectobject(&pen1); drawface(pdc); / 数量积大于零，表面可见，画出此表面 pdc-selectobject(poldpen); releasedc(pdc);void cmyview:visionpoint()/ 此函数用于给出视点位置/ 投影时初始值即正弦值和余弦值及其乘积的计算、赋值float th, 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;void cmyview:mydraw()redrawwindow();readvertics();readfaces();/ 绘出透视投影下的凸多面体图形visionpoint(); / 给出视点位置 drawobject(); / 画出立体的图形/ cmyview message handlersvoid cmyview:onkeydown(uint nchar, uint nrepcnt, uint nflags) /此函数用来利用上下左右键移动视点角度位置,c键切换投影类型.switch(nchar)case vk_up:/上下左右键选择phi=phi-incang;mydraw();break;case vk_down:phi=phi+incang;mydraw();break;case vk_right:theta=theta+incang;mydraw();break;case vk_left:theta=theta-incang;mydraw();break;default:break;void cmyview:ontumianti() rol = 600.0;s=1;theta = 60;phi = 135;de = 1000;mydraw();cdc*pdc=getdc();pdc-textout(10,10,按下键盘上的“上”、“下”、“左”、“右”箭头可从各方位观看图形);releasedc(pdc);void cmyview:onyuanjin() / todo: add your command handler code hereredrawwindow();cclientdc *pdc=new cclientdc(this);cpen *pen1=new cpen(ps_solid,1,rgb(0,0xff,0);cpen *pen2=new cpen(ps_solid,1,rgb(255,0,0);cpen *oldpen=pdc-selectobject(pen1);cbrush brush;brush.createsolidbrush(rgb(0,0,0);cbrush *oldbrush=(cbrush*)pdc-selectobject(&brush);int flag,col,r,ww,k1,k2,r1,r2,n,d,m,p,osw,osh,left,top;int xs1,xs2,xs3,xs4,ys1,ys2,ys3,ys4,i,j,lastp;double x,y,z,cx,cy,cz,thx,th1,th3,yw,zw,xw,thy,th,th2;double pi,ed,od,eh,zzw,ppw;double xs5017,zs5017,ys5017,zc5017,x1,y1;int zz850,pp850;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