图形学实验七课件

1、贵州大学实验报告学院： 计信学院 专业：计科 班级：计科101姓名罗琳学号1008060016实验组无实验时间2013-4-29指导教师吴云成绩实验项目名称消隐实验目的掌握常用的裁减及消隐算法：直线、多边形的裁减；消除隐藏面算法：Roberts消隐算法、Z缓冲器算法、扫描线Z缓冲器算法、光线跟踪算法。实验要求分别实现一个直线裁减算法、多边形的裁减算法、面消隐算法实验原理Roberts消隐算法算法原理：Roberts消隐算法是在图像空间实现的消隐算法，数学处理严谨，计算量甚大。Roberts算法要求所有被显示的物体都是凸的，因此对凹体要先分割成许多个凸体的组合。此算法的基本步骤是：l 逐个的独立

2、的考虑每个物体自身，找出为其自身所遮挡的边和面；l 将每一物体上留下的边再与其它物体逐个的进行比较，以确定其是完全可见还是部分或全部被遮挡；l 确定由于物体之间的相互贯穿等原因，是否要形成新的显示边等。从而使被显示各物体更接近现实。下面先介绍一些用到的一些基本概念以及有关的数学方法。l 体矩阵：假设在三维空间中，一平面的方程表示为：ax+by+cz+d=0,令P=a,b,c,d，表示平面的系数向量；又令S=x,y,z,1，表示三维空间重点的其次坐标。上式改写为：S·PT=0。所以凸体可由平面方程系数组成的体矩阵表示：矩阵的每一列表示物体的对应平面方程的系数，其列数与物体的面数一致。由

3、于当PT是一平面系数时，-PT也是该平面的系数，因此为了计算的需要，Roberts算法规定：对平面多面体内部的任一点S0，要使得 S0·V=Q=q1,q2,q3,qn式中的每一个分量qi都不小于零(i=1,2,n)。适当选取物体内部一点S0，用以测试单调态平面系数的符号，使其满足Roberts算法的规定，这是本算法最基本的一步。平面系数的计算方法： 方法一：根据平面上的已知点，求解线性方程组。已知平面上不共线三点(x1,y1,z1)，(x2,y2,z2)，(x3,y3,z3)，得到规范方程组：写成矩阵形式为：记为：XC=D，解得平面方程系数为：C=X-1D 方法二：根据平面的法矢量和

4、平面上一已知点，求得平面系数。已知平面的法矢量为：n=ai+bj+ck，其中i，j，k分别为x，y，z方向的单位矢量，且又已知平面上一点(x1,y1,z1)。则平面方程是：  ax+by+cz+d=0，其中   d=-(ax1+by1+cz1) 方法三：采用Martin Newell方法，即最佳逼近法，计算任何平面多边形所在平面的精确方程或接近于平面的多边形的最佳逼近平面方程。假设给定n个点(xi,yi,zi)(i=1,2,n)，则平面系数可用于下式计算：其中：若in，则j=i+1，否则j=1。d可由下式求得：d=-(ax1+by1+cz1) 体矩阵的变换在消隐算

5、法执行之前，为了得到从一指定的试点以给定的观察方向来看所需要显示的物体，常常先要对物体进行三维坐标变换。因此，在变换确定之后，或给定了变换矩阵T以后，需要对每一个物体的体矩阵V作一个相应的变换，得到变换后的体矩阵VT。同时，还要对物体的顶点齐次坐标矩阵B作一个相应的变换，得到变换后的顶点齐次坐标矩阵BT。有两种常用的计算VT的方法： 方法一：假设B与BT分别为在体矩阵变换前后的物体顶点齐次坐标构成的矩阵，则 BT=BT因为有XC=D，所以可得到该物体原各平面的方程为： BV=D 其中：D为零矩阵。同样，变换后的平面方程也可表示为：BTVT=D并且：BTVT=BV 代入到BT=BT，方程两边消去

6、B并左乘T-1，得到：VT=T-1V;所以，变换后的体矩阵是由原来的体矩阵左乘变换矩阵的逆矩阵而得到的。 方法二：假设原先并未计算形体矩阵V，也不希望计算T的逆矩阵，则可光计算：BT=BT,然后用变换后的物体顶点坐标BT，按照前面介绍的Martin Newell方法，直接计算变换后的体矩阵VT，两种方法所得结果完全一致。 视方向朝向z轴负向无穷远处 视方向朝向z轴正向无穷远处 结果图 自消隐方法:自消隐是对物体自身所遮挡的面(自隐面)和边(自隐边)的消除。对于不同的视点及视方向，既是对同一个物体来说，也会产生不同的自隐面和自隐边。因此自隐面和自隐边不仅取决于物体的形状，而且与视点方向相关。假设

7、视点位于z的负无穷远处，视方向为z轴的正向，即视方向朝z轴正向无穷远处，在齐次坐标系中，该方向矢量为：E=0,0,1,0显然，若视方向E和体矩阵VT的乘积中有负的元素，则E在这此元素对应的面与形体相对的另一侧，而这正说明这些面被物体自身所遮挡。所以利用 E·VT=w1,w2,wn(表示视线与表面内法线矢量夹角关系)寻找所有wi0的i值，其对应面即为自隐面，可被消除。 当找到了所有的自隐面之后，就可以确定自隐线，自隐线的确定方法是：若相交的两各平面都是自隐面的话，它们的相交边线就是自隐线，可以消除，否则为物体的可见边线。在确定了自隐面和自隐线之后，该物体余下的边线应当与其它物体一一比较

8、，以确定他们是否为其他物体所遮挡。为了提高算法的执行效率，应先将一些很明显由很容易确定的不必要的比较排除在外，常用的一些方法是最大最小测试法和边框测试法等。最大最小测试法是对要被显示的每一个物体，以其最小Z值(即最靠近视点的点)进行排序，由大到小组成一个Z值的表，比较某一边线，若它的最大Z值小于表中某一元素，则从该元素起及其以后的元素所对应的物体均不可能遮挡该边线，所以不用进一步的比较。边框测试法是为较复杂物体加上如球或长方体之类的边框，这样只要能确定某些边线完全处于这些框的上面、下面、左面、右面后前面时，边框内的物体就不会遮挡该边线。优先级1优先级2分割平面yz最大最小测试法如下：若物体1的

9、最大Z值物体2的最小Z值, 则物体1的优先级为1,物体2的优先级为2 优先级小的物体离视点距离较近 优先级小的物体可能遮挡优先极大的物体 优先级小的物体先投影(x_maxp , y_maxp )(x_maxe , y_maxe )(x_mine , y_mine )(x_minp , y_minp )边框测试法如下：判断下式：x_minpx_maxe ORx_minex_maxp ORy_minpy_maxe OR y_miney_maxpl 若上式为真，边与多边形不相交；若上式为假，二边框相交，但边与多边形可能相交，可能不相交，需进行第二次边框测试。l 第二次边框测试：把边的边框和多边形的每

10、条边的边框进行比较，进行交点测试。l 交点测试：对求出的交点，判别其是否同时在边或多边形边上(交点的x,y值是否在边的范围内)， 若是，边与多边形的边相交；若不是，边与多边形的边不相交。边线与物体的比较方法:p1p2gE完成上述工作后，还有一定数量的边要通过与其它物体的比较后方能确定其可见性。假设考虑边线P1P2的可见性，被比较的物体体矩阵为VT。采用直线的参数表示形式：P(t)=P1+(P2-P1)t 0t1 或 v=s+dt 0t1其中：v是边线上点的位置矢量，s是起始点，d为直线的方向。再构造由P1P2上一点至视点的直线，其参数表示形式为：Q(,t)=u=v+g=s+dt+g(0t1,0

11、)其中：g=0,0,-1,0,与视线方向E=0,0,1,0相反，且与t的意义相同。给定一个t值，对应边线P1P2上的一点P(t)，同样对于给定一个值，则决定了从该点至视点线段上的一点。所以Q(,t)可以看作是定义了这平面上的一点集,给定和t，就确定了这个平面上的一点。总是取正值，这是因为只有平面的这一区域才能包含遮挡上述边线的物体。如果物体于平面的交集不定，且落在点集Q(,t)中，则这个物体部分或全部地遮挡边线P1P2。否则，P1P2就不会被这个物体所遮挡。 现在把边线的对于给定物体的可见性问题，转为物体与整个点集之交是否为空集的问题。因为前面已经规定：物体中的点与体矩阵的乘积所产生的向量中所

12、有元素均为非负数。所以，H=u·VT=s·VT+t·dVT+·gVT0(0t1，0)对于物体中的每个面j=1,2,n，使得 hj=pj+tqj+wj0 (0t1，0)其中pj，qj，wj，hj分别为向量P，Q，W，H的分量：P=(p1,p2,pn)=s·VTQ=(q1,q2,qn)=d·VTW=(w1,w2,wn)=g·VTH=(h1,h2,hn)=Q(,t)·VT于是，可见与不可见的临界条件是hj=0。当hj=0时，该点恰好位于对应的平面上。若对物体的每一平面取hj=0，可得有关和t的联立方程组。为了求解这个方程

13、组，可将其中的方程两两联立，得到所有可能的和t值。可能的解的总数为n(n-1)/2。然后在(0t1,0)范围内求出t的最小值tmin和最大值tmax和相应的值。对于tminttmax,必须0，使得Q(,t)落在物体中，所有这样的t值是边线上被遮挡的点，对于那些=0的解，说明边线真正贯穿了物体。要保存这些贯穿点，然后连接这些贯穿点，得到的贯穿线再与其它物体相比较，其中可见部分就是可见贯穿线。可见贯穿线若下图所示: 红色处为贯穿点的位置紫色为可见贯穿线，黄色为不可见贯穿线 (不可见贯穿线仅列出几条)上述方法的计算量很大，下面介绍一种判别完全可见线段的方法，可节省计算量。 该方法的基本思想是判断一线

14、段的两端点是否位于视点和一可见面之间，若是，则完全可见。根据 u=s+dt+g (0t1,0) 当=0时，u表示该边线本身，此时当t=0和t=1是，分别表示该边线的两个端点，则：hj=u·VT=pj+qj·t+w·当=0和t=1时，pj+qj表示该边线另一端点和物体上j个平面的点积。因为wj0表示物体的第j个平面可见，所以，如果wj0和pj+qj0，则表示该端点位于可见面上或位于视点与可见面之间。综上，在物体中只要存在一个j，使得wj0&pj0&pj+qj0成立，则该边线完全可见。Z缓冲器算法算法原理：Z缓冲器算法是所有图像空间算法中最简单的一种隐

15、藏面消除算法。帧缓冲器用来存储图像空间中每一个象素的属性（光强度），Z缓冲器是用来存储图像空间中每一个可见象素相应的深度(或Z坐标)，是一个独立的深度缓冲器。算法主要是计算将要写入帧缓冲器象素的深度(或Z值)，并与已存储在Z缓冲器中该象素的原来深度进行比较 ：若新象素点位于帧缓冲器中原象素点的前面，则将新象素的属性写入帧缓冲器，并将相应的深度(Z值)也写入Z缓冲器；否则，帧缓冲器和Z缓冲器中的内容不变。本算法的实质是对给定的x,y,寻找最小的z(x,y)值。扫描线Z缓冲器算法算法原理：在多边形填充算法中，活性边表的使用取得了节省运行空间的效果。用同样的思想改造Z-buffer算法：将整个绘图区

16、域分割成若干个小区域，然后一个区域一个区域地显示，这样Z缓冲器的单元数只要等于一个区域内像素的个数就可以了。如果将小区域取成屏幕上的扫描线，就得到扫描线Z缓冲器算法。光线跟踪算法光线跟踪算法是一种带有强制性的方法，其基本思想是：观察者能够看到的物体是光源发出的光所照射着的物体，其中一部分的光到达人的眼睛，引起视觉。观察者看到的光可以是从物体表面反射来得，也可以是从物体背面折射或透射过来的。如果从光源出发跟踪光线，则只有其中极少部分的光线能到达观察者的眼睛，显然效率太低。所以光线跟踪算法是按反过程进行的，即从观察者到物体的方向。光线光栅网格算法原理： 假设图中的物体已变换到图像空间，且视点或观察

17、者位于z轴负无穷远处。光从观察者 出发，经过光栅屏幕上的像素点进入画面，然后沿光线方向进行跟踪，以确定该光线与画面中的哪一个物体相交。从视点至每一个像素点 所形成的光线都要与画面中的每一个物体进行比较。若光线与物体相交，则需计算它们之间所有可能的交点。若光线与画面中若干物体相交而出现多个交点，则按深度排序，具有最小Z值的交点所对应的面为此像素点的可见面，该像点的显示值由相应物体的属性(强度或颜色）所决定。观察者光栅网格 若视点不在无穷远处，则算法要复杂一些。假设观察者位于坐标系原点，方向朝Z轴，光栅平面垂直于Z轴，这样从视点对物体做透视变换且投影于光栅平面即可。 对于光线跟踪算法，最重要的部分

18、是为了确定可见面进行的求交运算。这里介绍一种减少求交运算的方法： 检查光线与包围该物体的包围体（如包围盒和包围球）是否相交； 若相交，则需计算光线与包围体内的物体的交点； 否则不交，不用进一步处理。在这里，对于包围球来说，判断一条光线与球面是否相交很简单：若包围球的球心至光线的距离小于球的半径，则该光线与包围球相交；若包围球的球心至光线的距离大于球的半径，则该光线与包围球不相交，则肯定光线与包围求内的物体不可能相交。于是只需计算点(球心)至一直线(光线)的距离。设点P1(x1,y1,z1)和P2(x2,y2,z2)连线的参数表示形式为：  P(t)=P1+(P2-P1)t 其中相应的

19、分量为： x=x1+(x2-x1)t=x1+aty=y1+(y2-y1)t=y1+btz=z1+(z2-z1)t=z1+ct点P0(x0,y0,z0)至该直线的最短距离d为： d2=(x-x0)2+(y-y0)2+(z-z0)2 此时参数t为：若d2R2(R为包围球的半径)，则光线与包围球中的物体不相交。相交无交光线无交若包围盒检查则计算量大得多。一般光线至少与包围盒的三个平面相交，而且得到的交点不一定在包围盒边界之内，因此要对每个交点作包含性检查。下面是一种简化的方法： 将光线平移和旋转，使其与z轴重合，且对包围盒作相应变换； 如果在变换后的包围盒的xmin和xmax，ymin和ymax的符

20、号皆相反，则光线与包围盒相交；否则不相交。实验环境硬件平台：PC软件(推荐)：Windows平台，Visual C+，matlab实验步骤1. 掌握算法原理；2. 依据算法，编写源程序并进行调试；3. 对运行结果进行保存与分析；4. 把源程序以文件的形式提交；5. 按格式书写实验报告。实验内容面消隐算法程序如下：void CTestView:ReadFace()/设置立方体的6个面F0.EdgeNum=4;F0.p0=0;F0.p1=1;F0.p2=2;F0.p3=3;F0.Color=RGB(255,255,0);/底面F1.EdgeNum=4;F1.p0=0;F1.p1=3;F1.p2=7

21、;F1.p3=4;F1.Color=RGB(0,255,255);/左面F2.EdgeNum=4;F2.p0=0;F2.p1=1;F2.p2=5;F2.p3=4;F2.Color=RGB(0,0,255);/前面F3.EdgeNum=4;F3.p0=1;F3.p1=2;F3.p2=6;F3.p3=5;F3.Color=RGB(0,255,0);/右面F4.EdgeNum=4;F4.p0=4;F4.p1=5;F4.p2=6;F4.p3=7;F4.Color=RGB(255,0,0);/顶面 F5.EdgeNum=4;F5.p0=3;F5.p1=2;F5.p2=6;F5.p3=7;F5.Color

22、=RGB(255,0,255);/后面bool CTestView:Painter(CDC* mdc)/画家算法 Rotate();for(Face=0;Face<6;Face+)int TotalEdge=FFace.EdgeNum;for(int edge=0;edge<TotalEdge;edge+)/边循环 int PointNumber=FFace.pedge;/面的顶点号;Pointedge=BoxNew.PPointNumber;CreatBucket();/建立桶结点Et();/用于建立边表GetMinDeep(mdc);/计算面的最小深度for(int i=0;i

23、<6;i+)/输出排序前深度 if(Fi.MinDeep>=SpecialZValue|Fi.MinDeep<=-SpecialZValue)/处理面深度无限大异常Fi.MinDeep=0;CString zBeforeSort;zBeforeSort.Format("%5.2f",Fi.MinDeep);Sorted();/深度排序for(i=0;i<6;i+)/输出排序后深度CString zAfterSort;zAfterSort.Format("%5.2f",Fi.MinDeep);DrawPolygon(mdc);/绘制

24、排序后的面return true;void CTestView:GetMinDeep(CDC* mdc)/获得每个面的最小深度FFace.MinDeep=SpecialZValue;doubleCurDeep=0.0;/当前扫描线的深度doubleDeepStep=0.0;/当前扫描线随着x增长的深度步长doubleA=0.0;/平面方程系数AdoubleB=0.0;/平面方程系数BdoubleC=0.0;/平面方程系数CdoubleD=0.0;/平面方程系数DA=(Point1.y-Point2.y)*(Point1.z-Point3.z)-(Point1.y-Point3.y)*(Poin

25、t1.z-Point2.z);B=(Point1.x-Point3.x)*(Point1.z-Point2.z)-(Point1.z-Point3.z)*(Point1.x-Point2.x);C=(Point1.x-Point2.x)*(Point1.y-Point3.y)-(Point1.x-Point3.x)*(Point1.y-Point2.y);D=-A*Point1.x-B*Point1.y-C*Point1.z;/计算curDeep;从x=xMin开始计算，此时针对yiDeepStep=-A/C;HeadE=NULL;for(CurrentB=HeadB;CurrentB!=NULL;CurrentB=CurrentB->next)/访问所有桶结点for(CurrentE=CurrentB->p;CurrentE!=NULL;CurrentE=CurrentE->next)/访问桶中排序前的边结点Edge *TEdge=new Edge;TEdge->x=CurrentE->x;TEdge->yMax=CurrentE->yMax;TEdge->k=CurrentE->k;TEdge->next=NULL;AddAet(TEdge);/将该边插入临时Aet表AetOrder();